美图数据研发工程师面试绝对会被问到的问题ConcurrentHashMapJDK1.7的实现在JDK1.7版本中，ConcurrentHas
hMap的数据结构是由一个Segment数组和多个HashEntry组成，如下图所示：Segment数组的意义就是将一个大的tab
le分割成多个小的table来进行加锁，也就是锁分离技术，而每一个Segment元素存储的是HashEntry数组+链表，这个和H
ashMap的数据存储结构一样。乐淘棋牌http://www.jiekeqipai.net初始化ConcurrentHashMap
的初始化是会通过位与运算来初始化Segment的大小，用ssize来表示，如下所示：intsshift=0;intssiz
e=1;while(ssize为ssize用位于运算来计算（ssize<<=1），所以Segment的大小取值都是以2的N次方，无关concurrencyLe
vel的取值，当然concurrencyLevel最大只能用16位的二进制来表示，即65536，换句话说，Segment的大小最多
65536个，没有指定concurrencyLevel元素初始化，Segment的大小ssize默认为16每一个Segment元素
下的HashEntry的初始化也是按照位于运算来计算，用cap来表示，如下所示：intcap=1;while(cap<
c)cap<<=1;如上所示，HashEntry大小的计算也是2的N次方（cap<<=1），cap的初始值为1，所以Ha
shEntry最小的容量为2put操作staticclassSegmentextendsReentrantLoc
kimplementsSerializable从上Segment的继承体系可以看出，Segment实现了ReentrantLo
ck，也就带有锁的功能，当执行put操作时，会进行第一次key的hash来定位Segment的位置，如果该Segment还没有初始
化，即通过CAS操作进行赋值，然后进行第二次hash操作，找到相应的HashEntry的位置，这里会利用继承过来的锁的特性，在将数
据插入指定的HashEntry位置时（链表的尾端），会通过继承ReentrantLock的tryLock（）方法尝试去获取锁，如果
获取成功就直接插入相应的位置，如果已经有线程获取该Segment的锁，那当前线程会以自旋的方式去继续的调用tryLock（）方法去
获取锁，超过指定次数就挂起，等待唤醒。get操作ConcurrentHashMap的get操作跟HashMap类似，只是Concu
rrentHashMap第一次需要经过一次hash定位到Segment的位置，然后再hash定位到指定的HashEntry，遍历该
HashEntry下的链表进行对比，成功就返回，不成功就返回null。size操作计算ConcurrentHashMap的元素大小
是一个并发操作，就是在计算size的时候，还在并发的插入数据，可能会导致所计算出来的size和实际的size有相差（即在retur
nsize的时候，插入了多个数据），要解决这个问题，JDK1.7版本用两种方案：第一种方案他会使用不加锁的模式去尝试多次计算Co
ncurrentHashMap的size，最多三次，比较前后两次计算的结果，结果一致就认为当前没有元素加入，计算的结果是准确的第
二种方案是如果第一种方案不符合，他就会给每个Segment加上锁，然后计算ConcurrentHashMap的size返回JDK1
.8的实现JDK1.8的实现已经摒弃了Segment的概念，而是直接用Node数组+链表+红黑树的数据结构来实现，并发控制使用Sy
nchronized和CAS来操作，整个看起来就像是优化过且线程安全的HashMap，虽然在JDK1.8中还能看到Segment的
数据结构，但是已经简化了属性，只是为了兼容旧版本。初始化ConcurrentHashMap的初始化其实是一个空实现，并没有做任何事
，这也是和其他的集合类有区别的地方，初始化操作并不是在构造函数实现的，而是在put操作中实现，当然ConcurrentHashMa
p还提供了其他的构造函数，有指定容量大小或者指定负载因子，跟HashMap一样，这里就不做介绍了。put操作put的过程很清晰，对
当前的table进行无条件自循环直到put成功，可以分成以下六步流程来概述：如果没有初始化就先调用initTable（）方法来进行
初始化过程如果没有hash冲突就直接CAS插入如果还在进行扩容操作就先进行扩容如果存在hash冲突，就加锁来保证线程安全，这
里有两种情况，一种是链表形式就直接遍历到尾端插入，一种是红黑树就按照红黑树结构插入，最后一个如果该链表的容量大于等于阈值8，就要
先转换成黑红树的结构，break再一次进入循环如果添加成功就调用addCount（）方法统计size，并且检查是否需要扩容get
操作ConcurrentHashMap的get操作的流程很简单，也很清晰，可以分为三个步骤来描述：计算hash值，定位到该tabl
e索引位置，如果是首节点符合就返回如果遇到扩容的时候，会调用标志正在扩容节点ForwardingNode的find方法，查找该节
点，匹配就返回以上都不符合的话，就往下遍历节点，匹配就返回，否则最后就返回null总结其实可以看出JDK1.8版本的Concur
rentHashMap的数据结构已经接近HashMap，相对而言，ConcurrentHashMap只是增加了同步的操作来控制并发
，从JDK1.7版本的ReentrantLock+Segment+HashEntry，到JDK1.8版本中synchronized
+CAS+HashEntry+红黑树,相对而言，总结如下：JDK1.8的实现降低锁的粒度，JDK1.7版本锁的粒度是基于Segme
nt的，包含多个HashEntry，而JDK1.8锁的粒度就是HashEntry（首节点）JDK1.8版本的数据结构变得更加简单
，使得操作也更加清晰流畅，因为已经使用synchronized来进行同步，所以不需要分段锁的概念，也就不需要Segment这种数据
结构了，由于粒度的降低，实现的复杂度也增加了JDK1.8使用红黑树来优化链表，基于长度很长的链表的遍历是一个很漫长的过程，而红黑
树的遍历效率是很快的，代替一定阈值的链表，这样形成一个最佳拍档JDK1.8为什么使用内置锁synchronized来代替重入锁R
eentrantLock。乐淘棋牌http://www.455573.comjvisualvm工具jdk自带的jvisualvm工
具，该工具可以用来监控java运行程序的cpu、内存、线程等的使用情况。并且使用图表的方式监控java程序、还具有远程监控能力。H
ive中元数据表的关系和含义Hive版本的元数据表version表字段含义VER_IDid主键SCHEMA_VERSIONHive
版本VERSION_COMMENT版本说明数据库相关元数据表">Hive数据库相关元数据表DBS表字段含义DB_ID数据库IDD
ESC数据库描述DB_LOCATION_URI数据库HDFS路径NAMEHive数据库名OWNER_NAMEHive数据库所有者用
户名OWNER_TYPEHive所有者角色Hive表和视图相关的元数据表TBLS表字段含义TBL_ID表IDCREATE_TIME
创建时间DB_ID数据库IDLAST_ACCESS_TIME上次访问时间OWNER所有者RETENTION保留字段SD_ID序列化
配置信息TBL_NAME表名TBL_TYPE表类型VIEW_EXPANDED_TEXT视图的详细HQLVIEW_ORIGINAL_
TEXT视图的原始HQLTTABLE_PARAMS表字段含义TBL_ID表IDPARAM_KEY表属性名PARAM_VALUE表属
性值Hive文件存储信息相关的元数据SDS表字段含义SD_ID存储信息IDCD_ID字段信息IDINPUT_FORMAT文件输入
格式IS_COMPRESSED是否压缩IS_STOREDASSUBDIRECTORIES是否以子目录存储LOCATIONHDFS路
径NUM_BUCKETS分桶OUTPUT_FORMAT文件输出格式SERDE_ID序列化类IDSERDES表字段含义SERDE_I
D序列化类配置IDNAME序列化类别名SLIB序列化类SERDE_PARAMS表字段含义SERDE_ID序列化类配置IDPARA
M_KEY属性名PARAM_VALUE属性值Hive表字段相关元数据表COLUMNS_V2表字段含义CD_ID字段信息IDCOMM
ENT字段注释COLUMN_NAME字段名TYPE_NAME字段类型INTEGER_IDX字段顺序Hive表分区相关元数据表PAR
TITIONS表字段含义PART_ID分区IDCREATE_TIME分区创建时间LAST_ACCESS_TIME最后一次访问时间
PART_NAME分区名SD_ID分区存储IDTBL_ID表IDPARTITION_KEYS表字段含义TBL_ID表IDPKEY
_COMMENT分区字段名说明PKEY_NAME分区字段名PKEY_TYPE分区字段类型INTEGER_IDX分区字段顺序PART
ITION_KEY_VALS表字段含义PART_ID分区IDPART_KEY_VAL分区字段值INTEGER_IDX分区字段顺序
PARTITION_PARAMS表字段含义PART_ID分区IDPARAM_KEY分区属性名PARAM_VALUE分区属性值各表
之间主键的关系图ASTTree&QueryBlock&OperatorTreeSQL生成ASTTreeHiveLe
xerX，HiveParser分别是Antlr对语法文件编译后自动生成的词法解析和语法解析类，在这两个类中进行复杂的解析，具体代码
在ParseDriver.java类中：分为以下三步骤：词法解析，忽略关键词的大小语法解析转换为ASTTreeSQL基本组成
单元QueryBlockQueryBlock是一条SQL最基本的组成单元，包括三个部分：输入源，计算过程，输出。简单来讲一个Qu
eryBlock就是一个子查询。QueryBlock中几个重要的属性在QB类和QBParseInfo类中：QB#aliasToS
ubq（表示QB类的aliasToSubq属性）保存子查询的QB对象，aliasToSubqkey值是子查询的别名QB#qbp
即QBParseInfo保存一个基本SQL单元中的给个操作部分的ASTTree结构，QBParseInfo#nameToDest
这个HashMap保存查询单元的输出，key的形式是inclause-i（由于Hive支持MultiInsert语句，所以可能有
多个输出），value是对应的ASTNode节点，即TOK_DESTINATION节点。类QBParseInfo其余HashMap
属性分别保存输出和各个操作的ASTNode节点的对应关系QBParseInfo#JoinExpr保存TOK_JOIN节点。QB#
QBJoinTree是对Join语法树的结构化QB#qbm保存每个输入表的元信息，比如表在HDFS上的路径，保存表数据的文件格式
等QBExpr这个对象是为了表示Union操作逻辑操作符OperatorHive最终生成的MapReduce任务，Map阶段和R
educe阶段均由OperatorTree组成。逻辑操作符，就是在Map阶段或者Reduce阶段完成单一特定的操作。Operato
r类的主要属性和方法如下：RowSchema表示Operator的输出字段InputObjInspectoroutputObj
Inspector解析输入和输出字段processOp接收父Operator传递的数据，forward将处理好的数据传递给子Op
erator处理Hive每一行数据经过一个Operator处理之后，会对字段重新编号，colExprMap记录每个表达式经过当前
Operator处理前后的名称对应关系，在下一个阶段逻辑优化阶段用来回溯字段名由于Hive的MapReduce程序是一个动态的程
序，即不确定一个MapReduceJob会进行什么运算，可能是Join，也可能是GroupBy，所以Operator将所有运行时
需要的参数保存在OperatorDesc中，OperatorDesc在提交任务前序列化到HDFS上，在MapReduce任务执行前
从HDFS读取并反序列化参考文章：https://tech.meituan.com/hive-sql-to-mapreduce.h
tml仅仅是粗略的了解了一下，后续进行详细补充提高shuffle操作的并行度是否能解决数据倾斜方案实现思路：在对RDD执行shu
ffle算子时，给shuffle算子传入一个参数，比如reduceByKey(1000)，该参数就设置了这个shuffle算子执行
时shufflereadtask的数量。对于SparkSQL中的shuffle类语句，比如groupby、join等，需要
设置一个参数，即spark.sql.shuffle.partitions，该参数代表了shufflereadtask的并行度，该值默认是200，对于很多场景来说都有点过小。638棋牌http://www.dadiqipaigw.cn方案实现原理：增加shufflereadtask的数量，可以让原本分配给一个task的多个key分配给多个task，从而让每个task处理比原来更少的数据。举例来说，如果原本有5个key，每个key对应10条数据，这5个key都是分配给一个task的，那么这个task就要处理50条数据。而增加了shufflereadtask以后，每个task就分配到一个key，即每个task就处理10条数据，那么自然每个task的执行时间都会变短了。具体原理如下图所示。方案优点：实现起来比较简单，可以有效缓解和减轻数据倾斜的影响。方案缺点：只是缓解了数据倾斜而已，没有彻底根除问题，根据实践经验来看，其效果有限。 |
|
