LSM原理解读

成玉

06年,Google发表了BigTable论文,从此推开了大数据时代的大门。

为什么又提及BigTable,是因为这篇论文中使用了LSM这种数据结构。
LSM: Log Structured-Merge Tree(日志结构合并树),是一种先于BigTable出现的文件组织方式,最早可以追溯到1996年 Patrick O'Neil等人的论文。在BigTable出现之后开始被重视被广泛应用,比较有名的产品就是Hbase、Cassandra、Leveldb等。

  • 用一句话先简单概括其原理

把一颗大树拆分成N棵小树,数据先写入内存中,随着小树越来越大,内存的小树会flush到磁盘中。 磁盘中的树定期做合并操作,合并成一棵大树,以优化读性能。

  • 先用个简单的结构看一下

image 最简单的LSM tree是两层树状结构C0,C1。 C0比较小,驻留在内存,当C0超过一定的大小, 一些连续的片段会从C0移动到磁盘中的C1中,这是一次merge的过程。在实际的应用中, 一般会分为更多的层级(level), 而层级C0都会驻留在内存中。

背景

LSM被设计来提供比传统的B+树或者ISAM(Indexed Sequential Access Method)更好的写操作吞吐量,通过消去随机的本地更新操作来达到这个目标。之所以说这是一个好方法,是因为对于存储来讲问题的本质还是磁盘随机操作慢,顺序读写快。顺序读写磁盘快于随机读写主存,而且快至少三个数量级。

如果对写操作的吞吐量敏感,一个好的办法是简单的将数据添加到文件。这个策略经常被使用在日志或者堆文件,因为他们是完全顺序的,所以可以提供非常好的写操作性能。
同时他们也有一些缺点,从日志文件中读一些数据将会比写操作需要更多的时间,需要倒序扫描,直接找到所需的内容。

这说明日志仅仅适用于一些简单的场景:1. 数据是被整体访问,像大部分数据库的WAL(write-ahead log) 2. 知道明确的offset,比如在Kafka。
与此同时我们也有多种方法来支持复杂的读场景,比如二分查找、哈希、B+数等。这些方式虽提升了读的性能,却丢失了日志文件很好的写性能。

不管怎样,随机的操作要尽量减少。所以LSM就出现了,保持了日志文件写性能,以及微小的读操作性能损失。本质上就是让所有的操作顺序化。

算法

LSM将之前使用一个大的查找结构,变换为将写操作顺序的保存到一些相似的有序文件(Sorted Strings Table,简称sstable)中。所以每个文件包 含短时间内的一些改动。因为文件是有序的,所以之后查找也会很快。文件是不可修改的,他们永远不会被更新,新的更新操作只会写到新的文件中。通过周期性的合并这些文件来减少文件个数。 此时可以回到上面看图

更具体的看,当一些更新操作到达时,他们会被写到内存缓存(也就是memtable)中,memtable使用树结构来保持key的有序,在大部分的实现中,memtable会通过写WAL的方式备份到磁盘,用来恢复数据,防止数据丢失。当memtable数据达到一定规模时会被刷新到磁盘上的一个新文件,重要的是系统只做了顺序磁盘读写,因为没有文件被编辑,新的内容或者修改只用简单的生成新的文件。 image

因为比较旧的文件不会被更新,重复的纪录只会通过创建新的纪录来覆盖,这也就产生了一些冗余的数据。所以系统会周期的执行合并操作(compaction)。 合并操作选择一些文件,并把他们合并到一起,移除重复的更新或者删除纪录,同时也会删除上述的冗余。更重要的是,通过减少文件个数的增长,保证读操作的性 能。因为sstable文件都是有序结构的,所以合并操作也是非常高效的。

当一个读操作请求时,系统首先检查内存数据(memtable),如果没有找到这个key,就会逆序的一个一个检查sstable文件,直到key 被找到。因为每个sstable都是有序的,所以查找比较高效(O(logN)),但是读操作会变的越来越慢随着sstable的个数增加,因为每一个 sstable都要被检查。
所以,读操作比其它本地更新的结构慢,幸运的是,有一些技巧可以提高性能。最基本的的方法就是页缓存(也就是leveldb的 TableCache,将sstable按照LRU缓存在内存中)在内存中,减少二分查找的消耗。
即使有每个文件的索引,随着文件个数增多,读操作仍然很慢。通过周期的合并文件,来保持文件的个数,因些读操作的性能在可接收的范围内。即便有了合 并操作,读操作仍然会访问大量的文件,大部分的实现通过布隆过滤器来避免大量的读文件操作, cassandra就采用了Bloom filter的方式。

思考

我们看到LSM有更好的写性能,同时LSM还有其它一些好处。sstable文件是不可修改的,这让对他们的锁操作非常简单。一般来说,唯一的竞争资源就是 memtable,相对来说需要相对复杂的锁机制来管理在不同的级别。

而如scylladb,通过异步IO,非阻塞线程,线程和线程之间通过消息通讯,没有内存的共享,没有互斥锁,也没有原子操作来大幅的提高了cpu的效率。

2016年,Lanyue Lu等人发布了WiscKey论文,这篇论文提出了一种新的设计 WiscKey: Separating Keys from Values
in SSD-conscious Storage,专门为SSD所优化,将key和value分别存储以减少I/O放大。key存在LSM tree中, value存在WAL中,叫做value log。
通常情况下,key比较小,所以LSM tree比较小,当获取value值的时候,再从SSD存储中读取。