轉(zhuǎn)載聲明

本文轉(zhuǎn)載自盤點(diǎn)SQL on Hadoop中用到的主要技術(shù)，個(gè)人覺(jué)得該文章對(duì)于諸如Impala這樣的MPP架構(gòu)的SQL引擎和Runtime Framework架構(gòu)的Hive/Spark SQL進(jìn)行對(duì)比，感覺(jué)總結(jié)的特別好，并且和本人最近的公司相近，學(xué)習(xí)轉(zhuǎn)載之。

自hive出現(xiàn)之后，經(jīng)過(guò)幾年的發(fā)展，SQL on Hadoop相關(guān)的系統(tǒng)已經(jīng)百花齊放，速度越來(lái)越快，功能也越來(lái)越齊全。本文并不是要去比較所謂“交互式查詢哪家強(qiáng)”，而是試圖梳理出一個(gè)統(tǒng)一的視角，來(lái)看看各家系統(tǒng)有哪些技術(shù)上相通之處。

考慮到系統(tǒng)使用的廣泛程度與成熟度，在具體舉例時(shí)一般會(huì)拿Hive和Impala為例，當(dāng)然在調(diào)研的過(guò)程中也會(huì)涉及到一些其他系統(tǒng)，如Spark SQL，Presto，TAJO等。而對(duì)于hawq這樣的商業(yè)產(chǎn)品和apache drill這樣成熟度還不是很高的開源方案就不做過(guò)多了解了。

系統(tǒng)架構(gòu)

runtime framework v.s. mpp

在SQL on Hadoop系統(tǒng)中，有兩種架構(gòu)，一種是基于某個(gè)運(yùn)行時(shí)框架來(lái)構(gòu)建查詢引擎，典型案例是Hive；另一種是仿照過(guò)去關(guān)系數(shù)據(jù)庫(kù)的MPP架構(gòu)。前者現(xiàn)有運(yùn)行時(shí)框架，然后套上sql層，后者則是從頭打造一個(gè)一體化的查詢引擎。有時(shí)我們能聽到一種聲音，說(shuō)后者的架構(gòu)優(yōu)于前者，至少在性能上。那么是否果真如此？

一般來(lái)說(shuō)，對(duì)于SQL on Hadoop系統(tǒng)很重要的一個(gè)評(píng)價(jià)指標(biāo)就是：快。后面提到的所有內(nèi)容也大多是為了查詢速度更快。在Hive逐漸普及之后，就逐漸有了所謂交互式查詢的需求，因?yàn)闊o(wú)論是BI系統(tǒng)，還是adhoc，都不能按照離線那種節(jié)奏玩。這時(shí)候無(wú)論是有實(shí)力的大公司（比如Facebook），還是專業(yè)的供應(yīng)商（比如Cloudera），都試圖去解決這個(gè)問(wèn)題。短期可以靠商業(yè)方案或者關(guān)系數(shù)據(jù)庫(kù)去支撐一下，但是長(zhǎng)遠(yuǎn)的解決方案就是參考過(guò)去的MPP數(shù)據(jù)庫(kù)架構(gòu)打造一個(gè)專門的系統(tǒng)，于是就有了Impala，Presto等等。從任務(wù)執(zhí)行的角度說(shuō)，這類引擎的任務(wù)執(zhí)行其實(shí)跟DAG模型是類似的，當(dāng)時(shí)也有Spark這個(gè)DAG模型的計(jì)算框架了，但這終究是別人家的孩子，而且往Spark上套sql又是Hive的那種玩法了。于是在Impala問(wèn)世之后就強(qiáng)調(diào)自己“計(jì)算全部在內(nèi)存中完成”，性能也是各種碾壓當(dāng)時(shí)還只有MR作為計(jì)算模型的Hive。那么Hive所代表的“基于已有的計(jì)算模型”方式是否真的不行？

不可否認(rèn)，按照這種方式去比較，那么類MPP模式確實(shí)有很多優(yōu)勢(shì)：

• DAG v.s. MR：最主要的優(yōu)勢(shì)，中間結(jié)果不寫磁盤（除非內(nèi)存不夠），一氣呵成。
• 流水線計(jì)算：上游stage一出結(jié)果馬上推送或者拉到下一個(gè)stage處理，比如多表join時(shí)前兩個(gè)表有結(jié)果直接給第三個(gè)表，不像MR要等兩個(gè)表完全join完再給第三個(gè)表join。
• 高效的IO：本地查詢沒(méi)有多余的消耗，充分利用磁盤。這個(gè)后面細(xì)說(shuō)。
• 線程級(jí)別的并發(fā)：相比之下MR每個(gè)task要啟動(dòng)JVM，本身就有很大延遲，占用資源也多。

當(dāng)然MPP模式也有其劣勢(shì)，一個(gè)是擴(kuò)展性不是很高，這在關(guān)系數(shù)據(jù)庫(kù)時(shí)代就已經(jīng)有過(guò)結(jié)論；另一個(gè)是容錯(cuò)性差，對(duì)于Impala來(lái)說(shuō)一旦運(yùn)行過(guò)程中出點(diǎn)問(wèn)題，整個(gè)查詢就掛了。

但是，經(jīng)過(guò)不斷的發(fā)展，Hive也能跑在DAG框架上了，不僅有Tez，還有Spark。上面提到的一些劣勢(shì)，其實(shí)大都也可以在計(jì)算模型中解決，只不過(guò)考慮到計(jì)算模型的通用性和本身的設(shè)計(jì)目標(biāo)，不會(huì)去專門滿足（所以如果從這個(gè)角度分類，Impala屬于“專用系統(tǒng)”，Spark則屬于“通用系統(tǒng)”）。在最近Cloudera做的benchmark中，雖然Impala仍然一路領(lǐng)先，但是基于Spark的Spark SQL完全不遜色于Presto，基于Tez的Hive也不算很差，至少在多用戶并發(fā)模式下能超過(guò)Presto，足見MPP模式并不是絕對(duì)占上風(fēng)的。所以這種架構(gòu)上的區(qū)別在我看來(lái)并不是制勝的關(guān)鍵，至少不是唯一的因素，真正要做到快速查詢，各個(gè)方面的細(xì)節(jié)都要有所把握。后面說(shuō)的都是這些細(xì)節(jié)。

核心組件

不管是上面提到的那種架構(gòu)，一個(gè)SQL on Hadoop系統(tǒng)一般都會(huì)有一些通用的核心組件，這些組件根據(jù)設(shè)計(jì)者的考慮放在不同的節(jié)點(diǎn)角色中，在物理上節(jié)點(diǎn)都按照master/worker的方式去做，如果master壓力太大，一些本來(lái)適合放在master上的組件可以放到一個(gè)輔助master上。

• UI層負(fù)責(zé)提供用戶輸入查詢的接口。一般有Web/GUI，命令行，編程方式3類。
• QL層負(fù)責(zé)把用戶提交的查詢解析成可以運(yùn)行的執(zhí)行計(jì)劃（比如MR Job）。這部分在后面會(huì)專門提到。
• 執(zhí)行層就是運(yùn)行具體的Job。一般會(huì)有一個(gè)master負(fù)責(zé)query的運(yùn)行管理，比如申請(qǐng)資源，觀察進(jìn)度等等，同時(shí)master也負(fù)責(zé)最終聚合局部結(jié)果到全局結(jié)果。而每個(gè)節(jié)點(diǎn)上會(huì)有相應(yīng)的worker做本地計(jì)算。
• IO層提供與存儲(chǔ)層交互的接口。對(duì)于HDFS來(lái)說(shuō)，需要根據(jù)I/O Format把文件轉(zhuǎn)換成K/V，Serde再完成K/V到數(shù)據(jù)行的映射。對(duì)于非HDFS存儲(chǔ)來(lái)說(shuō)就需要一些專門的handler/connector。
• 存儲(chǔ)層一般是HDFS，但也有可以查詢NoSQL，或者關(guān)系數(shù)據(jù)庫(kù)的。
• 系統(tǒng)另外還需要一個(gè)元數(shù)據(jù)管理服務(wù)，管理表結(jié)構(gòu)等。

執(zhí)行計(jì)劃

編譯流程

從SQL到執(zhí)行計(jì)劃，大致分為5步。

• 第一步將SQL轉(zhuǎn)換成抽象語(yǔ)法樹AST。這一步一般都有第三方工具庫(kù)可以完成，比如antlr。
• 第二步對(duì)AST進(jìn)行語(yǔ)義分析，比如表是否存在，字段是否存在，SQL語(yǔ)義是否有誤（比如select中被判定為聚合的字段在group by中有沒(méi)有出現(xiàn)）。
• 第三步生成邏輯執(zhí)行計(jì)劃,這是一個(gè)由邏輯操作符組成的DAG。比如對(duì)于Hive來(lái)說(shuō)掃表會(huì)產(chǎn)生TableScanOperator，聚合會(huì)產(chǎn)生GroupByOperator。對(duì)于類MPP系統(tǒng)來(lái)說(shuō)，情況稍微有點(diǎn)不同。邏輯操作符的種類還是差不多，但是會(huì)先生成單機(jī)版本，然后生成多機(jī)版本。多機(jī)版本主要是把a(bǔ)ggregate，join，還有top n這幾個(gè)操作并行化，比如aggregate會(huì)分成類似MR那樣的本地aggregate，shuffle和全局aggregate三步。
• 第四步做邏輯執(zhí)行計(jì)劃做優(yōu)化，這步在下面單獨(dú)介紹。
• 第五步把邏輯執(zhí)行計(jì)劃轉(zhuǎn)換成可以在機(jī)器上運(yùn)行的物理計(jì)劃。對(duì)于Hive來(lái)說(shuō)，就是MR/Tez Job等；對(duì)于Impala來(lái)說(shuō)，就是plan fragment。其他類MPP系統(tǒng)也是類似的概念。物理計(jì)劃中的一個(gè)計(jì)算單元（或者說(shuō)Job），有“輸入，處理，輸出”三要素組成，而邏輯執(zhí)行計(jì)劃中的operator相對(duì)粒度更細(xì)，一個(gè)邏輯操作符一般處于這三要素之一的角色。

下面分別舉兩個(gè)例子，直觀的認(rèn)識(shí)下sql、邏輯計(jì)劃、物理計(jì)劃之間的關(guān)系，具體解釋各個(gè)operator的話會(huì)比較細(xì)碎，就不展開了。

Hive on MR

select count(1) from status_updates where ds = '2009-08-01'
1
2

Presto

引用自美團(tuán)技術(shù)團(tuán)隊(duì)，其中SubPlan就是物理計(jì)劃的一個(gè)計(jì)算單元

select c1.rank, count(*) 
from dim.city c1 join dim.city c2 on c1.id = c2.id 
where c1.id > 10 group by c1.rank limit 10;
1
2
3
4

優(yōu)化器

關(guān)于執(zhí)行計(jì)劃的優(yōu)化，雖然不一定是整個(gè)編譯流程中最難的部分，但卻是最有看點(diǎn)的部分，而且目前還在不斷發(fā)展中。Spark系之所以放棄Shark另起爐灶做Spark SQL，很大一部分原因是想自己做優(yōu)化策略，避免受Hive的限制，為此還專門獨(dú)立出優(yōu)化器組件Catalyst（當(dāng)然Spark SQL目前還是非常新，其未來(lái)發(fā)展給人不少想象空間）?？傊@部分工作可以不斷的創(chuàng)新，優(yōu)化器越智能，越傻瓜化，用戶就越能解放出來(lái)解決業(yè)務(wù)問(wèn)題。

早期在Hive中只有一些簡(jiǎn)單的規(guī)則優(yōu)化，比如謂詞下推（把過(guò)濾條件盡可能的放在table scan之后就完成），操作合并（連續(xù)的filter用and合并成一個(gè)operator，連續(xù)的projection也可以合并）。后來(lái)逐漸增加了一些略復(fù)雜的規(guī)則，比如相同key的join + group by合并為1個(gè)MR，還有star schema join。在Hive 0.12引入的相關(guān)性優(yōu)化（correlation optimizer）算是規(guī)則優(yōu)化的一個(gè)高峰，他能夠減少數(shù)據(jù)的重復(fù)掃描，具體來(lái)說(shuō)，如果查詢的兩個(gè)部分用到了相同的數(shù)據(jù)，并且各自做group by / join的時(shí)候用到了相同的key，這個(gè)時(shí)候由于數(shù)據(jù)源和shuffle的key是一樣的，所以可以把原來(lái)需要兩個(gè)job分別處理的地方合成一個(gè)job處理。 
比如下面這個(gè)sql：

SELECT 
    sum(l_extendedprice) / 7.0 as avg_yearly 
FROM 
     (SELECT l_partkey, l_quantity, l_extendedprice 
      FROM lineitem JOIN part ON (p_partkey=l_partkey) 
      WHERE p_brand='Brand#35' AND p_container = 'MED PKG')touter 
JOIN 
     (SELECT l_partkey as lp, 0.2 * avg(l_quantity) as lq 
      FROM lineitem GROUP BY l_partkey) tinner 
ON (touter.l_partkey = tinnter.lp) 
WHERE touter.l_quantity < tinner.lq 
1
2
3
4
5
6
7
8
9
10
11
12

這個(gè)查詢中兩次出現(xiàn)lineitem表，group by和兩處join用的都是l_partkey，所以本來(lái)兩個(gè)子查詢和一個(gè)join用到三個(gè)job，現(xiàn)在只需要用到一個(gè)job就可以完成。

但是，基于規(guī)則的優(yōu)化（RBO）不能解決所有問(wèn)題。在關(guān)系數(shù)據(jù)庫(kù)中早有另一種優(yōu)化方式，也就是基于代價(jià)的優(yōu)化CBO。CBO通過(guò)收集表的數(shù)據(jù)信息（比如字段的基數(shù)，數(shù)據(jù)分布直方圖等等）來(lái)對(duì)一些問(wèn)題作出解答，其中最主要的問(wèn)題就是確定多表join的順序。CBO通過(guò)搜索join順序的所有解空間（表太多的情況下可以用有限深度的貪婪算法），并且算出對(duì)應(yīng)的代價(jià)，可以找到最好的順序。這些都已經(jīng)在關(guān)系數(shù)據(jù)庫(kù)中得到了實(shí)踐。

目前Hive已經(jīng)啟動(dòng)專門的項(xiàng)目，也就是Apache Optiq來(lái)做這個(gè)事情，而其他系統(tǒng)也沒(méi)有做的很好的CBO，所以這塊內(nèi)容還有很大的進(jìn)步空間。

執(zhí)行效率

即使有了高效的執(zhí)行計(jì)劃，如果在運(yùn)行過(guò)程本身效率較低，那么再好的執(zhí)行計(jì)劃也會(huì)大打折扣。這里主要關(guān)注CPU和IO方面的執(zhí)行效率。

CPU

在具體的計(jì)算執(zhí)行過(guò)程中，低效的cpu會(huì)導(dǎo)致系統(tǒng)的瓶頸落在CPU上，導(dǎo)致IO無(wú)法充分利用。在一項(xiàng)針對(duì)Impala和Hive的對(duì)比時(shí)發(fā)現(xiàn)，Hive在某些簡(jiǎn)單查詢上（TPC-H Query 1）也比Impala慢主要是因?yàn)镠ive運(yùn)行時(shí)完全處于CPU bound的狀態(tài)中，磁盤IO只有20%，而Impala的IO至少在85%。

在SQL on Hadoop中出現(xiàn)CPU bound的主要原因有以下幾種：

• 大量虛函數(shù)調(diào)用：這個(gè)問(wèn)題在多處出現(xiàn)，比如對(duì)于a + 2 * b之類的表達(dá)式計(jì)算，解釋器會(huì)構(gòu)造一個(gè)expression tree，解釋的過(guò)程就是遞歸調(diào)用子節(jié)點(diǎn)做evaluation的過(guò)程。又比如以DAG形式的operator/task在執(zhí)行的過(guò)程中，上游節(jié)點(diǎn)會(huì)層層調(diào)用下游節(jié)點(diǎn)來(lái)獲取產(chǎn)生的數(shù)據(jù)。這些都會(huì)產(chǎn)生大量的調(diào)用。
• 類型裝箱：由于表達(dá)式解釋器需要對(duì)不同數(shù)據(jù)類型的變量做解釋，所以在Java中需要把這些本來(lái)是primitive的變量包裝成Object，累積起來(lái)也消耗不少資源。這算是上面一個(gè)問(wèn)題附帶出來(lái)的。
• branch instruction： 現(xiàn)在的CPU都是有并行流水線的，但是如果出現(xiàn)條件判斷會(huì)導(dǎo)致無(wú)法并行。這種情況可能出現(xiàn)在判斷數(shù)據(jù)的類型（是string還是int），或者在判斷某一列是否因?yàn)槠渌侄蔚倪^(guò)濾條件導(dǎo)致本行不需要被讀取（列存儲(chǔ)情況下）。
• cache miss：每次處理一行數(shù)據(jù)的方式導(dǎo)致cpu cache命中率不高。（這么說(shuō)已經(jīng)暗示了解決方案）

針對(duì)上面的問(wèn)題，目前大多數(shù)系統(tǒng)中已經(jīng)加入了以下兩個(gè)解決辦法中至少一個(gè)。

一個(gè)方法是動(dòng)態(tài)代碼生成，也就是不使用解釋性的統(tǒng)一代碼。比如a + 2 * b這個(gè)表達(dá)式就會(huì)生成對(duì)應(yīng)的執(zhí)行語(yǔ)言的代碼，而且可以直接用primitive type，而不是用固定的解釋性代碼。具體實(shí)現(xiàn)來(lái)說(shuō)，JVM系的如Spark SQL，Presto可以用反射，C++系的Impala則使用了llvm生成中間碼。對(duì)于判斷數(shù)據(jù)類型造成的分支判斷，動(dòng)態(tài)代碼的效果可以消除這些類型判斷，還可以展開循環(huán)，可以對(duì)比下面這段代碼，左邊是解釋性代碼，右邊是動(dòng)態(tài)生成代碼。

另一個(gè)方法是vectorization（向量化），基本思路是放棄每次處理一行的模式，改用每次處理一小批數(shù)據(jù)（比如1k行），當(dāng)然前提條件是使用列存儲(chǔ)格式。這樣一來(lái)，這一小批連續(xù)的數(shù)據(jù)可以放進(jìn)cache里面，cpu不僅減少了branch instruction，甚至可以用SIMD加快處理速度。具體的實(shí)現(xiàn)參考下面的代碼，對(duì)一個(gè)long型的字段增加一個(gè)常量。通過(guò)把數(shù)據(jù)表示成數(shù)組，過(guò)濾條件也用selVec裝進(jìn)數(shù)組，形成了很緊湊的循環(huán)：

add(int vecNum, long[] result, long[] col1, int[] col2, int[] selVec) 
{   
  if (selVec == null)   
     for (int i = 0; i < vecNum; i++) 
         result[i] = col1[i] + col2[i];
  else 
     for (int i = 0; i < vecNum; i++) 
     {
         int selIdx = selVec[i];
         result[selIdx] = col1[selIdx] + col2[selIdx];
     }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

IO

由于SQL on Hadoop存儲(chǔ)數(shù)據(jù)都是在HDFS上，所以IO層的優(yōu)化其實(shí)大多數(shù)都是HDFS的事情，各大查詢引擎則提出需求去進(jìn)行推動(dòng)。要做到高效IO，一方面要低延遲，屏蔽不必要的消耗；另一方面要高吞吐，充分利用每一塊磁盤。目前與這方面有關(guān)的特性有：

• short-circuit local reads：當(dāng)發(fā)現(xiàn)讀取的數(shù)據(jù)是本地?cái)?shù)據(jù)時(shí)，不走DataNode（因?yàn)橐咭淮蝧ocket連接），而是用DFS Client直接讀本地的block replica。HDFS參數(shù)是dfs.client.read.shortcircuit和dfs.domain.socket.path。
• zero copy：避免數(shù)據(jù)在內(nèi)核buffer和用戶buffer之間反復(fù)copy，在早期的HDFS中已經(jīng)有這個(gè)默認(rèn)實(shí)現(xiàn)。
• disk-aware scheduling：通過(guò)知道每個(gè)block所在磁盤，可以在調(diào)度cpu資源時(shí)讓不同的cpu讀不同的磁盤，避免查詢內(nèi)和查詢間的IO競(jìng)爭(zhēng)。HDFS參數(shù)是dfs.datanode.hdfs-blocks-metadata.enabled。

存儲(chǔ)格式

對(duì)于分析類型的workload來(lái)說(shuō)，最好的存儲(chǔ)格式自然是列存儲(chǔ)，這已經(jīng)在關(guān)系數(shù)據(jù)庫(kù)時(shí)代得到了證明。目前hadoop生態(tài)中有兩大列存儲(chǔ)格式，一個(gè)是由Hortonworks和Microsoft開發(fā)的ORCFile，另一個(gè)是由Cloudera和Twitter開發(fā)的Parquet。

ORCFile顧名思義，是在RCFile的基礎(chǔ)之上改造的。RCFile雖然號(hào)稱列存儲(chǔ)，但是只是“按列存儲(chǔ)”而已，將數(shù)據(jù)先劃分成row group，然后row group內(nèi)部按照列進(jìn)行存儲(chǔ)。這其中沒(méi)有列存儲(chǔ)的一些關(guān)鍵特性，而這些特性在以前的列式數(shù)據(jù)庫(kù)中（比如我以前用過(guò)的Infobright）早已用到。好在ORCFile已經(jīng)彌補(bǔ)了這些特性，包括：

• 塊過(guò)濾與塊統(tǒng)計(jì)：每一列按照固定行數(shù)或大小進(jìn)一步切分，對(duì)于切分出來(lái)的每一個(gè)數(shù)據(jù)單元，預(yù)先計(jì)算好這些單元的min/max/sum/count/null值，min/max用于在過(guò)濾數(shù)據(jù)的時(shí)候直接跳過(guò)數(shù)據(jù)單元，而所有這些統(tǒng)計(jì)值則可以在做聚合操作的時(shí)候直接采用，而不必解開這個(gè)數(shù)據(jù)單元做進(jìn)一步的計(jì)算。
• 更高效的編碼方式：RCFile中沒(méi)有標(biāo)注每一列的類型，事實(shí)上當(dāng)知道數(shù)據(jù)類型時(shí)，可以采取特定的編碼方式，本身就能很大程度上進(jìn)行數(shù)據(jù)的壓縮。常見的針對(duì)列存儲(chǔ)的編碼方式有RLE（大量重復(fù)數(shù)據(jù)），字典（字符串），位圖（數(shù)字且基數(shù)不大），級(jí)差（排序過(guò)的數(shù)據(jù)，比如日志中用戶訪問(wèn)時(shí)間）等等。

ORCFile的結(jié)構(gòu)如下圖，數(shù)據(jù)先按照默認(rèn)256M分為row group，也叫strip。每個(gè)strip配一個(gè)index，存放每個(gè)數(shù)據(jù)單元（默認(rèn)10000行）的min/max值用于過(guò)濾；數(shù)據(jù)按照上面提到的編碼方式序列化成stream，然后再進(jìn)行snappy或gz壓縮。footer提供讀取stream的位置信息，以及更多的統(tǒng)計(jì)值如sum/count等。尾部的file footer和post script提供全局信息，如每個(gè)strip的行數(shù)，各列數(shù)據(jù)類型，壓縮參數(shù)等。

Parquet的設(shè)計(jì)原理跟ORC類似，不過(guò)它有兩個(gè)特點(diǎn)：

• 通用性：相比ORCFile專門給Hive使用而言，Parquet不僅僅是給Impala使用，還可以給其他查詢工具使用，如Hive、Pig，進(jìn)一步還能對(duì)接avro/thrift/pb等序列化格式。
• 基于Dremel思想的嵌套格式存儲(chǔ)：關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì)模式中反對(duì)存儲(chǔ)復(fù)雜格式（違反第一范式），但是現(xiàn)在的大數(shù)據(jù)計(jì)算不僅出現(xiàn)了這種需求（半結(jié)構(gòu)化數(shù)據(jù)），也能夠高效的實(shí)現(xiàn)存儲(chǔ)和查詢效率，在語(yǔ)法上也有相應(yīng)的支持（各種UDF，Hive的lateral view等）。Google Dremel就在實(shí)現(xiàn)層面做出了范例，Parquet則完全仿照了Dremel。

對(duì)嵌套格式做列存儲(chǔ)的難點(diǎn)在于，存儲(chǔ)時(shí)需要標(biāo)記某個(gè)數(shù)據(jù)對(duì)應(yīng)于哪一個(gè)存儲(chǔ)結(jié)構(gòu)，或者說(shuō)是哪條記錄，所以需要用數(shù)據(jù)清楚的進(jìn)行標(biāo)記。 在Dremel中提出用definition level和repetition level來(lái)進(jìn)行標(biāo)記。definition level指的是，這條記錄在嵌套結(jié)構(gòu)中所處于第幾層，而repetition level指的是，這條記錄相對(duì)上一條記錄，在第幾層重復(fù)。比如下圖是一個(gè)二級(jí)嵌套數(shù)組。圖中的e跟f在都屬于第二層的重復(fù)記錄（同一個(gè)level2），所以f的r值為2，而c跟d則是不同的level2，但屬于同一個(gè)level1，所以d的r值為1。對(duì)于頂層而言（新的一個(gè)嵌套結(jié)構(gòu)），r值就為0。

但是僅僅這樣還不夠。上圖說(shuō)明了r值的作用，但是還沒(méi)有說(shuō)明d值的作用，因?yàn)榘凑兆置娼忉?，d值對(duì)于每一個(gè)字段都是可以根據(jù)schema得到的，那為什么還要從行記錄級(jí)別標(biāo)記？這是因?yàn)橛涗浿袝?huì)插入一些null值，這些null值代表著他們“可以存在”但是因?yàn)槭莚epeated或者是optional所以沒(méi)有值的情況，null值是用來(lái)占位的（或者說(shuō)是“想象”出來(lái)的），所以他們的值需要單獨(dú)計(jì)算。null的d值就是說(shuō)這個(gè)結(jié)構(gòu)往上追溯到哪一層（不包括平級(jí)）就不是null（不是想象）了。在dremel paper中有完整的例子，例子中country的第一個(gè)null在code = en所在的結(jié)構(gòu)里面，那么language不是null（不考慮code，他跟country平級(jí)），他就是第二層；又比如country的第二個(gè)null在url = http://B 所在的結(jié)構(gòu)里面，那么name不是null（不考慮url，因?yàn)樗緛?lái)就是null的language平級(jí)），所以就是第一層。

通過(guò)這種方式，就對(duì)一個(gè)樹狀的嵌套格式完成了存儲(chǔ)。在讀取的時(shí)候可以通過(guò)構(gòu)造一個(gè)狀態(tài)機(jī)進(jìn)行遍歷。

有意思的是，雖然parquet支持嵌套格式，但是Impala還沒(méi)有來(lái)得及像Hive那樣增加array，map，struct等復(fù)雜格式，當(dāng)然這項(xiàng)功能已經(jīng)被列入roadmap了，相信不久就會(huì)出現(xiàn)。

在最近我們做的Impala2.0測(cè)試中，順便測(cè)試了存儲(chǔ)格式的影響。parquet相比sequencefile在壓縮比上達(dá)到1:5，查詢性能也相差5-10倍，足見列存儲(chǔ)一項(xiàng)就給查詢引擎帶來(lái)的提升。

資源控制

運(yùn)行時(shí)資源調(diào)整

對(duì)于一個(gè)MR Job，reduce task的數(shù)量一直是需要人為估算的一個(gè)麻煩事，基于MR的Hive也只是根據(jù)數(shù)據(jù)源大小粗略的做估計(jì)，不考慮具體的Job邏輯。但是在之后的框架中考慮到了這個(gè)情況，增加了運(yùn)行時(shí)調(diào)整資源分配的功能。Tez中引入了vertex manager，可以根據(jù)運(yùn)行時(shí)收集到的數(shù)據(jù)智能的判斷reduce動(dòng)作需要的task。類似的功能在TAJO中也有提到，叫progressive query optimization，而且TAJO不僅能做到動(dòng)態(tài)調(diào)整task數(shù)量，還能動(dòng)態(tài)調(diào)整join順序。

資源集成

在Hadoop已經(jīng)進(jìn)入2.x的時(shí)代，所有想要得到廣泛應(yīng)用的SQL on Hadoop系統(tǒng)勢(shì)必要能與YARN進(jìn)行集成。雖然這是一個(gè)有利于資源合理利用的好事，但是由于加入了YARN這一層，卻給系統(tǒng)的性能帶來(lái)了一定的障礙，因?yàn)閱?dòng)AppMaster和申請(qǐng)container也會(huì)占用不少時(shí)間，尤其是前者，而且container的供應(yīng)如果時(shí)斷時(shí)續(xù)，那么會(huì)極大的影響時(shí)效性。在Tez和Impala中對(duì)這些問(wèn)題給出了相應(yīng)的解決辦法：

• AppMaster啟動(dòng)延遲的問(wèn)題，采取long lived app master，AppMaster啟動(dòng)后長(zhǎng)期駐守，而非像是MR那樣one AM per Job。具體實(shí)現(xiàn)時(shí)，可以給fair scheduler或capacity scheduler配置的每個(gè)隊(duì)列配上一個(gè)AM池，有一定量的AM為提交給這個(gè)隊(duì)列的任務(wù)服務(wù)。
• container供應(yīng)的問(wèn)題，在Tez中采取了container復(fù)用的方式，有點(diǎn)像jvm復(fù)用，即container用完以后不馬上釋放，等一段時(shí)間，實(shí)在是沒(méi)合適的task來(lái)接班了再釋放，這樣不僅減少container斷供的可能，而且可以把上一個(gè)task留下的結(jié)果cache住給下一個(gè)task復(fù)用，比如做map join；Impala則采取比較激進(jìn)的方式，一次性等所有的container分配到位了才開始執(zhí)行查詢，這種方式也能讓它的流水線式的計(jì)算不至于阻塞。

其他

到這里為止，已經(jīng)從上到下順了一遍各個(gè)層面用到的技術(shù)，當(dāng)然SQL on Hadoop本身就相當(dāng)復(fù)雜，涉及到方方面面，時(shí)間精力有限不可能一一去琢磨。比如其他一些具有技術(shù)復(fù)雜度的功能有：

• 多數(shù)據(jù)源查詢：Presto支持從mysql，cassandra，甚至kafka中去讀取數(shù)據(jù)，這就大大減少了數(shù)據(jù)整合時(shí)間，不需要放到HDFS里才能查詢。Impala和Hive也支持查詢hbase。Spark SQL也在1.2版本開始支持External Datasource。國(guó)內(nèi)也有類似的工作，如秒針改造Impala使之能查詢postgres。
• 近似查詢：count distinct（基數(shù)估計(jì)）一直是sql性能殺手之一，如果能接受一定誤差的話可以采用近似算法。Impala中已經(jīng)實(shí)現(xiàn)了近似算法（ndv），Presto則是請(qǐng)blinkDB合作完成。兩者都是采用了HyperLogLog Counting。當(dāng)然，不僅僅是count distinct可以使用近似算法，其他的如取中位數(shù)之類的也可以用。

結(jié)束語(yǔ)

盡管現(xiàn)在相關(guān)系統(tǒng)已經(jīng)很多，也經(jīng)過(guò)了幾年的發(fā)展，但是目前各家系統(tǒng)仍然在不斷的進(jìn)行完善，比如：

• 增加分析函數(shù)，復(fù)雜數(shù)據(jù)類型，SQL語(yǔ)法集的擴(kuò)展。
• 對(duì)于已經(jīng)成形的技術(shù)也在不斷的改進(jìn)，如列存儲(chǔ)還可以增加更多的encoding方式。
• 甚至對(duì)于像CBO這樣的領(lǐng)域，開源界拿出來(lái)的東西還算是剛剛起步，相比HAWQ中的ORCA這種商業(yè)系統(tǒng)提供的優(yōu)化器還差的很多。

畢竟相比已經(jīng)比較成熟的關(guān)系數(shù)據(jù)庫(kù)，分布式環(huán)境下需要解決的問(wèn)題更多，未來(lái)一定還會(huì)出現(xiàn)很多精彩的技術(shù)實(shí)踐，讓我們?cè)诤Ａ繑?shù)據(jù)中更快更方便的查到想要的數(shù)據(jù)。

https://blog.csdn.net/yu616568/article/details/55054332