HBase文件格式演变之路

Apache HBase是Hadoop的分布式开源的存储管理工具，很适合随机实时的io操作。

我们知道，Hadoop的Sequence File是一个顺序读写，批量处理的系统。可是为什么HBase能做到随机的，实时的io操作呢？

Hadoop底层使用Sequence File文件格式存储，Sequence File同意以追加的方式添加k-v（Key-Value）数据，依据hdfs的append-only的特性，Sequence File不同意改动或删除一个指定的数据。仅仅有append操作是被同意的，并且你想要查找某个key，你仅仅能遍历文件，知道找到这个key为止。

所以，在这个文件格式至上搭建的HBase系统，是怎样搭建随机读写，低訪问延迟的呢？

HBase 0.20之前-MapFile

上文中提到了MapFile，是一个以Sequence File为基础的文件格式。MapFile实际上是由两个Sequence File组成的，/data存储了数据，/index存储了索引。

MapFile提供了一个按顺序存储的方式，每当N（N是可配置的）条记录写入后，会将文件偏移地址写入index文件；这就实现了高速查找，相比直接遍历Sequence File，你能够直接遍历index文件，index文件存储了更少的文件句柄，一旦找到了文件块所在的位置，能够直接跳到该文件块查找；因此查找速度很快。

可是还有另外两个问题：

1. 怎样删除或更新一个k-v记录；

2. 当插入数据不是有序的，怎样使用MapFile

MapFile文件格式例如以下：

HBase的key包含：行键，列族，column qualifier，时间戳，属性。

为了解决删除的问题，使用key中的type标记该记录是否被删除。

解决更新的问题，实际上是获取时间戳更晚的记录，正确的数据总会更接近文件的末尾。为了解决无序数据的问题，hbase将插入的数据暂存在内存中，直到一个阈值到达，hbase会将内存中的数据存储到MapFile中。hbase在内存中使用sorted ConcurrentSkipListMap数据结构存储数据，每次到达阈值（hbase.hregion.memstore.flush.size)或到达内存上限（hbase.regionserver.global.memstore.upperLimit），都会将内存中的数据向一个新的mapFile写入。因为每次flush操作都会写入一个新的MapFile，这就意味着查找时，会横跨多个文件，这也会耗费很多其它的资源和时间。

为了避免在查找get和scan扫描时横跨过多的文件，hbase中有一个线程来运行文件合并的相关操作。当线程发现文件数量达到阈值（hbase.hstore.compaction.max）后，会有一个compaction进程来运行文件合并，将小的文件合并到一个大文件里。

hbase中有两种合并模式，minor和major。minor会合并两个或多个较小的文件到一个大文件里。另外的major会合并全部的文件到一个文件里，而且运行一些清理，被删除的数据将不会被写入新的文件，而且反复的数据会被清除，仅仅留下最新的有效数据。0.20下面版本号的hbase使用上述的文件存储方式，到0.20以后，HFile V1被引入替代了MapFile。

HBase 0.20到0.92之前-HFile V1

从 HBase 0.20開始，HBase引入了HFile V1文件格式。HFile V1的详细格式例如以下：

KeyValue的详细格式例如以下：

上图中，keytype有四种类型，各自是Put、Delete、 DeleteColumn和DeleteFamily。RowLength为2个字节，Row长度不固定，ColumnFamilyLength为2个字节，ColumnFamily长度不固定，ColumnQualifier长度不固定，TimeStamp为4个字节，KeyType为1个字节。之所以不记录ColumnQualifier的长度是由于能够通过其它字段计算得到。

HFile文件的长度可变，唯一固定的是File Info和Trailer。Trailer存储指向其它块的指针，它在持久化数据到文件结束时写入的，写入后，该文件就会变成不可变的数据存储文件。数据块（data blocks）中存储key-values，能够看做是一个MapFile。当block关闭操作时，第一个key会被写入index中，index文件在hfile关闭操作时写入。Hfile V1还添加两个额外的元数据类型，Meta和FileInfo。这两个数据也是在hfile的close时被写入的。

块大小是由HColumnDescriptor设置的。该配置能够在建表时自己指定。默认是64KB。假设程序主要涉及顺序訪问，则设置较大的块大小更合适。假设程序主要涉及随机訪问，则设置较小的块大小更合适。只是较小的块也导致很多其它的块索引，有可能创建过程变得更慢（必须在每一个块结束的时候刷写压缩流，会导致一个FS I/O刷写）。块大小一般设置在8KB~1MB比較合适。

HBase的Regionserver的存储文件里，使用Meta Block存储了BloomFilter，使用FileInfo存储了最大的SequenceId，Major compaction key和时间跨度信息。这些信息在旧文件或很新的文件里推断key是否存在很实用。

BloomFilter是一种空间效率非常高的随机数据结构，它利用位数组非常简洁地表示一个集合，并能推断一个元素是否属于这个集合。

HBase 0.92到0.98之前-HFile V2

在hbase 0.92版本号中，为了改进在大数据存储下的效率，HFile做了改变。HFile V1的主要问题是，你须要载入(load)全部的单片索引和BloomFilter到内存中。为了解决问题，v2引入了多级索引和分块BloomFilter。HFile v2改进了速度，内存和缓存利用率。

HFile V2的详细格式例如以下：

上图中，主要包含四个部分：Scanned Block（数据block）、Non-Scanned block（元数据block）、Load-on-open（在hbase执行时，HFile须要载入到内存中的索引、bloom filter元数据和文件信息）以及trailer（文件尾）。

V1的时候，在数据块索引非常大时，非常难所有load到内存。如果每一个数据块使用默认大小64KB，每一个索引项64Byte，这样如果每台及其上存放了60TB的数据，那索引数据就得有60G，所以内存的占用还是非常高的。然而，将这些索引以树状结构进行组织，仅仅让顶层索引常驻内存，其它索引按需读取并通过LRU cache进行缓存，这样就不用所有载入到内存了。

v2的最主要特性是内联块。主要思想是拆分了索引和BloomFilter到每一个数据块中，来解决整个文件的索引和BloomFilter都load到内存中的问题。

由于索引被拆分到每一个数据块中，这就意味着每一个数据块都有自己的索引（leaf-index）。每一个数据块中的最后一个key被当做节点组建了类似b+树的多级索引结构。

数据块的头信息中的Block Magic被Block Type替换，Block Type包括描写叙述Block数据的一些信息，包括叶子索引，Bloom，元数据，根索引等。

详细实现来看，在写入HFile时，在内存中会存放当前的inline block index，当inline block index大小达到一定阈值(比方128KB)时就直接flush到磁盘，而不再是最后做一次flush，这样就不须要在内存中一直保持全部的索引数据。当全部的inline block index生成之后，HFile writer会生成更上一级的block index，它里面的内容就是这些inline block index的offset，依次递归，逐步生成更上层的block index，上层的包括的就是下层的offset，直到最顶层大小小于阈值时为止。所以整个过程就是自底向上的通过下层index block逐步构建出上层index block。

其它三个字段（compressed/uncompressed size and offset prev block）也被加入用于前后的高速查找。

在HFile V2中依据key查找数据的步骤例如以下：

1）先在内存中对HFile的root索引进行二分查找，假设支持多级索引，则定位到leaf index，假设是单级索引，则定位到数据块；

2）假设支持多级索引，则会从cache/hdfs中读取leaf index，然后再进行二分查找，找到相应的数据块；

3）从cache/hdfs中读取数据块；

4）在数据块中遍历查找相应的数据。

HBase 0.98開始添加了对cell tags的支持，所以其HFile结构也发生了改变。HFile V3的格式仅仅是在V2格式后添加了标签部分。其它保持不变，所以对V2保持了兼容性。用户能够从V2直接切换到V3。

转载请注明出处：http://blog.csdn.net/iAm333