Published onDecember 10, 2023

读Designing Data-Intensive Applications Chapter 3

两类存储引擎

基于日志 log-structured storage engines
基于页面，如B树 page-oriented storage engines

最简单的数据库：

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

append to file性能很难被超越，因为是最简单写操作

索引不影响db内容，影响查询性能。尤其是写入时有开销

CREATE INDEX index_name ON table_name (column1, column2, ...);

重要权衡：索引加快查询速度，减慢写入速度。因此db不会索引所有内容，而是要求开发者手动选择索引，考验对app的典型查询模式的了解

假设数据存储仅包括append to file，最简单的索引策略是：内存中哈希映射，键映射到数据文件中字节偏移量

理解：读取操作因为内存中有偏移量所以快，写入操作靠append to file，并改内存偏移量。后台线程去整理都是优化的后话

这正是 Bitcask（Riak 默认存储引擎）所做的。Bitcask 提供高性能读写，前提是所有键可装进 RAM。如果数据文件部分已在文件系统缓存中，读取不需磁盘 I/O

Riak 是分布式NoSQL DB

基于 Amazon Dynamo 系统的原理设计，支持多种数据模型，包括键值存储和文档存储

允许数据在多个节点间自动复制和分区，确保数据的持久性和可用性

支持多种查询方式，包括 MapReduce、搜索查询和二级索引

适用于需高吞吐量和低延迟的大规模分布式应用

Bitcask 适合值需经常更新的情况。如键是视频 URL，值是播放次数。这有很多写操作，但不是太多不同的键——有每个键大量写操作，但可以将所有键放进内存

如何避免存储空间耗尽？通过关闭达到一定大小的段文件，在新的段文件中进行后续写入，这将日志分割成一定大小的段。可对这些段压缩。意味着丢弃重复的键，只保留每个键的最新更新

段在写入后不会被修改，合并的段被写入新文件。合并和压缩段在后台线程中完成，仍然可继续使用旧的段文件处理读请求，将写请求写入最新段文件。合并过程完成后将读请求切换到新合并的段，旧段文件可删除

每个段有自己的内存哈希表。为找到一个键的值，检查最新段的哈希映射；如键不存在检查第二新的段，依此类推。合并过程保持段数量较少，因此不需检查很多哈希映射表

append to file优点：

追加和段合并是顺序写操作，比随机写入快得多，尤其在HDD上
段文件是追加只读或不可变的，并发和崩溃恢复会简单得多。不必担心在值被覆盖时发生崩溃的情况，留下包含部分旧值和部分新值拼接在一起的文件
合并旧段避免了数据文件随时间碎片化的问题 (这应该是和之后的B树对比)

局限性：

哈希表必须能放进内存。在磁盘上维护哈希映射很难表现良好
- 需要大量随机访问I/O
- 扩容成本高昂
- 哈希冲突需要复杂逻辑处理(随机访问I/O的问题)
  - 内存中处理哈希冲突通常通过开放寻址或链表等简单方法实现。但在磁盘上不够有效因为要求频繁的随机访问
  - 哈希表的扩容通常在填充因子达到一定阈值时进行，这个过程在内存中比较快速。磁盘上这个过程涉及大量数据的移动和重新哈希，成本要远高于内存
范围查询效率不高。如不能轻易地扫描所有在00000和99999间的键——必须在哈希映射中单独查找每个键

实现中重要问题：

文件格式: CSV不是日志的最佳格式。使用一种二进制格式会更快更简单，该格式首先编码字符串的长度（以字节为单位），然后是原始字符串（无需转义）
- 读取和写入速度更快(主要还是合并过程中开销更小了？)，因为减少了解析文本和处理转义字符
- 更紧凑，没有额外的分隔符和文本编码开销
删除记录: 删除一个键及其关联值，需在数据文件中追加特殊的删除记录（有时称墓碑记录）。日志段合并时墓碑记录会告诉合并过程丢弃被删除键的任何先前值
崩溃恢复: 数据库重新启动内存中的哈希映射将丢失。可从头到尾阅读每个段文件并恢复哈希映射。如果段文件很大可能需要很长时间，使服务器重启变得痛苦
- Bitcask将每个段的哈希映射快照存储在磁盘上来加速恢复
部分写入的记录: 数据库可能随时崩溃，包括在将记录追加到日志的过程中途。Bitcask文件包括校验和，允许检测并忽略日志中这样损坏的部分
并发控制: 写入严格按顺序追加到日志中，常见的实现选择是只有一个写入线程。数据文件段是append only，且在其他方面是不可变的，所以它们可被多个线程并发读取

对段文件格式做简单改变：要求键值对序列按键排序。将这种格式称为排序字符串表，称为SSTable。这种格式不能立即将新的键值对追加到段中，因为写入按任何顺序发生

SSTables与带有哈希索引的日志段相比几个优势：

合并段简单高效，即使文件大于可用内存。类似于归并排序算法
为在文件中找到特定键，不再需要在内存中保留所有键的索引。假设正寻找键handiwork，但不知道该键在段文件中的确切偏移量。然而知道键handbag和handsome的偏移量，知道handiwork必须出现在两者间。可跳转到handbag的偏移量，并从那里扫描
仍需内存中的索引指示某些键的偏移量，但它可以是稀疏的：隔几千字节的段文件就有一个键就足够，因为几千字节可非常快速地扫描

由于读取请求无论如何都需要扫描请求范围内的几个键值对，因此可以将这些记录分组成一个块，并在写入磁盘之前对其进行压缩。稀疏内存索引的每个条目都指向压缩块的起始处。除了节省磁盘空间外，压缩还减少了I/O带宽的使用

要构建和维护SSTable重要的问题是，如何让数据按键排序？写入操作可按任何顺序发生

可在磁盘上维护排序结构（B树），但在内存中维护它要容易得多。有很多树数据结构可用，如红黑树或AVL树。使用它们可按任何顺序插入键，并按排序顺序读回它们

现在可使我们的存储引擎如下工作：

写入请求到来时，将其添加到一个内存中的平衡树数据结构中（如红黑树）。内存中的树有时称memtable
memtable大小超过某个阈值——通常是几兆字节——将其作为SSTable文件写入磁盘。这可高效完成，因为树已经按键排序了键值对。新的SSTable文件成为数据库的最新段。将SSTable写入磁盘时，写入可以继续到新的memtable实例
为处理读请求，首先尝试在memtable中找到键，然后在最新磁盘段中找到键，然后在次新的段中找到键，依此类推
不时地在后台运行合并和压缩过程，以合并段文件并丢弃被覆盖或删除的值

这种方案只有一个问题：如果数据库崩溃，最近的写入（在memtable中但没写入磁盘）会丢失。为避免问题，在磁盘上保持单独的日志，每个写入都立即追加到其中。日志不是排序的但不重要，因为目的是在崩溃后恢复memtable。每次将memtable写入SSTable时，相应的日志可被丢弃

这算法是用在LevelDB 和 RocksDB 中的，这两是被设计来嵌入到其他应用程序中的键值存储引擎库。如LevelDB 可在 Riak 中用作 Bitcask 的替代品。类似的存储引擎也被用在 Cassandra 和 HBase 中，这两者都受到了 Google 的 Bigtable 论文（引入了 SSTable 和 memtable 这些术语）的启发

最初这种索引结构由 Patrick O’Neil 等人以“日志结构合并树”（即 LSM-Tree）的名字描述，基于早期关于日志结构文件系统的工作。基于这种合并和压缩排序文件原则的存储引擎通常被称为 LSM 存储引擎

Lucene 是 Elasticsearch 和 Solr 使用的全文搜索索引引擎，采用类似方法来存储其术语字典。全文索引比键值索引复杂得多，但基于类似的想法：给定搜索查询中的一个词，找出所有提到该词的文档（网页、产品描述等）。通过一个键值结构实现，其中键是一个词（一个术语），值是包含该词的所有文档的 ID 列表。 Lucene 中这种从术语到帖子列表的映射保留在类似 SSTable 的排序文件中，这些文件在后台按需合并

许多细节被投入到实际操作中以提高存储引擎性能。如 LSM-tree 算法在查找数据库中不存在的键时可能会变慢：必须检查 memtable，然后是一直到最旧的段才能确保键不存在。为优化这种访问，存储引擎通常使用额外的布隆过滤器（布隆过滤器是一种内存高效的数据结构，用于近似集合的内容。它可知数据库中是否没有某个键，从而节省许多不存在键的不必要磁盘读取）

还有不同的策略来确定 SSTables 的压缩和合并的顺序和时机。最常见的选项是基于大小的和层级的压缩。LevelDB 和 RocksDB 使用层级压缩，HBase 使用基于大小的压缩，Cassandra 支持两者。基于大小的压缩中，较新和较小的 SSTables 合并到较旧和较大的 SSTables 中。层级压缩中，键范围被划分为更小的 SSTables，旧数据被移到单独的“层级”中，这使压缩可更加逐步进行，使用更少磁盘空间

尽管有许多差别，LSM-trees 的基本思想"保持一系列在后台合并的 SSTables"简单而有效。即使数据集比可用内存大得多，它仍然工作良好。由于数据按排序顺序存储，可有效执行范围查询，且因为磁盘写入是顺序的，LSM-tree 可支持非常高的写入吞吐量

最广泛使用的索引结构：B树

B-树于 1970 年引入，不到 10 年后就“无处不在”。它们仍然是几乎所有关系数据库中的标准索引实现，且许多非关系数据库也使用它们

像 SSTables，B树按键排序来保存键值对，这允许有效的键值查找和范围查询。但相似性就此结束：B树有非常不同的设计理念

之前看到的日志结构化索引将数据库分解为可变大小的段，通常大小为几兆字节或更多，并始终顺序地写入一个段。B树将数据库分解为固定大小的块或页面，传统上大小为 4 KB（有时更大），并一次读取或写入一个页面。这种设计更符合底层硬件，因为磁盘是以固定大小的块组织的

每个页面可使用地址或位置来标识，这允许一个页面引用另一个页面——类似于内存中的指针，但在磁盘上而不是在内存中。可使用这些页面引用来构造一个页面树

一个页面被指定为 B树的根；在索引中查找一个键时，从这里开始。页面包含几个键和对子页面的引用。每个子页面负责一连串的键，引用之间的键指示这些范围的边界在哪里

寻找键 251，需要跟随 200 和 300 边界之间的页面引用。到一个类似的页面，进一步将 200–300 范围细分为子范围。最终得到了一个包含单独键（叶子页面）的页面，其中包含每个键的内联值或包含可以找到这些值的页面的引用

一个 B树页面中的子页面引用数量称为分支因子。实际上分支因子取决于存储页面引用和范围边界所需的空间量，但通常是几百

在 B树中更新现有键的值，需要搜索包含该键的叶页面，更改该页面中的值，将页面写回磁盘（对该页面的任何引用都保持有效）。如果添加一个新键，需要找到包含新键范围的页面，将其添加到该页面中。如果页面中没有足够的空闲空间容纳新键，会被分成两个半满的页面，并更新父页面以反映新的键范围划分

这种算法确保树的平衡：拥有 n 个键的 B-树始终具有 O(log n) 深度。大多数数据库可适应三到四层深的 B树，所以不需要跟随许多页面引用就可找到正在寻找的页面。（四层的 4 KB 页面树，分支因子 500，可存储 250 TB）

B树的基本底层写操作是用新数据覆盖磁盘上的页面。假设覆盖不改变页面位置；即当页面被覆盖时，对该页面的所有引用都保持不变。这与 LSM-trees 这样的日志结构化索引形成鲜明对比，后者只添加到文件中（并最终删除过时的文件）但不就地修改文件

可将磁盘上的页面覆盖视为实际的硬件操作。在磁盘硬盘上意味着将磁头移动到正确位置，等待旋转盘片上正确的位置出现，然后用新数据覆盖相应扇区。固态硬盘上发生的情况更复杂，因为固态硬盘必须一次擦除和重写存储芯片上相当大的块

某些操作需要覆盖几个不同页面。如因插入导致页面过满而分割页面，需写入被分割的两个页面，且还需要覆盖其父页面以更新对两个子页面的引用。这是危险操作，如果数据库在只有部分页面被写入后崩溃，最终会得到一个损坏的索引（可能会有一个没有任何父节点的页面）

使数据库能抵抗崩溃，B树实现通常在磁盘上包含额外数据结构：写前日志（WAL，也称重做日志）。这是只能添加的文件，每个 B树修改都必须写入该文件，然后才能应用到树本身的页面。当数据库在崩溃后重新启动时，此日志用于将 B树恢复到一致状态

更新页面的另一个复杂性是，如果多线程同时访问 B树，则需要谨慎的并发控制——否则线程可能会看到树的不一致状态。这通常通过使用闩锁（轻量级锁）来保护树的数据结构来完成。这个角度来看日志结构方法更简单，因为它们在后台进行所有合并，不干扰传入的查询，且不时地原子性地将旧段换成新段

B树多年来许多优化：

一些数据库（如 LMDB）使用写时复制方案代替覆盖页面和维护用于崩溃恢复的 WAL 。修改后的页面被写入不同位置，并创建树中父页面的新版本，指向新的位置。这种方法也对并发控制有用
通过不存储整个键，而是缩写键，可节省页面中的空间。特别在树的内部页面上，键只需要提供足够的信息来充当键范围之间的边界。将更多键打包进页面可让树有更高的分支因子，因此层级更少
一般来说页面可放置在磁盘的任何地方；没有要求具有临近键范围的页面在磁盘上也是临近的。如果查询需要按排序顺序扫描大部分键范围，那么逐页布局可能效率低下，因为可能需要为每个读取的页面进行一次磁盘寻道。因此许多 B树实现尝试布局树，使叶页面在磁盘上顺序出现。然而随着树的增长，维持这种顺序变得困难。相比之下，由于 LSM树在合并过程中一次性重写大量存储段，它们更容易在磁盘上保持顺序键彼此靠近
树中添加了额外指针。如每个叶页面可能有指向左右相邻页面的引用，允许按顺序扫描键而不必回到父页面
B树变体如分形树，借鉴了一些日志结构化的思想来减少磁盘寻道

尽管 B树通常比 LSM树更成熟，但由于性能特点，LSM树也很有趣。LSM树通常在写入方面更快，B树被认为在读取方面更快。LSM树上的读取通常较慢，因为它们需在不同阶段的压缩中检查几个不同的数据结构和 SSTables

基准测试往往是不确定的，对工作负载的细节非常敏感。需使用特定工作负载测试系统进行有效比较

B树索引必须至少将每条数据写入两次：一次写入预写日志，一次写入树页面本身（如果页面被分割，则可能再次写入）。还有缺点是即使页面中只有几个字节发生变化，也必须一次写入整个页面。一些存储引擎甚至会重写同一页面两次，避免在停电时出现部分更新的页面

由于重复压缩和合并 SSTables，日志结构化索引也会多次重写数据。这种效应——数据库中的一次写入导致其生命周期内对磁盘的多次写入——被称为写放大。这对 SSD 特别重要，因为 SSD 只能在磁盘上重写块有限次数，否则会磁盘磨损

写入密集型应用中性能瓶颈可能是数据库写入磁盘的速率。这种情况下写放大导致性能成本：存储引擎写入磁盘次数越多，可用磁盘带宽内能处理的写入次数越少

LSM树通常比 B树维持更高的写入吞吐量，部分原因是它们有时有较低的写放大（取决于存储引擎配置和工作负载），部分原因是它们顺序写入紧凑的 SSTable 文件，而不是覆盖树中多个页面。这点在HDD上尤其重要，HDD上顺序写入比随机写入快得多

LSM树可更好地压缩，通常在磁盘上产生比 B树更小的文件。由于碎片化，B树存储引擎在磁盘上留下一些未使用空间：当页面被分割或行不能适应现有页面时，页面中一些空间仍未使用。由于 LSM树不是面向页面的，且定期重写 SSTables 以去除碎片化，因此存储开销较低，尤其是在使用层级

许多 SSD 上固件在内部使用日志结构化算法将随机写入转换为在底层存储芯片上的顺序写入，因此存储引擎的写入模式影响不那么明显。然而较低的写放大和减少的碎片化仍对 SSD 有利：更紧凑地表示数据可在可用的 I/O 带宽内处理更多读写请求

日志结构化存储的缺点是，压缩过程有时会干扰正在进行的读写性能。尽管存储引擎尝试逐步执行压缩且不影响并发访问，但磁盘资源有限，因此请求在磁盘完成昂贵的压缩操作时可能需要等待。对吞吐量和平均响应时间的影响通常很小，但在更高的百分位数时，对日志结构化存储引擎的查询响应时间有时可能相当高，B树可能更加可预测

在高写入吞吐量时，压缩另一个问题：磁盘有限的写带宽需要在初始写入（日志记录和刷新 memtable 到磁盘）和后台运行的压缩线程间共享。写入一空数据库时，可将全部磁盘带宽用于初始写入，但数据库越大，压缩所需磁盘带宽就越多

如果写入吞吐量高且压缩配置不当，可能发生压缩无法跟上写入速率的情况。这种情况下磁盘上未合并的段数量不断增长，直到磁盘空间耗尽，读取也会变慢，因为需要检查更多段文件。通常基于 SSTable 的存储引擎即使在压缩无法跟上时也不会限制写入速率，因此需明确监控这种情况

B树的优势是索引中的每个键只存在于一个地方，而日志结构化存储引擎可能在不同段中有同一个键的多个副本。这点使 B树在想要提供强大事务语义的数据库中具有吸引力：许多关系数据库中事务隔离是通过对键范围加锁实现的，B树索引中，这些锁可直接附加到树上

B树在数据库架构中非常根深蒂固，且为许多工作负载提供一致良好性能，因此它们不太可能很快消失。新的数据存储中日志结构化索引越来越受欢迎

键值索引类似于关系模型中的主键索引。关系表中主键唯一标识一个行，或者在文档数据库中的一个文档，或者在图数据库中的一个顶点。数据库中的其他记录可通过其主键（或 ID）引用该行/文档/顶点，索引用于解析此类引用

辅助索引(secondary index)也很常见。关系数据库中可使用 CREATE INDEX 命令在同一表上创建多个辅助索引，这些索引通常对有效执行连接至关重要

可从键值索引构建辅助索引。区别在于辅助索引中，索引的值不一定唯一，可能有许多行（文档、顶点）在同一个索引项下。可通过两种方式解决：要么使索引中的每个值都是匹配行标识符的列表（类似于全文索引中的帖子列表），要么通过附加行标识符使每个条目唯一。无论哪种方式，B树和日志结构化索引都可用作辅助索引

see all posts