LSM树的不同实现介绍

2018-01-13 10:52:55来源:https://juejin.im/post/5a58542b6fb9a01c9064ce44作者:稀土掘金人点击

分享

这个需要和BTree一起来讲,我们都知道BTree是Balance Tree,为了维持Balancing的特性,每次读入的时候需要对树进行调整,是一笔不小的时间损耗。在一些使用场景下(例如google爬取网页),需要高性能写入,而对读的要求并不是那么高。 因此,LSM树是基于这样的背景下发展出来的,针对类似的场景LSM提出了很多优化措施。


应用场景

举几个比较常见的例子:HBase、LevelDB、RocksDB


HBase大家可能比较熟,LevelDB和RocksDB分别是Google和FaceBook推出的,同样也是开源的。对于英语好的同学可以直接看看官方的文档,对于LSM的工业实现会有一个更深入的理解。


为什么要看不同的DB的实现呢?因为虽然是同个数据结构,但是在实现上通过类似布隆过滤器等手段,不同的实现方式能够大大提升其效率,因此了解不同公司的LSM树实现还是很有必要的。


LSM树基础

LSM Tree,全写Log-Structured Merge Tree。本质上通过顺序写入log的方式,大大的提升写入的性能,同时NoSQL的结构属性帮助其天然适合Shard。


基本操作

1.将数据写入内存memtable(同时硬盘中复制一份,保证系统宕机数据不丢失) 2.数据到达一定容量,将数据flush到硬盘SStable,同时对硬盘中的数据进行merge


复杂之处:Compaction

SStable在硬盘中不断增多,会带来读的巨大压力。这时候就需要“数据结构”所独特的价值之处了,通过不同的Compaction(压缩)来构建不同的数据结构,能够有效的减低读的效率。 用空间来换取时间,这也是HBase、LevelDB、RocksDB三者之间的真正区别所在。


HBase中的LSM实现

先来看下HBase中的实现,如图所示。



网络上很多提到了Tree的概念,其实HBase的实现并没有依托于Tree。大家肯定有个疑问,“HBase那不是会很慢?”事实上肯定不慢,正是靠着布隆过滤器,HBase很好的诠释了数据结构时间和空间之间的艺术。


布隆过滤器

布隆过滤器和动态缓存有点像,不过都是数据结构很典型的例子,使用空间大幅度的降低了时间的使用。


bloom 借助的是一个大大大的位表以及多个hash函数,例如图中,将{x,y,z}的用3个hash函数映射到位表中。那么位表中有n个位置有标1,(3<=n<=9)。


如果这个时候来了个w,w经过3个hash函数,对应到位表上的位置有一个映射的值为0,那么说明w肯定不在{x,y,x}中。
如果w的3个hash函数映射后,都为1,并不能够说明w在{x,y,z}中。有可能是类似上图4,5,6位置格,而那些格是有不同的值映射出来的。
HBase的Compaction

如同上文所讲,Compaction才是一个LSM树的核心。HBase中分为两种:


Minor Compaction
Major Compaction

两者都是合并SStable(在HBase中SStable叫HFile)。Major Compaction在合并的时候回删除一些过期的Key,持续时间比较长,一般在业务低峰期手动触发。(业务低峰期可使用hbase.offpeak.start.hour和hbase.offpeak.end.hour配置)


同时,不同版本的HBase也提供了不同的Compaction策略让使用者来决策:


RatioBasedCompactionPolicy
ExploringCompactionPolicy

两种具体介绍看:http://hbasefly.com/2016/07/13/hbase-compaction-1/


因为笔者没有实际使用过HBase的经验,所以不敢大加妄论,各位看官可以通过上面的连接看看比较专业的介绍。但是,对于笔者这样的业务方而言,HBase没有提供索引,而是通过Scanner去查询数据,似乎这个数据结构不够“完美”。


LevelDB and RocksDB

RocksDb是facebook团队基于google开发的LevelDB的升级版本,提供了很多LevelDB所不具备的feature。(延伸一下,TiDB是一个newSQL数据库,它的底层就是基于RocksDb。网上已经有很多公司已经将TiDB上到生产环境,笔者所在公司的数据团队也已经灰度的一部分数据到TiDB上了。说明RocksDb也是挺可靠的。) LevelDB的文档比较少,所以一起来看RocksDB的实现吧。


LevelDB文档地址: https://github.com/google/leveldb/blob/master/doc/impl.md RocksDB文档地址: https://github.com/facebook/rocksdb/wiki


Compactions

RocksDB也提供了多种的策略:


Leveled style compaction
Universal style compaction
FIFO Compaction

这里主要介绍下Leveled style compaction,因为他是起源于LevelDB,方便大家和LevelDB一同了解。


Leveled style compaction

如上图,可以看到Leveled style将SStable划分为不同的Level,除了Level 1中可能存在重复的key之外,Level 2之后都不会有重复的key。同时每个SStable中,key都是有序的,不要小看了有序的作用,看到查找你就会知道他的妙用。


另外,每一层的容量是递增的,这个也比较好理解,如上图。

如上图,compaction的过程其实也比较简单,当某一个level的数量大于容量的时候,会选一个SStable与level+1的数据进行merge。选取的level+1的SStable是存在和当前SStable存在相同key的。如果生成的SStable导致level+1的容量也超过限度,那么继续往下merge。


比较吊的是,除了level0和level1的merge,其他的merge都是可以多线程一起进行的,因为是没有重复key的,所以不用担心并发问题。


查找

就像上面说的有序性能够极大的提升key查找的效率,查找通过两步:


二分查找所有文件的start和end,找到可能存在key的file
二分查找file中所有包含的key

所有的查找都是通过二分查找来实现的。


总结

本文从LSM介绍入手,概览了一些LSM的工程实现。由于还没深入了解这几种DB的源码,仅仅只能从文档中找到一些有价值的内容给大家看,希望能够抛砖迎玉,让大家重新体会到数据结构的妙用。如有内容不对或者想交流一下,请随时联系我~


最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台