DDIA Chapter 3：数据存储与检索

数据库核心：数据结构

最简单的数据库由两个Bash函数实现，底层采用一个纯文本文件实现，每一行包含一个key-value对，逗号隔开。每次调用db_set追加新内容到文件末尾，旧版本不会被覆盖，需要查找文件中最后一次出现的键来查找最新值。这种思想类似于日志，很多数据库内部使用日志，其是一个仅支持追加式更新的数据文件。此外数据库还需要考虑并发控制、回收磁盘以控制日志文件大小、错误处理、部分完成写记录等诸多问题。

当日志变得非常大时db_get的性能会非常差，每次查找一个键的最坏开销为$O(n)$，为了加快查找，引入索引。索引的方法论为保留额外的元数据作为路标帮助定位数据，也可以针对不同的查询方式，在数据的不同部分，定义多种不同的索引。索引是原始数据派生出来的，众多数据库允许单独添加或删除索引且不影响数据库内容。然而，维护索引这个额外数据结构会引入开销，尤其是新数据写入时性能很难超过简单的追加文件方式。由于每次写都需要额外更新索引，任何类型的索引通常都会降低写速度。

索引的创建需要经过仔细的trade-off，适当的索引可以加快读取查询，但是索引也会降低写性能。

哈希索引

原理：假设数据全部由追加式文件组成，在内存中保存一个hash map用来记录每个key对应的value在数据文件中特定的字节偏移量。每当写入新的key或对已有key进行更新都要同时更新hash map。这就是Riak中默认存储引擎Bitcask采用的核心做法，非常适用于每个键的值频繁更新的场景，例如key为某个视频的URL，value是这个视频的播放次数，每当有人点击播放按钮就增加，这种工作负载每个key都有很多写操作，但是key大多相同，将所有key放入内存是可行的。

为减少磁盘空间损耗，将日志分解为一定大小的段，当段文件达到一定大小时关闭它，进行压缩删除重复的键保存最新键，执行压缩时可以将多个段进行合并。将后续写入切换到新的段文件中。这些冻结段的合并和压缩可以通过后台线程完成，运行时可用旧段文件继续正常读写操作。合并过程完成后，将读请求切换到新的合并段上，旧的段文件可以安全删除。每个段都有自己的内存hash表，为找到键的值，首先读取最新段的hash map，如果不在检查第二新的段，以此类推。

在实现时还要考虑：

文件格式：CSV不是最佳的文件格式，可以用二进制格式，以字节为单位记录字符串的长度，后边跟上原始字符串。
删除记录：追加的方式删除key以及对应的value。追加一个特殊的记录，合并时一旦发现标记则丢弃删除的键。
崩溃恢复：当数据库崩溃时内存中的hash map丢失，虽然可以全部扫描整个段文件重建hash map但是当段文件很大时时间消耗将很大，使得服务器重启变得缓慢。Bitcask通过将每个段的hash map的快照存储在磁盘上，可以更快的加载到内存加快故障恢复。
部分写入数据：数据库可能随时崩溃，Bitcask文件包括检验值以发现损坏部分并丢弃。
并发控制：写入是以严格的先后顺序追加到日志中，通常的实现选择只有一个写线程。数据文件时追加的且不可变，可被多个线程同时读取。

也许你会问，追加日志浪费空间，为什么不原地更新文件，用新值覆盖旧值？但是追加写的性能也是非常不错的。因为：

追加和合并主要是顺序写，考虑到磁盘的硬件特性，比随机写快的多。
段文件追加且不可变，则有利于并发和崩溃恢复。
合并旧段可以避免随着时间的推移数据文件出现碎片化问题。

哈希索引也有局限性：

hash map必须全部放入内存，当键数量巨大，原则上可以在磁盘上维护hash map，但是需要大量随机访问I/O，性能不好，hash变满时继续增长代价昂贵，且hash冲突时需要复杂的处理逻辑。
区间查询效率不高。不能简单的支持扫描kitty00000和kitty99999之间的所有键，只能采用逐个查找的方式查询每一个键。

SSTable和LSM-tree

上文提到的日志结构中每个存储段都是一组key-value对，这些key-value对按照它们写入的顺序排列，对于出现在日志中的同一个键，后出现的值优于之前的值，除此之外文件中的key-value对的顺序并不重要。

我们稍加改变，每个段文件中的key-value对按照键排序，成为排序字符串表，简称为SSTable。每个键在每个合并段中只出现一次（compaction压缩过程保证），SSTable相较于哈希索引具有以下优点：

合并段更加高效，即使文件大于可用内存，可以用类似归并排序的方法，并发读取多个输入段文件，比较每个文件中的第一个键，将最小的键拷贝到输出文件。由于段写入时间的有序性，如果相同的键出现在多个输入段，可以保留最新段的值。
在文件中查找特定的键时，不再需要在内存中保存所有键的索引，由于键的有序性可以采用稀疏索引。
读请求通常需要扫描请求范围内的多个key-value对，可以将上图阴影部分的数据压缩后再写入磁盘，稀疏索引的每个entry指向压缩块的开头。这样即节省了磁盘空间，也减少了I/O带宽占用。

构建和维护SSTable

考虑到写入顺序的随机性，一般在内存中维护排序结构，比如红黑树和AVL树，使用这些数据结构可以按照任意顺序插入键并以排序后的顺序读取它们。因此此类存储引擎的基本工作流程可以总结如下：

（1）当数据写入时将其添加到内存中的平衡结构树种，这个树被称为内存表；

（2）内存表大于某个阈值时，将其做为SSTable文件写入磁盘，因为树已经维护了有序结构，所以写入磁盘比较高效，新的SSTable作为数据库的最新部分。SSTable写入磁盘的同时可以新建一个内存表来接收写入操作；

（3）读请求首先在内存表中查找键，之后在最新的磁盘段文件查找，接下来是次新的磁盘段文件，直到找到目标或者为空；

（4）后台进程周期性的执行段合并与compaction压缩操作，合并多个段文件，丢弃已被覆盖或者删除的值；

为了防止数据库崩溃导致最近写入内存表中的数据丢失，可以在磁盘中保留单独的日志，每个写入都立即追加到日志，日志文件不需要按键排序，每当内存表写入SSTable时相应的日志可以丢弃。

从SSTable到LSM-Tree

LevelDB和RocksDB本质上使用了上述思想，主要用于嵌入到其他应用程序的key-value存储引擎库，一般的基于合并和压缩排序文件原理的存储引擎都被称之为LSM存储引擎。

性能优化

当查找某个不存在的键时，必须先检查内存表，然后将段一直回溯访问到最旧的段文件（可能必须从磁盘多次读取），为了优化访问可以使用额外的布隆过滤器，其是内存高效的数据结构，可以减少查找不存在键时不必要的磁盘读取；
大小分级和分层压缩也会影响SSTable压缩和合并的顺序和时机。LevelDB和RocksDB使用分层压缩，HBase使用大小分级，Cassandra同时支持两种压缩。

B-Tree

像SSTable一样B-tree保留按键排序的key-value对以实现高效的key-value查找和区间查询。日志结构索引将数据库分解为大小可变的段，通常为几兆字节或更大且始终按顺序写入段。B-tree将数据库分解成固定大小的块或页，传统上大小为4 KB，页是内部读写的最小单元，因为磁盘也是以固定大小的块排序，这种设计更加接近底层硬件。

B-tree中每个页面都可以用地址或位置进行标识，一个页面可以引用另一个页面，类似指针，不同的是指针指向内存地址，这里的页面引用指向磁盘地址。具有n个键的B-tree具有$O(logn)$的深度，大多数数据库可以适用3~4层的B-tree，分支因子为500的4 KB页的四级树可以存储高达256 TB数据。

B-tree底层的基本写操作适用新数据覆盖磁盘上的旧页，假设覆盖不会改变页的磁盘存储位置，当页被覆盖是对该页的引用保持不变。磁盘上的页覆盖对应确定的硬件操作，在磁盘上首先将磁头移动到正确的位置，然后旋转盘面，最后用新的数据覆盖相应的扇区。对于SSD必须一次擦除并重写非常大的存储芯片块，情况更为复杂。

为了使数据库能从崩溃中恢复，需要支持磁盘上的额外数据结构：预写日志（write-ahead log，WAL），WAL仅支持追加操作，每个B-tree的修改必须首先更新WAL然后再修改树本身的页。当数据库崩溃后恢复时使用该日志将B-tree恢复到最近一致的状态。
为了应对多个线程同时访问B-tree需要并发控制，通常使用锁存器。

一些已有的优化B-tree的措施：

一些数据库如LMDB不使用覆盖页和维护WAL来进行崩溃恢复，使用写时复制方案。修改的页被写入不同的位置，树中父页的新版本被创建并指向新的位置；
保存树的缩略信息，而不是完整的键以节省页空间。如B+树；
一般而言页可以放置在磁盘的任意位置，没有要求相邻的页需要放置在磁盘的相邻位置。如果查询需要按照顺序扫描大段的键范围，考虑到每个读取的页都需要磁盘I/O，许多B-tree的实现尝试对树进行布局，使得叶子页面按顺序出现在磁盘上。但是，随着树的增长，维持这个顺序是很困难的。相比之下，由于LSM树在合并过程中一次又一次地重写存储的大部分，所以它们更容易使顺序键在磁盘上彼此靠近。
添加额外的指针到树中。例如，每个叶子页面可以在左边和右边具有对其兄弟页面的引用，这允许不跳回父页面就能顺序扫描。
B树的变体如分形树借用一些日志结构的思想来减少磁盘寻道（而且它们与分形无关）。

对比B-Tree和LSM-Tree

尽管B树实现通常比LSM树实现更成熟，但通常LSM树的写入速度更快，而B树的读取速度更快。 LSM树上的读取通常比较慢，因为它们必须在压缩的不同阶段检查几个不同的数据结构和SSTable。

然而，基准通常对工作量的细节不确定和敏感。您需要测试具有特定工作负载的系统，以便进行有效的比较。在本节中，我们将简要讨论一些在衡量存储引擎性能时值得考虑的事情。B树索引必须至少两次写入每一段数据：一次写入预先写入日志，一次写入树页面本身（也许再次分页）。即使在该页面中只有几个字节发生了变化，也需要一次编写整个页面的开销。有些存储引擎甚至会覆盖同一个页面两次，以免在电源故障的情况下导致页面部分更新。由于反复压缩和合并SSTable，日志结构索引也会重写数据。这种影响 —— 在数据库的生命周期中写入数据库导致对磁盘的多次写入 —— 被称为写放大（write amplification）。需要特别注意的是固态硬盘，固态硬盘的闪存寿命在覆写有限次数后就会耗尽。在写入繁重的应用程序中，性能瓶颈可能是数据库可以写入磁盘的速度。在这种情况下，写放大会导致直接的性能代价：存储引擎写入磁盘的次数越多，可用磁盘带宽内的每秒写入次数越少。

LSM-tree优点：

LSM树通常能够比B树支持更高的写入吞吐量，部分原因是它们有时具有较低的写放大（尽管这取决于存储引擎配置和工作负载），部分是因为它们顺序地写入紧凑的SSTable文件而不是必须覆盖树中的几个页面。这种差异在磁性硬盘驱动器上尤其重要，顺序写入比随机写入快得多。
LSM树可以被压缩得更好，因此经常比B树在磁盘上产生更小的文件。 B树存储引擎会由于分割而留下一些未使用的磁盘空间：当页面被拆分或某行不能放入现有页面时，页面中的某些空间仍未被使用。由于LSM树不是面向页面的，并且定期重写SSTable以去除碎片，所以它们具有较低的存储开销，特别是当使用平坦压缩时。
在许多固态硬盘上，固件内部使用日志结构化算法，将随机写入转变为顺序写入底层存储芯片，因此存储引擎写入模式的影响不太明显。但是，较低的写入放大率和减少的碎片对SSD仍然有利：更紧凑地表示数据可在可用的I/O带宽内提供更多的读取和写入请求。

LSM-tree缺点：

日志结构存储的缺点是压缩过程有时会干扰正在进行的读写操作。尽管存储引擎尝试逐步执行压缩而不影响并发访问，但是磁盘资源有限，所以很容易发生请求需要等待而磁盘完成昂贵的压缩操作。对吞吐量和平均响应时间的影响通常很小，但是在更高百分比的情况下，对日志结构化存储引擎的查询响应时间有时会相当长，而B树的行为则相对更具可预测性；
压缩的另一个问题出现在高写入吞吐量：磁盘的有限写入带宽需要在初始写入（记录和刷新内存表到磁盘）和在后台运行的压缩线程之间共享。写入空数据库时，可以使用全磁盘带宽进行初始写入，但数据库越大，压缩所需的磁盘带宽就越多；
如果写入吞吐量很高，并且压缩没有仔细配置，压缩跟不上写入速率。在这种情况下，磁盘上未合并段的数量不断增加，直到磁盘空间用完，读取速度也会减慢，因为它们需要检查更多段文件。通常情况下，即使压缩无法跟上，基于SSTable的存储引擎也不会限制传入写入的速率，所以您需要进行明确的监控来检测这种情况；

其他索引结构

到目前为止，我们只讨论了关键值索引，它们就像关系模型中的主键（primary key） 索引，二级索引也很常见。

将值存储在索引中

索引中的关键字是查询搜索的内容，但是该值可以是以下两种情况之一：它可以是所讨论的实际行（文档，顶点），也可以是对存储在别处的行的引用。在后一种情况下，行被存储的地方被称为堆文件（heap file），并且存储的数据没有特定的顺序（它可以是仅附加的，或者可以跟踪被删除的行以便用新数据覆盖它们后来）。堆文件方法很常见，因为它避免了在存在多个二级索引时复制数据：每个索引只引用堆文件中的一个位置，实际的数据保存在一个地方。在不更改键的情况下更新值时，堆文件方法可以非常高效：只要新值不大于旧值，就可以覆盖该记录。如果新值更大，情况会更复杂，因为它可能需要移到堆中有足够空间的新位置。在这种情况下，要么所有的索引都需要更新，以指向记录的新堆位置，或者在旧堆位置留下一个转发指针。

在某些情况下，从索引到堆文件的额外跳跃对读取来说性能损失太大，因此可能希望将索引行直接存储在索引中。这被称为聚集索引。例如，在MySQL的InnoDB存储引擎中，表的主键总是一个聚簇索引，二级索引用主键（而不是堆文件中的位置）。在SQL Server中，可以为每个表指定一个聚簇索引。

在 聚集索引（clustered index） （在索引中存储所有行数据）和 非聚集索引（nonclustered index） （仅在索引中存储对数据的引用）之间的折衷被称为 包含列的索引（index with included columns）或覆盖索引（covering index），其存储表的一部分在索引内。这允许通过单独使用索引来回答一些查询（这种情况叫做：索引 覆盖（cover） 了查询）。
多列索引

多维索引（multi-dimensional index）是一种查询多个列的更一般的方法，这对于地理空间数据尤为重要。一种选择是使用空间填充曲线将二维位置转换为单个数字，然后使用常规B树索引。更普遍的是，使用特殊化的空间索引，例如R树。例如，PostGIS使用PostgreSQL的通用Gist工具将地理空间索引实现为R树。

多维索引不仅可以用于地理位置。在电子商务网站上可以使用维度（红色，绿色，蓝色）上的三维索引来搜索特定颜色范围内的产品，也可以在天气观测数据库中搜索二维（日期，温度）的指数，以便有效地搜索2013年的温度在25至30°C之间的所有观测资料。使用一维索引，你将不得不扫描2013年的所有记（不管温度如何），然后通过温度进行过滤，反之亦然。二维索引可以同时通过时间戳和温度来收窄数据集。这个技术被HyperDex使用。
全文搜索和模糊索引

为了处理文档或查询中的拼写错误，Lucene能够在一定的编辑距离内搜索文本（编辑距离1意味着添加，删除或替换了一个字母）。
内存数据库

随着内存成本降低，每GB成本摊薄，许多数据集不是很大可以完全保留在内存中或者分布在多台机器上，推动了内存数据库的发展。内存数据库重新启动时，需要从磁盘或通过网络从副本重新加载其状态。尽管写入磁盘，它仍然是一个内存数据库，因为磁盘仅用作耐久性附加日志，读取完全由内存提供。写入磁盘也具有操作优势：磁盘上的文件可以很容易地由外部实用程序进行备份，检查和分析。

诸如VoltDB，MemSQL和Oracle TimesTen等产品是具有关系模型的内存数据库，供应商声称，通过消除与管理磁盘上的数据结构相关的所有开销，他们可以提供巨大的性能改进。 RAM Cloud是一个开源的内存键值存储器，具有持久性（对存储器中的数据以及磁盘上的数据使用日志结构化方法）。 Redis和Couchbase通过异步写入磁盘提供了较弱的持久性。
- 内存数据库的性能优势并不是因为它们不需要从磁盘读取，它们更快的原因在于省去了将内存数据结构编码为磁盘数据结构的开销。
- 除了性能，内存数据库的另一个有趣的领域是提供难以用基于磁盘的索引实现的数据模型。例如，Redis为各种数据结构（如优先级队列和集合）提供了类似数据库的接口。因为它将所有数据保存在内存中，所以它的实现相对简单。
- 最近的研究表明，内存数据库体系结构可以扩展到支持比可用内存更大的数据集，而不必重新采用以磁盘为中心的体系结构。所谓的 反缓存（anti-caching） 方法通过在内存不足的情况下将最近最少使用的数据从内存转移到磁盘，并在将来再次访问时将其重新加载到内存中。

事务处理与分析处理

属性	事务处理 OLTP	分析系统 OLAP
主要读取模式	查询少量记录，按键读取	在大批量记录上聚合
主要写入模式	随机访问，写入要求低延时	批量导入（ETL），事件流
主要用户	终端用户，通过Web应用	内部数据分析师，决策支持
处理的数据	数据的最新状态（当前时间点）	随时间推移的历史事件
数据集尺寸	GB ~ TB	TB ~ PB

数据仓库

一个企业可能有几十个不同的交易处理系统：面向终端客户的网站，控制实体商店的收银系统，跟踪仓库库存，规划车辆路线，供应链管理，员工管理等。这些系统中每一个都很复杂，需要专人维护，所以系统最终都是自动运行的。这些OLTP系统往往对业务运作至关重要，因而通常会要求 高可用 与 低延迟。所以DBA会密切关注他们的OLTP数据库，他们通常不愿意让业务分析人员在OLTP数据库上运行临时分析查询，因为这些查询通常开销巨大，会扫描大部分数据集，这会损害同时执行的事务的性能。相比之下，数据仓库是一个独立的数据库，分析人员可以查询他们想要的内容而不影响OLTP操作。数据仓库包含公司各种OLTP系统中所有的只读数据副本。从OLTP数据库中提取数据（使用定期的数据转储或连续的更新流），转换成适合分析的模式，清理并加载到数据仓库中。将数据存入仓库的过程称为“抽取-转换-加载（ETL）”。

表面上，一个数据仓库和一个关系OLTP数据库看起来很相似，因为它们都有一个SQL查询接口。然而，系统的内部看起来可能完全不同，因为它们针对非常不同的查询模式进行了优化。在事务处理领域中使用了大量不同的数据模型。另一方面，在分析中，数据模型的多样性则少得多。许多数据仓库都以相当公式化的方式使用，被称为星型模式（也称为维度建模）。

列式存储

面向列的存储背后的想法很简单：不要将所有来自一行的值存储在一起，而是将来自每一列的所有值存储在一起。如果每个列存储在一个单独的文件中，查询只需要读取和解析查询中使用的那些列，这可以节省大量的工作。面向列的存储布局依赖于包含相同顺序行的每个列文件。因此，如果您需要重新组装整行，您可以从每个单独的列文件中获取第23项，并将它们放在一起形成表的第23行。

列压缩

根据列中的数据，可以使用不同的压缩技术。在数据仓库中特别有效的一种技术是位图编码。

列存储中的排序

在列存储中，存储行的顺序并不一定很重要。按插入顺序存储它们是最简单的，因为插入一个新行就意味着附加到每个列文件。但是，我们可以选择强制执行一个命令，就像我们之前对SSTable所做的那样，并将其用作索引机制。排序的一个好处是可以优化查询优化器在第一个排序键上边的扫描，另一个好处是它可以帮助压缩列，第一个排序键的压缩效果最强。

聚合：数据立方体与物化视图

数据仓库的另一个值得一提的是物化汇总。如前所述，数据仓库查询通常涉及一个聚合函数，如SQL中的COUNT，SUM，AVG，MIN或MAX。如果相同的聚合被许多不同的查询使用，那么每次都可以通过原始数据来处理。为什么不缓存一些查询使用最频繁的计数或总和？

创建这种缓存的一种方式是物化视图。在关系数据模型中，它通常被定义为一个标准（虚拟）视图：一个类似于表的对象，其内容是一些查询的结果。不同的是，物化视图是查询结果的实际副本，写入磁盘，而虚拟视图只是写入查询的捷径。从虚拟视图读取时，SQL引擎会将其展开到视图的底层查询中，然后处理展开的查询。

物化视图的常见特例称为数据立方体或OLAP立方。它是按不同维度分组的聚合网格。物化数据立方体的优点是某些查询变得非常快，因为它们已经被有效地预先计算了。缺点是数据立方体不具有查询原始数据的灵活性。因此，大多数数据仓库试图保留尽可能多的原始数据，并将聚合数据（如数据立方体）仅用作某些查询的性能提升。

小结

在本章中，我们试图深入了解数据库如何处理存储和检索。将数据存储在数据库中会发生什么，以及再次查询数据时数据库会做什么。在高层次上，我们看到存储引擎分为两大类：优化事务处理（OLTP）或在线分析（OLAP）。这些用例的访问模式之间有很大的区别：

OLTP系统通常面向用户，这意味着系统可能会收到大量的请求。为了处理负载，应用程序通常只访问每个查询中的少部分记录。应用程序使用某种键来请求记录，存储引擎使用索引来查找所请求的键的数据。磁盘寻道时间往往是这里的瓶颈。
数据仓库和类似的分析系统会低调一些，因为它们主要由业务分析人员使用，而不是由最终用户使用。它们的查询量要比OLTP系统少得多，但通常每个查询开销高昂，需要在短时间内扫描数百万条记录。磁盘带宽（而不是查找时间）往往是瓶颈，列式存储是这种工作负载越来越流行的解决方案。

在OLTP方面，我们能看到两派主流的存储引擎：

日志结构学派：只允许附加到文件和删除过时的文件，但不会更新已经写入的文件。 Bitcask，SSTables，LSM树，LevelDB，Cassandra，HBase，Lucene等都属于这个类别；
就地更新学派：将磁盘视为一组可以覆写的固定大小的页面。 B树是这种哲学的典范，用在所有主要的关系数据库中和许多非关系型数据库；