数据的存储与检索

最简单的数据库

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

使用方法

source db.sh
db_set 123456 '{"name":"London","attractions":["Big Ben","London Eye"]}'
db_get 123456

该数据库，写入性能很好，但是读取性能非常糟糕，查找开销 O(n) 。

为了高效的查找数据可特有的键，我需要一个数据结构：索引（index）。即额外保存一些元数据作为路标，帮助找到我们想要的数据。索引是主数据的附加数据，在解决提升查询性能这一问题的同时，引入了新的问题，即写入数据时，要额外维护索引，也就产生了额外开销。这是一个权衡问题。

当然，写入的性能很难超过简单的追加文件，因为只是最简单的写入操作。任何索引都会减慢写入速度，因为每次写入数据都需更新索引。

Hash 索引

即在内存中保存一个哈希映射，hash map的key为上边数据库的键值，值为实际内容的字节偏移量。

当数据库中存储新的值时，除了将新的键值对追加到文件外，还需要更新内存中的hash映射（也适用于插入、更新现有键值对）；当查找一个值时，可以使用哈希映射来查找数据文件中的偏移量，寻找（seek）该位置并读取该值。

现实中，Bitcask（默认 Riak 引擎） 就是这么做的。Ritcask提供高性能读写的必要条件是所有的 key 都放置在可用RAM中，因为哈希映射完全在内存中。 value 可以使用比内存大的空间，因为它们可以通过磁盘seek加载。如果部分数据已经存在在文件系统缓存中，读取则不需要磁盘 I/O 了。

像 Bitcask 这样的存储引擎适合每个键经常更新的情况。

SSTables和LSM树

Sorted String Table（SSTable）是一种用于存储键值对的数据结构，常用于分布式存储系统中。它将键值对按照键的大小有序存储在磁盘文件中，使得查找和迭代操作变得高效。SSTable通常被设计成不可变的，即一旦存储就不能被修改，这样可以避免数据不一致性问题。为了支持数据的更新和删除操作，SSTable通常会与内存中的数据结构（如哈希表）结合使用，形成LSM-Tree（Log-Structured Merge-Tree）等数据结构。SSTable在大规模数据存储和查询场景中具有很高的性能和可靠性，被广泛应用于各种分布式存储系统中，如Hadoop、Cassandra、LevelDB等。

Sorted String Table 对比 Hash 的优点

1、合并段简单高效。

2、查找特定的键，不需要内存中所以的索引。

3、因为读请求无论如何都有扫描一部分键值对，因此在写入磁盘前，可以将记录分组、压缩，并在内存中维护一个压缩块开始的key和偏移量的索引。既可以节约磁盘空间，也可以减少IO带宽的使用。

构建和维护 SSTables

b树，在磁盘上维护有序结构。

红黑树、AVL树，在内存中维护有序结构。

1. 写入时，将其添加到内存中的平衡数据结构（例如，红黑树）。这种内存中的树有时叫 内存表（memtable）。
2. 当内存表大于某个阈值（通常几兆）时，将其作为 SSTable 文件写入磁盘。树已经维护了排序的键值对，所以写入可以高效完成。新的 SSTable 文件成为数据库最新的部分。当 SSTable 正在被写入磁盘时，第一步的写入操作可以继续到一个新的内存表实例中。
3. 为了提供读取请求，首先尝试在内存表中找到关键字，然后在最近的磁盘段中，然后在下一个较旧的段中找关键字。
4. 不时，会在后台运行合并和压缩进程以组合文件段、丢弃覆盖和删除值。

此方案问题：如果数据库崩溃，最近写入的（在内存表中，还未写入磁盘）数据将丢失。

解决问题：在磁盘上保存一个单独的日志，每个写入操作都被立刻追加到该文件中。此操作日志的唯一目的是为了崩溃后恢复内存表。所以每当内存表中的数据被当作SSTable文件写入磁盘时，相应的日志文件都会被丢弃。

用 SSTables 制作 LSM Tree

该算法本质就是 LevelDB （google 开发） 和 RocksDB（facebook 开发）所使用的算法，它们都是被设计成可以嵌入到其他应用程序中的键值存储引擎库。另外LevelDB可以作为Bitcask的替代选项，在Riak中使用。类似的存储引擎也被用于 Cassandra 和 HBase 中。

性能优化

1. 查找数据库中不存在的键，LSM-tree 算法很慢：必须先检查内存表，然后检查磁盘文件端一直到最久的数据（可能需要读取每一个），才能确定键不存在。通常使用存储引擎通常使用额外的Bloom过滤器解决这种问题。

2. 选择SSTables压缩和合并的顺序和时机会有不同的策略。最常见的策略有 大小分层（Size-tiered Compaction）和 平坦压缩 （Leveled compaction）[见参考连接]。LevelDB 和 RocksDB 使用了 平坦压缩 ，HBase 使用了 大小分层， Cassandra 同时都支持。

   1. Size-Tiered Compaction 策略：memtable 逐步刷入到磁盘 sst，刚开始 sst 都是小文件，随着小文件越来越多，当数据量达到一定阈值时，STCS 策略会将这些小文件 compaction 成一个中等大小的新文件。同样的道理，当中等文件数量达到一定阈值，这些文件将被 compaction 成大文件，这种方式不断递归，会持续生成越来越大的文件。数据合并不是即时的（达到阈值合并），相同数据的文件，可能存在于不同大小等级的多个文件中，故存在 空间放大（实际数据量只有1G，可能存储过程中占用远超1G）。对于覆写频繁的场景并不适用。

   2. Leveled compaction 策略：

      1. sst 的大小可控，默认每个 sst 的大小一致（Size-Tiered Compaction 策略最终会产生超大文件）
      2. LCS 在合并时，会保证除 Level 0（L0）之外的其他 Level 有序且无覆盖。
      3. 除 L0 外，每层文件的总大小呈指数增长，假如 L1 最多 10 个，则 L2 为 100 个，L3 为 1000 个…

      关键范围被拆分成更小的SSTables，而较旧的数据被移动到单独的“水平”，这使得压缩能够更加递增地进行，并且使用更少的磁盘空间。

      该策略会造成 写放大 。

LSM树的基本思想 —— 保存一系列在后台合并的SSTables —— 简单而有效。即使数据集比可用内存大得多，它仍能继续正常工作。由于数据按排序顺序存 储，因此可以高效地执行范围查询（扫描所有高于某些最小值和最高值的所有键），并且因为磁盘写入是连续的，所以LSM树可以支持非常高的写入吞吐量。

B树

像 SSTables 一样，B 树保持按键排序的键值对，这允许高效的键值查找和范围查询。但这也就是仅有的相似之处了：B 树有着非常不同的设计理念。

不同之处：

日志结构索引：将数据库分解为可变大小的 段（segments），通常几兆或更大，且都是顺序写入段。

B-tree ：将数据库分解为固定大小的 **块（block）**或 页（page）, 传统上大小为 4KB（有时会更大），且一次只能读取或写入一页。这样的设计更接近硬件底层（unix 上可以通过 dumpe2fs 或者 xfs_info 查看的块大小 ）。每个页面使用地址或位置来标记，允许一个页面引用另一个页面——类似指针（硬盘中非内存中）。

有一个 page 是 B-tree 的根（查找 key 时，从这里开始），这个 page 包含几个 key 和一些 child page 的引用。child page 负责一段连续的 key 范围 ，引用之间的 key 表明了范围的边界在那里。

叶子页面（ldaf page），要么直接包含了每个 key 的value，要么包含了 key 对应 value 存放位置的引用。

分支因子（branching factor），B-tree 中一个页面对子页面引用的数量。

更新操作某个key的值：先搜索该 key 所在的叶子页面，再更改该页中的值，并将该页面写回硬盘中。

新增一个 key ：先找到其范围包含新 key 的页面，并将其添加到该页面中，如果该页没有足够的空间容纳新 key，则将其分成两个 半页，并更新父页面以反映新的键范围分区。

删除一个 key：（同时保持树平衡）就会牵扯很多其他东西。

让 B-Trees 更可靠

B-trees 底层写操作：用新数据覆写硬盘上的页面，并假定对该页面的引用保持完整。

日志结构的索引（LSM-trees）：只追加文件（最终删除过时的文件），从不修改文件中已有的内容。

覆写硬盘页面对应的实际硬件层面的操作：磁性硬盘驱动器，将磁头移动到正确的半径位置，等待旋转盘转到正确的起始角度，使用新数据覆写适当的扇区。固态硬盘上，更复杂，ssd必须一次擦除和重写相当大的存储芯片块。

情况一 ： 一些操作需要覆写几个不同的页面，如：因为插入导致页面过满而拆分页面，则需要写入新拆分的两个页面，并覆写其父页面以更新对两个子页面的引用。这是一个危险的操作，因为如果数据库在系列操作进行到一半时崩溃，那么最终将导致一个损坏的索引（例如，可能有一个孤儿页面没有被任何页面引用） 。

为了应对这种情况，B 树实现通常会带有一个额外的硬盘数据结构：预写式日志（WAL，即 write-ahead log，也称为 重做日志，即 redo log）。这是一个仅追加的文件，每个 B 树的修改在其能被应用到树本身的页面之前都必须先写入到该文件。当数据库在崩溃后恢复时，这个日志将被用来使 B 树恢复到一致的状态。

情况二：如果多个线程要同时访问 B 树，则需要仔细的并发控制 —— 否则线程可能会看到树处于不一致的状态。这通常是通过使用 锁存器（latches，轻量级锁）保护树的数据结构来完成。

B-Trees 的优化

• 使用写时复制方案（非 WAL ） 来处理崩溃：经过修改的页面被写入到不同的位置，并且还在树中创建了父页面的新版本，以指向新的位置。同时，此方法对并发控制也很有用。
• 我们可以通过不存储整个键，而是缩短其大小，来节省页面空间。特别是在树内部的页面上，键只需要提供足够的信息来充当键范围之间的边界。在页面中包含更多的键允许树具有更高的分支因子，因此也就允许更少的层级。
• 通常，页面可以放置在硬盘上的任何位置；没有什么要求相邻键范围的页面也放在硬盘上相邻的区域。如果某个查询需要按照排序顺序扫描大部分的键范围，那么这种按页面存储的布局可能会效率低下，因为每个页面的读取都需要执行一次硬盘查找。因此，许多 B 树的实现在布局树时会尽量使叶子页面按顺序出现在硬盘上。但是，随着树的增长，要维持这个顺序是很困难的。相比之下，由于 LSM 树在合并过程中一次性重写一大段存储，所以它们更容易使顺序键在硬盘上连续存储。
• 额外的指针被添加到树中。例如，每个叶子页面可以引用其左边和右边的兄弟页面，使得不用跳回父页面就能按顺序对键进行扫描。
• B 树的变体如 分形树（fractal trees） 借用了一些日志结构的思想来减少硬盘查找（而且它们与分形无关）。

比较 B-Trees 和 LSM-Trees

LSM-Trees 的优点

B 树索引每块数据必须至少写入两次：一次写入预写入日志（WAL），一次写入树本身（如果分页还需再写入一次）。即使几个字节的变化，也需要接收写入整个页面的开销。有些存储引擎甚至覆写同一个页面两次，以免电源故障情况下页面未完整更新。

由于反复压缩与合并SSTable，日志结构索引会多次重写数据。这种影响——在数据库的生命周期中每笔数据导致对硬盘的多次写入 —— 被称为 写入放大（write amplification）。使用固态硬盘的机器需要额外关注这点，固态硬盘的闪存寿命在覆写有限次数后就会耗尽。

写放大会导致直接的性能代价：存储引擎写入硬盘的次数越多，可用硬盘带宽内它能处理的每秒写入次数就越少。

LSM 树通常能够比 B 树支持更高的写入吞吐量：

​ 原因一：它们有时具有较低的写放大（尽管这取决于存储引擎的配置和工作负载）

​ 原因二：它们顺序地写入紧凑的 SSTable 文件而不是必须覆写树中的几个页面。这种差异在机械硬盘上尤其重要，其顺序写入比随机写入要快得多。

LSM 树可以被压缩得更好，因此通常能比 B 树在硬盘上产生更小的文件。B 树存储引擎会由于碎片化（fragmentation）而留下一些未使用的硬盘空间：当页面被拆分或某行不能放入现有页面时，页面中的某些空间仍未被使用。由于 LSM 树不是面向页面的，并且会通过定期重写 SSTables 以去除碎片，所以它们具有较低的存储开销，特别是当使用分层压缩（leveled compaction）时。

LSM-Trees 的缺点

日志结构存储的缺点压缩过程有时会干扰正在进行的读写操作。尽管存储引擎尝试增量地执行压缩以尽量不影响并发访问，但是硬盘资源有限，所以很容易发生某个请求需要等待硬盘先完成昂贵的压缩操作。对吞吐量和平均响应时间的影响通常很小，但是日志结构化存储引擎在更高百分位的响应时间有时会相当长，而 B 树的行为则相对更具有可预测性。

压缩的另一个问题出现在高写入吞吐量时：硬盘的有限写入带宽 需要在 初始写入（记录和刷新内存表到硬盘）和在后台运行的压缩线程之间共享。当向一个空数据库写入时，整个磁盘带宽可以用于初始写入，但是随着数据库变得越来越大，压缩需要更多的磁盘带宽。

如果在高写入吞吐量的情况下，如果压缩没有经过仔细配置，可能会发生压缩无法跟上写入速率。这时，磁盘上的未合并段（nmerged segments）会不断增加，直到磁盘空间用尽，读取速度也会变慢，因为要检查更多的段文件。通常SSTable存储引擎不会限制传入写入速率，即使压缩跟不上，所以你需要建立监控来检测这种情况。

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

其他索引

主键（primary key） 索引。主键唯一标识关系表中的一行，或文档数据库中的一个文档或图形数据库中的一个顶点。数据库中的其他记录可以通过其主键（或 ID）引用该行 / 文档 / 顶点，索引就被用于解析这样的引用。

次级索引可以很容易地从键值索引构建。次级索引主要的不同是键不是唯一的，即可能有许多行（文档，顶点）具有相同的键。这可以通过两种方式来解决：将匹配行标识符的列表作为索引里的值（就像全文索引中的记录列表），或者通过向每个键添加行标识符来使键唯一。

将值存储到索引中

索引中的值可以存储实际的行（文档、顶点），也可以存储一个引用（行实际存储的位置的引用）。通常是 堆文件（heap file） ，它存储的数据是无序的。它避免了存在多个次级索引时对数据的复制：索引只引用堆文件上的一个位置，实际数据保存在一个地方。

在不更改键值时更新值，堆文件是非常高效的：新值占用字节数据不大于旧值时，覆盖该记录即可；新值占用空间大于旧值时，就需要将新值移动到堆中足够空间的新位置，这是要么更新所有的索引，指向新的堆位置，要么在旧的堆位置留一个转发指针。

从索引到堆文件的额外跳跃对读取来说性能损失较大，希望索引的行直接存储在索引中。这被称为 聚簇索引（Clustered Index） ，如 Mysql 的 InnoDB 存储引擎中表主键总是一个 聚簇索引，次级索引则引用主键。

聚簇索引（在索引中存储所有的行数据） 和 非聚簇索引（仅在索引中存储对数据的引用） 之间的折衷称为 覆盖索引（covering index），其在索引内部存储了一部分列。这就允许了通过单独使用索引来处理一些查询（这种情况下，可以说索引 覆盖（cover） 了查询）。

多列索引

连接索引（concatenated index） ，它通过将一列的值追加到另一列后面，简单地将多个字段组合成一个键（索引定义中指定了字段的连接顺序）。

多维索引（multi-dimensional index） 是一种查询多个列的更一般的方法，这对于地理空间数据尤为重要。

一种选择是使用 空间填充曲线（space-filling curve） 将二维位置转换为单个数字，然后使用常规 B 树索引。更普遍的是，使用特殊化的空间索引，例如 R 树。例如，PostGIS 使用 PostgreSQL 的通用 GiST 工具将地理空间索引实现为 R 树。

多维索引不仅可以用于地理位置。例如，在电子商务网站上可以使用建立在（红，绿，蓝）维度上的三维索引来搜索特定颜色范围内的产品，也可以在天气观测数据库中建立（日期，温度）的二维索引，以便有效地搜索 2013 年内的温度在 25 至 30°C 之间的所有观测资料。

全文索引和模糊索引

全文搜索引擎通常允许搜索目标从一个单词扩展为包括该单词的同义词，忽略单词的语法变体，搜索在相同文档中的近义词，并且支持各种其他取决于文本的语言分析功能。为了处理文档或查询中的拼写错误，Lucene 能够在一定的编辑距离内搜索文本（编辑距离 1 意味着单词内发生了 1 个字母的添加、删除或替换）。

Lucene 为其词典使用了一个类似于 SSTable 的结构。这个结构需要一个小的内存索引，告诉查询需要在排序文件中哪个偏移量查找键。在 LevelDB 中，这个内存中的索引是一些键的稀疏集合，但在 Lucene 中，内存中的索引是键中字符的有限状态自动机，类似于 trie 。这个自动机可以转换成 Levenshtein 自动机，它支持在给定的编辑距离内有效地搜索单词。

在内存中存储一切

某些内存中的键值存储（如 Memcached）仅用于缓存，在重新启动计算机时丢失的数据是可以接受的。但其他内存数据库的目标是持久性，可以通过特殊的硬件（例如电池供电的 RAM）来实现，也可以将更改日志写入硬盘，还可以将定时快照写入硬盘或者将内存中的状态复制到其他机器上。

内存数据库重新启动时，需要从硬盘或通过网络从副本重新加载其状态（除非使用特殊的硬件）。尽管写入硬盘，它仍然是一个内存数据库，因为硬盘仅出于持久性目的进行日志追加，读取请求完全由内存来处理。写入硬盘同时还有运维上的好处：硬盘上的文件可以很容易地由外部程序进行备份、检查和分析。

反直觉的是，内存数据库的性能优势并不是因为它们不需要从硬盘读取的事实。只要有足够的内存即使是基于硬盘的存储引擎也可能永远不需要从硬盘读取，因为操作系统在内存中缓存了最近使用的硬盘块。相反，它们更快的原因在于省去了将内存数据结构编码为硬盘数据结构的开销。

内存数据库的另一个有趣的地方是提供了难以用基于硬盘的索引实现的数据模型。例如，Redis 为各种数据结构（如优先级队列和集合）提供了类似数据库的接口。因为它将所有数据保存在内存中，所以它的实现相对简单。

内存数据库体系结构可以扩展到支持比可用内存更大的数据集，而不必重新采用以硬盘为中心的体系结构。所谓的 反缓存（anti-caching） 方法通过在内存不足的情况下将最近最少使用的数据从内存转移到硬盘，并在将来再次访问时将其重新加载到内存中。这与操作系统对虚拟内存和交换文件的操作类似，但数据库可以比操作系统更有效地管理内存，因为它可以按单个记录的粒度工作，而不是整个内存页面。尽管如此，这种方法仍然需要索引能完全放入内存中（就像本章开头的 Bitcask 例子）。

参考链接

Compaction 策略 - Size-Tiered

Compaction 策略 – Leveled