KFS的元數據持久化是依賴checkpoint和operation log結合來工作的，其中checkpoint顧名思義保存的是某個點內存的狀態，operation log記錄的是對元數據修改的操作日志。

使用checkpoint+log的設計
（1）    元數據信息必須要持久化，否則掉電或者人工重啟之后該信息丟失
（2）    便于快速重啟，可以從最近的一個cp中快速構建內存狀態，加上該cp之后的log就可以完整地構建內存

讀寫checkpoint和log的過程

Metaserver啟動時的內存構建：

在Startup.cc調用rebuild函數

（1）       如果之前已經有了checkpoint，從checkpoint里重建內存樹，否則新建一棵內存樹

（2）       在內存中replay該checkpoint之后的所有operation log

MetaServer運行時寫入新的checkpoint：

logcompactor_main.cc的main函數調用，應該是以調用另一個進程的方式來執行，猜想是Metaserver進程會定時調用該進程

（1）       根據舊的checkpoint在內存中生成狀態

（2）       在內存中replay之后的op log

（3）       將此時的內存狀態寫入新的checkpoint

MetaServer運行時寫入新的log：

由logger.cc來寫入新log，看了代碼應該是每次修改了元信息的操作，都會將這條op log寫入磁盤，雖然性能不高，但是比較可靠（之前也自己寫過日志庫，使用的是兩個buffer交換寫入，這樣比較高效一些）

此處的KFS是指Kosmos distributed file system，代碼位于http://sourceforge.net/projects/kosmosfs/，之后會寫幾篇相關的文章，以供后來者參考。

KFS里Meta的內存結構主要是一棵B+樹，保存在內存里，具體分析如下：

B-樹，B+樹的定義

關于這些樹的定義，最好還是參考算法導論等經典書，網路上的信息有些不是很準確，為了方便大家還是貼一個鏈接：

http://www.cnblogs.com/oldhorse/archive/2009/11/16/1604009.html

KFS為何選用B+樹而非B樹？

這是我個人的理解：

雖然B樹可以在非葉子節點命中，會縮短一些平均查找長度，但是B+樹在這種應用一個優勢就是每個節點都有指向next節點的指針，對于范圍查詢或者遍歷操作很適合。對于文件系統的一個ls某個子目錄的需求，用B+樹可以較高效的解決。

KFS里B+樹的類圖

MetaNode：base class for both internal and leaf nodes

Meta：base class for data objects (leaf nodes)

Node：an internal node in the KFS search tree

MetaChunkInfo：chunk information for a given file offset

MetaDentry ：Directory entry, mapping a file name to a file id

MetaFattr：File or directory attributes

各節點的介紹

（1）Meta類是子節點的父類，其最主要的成員變量是fid

有三個葉子節點：MetaChunkInfo，MetaDentry，MetaFattr

（2）MetaDentry：實現從文件名到fid的映射，對于每個文件（目錄）都擁有1個MetaDentry

成員變量包括：

dir：文件父目錄的fid

name：dentry的名稱，實際就是文件名

（3）MetaFattr：實現從fid到文件屬性的映射，對于每個文件（目錄）都擁有一個MetaFattr。

成員變量包括：

Type：文件還是目錄

numReplicas：文件有幾份副本

mtime：修改時間

ctime：屬性修改時間

crtime：文件創建時間

chunkcount：連續的chunk數目

filesize：文件大小

nextChunkOffset：最后一個chunk在文件的所處的offset

mode_t mode：文件屬性（rwx位）

key：由KFS_FATTR，fid來構成，可以通過fid直接找到保存文件屬性的節點。

（4）MetaChunkInfo：標志某個文件對應的chunk信息，如果一個文件包含多個chunk，那么需要有多個MetaChunkInfo。

成員變量包括：

offset：chunk在文件中的偏移量，因為一個文件可能由多個chunk組成

chunkId：chunk的id號

chunkVersion：chunk的version值

（5）Node：實現的是B+樹的內部節點，這種節點僅僅作為索引用途，存儲實際元數據信息的節點位于最底部的葉子節點。

成員變量包括：

NKEY = 32：每個節點最多擁有的關鍵字數目，實際上也就是最多擁有的子節點數目，如果多余這個值節點進行分裂

NSPLIT = NKEY / 2：分裂之后每個節點的關鍵字數目

NFEWEST = NKEY - NSPLIT：每個節點最少擁有的關鍵字數目，如果少于這個值兩個節點進行合并

count：節點實際擁有的關鍵字數目

Key childKey[NKEY]：節點存儲的關鍵字列表

MetaNode *childNode[NKEY]：節點指向子節點的指針列表

Node *next：指向下一個同級節點的指針

實際上每個內部節點的階數為32，可以有32個子節點，而每個葉子節點只保存一個key值。

三類子節點在B+樹中如何分布？

可以想象，必定是將同一類的節點聚集在一起。因此對于排序函數就是先比較節點類型，然后再對節點內部的成員變量進行比較。MetaDentry是根據dir（父目錄的id），MetaFattr是根據fid，MetaChunkInfo是根據id和chunkId來排序。

一個不太相關的思考

看上面的三類子節點，我們可以發現chunk的位置信息并沒有保存在B+樹里，它是單獨保存在一個Map數據結構里的，也不會在meta server里進行持久化，而是每次chunk啟動時向meta server來報告。之所以不做持久化，可以這樣來理解：

只有Chunk服務器才能最終確定一個Chunk是否在它的硬盤上。Chunk服務器的錯誤可能會導致Chunk自動消失(比如，硬盤損壞了或者無法訪問了)，亦或者操作人員可能會重命名一個Chunk服務器，還是由chunk server來報告比較靠譜。

    Dremel是google推出的又一神器，paper中宣稱能夠在3s內分析1PB的數據，主要是面向交互式查詢。這篇paper對嵌套類型的存儲方式方面，思維確實有些跳躍，這篇文章主要講講這個，一方面是方便后來者理解，另一方面是讓自己也整理下思路。

    首先Dremel使用的是列存模型，對于基本類型列存較容易做到；但是對于嵌套類型，Dremel也能做到將其拆解成基本類型并進行列存，這是值得我們研究的。

    直觀看下嵌套類型按行存儲和拆解后按列存儲的對比效果：

    然后對于嵌套數據類型，Dremel里面定義了里面三種類型的字段

    1，必須出現1次而且僅出現1次的字段：required

    2，可能出現1次或者0次的字段：optional

    3，可能出現0次或者N次字段：repeated

    下面以paper的例子來講述吧：

    其中DocId是required字段，因此在r1,r2中必須出現1次；url字段是optional字段，因此在r1的第三個Name里未出現，在r1的前兩個Name里出現了1次；Backward字段是repeated字段，因此在r1的Links里未出現，在r2的Links里出現了2次。

    理解了上面這些，直接來看下Dremel是怎么來存它的吧：

    上表中的每條記錄都有兩個屬性，"r"代表repetition level，"d"代表definition level，定義如下：

    repetition level:what repeated field in the field’s path the value has repeated，記錄該字段是在哪個repeated級別上重復的

    definition level:how many fields inpthat could be undefined (because they are optional or repeated) are actually present，記錄該字段之上有多少個optional或者repeated字段實際是有值的（本來可以為null的）

    看到這里，各位可能已經在心里默念了：WTF！別急，可以結合一個例子來看：

先看repetition level（下面以r替代），以Name.Language.Code為例：

    1)對第1個出現的值，其r始終為0，因此'en-us'的r為0

    2)對于第2個值'en'，其上一個值是'en-us'，它們是在Language級別發生的重復，Name.Language是兩級的repeated字段，因此r為2

    3)對于第3個值null，是為了記錄'en-gb'是出現在第三個Name而非第二個Name里，特意占位用的。null的上一個值是'en'，它們是在Name級別發生的重復，因此r是1

    4)對于第4個值'en-gb'，其上一個值是null，它們也是在Name級別發生的重復，因此r是1

    5)對于第5個值null，其上一個值是'en-gb'，它們出現在兩個不同Document里，因此r是0

    總結下，看repetition level注意兩點：1,只比較該值和上一個值；2,只需要看這兩個值的重復位置上有幾個repeated字段

再看definition level（下面以d替代），也以Name.Language.Code為例：

    1)對于'en-us'，其上的Name，Language都出現了，因此d為2（其實對于非null值的字段，其上的optional或者repeated字段肯定是出現了，所以都是相同的，只是null字段的d值有差別）

    2)對于'en'，同理d也為2

    3)對于null，其上只出現了Name，沒有出現Language，因此d為1

    4)對于'en-gb',d也為2

    5)對于最后一個null，其上也只出現了Name，沒有出現Language，因此d為1

    以上只是講了dremel怎么去存嵌套類型，至于這種存法是怎么想出來的，真非我輩能理解的了。。。更多內容，請參考原著paper及網上解析。

    上篇文章從整體介紹了Orcfile的存儲格式，接下來重點介紹下Orc里用到的幾種編碼格式：

    字典編碼：用于String類型的字段

    Run-Length編碼：用于int，long，short等類型的編碼

    Bit編碼：可以用于各種數據類型

1，字典編碼：

    對于String類型的每個字段分別保存一個字典，記錄每個值在字典中的位置，保存字典的數據結構采用一棵紅黑樹。對于每個String字段，最終會有三個輸出Stream，分別是StringOuptut(記錄字典中的值)，LengthOutput(記錄每個字典值的長度)，RowOutput(記錄字段在字典中的位置)。

    思考1：為什么要用紅黑樹？

    因為紅黑樹無論是插入，刪除，查找的性能都比較平均，都是O(logN)，而且是平衡查找樹，最壞情況也不會退化成O(N)

    思考2：其實一般存儲時還會使用LZO之類的壓縮，它們本身就是一種字典壓縮，為什么Orc里面要自己做字典壓縮？

    因為LZO之類的壓縮窗口一般比較小（LZO默認是64KB），而Orc的字典壓縮是以整個字段為范圍來壓縮的，壓縮率會更好。

2，Run-Length編碼：

    對于int,long,short類型的字段，使用Run-Length編碼。該Run-Length能夠對等差數列（完全相等也屬于等差數列）進行壓縮，該等差數列需要滿足以下兩個條件：

    1，至少包含3個元素

    2，差值在-128~127之間（因為差值用1Byte來表示）

    對于不滿足等差數列的數字，Run-Length編碼也能存儲，但是沒有壓縮效果，Run-Length的具體存儲如下：

    第一個Byte是Control Byte，取值在-128~127之間，其中-1~-128代表后面存儲著1~128個不滿足等差數列的數字，0~127代表后面存儲著3~130個等差數列的數字；

    如果Control Byte>=0，則后面跟著一個Byte存儲差值，否則不存儲該Byte；

    如果Control Byte>=0，則后面跟著等差數列的第一個數，否則跟著-Control Byte個數字。

    例子：

    原始數字：12,12,12,12,12,10,7,13

    經過Run-Length的數字：2,0,12,-3,10,7,13

    紅色代表Control Byte，黃色代表差值，黑色代表具體的數字。

3，Bit編碼：

對所有類型的字段都可以采用Bit編碼來表示該值是否為null。在寫任何類型字段之前，先判斷該字段值是夠為null，如果為null則bit值存為0，否則存為1，對于為null的字段在實際編碼時不需要存儲了。經過Bit編碼之后，可以對于8個bit組成一個Byte，再對其進行Run-Length編碼。

    其實除了這三種編碼格式之外，Orc對于hive的復雜類型array,map,list等，將其降維成基本類型來存儲，這個也是值得借鑒的，如果有空之后會進行分析。

    Orcfile(Optimized Row Columnar)是hive 0.11版里引入的新的存儲格式，是對之前的RCFile存儲格式的優化。寫這個的哥們來自于HortonWorks，代碼寫的很不錯，比之前的rcfile強多了（據說rcfile是個中科院的童鞋跑去facebook寫的，看來中國的計算機教育水平還是有限啊。。。囧，跑題了）

    先介紹下Orc的文件格式，截一張官方的圖：

    可以看到每個Orc文件由1個或多個stripe組成，每個stripe250MB大小，這個Stripe實際相當于之前的rcfile里的RowGroup概念，不過大小由4MB->250MB，這樣應該能提升順序讀的吞吐率。每個Stripe里有三部分組成，分別是Index Data,Row Data,Stripe Footer：

    1，Index Data：一個輕量級的index，默認是每隔1W行做一個索引。這里做的索引應該只是記錄某行的各字段在Row Data中的offset，據說還包括每個Column的max和min值，具體沒細看代碼。

    2，Row Data：存的是具體的數據，和RCfile一樣，先取部分行，然后對這些行按列進行存儲。與RCfile不同的地方在于每個列進行了編碼，分成多個Stream來存儲，具體如何編碼在下一篇解析里會講。

    3，Stripe Footer：存的是各個Stream的類型，長度等信息。

    每個文件有一個File Footer，這里面存的是每個Stripe的行數，每個Column的數據類型信息等；每個文件的尾部是一個PostScript，這里面記錄了整個文件的壓縮類型以及FileFooter的長度信息等。在讀取文件時，會seek到文件尾部讀PostScript，從里面解析到File Footer長度，再讀FileFooter，從里面解析到各個Stripe信息，再讀各個Stripe，即從后往前讀。

    接下來看下ORcfile相對于RCfile做了哪些改進，從Orc作者的ppt里截了張圖，分別解釋下各行：

    Hive type model:RCfile在底層存儲時不保存類型，都當做Byte流來存儲

    Separtor complex columns:Orc將復雜類型拆開存儲

    Splits Found Quickly：不很理解

    Default Column group size：不用解釋了

    Files per a bucket：不很理解

    Store min，max，count，sum：存了這些便于快速地skip掉一個stripe

    Versioned metadata:不很理解

    Run-Length Data-coding：整數類型做Run-Length變長編碼

    Store Strings in dictionary：String類型做字典編碼

    Store Row Count：每個Stripe會存儲行數

    Skip Compressed blocks:可以直接skip掉壓縮過的block

    Store internal indexes:存儲了一個輕量級的index

    整個Orc看下來，代碼寫的還是比較清晰明了的，而且我們也進行了測試，壓縮效果比RCfile提升了不少，有興趣的朋友可以來看下，之后會寫第二篇解析，主要是講Orc用到的幾種編碼格式。