系统设计：设计一个key-value存储（06）

Published: at 19:45:44

键值存储，也称为键值数据库，是一种非关系数据库。每个唯一标识符都存储为一个键及其关联值，这种数据配对称为“键值”对。

在键值对中，键必须是唯一的，通过键可以访问与键关联的值。键可以是纯文本或散列值。出于性能原因，短键效果更好。键是什么样子的？

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

下面是一个键值存储中的数据片段：

table6-1

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

理解问题并确定设计范围

这里没有完美的设计。每种设计都在读取、写入和内存使用方面取得了特定的权衡。必须在一致性和可用性之间做出另一个权衡。

在本章中，我们设计了一个包含以下特征的键值存储：

单一服务器的键值存储

开发一个驻扎在单个服务器中的键值存储很容易，一种直观的方法是将键值对存储在哈希表中，该哈希表将所有内容保存在内存中。

为了在一个服务器中容纳更多的数据，可以做两个优化措施：

- 数据压缩
- 只在内存中存储经常使用的数据，其余的存储在磁盘上

即使进行了这些优化，单个服务器也可以很快达到其容量。需要分布式键值存储来支持大数据

分布式键值存储

分布式键值存储也称为分布式哈希表，它将键值对分布在许多服务器上。在设计分布式系统时，了解 CAP（C一致性、A可用性、P分区容错性）定理很重要。

CAP 定理指出，分布式系统不可能同时提供以下三种保证中的两种以上：一致性、可用性和分区容错性。让我们熟悉一些定义。

一致性：一致性意味着所有客户端无论连接到哪个节点，都在同一时间看到相同的数据。

可用性：可用性意味着即使某些节点已关闭，任何请求数据的客户端都会得到响应。

分区容忍度：分区表示两个节点之间的通信中断，分区容错意味着系统在网络分区的情况下继续运行。

CAP 定理指出，必须牺牲三个属性之一来支持 3 个属性中的 2 个，如图 6-1 所示：

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

figure6-1

CP（一致性和分区容错）系统：CP 键值存储在牺牲可用性的同时支持一致性和分区容错。

AP（可用性和分区容错）系统：AP 键值存储支持可用性和分区容错，同时牺牲一致性

CA（一致性和可用性）系统：CA 键值存储支持一致性和可用性，同时牺牲分区容错性。由于网络故障是不可避免的，分布式系统必须容忍网络分区。因此，CA 系统不能存在于现实世界的应用程序中。

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

系统组件

在本节中，我们将讨论以下用于构建键值存储的核心组件和技术：

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

数据分区

对于大型应用程序，将完整的数据集放在单个服务器中是不可行的。实现这一点的最简单方法是将数据拆分为更小的分区并将它们存储在多个服务器中。分区数据时有两个挑战：

第 5 章中讨论的一致性哈希是解决这些问题的一种很好的技术。让我们重新审视一致性哈希在高层次上的工作原理。

使用一致性哈希对数据进行分区有以下优点：

数据复制

为了实现高可用性和可靠性，必须在 N 个服务器上异步复制数据，其中 N 是一个可配置参数。这N台服务器的选择逻辑如下：将key映射到哈希环上的某个位置后，从该位置顺时针走，选择环上的前N台服务器存储数据副本。在图 6-5（N = 3）中，key0 被复制到 s1、s2 和 s3。

figure6-5

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

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

一致性

由于数据在多个节点进行复制，因此必须跨副本同步。Quorum 共识可以保证读写操作的一致性。 让我们先建立几个定义。

N = 副本数

W = 大小为 W 的规定写入。要将写入操作视为成功，必须从 W 个副本确认写入操作。

R = 大小为 R 的读取规定人数。为了使读取操作被认为是成功的，读取操作必须等待至少R个副本的响应。

考虑以下图 6-6 中所示的示例，其中 N = 3。

figure6-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以适应我们的使用情况？

下面是一些可能的设置：

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

一致性模型

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

强一致性通常是通过强迫一个副本不接受新的读/写，直到每个副本都同意当前的写来实现的。这种方法对于高可用系统来说并不理想，因为它可能会阻塞新的操作。Dynamo和Cassandra采用最终一致性，这是我们推荐的键值存储的一致性模型。

从并发写入来看，最终一致性允许不一致的值进入系统，并迫使客户端读取这些值来进行调和。下一节将解释调和是如何与版本管理一起工作的。

不一致的解决方法：版本控制

复制提供了高可用性，但会导致副本之间的不一致。 版本控制和矢量锁用于解决不一致问题。版本化意味着将每一次数据修改都视为一个新的不可更改的数据版本。在我们谈论版本控制之前，让我们用一个例子来解释不一致是如何发生的：

如图6-7所示，副本节点n1和n2的值相同。 让我们称这个值为原始值。 server 1 和 server 2 通过 get(“name”) 操作获得相同的值。

figure6-7

接下来，server 1 将名称更改为“johnSanFrancisco”，server 2 将名称更改为“johnNewYork”，如图 6-8 所示。 这两个更改是同时执行的。 现在，我们有冲突的值，称为版本 v1 和 v2。

figure6-8

在此示例中，可以忽略原始值，因为修改是基于它的。 但是，没有明确的方法来解决最后两个版本的冲突。 为了解决这个问题，我们需要一个可以检测冲突并协调冲突的版本控制系统。

向量时钟是解决此问题的常用技术。

让我们来看看向量时钟是如何工作的。

向量时钟是与数据项关联的键值 [server, version] 对。 它可用于检查一个版本是否先于、成功或与其他版本冲突。

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

上面的抽象逻辑用一个具体的例子来解释，如图6-9所示：

figure6-9

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

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

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

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

其次，向量时钟中的 [server: version] 对可能会快速增长。为了解决这个问题，我们为长度设置了一个阈值，如果超过了限制，则删除最旧的对。这可能导致协调效率低下，因为后代关系无法准确确定。然而，基于Dynamo论文[4]，亚马逊在生产中还没有遇到这个问题；因此，这可能是大多数公司可以接受的解决方案。

故障处理

与任何大规模的系统一样，故障不仅是不可避免的，而且是常见的。处理故障情况是非常重要的。在本节中，我们首先介绍检测故障的技术。然后，我们将介绍常见的故障解决策略。

系统构架图

现在我们已经讨论了设计键值存储时的不同技术考虑，我们可以将注意力转移到架构图上，如图 6-17 所示。

figure6-17

架构的主要特点列举如下：

由于设计是分散的，每个节点执行许多任务，如图6-18所示。

figure6-18

写入路径

图 6-19 解释了将写请求定向到特定节点后会发生什么。 请注意，建议的写/读路径设计主要基于 Cassandra [8] 的体系结构。

  1. 写入请求持久保存在提交日志文件中。
  2. 数据保存在内存缓存中。

figure6-19

  1. 当内存缓存已满或达到预定义的阈值时，数据将刷新到磁盘上的 SSTable [9]。 注意：排序字符串表 (SSTable) 是 <key, value> 对的排序列表。 有兴趣进一步了解 SStable 的读者，请参阅参考资料 [9]。

读取路径

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

figure6-20

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

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

figure6-21

  1. 系统首先检查数据是否在内存中。如果没有，就转到第2步。
  2. 如果数据不在内存中，系统会检查Bloom过滤器。
  3. Bloom过滤器被用来计算哪些SSTables可能包含密钥。
  4. SSTables会返回数据集的结果。
  5. 数据集的结果被返回给客户端。

总结

本章涵盖了许多概念和技术。为了加深记忆，下表总结了分布式键值存储的特点和相应的技术。

目标/问题技术
存储大数据的能力使用一致性哈希将负载分散到多个服务器上
高可用性读取数据复制 多数据中心设置
高可用性写入使用向量时钟（vector clocks）进行版本控制和冲突解决
数据分区一致性哈希
增量可扩展性一致性哈希
异质性（heterogeneity）一致性哈希
处理临时性故障草率仲裁（sloppy quorum）和暗示切换（hinted handoff）
处理永久性故障Merkle 树
处理数据中心中断跨数据中心复制

参考资料