数据库存储引擎对比

B 树类

B 树就是可以修改类存储引擎比较典型的一个代表。它是目前的分布式数据库,乃至于一般数据库最常采用的数据结构。它是为了解决搜索树(BST)等结构在 HDD 磁盘上性能差而产生的,结构特点是高度很低,宽度很宽。检索的时候从上到下查找次数较少,甚至如 B+ 树那样,可以完全把非叶子节点加载到内存中,从而使查找最多只进行一次磁盘操作。

下面让我介绍几种典型的 B 树结构的存储引擎。

InnoDB

InnoDB 是目前 MySQL 的默认存储引擎,同时也是 MariaDB 10.2 之后的默认存储引擎。

根据上文的评估指标看,它的 B+ 树节点是可变的,且叶子节点保存的数据是经过排序的。同时由于数据的持续写入,在高度不变的情况下,这个 B+ 树一定会横向发展,从而使原有的一个节点分裂为多个节点。而 InnoDB 使用缓存的模式就是:为这种分裂预留一部分内存页面,用来容纳可能的节点分裂

这种预留的空间其实就是一种浪费,是空间放大的一种表现。用 RUM 假设来解释,InnoDB 这种结构是牺牲了空间来获取对于读写的优化

在事务层面,InnoDB 实现了完整的隔离级别,通过 MVCC 机制配合各种悲观锁机制来实现不同级别的隔离性。

WiredTiger

WiredTiger 是 MongoDB 默认的存储引擎。它解决了原有 MongoDB 必须将大部分数据放在内存中,当内存出现压力后,数据库性能急剧下降的问题。

它采用的是 B 树结构,而不是 InnoDB 的 B+ 树结构。这个原因主要是 MongoDB 是文档型数据库,采用内聚的形式存储数据(你可以理解为在关系型数据库上增加了扩展列)。故这种数据库很少进行 join 操作,不需要范围扫描且一次访问就可以获得全部数据。而 B 树每个层级上都有数据,虽然查询性能不稳定,但总体平均性能是要好于 B+ 树的。

故 WiredTiger 首先是可变数据结构,同时由于不进行顺序扫描操作,数据也不是排序的。那么它是如何运用缓存的呢?这个部分与 InnoDB 就有区别了。

在缓存中每个树节点上,都配合一个更新缓冲,是用跳表实现的。当进行插入和更新操作时,这些数据写入缓冲内,而不直接修改节点。这样做的好处是,跳表这种结构不需要预留额外的空间,且并发性能较好。在刷盘时,跳表内的数据和节点页面一起被合并到磁盘上。

由此可见,WiredTiger 牺牲了一定的查询性能来换取空间利用率和写入性能。因为查询的时候出来读取页面数据外,还要合并跳表内的数据后才能获取最新的数据。

BW-Tree

BW-Tree 是微软的 Azure Cosmos DB 背后的主要技术栈。它其实通过软件与硬件结合来实现高性能的类 B 树结构,硬件部分的优化使用 Llama 存储系统,有兴趣的话你可以自行搜索学习。我们重点关注数据结构方面的优化。

BW-Tree 为每个节点配置了一个页面 ID,而后该节点的所有操作被转换为如 LSM 树那样的顺序写过程,也就是写入和删除操作都是通过日志操作来完成的。采用这种结构很好地解决了 B 树的写放大和空间放大问题。同时由于存在多个小的日志,并发性也得到了改善。

刷盘时,从日志刷入磁盘,将随机写变为了顺序写,同样提高了刷盘效率。我们会发现,BW-Tree 也如 LSM 树一样存在读放大问题,即查询时需要将基础数据与日志数据进行合并。而且如果日志太长,会导致读取缓慢。而此时 Cosmos 采用了一种硬件的解决方案,它会感知同一个日志文件中需要进行合并的部分,将它们安排在同一个处理节点,从而加快日志的收敛过程。

以上就是典型的三种 B 树类的存储引擎,它们各具特色,对于同一个问题的优化方式也带给我们很多启发。

LSM 类

lsm是典型的不可变数据结构,使用缓存也是通过将随机写转为顺序写来实现的

我们在说 LSM 树时介绍了它存储的数据是有顺序的,其实目前有两种无顺序的结构也越来越受到重视。

经典存储

经典的 LSM 实现有 LeveledDB,和在其基础之上发展出来的 RocksDB。它们的特点我们之前有介绍过,也就是使用缓存来将随机写转换为顺序写,而后生成排序且不可变的数据。它对写入和空间友好,但是牺牲了读取性能。

Bitcask

Bitcask 是分布式键值数据库 Riak 的一种存储引擎,它也是一种典型的无顺序存储结构。与前面介绍的典型 LSM 树有本质上的不同,它没有内存表结构,也就是它根本不进行缓存而是直接将数据写到数据文件之中。

可以看到,其写入是非常高效的,内存占用也很小。但是如何查询这种“堆”结构的数据呢?答案是在内存中有一个叫作 Keydir 的结构保存了指向数据最新版本的引用,旧数据依然在数据文件中,但是没有被 Keydir 引用,最终就会被垃圾收集器删除掉。Keydir 实际上是一个哈希表,在数据库启动时,从数据文件中构建出来。

这种查询很明显改善了 LSM 树的读放大问题,因为每条数据只有一个磁盘文件引用,且没有缓存数据,故只需要查询一个位置就可以将数据查询出来。但其缺陷同样明显:不支持范围查找,且启动时,如果数据量很大,启动时间会比较长。

此种结构优化了写入、空间以及对单条数据的查找,但牺牲了范围查找的功能

WiscKey

那么有没有一种结构,既能利用无顺序带来的高速写入和空间利用率上的优点,又可以支持非常有用的范围查询呢?WiscKey 结构正是尝试解决这个问题的一个手段。

它的特点是将 Key 和 Value 分别放在两个文件中。Key 还是按照 LSM 树的形式,这样就保证了 Key 是有顺序的,可以进行范围扫描。同时使用 LSM 树,即不需要将所有的 Key 放到内存里,这样也解决了 Bitcask 加载慢的问题。

而 Value 部分称为 vLogs(value Logs),其中的数据是没有顺序的。这种结构适合更新和删除比较少的场景,因为范围扫描会使用随机读,如果更新删除很多,那么其冲突合并的效率很低。同时在合并操作的时候,需要扫描 Key 而后确定合并方案,这个在普通的 LSM 树中也是不存在的。

WiscKey 非常适合在 SSD 进行运行,因为读取 Value 需要进行随机读取。目前 dgraph.io 的 Badger 是该模式比较成熟的实现。

ps

  • 引擎很多 不只是InnoDB
上一篇:联网数据库 IoTDB —— 存储引擎原理篇


下一篇:理解 LSM 树:写入密集型数据库的秘诀