这是来自于阿里技术嘉年华的一个分享，因为在百度也考虑过类似的事情，所以听得比较有感悟，这里把相关内容整理一下。

首先尊重版权，还是把原链接和作者贴上：

http://adc.alibabatech.org/carnival/history/schedule/2013/detail/main/286?video=0

来自于阿里吴威工程师的分享

首先需要说明一点，跨机房hadoop可能应用场景并不是很多，国内像BAT这种巨头也许需要，但是大部分的中小公司也许并不需要这个，也许这是个屠龙之技，呵呵。

把这个问题分三段来讲，第一段是问题出现的背景，第二段是解决该问题的难点，第三段是最终的解决方案。

（一） 背景：

先要看下为什么需要做一个跨机房的大集群？

大集群的优点在于数据管理和授权容易（这个问题在一个多部门的大公司还是很重要的）；跨部门的使用数据容易，无需重复拉取数据。

在集群达到一定规模时，单机房（机房内的容量是有限的）已经无法满足集群的需求了，要想一劳永逸的解决问题，需要建设一个跨机房的hadoop集群。

（二）技术挑战：

2.1 NameNode的性能问题：

         在管理一个巨大的hadoop集群时，由于原始的Namenode是单节点，因此会成为一个性能瓶颈，遇到的性能问题主要包括两方面：存储容量问题（存储元数据）和计算压力（处理rpc请求，修改内存树时候需要全局锁）问题。

         其中存储容量问题可以依赖内存的垂直扩展来解决，但是计算压力却很难通过提升硬件来解决（因为目前厂商的主要发展方向是多核，而非提高主频）

2.2机房之间的网络限制：

         机房之间的网络永远是个硬件条件的限制，跨机房的网络传输带来了数据延时和带宽限制：

1， 延时一般是在10ms之内，而hadoop上大部分运行的是离线作业，基本可接受

2， 带宽限制的问题比较大，因为单机房内的点对点带宽一般是在1Gbps，而机房之间的带宽确在20Mbps左右，非常有限。

2.3资源组之间的管理

         每个部门可以看做一个资源组，它们可能会互相使用对方的数据，因此如何规划计算和存储的位置就很重要，否则会在多个机房之间出现大量的数据拷贝。

（三）解决方案：

先看下整个跨集群hadoop的架构图：

重点介绍里面三点，也就是和上面三个问题相对应的：

1， 可以看到这里画出了两个NN（namenode），它们实际上还是属于一个hadoop集群，这是业界里的一个解决方案：HDFS Fedaration，它为了解决元数据节点性能问题；

2， 可以看到这里有一个cross node节点，它是用来在两个机房之间同步数据的，它的设计考虑到了机房间的网络限制；

3， 最后是groupA、groupB，这是为了解决数据产出方和使用方关系来用的。

3.1 Federation

Federation相关资料见：

http://hadoop.apache.org/docs/current/hadoop-project-dist/hadoop-hdfs/Federation.html#HDFS_Federation

为了水平扩展Namenode，federation使用了多个互相独立的namenode。它们之间互相不需要通信，每个datenode需要向全部namenode注册并发送信息。

BlockPool是属于一个namenode的block集合，每个blockpool之间也是互相独立的。

         在federation里，有一个需要关注的问题，就是多个namenode的地址如何对用户进行透明？它采用的解决方案是目录树挂载的方案（社区有个viewFS，应该就是为了解决这个问题）：熟悉linux或者nfs的朋友应该都知道mount这个概念，目录树挂载就是这个意思。

不过使用目录树挂载也存在着一个问题，就是各个子目录下的存储资源需要人为的介入管理，不能出现严重的不均。

3.2 crossNode

         机房间的网络限制要求不能出现大规模、长时间的数据拷贝，需要一个专门管理机房间数据拷贝的进程，叫做crossNode。它是独立部署的一个节点，和元数据节点是分离的。

         它能提供的功能概括来说主要包括以下三点：

a） 根据预置的跨机房文件，进行数据拷贝

b） 处理实时的数据拷贝请求

c） 进行跨机房的数据流量控制

如何得知跨机房文件列表？

         由于离线任务基本都是定时触发的，可以根据对历史作业的分析来形成一个跨机房文件列表

3.3   资源组之间的管理

各个资源组之间存在数据的依赖，我们希望通过资源组管理，能实现大部分任务在本机房内产出数据，只有少量跨机房产出数据；大部分任务读取本机房的数据副本，只有少量跨机房读取数据。

为了标识资源组之间的数据依赖性，定义一个资源组之间的距离概念：一个资源组访问另一个资源组的数据量越多，则两者的距离越近，应该将距离接近的资源组放在同一个机房内。

为了让计算和产出尽可能地靠近，使用一个MRProxy，对于不同类型的任务做不同处理：

a）            离线计算：跨机房列表中的数据正在传输中（DC1->DC2），DC2上的 Job 被暂停调度，等待传输完毕

b）            Ad-hoc查询：DC2上的 Job 需要读DC1上的数据，Job暂停调度，通知 CrossNode，数据传输完毕后继续调度

c）             特殊情况：跨机房数据 Join，DC1大表，DC2小表，Job 调度到DC1上，跨机房直接读取DC2数据，无需等待

由于是根据视频和ppt整理，并没有代码或者文档，所以可能有些地方的理解有偏差，欢迎来提意见~

使用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交换写入，这样比较高效一些）

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使用的是列存模型，对于基本类型列存较容易做到；但是对于嵌套类型，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及网上解析。

    字典编码：用于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等，将其降维成基本类型来存储，这个也是值得借鉴的，如果有空之后会进行分析。

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