阅读 2562

LSM存储引擎基本原理

本文是阅读了DDIA的第三章后整理的读书笔记,总结了什么是LSM存储引擎,以及在实现上的一些细节优化。

1 什么是LSM?

LSM一词最早来自于Partrick O'Neil et al.发表的文章[1],全称为"Log-Structured Merged-Tree"。后来,Google发表的Bigtable论文[2]将其发扬光大。

目前所有基于该思想实现的存储引擎,我们都可以称之为“LSM存储引擎”,例如:

  • LevelDB。Google开源的单机版Bigtable实现,使用C++编写。
  • RocksDB。来自Facebook,基于LevelDB改良而来,使用C++编写。
  • HBase。最接近的BigTable开源实现,使用Java编写,是Hadoop的重要组成部分。
  • Cassandra。来自Facebook的分布式数据库系统,同样借鉴了BigTable设计思想,使用Java编写。
  • 其它等等。

不同于传统的基于B+树的数据库存储引擎,基于LSM的引擎尤其适合于写多读少的场景。

我们先从一个最简单的存储引擎示例出发,然后再描述LSM引擎的基本原理。

2 最基本的存储引擎

一个最基本的存储引擎,需要支持下面两个操作:

  • Put(Key, Value)
  • Get(Key)

加快写操作

我们知道,磁盘特别是机械硬盘,其随机写的速度是非常惨不忍睹的。但是,如果我们是顺序写磁盘的话,那速度跟写内存是相当的:因为减少了寻道时间和旋转时间。而且顺序写的情况下,还能将数据先放到buffer,等待数量达到磁盘的一页时,再落盘,能进一步减少磁盘IO次数。

所以,这里我们规定,每一次写数据都追加到数据文件的末尾。

#!/bin/sh
# usage: ./Put key value
echo "$1:$2" >> simpledb.data
复制代码

注:如果对同一个key写多次,最终以最后一次的值为准(即对于读请求,应返回最后一次写入的值)。

加快读操作

要从数据文件里面查询:

# usage: ./Get key
grep "^$1:" simpledb.data | sed -e 's/^://g' | tail -n 1
复制代码

直接从数据文件查询的效率是很低的:我们需要遍历整个数据文件。

这时候就需要“index”来加快读操作了。我们可以在内存中保存一个key到文件偏移量的映射关系(哈希表索引):在查找时直接根据哈希表得到偏移量,再去读文件即可。

当然,加了索引表也相应地增加了写操作的复杂度:写数据时,在追加写数据文件的同时,也要更新索引表。

这样的建索引的方式有个缺点:因为索引map必须常驻内存,所以它没法处理数据量很大的情况。当内存无法加载完整索引数据时,就无法工作了。

防止数据文件无止尽的增长

我们再来看看另外一个问题:传统的B+树,每个key只会存一份值,占用的磁盘空间是跟数据量严格对应的。但是在追加写的方案中,磁盘空间是永无止尽的,只要这个系统在线上运行,产生写请求,文件体积就会增加。

解决文件无限增长的方法就是 compaction

  • 将数据文件分段(segment)。每个segment文件最大不超过多少字节,当segment满时创建一个新的segment。当前写入的segment称为活跃segment。同一时刻只有一个活跃segment。
  • 后台定期将旧的segment文件合并压缩:每个key只保留最新的值。

以上就是一个简单的基于内存索引+文件分段并定期压缩的存储引擎。可以看到,它能够提供很好的写入性能,但是无法应对数据量过大的场景。

3 LSM存储引擎

首先看看怎么解决内存索引过大的问题。

假定现在我们要存储Nkey-value,那么我们同样需要在索引里面保存Nkey-offset。但是,如果数据文件本身是按序存放的,我们就没必要对每个key建索引了。我们可以将key划分成若干个block,只索引每个blockstart_key。对于其它key,根据大小关系找到它存在的block,然后在block内部做顺序搜索即可。

在LSM里面,我们把按序组织的数据文件称为SSTableSorted String Table)。只保存block起始key的offset的索引,我们称为“稀疏索引”(Sparse Index)。

sstable_sparse_index

而且,有了block的概念之后,我们可以以block为单位将数据进行压缩,以达到减少磁盘IO吞吐量。

那怎么生成和维护SSTable呢?

我们可以在内存里面维护一个平衡二叉树(例如AVL树或者红黑树)。每当有Put(Key, Value)请求时,先将数据写入二叉树,保证其顺序性。当二叉树达到既定规模时,我们将其按序写入到磁盘,转换成SSTable存储下来。

在LSM里面,我们把内存里的二叉树称为memtable

注意,这里的memtable虽然也是存在内存中的,但是它跟上面说的稀释索引不一样。对每一个SSTable,我们都会为它维护一个稀疏的内存索引;但是memtable只是用来生成新的SSTable

再来看看如何compaction

SSTable,我们同样是通过 segment + compaction 来解决磁盘占用的问题。

segmentmemtableSSTable的时候就已经做了。

compaction则依赖后台线程定期执行了。但是对于有序的SSTable,我们可以使用归并排序的思路来合并和压缩文件:

sstable_merge

故障恢复

如果在将memtable转存SSTable时,进程挂掉了,怎么保证未写入SSTable的数据不丢失呢?

参考数据库的redo log,我们也可以搞一个log记录当前memtable的写操作。在有Put请求过来时,除了写入memtable,还将操作追加到log。当memtable成功转成SSTable之后,它对应的log文件就可以删除了。在下次启动时,如果发现有残留的log文件,先通过它恢复上次的memtable

Bloom Filter

对于查询那些不存在的key,我们需要搜索完memtable和所有的SSTable,才能确定地说它不存在。

在数据量不大的情况下,这不是个问题。但是当数据量达到一定的量级后,这会对系统性能造成非常严重的问题。

我们可以借助Bloom Filter(布隆过滤器)来快速判断一个key是否存在。

布隆过滤器的特点是,它可能会把一个不存在的key判定为存在;但是它绝不会把一个存在的key判定为不存在。这是可以接受的,因为对于极少数误判为存在的key,只是多几次搜索而已,只要不会将存在的key误判为不存在就行。而且它带来的好处是显而易见的:可以节省大量的对不存在的key的搜索时间。

合并策略

上文已经提到,我们需要对SSTables做合并:将多个SSTable文件合并成一个SSTable文件,并对同一个key,只保留最新的值。

那这里讨论的合并策略(Compaction Strategy)又是什么呢?

A compaction strategy is what determines which of the sstables will be compacted, and when.

也就是说,合并策略是指:1)选择什么时候做合并;2)哪些SSTable会合并成一个SSTable

目前广泛应用的策略有两种:size-tiered策略和leveled策略。

  • HBase采用的是size-tiered策略。
  • LevelDB和RocksDB采用的是leveled策略。
  • Cassandra两种策略都支持。

这里简要介绍下两种策略的基本原理。后面研究LevelDB源码时再详细描述leveled策略。

size-tiered策略

简称STCS(Size-Tiered Compaction Strategy)。其基本原理是,每当某个尺寸的SSTable数量达到既定个数时,合并成一个大的SSTable,如下图所示:

stcs

它的优点是比较直观,实现简单,但是缺点是合并时的空间放大效应(Space Amplification)比较严重,具体请参考Scylla’s Compaction Strategies Series: Space Amplification in Size-Tiered Compaction

空间放大效应,比如说数据本身只占用2GB,但是在合并时需要有额外的8G空间才能完成合并,那空间放大就是4倍。

leveled策略

STCS策略之所以有严重的空间放大问题,主要是因为它需要将所有SSTable文件合并成一个文件,只有在合并完成后才能删除小的SSTable文件。那如果我们可以每次只处理小部分SSTable文件,就可以大大改善空间放大问题了。

leveled策略,简称LCS(Leveled Compaction Strategy),核心思想就是将数据分成互不重叠的一系列固定大小(例如 2 MB)的SSTable文件,再将其分层(level)管理。对每个Level,我们都有一份清单文件记录着当前Level内每个SSTable文件存储的key的范围。

Level和Level的区别在于它所保存的SSTable文件的最大数量:Level-L最多只能保存 10 LSSTable文件(但是Level 0是个例外,后面再说)。

lcs

注:上图中,"run of"就表示一个系列,这些文件互不重叠,共同组成该level的所有数据。Level 1有10个文件;Level 2有100个文件;依此类推。

下面对照着上图再详细描述下LCS压缩策略:

先来看一下当Level >= 1时的合并策略。以Level 1为例,当Level 1SSTable数量超过10个时,我们将多余的SSTable转存到Level-2。为了不破坏Level-2本身的互不重叠性,我们需要将Level-2内与这些待转存的SSTable有重叠的SSTable挑出来,然后将这些SSTable文件重新合并去重,形成新的一组SSTable文件。如果这组新的SSTable文件导致Level-2的总文件数量超过100个,再将多余的文件按照同样的规则转存到Level-3

再来看看Level 0Level 0SSTable文件是直接从memtable转化来的:你没法保证这些SSTable互不重叠。所以,我们规定Level 0数量不能超过4个:当达到4个时,我们将这4个文件一起处理:合并去重,形成一组互不重叠的SSTable文件,再将其按照上一段描述的策略转存到Level 1

4 引用

[1] Patrick O’Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O’Neil: “The Log- Structured Merge-Tree (LSM-Tree),” Acta Informatica, volume 33, number 4, pages 351–385, June 1996. doi:10.1007/s002360050048

[2] Fay Chang, Jeffrey Dean, Sanjay Ghemawat, et al.: “Bigtable: A Distributed Storage System for Structured Data,” at 7th USENIX Symposium on Operating System Design and Implementation (OSDI), November 2006.

关注下面的标签,发现更多相似文章
评论