美圖數(shù)據(jù)研發(fā)工程師面試絕對會(huì)被問到的問題

美圖數(shù)據(jù)研發(fā)工程師面試絕對會(huì)被問到的問題ConcurrentHashMapJDK1.7的實(shí)現(xiàn)在JDK1.7版本中，ConcurrentHashMap的數(shù)據(jù)結(jié)構(gòu)是由一個(gè)Segment數(shù)組和多個(gè)HashEntry組成，如下圖所示：

Segment數(shù)組的意義就是將一個(gè)大的table分割成多個(gè)小的table來進(jìn)行加鎖，也就是鎖分離技術(shù)，而每一個(gè)Segment元素存儲(chǔ)的是HashEntry數(shù)組+鏈表，這個(gè)和HashMap的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)一樣。樂淘棋牌初始化ConcurrentHashMap的初始化是會(huì)通過位與運(yùn)算來初始化Segment的大小，用ssize來表示，如下所示：intsshift=0;intssize=1;while(ssize<concurrencyLevel){++sshift;ssize<<=1;}因?yàn)閟size用位于運(yùn)算來計(jì)算（ssize<<=1），所以Segment的大小取值都是以2的N次方，無關(guān)concurrencyLevel的取值，當(dāng)然concurrencyLevel最大只能用16位的二進(jìn)制來表示，即65536，換句話說，Segment的大小最多65536個(gè)，沒有指定concurrencyLevel元素初始化，Segment的大小ssize默認(rèn)為16每一個(gè)Segment元素下的HashEntry的初始化也是按照位于運(yùn)算來計(jì)算，用cap來表示，如下所示：intcap=1;while(cap<c)cap<<=1;如上所示，HashEntry大小的計(jì)算也是2的N次方（cap<<=1），cap的初始值為1，所以HashEntry最小的容量為2put操作staticclassSegment<k,v>extendsReentrantLockimplementsSerializable從上Segment的繼承體系可以看出，Segment實(shí)現(xiàn)了ReentrantLock，也就帶有鎖的功能，當(dāng)執(zhí)行put操作時(shí)，會(huì)進(jìn)行第一次key的hash來定位Segment的位置，如果該Segment還沒有初始化，即通過CAS操作進(jìn)行賦值，然后進(jìn)行第二次hash操作，找到相應(yīng)的HashEntry的位置，這里會(huì)利用繼承過來的鎖的特性，在將數(shù)據(jù)插入指定的HashEntry位置時(shí)（鏈表的尾端），會(huì)通過繼承ReentrantLock的tryLock（）方法嘗試去獲取鎖，如果獲取成功就直接插入相應(yīng)的位置，如果已經(jīng)有線程獲取該Segment的鎖，那當(dāng)前線程會(huì)以自旋的方式去繼續(xù)的調(diào)用tryLock（）方法去獲取鎖，超過指定次數(shù)就掛起，等待喚醒。get操作ConcurrentHashMap的get操作跟HashMap類似，只是ConcurrentHashMap第一次需要經(jīng)過一次hash定位到Segment的位置，然后再hash定位到指定的HashEntry，遍歷該HashEntry下的鏈表進(jìn)行對比，成功就返回，不成功就返回null。size操作計(jì)算ConcurrentHashMap的元素大小是一個(gè)并發(fā)操作，就是在計(jì)算size的時(shí)候，還在并發(fā)的插入數(shù)據(jù)，可能會(huì)導(dǎo)致所計(jì)算出來的size和實(shí)際的size有相差（即在returnsize的時(shí)候，插入了多個(gè)數(shù)據(jù)），要解決這個(gè)問題，JDK1.7版本用兩種方案：第一種方案他會(huì)使用不加鎖的模式去嘗試多次計(jì)算ConcurrentHashMap的size，最多三次，比較前后兩次計(jì)算的結(jié)果，結(jié)果一致就認(rèn)為當(dāng)前沒有元素加入，計(jì)算的結(jié)果是準(zhǔn)確的第二種方案是如果第一種方案不符合，他就會(huì)給每個(gè)Segment加上鎖，然后計(jì)算ConcurrentHashMap的size返回JDK1.8的實(shí)現(xiàn)JDK1.8的實(shí)現(xiàn)已經(jīng)摒棄了Segment的概念，而是直接用Node數(shù)組+鏈表+紅黑樹的數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)，并發(fā)控制使用Synchronized和CAS來操作，整個(gè)看起來就像是優(yōu)化過且線程安全的HashMap，雖然在JDK1.8中還能看到Segment的數(shù)據(jù)結(jié)構(gòu)，但是已經(jīng)簡化了屬性，只是為了兼容舊版本。

初始化ConcurrentHashMap的初始化其實(shí)是一個(gè)空實(shí)現(xiàn)，并沒有做任何事，這也是和其他的集合類有區(qū)別的地方，初始化操作并不是在構(gòu)造函數(shù)實(shí)現(xiàn)的，而是在put操作中實(shí)現(xiàn)，當(dāng)然ConcurrentHashMap還提供了其他的構(gòu)造函數(shù)，有指定容量大小或者指定負(fù)載因子，跟HashMap一樣，這里就不做介紹了。put操作put的過程很清晰，對當(dāng)前的table進(jìn)行無條件自循環(huán)直到put成功，可以分成以下六步流程來概述：如果沒有初始化就先調(diào)用initTable（）方法來進(jìn)行初始化過程如果沒有hash沖突就直接CAS插入如果還在進(jìn)行擴(kuò)容操作就先進(jìn)行擴(kuò)容如果存在hash沖突，就加鎖來保證線程安全，這里有兩種情況，一種是鏈表形式就直接遍歷到尾端插入，一種是紅黑樹就按照紅黑樹結(jié)構(gòu)插入，最后一個(gè)如果該鏈表的容量大于等于閾值8，就要先轉(zhuǎn)換成黑紅樹的結(jié)構(gòu)，break再一次進(jìn)入循環(huán)如果添加成功就調(diào)用addCount（）方法統(tǒng)計(jì)size，并且檢查是否需要擴(kuò)容get操作ConcurrentHashMap的get操作的流程很簡單，也很清晰，可以分為三個(gè)步驟來描述：計(jì)算hash值，定位到該table索引位置，如果是首節(jié)點(diǎn)符合就返回如果遇到擴(kuò)容的時(shí)候，會(huì)調(diào)用標(biāo)志正在擴(kuò)容節(jié)點(diǎn)ForwardingNode的find方法，查找該節(jié)點(diǎn)，匹配就返回以上都不符合的話，就往下遍歷節(jié)點(diǎn)，匹配就返回，否則最后就返回null總結(jié)其實(shí)可以看出JDK1.8版本的ConcurrentHashMap的數(shù)據(jù)結(jié)構(gòu)已經(jīng)接近HashMap，相對而言，ConcurrentHashMap只是增加了同步的操作來控制并發(fā)，從JDK1.7版本的ReentrantLock+Segment+HashEntry，到JDK1.8版本中synchronized+CAS+HashEntry+紅黑樹,相對而言，總結(jié)如下：JDK1.8的實(shí)現(xiàn)降低鎖的粒度，JDK1.7版本鎖的粒度是基于Segment的，包含多個(gè)HashEntry，而JDK1.8鎖的粒度就是HashEntry（首節(jié)點(diǎn)）JDK1.8版本的數(shù)據(jù)結(jié)構(gòu)變得更加簡單，使得操作也更加清晰流暢，因?yàn)橐呀?jīng)使用synchronized來進(jìn)行同步，所以不需要分段鎖的概念，也就不需要Segment這種數(shù)據(jù)結(jié)構(gòu)了，由于粒度的降低，實(shí)現(xiàn)的復(fù)雜度也增加了JDK1.8使用紅黑樹來優(yōu)化鏈表，基于長度很長的鏈表的遍歷是一個(gè)很漫長的過程，而紅黑樹的遍歷效率是很快的，代替一定閾值的鏈表，這樣形成一個(gè)最佳拍檔JDK1.8為什么使用內(nèi)置鎖synchronized來代替重入鎖ReentrantLock。樂淘棋牌jvisualvm工具jdk自帶的jvisualvm工具，該工具可以用來監(jiān)控java運(yùn)行程序的cpu、內(nèi)存、線程等的使用情況。并且使用圖表的方式監(jiān)控java程序、還具有遠(yuǎn)程監(jiān)控能力。Hive中元數(shù)據(jù)表的關(guān)系和含義Hive版本的元數(shù)據(jù)表version表字段含義VER_IDid主鍵SCHEMA_VERSIONHive版本VERSION_COMMENT版本說明數(shù)據(jù)庫相關(guān)元數(shù)據(jù)表">Hive數(shù)據(jù)庫相關(guān)元數(shù)據(jù)表DBS表字段含義DB_ID數(shù)據(jù)庫IDDESC數(shù)據(jù)庫描述DB_LOCATION_URI數(shù)據(jù)庫HDFS路徑NAMEHive數(shù)據(jù)庫名OWNER_NAMEHive數(shù)據(jù)庫所有者用戶名OWNER_TYPEHive所有者角色Hive表和視圖相關(guān)的元數(shù)據(jù)表TBLS表字段含義TBL_ID表IDCREATE_TIME創(chuàng)建時(shí)間DB_ID數(shù)據(jù)庫IDLAST_ACCESS_TIME上次訪問時(shí)間OWNER所有者RETENTION保留字段SD_ID序列化配置信息TBL_NAME表名TBL_TYPE表類型VIEW_EXPANDED_TEXT視圖的詳細(xì)HQLVIEW_ORIGINAL_TEXT視圖的原始HQLTTABLE_PARAMS表字段含義TBL_ID表IDPARAM_KEY表屬性名PARAM_VALUE表屬性值Hive文件存儲(chǔ)信息相關(guān)的元數(shù)據(jù)SDS表字段含義SD_ID存儲(chǔ)信息IDCD_ID字段信息IDINPUT_FORMAT文件輸入格式IS_COMPRESSED是否壓縮IS_STOREDASSUBDIRECTORIES是否以子目錄存儲(chǔ)LOCATIONHDFS路徑NUM_BUCKETS分桶OUTPUT_FORMAT文件輸出格式SERDE_ID序列化類IDSERDES表字段含義SERDE_ID序列化類配置IDNAME序列化類別名SLIB序列化類SERDE_PARAMS表字段含義SERDE_ID序列化類配置IDPARAM_KEY屬性名PARAM_VALUE屬性值Hive表字段相關(guān)元數(shù)據(jù)表COLUMNS_V2表字段含義CD_ID字段信息IDCOMMENT字段注釋COLUMN_NAME字段名TYPE_NAME字段類型INTEGER_IDX字段順序Hive表分區(qū)相關(guān)元數(shù)據(jù)表PARTITIONS表字段含義PART_ID分區(qū)IDCREATE_TIME分區(qū)創(chuàng)建時(shí)間LAST_ACCESS_TIME最后一次訪問時(shí)間PART_NAME分區(qū)名SD_ID分區(qū)存儲(chǔ)IDTBL_ID表IDPARTITION_KEYS表字段含義TBL_ID表IDPKEY_COMMENT分區(qū)字段名說明PKEY_NAME分區(qū)字段名PKEY_TYPE分區(qū)字段類型INTEGER_IDX分區(qū)字段順序PARTITION_KEY_VALS表字段含義PART_ID分區(qū)IDPART_KEY_VAL分區(qū)字段值INTEGER_IDX分區(qū)字段順序PARTITION_PARAMS表字段含義PART_ID分區(qū)IDPARAM_KEY分區(qū)屬性名PARAM_VALUE分區(qū)屬性值各表之間主鍵的關(guān)系圖ASTTree&QueryBlock&OperatorTreeSQL生成ASTTreeHiveLexerX，HiveParser分別是Antlr對語法文件編譯后自動(dòng)生成的詞法解析和語法解析類，在這兩個(gè)類中進(jìn)行復(fù)雜的解析，具體代碼在ParseDriver.java類中：

分為以下三步驟：詞法解析，忽略關(guān)鍵詞的大小語法解析轉(zhuǎn)換為ASTTreeSQL基本組成單元QueryBlockQueryBlock是一條SQL最基本的組成單元，包括三個(gè)部分：輸入源，計(jì)算過程，輸出。簡單來講一個(gè)QueryBlock就是一個(gè)子查詢。QueryBlock中幾個(gè)重要的屬性在QB類和QBParseInfo類中：QB#aliasToSubq（表示QB類的aliasToSubq屬性）保存子查詢的QB對象，aliasToSubqkey值是子查詢的別名QB#qbp即QBParseInfo保存一個(gè)基本SQL單元中的給個(gè)操作部分的ASTTree結(jié)構(gòu)，QBParseInfo#nameToDest這個(gè)HashMap保存查詢單元的輸出，key的形式是inclause-i（由于Hive支持MultiInsert語句，所以可能有多個(gè)輸出），value是對應(yīng)的ASTNode節(jié)點(diǎn)，即TOK_DESTINATION節(jié)點(diǎn)。類QBParseInfo其余HashMap屬性分別保存輸出和各個(gè)操作的ASTNode節(jié)點(diǎn)的對應(yīng)關(guān)系QBParseInfo#JoinExpr保存TOK_JOIN節(jié)點(diǎn)。QB#QBJoinTree是對Join語法樹的結(jié)構(gòu)化QB#qbm保存每個(gè)輸入表的元信息，比如表在HDFS上的路徑，保存表數(shù)據(jù)的文件格式等QBExpr這個(gè)對象是為了表示Union操作邏輯操作符OperatorHive最終生成的MapReduce任務(wù)，Map階段和Reduce階段均由OperatorTree組成。邏輯操作符，就是在Map階段或者Reduce階段完成單一特定的操作。Operator類的主要屬性和方法如下：RowSchema表示Operator的輸出字段InputObjInspectoroutputObjInspector解析輸入和輸出字段processOp接收父Operator傳遞的數(shù)據(jù)，forward將處理好的數(shù)據(jù)傳遞給子Operator處理Hive每一行數(shù)據(jù)經(jīng)過一個(gè)Operator處理之后，會(huì)對字段重新編號(hào)，colExprMap記錄每個(gè)表達(dá)式經(jīng)過當(dāng)前Operator處理前后的名稱對應(yīng)關(guān)系，在下一個(gè)階段邏輯優(yōu)化階段用來回溯字段名由于Hive的MapReduce程序是一個(gè)動(dòng)態(tài)的程序，即不確定一個(gè)MapReduceJob會(huì)進(jìn)行什么運(yùn)算，可能是Join，也可能是GroupBy，所以O(shè)perator將所有運(yùn)行時(shí)需要的參數(shù)保存在OperatorDesc中，OperatorDesc在提交任務(wù)前序列化到HDFS上，在MapReduce任務(wù)執(zhí)行前從HDFS讀取并反序列化參考文章：/hive-sql-to-mapreduce.html僅僅是粗略的了解了一下，后續(xù)進(jìn)行詳細(xì)補(bǔ)充提高shuffle操作的并行度是否能解決數(shù)據(jù)傾斜方案實(shí)現(xiàn)思路：在對RDD執(zhí)行shuffle算子時(shí)，給shuffle算子傳入一個(gè)參數(shù)，比如reduceByKey(1000)，該參數(shù)就設(shè)置了這個(gè)shuffle算子執(zhí)行時(shí)shufflereadtask的數(shù)量。對于SparkSQL中的shuffle類語句，比如groupby、join等，需要設(shè)置一個(gè)參數(shù)，即spark.sql.shuffle.partitions，該參數(shù)代表了shufflereadtask的并行度，該值默認(rèn)是200，對于很多場景來說都有點(diǎn)過小。638棋牌方案實(shí)現(xiàn)原理：增加