B-tree和LSM-tree

Page content

最初的数据库

LSM-tree得从最简单的数据库的shell实现说起,如:

#! /bin/bash

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

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

db_set将两个参数简单追加database文件,而db_get利用匹配出来的结果去掉key和逗号得到value,再利用tail获取到最set到database中去。

读取优化

很明显,由于是追加写也是最简单的写操作,这种set方式通常足够高效,但是对于get,事件复杂度就需要上升到O(n),所以最常见的想法是对数据追加索引,比如利用哈希表在内存中设置一个key,而key对应的value设置为该key/value在文件中的偏移。

key byte offset
abc 0
b 64
aacb 3613

就有类似于这样一个哈希表存储在内存中,这也就是Bitcask的核心做法,只需要一次磁盘寻址就可以加载到这个value,适合每个键的值频繁更新的场景。

存储优化

因为都会往同一个文件追加文件,所以设置键的写入,会造成磁盘空间用尽。解决办法是将日志分解成一定大小的段,文件到达一定大小就关闭,后续的写入写到新的段文件中,读请求仍旧使用旧段文件,当后台线程将后台文件合并/压缩后,读请求就能切换到新的合并段上,旧段文件安全删除。

其他

  • 文件格式:替换类似于CSV的字符格式为二进制格式。
  • 删除记录:追加删除标记,当合并时检测到这个标记丢弃响应的key
  • 崩溃恢复:这个主要针对存储在内存中的哈希表,当机器宕机后,哈希表将会丢失,重启恢复需要重新读取所有的段文件才能恢复,Bitcask的做法时将相应段的哈希表快照存储磁盘中。
  • 记录写入:写入操作的过程中如果发送了崩溃,那么最新的值将是不完整的,可以在一条记录前追加校验,如果损毁就需要丢弃。
  • 并发控制:写入需要按先后顺序写入,所以写线程通常只有一个,而读取是可以多个同时进行的。

SSTables

SSTables全名为排序字符串表(Sort String Tables),写入的记录会被排序。对key进行排序会有如下的有点:

  1. 合并段更加高效:方法类似于归并排序,同时读取多个段文件,比较每一个文件的第一个键,将最小的键拷贝到输出文件,重复这个过程,就可以得到一个按键排序的合并段文件。另外就是文件大于可用内存也可以进行,像前面的方法,需要将所有kv都保存在内存中,合并完成才能写入磁盘,而归并的方法只需要维护输入端的数量个kv,即使出现相同的kv,也可以保证他们是相邻的,覆盖即可。
  2. 压缩内存:查找特定键时,不需要保存所有键的索引,而是建立稀疏索引,比如1个几KB大小的文件,只需要1个key即可。根据这个key的字典序找到稀疏索引中提供的偏移,读取该部分,找到相应的key即可。
  3. 范围查询:请求某个范围内的多个key/value更加方便。

构建和维护SSTables

  1. 写入Key写写入内存表(类似于红黑树的平衡树)
  2. 内存表大小大于某个阈值,根据二叉排序树的特点,顺序写入磁盘,此时在内存中新生成一个内存表
  3. 查表时,先查询内存表找到偏移,如果没找到,那么查找以前的段文件
  4. 后台周期性合并,压缩,丢弃不需要的key
  5. 写入key需要追加日志(用于恢复内存表),但是超出阈值并写完当前内存表后,可以删除该日志。

优化SSTables

  • 读取SSTables中不存在的key会回溯到最旧的段文件,所以开销很大,对于这种存在问题,可以使用布隆过滤器。
  • 其他是一些压缩/合并的方式,例如LevelDB/RocksDB使用的分层压缩,HBase使用大小分级,而Cassandra两种都支持。

LSM-tree和SSTables

SSTables的算法本质就是LevelDB和RocksDB所使用,并且最初这种索引结构是被称为以日志结构的合并树(Log-Structured Merge-Tree),因此,基于合并和压缩排序文件原理的存储引擎,通常被称为LSM存储引擎。

B-tree

B树其实已经非常熟悉了,常见于各大关系型数据的索引。Btree也是按键排序的key-value对,以及高效的区间查询。但是在存储方面,是以4KB甚至更大作为存储单元,这样更加借鉴底层硬件。

由于B树也保持平衡,具有n个key的B树深度也是O(log n),其中一个页中包含子页的引用数量称为分页因子,当分页因子为500的4KB页的四级树可存储256TB数据。

崩溃问题:和日志合并树一样,也要考虑写时发生崩溃的问题,因为在重写页时,如果发生崩溃直接导致的结果是索引破坏,所以需要预写日志WAL(WriteAhead Log)在写入前,追加写入日志文件,用于恢复B树到最近一致状态。

优化B-tree

  • 写时复制:修改的页被写入不同位置,创建完成后修改父页中的引用。这样就不用覆盖和维护WAL
  • 保存键的缩略信息,减少key在页内占用,增加分页因子,降低层数
  • 尝试让页的磁盘位置更加接近,减少寻道时间
  • 另外一点就是常见的添加一个额外的指针到相邻的页,这样就不需要跳回父页,减少不必要的I/O
  • 最后就是分型树等等

LSM-tree和B-tree的优劣

通常认为B树读取更快,而LSM树写入更快。

LSM-tree的优点

对于B树来说,一次写操作需要写两次磁盘:

  • 写入日志(WAL)
  • 写入到实际的B树中,另外还有页分裂的可能,导致多次I/O

而对于LSM树来说:

  • 追加写一次
  • 但是又反复的后台压缩和SSTables合并

所以要注意一次写入请求会导致多次磁盘写(写放大),SSD由于其物理性质所决定,只能承受住比机械硬盘更低覆盖重写次数,所以需要加入考量,另外,如果写入磁盘占用的带块越多,可用的磁盘带宽也就越少。而LSM时拥有较低的写放大。

另外,回到SSTables的构建,LSM的写入时是从内存一次性写入到磁盘的,也就是其磁盘块更加连续,顺序写比随机写要快得多,相比于分散的磁盘块,拥有更低的寻道时间。相关联的还有碎片化问题,由于B树是面向页的,也可能被分裂成多个页时,页中空间无法使用,导致碎片化。而SSTables的定期合并可以消除碎片话,拥有更加紧凑的数据表达方式。

LSM-tree的缺点

  • 压缩过程(I/O)中会干扰当前读写操作(I/O),造成读写等待。
  • 另外B-tree的key在磁盘中,只有一个副本,而LSM-tree有多个。所以在关系型数据库中,B树可以直接定义锁在页中,完成键范围上的事务隔离。

参考

  • 《数据密集型应用系统设计》