当前位置：首页 > article >正文

面试场景题系列：设计键值存储系统

article 2025/1/5 7:22:19

键值存储也称为键值数据库，是一种非关系型数据库。每个唯一的标识符作为键(key)与其相关联的值(value)存储在一起。这种数据对也叫作“键值对”。

在一个键值对中，键必须是唯一的，通过键可以访问与其相关联的值。键可以是纯文本数据或者哈希值。出于性能上的考虑，较短的键更好。下面是一些键的例子。

•纯文本键：“last_logged_in_at”

•哈希键：253DDEC4

键值对中的值可以是字符串、列表、对象等。在键值存储中，比如Amazon Dynamo、Memcached、Redis等，值通常被当作不透明对象。表6-1展示的是键值存储中的一个数据片段。

6.1 场景需求界定

在本文中，你被要求设计一个键值存储系统来支持下面的操作：

•put(key，value)//插入值，幵与键相关联

•get(key)//获取与键关联的值

每一个键值存储系统的设计都是在读操作、写操作及内存使用之间进行权衡以达到某种平衡。另一种权衡则在一致性和可用性之间进行。具体的场景需求如下：

•每个键值对都不大，小于10KB。

•可以存储大数据。

•高可用性。即使发生故障，系统也能迅速响应。

•高可扩展性。系统可以扩展以支持大数据集。

•自动伸缩。可以基于流量自动添加/移除服务器。

•可调节的一致性。

•低延时。

6.2 单服务器的键值存储

开发一个运行在单服务器上的键值存储系统是容易的。一个直观的方法是把键值对存储在哈希表中，将所有的数据都保存到内存里。虽然内存访问起来很快，但因为空间有限，可能无法将所有数据都放在里面。为了在单服务器上存储更多的数据，可以从以下两个方面进行优化：

•压缩数据。

•只把频繁使用的数据存储在内存里，其他的则放在硬盘上。然而，即使进行了这些优化，依然会很快达到单服务器容量的上限。这时就需要通过分布式键值存储系统来支持大数据了。

6.3 分布式键值存储

分布式键值存储也称为分布式哈希表，它将键值对分布到很多服务器上。

6.3.1 CAP理论

在设计分布式系统时，理解CAP理论是很重要的。CAP理论提出，一个分布式系统最多只能同时满足下面三个特性中的两个：一致性(Consistency)、可用性(Availability)和分区容错性(Partition Tolerance)。我们来看下面的定义。

**一致性：**指的是所有的客户端在相同的时间点看到的是同样的数据，而不管它们连接的是哪个节点（服务器）。

**可用性：**指的是即便有节点发生故障，任意客户端发出的请求都能被响应。

**分区容错性：**分区意味着两个节点之间的通信中断。分区容错性的意思是尽管网络被分区，系统依然可以继续运行。

CAP理论提出，如果要支持上述三个特性中的两个，就必须牺牲剩下的那一个，如图6-1所示。

基于所支持的两种特性，键值存储系统现在有如下分类：

CP（一致性和分区容错性）系统：支持一致性和分区容错性，但牺牲了可用性。

AP（可用性和分区容错性）系统：支持可用性和分区容错性，但牺牲了一致性。

CA（一致性和可用性）系统：支持一致性和可用性，但牺牲了分区容错性。因为网络故障是无法避免的，所以分布式系统必须容忍网络分区。因此，在现实世界中CA系统不可能存在。

为了更好地理解以上定义，我们来看几个具体的例子。在分布式系统中，数据通常会被复制多次。假设数据在3个副本节点上（n1、n2和n3）被复制，如图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。

选择适合你的使用场景的CAP保证是构建分布式键值存储系统的重要步骤。你可以和面试官讨论这个问题，并根据讨论结果来设计系统。

6.3.2 系统组件

在本节中，我们会讨论下面这些用来构建键值存储系统的核心组件和技术：

•数据分区。

•数据复制。

•一致性。

•不一致性的解决方案。

•处理故障。

•系统架构图。

•写路径。

•读路径。

下面的内容大部分基于三种流行的键值存储系统：Dynamo、Cassandra和BigTable。

6.3.3 数据分区

对于大应用来说，把全部数据集放到单服务器上是不现实的。最简单的方法是把数据分割为小的分区并把它们存储在多个服务器中。对数据分区时会有两个挑战：

•将数据均匀地分布在多个服务器上。

•添加或者移除节点时，尽量减少数据的迁移。

一致性哈希是解决这些问题的好方法。

•首先，将服务器放在一个哈希环上。在图6-4中，8个服务器被放在哈希环上，用s0，s1，…，s7表示。

•接下来，键被哈希映射到同一个环上，并存储在按顺时针方向移动时遇到的第一个服务器上。比如，依照这种逻辑，key0存储在s1上。

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

•自动伸缩：可以基于负载自动添加和移除服务器。

•异质性：服务器的虚拟节点数量可以与服务器的性能成比例。比如，可以为性能高的服务器分配更多的虚拟节点。

6.3.4 数据复制

为了实现高可用性和可靠性，数据必须在N个服务器上异步复制，这里的N是一个可配置的参数。这N个服务器是基于下面的逻辑来挑选的：当一个键被映射到哈希环上的某个位置后，从这个位置开始顺时针遍历哈希环，找到先遇到的N个服务器来存储数据副本。如图6-5所示(N=3)，key0被复制到s1、s2和s3上。

使用虚拟节点时，在哈希环上最先找到的N个节点对应的物理服务器数量可能少于N。为了解决这个问题，当执行顺时针遍历逻辑时，我们只选择不重复的服务器。

同一个数据中心内的节点经常会因为电力中断、网络故障、自然灾害等原因同时出现故障。为了提高可靠性，数据副本被存储在不同的数据中心，并且数据中心之间通过高速网络连接。这样即使一个数据中心发生故障，其他数据中心仍然可以提供服务，确保系统的可用性和容错性。

6.3.5 一致性

因为数据被复制到多个节点上，所以副本之间必须同步。仲裁一致性(Quorum Consensus)[插图]可以保证读写操作的一致性。我们先定义一些东西。

N：代表副本的数量。

W：代表写操作的Quorum大小。一个写操作要被认为是成功的，必须获得W个副本的确认。

R：代表读操作的Quorum大小。一个读操作要被认为是成功的，必须至少获得R个副本的响应。

我们思考如图6-6所示的例子，这里N=3。

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

W、R和N的配置是典型的延时和一致性之间的权衡。如果W=1或者R=1，因为协调者只需要等待任意一个副本的响应，所以一个操作很快会返回。如果W＞1或者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采用了最终一致性模型，这也是我们推荐的键值存储的一致性模型。通过并行写，最终一致性模型允许不一致的值进入系统，并强制客户端读取这些值来进行协调。下一节会解释版本控制和协调的工作原理。

6.3.6 不一致性的解决方案：版本控制

复制副本提供了高可用性但会导致副本之间的数据不一致。版本控制和向量时钟被用来解决这些不一致问题。版本控制的意思是每次修改数据都生成一个新的不可变的数据版本。在讨论版本控制之前，我们用一个例子来解释不一致性是怎么发生的。

如图6-7所示，副本节点n1和n2有同样的值。我们把这个值称作原始值。服务器server1和server2通过get(“name”)操作获取了同样的值。

接下来，server1把name的值改为“johnSanFrancisco”，server2把name的值改为“johnNewYork”，如图6-8所示。这两个改变同时发生。现在有了两个冲突的值，我们将它们分别称为v1和v2版本。

在这个例子中，可以忽略原始值，因为我们对它进行了修改。但是，没有明确的方法来解决最后两个版本之间的冲突。为了解决这个问题，我们需要一个版本控制系统来检测和解决冲突。向量时钟是解决这个问题的常用方法。下面我们分析向量时钟是怎么工作的。

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

假设一个向量时钟是用D([S1，v1]，[S2，v2]，…，[Sn，vn])来表示的，其中D是数据项，v1是版本计数器的值，S1是服务器编号，以此类推。如果数据项D被写入服务器Si，则系统必须执行下面任务中的一个。

•如果[Si，vi]存在，则增加vi的值。

•否则，创建新的记录[Si，1]。

图6-9用通过一个具体的例子解释了上面抽象的逻辑。

在这个例子中，假设有一个数据项D1，并且系统中有五个客户端(A、B、C、D、E)，系统还有三个服务器（Sx、Sy和Sz）。

1.客户端A将数据项D1写入系统，写操作是由服务器Sx来处理的，此时Sx的向量时钟为D1[(Sx，1)]。

2.客户端B读取最新的D1，将其更新成D2并写回系统。D2继承自D1，因此它覆盖了D1。假设写操作由同一个服务器Sx来处理，此时Sx的向量时钟为D2([Sx，2])。

3.客户端C读取最新的D2，将其更新成D3并写回系统。假设写操作是由服务器Sy来处理的，此时Sy的向量时钟为D3([Sx，2]，[Sy，1])）。

4.客户端D读取最新的D2，将其更新成D4并写回系统。假设写操作是由服务器Sz来处理的，此时Sz的向量时钟为D4([Sx，2]，[Sy，1]，[Sz，1])。

5.客户端E读取D3和D4时，发现数据存在冲突，因为数据项D2被Sy和Sz修改了。客户端解决了冲突，并且把更新后的数据发给服务器。假设写操作是由Sx来处理的，那么此时Sx的向量时钟为D5([Sx，3]，[Sy，1]，[Sz，1])。我们稍后会解释如何检测冲突。

使用向量时钟，很容易判断版本X是否为版本Y的祖先（即是否有冲突）——只需要检查版本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])就存在冲突。

尽管向量时钟可以解决冲突，它也有两个缺点值得注意。

第一，向量时钟增加了客户端的复杂性，因为客户端需要实现冲突解决逻辑。

第二，向量时钟中的[服务器，版本号]数据对可能会迅速增长。为了解决这个问题，我们设定了长度阈值，如果超过了阈值，最老的数据对就会被移除。这可能会导致协调效率下降，因为无法准确地判断后代关系。但是，根据论文“Dynamo：Amazon’s Highly Available Key-value Store”中的描述，亚马逊还没有在生产环境中遇到过这个问题。因此，对大部分公司来说，这可能是一个可接受的解决方案。

6.3.7 处理故障

对于任何大型系统，故障不仅是不可避免的，而且还很常见。处理故障场景非常重要。在本节中，我们先介绍检测故障的技术，然后讨论常见的故障处理策略。

故障检测

在分布式系统中，不能仅凭服务器A说服务器B出了故障就断定服务器B真的出了故障。通常，至少需要两个独立的信息源才能标记一个服务器出故障了。

如图6-10所示，全对全多播(All-to-All Multicasting)是一个简单明了的解决方案。但是，当系统中有很多服务器时，这种方法效率较低。

使用去中心化的故障检测方法，比如Gossip协议，是一个更好的解决方案。Gossip协议的工作原理如下所述。

•每个节点维护一个节点成员列表，其中包括成员ID和心跳计数。

•每个节点定期地增加自己的心跳计数。

•每个节点定期地给一组随机节点发送心跳信号，这些节点又会将心跳信号接着传递给另一组节点。

•一旦节点收到心跳信号，就会据此更新成员列表。

•如果心跳计数在预定时间内没有增加，该成员就被认为宕机了。

如图6-11所示：

•节点s0维护着左侧的节点成员列表。

•节点s0发现节点s2（成员ID=2）的心跳计数很长时间都没有增加了。

•节点s0将包含s2信息的心跳信号发送给一组随机节点。一旦其他节点确认s2的心跳计数很长时间没有更新，节点s2就被标记为已发生故障，这个信息也会被传播给其他节点。

处理临时故障

通过Gossip协议发现故障后，系统需要采取某种机制来确保可用性。在严格的仲裁协议中，读写操作可能会被阻塞，如6.3.5节所述。

一种叫作“松散仲裁”(Sloppy Quorum)[插图]的技术被用来提高可用性。与强制执行仲裁要求不同，这种技术选择在哈希环上最先发现的W个正常工作的服务器来进行写操作，并选择在哈希环上最先发现的R个正常工作的服务器来进行读操作。发生故障的服务器将被忽略。

如果一个服务器因为网络或者服务器故障而不可用，另一个服务器会临时处理请求。当该服务器恢复运行时，变更会被推送回来以实现数据一致性。这个过程被称为暗示性传递(Hinted Handoff)。在图6-12中，因为服务器s2不可用，读/写操作将由服务器s3临时处理。当s2恢复在线时，s3会把数据发回给s2。

处理永久故障

暗示性传递被用来处理临时故障。那么，如果一个副本永久不可用该怎么办？为了应对这种情形，我们实现了反熵协议(Anti-entropy Protocol)来保持副本同步。反熵需要比较副本上的每条数据并将每个副本都更新到最新的版本。Merkle树被用来检测不一致性并最小化数据传输量。

哈希树也叫作Merkle树，对于每个非叶节点，它的标记是基于其子节点的标签或值进行的哈希运算得到的结果。如果该节点是叶子节点，那么其标记直接由该叶子节点的值进行哈希运算得到。哈希树可以高效和安全地验证大型数据结构的内容。

假设键空间是从1到12，下面的步骤展示了如何构建一个Merkle树。灰底的格子标出了不一致的地方。

第一步：把键空间分成不同的桶（在我们的例子中有4个桶），如图6-13所示。桶用作根节点以维护树的有限深度。

第二步：一旦创建了桶，就把桶里的每个键都用一致哈希方法(Uniform Hashing Method)计算哈希值（见图6-14）。

第三步：为每个桶创建一个哈希节点（见图6-15）。

第四步：向上构建树，直到根节点，通过计算子节点的哈希值来得到父节点的哈希值（见图6-16）。

比较两个Merkle树是从比较根节点的哈希值开始的。如果根节点的哈希值匹配上了，则表示两个服务器有同样的数据。如果根节点的哈希值不一样，那么采用“先左后右”的顺序来比较子节点的哈希值。你可以遍历这两个Merkle树来找出哪些桶不同步并同步这些桶。

使用Merkle树，需要同步的数据量是与两个副本间的差异成比例的，而不是与副本包含的整体数据量成比例。在真实世界的系统中，桶的数量非常大。例如，一个可能的配置是100万个桶对应10亿个键，每个桶包含1000个键。

处理数据中心故障

因为电力中断、网络故障、自然灾害等原因，数据中心有可能发生故障。要构建一个可以处理数据中心故障的系统，在多个数据中心之间复制数据至关重要。就算某个数据中心完全无法工作，用户依然可以从其他数据中心获取数据。

6.3.8 系统架构图

我们已经讨论了设计键值存储系统时的不同技术考量，现在可以把关注点放到架构图上了，如图6-17所示。

该系统架构的主要特点如下：

•客户端与键值存储系统之间通过简单的API通信：get(key)和put(key，value)。

•协调者是一个节点，在客户端和键值存储系统之间充当代理。

•节点通过一致性哈希分布在哈希环上。

•系统完全去中心化，所以添加和移除节点的工作完全可以自动进行。

•数据被复制到多个节点。

•因为每个节点有同样的职责，所以没有单点故障。因为这个设计是去中心化的，所以每个节点都需要执行图6-18中所示的任务。

6.3.9 写路径

图6-19解释了写请求被导向到某个特定节点后会发生什么。请注意，下面推荐的关于写/读路径的设计主要基于Cassandra的架构。

1.写请求在提交日志(Commit Log)文件中被持久化。

2.数据被保存在内存缓存中。

3.当内存缓存已满或者达到预定的阈值时，数据会被刷新到硬盘上的SSTable[插图]。请注意，SSTable（Sorted-String Table，有序字符串表）是一个排过序的<键，值>对列表。对SStable感兴趣的读者可以自行阅读Ilya Grigorik发表在网站igvita上的文章“SSTable and Log Structured Storage：LevelDB”。