『数据密集型应用系统设计』读书笔记(三)

一个数据库在最基础的层次上需要完成两件事情: 当你把数据交给数据库时，它应当把数据存储起来；而后当你向数据库要数据时，它应当把数据返回给你。
上一章，我们讨论了数据模型和查询语言，即将数据录入数据库的格式，以及再次返回数据的机制。在本章中我们会从数据库的视角来讨论同样的问题: 数据库如何存储我们提供的数据，以及如何在我们需要时重新找到数据。

我们将研究两大类存储引擎: 日志结构(log-structured)的存储引擎，以及面向页面(page-oriented)的存储引擎(例如 B 树)。

存储与检索

驱动数据库的数据结构

最简单的数据库可以用两个 Bash 函数实现:

#!/bin/bash
db_set () {
  echo "$1,$2" >> database
}

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

这两个函数实现了键值存储的功能。执行 db_set key value 会将键(key)和值(value)存储在数据库中。

$ 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 的调用都会向文件末尾追加记录，所以更新键的时候旧版本的值不会被覆盖。

db_set 函数对于极其简单的场景其实有非常好的性能，因为在文件尾部追加写入通常是非常高效的。与 db_set 做的事情类似，许多数据库在内部使用了日志(log)，也就是一个仅追加(append-only)的数据文件。真正的数据库有更多的问题需要处理，但基本原理是一样的。

另一方面，如果这个数据库中有着大量记录，则这个 db_get 函数的性能会非常糟糕。每次你想查找一个键时，db_get 必须从头到尾扫描整个数据库文件来查找键。

为了高效查找数据库中特定键的值，我们需要一个数据结构: 索引(index)。索引背后的大致思想是通过保存一些额外的元数据作为路标来帮助你找到想要的数据。

索引是从主数据衍生的额外的(additional)结构。许多数据库允许添加与删除索引，这不会影响数据的内容，只会影响查询的性能。维护额外的结构会产生开销，特别是在写入时。写入性能很难超过简单地追加写入文件，因为追加写入是最简单的写入操作。任何类型的索引通常都会减慢写入速度，因为每次写入数据时都需要更新索引。

这是存储系统中一个重要的权衡: 精心选择的索引加快了读查询的速度，但是会拖慢写入速度。我们应当选择那些能为应用带来最大收益而且又不会引入超出必要开销的索引。

散列索引

我们从键值数据(key-value Data)的索引开始介绍。

散列索引是最简单的索引策略就是: 保留一个内存中的散列映射，其中每个键都映射到数据文件中的一个字节偏移量，指明了可以找到对应值的位置。当你将新的键值对追加写入文件中时，要更新散列映射，以反映刚刚写入的数据的偏移量。当想查找一个值时，使用散列映射来查找数据文件中的偏移量，寻找(seek)该位置并读取该值即可。

以如何避免最终用完硬盘空间？一种好的解决方案是，将日志分为特定大小的段(segment)，当日志增长到特定尺寸时关闭当前段文件，并开始写入一个新的段文件。然后，我们就可以对这些段进行压缩(compaction)。

散列索引虽然简单，但也有其局限性:

散列表必须能放进内存
范围查询效率不高

SSTables 和 LSM 树

在散列索引中，每个日志结构存储段都是一系列键值对。这些键值对按照它们写入的顺序排列，日志中稍后的值优先于日志中较早的相同键的值。除此之外，文件中键值对的顺序并不重要。

现在我们可以对段文件的格式做一个简单的改变: 要求键值对的序列按键排序。我们把这个格式称为排序字符串表(Sorted String Table)，简称 SSTable。我们还要求每个键只在每个合并的段文件中出现一次。

如何让你的数据能够预先排好序呢？虽然在硬盘上维护有序结构也是可能的，但在内存保存则要容易得多。有许多可以使用的众所周知的树形数据结构，例如红黑树或 AVL 树。使用这些数据结构，你可以按任何顺序插入键，并按排序顺序读取它们。

现在我们可以让我们的存储引擎以如下方式工作:

有新写入时，将其添加到内存中的平衡树数据结构，这个内存树有时被称为内存表(memtable)
当内存表大于某个阈值(通常为几兆字节)时，将其作为 SSTable 文件写入硬盘。这可以高效地完成，因为树已经维护了按键排序的键值对
收到读取请求时，首先尝试在内存表中找到对应的键，如果没有就在最近的硬盘段中寻找，如果还没有就在下一个较旧的段中继续寻找
在后台运行一个合并和压缩过程，以合并段文件并将已覆盖或已删除的值丢弃掉

上述操作只会遇到一个问题: 如果数据库崩溃，则最近的写入(在内存表中，但尚未写入硬盘)将丢失。为了避免这个问题，我们可以在硬盘上保存一个单独的日志，每个写入都会立即被追加到这个日志上，就像在前面的章节中所描述的那样。这个日志没有按排序顺序，但这并不重要，因为它的唯一目的是在崩溃后恢复内存表。

Google 的 Bigtable 论文最先引入了术语 SSTable 和 memtable。

最初这种索引结构是由 Patrick O’Neil 等人描述的，被命名为日志结构合并树(LSM 树)，它是基于更早之前的日志结构文件系统来构建的。基于这种合并和压缩排序文件原理的存储引擎通常被称为 LSM 存储引擎。

性能优化

当查找数据库中不存在的键时，LSM 树算法可能会很慢: 你必须先检查内存表，然后查看从最近的到最旧的所有的段，然后才能确定这个键不存在。
为了优化这种访问，存储引擎通常使用额外的布隆过滤器(Bloom filters)。布隆过滤器是用于近似集合内容的高效内存数据结构，它可以告诉你数据库中是不是不存在某个键，从而为不存在的键节省掉许多不必要的硬盘读取操作。

B 树

从 1970 年被引入至今，B 树很好地经受了时间的考验。在几乎所有的关系数据库中，它们仍然是标准的索引实现，许多非关系数据库也会使用到 B 树。

像 SSTables 一样，B 树保持按键排序的键值对，这允许高效的键值查找和范围查询。

前面提到，日志结构索引将数据库分解为可变大小的段，通常是几兆字节或更大的大小，并且总是按顺序写入段。相比之下，B 树将数据库分解成固定大小的块(block)或页面(page)，传统上大小为 4KB，并且一次只能读取或写入一个页面。
每个页面都可以使用地址或位置来标识，这允许一个页面引用另一个页面 —— 类似于指针，但其实现在硬盘而不是在内存中。我们可以使用这些页面引用来构建一个页面树。

一个页面会被指定为 B 树的根；在索引中查找一个键时，就从这里开始。该页面包含几个键和对子页面的引用。每个子页面负责一段连续范围的键，引用之间的键，指明了引用子页面的键范围。
如上如所示，我们正在寻找键 251 ，所以我们知道我们需要跟踪边界 200 和 300 之间的页面引用。这将我们带到一个类似的页面，进一步将 200 到 300 的范围拆分到子范围。
最终，我们将到达某个包含单个键的页面(叶子页面，leaf page)，该页面或者直接包含每个键的值，或者包含了对可以找到值的页面的引用。

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

如果要更新现有键的值，需要搜索包含该键的叶子页面，更改该页面中的值，并将该页面写回到硬盘(对该页面的任何引用都将保持有效)。
如果要添加一个新的键，需要找到其范围能包含新键的页面，并将其添加到该页面。如果页面中没有足够的可用空间容纳新键，则将其分成两个半满页面，并更新父页面以反映新的键范围分区，如下图所示:

这个算法可以确保树保持平衡:
具有 n 个键的 B 树总是具有 O(logn) 的深度。大多数数据库可以放入一个三到四层的 B 树，所以你不需要追踪多个页面引用来找到你正在查找的页面。分支因子为 500 的 4KB 页面的四层树可以存储多达 256TB 的数据。

让 B 树更可靠

为了使数据库能处理异常崩溃的场景，B 树实现通常会带有一个额外的硬盘数据结构:
预写式日志(WAL，即 write-ahead log，也称为重做日志，即 redo log)。这是一个仅追加的文件，每个 B 树的修改在其能被应用到树本身的页面之前都必须先写入到该文件。

另外还有一个更新页面的复杂情况是，如果多个线程要同时访问 B 树，则需要仔细的并发控制 —— 否则线程可能会看到树处于不一致的状态。这通常是通过使用锁存器(latches)保护树的数据结构来完成。

其他索引结构

到目前为止，我们只讨论了键值索引，它们就像关系模型中的主键(primary key)索引。次级索引(secondary indexes)也很常见。
在关系数据库中，你可以使用 CREATE INDEX 命令在同一个表上创建多个次级索引，而且这些索引通常对于有效地执行联接(join)而言至关重要。B 树和日志结构索引都可以用作次级索引。

将值存储在索引中

索引中的键是查询要搜索的内容，而其值可以是以下两种情况之一:

实际的行(文档，顶点)
对存储在别处的行的引用

对于第二种情况，行被存储的地方被称为堆文件(heap file)，并且存储的数据没有特定的顺序。堆文件方法很常见，因为它避免了在存在多个次级索引时对数据的复制: 每个索引只引用堆文件中的一个位置，实际的数据都保存在一个地方。

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

在聚集索引(在索引中存储所有的行数据)和非聚集索引(仅在索引中存储对数据的引用)之间的折衷方案被称为覆盖索引(covering index)。允许通过单独使用索引来处理一些查询。这种情况叫做: 索引覆盖(cover)了查询。

聚集索引和覆盖索引可以加快读取速度，但是它们需要额外的存储空间，并且会增加写入开销。

全文搜索和模糊索引

到目前为止所讨论的所有索引都假定你有确切的数据，并允许你查询键的确切值或具有排序顺序的键的值范围。他们不允许你做的是搜索类似的键，如拼写错误的单词。这种模糊的查询需要不同的技术。其他的模糊搜索技术正朝着文档分类和机器学习的方向发展，在此不再赘述。

在内存中存储一切

与内存相比，硬盘处理起来很麻烦。对于磁性硬盘和固态硬盘，如果要在读取和写入时获得良好性能，则需要仔细地布置硬盘上的数据。
但是硬盘有两个显著的优点:

持久的(内容在电源关闭时不会丢失)
每 GB 的成本比 RAM 低

随着 RAM 变得更便宜，成本已不再是数据库选择的最重要因素。而且许多数据集不是那么大，所以将它们全部保存在内存中是非常可行的。这导致了内存数据库的发展。

某些内存中的键值存储(如 Memcached)仅用于缓存，在重新启动计算机时丢失的数据是可以接受的。但其他内存数据库的目标是持久性，可以通过特殊的硬件来实现，也可以将更改日志写入硬盘。例如 Redis 就通过异步写入硬盘提供了较弱的持久性。

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

事务处理还是分析

在早期的业务数据处理过程中，一次典型的数据库写入通常与一笔商业交易(commercial transaction)相对应。但随着数据库开始应用到那些不涉及到钱的领域，术语交易/事务(transaction)仍留了下来，用于指代一组读写操作构成的逻辑单元。

应用程序通常使用索引通过某个键查找少量记录。根据用户的输入插入或更新记录。由于这些应用程序是交互式的，这种访问模式被称为在线事务处理(OLTP, OnLine Transaction Processing)。

但是，数据库也开始越来越多地用于数据分析，这些数据分析具有非常不同的访问模式。通常，分析查询需要扫描大量记录，每个记录只读取几列，并计算汇总统计信息(如计数、总和或平均值)，而不是将原始数据返回给用户。为了将这种使用数据库的模式和事务处理区分开，它被称为在线分析处理(OLAP, OnLine Analytice Processing)。

起初，事务处理和分析查询使用了相同的数据库。在二十世纪八十年代末和九十年代初期，企业有停止使用 OLTP 系统进行分析的趋势，转而在单独的数据库上运行分析。这个单独的数据库被称为数据仓库(data warehouse)。

数据仓库

OLTP 系统往往对业务运作至关重要，因而通常会要求”高可用”与”低延迟”。通常不愿意让业务分析人员在 OLTP 数据库上运行临时的分析查询。相比之下，数据仓库是一个独立的数据库，分析人员可以查询他们想要的内容而不影响 OLTP 操作。

数据仓库包含公司各种 OLTP 系统中所有的只读数据副本。从 OLTP 数据库中提取数据(使用定期的数据转储或连续的更新流)，转换成适合分析的模式，清理并加载到数据仓库中。

将数据存入仓库的过程称为抽取-转换-加载(ETL)。

在典型的数据仓库中，表格通常非常宽: 事实表通常有 100 列以上，有时甚至有数百列。维度表也可以是非常宽的，因为它们包括了所有可能与分析相关的元数据。

列式存储

如果事实表中有万亿行和数 PB 的数据，那么高效地存储和查询它们就成为一个具有挑战性的问题。维度表通常要小得多，所以在本节中我们将主要关注事实表的存储。

尽管事实表通常超过 100 列，但典型的数据仓库查询一次只会访问其中 4 个或 5 个列。列式存储背后的想法很简单: 不要将所有来自一行的值存储在一起，而是将来自每一列的所有值存储在一起。如果每个列式存储在一个单独的文件中，查询只需要读取和解析查询中使用的那些列，这可以节省大量的工作。
列式存储布局依赖于每个列文件包含相同顺序的行。因此，如果你需要重新组装完整的行，你可以从每个单独的列文件中获取第 23 项，并将它们放在一起形成表的第 23 行。

列压缩

除了仅从硬盘加载查询所需的列以外，我们还可以通过压缩数据来进一步降低对硬盘吞吐量的需求。幸运的是，列式存储通常很适合压缩。

数据立方体和物化视图

并不是每个数据仓库都必定是一个列式存储: 传统的面向行的数据库和其他一些架构也被使用。然而，列式存储可以显著加快专门的分析查询。

数据仓库的另一个值得一提的方面是物化汇总(materialized aggregates)。如前所述，数据仓库查询通常涉及一个聚合函数，如 SQL 中的 COUNT、SUM、AVG、MIN 或 MAX。如果相同的聚合被许多不同的查询使用，则可以将一些查询使用最频繁的计数或总和缓存起来。创建这种缓存的一种方式是物化视图(Materialized View)。在关系数据模型中，它通常被定义为一个标准(虚拟)视图。不同的是，物化视图是查询结果的实际副本，会被写入硬盘，而虚拟视图只是编写查询的一个捷径。

当底层数据发生变化时，物化视图需要更新，因为它是数据的非规范化副本。数据库可以自动完成该操作，但是这样的更新使得写入成本更高，这就是在 OLTP 数据库中不经常使用物化视图的原因。

物化视图的常见特例称为数据立方体或 OLAP 立方。它是按不同维度分组的聚合网格。