大數據小視角2：ORCFile與Parquet，開源圈背後的生意

上一篇文章聊了聊基於PAX的混合存儲結構的RCFile，其實這裡筆者還瞭解一些八卦，RCfile的主力團隊都是來自中科院的童鞋在Facebook完成的，算是一個由華人主導的編碼項目。但是RCfile仍然存在一些缺陷，後續被 HortonWorks 盯上之後上馬了 ORCFile 格式，而老對頭 Cl ...

上一篇文章聊了聊基於PAX的混合存儲結構的RCFile，其實這裡筆者還瞭解一些八卦，RCfile的主力團隊都是來自中科院的童鞋在Facebook完成的，算是一個由華人主導的編碼項目。但是RCfile仍然存在一些缺陷，後續被HortonWorks盯上之後上馬了ORCFile格式，而老對頭Cloudera則緊抱Google大腿推出了Parquet格式。其實二者需要解決的問題是殊途同歸的，但是不同的爹似乎導致了不太相同的命運。這篇文章，我們主要還是聊聊兩者的技術細節，再穿插一些開源圈的商業八卦~~~

1.ORCFile

Facebook在 2011年的 ICDE 會議之上發佈了RCFile。之後RCFile在Hive之中作為很好的列存儲模型被廣泛使用，雖然RCFile能夠很好的提升Hive的工作性能，但是在Facebook論文之中也提出了一些RCFile值得改進的地方。所以在2013年，HortonWorks就在RCFile的基礎之上開發出了ORCFile，並且ORCFlie很順利地在2015年成為Apache的頂級項目。接下來我們來看一看ORCFile相對於原本的RCFile解決了什麼樣的問題：

列數據的類型感知：與RCFile之前對於列數據都統一為Blob數據不同，ORCFile可以感知列的數據類型，做出更為合理的數據壓縮選擇。顯然，這樣可以節省不少存儲資源。（Facebook論文之中已經提到這個思路了，但是發佈論文的時候還沒有實現，屬於一個next to do的工作）
嵌套數據類型支持：ORCFile可以在列數據之中插入Struct，Union，List，Map等數據，讓數據的操作更加靈活，也更加適合非結構化數據的存儲與處理。
謂詞下推：這個算是RCFile原先功能的補強，在元數據層面增加了很多內容，來利用謂詞下推加速處理的過程。ORCFile自己稱之為輕量級索引，其實就是一些相較於RCFile更為詳細的統計數據。

存儲結構

首先，我們先來看看ORCFile的存儲結構。如下圖所示，ORCFile完全拋棄了原有RCFile之中所謂Row Group的概念。引入了三個新的組件，我們分別來看看對應組件的內容：

(1) stripe：stripe是ORC文件的主體，還記的上文提到RCfile之中的Row Group的大小為4MB，而stripe的大小膨脹到了250MB。（果真還是越大越好麽~~）至於為什麼選擇250MB這個大小的用意也很明顯，是為了與底層HDFS的塊大小契合，來減少MapReduce處理時可能會帶來的通信損耗。 stripe也分為具體三個部分：
Index Data：存儲每行的統計數據，預設是10000行的大小。Index Data在Strip的最前面，因它們只在使用謂詞向下推或讀者尋找特定行時載入。（這裡主要利用的是統計信息與布隆過濾器實現的）
Row Data：實際存儲數據的單元，利用列存原理，對不同列可以實現不同壓縮方案，所有的列數據可以組成行數據。
Stripe Footer：存儲了每個列的編碼與位置。
(2) File Footer：部分包含Row data的佈局、類型信息、行數和每個列的統計信息。通過這塊可以篩選出需要讀取列的數據。至於類型消息，假如有如下的表定義：
```
  create table Foobar (
myInt int,
 myMap map<string,
 struct<myString : string,
 myDouble: double>>,
 myTime timestamp
);
```
則定義的類型是如同下圖的嵌套模式：
(3) PostScript：這塊保存的內容就是ORCFile的元數據了，包括了使用的壓縮類型，各個數據的長度等。由於HDFS只支持Append的操作，所以，元數據放在文件的末尾是便於修改的。

上述就是ORCFile核心的存儲結構了。對比原先的RCFile，ORCFile沒有標新立異的之處，只是補足了數據壓縮與數據處理的短板。

2.Parquet

Google同樣在 2010年發佈了最新交互處理的數據系統Dremel，並且在Dremel之上構建了一個與Protocol Buffer相容的數據模型。基本上Google推出啥，開源圈一定會照貓畫虎的弄一個出來。於是同樣在2013年，Cloudera與Twitter針對Dremel的數據模型為模板，推出了Parquet，Parquet同樣在2015年順利“畢業”，成為Apache的頂級項目。

其實Parquet與ORCFile像是孿生兄弟，許多設計的思路與細節是相同的，都是列存儲，數據壓縮那一套。所以這裡筆者不展開來講Parquet的技術細節了，而是結合Google的論文，來看一看Parquet與ORCFile最大的區別：數據模型。

數據模型

為了相容Protocol Buffer的嵌套結構，Google的工程師設計了很精巧的模型來將Protocol Buffer的結構落地到實際的存儲結構之中。坦白說，這或許是Google內部為了相容Protocol Buffer而實現的一個很trade off的設計，所以看起來有點奇怪：

Protocol Buffer的數據格式

如上圖所示，通過Protocol Buffer定義了一個組合類型Document，其中required欄位是必須填寫的，optional欄位是可以省略的，而repeated欄位是可以重覆的欄位。其中I1與I2為示例數據。如何將上述的數據模型轉換為列存呢？我們接著往下看：

將嵌套欄位切分之後變為列存的模式

首先，將上述結構之中每一個欄位拆分出來，就可以變為列存儲的模式了。但是接下來的問題在於如何處理非結構化數據之中repeated與optional欄位。這裡是通過Repetition Level與Definition Level才能來完整的還原數據的結構。

Repetition Level：顧名思義，記錄了該列的值是在哪一個級別的欄位上重覆的。
Definition Level：對於非NULL值並沒有什麼意義，因為非NULL值Definition Level一定是相同的。（顯然是可以壓縮存儲）記錄了該列的值是在哪一個級別上開始作為NULL值存儲的。

通過上述的兩個值，便可以通過有限狀態機來還原Protocol Buffer格式所定義的數據結構，落地到實際的存儲之中。（這裡涉及到列存儲的跳轉，詳細的內容可以參考Dremel論文的原文）

上述Parquet的核心就在於：通過嵌套的數據模型設計來規避Join操作和掃描最少的列存儲。下圖是Parquet的數據模型，可以看出除了列存的模式之外，其餘與ORCFile大同小異，筆者在這裡就不進贅述了：

Parquet的數據結構