![LSM树如何在HBase中应用](/default/index/img?u=aHR0cHM6Ly9jYWNoZS55aXN1LmNvbS91cGxvYWQvaW5mb3JtYXRpb24vMjAyMTA1MjMvMzQ3LzcwODA2Ni5wbmc=&w=245&h=&w=700)
这篇文章主要介绍“LSM树如何在HBase中应用”,在日常操作中,相信很多人在LSM树如何在HBase中应用问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”LSM树如何在HBase中应用”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!
前言
在有代表性的关系型数据库如MySQL、SQL Server、Oracle中,数据存储与索引的基本结构就是我们耳熟能详的B树和B+树。而在一些主流的NoSQL数据库如HBase、Cassandra、LevelDB、RocksDB中,则是使用日志结构合并树(Log-structured Merge Tree,LSM Tree)来组织数据。本文先由B+树来引出对LSM树的介绍,然后说明HBase中是如何运用LSM树的。
回顾B+树
为什么在RDBMS中我们需要B+树(或者广义地说,索引)?一句话:减少寻道时间。在存储系统中广泛使用的HDD是磁性介质+机械旋转的,这就使得其顺序访问较快而随机访问较慢。使用B+树组织数据可以较好地利用HDD的这种特点,其本质是多路平衡查找树。下图是一棵高度为3的4路B+树示例。
与普通B树相比,B+树的非叶子节点只有索引,所有数据都位于叶子节点,并且叶子节点上的数据会形成有序链表。B+树的主要优点如下:
结构比较扁平,高度低(一般不超过4层),随机寻道次数少;
数据存储密度大,且都位于叶子节点,查询稳定,遍历方便;
叶子节点形成有序链表,范围查询转化为顺序读,效率高。相对而言B树必须通过中序遍历才能支持范围查询。
当然,B+树也不是十全十美的,它的主要缺点有两个:
可见,B+树在多读少写(相对而言)的情境下比较有优势,在多写少读的情境下就不是很有威力了。当然,我们可以用SSD来获得成倍提升的读写速率,但成本同样高昂,对海量存储集群而言不太可行。日志结构合并树(LSM Tree)就是作为B+树的替代方案产生的。LSM树由Patrick O'Neil等人在论文《The Log-Structured Merge Tree》中提出,它实际上不是一棵树,而是2个或者多个树或类似树的结构(注意这点)的集合。下图示出最简单的有2个结构的LSM树。在LSM树中,最低一级也是最小的C0树位于内存里,而更高级的C1、C2...树都位于磁盘里。数据会先写入内存中的C0树,当它的大小达到一定阈值之后,C0树中的全部或部分数据就会刷入磁盘中的C1树,如下图所示。由于内存的读写速率都比外存要快非常多,因此数据写入C0树的效率很高。并且数据从内存刷入磁盘时是预排序的,也就是说,LSM树将原本的随机写操作转化成了顺序写操作,写性能大幅提升。不过,它的tradeoff就是牺牲了一部分读性能,因为读取时需要将内存中的数据和磁盘中的数据合并。总体上来讲这种tradeoff还是值得的,因为:
在实际应用中,为了防止内存因断电等原因丢失数据,写入内存的数据同时会顺序在磁盘上写日志,类似于我们常见的预写日志(WAL),这就是LSM这个词中Log一词的来历。另外,如果有多级树的话,低级的树在达到大小阈值后也会在磁盘中进行合并,如下图所示。下面以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就能以少量的空间代价,换来在读取数据时非常快速地确定是否存在某条数据,效率进一步提升。到此,关于“LSM树如何在HBase中应用”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注网站,小编会继续努力为大家带来更多实用的文章!