首页 - 石家庄新闻 - 从B树到LSM树 以及LSM树在HBase中的应用

从B树到LSM树 以及LSM树在HBase中的应用

发布时间:2022-05-27  分类:石家庄新闻  作者:seo  浏览:6526

在MySQL、SQL Server、Oracle等有代表性的关系数据库中,数据存储和索引的基本结构是大家熟悉的B树和B树。而在一些主流的NoSQL数据库如HBase、Cassandra、LevelDB和RocksDB中,则采用日志结构的归并树(LSM树)来组织数据。本文首先通过B树介绍LSM树,然后说明如何在HBase中使用LSM树。

查看b树

为什么我们在RDBMS中需要B树(或者广义地说,索引)?底线:减少寻道时间。广泛应用于存储系统中的HDD是由磁介质机械旋转的,这使得其顺序访问更快,随机访问更慢。用B树组织数据可以很好的利用HDD的这一特性,其本质就是多路径平衡搜索树。下图是一个高度为3的4向B树的示例。

与普通B树相比,B树的非叶节点只有索引,所有数据都位于叶节点,叶节点上的数据会形成有序链表。B的主要优点如下:

结构扁平化,高度低(一般不超过4层),随机找的次数少;

数据存储密度高,且都位于叶节点,查询稳定,遍历方便;

叶子形成有序链表,范围查询转化为顺序读取,效率高。相对而言,B树必须按中间顺序遍历才能支持范围查询。

当然,B树并不完美。它的主要缺点有两个:

如果写入的数据比较分散,那么在寻找写入位置时,很有可能子节点不在内存中,最终会产生大量的随机写入,降低性能。下图来自TokuDB的PPT,说明了这一点。

如果B树运行了很长时间,写了很多数据,随着叶子节点的分裂,其对应的块将不再按顺序存储,而是变得分散。这时执行范围查询也会变成随机读取,降低了效率。

可见,B+树在多读少写(相对而言)的情境下比较有优势,在多写少读的情境下就不是很有威力了.当然我们可以用SSD把读写速度提高一倍,但是成本也很高,对于海量存储集群来说不可行。日志合并树(LSM树)是作为B树的替代而产生的。

了解LSM树

LSM树实际上并不是一棵树,而是两棵树或多棵树的集合或树状结构(注意这一点)。下图显示了具有两种结构的最简单的LSM树。

(上图中,少了一个字母D)

在LSM树中,最低最小的C0树位于内存中,而更先进的C2 C1,树位于磁盘中。数据会先写入内存中的C0树,当其大小达到一定阈值时,C0树中的全部或部分数据会被刷入磁盘中的C1树,如下图所示。

因为内存的读写速度比外存快很多,所以将数据写入C0树的效率非常高。并且当数据从存储器刷到磁盘时,数据被预先排序,也就是说,

ong>LSM树将原本的随机写操作转化成了顺序写操作,写性能大幅提升。不过,它的tradeoff就是牺牲了一部分读性能,因为读取时需要将内存中的数据和磁盘中的数据合并。总体上来讲这种tradeoff还是值得的,因为:

可以先读取内存中C0树的缓存数据。内存的效率很高,并且根据局部性原理,最近写入的数据命中率也高。

写入数据未刷到磁盘时不会占用磁盘的I/O,不会与读取竞争。读取操作就能取得更长的磁盘时间,变相地弥补了读性能差距。

在实际应用中,为了防止内存因断电等原因丢失数据,写入内存的数据同时会顺序在磁盘上写日志,类似于我们常见的预写日志(WAL),这就是LSM这个词中Log一词的来历。另外,如果有多级树的话,低级的树在达到大小阈值后也会在磁盘中进行合并,如下图所示。

下面以HBase为例来简要讲解LSM树是如何发挥其作用的。

HBase中的LSM树

在之前的学习中,我们已经了解HBase的读写流程与MemStore的作用。MemStore作为列族级别的写入和读取缓存,它就是HBase中LSM树的C0层。并且它确实也没有采用树形结构来存储,而是采用了跳表——一种替代自平衡BST的结构。MemStore Flush的过程,也就是LSM树中C0层刷写到C1层的过程,而LSM中的日志对应到HBase自然就是HLog了。

为了方便理解,再次祭出之前用过的HBase读写流程简图。

HFile就是LSM树中的高层实现。从逻辑上来讲,它是一棵满的3层B+树,从上到下的3层索引分别是Root index block、Intermediate index block和Leaf index block,对应到下面的Data block就是HFile的KeyValue结构了。HFile V2索引结构的图示如下:

我们已经知道,HFile过多会影响读写性能,因此高层LSM树的合并即对应HFile的合并(Compaction)操作。合并操作又分别Minor和Major Compaction,由于Major Compaction涉及整个Region,对磁盘压力很大,因此要尽量避免。

HBase为了提升LSM结构下的随机读性能,还引入了布隆过滤器(建表语句中可以指定),对应HFile中的Bloom index block,其结构图如下所示。

通过布隆过滤器,HBase就能以少量的空间代价,换来在读取数据时非常快速地确定是否存在某条数据,效率进一步提升。

标签: hbase  磁盘  索引  数据存储 

快捷导航
最新发布
标签列表