首页 > 资讯 > 其他综合 >

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

2018-04-21

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

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 版本说明
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的执行时间都会变短了。具体原理如下图所示。

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

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

相关文章
最新文章
热点推荐