KFS的元數(shù)據(jù)持久化是依賴checkpoint和operation log結(jié)合來工作的，其中checkpoint顧名思義保存的是某個(gè)點(diǎn)內(nèi)存的狀態(tài)，operation log記錄的是對元數(shù)據(jù)修改的操作日志。

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

讀寫checkpoint和log的過程

Metaserver啟動時(shí)的內(nèi)存構(gòu)建：

在Startup.cc調(diào)用rebuild函數(shù)

（1）       如果之前已經(jīng)有了checkpoint，從checkpoint里重建內(nèi)存樹，否則新建一棵內(nèi)存樹

（2）       在內(nèi)存中replay該checkpoint之后的所有operation log

MetaServer運(yùn)行時(shí)寫入新的checkpoint：

logcompactor_main.cc的main函數(shù)調(diào)用，應(yīng)該是以調(diào)用另一個(gè)進(jìn)程的方式來執(zhí)行，猜想是Metaserver進(jìn)程會定時(shí)調(diào)用該進(jìn)程

（1）       根據(jù)舊的checkpoint在內(nèi)存中生成狀態(tài)

（2）       在內(nèi)存中replay之后的op log

（3）       將此時(shí)的內(nèi)存狀態(tài)寫入新的checkpoint

MetaServer運(yùn)行時(shí)寫入新的log：

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

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

KFS里Meta的內(nèi)存結(jié)構(gòu)主要是一棵B+樹，保存在內(nèi)存里，具體分析如下：

B-樹，B+樹的定義

關(guān)于這些樹的定義，最好還是參考算法導(dǎo)論等經(jīng)典書，網(wǎng)路上的信息有些不是很準(zhǔn)確，為了方便大家還是貼一個(gè)鏈接：

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

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

這是我個(gè)人的理解：

雖然B樹可以在非葉子節(jié)點(diǎn)命中，會縮短一些平均查找長度，但是B+樹在這種應(yīng)用一個(gè)優(yōu)勢就是每個(gè)節(jié)點(diǎn)都有指向next節(jié)點(diǎn)的指針，對于范圍查詢或者遍歷操作很適合。對于文件系統(tǒng)的一個(gè)ls某個(gè)子目錄的需求，用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

各節(jié)點(diǎn)的介紹

（1）Meta類是子節(jié)點(diǎn)的父類，其最主要的成員變量是fid

有三個(gè)葉子節(jié)點(diǎn)：MetaChunkInfo，MetaDentry，MetaFattr

（2）MetaDentry：實(shí)現(xiàn)從文件名到fid的映射，對于每個(gè)文件（目錄）都擁有1個(gè)MetaDentry

成員變量包括：

dir：文件父目錄的fid

name：dentry的名稱，實(shí)際就是文件名

（3）MetaFattr：實(shí)現(xiàn)從fid到文件屬性的映射，對于每個(gè)文件（目錄）都擁有一個(gè)MetaFattr。

成員變量包括：

Type：文件還是目錄

numReplicas：文件有幾份副本

mtime：修改時(shí)間

ctime：屬性修改時(shí)間

crtime：文件創(chuàng)建時(shí)間

chunkcount：連續(xù)的chunk數(shù)目

filesize：文件大小

nextChunkOffset：最后一個(gè)chunk在文件的所處的offset

mode_t mode：文件屬性（rwx位）

key：由KFS_FATTR，fid來構(gòu)成，可以通過fid直接找到保存文件屬性的節(jié)點(diǎn)。

（4）MetaChunkInfo：標(biāo)志某個(gè)文件對應(yīng)的chunk信息，如果一個(gè)文件包含多個(gè)chunk，那么需要有多個(gè)MetaChunkInfo。

成員變量包括：

offset：chunk在文件中的偏移量，因?yàn)橐粋€(gè)文件可能由多個(gè)chunk組成

chunkId：chunk的id號

chunkVersion：chunk的version值

（5）Node：實(shí)現(xiàn)的是B+樹的內(nèi)部節(jié)點(diǎn)，這種節(jié)點(diǎn)僅僅作為索引用途，存儲實(shí)際元數(shù)據(jù)信息的節(jié)點(diǎn)位于最底部的葉子節(jié)點(diǎn)。

成員變量包括：

NKEY = 32：每個(gè)節(jié)點(diǎn)最多擁有的關(guān)鍵字?jǐn)?shù)目，實(shí)際上也就是最多擁有的子節(jié)點(diǎn)數(shù)目，如果多余這個(gè)值節(jié)點(diǎn)進(jìn)行分裂

NSPLIT = NKEY / 2：分裂之后每個(gè)節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)目

NFEWEST = NKEY - NSPLIT：每個(gè)節(jié)點(diǎn)最少擁有的關(guān)鍵字?jǐn)?shù)目，如果少于這個(gè)值兩個(gè)節(jié)點(diǎn)進(jìn)行合并

count：節(jié)點(diǎn)實(shí)際擁有的關(guān)鍵字?jǐn)?shù)目

Key childKey[NKEY]：節(jié)點(diǎn)存儲的關(guān)鍵字列表

MetaNode *childNode[NKEY]：節(jié)點(diǎn)指向子節(jié)點(diǎn)的指針列表

Node *next：指向下一個(gè)同級節(jié)點(diǎn)的指針

實(shí)際上每個(gè)內(nèi)部節(jié)點(diǎn)的階數(shù)為32，可以有32個(gè)子節(jié)點(diǎn)，而每個(gè)葉子節(jié)點(diǎn)只保存一個(gè)key值。

三類子節(jié)點(diǎn)在B+樹中如何分布？

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

一個(gè)不太相關(guān)的思考

看上面的三類子節(jié)點(diǎn)，我們可以發(fā)現(xiàn)chunk的位置信息并沒有保存在B+樹里，它是單獨(dú)保存在一個(gè)Map數(shù)據(jù)結(jié)構(gòu)里的，也不會在meta server里進(jìn)行持久化，而是每次chunk啟動時(shí)向meta server來報(bào)告。之所以不做持久化，可以這樣來理解：

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

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

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

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

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

    1，必須出現(xiàn)1次而且僅出現(xiàn)1次的字段：required

    2，可能出現(xiàn)1次或者0次的字段：optional

    3，可能出現(xiàn)0次或者N次字段：repeated

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

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

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

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

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

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

    看到這里，各位可能已經(jīng)在心里默念了：WTF！別急，可以結(jié)合一個(gè)例子來看：

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

    1)對第1個(gè)出現(xiàn)的值，其r始終為0，因此'en-us'的r為0

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

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

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

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

    總結(jié)下，看repetition level注意兩點(diǎn)：1,只比較該值和上一個(gè)值；2,只需要看這兩個(gè)值的重復(fù)位置上有幾個(gè)repeated字段

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

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

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

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

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

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

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

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

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

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

    Bit編碼：可以用于各種數(shù)據(jù)類型

1，字典編碼：

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

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

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

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

    因?yàn)長ZO之類的壓縮窗口一般比較小（LZO默認(rèn)是64KB），而Orc的字典壓縮是以整個(gè)字段為范圍來壓縮的，壓縮率會更好。

2，Run-Length編碼：

    對于int,long,short類型的字段，使用Run-Length編碼。該Run-Length能夠?qū)Φ炔顢?shù)列（完全相等也屬于等差數(shù)列）進(jìn)行壓縮，該等差數(shù)列需要滿足以下兩個(gè)條件：

    1，至少包含3個(gè)元素

    2，差值在-128~127之間（因?yàn)椴钪涤?Byte來表示）

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

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

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

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

    例子：

    原始數(shù)字：12,12,12,12,12,10,7,13

    經(jīng)過Run-Length的數(shù)字：2,0,12,-3,10,7,13

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

3，Bit編碼：

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

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

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

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

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

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

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

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

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

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

    Hive type model:RCfile在底層存儲時(shí)不保存類型，都當(dāng)做Byte流來存儲

    Separtor complex columns:Orc將復(fù)雜類型拆開存儲

    Splits Found Quickly：不很理解

    Default Column group size：不用解釋了

    Files per a bucket：不很理解

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

    Versioned metadata:不很理解

    Run-Length Data-coding：整數(shù)類型做Run-Length變長編碼

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

    Store Row Count：每個(gè)Stripe會存儲行數(shù)

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

    Store internal indexes:存儲了一個(gè)輕量級的index

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