DDIA 笔记 | 存储引擎

存储引擎

什么是存储引擎呢？如果说引擎是汽车的核心部件，那存储引擎同样也是数据库的核心部件，它规定了数据存储时的结构、对数据进行增删改查操作的接口，以及索引、锁和其他功能。

存储引擎也有许多不同的分类维度。从对数据的处理方式上来看，主要有两种，OLTP 和 OLAP；而从数据存储的结构上来看，也会分为行存和列存；为了加速数据的查询，又设计出了各种不同的索引结构。

这篇文章，就从这几个角度来分别介绍一下概念、原理和优缺点，在掌握了这些有关存储引擎内部的知识，你就能更好地为自己的应用挑选合适的存储引擎，做出更有效的优化。

本文的大部分内容，来自于《Designing Data-Intensive Application》，好书值得细品。

最简单的存储引擎

如果让你用几行代码来实现一个存储引擎（或者数据库），你会怎么做？

我们可以用 linux 命令来实现数据的读取和写入：

#!/bin/bash
db_set () {
  echo "$1,$2" >> database
}

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

写入时，使用 echo 命令将数据以 key - value （键值对）的形式存入文件；查询时，使用 grep 和 sed 命令来获取 key 对应的 value，并用 tail 命令获取最新的一条数据。

这样，我们用两个函数就实现了一个最简单的数据库，可以存入 key - value 结构的数据，而且和很多真正的数据库一样，内部使用 log （日志）数据文件，并且是 append-only（仅追加）的数据文件，而正因为每次写入都是在文本尾部追加，这个数据库有非常不错的写入性能。

但是读取数据的时候，性能就不尽人意了。如果存储的数据量很大，每次使用 db_get() 查询时，必须从头到尾扫描整个数据库文件，时间开销是 O(n) 的，意味着如果数据量翻了 n 倍，查询耗时也要翻 n 倍，这是不能接受的。

为了提升数据库的查询性能，我们需要一个特殊的数据结构：index（索引）。索引就像书本的目录，提前存放了关键的元数据，查询时，就能通过这个目录快速定位到数据的真实位置，而不用通过耗时的扫描来获取数据。本质上，这也是利用空间来换取时间。

索引是一种额外的数据结构，它不会影响数据库中存放的数据，但是，它会影响数据的写入效率。每次写入数据时，还需要更新、维护相关的索引。所以，对于存储系统而言，这是一个非常重要的 trade-off：选好索引可以加速查询，但是索引又会拖慢写入。

Hash 索引

Hash 索引是一个 key - value 数据结构的索引，通常用 hash map 来实现。

上文中我们使用的小数据库，数据都是在文件末尾不停地追加写入，所以最简单可行的索引策略是：在内存中保存一个 hash map，每个 key 都映射了数据在文件中的字节偏移，也就是在文件中的存储位置。在查询时，通过 key 值能获得位置，就能定位到磁盘上具体的扇区来获取数据。在数据库里写入新的数据时，这个 hash map 也要增加对应的键值。

实际上，分布式 NoSQL 数据库 Riak，默认的存储引擎 Bitcask 就是这么实现的。这种存储引擎，非常适合 value 高频更新的情况，例如 key 是视频的 url，value 是该视频播放次数的统计值，value 会有大量的写入，而 key 值并不是很多，所以可以将整个索引放在内存中。

当然，hash map 索引也有局限性：

• hash map 要存在内存中，而内存又小又贵，因此不能有太多的 key；如果存在磁盘里，查询性能就会大打折扣，有大量的随机 I/O 读取；hash 碰撞也需要复杂的逻辑来处理。
• 范围查询很低效，需要对每个 key 进行独立的查询。

数据的合并与压缩

我们的小数据库，除了查询效率之外，还有一个比较突出的问题。我们的数据在文件末尾不断追加写入，而如果有非常多重复的 key 值，就很浪费磁盘空间，如何避免磁盘被用尽呢？

我们可以使用分段文件（segment file），当数据文件达到指定大小后，新建一个文件来继续写入，而旧的文件可以进行压缩，丢弃重复 key，仅保留最新的值。经过压缩后的分段文件会变得很小，而且多个分段文件又可以合并在一起。这个合并、压缩的过程可以使用后台线程来运行，不会影响当前的写入。

针对每一个分段文件，都有对应的在内存中的 hash map，每次查询时，先从最近一个分段文件的 hash map 开始，如果没找到对应的 key，就再往前。合并操作能有效降低分段文件的数量，所以通常不会有太多次的查询。

这个方法看起来简单，但如果想实际应用的话，还有许多东西需要考虑。例如文件的格式、崩溃后快速恢复、并发控制等等。

OLTP 和 OLAP

在业务应用系统中，一次数据写入，通常都是因为有一次交易行为，例如创建一笔交易订单，支付一笔费用。如今，系统的使用场景已经不仅仅是金钱相关的领域了，例如在博客上留下一条评论，或是游戏场景里的一次动作。但是 transaction（交易/事务）这个术语仍旧沿用至今，通常用于描述一组读写操作构成的逻辑单元。而这种面向业务、用户的数据访问模式，被称为 OLTP （OnLine Transaction Processing，在线事务处理）。

相对应的，随着大数据时代的来临，数据库更多也被用于数据分析。与事务处理不同，数据分析往往需要扫描大量的数据，用于计算、汇总和统计，这种数据访问模式，被称为 OLAP（OnLine Analytical Processing，在线分析处理）。

比较一下两者的特点：

以上，我们了解了存储引擎中，索引、分段文件的概念，以及 OLTP、OLAP 这两种不同的使用场景，接下来，我们一起来看看，如何基于这些概念来构建高性能、高可靠的存储引擎。

OLTP 中的存储引擎

LSM-tree

上文讲述了分段文件 segment file，如果我们稍微改动一下结构，将存储的健值对数据按 key 来排序，就形成了 SSTable（Sorted String Table）。

相比于使用 hash 索引的 segment file，SSTable 有以下好处：

• 合并操作可以更简单高效，类似于归并算法，如果多个分段中有重复的 key，取最新分段的值即可
• 进一步节省内存空间，不再需要把所有的 key 都存放在内存中，因为 key 排序后，保留部分的 key 就能完成查询
• 同样也可以减少磁盘空间，因为 key 按序排列，对应的数据也可以排序后压缩写入磁盘中，key 指向的是磁盘区块的开头

数据的写入是无序的，那要如何保证 key 值的有序呢？我们都知道，在磁盘里维护一个有序结构是非常困难的事，但是在内存里就相对容易。有许多树结构可以使用，例如红黑树和 AVL 树，使用这些树来保证任意顺序的写入，而在读取时有序。

于是把上述方法结合起来，存储引擎可以这样运行：

• 写数据时，把数据先存入内存中的平衡树结构（例如红黑树），这个树也被称为 memtable（内存表）
• 当内存表的大小超过阈值（一般是 MB 量级），就写入磁盘中的 SSTable 文件，即最新的分段文件。树中已经维护好了数据的顺序，所以写入 SSTable 非常高效，完成后就可以生成新的内存表
• 读数据时，先尝试从内存表中获取，然后是最新的分段文件，再一路往前查询
• 后台线程可以合并、压缩分段文件，擦除重复或者已删除的值
• 如果数据库崩溃了，内存表会丢失，为了避免这个问题，可以保存一个写入日志，仅在崩溃恢复时使用，内存表写入 SSTable 后，关联的日志就可以删除

这种索引结构由 Patrick O’Neil 等人提出，被命名为 LSM 树，这种基于合并和压缩排序文件原理的存储引擎就是 LSM 存储引擎。

为了进一步提升 LSM 存储引擎的性能，还有许多细节的设计。

例如，LSM-tree 在查询不存在的 key 时，效率很低，得一路查完所有文件才能确定 key 不存在。为了优化这种查询，存储引擎通常会使用额外的布隆过滤器（Bloom Filters）。

还有一些不同的策略来决定 SSTable 排序、合并、压缩的时机。最常见的是 size-tiered 和 leveled compaction。size-tiered 是指较新、较小的 SSTable 会被合并入较旧、较大的 SSTable 中，而 leveled compaction 是指将较旧的数据移入单独的层级（level），使得压缩可以增量进行，节省磁盘空间。

所以，LSM-tree 的核心思想是：保存一系列在后台合并的 SSTable，简单又高效。即使数据远远大于内存，也可以保持运行。数据按序存储，可以支持高效的范围查询，在磁盘上又是顺序写入，LSM-tree 可以支持非常高的写入吞吐。

B-Trees

B-tree 是目前使用最多的索引结构。它也是健值对的形式，但是和 LSM-tree 相比，是截然不同的设计哲学。

LSM-tree 将数据拆分为可变大小的分段，通常是 MB 量级，按顺序写入；而 B-tree 则是将数据拆分为固定大小的页（或者叫区块 block），通常一页的大小是 4KB，一次只读写一页。这个设计更贴近于底层的硬件，磁盘就是固定大小的区块。

每一页都有另一页的地址引用，指向另一页所在磁盘的位置，有点像指针，就可以通过页之间的引用来形成树结构，有一页是根，每次查询都是从这个根开始。页中有许多的 key，每一个子页都负责了一定范围内连续的 key，key 之间的差值就表明了数据的范围。页中还有许多子页的引用，子页的数量被称为分支系数（branching factor），通常是数百的量级。

如果想要更新一个 key 对应的值，首先要找到存有这个 key 的页，更改 value，再将整个页写回磁盘。如果想要新增一个 key，同样先找到 key 所在范围的页，往里面插入 key；如果页中没有足够的空间来插入 key，就会将这一页拆分为两个半页，父页也要更新 key 的范围。

这个算法保证了树的平衡，即一个包涵 n 个 key 的 B-tree，深度为 O(log n)。例如一个 4 层，每页大小 4 KB，分支系数为 500 的树，可以存储 256TB 的数据。所以大部分数据库中的 B-tree，深度为 3 或者 4，不需要经过太多次的引用就能找到对应的页。

可靠的 B-tree

覆盖更新页数据是磁盘操作，而如果写入的同时造成了页分离，一次更新就需要磁盘多次旋转、写入，要是这时候数据库崩溃了，该怎么办呢？

为了保证数据库在崩溃时也可靠，通常会在磁盘里增加一个额外的数据结构：WAL（write-ahead-log，话也被称为 redo log）。这个仅追加的文件保存了 B-tree 在真正更新页数据及其自身前的所有修改日志，当数据库在崩溃后启动，可以用这个日志来使 B-tree 复位到与先前一致的状态。

更新页面时，多线程同时访问 B-tree 也是需要考虑的问题，否则不同线程能读取到不一致的数据，通常使用 latches（轻量级锁）来保存树的数据结构。LSM-tree 则不必担心这点，后台的合并操作并不会影响查询。

B-tree 的优化

B-tree 有很多变体，最常见的就是 B+ tree。

在 B+ tree 中，内部页只存有 key，key 只需要提供足够的信息来充当键范围之间的边界，页中也就能存放更多的 key，减少树的层级。数据都存放在最底层的页上，并且有链指针，可进行快速的范围查询。

比较 LSM-tree 和 B-tree

简单来说，LSM-tree 写入更快，而 B-tree 查询更快。

LSM-tree 的优势

一次更新，使用 B-tree 索引的话，至少得写入两次数据。第一次是 WAL 日志，为了崩溃恢复，第二次才是页本身的数据，而且页更新的时候，整个页都得覆盖写入。

一次数据库的写入导致磁盘的多次写入，这种情况被称为写扩增（write amplification）。使用 SSD 时要考虑这种情况，因为 SSD 的区块会磨损，写入次数是有限的。

对于重写入的应用，性能的瓶颈很可能是数据库写入磁盘的效率，所以写扩增会直接影响性能。

虽然 LSM-tree 在压缩、合并 SSTable 时也会有多次写入，但是相比较于 B-tree，写扩增更少，并且是顺序写入 SSTable 文件，而不是不像 B-tree 中的页是覆盖更新，这对于机械硬盘来说比较重要，因为顺序写入比随机写入快得多。

另外一点，得益于 LSM-tree 的压缩，所以在磁盘上的文件占用空间也比 B-tree 少，B-tree 的页分裂也会导致磁盘上有难以利用的碎片化的空间。

LSM-tree 的劣势

LSM-tree 的合并操作带来了不少好处，同时也带来了一些影响。这个操作可能会影响到读写操作。磁盘的资源是有限的，一个请求可能需要等待磁盘完成合并操作。磁盘的带宽也是固定的，对于一个空数据库，全部的带宽可以用来初始写入，而随着数据的增加，更多的带宽会用于合并操作。

如果写入的吞吐很高，并且没有配置好合并的频率，和有可能造成合并赶不上写入。没有合并的分段会持续扩增，直至磁盘用尽，查询也会因为要回溯更多的分段而变慢。

B-tree 的优势就在于索引中的 key 存在唯一且固定的位置，而 LSM-tree 的 key 可能存在多个分段中，这有利于 B-tree 实现强事务语义，例如在很多关系型数据库中，事务隔离就是通过锁住一定范围的 key 来实现的。

OLAP 中的存储引擎

OLTP 是面向业务，通常会要求高可用与低延迟，所以就需要单独的数据库来用于数据分析，也就是数据仓库。

数据仓库内，存储了业务数据的只读副本。从 OLTP 数据库中提取数据（定期数据转储或是流处理），转换成可用于数据分析的模型，清理并加载进数据仓库中，这个过程也就是 ETL（extract - transform - load）。

星型模型

我们知道在 OLTP 中有许多数据模型，例如关系型、NoSQL、图，但是在 OLAP 中，数据模型就比较少，现在数据仓库使用的通常是基于关系模型的星型模型（或称为维度模型）。

在进行事务处理时，会产生事实数据，事实表（fact table）的每一行就代表了在特定时间发生的事件，一部分列是属性，另一部分列是对其他表（称为维度表 dimension table）的外键引用，维度表代表了事件的对象、内容、地点、时间、方式和原因（who, what, where, when, how and why）。

而“星型模型（star schema）”这个名字的来源，就是将这些关系变成可视化来看，事实表被维度表包围在中间，这些表的关系就像星星的光芒。

星型模型有一个变体，是雪花模型（snowfalke schema），就是将维度表进一步拆分成更细粒度的子维度表。雪花模型比星型模型更规范，但是也更复杂，所以星型模型是首选。

列式存储

如果事实表中的数据有上亿行，甚至 PB 级的大小，高效率的存储和查询将会是一个巨大的挑战。

并且事实表通常由超过 100 个字段列，但是典型的数仓查询只会访问其中的 4 个或者 5 个字段列，该如何优化查询效率呢？

大部分 OLTP 数据库中，都是行存储模式，即表中的每一行数据相邻存储在一起，NoSQL 也是一样的连续字节序列。如果字段很多、数据量很大，每次查询都需要先把这些数据从磁盘加载到内存中，解析并过滤掉不需要的属性，会浪费很多时间和空间。

所以就诞生了列式存储，不是将每一行内的数据存在一起，而是将每一列的值存在一起。每一列的数据单独存在一个文件中，查询只需要读取列所对应的文件，可以节省大量的工作。

在列式存储中，行之间的关系依赖于每一行的顺序，例如想要查询第 7 行完整的数据，就可以从每个列文件中获取第 7 个值，组合起来形成完整的第 7 行数据。

除了减少每次查询加载的列之外，还可以通过压缩数据来进一步提升效率。列式存储很适合进行数据压缩，也有很多不同的压缩技术，比较有效的是位图编码。

列式存储和压缩，有效提高了数据查询的效率，但是写入也变得困难。如果想在压缩后的列文件内增加一行记录，就得重写所有的列文件，因为插入必须对所有列进行一致的更新。

其实上文已经提到了一个很好的解决方案：LSM-tree。所有的写操作先写入内存表，维护到一个已排序的结构中，准备写入磁盘。此时，内存表中采用行存储或是列存储都可以，达到阈值后，与磁盘中的列文件合并，批量写入新文件即可。

总结

在本章中，从一个最简单的小数据库入手，逐步了解数据库中是如何存储、检索数据的，并了解了针对不同场景优化的存储引擎。

从数据的使用角度来看，分为 OLTP 和 OLAP。OLTP 面向业务和用户，对实时性和可靠性的要求比较高，通常一次查询只会获取少量数据，硬盘查找时间往往会是瓶颈；OLAP 则是用于大数据的分析，查询量和频率会低于 OLTP，但是单次查询所获取的数据量和查询开销会很高，这种情况下，磁盘带宽会成为瓶旧，所以使用列式存储来解决。

在 OLTP 场景下，又会分为两个主要的派系。一种是日志结构派，只允许追加到文件和删除过时的文件，但不会更新已经写入的文件。Bitcask、SSTables、LSM-tree、LevelDB、Cassandra、HBase、Lucene 等都属于这个类别；另一种是就地更新派，将硬盘视为一组可以覆写的固定大小的页面。 B-tree 是这种理念的典范，用在所有主要的关系数据库和许多非关系型数据库中。

因为篇幅有限，还有很多索引结构并没有来得及介绍，例如用于全文检索的索引，甚至将所有的数据都放在内存中，存储引擎内部也有大量细节的设计和内容可以去了解。

当然，本章的目的，是为了让你掌握基本的概念，来帮助你为自己的应用，挑选合适的存储引擎，为性能优化提供思路。

Reference

《Designing Data-Intensive Application》