五分钟技术趣谈 | 浅谈HBase数据结构和系统架构

作者：张程、张俊杰，单位：中国移动智慧家庭运营中心智慧互联产品部

Apache HBase是以谷歌的BigTable为模型，一种分布式的、面向列的开源数据库，用于收集数据并为各种谷歌服务（如地图、金融、地球等）提供请求，最初是Powerset for Natural Language Search公司的一个项目，用于处理大量稀疏的数据集，于2007年2月首次发布，2008年1月成为Apache Hadoop的一个子项目，2010年，HBase成为Apache的顶级项目。

Part 01●LSM树模型●

常见的的关系型数据库，如MySQL、SQL Server、Oracle等，使用B+ Tree作为数据存储与索引的基本结构，非叶子节点只存放索引数据，叶子节点存放所有数据和指向相邻节点的指针，具有高效的范围查询和稳定的查找效率，以及具有较小的读放大和空间放大。采用磁盘随机读写方式，且以磁盘数据页作为最小的读写单元，随着数据大量插入，导致叶子节点不断分裂，最终导致逻辑连续的数据存放到不同物理磁盘块位置，产生大量的读随机 I/O，从而导致范围查询效率下降和读写放大，磁盘随机读写成为 B+Tree 的瓶颈，适用于读多写少的场景。

Log Structured Merge Tree (日志结构合并树) ，一种先于BigTable出现的文件组织方式，最早可以追溯到1996年 Patrick O'Neil等人的论文，因其独特的数据组织方式（Log Structured）和需要在后台通过不断合并（Merge）的维护方式而得名，在BigTable出现之后，开始被重视被广泛应用于 HBase、Cassandra、ClickHouse、LevelDB、RocksDB 和 TiDB 等写密集型 KV 数据库和存储引擎上。

LSM 树实际上并非是一种具体的数据结构，而是一种具备顺序追加、多层数据结构和定期合并等特性的数据处理逻辑。将离散的随机写转化为批量的顺序写，减少了磁盘寻道时间提高了写入性能，适用于写密集型应用，在Patrick O'Neil的论文中给出了多级的日志结构合并树的结构。

C0 tree在内存中，C1到Ck tree在磁盘上，Ck tree是一个有序的树状结构，数据的写入流转从C0 tree 内存开始，不断被合并到磁盘上更大容量的Ck tree上。由于内存的读写速率都比外存要快非常多，因此数据写入的效率很高。并且数据从内存刷入磁盘时是预排序的，也就是说，LSM树将原本的随机写操作转化成了顺序写操作，写性能大幅提升。但是读取时需要将内存中的数据和磁盘中的数据合并，牺牲了一部分读性能。

Part 02●HBase系统架构●

HBase基LSM树模型构建一个分布式的列数据库，HBase采用Master/Slave架构搭建集群，隶属于Hadoop生态系统，数据存储于HDFS中，其整体的系统架构如下图所示：

一个RegionServer由一个(或多个)HLog、一个 BlockCache以及多个Region组成

· HLog用来保证数据写入的可靠性；

· BlockCache可以将数据块缓存在内存中以提升数据读取性能；

· Region是HBase中数据表的一个数据分片，一个RegionServer上通常会负责多个Region 的数据读写。

一张表会被水平切分成多个Region，每个 Region负责自己区域的数据读写请求。一个Region由多个Store组成，每个Store存放对应列簇的数据，比如一个表中有两个列簇，这个表的所有Region就都会包含两个Store。每个Store包含一个MemStore和多个HFile，用户数据写入时会将对应列簇数据写入相应的 MemStore，一旦写入数据的内存大小超过设定阈值，系统就会将MemStore中的数据落盘形成HFile文件。HFile存放在HDFS上，是一种定制化格式的数据存储文件，方便用户进行数据读取。

Part 03●MemStore实现●

MemStore是LSM中C0Tree的实现，由一个可写的Segment，以及一个或多个不可写的Segments构成，所有的数据写入操作，会按顺序先写入日志HLog，再写入MemStore，当MemStore中数据大小超过阈值之后，再将这些数据批量写入磁盘，生成一个新的StoreFile（HFile），最后多个StoreFile（HFile）又会进行Compact。

·通过MemStoreLAB（Local Allocation Buffer），使用堆外一段固定的内存段Chunk来存储KeyValue数据，当Region执行flush之后释放的就是一段Chunk所占有的连续内存，而不是KeyValue占有的零散内存，很好地解决了内存碎片的问题。

·使用CellSet存放所有的KeyValue的数据，CellSet核心是一个ConcurrentSkipListMap，数据按照Key值有序存放，而且在高并发写入时，性能远高于ConcurrentHashMap，通过跳表实现高效插入、更高的并发性。

在HBaseV2.x后，使用带合并写内存的CompactingMemStore，MemStore中的Active的Segment数据先Flush成一个Immutable的Segment，多个Immutable Segments可在内存中进行Compaction，当达到一定阈值以后才将内存中的数据持久化成HDFS中的HFile文件。

Part 04●HFile文件结构●

HBase使用列族式存储，列族数据是存储在一起的，列族式存储介于行数存储和列式存储之间。

·一张表，只设置一个列族，等同于行式存储；

·一张表，设置大量列族，每个列族下仅有一列，等同于行数存储。

在将文件结构前，先看下数据存储格式，当put到hbase一个key和value的时候，会增加一条记录：

(Table, RowKey, Family, Qualifier, Timestamp) -> Value

该记录以字节流的方式存储，对应到磁盘中的存储格式为：

从HBase开始到现在，HFile经历了三个版本，主要变更如下：

·HFile V1 ，HBase 0.92之前，结构简单，参考了Bigtable的SSTable以及Hadoop的TFile，Region Open的时候，需要加载所有的Data Block Index数据，另外，第一次读取时需要加载所有的Bloom Filter数据到内存中。一个HFile中的Bloom Filter的数据大小可达百MB级别，一个RegionServer启动时可能需要加载数GB的Data Block Index数据

·HFile V2 ，使用分层索引，按需读取Data Block的索引数据和Bloom Filter数据，避免在Region Open阶段或读取阶段一次读入大量的数据，有效降低时延。等load-on-open加载到完，regions server可以认为完成启动，加速启动时间

·HFile V3 ，从0.98版本开始引，主要是为了支持Tag特性，在HFile V2基础上只做了微量改动

在下文内容中，主要围绕HFile V2的设计展开。

无论是Data Block Index，还是Bloom Filter，都采用了分层索引的设计，最多可支持三层索引：

·最上层为Root Data Index，放在一个称之为Load-on-open Section区域，Region Open时会被加载到内存中，从Root Data Index 索引到 Intermediate Block Index

·中间层为Intermediate Index Block，从Intermediate Block Index 索引到 Leaf Index Block

·最底层为Leaf Index Block，可直接索引到Data Block

在实际场景中，Intermediate Block Index基本上不会存在，因此，索引逻辑被简化为：由Root Data Index直接索引到Leaf Index Block，再由Leaf Index Block查找到的对应的Data Block。

Part 05●HFile Compaction合并●

HBase Compaction分为两种：Minor Compaction和Major Compaction，通常我们简称为小合并、大合并，以短时间内的IO消耗，以换取相对稳定的读取性能，下面是一个简单示意图：

Minor Compaction，指选取一些小的、相邻的HFile将他们合并成一个更大的HFile。通过少量的 IO 减少文件个数，提高读取操作的性能，适合较高频率的跑。缺点是只合并了局部的数据，对于那些全局删除操作，无法在合并过程中完全删除。默认情况下，minor compaction会删除选取HFile中的TTL过期数据。

Major Compaction，指将一个Store中所有的HFile合并成一个HFile，这个过程会清理三类没有意义的数据：被删除的数据（打了Delete标记的数据）、TTL过期数据、版本号超过设定版本号的数据。另外，一般情况下，Major Compaction时间会持续比较长，整个过程会消耗大量系统资源，对上层业务有比较大的影响。因此，生产环境下通常关闭自动触发Major Compaction功能，改为手动在业务低峰期触发。

Part 06●总结●

HBase基于LSM Tree模型，通过MemStore和StoreFile实现内存和磁盘中的日志合并，使用顺序追加、定期合并方式，提高数据的写入性能，支持海量数据的存储。通过Compaction合并，以短时间内的IO消耗，获取相对稳定的读取性能。在实际业务中，需要配置合适的合并策略，在读放大、写放大和空间放大中，做好权衡和取舍。