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用到的几种编码格式。