最近在看《Designing Data-Intensive Applications》，本文主要记录书中第三章存储和检索的内容，加深自己的理解。

最简单的数据库

什么是世界上最简单的数据库？只需要两个 bash 函数：

#!/bin/bashdb_set () {    echo "$1,$2" >> database}db_get () {    grep "^$1," database | sed -e "s/^$1,//" | tail -n 1}

使用例子：

$ db_set 123456 '{"name":"London","attractions":["Big Ben","London Eye"]}' $ db_set 42 '{"name":"San Francisco","attractions":["Golden Gate Bridge"]}'$ db_get 42{"name":"San Francisco","attractions":["Golden Gate Bridge"]}$ db_set 42 '{"name":"San Francisco","attractions":["Exploratorium"]}' $ db_get 42{"name":"San Francisco","attractions":["Exploratorium"]}$ cat database123456,{"name":"London","attractions":["Big Ben","London Eye"]} 42,{"name":"San Francisco","attractions":["Golden Gate Bridge"]} 42,{"name":"San Francisco","attractions":["Exploratorium"]}

这个最简单的数据库底层存储文件是一个文本文件"database"，每行是用逗号分隔的 key 和 value。每次调用 db_set，把 key 和 value 追加到 dababase 文件中。每次调用 db_get，查询的是对应 key 的最后一次写入记录。

这个数据库具备了存储和查询这两种最基本的数据库功能。存储使用了 append 操作，而不是随机写。对于写操作，append 是最快的操作。对于读操作，使用的是线性查找，复杂度 O(n)。随着数据量的增加，查找所花的时间也会线性增长。

为了提升查询性能，可以给数据增加索引。索引可以显著地提升查询性能，但同时也会降低写入性能，因为写入时除了要写入数据本身，还要更新索引，所以需要权衡如何高效地建立索引。

哈希索引

一种直观地建立索引的方法是使用哈希表索引(Hash Indexes)。我们可以在内存中建立一个哈希表，哈希表的 key 是数据的 key，哈希表的 value 是这个 key 对应的数据所在的文件的偏移。举个例子，上文 123456 和 42 这两个 key 的索引如下：

Bitcask存储引擎使用的就是这种方式。Bitcask 存储引擎写入时对文件执行的是追加(append)操作，查询的时候通过建立哈希索引加快查询性能。哈希表保存在内存中。这种存储引擎比较适合 key 的数量有限，并且写操作比较频繁的场景。Bitcask 存储引擎遇到的问题和解决方案如下。

数据文件只有 append 操作，磁盘早晚会有耗尽的一天，怎么解决这个问题？

解决方案是写入数据的时候，把数据文件分成固定的大小，一个数据文件达到大小后，写入新的文件中。然后对已经写入的文件进行压缩(compaction)操作。因为同一个 key 的操作可能有很多次，只有最后一次操作的值才有意义，之前操作的记录没有存在的必要，所以我们可以遍历已经保存过的文件，只保留每个 key 的最后一次操作值，然后把这些最新的值写入新的数据文件中，老的数据文件就可以删除了。压缩完了还需要更新哈希表中 key 对应的文件偏移。

上图中 yawn, scratch, memw, purr 这四个 key 在老的数据文件中出现了多次，经过压缩后，数据减少了很多。

哈希表只保存在内存中，进程重启或者崩溃的时候怎么办？

一种解决方法是进程重启的时候，扫描所有的数据文件，在内存中重建哈希表。这个过程可能很耗时间，所以 Bitcask 使用的优化方式是把哈希表也保存在磁盘中，重启的时候可以加载磁盘的哈希表，快速建立索引。当然这样会降低写入的性能，因为写入数据的时候需要把哈希索引表也写入磁盘中，需要权衡。

哈希索引也有缺点，主要有两个：

1. 如果 key 的数量很多，内存不够大，无法把所有的 key 都保存在内存中。

2. 范围查询效率不高。比如需要查询 kitty00000 到 kitty99999 这个范围的数据，必须先到哈希表中查询每个 key 的文件偏移位置，再去读磁盘。

SSTable 和 LSM-Tree

既然哈希索引范围查询效率不高，有没有优化方法呢？

有一种解决方案是使用 Sorted String Table(SSTable)。上文介绍 Bitcask 存储引擎的数据分成了一个个固定大小的文件，每个文件中 key 的顺序是不固定的。SSTable 的区别在于每个数据文件是根据 key 排过序的。这是如何做到的呢？

首先，数据写入的时候先把数据保存在内存中的平衡树结构中（比如红黑树或者 AVL 树）。这种内存树结构也被叫做 memtable。

当 memtable 的大小超过一定值时（比如几 MB），把当前 memtable 写入磁盘的 SSTable 文件中。因为平衡树本身是有序的，所以把它们写入磁盘的时候也可以保持顺序写入。新的写请求会写入到内存中新的 memtable。

和 Bitcask 存储引擎一样，SSTables 方案里有一个后台压缩进程持续地对已经生成的 SSTable 文件进行合并。合并的方式可以采用归并排序(mergesort)算法，这样合并后的 SSTable 文件也是有序的。排序过程中，如果一个 key 在多个文件中出现，只需要使用最新的文件中的数据。如下图所示：

使用 SSTables 结构，查询数据时，首先到内存 memtable 中查询数据是否存在，如果不存在，再到磁盘的 SSTable 文件中查找。对于 SSTable 文件，内存中也有 key 的索引表，区别在于我们不需要在内存中保存所有的 key。因为 SSTable 中数据是有序的，我们只需要保存少数几个 key 的文件位置偏移就行了。如下图所示：

对于 key 的范围为 handbag 和 handprinted，内存中只需要保存 handbag 的位置偏移，查找 key 时先查找和这个 key 最相近的 key 所对应的位置偏移，然后读取整个偏移范围的内容，对这个范围内的数据再查找我们想要查的 key。以 handiwork 为例，查找这个 key 时，先在内存索引表中找到最近的 key 为 handbag，然后从 SSTable 文件中对应偏移位置开始读取对应长度的数据，然后扫描这段范围的数据，找到 handiwork 的值。一般来说内存索引表中一个 key 对应几 KB 的数据，所以扫描很快。另外保存这段范围的数据时，可以压缩之后再写入磁盘，这样增加磁盘 IO 的效率，不过这也带来了 CPU 压缩和解压缩的开销。比如 handbag 到 handprinted 这个范围的数据可以先压缩后再保存在磁盘中。

上文说到查询数据时先到 memtable 中查找 key 是否存在，不存在再到最新的 SSTable 文件中查找，然后再到旧的 SSTable 文件中查找，一直到最老的 SSTable 文件。如果数据库中根本不存在这个 key 的话，查找过程可能会比较耗时间，一种优化方式是使用布隆过滤器(Bloom filter)来判断 key 是否不存在，key 存在的话再执行上面的查找流程。

SSTable 方案内存中保存了 memtable，如果进程重启或者崩溃怎么处理？一种方案是内存写入 memtable 前，磁盘先写入一个 log 文件，这个 log 文件只有 append 操作。进程重启的时候，使用这个 log 文件重建 memtable。每次内存中的 memtable 写入 SSTable 文件后，这个 log 文件也可以删除了。

整个方案写入数据的时候写入 memtable 和 append-only log 文件中，所以写入性能很高，同时 SSTable 文件是有序的，进行范围查询的时候性能也很高。

方案最早是在The Log-Structured Merge-Tree (LSM-Tree)这篇论文中描述，所以也叫 LSM-Tree。很多数据库都使用了 LSM-Tree，包括 LevelDB、RocksDB、Cassandra、HBase 等。

B-Tree

虽然 LSM-Tree 近来发展很快，B-Tree 仍然是目前使用最广泛的索引结构。

B-Tree 也是一种有序的数据结构，可以高效地进行范围查找。示例如下：

B-Tree 中，每个数据文件的大小是固定，一般为 4K 或者更大，称作块(block)或者页(page)。B-Tree 是分层结构。最上层的页作为根页。根页中按顺序保存了一些 key，同时保存了指向子页的指针，也就是子页数据文件的位置。每个子页保存了一段范围的 key 和对应的位置指针。最底层的称做叶子页(leaf page)，叶子页保存了所有的数据，也有实现方式是在叶子页中只保存数据的指针。每页中保存的指针数量叫做分支系数(branching factor)，一般是几百个。大部分数据库 B-Tree 的层数是 3 到 4 层。对于 4 层的 B-Tree，如果页是 4KB，分支系数是 500 的话，可以储存 256TB 数据。

B-Tree 添加 key 的时候，需要找到包含这个 key 的页，如果这个页已经满了，需要分裂成两个新的页。示例如下：

B-Tree 修改页的时候也面临进程崩溃的问题。为了解决这个问题，写入的时候会先写入一个 append-only log 文件中，也叫做 write-ahead log(WAL)或者redo log。WAL 写入成功后再写入数据页，如果进程崩溃了，WAL 可以用来恢复数据页。

B-Tree 和 LSM-Tree 比较

我们来比较一下 B-Tree 和 LSM-Tree。一般来说，LST-Tree 写入速度更快，而 B-Tree 查询速度更快。LSM-Tree 查询慢一些的原因是因为需要查询几次才能在对应的 SSTable 中找到数据。不过究竟哪个更合适还是需要根据自己业务数据的性能测试结果来定。

B-Tree 写入时需要至少两次 IO 操作，第一次写入 WAL，第二次写入数据页。LSM-Tree 执行写入操作的时候只需要写入一次 WAL，另外一次是内存操作。但是因为后台有个压缩进程会反复对数据进行合并和压缩，一个数据会反复写入多次，这对 SSD 不太友好，因为 SSD 的写入次数是有限的。另外后台压缩进程运行的时候会占据大量磁盘 IO，可能会影响正在执行的写入操作。随着数据文件的增大，压缩占据的磁盘 IO 也会更多，如果同时写入操作也很多的话，有可能压缩操作的速度赶不上写入操作的速度，导致磁盘空间被用光。

LSM-Tree 更容易被压缩，所以数据文件比 B-Tree 要小一些。而且 B-Tree 数据页可能不是完全利用的，比如一个页分裂成两个页的时候，这两个页都只有一半空间被使用了，LSM-Tree 不存在这个问题。

二级索引

我们知道很多数据库都可以建立二级索引，它的实现方式和一级索引一样，也可以使用 B-Tree 或者 LSM-Tree。这里会遇到的问题主要是数据本身存在哪里？

一种方式是数据存在每个索引中，这样会造成数据重复，有几个索引就会有几份数据，更新数据的时候会比较麻烦，需要更新多份数据，可能会导致一致性问题。这种方式也叫聚集索引(clustered index)，MySQL InnoDB 的主键使用了这种方式。

另外一种方式是数据只有一份，所有索引中不保存数据，只保存数据的指针。更新数据的时候如果数据长度没有变大的话，只需要更新一次。如果数据变大的话，可能需要把数据保存在新的地方，所有索引中的数据指针都需要更新。MySQL InnoDB 中的二级索引使用了类似的方式，没有保存数据，保存的是主键中的数据指针。

还有一种折中方案是在索引文件中只保存部分数据列，而不是整行，这也称作覆盖索引(covering index)。

参考

Designing Data-Intensive Applications

The Log-Structured Merge-Tree (LSM-Tree)