SSTables, LSM Tree 与 B-Tree

​ 目前最常用的两种数据库无非是:关系型数据库NoSQL数据库。 这两种数据库的存储引擎通常是:面向页的存储引擎(page-oriented storage engine)例如B树和日志结构存储引擎(log-structured storage engine)例如SSTables 。

SSTables

SSTables(Sort String Table) 是google的大数据三驾马车之一 — 《Bigtable: A Distributed Storage System for Structured Data》中引入的名词,在LevelDB,Bitcask, Cassandra, Hbase, 甚至Lucene的关键词字典(term dictionary)中都得到了应用。

SSTables可以看做是对最常见的键值索引进行的扩展。 例如最简单的键值存储引擎可能是这样的:

1
2
3
4
5
6
7
8
9
#!/bin/bash

db_set () {
echo "$1,$2" >> database
}

db_get () {
grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

​ 上面的几行代码实现了一个简单的键值数据库,数据写入是追加写,由于后面写入的值应该覆盖先前写入的值,因此读取是从后往前读的。

​ 由于上面的程序写入记录只是简单的往文件里追加一行记录,因此写入速度非常快;但是读取记录却需要从后往前顺序扫描文件,时间复杂度是O(N)。 当然,加快读取速度的方法也很简单,可以维护一份hash表。为了节约磁盘空间以及充分利用小磁盘空间,可以把上面的database文件分成一系列小文件,然后用一个后台进程去压缩数据记录(去除重复记录,只保存最新值, 忽略已经被删除的记录),只使用每个键的最新值构建hash索引。 但是hash索引有一个致命的弱点: 无法提供范围查询。而SSTables没有这个缺点。

​ 把上诉的一系列小文件按照键排序,就得到了SSTables。如下图所示:

SSTables-merge-imag

​ 如图,我们把键值数据记录,分文件(分段)以只追加写的方式写入上面的三个文件中。 然后由一个后台进程,以类似于归并排序的方式把数据合并(去除重复,去除删除的记录等)到下面的一个文件中,删除已经合并过的文件。 SSTables这种方式有很多优势:

  1. 存储数据分成若干段(可以认为分成各个不太大的文件),可以充分利用小磁盘空间,减少磁盘碎片的浪费。 另外,每个段都是有序的,可以使用类似于归并排序的方式进行合并,由于归并排序具有很好的局部性,即使是内存空间比较有限,仍旧可以有效的处理大段数据记录的合并。
  2. 实时的变更可以写入一个内存中的数据结构(memtable),通常以红黑树和平衡树实现,例如Google BigTable论文中就是用红黑树实现的memtable。在写入memtable之前,需要追加一条操作日志到一个磁盘上的小文件中,以备机器突然宕机时,用于恢复数据。当memtable的大小达到一定的阈值后,就可以把memtable里面的数据写入到一个SSTable文件中了。于此同时,此时正发生的变更操作可以写入一个新的memtable中。
  3. 当查找记录时,从最近时间的数据记录开始查找,先检查memtable里的数据,然后读取最新的SStable文件,直到查到记录或者遍历完所有SSTable文件。为加快查找,况且这些合并后的SSTable文件都是有序的,可以为这些合并后的SSTable文件建立范围索引(如下图),范围索引根据内存的大小和SSTables文件的整体大小,确定范围索引键之间的跨度,索引信息一般都常驻在内存中。 另外,我们还可以用布隆过滤(Bloom Filter)判断一条记录是否存在。例如我们要在下图中查询handoff的值,根据字母序我们知道handoff在索引handbag和handsome之间,即偏移量在102134 ~ 104667之间。 我们从102124开始扫描,最终查找到handoff的值: 5741。但是对于不存在的值,我们也需要花费类似的查询开销。对于一些不太严格的场景,可以使用一个bitmap做布隆过滤,节省查询不存在值的开销。 image-20190601235236021
  4. 由于SStables是有序的,因此可以有效的支持范围查询,以及顺序读取。

LSM Tree

Google发表的SSTables的结构和Patrick O‘Neil等人发表的LSM-Tree(Log-Structured)非常类似。后者的发表,奠定了日志结构文件系统的基础。目前所有基于合并压缩排序文件原则建立起来的存储引擎都通常被叫做LSM存储引擎。

B Tree

​ B树常常被拿来和红黑树相比较,前者由于和磁盘亲和性非常好,常常被用作面向磁盘的存储引擎,后者由于稳定快速的增删改查性能(时间复杂度都是log(N))而被广泛的用作内存中的数据结构。前者为人熟知的被用于MySQL的MYISAM引擎,InnoDB引擎中,以及etcd中。后者被用于STL库中的Map, Set容器中,Nginx,epoll的实现中,以及上文中的memtable中, 应用非常广泛。这里仅重点讨论一下B树的特点。

B树是一种非常严格的平衡二叉搜索树。通常靠沿途分裂和沿途合并保持B树平衡有序的性质。而且每个节点非常大(通常和内存页一样大,Linux中内存页大小一般默认是4K), 一个节点通常包含50~2000个关键字,具体个数取决于关键字的大小。

图片来源:算法导论

上图中 t 是B树的度(t >= 2), 根据B树的定义,除根结点外每个结点至少包含 t-1个关键字,每个结点最多包含2t-1个关键字。h为树的高度。因此,一个高度为 4,t 为 500的B树,至少可以包含 个结点。使用时,B树的根节点一般常驻内存中。也就是说,检索这个结点中的任意一个,至多需要读四次磁盘。如果程序具有局部性,因为B树读取数据时,是整块读取,因此速度会更快。为了使得每个结点中容纳更多的关键字,B树的一个变种: B+树,只在内部节点中存放数据记录的地址,在叶子节点存放实际的数据记录的内容,这样所有数据记录内容都有序的排列在一起,各个记录之间以指针相连,大大加快顺序读取的速度。

简单总结一下B树的优点,如下:

  1. 减少读取磁盘的次数: 读写DRAM(主存)的速度比读写磁盘速度的大约快10万倍可以参考CSAPP 虚拟存储器章节),并且第一次读写某扇区第一字节的速度比连续读该磁盘其他字节的速度约慢10万倍。 因为B树每个结点包含的关键字非常多,而且完全平衡,根结点常驻内存,大大减少了访问磁盘的次数。
  2. 局部性和磁盘亲和性: B树的结点大小与磁盘页一样大(Linux中一般是4K,这是和虚拟存储器系统运行的机制有关,存储器映射是虚拟页(磁盘, linux中一般是4K)映射到物理页(主存,Linux中一般是4K),然后由虚拟存储器系统在背后默默地悄无声息地完成数据移动的工作。B树就实现了页读取,即:每次读取一个内存页的数据块。对于具有时间局部性和空间局部性的读取操作,减少了重新读取磁盘,读写头扇区寻址的开销。
  3. B树的插入和删除: B树在插入和删除的时候,是采用沿途分裂和沿途合并的方式进行的,基本上避免了回溯(只删除时有一种情况需要回溯),沿途分裂和沿途合并的方式使得结点分裂和合并时,不需要再次访问磁盘,花费多于的开销。
  4. B+树: 为了进一步使得一个结点内容纳更多的关键字,进而减小树高,提高局部性,减少磁盘访问次数, B+树在内部节点中只存放数据记录的地址,在叶子节点存放实际的数据记录,这样数据记录都有序的排列在一起,各个记录之间以指针相连,方便顺序读取。

SSTables VS B Tree

一个简单的准则是:通常情况下,SSTables(LSM Tree)索引写操作更快;B 树索引读操作更快。 因为,SSTables的读取操作往往需要读取多个SSTable;而B树的写操作需要同步更新索引,索引越多,写操作越慢。 但是数据库的性能一般对数据类型和数据量等特征很敏感,所以选择最适合的数据库的时候,最保险的做法还是实际压测。尽管如此,了解数据库的存储引擎,对数据库的选型,对数据库行为的解释,以及如何高效实用数据库都非常有帮助。

参考资料