6. Design A Key-value Store #

设计键值存储系统

键值存储是一种非关系型数据库。每个唯一的标识符都以键(key)的形式存储，并关联一个值。键必须是唯一的，可以是纯文本或哈希值。从性能角度来看，短键效果更好。

键示例：

• 纯文本 - “last_logged_in_at”
• 哈希键 - 253DDEC4

我们现在要设计一个支持以下操作的键值存储：

• put(key, value) - 插入与 key 关联的 value。
• get(key) - 获取与 key 关联的 value。

值(value)可以是字符串、列表、对象等。

6.1 理解问题并确定设计范围 #

世上没有完美的设计：

• 在读/写性能和内存使用之间总是需要进行权衡。
• 另一个权衡是在一致性和可用性之间。

以下是我们努力实现的目标特性：

• 每个键值对大小较小 - 小于10kb
• 需要能够存储大量数据。
• 高可用性 - 系统即使在发生故障时也能快速响应。
• 高可扩展性 - 系统可以扩展以支持大型数据集。
• 自动扩展 - 服务器的添加/删除应根据流量自动进行。
• 可调节的一致性。
• 低延时。

6.2 单服务器键值存储 #

单服务器键值存储很容易开发。我们可以只维护一个存储键值对的内存哈希表。然而，内存可能成为瓶颈，因为我们无法将所有内容都放入内存。以下是我们扩展的选项：

• 数据压缩
• 仅将频繁使用的数据存储在内存中。其余的存储在磁盘上。

即使进行了这些优化，单台服务器也可能很快达到其容量上限。

6.3 分布式键值存储 #

分布式键值存储由一个分布式哈希表组成，该表将键分布在多个节点上。在开发分布式数据存储时，我们需要考虑CAP定理。

6.3.1 CAP定理 #

该定理指出，一个分布式系统最多只能同时满足下面三个特性中的两个:

• 一致性 (Consistency): 所有客户端在同一时间看到同样的数据，无论客户端连接到哪个节点
• 可用性 (Availability): 即使有节点发生故障，任意客户端发出的请求都能被响应
• 分区容错性 (Partition tolerance): 网络分区意味着集群中并非所有节点都能通信。分区容错性意味着即使在这种情况下，系统也能正常运行。

图6.1:

• CP（一致性和分区容错性）系统：支持一致性和分区容错性，但牺牲了可用性。
• AP（可用性和分区容错性）系统：支持可用性和分区容错性，但牺牲了一致性。
• CA（一致性和可用性）系统：支持一致性和可用性，但牺牲了分区容错性。
  • 一个同时支持一致性和可用性的分布式系统在现实世界中是不可能存在的，因为网络故障是不可避免的。因此，在现实世界中CA系统不可能存在。

理想情况下的分布式数据存储示例:

图6.2：理想的场景。在理想世界中，网络分区永远不会发生。写入节点 n1 的数据会自动复制到 n2 和 n3。一致性和可用性都得以实现。

图6.3: 真实世界的分布式系统。在分布式系统中，分区是无法避免的，当分区发生时，我们必须在一致性和可用性之间做出选择。在本图，n3宕机，无法与n1和n2通信。如果客户端向n1或n2写入数据，数据就无法传播到n3。如果数据写入了n3但尚未传播到n1和n2，那么n1和n2将拥有过时的数据。

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

然而，如果我们选择可用性而不是一致性(AP系统)，系统会继续接受读取，即使它可能返回过时的数据。对于写入，n1和n2将继续接受写入，并且当网络分区解决后，数据将同步到n3。

选择CP还是AP是构建分布式键值存储的重要一步，你可以与面试官讨论这一点，并据此设计系统。每种选择都有不同的权衡。

6.3.2 系统组件 #

本节将介绍构建分布式键值存储所需的关键组件。

数据分区(Data partition) #

对于足够大的数据集，将其维护在单个服务器上是不可行的。因此，我们可以将数据分割成更小的分区，并将它们分布在多个节点上。

接下来的挑战是如何均匀地分布数据，并在集群调整大小时最大限度地减少数据移动。

这两个问题都可以使用一致性哈希（在«5. Design Consistent Hashing»中讨论过）来解决：

• 服务器被放置在一个哈希环上
• 键被哈希，并放置在顺时针方向最近的服务器上

使用一致性哈希来进行数据分区有如下好处。

• 自动伸缩：可以基于负载自动添加和移除服务器。
• 异质性：服务器的虚拟节点数量可以与服务器的性能成比例。例如，可以为性能高的服务器分配更多的虚拟节点。

数据复制(Data replication) #

为了实现高可用性和可靠性，数据必须在N个服务器上进行异步复制，其中N是一个可配置的参数。这N个服务器使用以下逻辑选择：在将一个键映射到哈希环上的一个位置后，从该位置顺时针行走，并选择环上的前N个服务器来存储数据副本。

图6.5: N=3时，key0在s1、s2和s3上进行复制

使用虚拟节点时，环上的前N个节点可能由少于N个物理服务器拥有。为了避免这个问题，我们在执行顺时针行走逻辑时只选择唯一的服务器。

同一数据中心内的节点经常由于停电、网络问题、自然灾害等原因同时发生故障。为了获得更好的可靠性，副本被放置在不同的数据中心，并且数据中心通过高速网络连接。

一致性(Consistency) #

由于数据在多个节点上复制，因此必须在副本之间进行同步。

法定人数共识(Quorum consensus)可以保证读写操作的一致性：

• N - 副本数量
• W - 写法定人数。写操作必须得到W个节点的确认。
• R - 读法定人数。读操作必须得到R个节点的确认。

图6.6

W = 1 并不意味着数据只写入一个服务器。例如，使用图6.6中的配置，数据在 s0、s1 和 s2 上复制。W = 1 意味着协调器必须在写操作被视为成功之前至少收到一个确认。例如，如果我们收到来自 s1 的确认，我们就不再需要等待来自 s0 和 s2 的确认。协调器充当客户端和节点之间的代理。

W、R 和 N 的配置是延迟和一致性之间典型的权衡。如果 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 的值以达到所需的一致性级别。

一致性模型 #

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

• 强一致性： 任何读取操作都返回与最新写入数据项的结果相对应的值。客户端永远不会看到过时的数据。
• 弱一致性： 后续的读取操作可能看不到最新的值。
• 最终一致性： 这是弱一致性的一种特定形式。给定足够的时间，所有更新都会传播，并且所有副本都保持一致。

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

不一致性解决(Inconsistency Resolution) #

复制提供了高可用性，但会导致副本之间的数据不一致。

不一致的例子：

图6.8

这种不一致可以使用使用向量时钟的版本控制系统来解决。向量时钟是一个与数据项关联的[服务器，版本]对。每次在服务器中更改数据项时，其关联的向量时钟都会更改为[server_id, curr_version+1]。

不一致性解决示例：

图6.9

• 客户端写入D1，由Sx处理，Sx写入版本[Sx, 1]
• 另一个客户端读取D1，更新它，Sx将版本递增到[Sx, 2]
• 客户端在Sy中基于D2写入D3 -> D3([Sx, 2],[Sy, 1])。
• 同时，另一个客户端在Sz中写入D4 -> D4([Sx, 2],[Sz, 1])
• 客户端读取D3和D4并检测到冲突。它进行解析并在Sx中添加更新后的版本 -> D5([Sx, 3],[Sy, 1],[Sz, 1])

通过检查一个版本是否是另一个版本的祖先来检测冲突。这可以通过验证所有版本戳是否小于或等于另一个版本来完成。

• [s0, 1],[s1, 1] 是[s0, 1],[s1, 2] 的祖先 -> 没有冲突。
• [s0, 1]不是[s1, 1]的祖先 -> 需要解决冲突。

这种冲突解决技术存在权衡：

• 由于客户端需要解决冲突，因此客户端复杂性增加。
• 向量时钟中的[服务器, 版本]对会快速增长，从而增加每个键值对的内存占用。为了解决这个问题，我们为长度设置了一个阈值，如果超过限制，则删除最旧的对。这可能会导致协调效率低下，因为无法准确确定后代关系。但是，根据Dynamo的论文，亚马逊尚未在生产中遇到此问题；因此，对于大多数公司来说，这可能是一个可以接受的解决方案。

处理故障(Handling Failures) #

在足够大的规模下，故障是不可避免的。确定你的错误检测和解决策略非常重要。

故障探测

在一个分布式系统中，仅仅因为你无法访问某个服务器就断定它宕机是不够的。你至少需要另一个信息来源。

一种方法是使用全对多广播(all-to-all multi-casting)。但是，当系统中存在大量服务器时，这种方法效率低下。

图6.10

一个更好的解决方案是使用分散式故障检测方法，例如gossip protocol。

一个更好的解决方案是使用分散式故障检测方法，例如gossip协议的工作方式如下：

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

图6.11

在上述场景中，s0检测到s2宕机，因为长时间没有收到心跳。它将该信息传播给其他节点，其他节点也验证了心跳没有更新。因此，s2被标记为离线。

处理临时故障

一个提高故障情况下可用性的小技巧是hinted handoff(暗示性传递)。

它的意思是，如果一个服务器暂时离线，你可以提升另一个健康的服务器来临时处理数据。在该服务器恢复在线后，数据和控制权将交还给它。

处理永久性故障

如果某个副本永久不可用，我们会实施反熵协议((Anti-entropy Protocol)以保持副本同步。

这是通过利用默克尔树(Merkle tree)来实现的，目的是最大限度地减少传输和比较的数据量。

默克尔树的工作方式是构建一个哈希树，其中叶子节点是键值对的桶(buckets)。

如果两个副本中的任何一个桶不同，那么默克尔树的哈希值将一直到根都不同：

图6.16

使用默克尔树，两个副本将只比较它们之间不同的数据，而不是比较整个数据集。

要比较两棵默克尔树，首先比较根哈希。如果根哈希匹配，则两个服务器拥有相同的数据。如果根哈希不一致，则比较左子哈希，然后比较右子哈希。您可以遍历树以查找哪些桶未同步，并仅同步这些桶。

使用默克尔树，需要同步的数据量与两个副本之间的差异成正比，而不是与它们包含的数据量成正比。在实际系统中，桶的大小相当大。例如，一种可能的配置是每十亿个键有一百万个桶，因此每个桶仅包含 1000 个键。

处理数据中心中断

数据中心中断可能是由于自然灾害或严重的硬件故障造成的。

为了确保弹性，请确保您的数据在多个数据中心之间进行复制。

系统架构图(System Architecture Diagram）) #

图6.17

主要特性：

• 客户端通过一个简单的 API 与键值存储进行通信
• 协调器是客户端和键值存储之间的代理
• 节点使用一致性哈希分布在环上
• 系统是去中心化的，因此支持添加和删除节点，并且可以自动化
• 数据在多个节点上复制
• 没有单点故障

每个节点负责的一些任务：

图6.18

写入路径(Write Path) #

图6.19

• 写请求持久化在提交日志中。
• 数据保存在内存缓存中。
• 当内存缓存已满或达到给定阈值时，数据将刷新到磁盘上的SSTable。

SSTable即Sorted String Table(排序字符串表)。保存键值对的排序列表。

读取路径(Read Path) #

图6.20: 当数据在内存中时的读取路径：

图6.21: 当数据在不内存中时的读取路径：

• 如果数据在内存中，则从内存中获取。否则，在 SSTable 中查找。
• 布隆过滤器用于在 SSTable 中进行高效查找。
• SSTables返回结果数据，然后将其返回给客户端。

6.4 总结 #

我们涵盖了很多概念和技术，以下是总结：