Yangming's Blog

beware the barrenness of a busy life

From Btree To LSM-tree

10 Dec 2019 » datastruct, Database

两年前对LSM-tree只有一个初步的认识;回过头一看,很多认识还不够,重写此文。

Btree和LSM-tree是存储引擎中经典的两种存储架构,关于两者的八股文也不少,原先的本文更是一个两者八股的融合;而今看着很粗鄙,而希望现在能基于自己的经历,给出自己的认识。

首先,存储引擎(本文特指单机存储引擎)的设计离不开三种放大的讨论,这就是RUM 猜想;在RUM中,一个存储引擎不能同时在read、write、storage三个方面达到最优,必然要有所取舍;而Btree选择了Read,LSM-tree选择了Write。

这里三方面的指标通常是指放大系数:

对于读放大,就是IO per query;没有Cache的之下,理想上应一次IO返回数据,但是存在多层索引的情况下,往往需要多次IO。优化读最简单的优化方式就是增加Cache,但是读的优化更重要是关注在长尾优化,因为只要你索引的层高在那摆着,永远会有读会穿透到最底层。Btree是通过增大扇出数,从而减少了层高;同样的,在LSM-tree中,也可以增大层间扇出数,减少层高,但是会带来更大的后台写放大;另外,还有通过filter、metadata进行读IO过滤;LSM-tree中关于读的优化,基本都是不够彻底,P99或者Pmax还是会有长尾。

对于写放大,就是DataWriteIntoStorage / DataWriteIntoDatabase;理想情况下,我向DB内写了N bytes的数据,DB向Disk也写N bytes的数据;但实际上,我们为了管理数据, 还需要写Meta、Index、Checksum等等其他数据。首先,这里关注的写放大只关注说了高优的用户前台写,LSM-tree在此维度取得的优势也是来自前台写,因为Btree必须按块落盘,写一个entry也是,LSM-tree则不需要;但是DB的写不仅仅发生在前台,后续很多维护操作(PgSQL的Vacuum、MySQL的Purge以及RocksDB的Compact)对磁盘的反复倒腾也不可忽略的;如果考虑上这个,在这一项上Btree和LSM-tree也不一定就孰优孰劣。不过两者在写放大上的优化手段都是类似的:

  • 优化前台可以采用合并写(Write consolidation),充分利用Disk的带宽;Btree模型的BufferPool,写日志的GroupCommit以及RocksDB的WriteBatch都是这个道理;

  • 优化后台写就是尽量减小数据重组(data reorganization),减少数据的重复搬运;在Inplace-Update的Btree中,比如InnoDB,相对来说其后台的数据搬运量不太多;数据搬运主要出现在多版本混合存储中,在LSM-tree中天然就是这样,所以Compaction问题很明显;但是在Btree类型中,PostgreSQL同样是将多版本混合存储在Heap中,因此其Vacuum进程同样成为其不可避开的问题,不过Vacuum的数据搬运工作都是集中在单个Page内部的整理,这样secondary index只需要一直保留ctid(pageid+tupleid)即可;对于LSM-tree,减少数据搬运,可通过数据复用来解决,比如在Xengine中将LSMtree基于固定大小extent来管理,在Compaction中可尽量复用non-overlap的extent;但是数据数据复用一般需要一个额外的MetaIndex部分,而解决数据搬运最直接的办法就是一次将其搬运到其最终位置上(InplaceUpdate天然就是这样,因此Btree这个问题比较少),在LSM-tree就是最后一层,因此采用tier(universal)compaction strategy能够减少写放大,比如ScyllaDB。

对于空间放大,就是DataSizeInStorage / DataSizeInDatabase;理想情况下,我总共写了N bytes的数据,Disk最终应该也只用了N bytes的空间;和写放大同理,我们还需要存储额外的信息;另外空间放大最重要的还有无效数据空间占用,常说的就是多版本和已删除的数据的清理;通常来说,Btree是InplaceUpdate虽然不会存储所有版本,到那时Page内部会有碎片;LSM-tree的SST是read-only且有序紧密排布不存在碎片浪费,这是LSM-tree不可忽略的优势。另外LSM-tree的SST可以使用前缀压缩等按条目压缩算法,效果比块压缩好,但是压缩好对应着解压代价高,有进一步拉低了读方面的能力。

以上简单介绍了存储引擎设计时考虑的维度;另外存储引擎如何才能跑得好,和底层硬件特性更是密不可分;为什么Btree在传统DB中能够得到普遍应用,其中很重要的原因就是HDD读起来实在太慢了,Btree的多路平衡树能够比较好的保证稳定且少量的IO次数;而现在企业场景下,SSD被广泛应用,虽然其在随机读写上的性能上去了,但是SSD更多考虑的是磨损均衡、内部GC效率等问题,整盘的随机读写会加剧这些问题,这使得Append-Only的存储模型能够发挥很好的用处,由此LSM-tree也得以发光发热,并且在Btree体系中的Bwtree也获得了很高的关注度。

不过这并不代表传统Btree已经日薄西山了,作为数据库更多的应该解决用户问题,LSM-tree的广泛应用我认为还有一个原因就是,在大数据的时代背景下,OLAP的性能要求。

Btree架构的传统DB,在其问世的时候,是为了解决OLTP问题出现的。底层的Page内部存储了完整的行,以及Page内部对行索引。OLAP的发展推动了列存类型存储引擎的发展,OLAP的特点的大量的读IO并且集中在某几列中;Btree倒也不是不能存Column,但是其存储不够紧凑,这会导致盘内大量的随机IO。因此,现在惯用的列存解决方案就是先将Table水平划分为多个segment,每个segment再按列划分为多个columnfamily(RocksDB之ColumnFamily),在每个Columnfamily中,则可以根据数据类型的不同,选择不同的索引和压缩算法;而Btree依然还是OLTP服务的最佳选择,像现在流行的概念HTAP中,存储模型还是将TP和AP的数据分开放,没有一个完美的银弹。