Hadoop SequenceFile

详见：http://hadoop.apache.org/docs/r1.0.4/api/org/apache/hadoop/io/SequenceFile.html

3个概念：记录(Record)、块(Block)、文件(File)。

记录（Record）: Hadoop SequenceFile的存储格式是通用的KV数据存储格式，key和value都是变长二进制数据。Record Len 表示的是key 和value 的占用的byte之和，Record压缩方式中 key 是不压缩。同步点Sync 作用数据恢复和扫描。当指定读取的位置不是记录首部的时候，通过读取一个同步点的记录，不至于读取数据的reader “迷失”。 (hadoop实现：每2000byte 就插入一个同步点，这个同步点占16 byte ，包括同步点标示符：4byte ，一个同步点的开销是20byte 。）对二进制数据，任何字符都可出现，故采用单字节的Sync标识难于区分数据和同步点，需要采用多字节的Sync(什么样的多个字节常被用来所Sync标识？0xFFFFFFFFFFFFFFFF？)。

块（Block）：存储Block header和多个record数据。Hadoop SequenceFile可认为没有块概念，只有Block-Compressed SequenceFile才会将多个record压缩后一起存储，详见hadoop文档。

文件(File): 文件头+数据。存储如下信息：文件标识SEQ，key和value的格式说明，压缩相关信息，metadata(二级索引，The sequence file also can contain a “secondary” key-value list that can be used as file Metadata. This key-value list can be just a Text/Text pair, and is written to the file during the initialization that happens in the SequenceFile.Writer constructor, so you can’t edit your metadata.)，Sync。常规的文件头需要的数据：文件标识、Sync标识、数据格式说明(含压缩)、文件元数据(时间、owner、权限等)、检验信息等。

HBase

Hbase MapFile

Hbase最初直接使用Hadoop的MapFile实现有序的Key存储(将数据和索引分别存成Hadoop SequenceFile)。用MapFile实现有序Key存储需要解决2个问题：1）如何删除数据？2）如何保证数据有序？解决方案：1）使用删除标志Type；2）内存中排序，达到阈值后写成MapFile(MemStore实现)。

MemStore 的方案意味这存在多个MapFile，这样对于读数据意味着可能需要扫描多个文件。为了减少需要读取的文件数，Hbase的设计者引入compaction：1) 将多个小文件合并成大文件；2）将所有的文件合并成一个大文件。

HFile V1

引入版本：HBase 0.20。核心特性：1）将index和数据合成一个文件(为减少index量，可只对每个块的首个key做索引)；2）增加metadata特性。

The Meta block is designed to keep a large amount of data with its key as a String, while FileInfo is a simple Map preferred for small information with keys and values that are both byte-array. Regionserver’s StoreFile uses Meta-Blocks to store a Bloom Filter, and FileInfo for Max SequenceId, Major compaction key and Timerange info. This information is useful to avoid reading the file if there’s no chance that the key is present (Bloom Filter), if the file is too old (Max SequenceId) or if the file is too new (Timerange) to contain what we’re looking for.

HFile V2

引入版本：HBase 0.92。核心特性：1）引入多级索引；2）引入基于块的索引和Bloom Filter(解决问题：无需载入所有索引和Bloom Filter数据)。

从图上可知，HFileV2有3种索引：Root Index记录每个块首个key极其索引；Leaf Index记录块内每个record的索引；intermediate index记录每个块最后的key极其索引。(Since the index is moved to block level you then have a multi-level index, meaning each block has its own index (leaf-index).  The last key of each block is kept to create the intermediate/index that makes the multilevel-index b+tree like.)

前向扫描和后向扫描：The block header now contains some information: The “Block Magic” field was replaced by the “Block Type” field that describes the content of the block “Data”, Leaf-Index, Bloom, Metadata, Root-Index, etc. Also three fields (compressed/uncompressed size and offset prev block) were added to allow fast backward and forward seeks.

前缀压缩和差异压缩（Prefix and Diff Encoding）:HBase的数据是有序的，因此Key差异不大，为了提高压缩比，引入2种针对性的压缩算法。

HFile V3

为了进一步提高压缩率：1）将块内的key和value分开存储, key存在块前面，value存在块后面。2）Compress timestamps。

相关文章

Hadoop I/O: Sequence, Map, Set, Array, BloomMap Files

HBase I/O – HFile

附录 oceanbase(类似HFile)

记录：oceanbase的记录value是有结构的二进制数据。格式为：keyLen(2B)+keyData+valueData。 其中valueData由一个或多个common::ObObj对象串化而成。详见：oceanbase\src\sstable\ob_sstable_row.h

块(Block)格式：block header + serialized rows + row index。详见：oceanbase\src\sstable\ob_sstable_block_builder.h

文件格式：详见：oceanbase\src\sstable\ob_sstable_writer.h

Leveldb 实现原理：http://www.cnblogs.com/haippy/archive/2011/12/04/2276064.html
leveldb源代码分析: http://blog.nosqlfan.com/tags/leveldb