第六章：设计一个键值存储 (Design A Key-Value Store)

键值存储，也称为键值数据库，是一种非关系型数据库。每个唯一标识符作为一个键存储，并与其相关的值进行关联。这个数据对被称为“键值对”。

在键值对中，键必须是唯一的，而与该键相关联的值可以通过键进行访问。键可以是明文或哈希值。出于性能原因，较短的键更为理想。那么，键是什么样子的呢？以下是几个示例：

明文键： “last_logged_in_at”
哈希键： 253DDEC4

键值对中的值可以是字符串、列表、对象等。在键值存储中，值通常被视为一个不透明对象，例如 Amazon Dynamo [1]、Memcached [2]、Redis [3] 等。

以下是键值存储中的数据片段：

表6-1

在本章中，你需要设计一个支持以下操作的键值存储：

put(key, value) // 插入与“key”相关联的“value”
get(key) // 获取与“key”相关联的“value”

理解问题并确定设计范围

没有完美的设计，每个设计都在读取、写入和内存使用的权衡中达成了特定的平衡。另一个需要权衡的因素是一致性和可用性之间的取舍。在本章中，我们将设计一个具有以下特征的键值存储系统：

键值对的大小较小：每个键值对小于 10 KB。
能够存储大数据。
高可用性：即使在系统故障期间，系统也能快速响应。
高扩展性：系统能够扩展以支持大型数据集。
自动扩展：服务器的添加和删除应根据流量自动进行。
可调一致性：可以根据需要调整系统的一致性级别。
低延迟：系统在处理操作时具有低延迟。

单服务器键值存储 (Single server key-value store)

开发一个驻留在单个服务器上的键值存储比较简单。一个直观的方法是将键值对存储在哈希表中，哈希表将所有内容保存在内存中。尽管内存访问速度快，但由于空间限制，将所有数据都放入内存中可能是不现实的。为了在单个服务器上容纳更多数据，可以进行以下两项优化：

数据压缩
仅将经常使用的数据存储在内存中，其他数据存储在磁盘上

即使有这些优化，单个服务器仍然很快会达到其容量极限。为了支持大数据，必须使用分布式键值存储。

分布式键值存储 (Distributed key-value store)

分布式键值存储也被称为分布式哈希表，它将键值对分布在多台服务器上。在设计分布式系统时，理解 CAP 定理（一致性、可用性、分区容忍）是非常重要的。

CAP 定理 (CAP theorem)

CAP 定理指出，分布式系统不可能同时提供以下三项保证中的两项以上：一致性、可用性和分区容忍。我们先定义一下这些概念：

一致性 (Consistency)：一致性意味着无论客户端连接到哪个节点，所有客户端都在同一时间看到相同的数据。
可用性 (Availability)：可用性意味着即使有些节点宕机，任何请求数据的客户端都能获得响应。
分区容忍 (Partition Tolerance)：分区指的是两个节点之间的通信中断。分区容忍意味着系统即使在网络分区的情况下仍能继续运行。

CAP 定理表明，必须牺牲三个属性中的一个才能支持另外两个属性，如图 6-1 所示。

图6-1

如今，键值存储根据它们支持的两种 CAP 特性进行分类：

CP 系统（一致性和分区容忍）：CP 键值存储支持一致性和分区容忍，但牺牲可用性。
AP 系统（可用性和分区容忍）：AP 键值存储支持可用性和分区容忍，但牺牲一致性。
CA 系统（一致性和可用性）：CA 键值存储支持一致性和可用性，但牺牲分区容忍。由于网络故障不可避免，分布式系统必须容忍网络分区。因此，CA 系统无法在实际应用中存在。

上述内容大多属于定义部分。为了更容易理解，让我们看一些具体示例。在分布式系统中，数据通常会被多次复制。假设数据被复制到三个副本节点 n1、n2 和 n3，如图 6-2 所示。

理想情况 (Ideal situation)

在理想的世界中，网络分区从未发生。写入 n1 的数据会自动复制到 n2 和 n3，既实现了一致性，也保证了可用性。

图6-2

现实中的分布式系统 (Real-world distributed systems)

在分布式系统中，网络分区是不可避免的。当分区发生时，必须在一致性和可用性之间做出选择。在图 6-3 中，节点 n3 出现故障，无法与节点 n1 和 n2 通信。如果客户端将数据写入 n1 或 n2，数据无法传播到 n3。如果数据写入 n3，但尚未传播到 n1 和 n2，则 n1 和 n2 将拥有过期数据。

图6-3

如果我们选择一致性优先于可用性（CP 系统），则必须阻止对 n1 和 n2 的所有写操作，以避免这三台服务器之间的数据不一致，这会导致系统不可用。银行系统通常对一致性有极高的要求。例如，对于银行系统来说，显示最新的余额信息至关重要。如果由于网络分区导致数据不一致，银行系统会在问题解决之前返回错误信息。

然而，如果我们选择可用性优先于一致性（AP 系统），即使系统可能返回过期数据，仍然会继续接受读取请求。对于写入操作，n1 和 n2 将继续接受写入请求，并在网络分区恢复后将数据同步到 n3。

选择适合用例的 CAP 保证是构建分布式键值存储的重要步骤。你可以与面试官讨论并根据需求设计系统。

系统组件 (System components)

在本节中，我们将讨论构建键值存储系统使用的核心组件和技术，包括：

数据分区
数据复制
一致性
不一致性解决
故障处理
系统架构图
写路径
读路径

以下内容主要基于三个流行的键值存储系统：Dynamo[4]、Cassandra[5] 和 BigTable[6]。

数据分区 (Data partition)

对于大型应用程序，将完整的数据集放入单个服务器是不现实的。最简单的解决方案是将数据拆分为较小的分区并存储在多台服务器上。在进行数据分区时面临的两个挑战是：

将数据均匀地分布在多台服务器上。
在添加或删除节点时，尽量减少数据移动。

在第 5 章讨论的一致性哈希是一种解决这些问题的优秀技术。让我们从高层次上重新回顾一致性哈希的工作原理：

首先，将服务器放置在哈希环上。在图 6-4 中，八台服务器（用 s0, s1, …, s7 表示）被放置在哈希环上。
接下来，将键哈希到同一哈希环上，并且它存储在顺时针方向上遇到的第一个服务器上。例如，key0 使用此逻辑存储在 s1。

图6-4

使用一致性哈希进行数据分区的优点

自动扩展：根据负载情况，服务器可以自动添加或移除。
异构性：每台服务器的虚拟节点数量与其容量成比例。例如，容量较大的服务器会分配更多的虚拟节点。

数据复制 (Data replication)

为了实现高可用性和可靠性，数据必须在 N 台服务器上进行异步复制，其中 N 是一个可配置参数。这些 N 台服务器的选择逻辑如下：当一个键被映射到哈希环上的某个位置时，从该位置开始，顺时针方向选择前 N 台服务器来存储数据副本。

在图 6-5 中（N = 3），key0 被复制到 s1、s2 和 s3 上。

图6-5

使用虚拟节点时，环上的前 N 个节点可能归属于少于 N 个物理服务器。为避免此问题，在执行顺时针遍历逻辑时，我们只选择唯一的服务器。

由于同一个数据中心的节点常常会因为停电、网络问题或自然灾害等原因同时失效，为了更好的可靠性，副本通常会放置在不同的数据中心，并通过高速网络连接这些数据中心。

一致性 (Consistency)

由于数据在多个节点上复制，因此需要在副本间保持数据同步。Quorum 共识机制可以保证读写操作的一致性。首先，我们需要定义几个参数：

N = 副本的数量。
W = 写入法定数量。要使写操作成功，必须从 W 个副本收到写入确认。
R = 读取法定数量。要使读取操作成功，必须从至少 R 个副本收到响应。

让我们通过图 6-6 中的例子来说明（假设 N = 3）。

图6-6

W = 1 并不意味着数据只写在一台服务器上。例如，在图 6-6 的配置中，数据会被复制到 s0、s1 和 s2。W = 1 意味着协调器（coordinator）必须收到至少一个副本的确认，才会认为写操作成功。例如，如果我们从 s1 收到确认，协调器就不需要再等待来自 s0 和 s2 的确认。协调器在客户端和存储节点之间起到代理的作用。

W、R 和 N 的配置是延迟（latency）与一致性（consistency）之间的典型权衡。如果 W = 1 或 R = 1，操作会很快返回结果，因为协调器只需要等待任意副本的响应。如果 W 或 R 大于 1，系统提供更好的一致性；然而，由于协调器需要等待最慢的副本响应，查询速度会变慢。

如果 W + R > N，系统可以保证强一致性，因为至少有一个副本会包含最新数据，确保数据一致性。

我们如何配置 N、W 和 R 以满足我们的使用需求呢？以下是一些可能的配置：

如果 R = 1 且 W = N，系统优化为快速读取。
如果 W = 1 且 R = N，系统优化为快速写入。
如果 W + R > N，系统可以保证强一致性（通常 N = 3，W = R = 2）。
如果 W + R <= N，系统不能保证强一致性。

根据需求，我们可以调整 W、R 和 N 的值，以达到所需的一致性水平。

一致性模型 (Consistency models)

在设计键值存储时，另一个重要的考虑因素是一致性模型。一致性模型定义了数据一致性的程度，存在广泛的可能一致性模型：

强一致性（Strong Consistency）：任何读取操作都会返回与最新写入结果一致的值。客户端永远不会看到过时的数据。
弱一致性（Weak Consistency）：后续的读取操作可能不会看到最新的值。
最终一致性（Eventual Consistency）：这是一种特定形式的弱一致性。经过足够长的时间，所有更新都会传播，最终所有副本达到一致。

通常，强一致性是通过强制一个副本在所有副本对当前写入达成一致之前，不接受新的读/写操作来实现的。然而，这种方法对于高度可用的系统并不理想，因为它可能会阻塞新的操作。Dynamo 和 Cassandra 采用的是最终一致性，这是我们为键值存储推荐的一致性模型。对于并发写入，最终一致性允许系统中存在不一致的值，并强制客户端读取这些值以进行调解。下一节将解释如何通过版本控制来处理调解。

不一致性解决：版本控制 (Inconsistency resolution: versioning)

复制可以提高系统的可用性，但会导致副本之间的不一致性。为了解决这个问题，通常使用版本控制和向量时钟。版本控制的意思是将每次数据修改视为数据的一个新的不可变版本。在讨论版本控制之前，我们可以先通过一个例子来说明不一致性是如何发生的：

如图 6-7 所示，副本节点 n1 和 n2 都有相同的值。我们称这个值为原始值。此时，服务器 1 和服务器 2 都会在执行 get("name") 操作时获得相同的值。

图6-7

接下来，如图 6-8 所示，服务器 1 将名字更改为 “johnSanFrancisco”，而服务器 2 将名字更改为 “johnNewYork”。这两个修改是同时进行的。现在，我们有了冲突的值，分别是版本 v1 和版本 v2。

图6-8

在这个例子中，原始值可以被忽略，因为修改是基于它进行的。然而，无法直接解决最后两个版本之间的冲突。为了解决这个问题，我们需要一个版本控制系统，能够检测冲突并进行冲突调解。向量时钟是一种常用的技术来解决这个问题。让我们来看一下向量时钟是如何工作的。

向量时钟是一个与数据项关联的 [服务器, 版本] 对，可以用来检查一个版本是先于、后于还是与其他版本冲突。

假设一个向量时钟表示为 D([S1, v1], [S2, v2], ... , [Sn, vn])，其中 D 是数据项，v1 是版本计数器，s1 是服务器编号。如果数据项 D 被写入服务器 Si，系统必须执行以下任务之一：

如果 [Si, vi] 存在，则增加 vi。
否则，创建一个新的条目 [Si, 1]。

上述抽象逻辑可以通过图 6-9 中的具体示例来解释。

图6-9

客户端向系统写入数据项 D1，该写入由服务器 Sx 处理，此时的向量时钟为 D1([Sx, 1])。
另一个客户端读取最新的 D1，将其更新为 D2，并写回。D2 继承自 D1，因此它会覆盖 D1。假设写入由同一服务器 Sx 处理，此时的向量时钟为 D2([Sx, 2])。
另一个客户端读取最新的 D2，将其更新为 D3，并写回。假设写入由服务器 Sy 处理，此时的向量时钟为 D3([Sx, 2], [Sy, 1])。
另一个客户端读取最新的 D2，将其更新为 D4，并写回。假设写入由服务器 Sz 处理，此时的向量时钟为 D4([Sx, 2], [Sz, 1])。
当另一个客户端读取 D3 和 D4 时，发现发生了冲突，这种冲突是由于数据项 D2 被 Sy 和 Sz 都进行了修改。冲突由客户端解决，更新后的数据被发送回服务器。假设写入由 Sx 处理，此时的向量时钟为 D5([Sx, 3], [Sy, 1], [Sz, 1])。我们将稍后解释如何检测冲突。

使用向量时钟，可以很容易地判断版本 X 是版本 Y 的祖先（即没有冲突），如果 Y 的向量时钟中每个参与者的版本计数器都大于或等于 X 中的计数器。例如，向量时钟 D([s0, 1], [s1, 1]) 是 D([s0, 1], [s1, 2]) 的祖先，因此没有记录冲突。

同样，如果 Y 的向量时钟中有任何参与者的计数器小于其对应的 X 的计数器，则可以判断版本 X 是版本 Y 的兄弟（即存在冲突）。例如，以下两个向量时钟表示存在冲突：D([s0, 1], [s1, 2]) 和 D([s0, 2], [s1, 1])。

尽管向量时钟可以解决冲突，但也有两个显著的缺点。首先，向量时钟为客户端增加了复杂性，因为客户端需要实现冲突解决逻辑。

其次，向量时钟中的 [服务器: 版本] 对可能会迅速增长。为了解决这个问题，我们设定一个长度阈值，如果超过该限制，将移除最旧的对。这可能会导致在和解时的低效率，因为后代关系无法被准确确定。然而，根据 Dynamo 论文的描述 [4]，亚马逊在生产中尚未遇到这个问题；因此，对于大多数公司来说，这可能是一个可以接受的解决方案。

处理故障 (Handling failures)

在任何大规模系统中，故障不仅是不可避免的，而且是常见的。因此，处理故障场景非常重要。在本节中，我们首先介绍检测故障的技术。然后，我们讨论常见的故障解决策略。

故障检测 (Failure detection)

在分布式系统中，单靠另一个服务器的说法不足以判断某个服务器是否宕机。通常，标记一个服务器为宕机至少需要两个独立的信息来源。

如图 6-10 所示，全对全多播是一种简单的解决方案。然而，当系统中有许多服务器时，这种方法效率较低。

图6-10

更好的解决方案是使用去中心化的故障检测方法，例如八卦协议（Gossip Protocol）。八卦协议的工作原理如下：

每个节点维护一个节点成员列表，其中包含成员 ID 和心跳计数器。
每个节点定期递增其心跳计数器。
每个节点定期向一组随机节点发送心跳信号，这些节点又将信号传播给其他节点。
一旦节点接收到心跳信号，成员列表将更新为最新信息。
如果心跳在预定义的时间段内没有增加，则该成员将被视为离线。

图6-11

如图 6-11 所示：

节点 s0 维护一个节点成员列表，如左侧所示。
节点 s0 注意到节点 s2（成员 ID = 2）的心跳计数器长时间没有增加。
节点 s0 将包含 s2 信息的心跳信号发送给一组随机节点。一旦其他节点确认 s2 的心跳计数器长时间没有更新，s2 将被标记为下线，该信息将传播给其他节点。

处理临时故障 (Handling temporary failures)

通过八卦协议检测到故障后，系统需要部署某些机制以确保可用性。在严格的仲裁方法中，读写操作可能会被阻塞，如仲裁共识部分所示。

为了提高可用性，采用了一种称为“松散仲裁（sloppy quorum）”的技术 [4]。系统不是强制执行仲裁要求，而是选择哈希环上前 W 个健康服务器进行写入，前 R 个健康服务器进行读取。离线服务器会被忽略。

如果由于网络或服务器故障导致某个服务器不可用，另一台服务器将临时处理请求。当故障服务器重新上线时，将推送更改以实现数据一致性。这个过程被称为“提示交接（hinted handoff）”。由于图 6-12 中的 s2 不可用，读取和写入将由 s3 临时处理。当 s2 重新上线时，s3 会将数据交回给 s2。

图6-12

处理永久故障 (Handling permanent failures)

提示交接（hinted handoff）用于处理临时故障。那么如果某个副本永久不可用该如何处理呢？为了解决这种情况，我们实现了一种**反熵协议（anti-entropy protocol）**来保持副本之间的同步。反熵涉及比较每个副本上的每个数据块，并将每个副本更新为最新版本。Merkle 树被用于不一致性检测并最小化传输的数据量。

引用自维基百科 [7]：“哈希树或 Merkle 树是一种树形结构，其中每个非叶子节点的标签是其子节点标签或值（在叶子节点情况下）的哈希值。哈希树允许高效和安全地验证大数据结构的内容。”

假设键空间从 1 到 12，以下步骤展示如何构建一个 Merkle 树。高亮的框表示不一致性。

第 1 步：将键空间分为桶（在本例中为 4 个），如图 6-13 所示。每个桶用作根级节点，以保持树的深度有限。

图6-13

第 2 步：一旦桶创建完成，使用均匀哈希方法对每个桶中的键进行哈希处理（如图 6-14 所示）。

图6-14

第 3 步：为每个桶创建一个单独的哈希节点（如图 6-15 所示）。

图6-15

第 4 步：通过计算子节点的哈希值向上构建树，直到根节点（如图 6-16 所示）。

图6-16

比较两个 Merkle 树，首先比较根哈希值。如果根哈希匹配，则两个服务器的数据相同。如果根哈希不一致，则比较左子节点的哈希值，然后比较右子节点的哈希值。可以遍历树结构，找出哪些桶不同步，并仅同步这些桶。

使用 Merkle 树，同步所需的数据量与两个副本之间的差异成正比，而不是与它们包含的数据总量成正比。在现实世界的系统中，桶的大小通常很大。例如，一个可能的配置是每十亿个键有一百万个桶，因此每个桶只包含 1000 个键。

处理数据中心故障 (Handling data center outage)

数据中心故障可能由于电力故障、网络故障、自然灾害等原因发生。为了构建一个能够应对数据中心故障的系统，重要的是在多个数据中心之间复制数据。即使某个数据中心完全离线，用户仍然可以通过其他数据中心访问数据。

系统架构图 (System architecture diagram)

现在我们已经讨论了设计键值存储的不同技术考虑因素，可以将重点转向架构图，如图 6-17 所示。架构的主要特点如下：

图6-17

客户端通过简单的 API 与键值存储进行通信：get(key) 和 put(key, value)。
协调器是充当客户端与键值存储之间代理的节点。
节点使用一致性哈希分布在一个环上。
系统完全去中心化，因此添加和移动节点可以是自动的。
数据在多个节点上进行复制。
每个节点都有相同的职责，因此没有单点故障。

由于设计是去中心化的，每个节点执行多种任务，如图 6-18 所示。

图6-18

写入路径 (Write path)

图 6-19 解释了写请求被定向到特定节点后发生的事情。请注意，写/读路径的提议设计主要基于 Cassandra 的架构 [8]。

图6-19

写请求会被持久化到提交日志文件中。
数据会被保存在内存缓存中。
当内存缓存满或达到预定义阈值时，数据会被刷新到磁盘上的 SSTable [9]。注意：有序字符串表 (SSTable) 是一组排序的 <key, value> 对。对于对 SSTable 感兴趣的读者，请参考参考材料 [9]。

读取路径 (Read path)

在读取请求被定向到特定节点后，首先检查数据是否在内存缓存中。如果数据存在，则如图 6-20 所示，数据会返回给客户端。

图6-20

如果数据不在内存中，则需要从磁盘检索数据。我们需要一种有效的方法来查找哪个 SSTable 包含该键。布隆过滤器 [10] 通常用于解决这个问题。

当数据不在内存中时，读取路径如图 6-21 所示：

图6-21

系统首先检查数据是否在内存中。如果不在，则进入第 2 步。
如果数据不在内存中，系统检查布隆过滤器。
布隆过滤器用于确定哪些 SSTable 可能包含该键。
SSTable 返回数据集的结果。
数据集的结果返回给客户端。

总结

本章涵盖了许多概念和技术。为了帮助您回顾，以下表格总结了分布式键值存储所使用的特性和相应的技术。

特性	技术
数据分区	一致性哈希
数据复制	异步复制
一致性	读写法定，强一致性与最终一致性
不一致性解决	版本控制，向量时钟
故障处理	故障检测（八卦协议），临时故障与永久故障处理
数据中心故障处理	数据跨多个数据中心复制
系统架构	去中心化设计，协调器作为客户端与存储之间的代理
写路径	提交日志，内存缓存，SSTable写入
读取路径	内存缓存检查，布隆过滤器，SSTable查找