SQL on Hadoop技術(shù)綜述
一、系統(tǒng)架構(gòu)
runtime framework v.s. mpp
在SQL on Hadoop系統(tǒng)中愿题，有兩種架構(gòu)：
1免胃、一種是基于某個(gè)運(yùn)行時(shí)框架來(lái)構(gòu)建查詢引擎粉楚，典型案例是Hive辣恋；
2、另一種是仿照過(guò)去關(guān)系數(shù)據(jù)庫(kù)的MPP架構(gòu)模软，就是參考過(guò)去的MPP數(shù)據(jù)庫(kù)架構(gòu)打造一個(gè)專門的系統(tǒng)伟骨，于是就有了Impala，Presto等等燃异。
前者現(xiàn)有運(yùn)行時(shí)框架携狭，然后套上sql層，后者則是從頭打造一個(gè)一體化的查詢引擎回俐。
對(duì)于SQL on Hadoop系統(tǒng)很重要的一個(gè)評(píng)價(jià)指標(biāo)就是：快逛腿。
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蝙场，本身就有很大延遲，占用資源也多粱年。
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ì)算模型中解決皆尔。基于Spark的Spark SQL完全不遜色于Presto币励，基于Tez的Hive也不算很差慷蠕，至少在并發(fā)模式下能超過(guò)Presto，足見(jiàn)MPP模式并不是絕對(duì)占上風(fēng)的食呻。
二流炕、核心組件
不管是上面提到的那種架構(gòu)，一個(gè)SQL on Hadoop系統(tǒng)一般都會(huì)有一些通用的核心組件仅胞，這些組件根據(jù)設(shè)計(jì)者的考慮放在不同的節(jié)點(diǎn)角色中每辟，在物理上節(jié)點(diǎn)都按照master/worker的方式去做
三、執(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)化赵颅。
?第五步把邏輯執(zhí)行計(jì)劃轉(zhuǎn)換成可以在機(jī)器上運(yùn)行的物理計(jì)劃虽另。
四、優(yōu)化器
關(guān)于執(zhí)行計(jì)劃的優(yōu)化饺谬，雖然不一定是整個(gè)編譯流程中最難的部分捂刺，但卻是最有看點(diǎn)的部分，而且目前還在不斷發(fā)展中募寨。Spark系之所以放棄Shark另起爐灶做Spark SQL族展，很大一部分原因是想自己做優(yōu)化策略，避免受Hive的限制拔鹰。早期在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锣尉。
但是，基于規(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í)踐凉敲。
五衣盾、存儲(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ǔ)迈窟。
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ù)的壓縮钱烟。常見(jiàn)的針對(duì)列存儲(chǔ)的編碼方式有RLE（大量重復(fù)數(shù)據(jù)）晰筛，字典（字符串），位圖（數(shù)字且基數(shù)不大）拴袭，級(jí)差（排序過(guò)的數(shù)據(jù)读第，比如日志中用戶訪問(wèn)時(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觉渴。
多數(shù)據(jù)源查詢：Presto支持從mysql介劫，cassandra，甚至kafka中去讀取數(shù)據(jù)案淋，這就大大減少了數(shù)據(jù)整合時(shí)間座韵，不需要放到HDFS里才能查詢。Impala和Hive也支持查詢hbase踢京。
近似查詢：count distinct（基數(shù)估計(jì)）一直是sql性能殺手之一誉碴，如果能接受一定誤差的話可以采用近似算法。Impala中已經(jīng)實(shí)現(xiàn)了近似算法（ndv）瓣距，Presto則是請(qǐng)blinkDB合作完成黔帕。兩者都是采用了HyperLogLog Counting。
