浅谈HBase数据结构和系统架构 _HBase

文章插图
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中C0 Tree的实现，由一个可写的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文件。