美图数据研发工程师面试绝对会被问到的问题

ConcurrentHashMap

JDK1.7的实现

在JDK1.7版本中，ConcurrentHashMap的数据结构是由一个Segment数组和多个HashEntry组成，如下图所示：

Segment数组的意义就是将一个大的table分割成多个小的table来进行加锁，也就是锁分离技术，而每一个Segment元素存储的是HashEntry数组+链表，这个和HashMap的数据存储结构一样

初始化

ConcurrentHashMap的初始化是会通过位与运算来初始化Segment的大小，用ssize来表示，如下所示：

int sshift = 0;
int ssize = 1;
while (ssize < concurrencyLevel) {
    ++sshift;
    ssize <<= 1;
}

因为ssize用位于运算来计算（ssize <<=1），所以Segment的大小取值都是以2的N次方，无关concurrencyLevel的取值，当然concurrencyLevel最大只能用16位的二进制来表示，即65536，换句话说，Segment的大小最多65536个，没有指定concurrencyLevel元素初始化，Segment的大小ssize默认为16

每一个Segment元素下的HashEntry的初始化也是按照位于运算来计算，用cap来表示，如下所示：

int cap = 1;
while (cap < c)
    cap <<= 1;

如上所示，HashEntry大小的计算也是2的N次方（cap <<=1）， cap的初始值为1，所以HashEntry最小的容量为2

put操作

static class Segment extends ReentrantLock implements Serializable

从上Segment的继承体系可以看出，Segment实现了ReentrantLock，也就带有锁的功能，当执行put操作时，会进行第一次key的hash来定位Segment的位置，如果该Segment还没有初始化，即通过CAS操作进行赋值，然后进行第二次hash操作，找到相应的HashEntry的位置，这里会利用继承过来的锁的特性，在将数据插入指定的HashEntry位置时（链表的尾端），会通过继承ReentrantLock的tryLock（）方法尝试去获取锁，如果获取成功就直接插入相应的位置，如果已经有线程获取该Segment的锁，那当前线程会以自旋的方式去继续的调用tryLock（）方法去获取锁，超过指定次数就挂起，等待唤醒。

get操作

ConcurrentHashMap的get操作跟HashMap类似，只是ConcurrentHashMap第一次需要经过一次hash定位到Segment的位置，然后再hash定位到指定的HashEntry，遍历该HashEntry下的链表进行对比，成功就返回，不成功就返回null。

size操作

计算ConcurrentHashMap的元素大小是一个并发操作，就是在计算size的时候，还在并发的插入数据，可能会导致所计算出来的size和实际的size有相差（即在return size的时候，插入了多个数据），要解决这个问题，JDK1.7版本用两种方案：

第一种方案他会使用不加锁的模式去尝试多次计算ConcurrentHashMap的size，最多三次，比较前后两次计算的结果，结果一致就认为当前没有元素加入，计算的结果是准确的 第二种方案是如果第一种方案不符合，他就会给每个Segment加上锁，然后计算ConcurrentHashMap的size返回

JDK1.8的实现

JDK1.8的实现已经摒弃了Segment的概念，而是直接用Node数组+链表+红黑树的数据结构来实现，并发控制使用Synchronized和CAS来操作，整个看起来就像是优化过且线程安全的HashMap，虽然在JDK1.8中还能看到Segment的数据结构，但是已经简化了属性，只是为了兼容旧版本。

初始化

ConcurrentHashMap的初始化其实是一个空实现，并没有做任何事，这也是和其他的集合类有区别的地方，初始化操作并不是在构造函数实现的，而是在put操作中实现，当然ConcurrentHashMap还提供了其他的构造函数，有指定容量大小或者指定负载因子，跟HashMap一样，这里就不做介绍了。

put操作

put的过程很清晰，对当前的table进行无条件自循环直到put成功，可以分成以下六步流程来概述：

如果没有初始化就先调用initTable（）方法来进行初始化过程 如果没有hash冲突就直接CAS插入 如果还在进行扩容操作就先进行扩容 如果存在hash冲突，就加锁来保证线程安全，这里有两种情况，一种是链表形式就直接遍历到尾端插入，一种是红黑树就按照红黑树结构插入， 最后一个如果该链表的容量大于等于阈值8，就要先转换成黑红树的结构，break再一次进入循环 如果添加成功就调用addCount（）方法统计size，并且检查是否需要扩容

get操作

ConcurrentHashMap的get操作的流程很简单，也很清晰，可以分为三个步骤来描述：

计算hash值，定位到该table索引位置，如果是首节点符合就返回 如果遇到扩容的时候，会调用标志正在扩容节点ForwardingNode的find方法，查找该节点，匹配就返回 以上都不符合的话，就往下遍历节点，匹配就返回，否则最后就返回null

总结

其实可以看出JDK1.8版本的ConcurrentHashMap的数据结构已经接近HashMap，相对而言，ConcurrentHashMap只是增加了同步的操作来控制并发，从JDK1.7版本的ReentrantLock+Segment+HashEntry，到JDK1.8版本中synchronized+CAS+HashEntry+红黑树,相对而言，总结如下：

JDK1.8的实现降低锁的粒度，JDK1.7版本锁的粒度是基于Segment的，包含多个HashEntry，而JDK1.8锁的粒度就是HashEntry（首节点） JDK1.8版本的数据结构变得更加简单，使得操作也更加清晰流畅，因为已经使用synchronized来进行同步，所以不需要分段锁的概念，也就不需要Segment这种数据结构了，由于粒度的降低，实现的复杂度也增加了 JDK1.8使用红黑树来优化链表，基于长度很长的链表的遍历是一个很漫长的过程，而红黑树的遍历效率是很快的，代替一定阈值的链表，这样形成一个最佳拍档 JDK1.8为什么使用内置锁synchronized来代替重入锁ReentrantLock

jvisualvm工具

jdk自带的jvisualvm工具，该工具可以用来监控java运行程序的cpu、内存、线程等的使用情况。并且使用图表的方式监控java程序、还具有远程监控能力。

Hive中元数据表的关系和含义

Hive版本的元数据表

version表

字段	含义
VER_ID	id主键
SCHEMA_VERSION	Hive 版本
VERSION_COMMENT	版本说明

Hive数据库相关元数据表

DBS表

字段	含义
DB_ID	数据库ID
DESC	数据库描述
DB_LOCATION_URI	数据库HDFS路径
NAME	Hive数据库名
OWNER_NAME	Hive数据库所有者用户名
OWNER_TYPE	Hive所有者角色

Hive表和视图相关的元数据表

TBLS表

字段	含义
TBL_ID	表ID
CREATE_TIME	创建时间
DB_ID	数据库ID
LAST_ACCESS_TIME	上次访问时间
OWNER	所有者
RETENTION	保留字段
SD_ID	序列化配置信息
TBL_NAME	表名
TBL_TYPE	表类型
VIEW_EXPANDED_TEXT	视图的详细HQL
VIEW_ORIGINAL_TEXT	视图的原始HQL

TTABLE_PARAMS表

字段	含义
TBL_ID	表ID
PARAM_KEY	表属性名
PARAM_VALUE	表属性值

Hive 文件存储信息相关的元数据

SDS表

字段	含义
SD_ID	存储信息ID
CD_ID	字段信息ID
INPUT_FORMAT	文件输入格式
IS_COMPRESSED	是否压缩
IS_STOREDASSUBDIRECTORIES	是否以子目录存储
LOCATION	HDFS路径
NUM_BUCKETS	分桶
OUTPUT_FORMAT	文件输出格式
SERDE_ID	序列化类ID

SERDES表

字段	含义
SERDE_ID	序列化类配置ID
NAME	序列化类别名
SLIB	序列化类

SERDE_PARAMS 表

字段	含义
SERDE_ID	序列化类配置ID
PARAM_KEY	属性名
PARAM_VALUE	属性值

Hive表字段相关元数据表

COLUMNS_V2表

字段	含义
CD_ID	字段信息ID
COMMENT	字段注释
COLUMN_NAME	字段名
TYPE_NAME	字段类型
INTEGER_IDX	字段顺序

Hive表分区相关元数据表

PARTITIONS 表

字段	含义
PART_ID	分区ID
CREATE_TIME	分区创建时间
LAST_ACCESS_TIME	最后一次访问时间
PART_NAME	分区名
SD_ID	分区存储ID
TBL_ID	表ID

PARTITION_KEYS 表

字段	含义
TBL_ID	表ID
PKEY_COMMENT	分区字段名说明
PKEY_NAME	分区字段名
PKEY_TYPE	分区字段类型
INTEGER_IDX	分区字段顺序

PARTITION_KEY_VALS 表

字段	含义
PART_ID	分区ID
PART_KEY_VAL	分区字段值
INTEGER_IDX	分区字段顺序

PARTITION_PARAMS 表

字段	含义
PART_ID	分区ID
PARAM_KEY	分区属性名
PARAM_VALUE	分区属性值

各表之间主键的关系图

AST Tree & Query Block & Operator Tree

SQL生成AST Tree

HiveLexerX，HiveParser分别是Antlr对语法文件编译后自动生成的词法解析和语法解析类，在这两个类中进行复杂的解析，具体代码在ParseDriver.java类中：

分为以下三步骤：

词法解析，忽略关键词的大小 语法解析 转换为AST Tree

SQL基本组成单元Query Block

QueryBlock是一条SQL最基本的组成单元，包括三个部分：输入源，计算过程，输出。简单来讲一个Query Block就是一个子查询。

QueryBlock中几个重要的属性在QB类和QBParseInfo类中：

QB#aliasToSubq（表示QB类的aliasToSubq属性）保存子查询的QB对象，aliasToSubq key值是子查询的别名 QB#qbp即QBParseInfo保存一个基本SQL单元中的给个操作部分的AST Tree结构，QBParseInfo#nameToDest这个HashMap保存查询单元的输出，key的形式是inclause-i（由于Hive支持Multi Insert语句，所以可能有多个输出），value是对应的ASTNode节点，即TOK_DESTINATION节点。类QBParseInfo其余HashMap属性分别保存输出和各个操作的ASTNode节点的对应关系 QBParseInfo#JoinExpr保存TOK_JOIN节点。QB#QBJoinTree是对Join语法树的结构化 QB#qbm保存每个输入表的元信息，比如表在HDFS上的路径，保存表数据的文件格式等 QBExpr这个对象是为了表示Union操作

逻辑操作符Operator

Hive最终生成的MapReduce任务，Map阶段和Reduce阶段均由OperatorTree组成。逻辑操作符，就是在Map阶段或者Reduce阶段完成单一特定的操作。

Operator类的主要属性和方法如下：

RowSchema表示Operator的输出字段 InputObjInspector outputObjInspector解析输入和输出字段 processOp接收父Operator传递的数据，forward将处理好的数据传递给子Operator处理 Hive每一行数据经过一个Operator处理之后，会对字段重新编号，colExprMap记录每个表达式经过当前Operator处理前后的名称对应关系，在下一个阶段逻辑优化阶段用来回溯字段名 由于Hive的MapReduce程序是一个动态的程序，即不确定一个MapReduce Job会进行什么运算，可能是Join，也可能是GroupBy，所以Operator将所有运行时需要的参数保存在OperatorDesc中，OperatorDesc在提交任务前序列化到HDFS上，在MapReduce任务执行前从HDFS读取并反序列化

参考文章：https://tech.meituan.com/hive-sql-to-mapreduce.html 仅仅是粗略的了解了一下，后续进行详细补充

提高shuffle操作的并行度是否能解决数据倾斜

方案实现思路：在对RDD执行shuffle算子时，给shuffle算子传入一个参数，比如reduceByKey(1000)，该参数就设置了这个shuffle算子执行时shuffle read task的数量。对于Spark SQL中的shuffle类语句，比如group by、join等，需要设置一个参数，即spark.sql.shuffle.partitions，该参数代表了shuffle read task的并行度，该值默认是200，对于很多场景来说都有点过小。

方案实现原理：增加shuffle read task的数量，可以让原本分配给一个task的多个key分配给多个task，从而让每个task处理比原来更少的数据。举例来说，如果原本有5个key，每个key对应10条数据，这5个key都是分配给一个task的，那么这个task就要处理50条数据。而增加了shuffle read task以后，每个task就分配到一个key，即每个task就处理10条数据，那么自然每个task的执行时间都会变短了。具体原理如下图所示。

方案优点：实现起来比较简单，可以有效缓解和减轻数据倾斜的影响。

方案缺点：只是缓解了数据倾斜而已，没有彻底根除问题，根据实践经验来看，其效果有限。