数据库选型时必知的存储引擎基础

在评估和选型数据库的时候，人们往往将重点放在数据建模的灵活性，一致性保证，线性可伸缩性，容错性，低延迟，高吞吐量和易于管理等方面。但怎么才能评判出这些指标呢？很多人往往会网上一通搜索和看官方文档，再加上自己的“经验”来得出这些指标。

这些都没有错，但如果你对数据库的底层的存储引擎有基本的了解，那么可以帮助你更加有底气和科学的得出你评估的数据库是如何真正的保证了上面的指标。

本文就带你了解数据库存储引擎的基础，从而帮你在日后存储引擎的选型上做出明智的选择。

先来看看存储引擎的一个定义：

数据库存储引擎是数据库服务器（database server）用来在底层内存（memory）和存储系统（storage system）中存储，读取，更新和删除数据的内部软件组件（component）。

从1970年以来，数据库存储引擎有很多，但被人们广为讨论的也就两种，比如上周我们就讨论到这两个：基于B-tree的和基于LSM的。

基于B-Tree的存储引擎

B树在1971年首次被公布，是一种自平衡树数据结构，可对数据进行排序，并允许以对数时间进行搜索，顺序访问，插入和删除。

基于B树的存储引擎就是基于B树（B-tree）的主索引（primary index）和二级索引（secondary index）与基于行存储的组合。也就是基于B树的索引加上基于行存储组成了这个存储引擎。基于行存储指的就是在数据库中一个单独的记录。

优点和缺点

B树通常会变宽而变浅，因此对于大多数查询而言，几乎只需要遍历很少的节点。就是高吞吐量，低延迟读。但是，为了保证有序的数据结构，写操作就变成了随机写，写的性能就会变差。这是因为随机写到存储（storage，一般叫“磁盘”）要比顺序写入更慢更麻烦。此外，对块（block）中某一行进行更新也需要对整个块的read-modify-write，这显然也很昂贵。总之就是写入慢，读取快。

实际使用情况

基本上流行的单体式关系/ SQL数据库的默认存储引擎都遵循了B树结构。包括Oracle DB，MS SQL Server，IBM DB2，MySQL（InnoDB）和PostgreSQL。 现在看起来貌似B树引擎就仅适用于SQL数据库，但其实不然，NoSQL数据库也可以基于B树引擎。 比如：MMAPv1是MongoDB的原始存储引擎（3.2之前的版本中的默认值），就是基于B树，虽然后来MongoDB换了其他存储引擎。Couchbase也是存储引擎基于B树的NoSQL数据库。

基于LSM（Log Structured Merge）树的存储引擎

随着2000年后，数据量急剧的增长，更大的数据集需要写入数据库中。由于B-tree引擎写入性能差导致在某些场景下不再受欢迎。数据库设计人员开始转向一种全新的数据结构，称为LSM(log-structured merge)树的结构,该数据结构于1996年首次在学术研究中发表。

LSM树使用一种推迟和批量对索引更改的算法，以一种类似于合并排序的高效手法将更改从基于内存的组件（上图中的C0）到一个或多个磁盘组件（C1到CL）级联。请注意，在内存中的C0组件处的随机写入将转换为在基于磁盘的C1组件处的顺序写入。

LSM的原理：将对数据的修改增量保存在内存中，达到指定大小限制之后批量把数据flush到磁盘中，磁盘中树定期可以做merge操作，合并成一棵大树，以优化读性能。不过读取的时候稍微麻烦一些，读取时看这些数据在内存中，如果未能命中内存，则需要访问较多的磁盘文件。极端的说，基于LSM树实现的hbase写性能比mysql高了一个数量级，读性能却低了一个数量级。简而言之，LSM树原理就是把一颗大树拆分成N颗小树。它首先写入内存中，随着小树越来越大，内存中的小树会flush到磁盘中，磁盘中的树定期可以做merge操作，合并成为一个大树，用来优化读性能。

优点缺点

LSM引擎现在基本就是在处理大量快速增长的数据的存储的场景中的事实标准。因为它能够执行快速顺序写入（与B树引擎中的慢速随机写入相反），特别是在本质上更适合顺序访问的基于现代闪存的SSD上。也更适合分层存储，在这些分层存储中，可以利用具有不同性能/成本特征的不同类型的存储，例如RAM，SSD，HDD和远程文件存储（例如AWS S3），尤其是当数据量增长到无法在一个单体存储机制中存储的时候。

那么问题来了：与基于B树的引擎相比，基于LSM树的引擎读取吞吐量是不是更差？从理论上讲，答案是肯定的。MongoDB的WiredTiger的基准测试就印证了这个推断。（WiredTiger是同时支持B树和LSM树的存储引擎）。

这是因为LSM引擎表现出比B树更高的读取放大和空间放大。

至于放大是个什么概念，自己看以下解释：

写放大（write amplification）是数据库写入的字节数乘以用户更改的字节数。 由于某些LSM树会随时间重写不变的数据，因此LSM树中的写放大可能很高。 读取放大（read amplification）是与返回的字节相比，数据库必须实际读取多少字节才能将值返回给用户。 由于LSM树可能必须在多个位置查找以查找数据或确定数据的最新值，因此读取放大可能很高。 空间放大（space amplification）是相对于数据库包含多少逻辑字节，磁盘上存储多少字节数据。 由于LSM树未就地更新，因此经常更新的值会导致空间放大。

简单来说，LSM引擎在读取操作期间会消耗更多的CPU资源，并占用更多的内存/磁盘存储空间。比如一个查询使用LSM树的话可能需要多次随机读取。但是，这些问题在实践中得到了缓解。时光飞逝岁月穿梭，存储变得越来越便宜。另外使用布隆过滤器（以减少在查询期间要检查的文件数量）和per-SSTable min-max metadata hints（用于范围查询）之类的方法，可使读取速度更快。

实际使用情况

LSM引擎现在几乎是流行的NoSQL数据库的默认数据库存储引擎。包括Apache Cassandra，Elasticsearch（Lucene），Google Bigtable，Apache HBase和InfluxDB。甚至一些著名的嵌入式数据库（例如LevelDB和RocksDB）也是基于LSM。MyRocks就是其中一种嵌入式RocksDB实现，它取代了MySQL中默认的InnoDB引擎。YugabyteDB存储引擎DocDB也是基于RocksDB的定制版本构建的。包括前面提到的，MongoDB的默认存储引擎WiredTiger也支持B树和LSM两种配置。

总结

总之，数据库存储引擎要么使用读性能更好的B树（B-tree），要么选择使用写性能更好的LSM树。数据库API层（SQL vs. NoSQL）是独立于存储引擎的。B树可能被用于SQL数据库也可能被用于NoSQL数据库，LSM同样如此。所以在你选择要使用什么数据库的时候，不妨回看此文，想想数据库的底层存储引擎到底适不适合你的场景。