《数据密集型应用系统设计》读书笔记（三）

从最基本的层面来看，数据库只需要做两件事情：

1. 当给出数据时对数据进行存储
2. 当查询数据时对数据进行返回

上一章讨论了数据模型与查询语言，即向数据库给出数据时数据的格式以及数据查询的机制，其可以理解为从应用开发者的角度出发讨论了上述两件事情。本章将从「数据库」的角度来进行讨论，即如何存储给出的数据以及如何在要求查询时找到所需的数据，所介绍的存储引擎可以用于传统的关系数据库和大多数 NoSQL 数据库。

1 数据库核心：数据结构

首先介绍一个世界上最简单的数据库，其通过两个 Bash 函数实现：

#!/bin/bash

db_set () {
    echo "$1,$2" >> database
}

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

这两个函数实现了一个 key-value 存储。当调用 db_set key value 时，它将在数据库中保存所输入的 key 和 value；然后，调用 db_get key，它会查找与输入 key 相关联的最新值并返回。例如：

$ db_set 123456 '{"name":"London","attractions":["Big Ben","London Eye"]}'

$ db_set 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 database
123456,{"name":"London","attractions":["Big Ben","London Eye"]}
42,{"name":"San Francisco","attractions":["Golden Gate Bridge"]}
42,{"name":"San Francisco","attractions":["Exploratorium"]}

该数据库的底层存储格式非常简单：一个「纯文本」文件，其中每行包含一个 key-value 对，用逗号分隔（与 CSV 文件类似，忽略转义问题）。每次调用 db_set 文件将追加新内容到文件末尾，即便多次更新某个键，旧版本的值也不会被覆盖，而是需要查看文件中「最后一次」出现的键来找到最新的值（在 db_get 中使用了 tail -n 1）。

追加文件尾部方式的「优点」在于其非常高效，使得 db_set 函数的性能很好。当前许多数据库内部都使用了与这种方式的基本原理相同的「日志」（log），其是一个仅支持追加式更新的数据文件。另一方面，这种方式的「缺点」在于，如果日志文件保存了大量的记录，那么 db_get 函数的性能会非常差，每一次查询都需要从头到尾扫描整个数据库文件。

为了高效地查找数据库中特定键的值，我们需要一种新的数据结构：「索引」（index）。索引的基本想法是保留一些额外的元数据，这些元数据作为路标，帮助定位想要的数据。很多数据库允许单独添加和删除索引，而不影响数据库的内容。然而，维护额外的结构势必会引入开销，特别是在新数据写入时。我们需要在读和写之间进行「权衡」：适当的索引可以加速读取查询，但是每个索引都会减慢写速度。默认情况下，数据库通常不会对所有内容进行索引，需要开发人员基于对应用程序典型查询模式的了解，来手动选择索引，以在为应用程序提供最有利加速的同时，避免引入过多不必要的开销。

1.1 哈希索引

键-值数据是一种常见的数据类型，其与大多数编程语言内置的字典结构相似，而字典通常采用「哈希表」（hash map or hash table，本节不作区分）来实现。对于这种类型的数据，我们可以考虑基于哈希表来构建索引，即「哈希索引」。

假定数据存储全部采用追加式文件组成，那么一种可行的索引方式是：在内存中保存一个 hash map，把每个键一一映射到数据文件中特定的字节偏移量，以便找到每个值的位置，如下图所示：

每当在文件中追加新的 key-value 对时，需要更新 hash map 来反映刚刚写入数据的偏移量（包括插入新的键与更新已有的键）。当查找某个值时，使用 hash map 来找到文件中的偏移量，即存储位置，然后读取其内容。

上述方法虽然简单，但确实可行，并且能够实现较高性能的读和写，只要所有的 key 可以放入内存（key-value 类型一般不涉及额外的索引，也就没有权衡问题）。对于 value 数据，则可以超过内存大小，存放在磁盘中，并且能够通过缓存等方式来减少磁盘 I/O。

对于追加文件的存储方式，还需要考虑的一个问题是如何避免用尽「磁盘空间」。一种较好的解决方案是将日志分解成一定大小的「片段」（segments），当片段达到指定大小时就关闭它，并将后续写入到新的片段文件中。然后，在这些片段上进行「压缩」（compaction），丢弃日志中重复的键，只保留每个键最近的更新，如下图所示：

此外，由于压缩往往使得片段变得更小，也可以在执行压缩的同时将多个片段合并在一起，如下图所示。由于片段在写入后不可修改（只会追加），所以合并后的片段会被写入另一个新的文件。对于这些冻结段（已达到指定大小）的合并与压缩过程可以在后台线程中完成，且在运行时，仍然可以使用旧的片段文件执行读取请求（写请求在新的片段中）。在合并完成后，将读取请求切换到新的合并片段上，并将旧的片段删除。

每个片段中都有自己的内存哈希表，将键映射到文件的偏移量。为了找到键的值，首先检查最新片段的哈希表，如果键不存在，则检查第二新的片段，以此类推。由于合并过程可以维持较少的片段数量，查找通常不需要检查很多的哈希表。

以上就是对哈希索引的简单介绍。在哈希索引的实际实现（例如 Bitcask）中，还需要考虑以下这些重要问题：

• 「文件格式」：在上面的案例中，使用 CSV 作为日志的格式。实际上，更快更简单的方法是使用二进制格式，以字节为单位来记录字符串的长度，并在之后跟上原始字符串（不需要转义）。
• 「删除记录」：如果要删除键和它关联的值，则需要在数据文件中追加一个特殊的删除记录（因为无法修改），该记录有时也被称为墓碑标记（tombstone）。当合并日志片段时，墓碑标记会告知合并过程丢弃这个已删除键的所有值。
• 「崩溃恢复」：如果数据库重新启动，则内存中的哈希表会丢失。原则上，可以通过从头到尾读取整个片段文件，记录每个键的最新值的偏移量，来恢复每个片段的哈希表。为了加快恢复速度，可以考虑将每个片段的哈希表快照存储在磁盘上，以便更快的加载到内存中。
• 「部分写入的记录」：由于数据库随时可能崩溃，需要在将记录追加到日志的时候设置校验值，以便于发现损坏部分并丢弃。
• 「并发控制」：由于写入以严格的先后顺序追加到日志中，通常的实现选择是只有一个写线程。数据文件片段是不可变的（仅支持追加），可以被多个线程同时读取（不用担心出现读取结果不一致的情况）。

总的来看，以追加式设计为核心的哈希索引具有写入速度快、并发与崩溃恢复简单等优点，但也存在着内存限制、区间查询效率低等局限性。

1.2 SSTable 和 LSM-Tree

1.2.1 SSTable 简介

在上一节介绍的原始哈希索引中，键值对按照写入顺序排列，对于同一个键，后出现的值优于之前的值。除此之外，文件中的键值对顺序并不重要。现在，我们将简单地改变片段文件的形式：要求键值对「按照键进行排序」，这种格式被称为「排序字符串表」（Sorted String Table，SSTable），其要求每个键在每个合并的片段文件中只出现一次（合并过程已经确保了这一点）。与原始哈希索引的日志片段相比，SSTable 的优点主要体现在以下三个方面：

1. 「合并片段更加简单高效」。对于 SSTable，其段落的合并类似于归并排序算法，如下图所示。端到端地并发读取多个输入片段文件，比较每个文件中的第一个键，将最小的键拷贝到输出文件，并不断重复上述过程，以产生一个新的按键排序的合并片段文件。这种方法对于文件大于可用内存的情况也能够处理（并非一次性读取整个文件）。

1. 「不再需要在内存中保存所有键的索引」。由于键是按顺序存储的，所以在文件中查找特定的键时，可以直接跳到该键前某个键的偏移，从那里开始扫描，而无需遍历所有键。如下图所示，handiwork 键一定位于 handbag 和 handsome 之间。因此，所构建的内存索引可以是稀疏的，只需要记录某些键的偏移量。定位到离目标键最近的键后，直接在片段文件中进行扫描即可。

1. 「可以对记录进行压缩存储以节省空间」。由于查询请求需要扫描一定范围内的多个键值对，我们可以考虑将这些记录保存到一个块中，并在写磁盘之间将其进行压缩（如上图所示，此处的压缩为使用特定的压缩算法如 Snappy 进行压缩，注意与合并过程中的压缩区分），然后稀疏内存索引的每个条目指向压缩块的开头。除了节省磁盘空间外，这种压缩还减少了 I/O 带宽的占用。

1.2.2 构建和维护 SSTable

了解了 SSTable 的基本工作原理后，考虑到写入可能以任意顺序出现，我们需要一种方法来让数据能够依照键进行排序。虽然在磁盘上维护排序结构是可行的，不过在内存中进行要更加容易。内存排序有很多广为人知的树状数据结构，例如红黑树或 AVL 树。使用这些数据结构，可以按任意顺序插入键并以排序后的顺序读取它们。

具体来说，基于 SSTable 的存储引擎的基本工作流程如下：

• 当写入数据时，将其添加到内存中的平衡树结构中（如红黑树）。这个内存中的树有时被称为「内存表」（memtable）。
• 当内存表大于某个阈值（通常为几兆字节）时，将其作为 SSTable 文件写入磁盘。由于树已经维护了排序后的键值对，所以写入会比较高效。新的 SSTable 文件将会成为数据库的最新片段。当 SSTable 写入磁盘的同时，写入可以继续添加到一个新的内存表实例。
• 为了处理读取请求，首先会尝试在内存表中查找键，然后是最新的磁盘片段，接下来是次新的磁盘片段，以此类推，直到找到目标。
• 后台进程会周期性地执行合并与压缩过程，以合并多个片段文件，并丢弃那些已被覆盖或删除的值，同时节省磁盘空间。

上述方案可以很好地工作，但也存在一个问题：如果数据库崩溃，那么最近的写入（在内存表中但尚未写入磁盘）将会丢失。为了避免该问题，可以在磁盘上保留单独的日志，每个写入都会立即追加到该日志。该日志不需要按键排序，其唯一目的是在崩溃后恢复内存表。每当将内存表写入 SSTable 时，相应的日志可以被丢弃。

基于上述算法构建的存储引擎被用在包括 LevelDB、RocksDB、Cassandra、HBase 等数据库中。最初这种索引结构由 Patrick O'Neil 等人命名为「日志结构的合并树」（LSM-Tree），现在将基于合并和压缩排序文件原理的存储引擎统称为 LSM 存储引擎。

1.2.3 性能优化

在进行存储引擎的实际实现时，还有很多细节值得深入优化。例如，当查找数据库中某个不存在的键时，LSM-Tree 算法需要先检查内存表，再一直回溯访问到最旧的片段文件，导致速度非常慢。为了优化这种访问，存储引擎常常使用额外的「布隆过滤器」（bloom filters）。布隆过滤器是一种内存高效的数据结构，用以近似计算集合的内容，能够很快地知道数据库中是否存在某个键。

此外，对于 SSTable 的压缩合并的具体顺序与时机，最常见的方式是「大小分级」（size-tiered）和「分层压缩」（leveled compaction）。在大小分级的压缩中，较新与较小的 SSTable 被连续合并到较旧和较大的 SSTable 中；在分层压缩中，键的范围分裂成多个更小的 SSTables，旧数据被移动到单独的”层级“，这样压缩可以逐步进行并使用更少的磁盘空间。在上一小节提到的数据库中，LevelDB 与 RocksDB 使用分层压缩，HBase 使用大小分级，而 Cassandra 则同时支持这两种压缩。

总的来说，即使有很多细微的差异，但 LSM-tree 的基本思想——「保存在后台合并的一系列 SSTable」——是非常简单且有效的。即便数据集远远大于可用内存，它仍然能够正常工作。由于数据按排序存储，我们可以高效地执行区间查询，且序列性的磁盘写入可以支持非常高的写入吞吐量。

1.3 B-Tree

除了上述讨论的日志结构索引，实际上，目前最常见且广泛使用的一种索引类型是 「B-tree」。与 SSTable 一样，B-tree 保留按键排序的键值对，以实现高效的 key-value 查找和区间查询，但是其本质上有着非常不同的设计理念。

不同于日志结构索引将数据库分解为可变大小的段（一般几兆字节或更大），B-tree 将数据库分解成「固定大小」的块或页（一般为 4 KB），页是内部读/写的最小单元，每个页面都可以使用地址或位置进行标识，这样可以让一个页面引用另一个页面，类似指针。我们可以使用这些页面引用来构造一个「树状页面」，如下图所示：

某一页会被指定为 B-tree 的「根」（root），当查找索引中的一个键时，总是从这里开始。该页面包含若干个键和对子页的引用，每个子页都负责一系列连续范围内的键，相邻引用之间的键可以指示这些范围之间的边界。B-tree 中一个页所包含的子页的引用数量称为「分支因子」（branching factor），上图中的分支因子为 6，实际情况下分支因子的大小取决于存储页面引用和范围边界所需的空间总量，通常为几百个。

如果需要更新 B-tree 中「现有键的值」，首先应搜索包含该键的叶子页，更改该页的值，并将页写回到磁盘；如果需要添加「新键」，则需要找到其范围包含新键的页，并将其添加到该页，如果页中没有足够的空间来容纳新键，则将其分裂为两个半满的页，并且父页也需要更新以包含分裂之后的新的键范围，如下图所示：

上述算法可以确保树保持「平衡」：具有

个键的 B-tree 总是具有

的深度。大多数数据库可以构建 3-4 层的 B-tree，不需要遍历非常深的页面引用即可找到所需的页（分支因子为 500 的 4 KB 页的四级树可以存储高达 256 TB）。

1.3.1 使 B-tree 可靠

对于 B-tree 来说，其底层的写操作是使用新数据来「覆盖」磁盘上的旧页，假定覆盖不会改变页的磁盘存储位置，对该页的所有引用保持不变。与之相比，日志结构索引（如 LSM-tree）仅追加更新文件（并删除过时文件），但不会修改文件。

在硬件层面上，对于磁性硬盘驱动器，覆盖操作意味着将磁头移动到正确的位置，然后旋转盘面，最后用新的数据覆盖相应的扇区；而对于 SSD，由于 SSD 必须一次擦除并重写非常大的存储芯片块，情况会更加复杂。

由于覆盖操作的复杂性，其有时会带来较大的风险。一方面，某些操作需要覆盖多个不同的页，如果数据库在完成部分页写入之后发生崩溃，最终会导致索引被破坏。为了防止上述情况发生，常见的 B-tree 实现需要包括一个磁盘上的额外数据结构：「预写日志」（write-ahead log，WAL），这是一个仅支持追加修改的文件，每个 B-tree 的修改必须先更新 WAL 然后再修改树本身的页。当数据库崩溃后需要修复时，该日志用于将 B-tree 恢复到一致的状态。

另一方面，如果多个线程要同时访问 B-tree，原地更新页需要注意并发控制，以防止线程可能会看到树处于不一致的状态。通常可以使用「锁存器」（latches），即轻量级的锁来保护树的数据结构。与之相比，日志结构索引在后台执行所有合并，并不会干扰前端的查询，并且会不时地用新段原子性地替换旧段。

1.3.2 优化 B-tree

下面列举一些针对 B-tree 的优化措施：

• 某些数据库不使用覆盖页和维护 WAL 来进行崩溃恢复，而是使用写时复制方案，修改的页被写入不同的位置
• 保存键的缩略信息以节省页空间，只需要提供足够的信息来描述键的起止范围
• 许多 B-tree 的实现尝试对树进行布局，以便相邻叶子页可以按顺序保存在磁盘上，提升读取效率
• 添加额外的指针到树中，如每个叶子页面可能会向左和向右引用其同级的兄弟页，这样可以避免跳回父页
• 借鉴日志结构的想法来减少磁盘寻道（分形树）

1.4 对比 B-Tree 和 LSM-Tree

虽然 B-tree 的实现比 LSM-tree 更成熟，但是由于 LSM-tree 的性能优点，其所代表的日志结构索引正越来越受欢迎。根据经验，LSM-tree 通常对于写入更快，而 B-tree 被认为对于读取更快，下面将简要地描述 LSM-tree 与 B-tree 相比的优缺点。

1.4.1 LSM-tree 的优点

对于 B-tree 索引来说，一次写操作必须至少写两次数据：一次写入预写日志，一次写入树的页本身；而日志结构索引由于反复压缩和 SSTable 的合并，也会重写数据多次。这种一次数据库写入请求导致的多次磁盘写被称为「写放大」（write amplification）。对于大量写密集的应用程序，写放大具有直接的性能成本。

一般来说，LSM-tree 有时具有「较低的写放大」，能够承受比 B-tree 更高的写入吞吐量。部分原因在于它们以顺序方式写入紧凑的 SSTable 文件，而不必重写树中的多个页。

另一方面，LSM-tree 可以支持更好的压缩，通常磁盘上的文件比 B-tree 小很多。由于页的碎片化，B-tree 存储引擎有时会使某些磁盘空间无法使用，而 LSM-tree 不是面向页的，且定期重写 SSTable 以消除碎片化。综合以上几点，LSM-tree 相比 B-tree 具有「较低的存储开销」。

1.4.2 LSM-tree 的缺点

日志结构索引的缺点主要体现在压缩过程有时会干扰正在进行的读写操作。一方面，由于磁盘的并发资源有限，当执行昂贵的压缩操作时，很容易发生读写请求等待的情况；另一方面，在高写入吞吐量时，磁盘的有限写入带宽需要在的初始写入和后台运行的压缩线程之间所共享，可能发生压缩无法匹配新数据写入速率的情况，导致读取速度的降低（需要检查更多的段文件）。

相比之下，B-tree 的优点在于每个键都恰好唯一对应于索引中的某个位置，而日志结构的存储引擎可能在不同段中具有相同键的多个副本，这一优点可以为 B-tree 带来更强大的事务语义。

总的来看，虽然日志结构索引越来越受欢迎，但是对于具体的应用场景，还是需要「实地测试」来决定哪种存储引擎更加适合。

1.5 其他索引结构

上述讨论的索引都是 key-value 索引，其作用类似于关系模型中的「主键」（primary key）索引，主键唯一标识关系表中的一行，或文档数据库中的一个文档，或图形数据库中的一个顶点。数据库中的其他记录可以通过其主键来引用该行/文档/顶点，主键索引用于解析此类引用。

与主键索引相呼应，「二级索引」（secondary index）也很常见，其通常对于高效地执行联结操作十分重要。在关系数据库中，我们可以在同一个表上创建多个二级索引。二级索引可以较容易地基于 key-value 索引来构建，区别在于它的键不是唯一的，这可以通过两种方式解决：

• 使索引中的每个值成为匹配行标识符的列表
• 追加一些行标识符来使每个键变得唯一

无论使用哪种方式，B-tree 和日志结构索引都可以用作二级索引。实际上，除了这两种常见的索引结构，还有一些其他的索引结构，下面将对这些索引结构进行简要的介绍。

1.5.1 在索引中存储值

索引中的键是查询搜索的对象，而值可以是以下两类之一：

• 实际的行（文档、顶点）
• 对其他地方存储的行的引用

对于第二种情况，存储行的具体位置被称为「堆文件」（heap file），它不以特定的顺序存储数据（可以是追加式或覆盖式），当存在多个二级索引时，可以避免复制数据。如果采用覆盖式更新，对方法在更新值而不更改键时会非常高效，只要新值的字节数不大于旧值，记录就可以直接覆盖。

对于第一种情况，有时从索引到堆文件的额外跳转会带来较大的读取性能损失，这时我们希望将索引行直接存储在索引中，这被称为「聚集索引」（clustered index）。例如，在 MySQL InnoDB 存储引擎中，表的主键始终是聚集索引，二级索引引用主键位置。PS: 索引还是保存在磁盘中的，需要查询时再加载到内存里。

聚集索引和非聚集索引之中有一种折中设计，称为「覆盖索引」（covering index）或「包含列的索引」（index with included columns），它在索引中保存一些表的列值，可以支持只通过索引即可回答某些简单查询。

总的来看，聚集和覆盖索引可以加快读取速度，但是它们需要额外的存储，并且会增加写入的开销。此外，数据库还需要更多的工作来保证事务性，以防止应用程序因为数据冗余而得到不一致的结果。

1.5.2 多列索引

目前为止讨论的索引只将一个键映射到一个值，如果需要同时查询表的多个列，则无法满足要求，需要构建多列索引。

最常见的多列索引类型称为「级联索引」（concatenated index），它通过将一列追加到另一列，将几个字段简单地组合成一个键（索引的定义指定字段连接的顺序）。需要注意，索引的查找会严格遵循字段的连接顺序（可以单独查第一个字段，但不能单独查第二个字段）。

更普遍的一次查询多列的方法是多维索引。以地理空间数据为例，当用户在地图上查找地点时，需要进行一个包含经度和纬度的二维范围查询，如下所示：

SELECT * FROM restaurants WHERE latitude > 51.4946 AND latitude < 51.5079 
                            AND longitude > -0.1162 AND longitude < -0.1004;

标准的 B-tree 或 LSM-tree 无法高效地应对这种查询，只能分次进行。一种优化方法是使用空格填充曲线将二维位置转换为单个数字，然后使用常规的 B-tree 索引；另一种更常见的方法是使用专门的空间索引，如 R 树，此处不作展开。

1.5.3 全文搜索和模糊索引

目前为止讨论的索引都假定具有确切的数值，并允许查询键的确切值或排序后的键的取值范围。在某些场景下，我们需要进行模糊搜索，仅搜索类似的键，例如拼写错误的单词。实现这种模糊查询需要不同的技术。在全文搜索中，通常支持对一个单词的所有同义词进行查询，并忽略单词语法上的变体，Lucene（一种全文搜索引擎工具包）支持在某个编辑距离内搜索文本，其对词典使用类似 SSTable 的结构，内存中的索引是键中的字符序列的有限状态自动机，支持在给定编辑距离内高效地搜索单词。

此外，其他模糊搜索技术则沿着文档分类和机器学习的方向发展，更多细节需参考信息检索方面的文献。

1.5.4 在内存中保存所有内容

目前为止讨论的数据结构都是为了适应磁盘限制。与内存相比，磁盘更难以处理，如果要获得良好的读写性能，需要精心安排磁盘上的数据布局。随着内存变得更便宜，其成本逐渐降低，且许多数据集并没有那么大，可以将它们完全保留在内存中，这推动了「内存数据库」（in-memory databases）的发展。

对于某些内存数据库来说，内存中的 key-value 存储仅用于缓存（例如 Memcached），其接受机器重启造成的数据丢失。而对于其他内存数据库来说，其旨在实现「持久性」，例如可以通过特殊硬件、或将更改记录写入磁盘，或将定期快照写入磁盘，以及复制内存中的状态到其他机器等方式来实现。当内存数据库重启时，需要基于持久性的实现媒介来重新载入其状态。

在实际产品上，诸如 VoltDB、MemSQL 和 Oracle TimesTen 都是具有关系模型的内存数据库，通过移除与管理磁盘数据结构相关的开销，这些数据库可以获得极大的性能提升。RAMCloud 是一个开源的、具有持久性的内存 key-value 存储（使用日志结构），而 Redis 和 Couchbase 则通过异步写入磁盘提供较弱的持久性。

与直觉相反，内存数据库的性能优势并不是因为它们不需要从磁盘读取（在足够内存下基于磁盘的存储引擎也可能不需要读取），而是因为它们避免了使用写磁盘的格式对内存数据结构编码的开销。此外，内存数据库还提供了基于磁盘索引难以实现的某些数据模型，例如 Redis 为各种数据结构（如优先级队列和集合）都提供了类似数据库的访问接口。

最近的研究表明，内存数据库架构还可以扩展到支持远大于内存的数据集，而不会导致以磁盘为中心架构的开销。这种所谓的「反缓存」（anti-caching）方法，当没有足够的内存时，通过将最近最少使用的数据从内存写到磁盘，并在将来再次被访问时将其加载到内存。这种方法与操作系统对虚拟内存和交换文件的操作类似，但是可以在记录级别而不是整个内存页的粒度工作。不过，这种方法仍然需要索引完全放入内存。

2 事务处理与分析处理

在商业数据处理的早期阶段，写入数据库通常对应于商业交易场景。尽管目前数据库已经扩展到了各种领域，但「事务」（transaction）一词仍然存在，主要指一个逻辑单元的一组读写操作。事务不一定具有 ACID （原子性、一致性、隔离性和持久性）属性，只是意味着允许客户端进行低延迟读取和写入。进一步地，尽管处理数据的种类不同，数据库的基本访问方式仍然与处理业务交易类似，通常使用索引中的某些键查找少量记录，根据用户的输入插入或更新记录，这种基于交互式应用的访问模式被称为「在线事务处理」（OLTP）。

另一方面，数据库也开始越来越多地用于「数据分析」。数据分析具有非常不同的访问模式：分析查询通常需要扫描大量记录，每条记录只读取少数几列，并计算汇总统计信息，而不是返回原始数据给用户。这些查询通常由业务分析师编写，称之为「在线分析处理」（OLAP）。OLTP 和 OLAP 之间的区别有时并不那么明确，下表对它们的一些经典特征进行了总结：

最初，相同的数据库可以同时用于事务处理与分析查询，例如 SQL 可以同时胜任 OLTP 和 OLAP 类型的查询。然而，自 20 世纪 80 年代后期以来，很多公司放弃使用 OLTP 系统用于分析目的，而是在单独的数据库上进行分析，这个单独的数据库被称为「数据仓库」（data warehouse）。

2.1 数据仓库

「数据仓库」是一种独立于 OLTP 系统之外的数据库，可以帮助分析人员在不影响 OLTP 操作的情况下进行分析，其通常包括所有各种 OLTP 系统的只读副本。从 OLTP 数据库中提取数据（使用周期性数据转储或连续更新流），转换为分析友好的模式，执行必要的清理，然后加载到数据仓库中，这种将数据导入数据仓库的过程称为「提取-转换-加载」（ETL），如下图所示：

使用单独的数据仓库而不是直接查询 OLTP 系统进行分析，一个优势在于数据仓库可以针对分析访问模式进行优化。事实证明，本章前半部分讨论的索引算法适合 OLTP，但不擅长应对分析查询。数据仓库的数据模型最常见的是关系型，虽然其和关系型 OLTP 表面上都具有 SQL 查询接口，但是系统内部针对迥然不同的查询模式进行了各自优化。

许多数据库供应商现在专注于支持事务处理或分析工作负载，但不能同时支持两者。事务处理与数据仓库越来越成为两个独立的存储和查询引擎。此外，除了成熟的商业数据仓库系统，还出现了大量开源的基于 Hadoop 的 SQL 项目，包括 Apache Hive、Spark SQL、Cloudera Impala、Facebook Presto、Apache Tajo 和 Apache Drill，其中一些系统基于 Google Dremel 而构建。

2.2 星型与雪花型分析模式

根据不同的应用需求，事务处理领域广泛使用了多种不同的数据模型（见第 2 章），而分析型业务的数据模型则要少得多，许多数据仓库都相当公式化地使用了「星型模式」（star schema），也被称为「维度建模」（dimensional modeling）。该模式基于关系型数据库实现。

如下图所示，星型模式的中心是一个所谓的「事实表」（fact table），图中对应为 fact_sales 表。事实表的每一行表示在特定时间发生的事件（图中每一行表示客户购买的一个产品）。通常，事实被捕获为独立的事件，使得之后的分析具有最大的灵活性，这也意味着事实表可能会变得非常庞大。

事实表中的部分列是属性，例如产品销售的价格，供应商的成本等，而其他列可能会引用其他表的外键，称为「维度表」（dimension tables），维度通常代表事件的对象（who）、内容（what）、地点（where）、时间（when）、方法（how）以及原因（why）。

星型模式的一个变体被称为「雪花模式」（snowflake schema），其中维度进一步细分为子空间。雪花模式比星型模式更规范化，但是星型模式通常是首选，主要是因为对于分析人员，星型模式使用起来更简单。

3 列式存储

如果事实表中有数以万亿行、PB 大小的数据，高效地存储与查询这些数据将成为一个具有挑战性的问题，相比之下维度表通常小得多，因此本节将主要关注事实表的存储。实际上，虽然事实表通常超过 100 列，但典型的数据仓库查询往往一次只访问其中的 4 或 5 个，如下例所示（结果只需返回三列）：

SELECT 
  dim_date.weekday, dim_product.category,
  SUM(fact_sales.quantity) AS quantity_sold
FROM fact_sales
    JOIN dim_date ON fact_sales.date_key = dim_date.date_key
    JOIN dim_product ON fact_sales.product_sk = dim_product.product_sk
WHERE
    dim_date.year = 2013 AND
    dim_product.category IN ('Fresh fruit', 'Candy')
GROUP BY
    dim_date.weekday, dim_product.category;

对于大多数 OLTP 数据库（无论是关系模型还是文档模型），存储以面向行的方式布局：来自表的一行的所有值彼此相邻存储。对于上述查询，即使为特定键构建索引，仍然需要将所有行从磁盘加载到内存中（对于非内存数据库），进行解析并过滤出不符合所选条件的行，这样的操作较为消耗时间与空间。

为了应对上述问题，「面向列存储」（column-oriented storage）的想法被提出：不要将一行中的所有值存储在一起，而是将每列中的所有值存储在一起。如果每个列存储在一个单独的文件中，查询只需要读取和解析在该查询中使用的那些列。如下图所示：

列存储在关系数据模型中最容易理解，但它同样适用于非关系数据。需要注意，面向列的存储布局依赖一组列文件，每个文件以相同顺序保存着数据行。

3.1 列压缩

除了仅从磁盘中加载查询所需的列之外，还可以通过压缩数据来进一步降低对磁盘吞吐量的要求。对于列中不同的数据模式，可以采用不同的压缩技术，在数据仓库中特别有效的一种技术是「位图编码」（bitmap encoding），如下图所示：

通常，列中不同值的数量小于行数，我们可以将一个包含

个不同值的列转化为

个单独的位图，每个位图对应一个不同的值，其中的一个位对应为一行，如果行具有该值，则该位为 1，否则为 0（相当于把一列具体数值变成了一坨仅包含 0 或 1 的文件）。基于位图索引，我们可以方便地使用「按位」与或计算等方式来进行查询条件的执行。

另一方面，如果 n 非常小，上述这种每行对应一位的存储方式可能会包含很多 0（即较为稀疏），我们可以改为「游程编码」（run-length encoding）的方式，如上图的下半部分所示。

此外，除了减少需要从磁盘加载的数据量之外，面向列的存储布局也有利于高效利用 CPU 周期与内存带宽。列压缩使得列中更多的行可以加载到 L1 缓存，按位运算符可以直接对这样的列压缩数据块进行操作，这种技术被称为「矢量化处理」（vectorized processing）。

3.2 列存储中的排序

在列存储中，行的存储顺序并不太重要，但是需要一次排序整行，以保证可以正确维护列与列之间的关系。数据库管理员可以基于常见查询的知识来选择要排序表的列，以提升查询的速度。当第一列排序出现相同值时，可以指定第二列继续进行排序。

排序的另一个优点在于，它可以帮助进一步压缩列。如果主排序列上没有很多的值，那么在排序之后，其将出现一个非常长的序列，其中相同的值在一行中会连续重复多次，我们可以通过一个简单的游程编码，将一个包含数十亿行的表压缩到几千字节。一般来说，基于第一个排序键的压缩效果通常最好，第二个和第三个排序键会使情况更加负载，也通常不会有太多相邻的重复值。

另一方面，C-Store 提出了一种列存储的改进方式：同时存储不同方式排序的冗余数据，以便在处理查询时，可以选择最适合特定查询模式的排序版本。对于列存储来说，这与面向行存储中的多个二级索引类似，最大的区别在于，面向行的存储将每一行都保存在一个位置（在堆文件或聚集索引中），二级索引只包含匹配行的指针；而对于列存储，通常没有任何指向别处数据的指针，只有包含值的列。

3.3 列存储的写操作

面向列存储的缺点在于写入较为困难，类似 B-tree 使用的原地更新方式，对于压缩的列是不可能的，因为各行是由它们在列中的位置标识的，因此插入操作必须一致地更新所有列。

一种较好的列存储写入方案是参考 LSM-tree。所有的写入首先进入内存存储区，将其添加到已排序的结构中，接着再准备写入磁盘。内存中的存储可以是面向行或面向列（不重要），当积累了足够的写入时，它们将与磁盘上的列文件合并，并批量写入新文件。

执行查询时，需要检查磁盘上的列数据和内存中最近的写入，并结合这两者，而查询优化器可以对用户隐藏这些内部细节。

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

数据仓库的另一个值得一提的是「物化聚合」（materialized aggregates）。如前所述，数据仓库查询通常涉及各种聚合函数，如果许多不同查询使用相同的聚合，每次都处理原始数据将非常浪费，我们可以通过缓存查询最常适用的一些技术或总和，以减少查询时间。

创建这种缓存的一种方式是「物化视图」（materialized view）。与关系数据模型中的标准（模拟）视图不同，物化视图是查询结果的实际副本，并被写入到磁盘，而虚拟视图只是用于编写查询的快捷方式。当底层数据发生变化时，物化视图也需要随之更新，这种更新方式对于数据写入性能会有所影响，因此其通常对于大量读密集的数据仓库更有意义，在 OLTP 数据库中则不经常使用。

物化视图常见的一种特殊情况称为「数据立方体」（data cube）或 「OLAP 立方体」，它是由不同维度分组的聚合网格，如下图所示：

上图给出的例子包含了两个维度表的外键，每个轴代表一个维度，每个单元格即为不同维度组合的所有事实的属性，沿着每一行或列应用聚合操作，即可得到一个减少一个维度的总和。

物化数据立方体的优点在于某些查询会非常快，因为它们已经被预先计算出来；缺点则是缺乏像查询原始数据那样的灵活性。因此，大多数数据仓库都保留尽可能多的原始数据，仅当数据立方体可以对特定查询显著提升性能时，才会采用多维数据聚合。

4 小结

本章节简单介绍了数据库内部处理「存储」与「检索」的底层原理。概括来讲，存储引擎分为两大类：针对事务处理（OLTP）优化的架构，以及针对分析型（OLAP）的优化架构，它们典型的访问方式存在较大差异：

• 「OLTP 系统」通常面向用户，可能收到大量的请求。为了处理负载，应用程序通常在每个查询中只涉及少量的记录。应用程序基于某类键来请求记录，而存储引擎使用索引来查找所请求键的数据，磁盘寻道时间往往是瓶颈。
• 「OLAP 系统」（以数据仓库为代表）主要由业务分析师使用，处理的查询请求数目远低于 OLTP 系统，但每个查询通常要求非常苛刻，需要在短时间内扫描数百万条记录，磁盘带宽（而非寻道时间）通常是瓶颈，而面向列的存储对于这种工作负载逐渐成为流行的解决方案。

在 OLTP 方面，有两个主要流派的存储引擎：

• 「日志结构流派」。只允许追加式更新文件和删除过时的文件，但不会修改已写入的文件。BitCask、SSTables、LSM-tree、LevelDB、Cassandra、HBase、Lucene 等属于此类。
• 「原地更新流派」。将磁盘视为可以覆盖的一组固定大小的页，B-tree 是这一哲学的最典型代表，它已用于所有主要的关系数据库，以及大量的非关系数据库。

日志结构的存储引擎是一个相对较新的方案，其关键思想是系统地将磁盘上随机访问转为顺序写入，由于硬盘驱动器和 SSD 的功能特性，可以实现更高的写入吞吐量。此外，还有一些更复杂的索引结构，以及为全内存而以优化的数据库。

作为应用开发人员，掌握更多有关存储引擎内部的知识，可以更好地了解哪种工具最适合你的具体应用。如果还需要进一步调整数据库的可调参数，这些理解还可以帮助开发者正确评估调高或调低参数所带来的影响。

思维导图