系统设计面试的行家指南（上）（2）https://developer.aliyun.com/article/1481932
五、设计一致哈希
为了实现水平扩展，在服务器之间高效、均匀地分配请求/数据非常重要。一致哈希是实现这一目标的常用技术。但首先，让我们深入研究一下这个问题。
老调重弹问题
如果你有 n 个缓存服务器，平衡负载的一个常用方法是使用下面的哈希方法：
server index = hash(key)% N，其中 N 是服务器池的大小。
让我们用一个例子来说明它是如何工作的。如表 5-1 所示，我们有 4 台服务器和 8 个带哈希的字符串键。
为了获取存储密钥的服务器，我们执行模块化操作 f(key) % 4 。例如， hash(key0) % 4 = 1 表示客户端必须联系服务器 1 来获取缓存的数据。图 5-1 显示了基于表 5-1 的键的分布。
当服务器池的大小固定且数据分布均匀时，这种方法非常有效。然而，当添加新的服务器或者移除现有的服务器时，问题 出现 。例如，如果服务器 1 脱机，服务器池的大小将变为 3。 使用相同的哈希函数，我们得到一个键的相同哈希值。但是应用模运算给了我们不同的服务器索引，因为服务器的数量减少了 1。 我们应用 hash % 3 : 得到如表 5-2 所示的结果
图 5-2 显示了基于表 5-2 的新的密钥分布。
如图 5-2 所示，大部分的键都是重新分配的，而不仅仅是原来存储在离线服务器(服务器 1)中的那些。 这意味着当服务器 1 离线时，大多数缓存客户端将连接到错误的服务器来获取数据。这导致了高速缓存未命中的风暴。一致哈希是缓解这一问题的有效技术。
一致哈希
引自维基百科：“一致哈希是一种特殊的哈希，当哈希表重新调整大小并使用一致哈希时，平均只有 k/n 个键需要重新映射，其中 k 是键的数量，n 是槽的数量。相反，在大多数传统哈希表中，数组槽数量的变化会导致几乎所有的键被重新映射[1]”。
哈希空间和哈希环
现在我们了解了一致性哈希的定义，让我们看看它是如何工作的。假设 SHA-1 作为哈希函数 f， 哈希函数的输出 范围为 : x0, x1, x2, x3, …, xn 。在密码学中，SHA-1 的哈希空间从 0 到 2¹⁶⁰ - 1。这意味着 x0 对应于 0， xn 对应于2¹⁶⁰ - 1，中间的所有其他哈希值落在 0 和 2¹⁶⁰-1 之间。图 5-3 显示了哈希空间。
通过连接两端，我们得到一个哈希环如图 图 5-4 :
哈希服务器
使用相同的哈希函数 f ，我们基于服务器 IP 或名称将服务器映射到环上。图 5-5 显示了 4 个服务器被映射到哈希环上。
哈希键
值得一提的是，这里使用的哈希函数与“重哈希问题”中的不同，没有模运算。如图 5-6 所示，4 个缓存键(key0、key1、key1和 key3)被哈希到哈希环上
服务器查找
为了确定一个密钥存储在哪个服务器上，我们从环上的密钥位置开始顺时针旋转，直到找到一个服务器。 图 5-7 解释了这个过程。顺时针转动 ， 键 0 存储在 服务器 0 上；key1存储在 服务器 1 上；key1存储在 服务器 2 和key1存储在 服务器 3 。
添加服务器
使用上述逻辑，添加新的服务器将只需要重新分发一小部分密钥。
在图 5-8 中，增加了一个新的 服务器 4 后，只有key0需要重新分配。k1、k1、 和k1保持在相同的服务器上。让我们仔细看看其中的逻辑。在添加 服务器 4 之前，key0存储在 服务器 0 上。现在，key0将被存储在服务器 4 上，因为服务器 4 是它从key0在环上的位置顺时针方向遇到的第一个服务器。其他密钥不会基于一致的哈希算法进行重新分配。
移除一个服务器
当服务器被移除时，只有一小部分密钥需要用一致的哈希法重新分配。在图 5-9 中，当 服务器 1 被移除后，只有key1必须重新映射到 服务器 2 。其余的键不受影响。
两个问题的基本处理方法
一致性哈希算法是由 Karger 等人在麻省理工学院提出的[1]。基本步骤是：
使用均匀分布的哈希函数将服务器和密钥映射到环上。
要找出一个密钥映射到哪个服务器，从密钥位置开始顺时针方向走，直到找到环上的第一个服务器。
这种方法发现了两个问题。首先，考虑到可以添加或移除服务器，不可能为环上的所有服务器保持相同大小的分区。分区是相邻服务器之间的哈希空间。分配给每个服务器的环上的分区的大小可能非常小或相当大。在图 5-10 中，如果去掉s1，s1的 分区(用双向箭头突出显示)是s1和s1的 分区的两倍。
第二，环上可能有不均匀的密钥分布。例如，如果服务器被映射到图 5-11 中列出的位置，那么大部分密钥都存储在 服务器 2 上。但是 服务器 1 服务器 3 没有数据。
一种叫做虚拟节点或副本的技术被用来解决这些问题。
虚拟节点
虚拟节点是指真实节点，每个服务器由环上的多个虚拟节点表示。在图 5-12 中， 服务器 0 和 服务器 1 都有 3 个虚拟节点。3 是任意选择的；而在现实世界的系统中，虚拟节点的数量要大得多。我们没有用 s0 ，而是用 s0_0，s0_1 ，s0_2 来代表环上的 服务器 0 。同样， s1_0，s1_1 ，和 s1_2 代表环上的服务器 1。对于虚拟节点，每台服务器负责多个分区。标签为s0的分区(边缘)由服务器 0 管理。另一方面，标签为 s1 的分区由 服务器 1 管理。
为了找到一个密钥存储在哪个服务器上，我们从密钥的位置开始顺时针方向，找到环上遇到的第一个虚拟节点。在图 5-13 中，为了找出k0存储在哪个服务器上，我们从k0的位置顺时针方向，找到虚拟节点 s1_1 ，它指的是 服务器 1 。
随着虚拟节点数量的增加，键的分布变得更加均衡。这是因为虚拟节点越多，标准偏差就越小，从而导致平衡的数据分布。标准差衡量数据是如何分布的。在线研究 [2]进行的实验结果显示，对于一个或两百个虚拟节点，标准偏差在平均值的 5% (200 个虚拟节点)和 10% (100 个虚拟节点)之间。当我们增加虚拟节点的数量时，标准偏差会更小。然而，需要更多的空间来存储关于虚拟节点的数据。这是一种权衡，我们可以调整虚拟节点的数量来适应我们的系统需求。
找到受影响的按键
当添加或删除服务器时，需要重新分配一小部分数据。如何找到受影响的范围来重新分配密钥？
在图 5-14 中， 服务器 4 被添加到环上。受影响的范围从 s4 (新增节点)开始，绕环逆时针移动，直到找到一个服务器( s3 )。因此，位于s3和s3之间的键需要重新分配给s3。
当一个服务器( s1 )被移除时，如图 5-15 所示，受影响的范围从 s1 (被移除的节点)开始，绕环逆时针移动，直到找到一个服务器( s0 )。因此，位于s0和s0之间的键必须重新分配给s0。
总结起来
在本章中，我们深入讨论了一致性哈希，包括为什么需要它以及它是如何工作的。一致哈希的好处包括：
添加或删除服务器时，最小化的密钥会重新分配。
因为数据分布更均匀，所以水平缩放更容易。
缓解热点关键问题。对特定碎片的过度访问可能会导致服务器过载。想象一下凯蒂·佩里、贾斯汀比伯和 Lady Gaga 的数据都在同一个碎片上。一致哈希通过更均匀地分布数据来帮助缓解这个问题。
一致性哈希在现实世界的系统中被广泛使用，包括一些著名的：
亚马逊迪纳摩数据库分区组件【3】
Apache Cassandra[4]中跨集群的数据分区
不和谐聊天应用【5】
Akamai 内容交付网络【6】
磁悬浮网络负载均衡器【7】
祝贺你走到这一步！现在给自己一个鼓励。干得好！
参考资料
[1] Consistent hashing: https://en.wikipedia.org/wiki/Consistent_hashing [2] Consistent Hashing: https://tom-e-white.com/2007/11/consistent-hashing.html [3] Dynamo: Amazon’s Highly Available Key-value Store: https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf [4] Cassandra - A Decentralized Structured Storage System: http://www.cs.cornell.edu/Projects/ladis2009/papers/Lakshman-ladis2009.PDF [5] How Discord Scaled Elixir to 5,000,000 Concurrent Users: https://blog.discord.com/scaling-elixir-f9b8e1e7c29b [6] CS168: The Modern Algorithmic Toolbox Lecture #1: Introduction and Consistent Hashing: http://theory.stanford.edu/~tim/s16/l/l1.pdf [7] Maglev: A Fast and Reliable Software Network Load Balancer: https://static.googleusercontent.c
六、设计键值存储
键值存储，也称为键值数据库，是一种非关系数据库。每个唯一标识符都存储为一个键及其相关值。这种数据配对被称为“键-值”对。
在键-值对中，键必须是唯一的，与键相关联的值可以通过键来访问。键可以是纯文本或哈希值。出于性能原因，短键效果更好。钥匙长什么样？下面举几个例子：
纯文本密钥：“上次登录时间”
哈希键：253 dec 4
键值对中的值可以是字符串、列表、对象等。在键值存储中，值通常被视为不透明的对象，如 Amazon dynamo [1]、Memcached [2]、Redis [3]等。
下面是键值存储中的一个数据片段：
在本章中，要求你设计一个支持以下操作的键值存储：
put(key，value)：插入与key关联的valueget(key)：获取与key关联的value
了解问题并建立设计范围
没有完美的设计。每种设计都在读取、写入和内存使用之间取得了特定的平衡。另一个需要权衡的是一致性和可用性。在这一章中，我们设计了一个键值存储，它包括以下特征：
键-值对的大小很小：小于 10 KB。
存储大数据的能力。
高可用性：即使在故障期间，系统也能快速响应。
高可扩展性：系统可以扩展以支持大数据集。
自动伸缩：服务器的添加/删除应根据流量自动进行。
可调一致性。
低潜伏期。
单服务器键值存储
开发驻留在单个服务器上的键值存储很容易。一种直观的方法是将键值对存储在哈希表中，将所有内容保存在内存中。尽管内存访问速度很快，但由于空间限制，将所有内容都放入内存可能是不可能的。可以进行两种优化，以便在单个服务器中容纳更多数据：
数据压缩
仅将常用数据存储在内存中，其余数据存储在磁盘上
即使进行了这些优化，单台服务器也能很快达到其容量。支持大数据需要分布式键值存储。
分布式键值存储
分布式键值存储也称为分布式哈希表，它将键值对分布在许多服务器上。在设计分布式系统时，理解 CAP ( C 一致性， A 可用性， P 分区容差)定理是很重要的。
上限定理
CAP 定理指出，分布式系统不可能同时提供三个保证中的两个以上：一致性、可用性和分区容差。让我们建立几个定义。
一致性 :一致性是指所有客户端同时看到相同的数据，无论它们连接到哪个节点。
可用性： 可用性意味着任何请求数据的客户端都可以得到响应，即使某些节点出现故障。
分区容错： 一个分区表示两个节点之间的通信中断。分区容差意味着尽管存在网络分区，系统仍能继续运行。
CAP 定理指出，必须牺牲三个属性中的一个来支持三个属性中的两个，如图 6-1 所示。
现在，键值存储是根据它们支持的两个 CAP 特征来分类的：
CP(一致性和分区容差)系统：CP 键值存储支持一致性和分区容差，但牺牲了可用性。
AP(可用性和分区容差)系统：AP 键值存储支持可用性和分区容差，但牺牲了一致性。
CA(一致性和可用性)系统：CA 键值存储支持一致性和可用性，同时牺牲分区容差。由于网络故障不可避免，分布式系统必须容忍网络分区。因此，CA 系统不能存在于现实世界的应用程序中。
你上面读到的大多是定义部分。为了更容易理解，让我们看一些具体的例子。在分布式系统中，数据通常被复制多次。假设数据复制在三个副本节点上，n1，n1和n1如图 6-2 所示。
理想情况
在理想世界中，网络分区永远不会发生。写入n1的数据自动复制到n1和n1。实现了一致性和可用性。
现实世界的分布式系统
在分布式系统中，分区是不可避免的，当出现分区时，我们必须在一致性和可用性之间做出选择。图 6-3 中，n3下行，无法与n3和n3通信。如果客户端向n3或n3写入数据，数据无法传播到n3。如果数据被写入到【n3】但是没有被传播到n3和n3，n3和n3就会有陈旧数据。
如果我们选择一致性而不是可用性(CP 系统)，我们必须阻止对n1和n1的所有写操作，以避免这三个服务器之间的数据不一致，从而导致系统不可用。银行系统通常有极高的一致性要求。例如，对于银行系统来说，显示最新的余额信息至关重要。如果由于网络分区而出现不一致，银行系统会在解决不一致之前返回一个错误。
然而，如果我们选择可用性而不是一致性(AP 系统)，系统会继续接受读取，即使它可能会返回过时的数据。对于写入，n1和n1将继续接受写入，并且当网络分区被解析时，数据将被同步到n1。
选择适合您的用例的正确 CAP 担保是构建分布式键值存储的重要一步。你可以和你的面试官讨论这个问题，并据此设计系统。
系统组件
在本节中，我们将讨论以下用于构建键值存储的核心组件和技术：
数据分区
数据复制
一致性
不一致性解决
处理故障
系统架构图
写路径
读取路径
下面的内容主要基于三个流行的键值存储系统：Dynamo [4]、Cassandra [5]和 BigTable [6]。
数据分区
对于大型应用程序，将完整的数据集放在一台服务器上是不可行的。实现这一点的最简单方法是将数据分割成更小的分区，并将它们存储在多个服务器中。对数据进行分区时有两个挑战：
将数据均匀分布在多台服务器上。
添加或删除节点时，尽量减少数据移动。
第五章中讨论的一致哈希法是解决这些问题的一个很好的技术。让我们从高层次上重新审视一下一致性哈希是如何工作的。
首先，服务器被放置在一个哈希环上。在图 6-4 中，八个服务器，分别用s0，s0，…，s0表示，放置在哈希环上。
接下来，一个密钥被哈希到同一个环上，并存储在顺时针方向移动时遇到的第一个服务器上。例如，key0使用此逻辑存储在s1中。
使用一致哈希对数据进行分区有以下优点：
自动扩展： 可以根据负载自动添加和删除服务器。
异构： 一台服务器的虚拟节点数量与服务器容量成正比。例如，为容量较高的服务器分配更多的虚拟节点。
数据复制
为了实现高可用性和可靠性，数据必须通过 N 服务器异步复制，其中 N 是一个可配置的参数。使用以下逻辑选择这些 N 服务器：在将一个键映射到哈希环上的一个位置之后，从该位置顺时针行走，选择环上的第一个 N 服务器来存储数据副本。在图 6-5 中( N = 3 )，key0被复制在s1、 和s1。
有了虚拟节点，环上的第一个 N 个 节点可能归少于 N 个 物理服务器所有。为了避免这个问题，我们在执行顺时针遍历逻辑时只选择唯一的服务器。
由于停电、网络问题、自然灾害等原因，同一数据中心的节点经常同时发生故障。为了更好的可靠性，副本被放置在不同的数据中心，并且数据中心通过高速网络连接。
一致性
由于数据在多个节点上复制，因此必须跨副本进行同步。仲裁共识可以保证读写操作的一致性。让我们先确立几个定义。
N = 副本数量 W = 一写法定人数 W 。为了使写入操作被认为是成功的，必须从 W 副本确认写入操作。 R = 一读法定人数大小 R 。为了使读取操作被认为是成功的，读取操作必须等待来自至少 R 个副本的响应。
考虑下面图 6-6 所示的例子，其中 N = 3 。
W = 1 并不意味着数据写在一台服务器上。例如，在图 6-6 的配置中，数据在s0、s0、 和s0被复制。 W = 1 表示在写入操作被认为成功之前，协调器必须收到至少一个确认。例如，如果我们从s0得到确认，我们就不再需要等待来自s0和s0的确认。协调器充当客户端和节点之间的代理。
W，RN 的配置是典型的延迟和一致性的权衡。如果 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 采用最终一致性，这是我们为键值存储推荐的一致性模型。对于并发写入，最终一致性允许不一致的值进入系统，并迫使客户端读取这些值进行协调。下一节解释了协调如何与版本控制一起工作。
不一致解决方案：版本控制
复制提供了高可用性，但会导致副本之间的不一致。版本控制和向量时钟用于解决不一致性问题。版本化意味着将每个数据修改视为数据的一个新的不可变版本。在我们谈论版本控制之前，让我们用一个例子来解释不一致是如何发生的：
如图 6-7 所示，两个副本节点n1和n1具有相同的值。让我们称这个值为原来的 值。服务器 1 和 服务器 2 对name操作获取相同的值。
接下来， 服务器 1 将名称改为johnSanFrancisco， 服务器 2 将名称改为johnNewYork，如图 6-8 所示。这两种变化是同时进行的。现在，我们有相互冲突的值，叫做版本 v1 和 v2 。
在这个例子中，原始值可以被忽略，因为修改是基于它的。但是，没有明确的方法来解决后两个版本的冲突。为了解决这个问题，我们需要一个能够检测冲突并协调冲突的版本控制系统。矢量时钟是解决这一问题的常用技术。让我们来看看矢量时钟是如何工作的。
向量时钟是与数据项相关联的 【服务器，版本】 对。它可用于检查一个版本是否领先、成功或与其他版本冲突。
假设一个矢量时钟用D([S1, v1], [S1, v2], …, [Sn, VN])表示，其中 D 为数据项， v1 为版本计数器，S1为服务器号等。如果数据项 D 被写入服务器 Si ，系统必须执行以下任务之一。
增量 vi 如果[Si, vi]存在。
否则，新建一个条目[Si, 1]。
以上抽象的逻辑用一个具体的例子来说明，如图 6-9 所示。
1。一个客户端向系统写一个数据项，这个写由服务器 Sx 处理，它现在有了向量时钟D1[Sx, 1]。
2。另一个客户端读取最新的 D1 ，更新为 D2 ，并写回。 D2 是 D1 的后代，所以它覆盖了 D1 。假设写操作由同一个服务器Sx处理，该服务器现在有向量时钟D2(Sx, 2)。
3。另一个客户端读取最新的，更新为 D3 ，并写回。假设写操作由服务器Sy处理，它现在有向量时钟 D3([Sx，2]，[Sy，1])。
4。另一个客户端读取最新的 D2 ，更新为 D4 ，并写回。假设写操作由服务器处理，它现在有D4([Sx, 2], [Sz, 1])。
5。当另一个客户端读取 D3 和 D4 时，发现一个冲突，这个冲突是由于数据项D2被和 Sz 同时修改引起的。客户端解决冲突，并将更新的数据发送到服务器。假设写的是由Sx处理的，这里面现在有D5([Sx, 3], [Sy, 1], [Sz, 1])。我们将很快解释如何检测冲突。
使用矢量时钟，很容易判断出一个 版本 X 是一个 Y 版本的祖先(即没有冲突)，如果 版本的计数器对于的矢量时钟中的每个参与者都大于或等于版本 X 中的计数器。比如向量时钟 D([s0, 1], [s0, 1])就是 D([s0, 1], [s0, 2]) 的一个祖先。因此，不会记录冲突。
同样，如果 Y 的向量时钟中有任何参与者的计数器小于其在 X 中对应的计数器，则可以看出版本 X 是 Y 的兄弟(即存在冲突)。比如下面两个向量时钟表示有冲突： D([s0, 1], [s0, 2]) 和 D([s0, 2], [s0, 1])。
尽管矢量时钟可以解决冲突，但也有两个明显的缺点。首先，向量时钟增加了客户端的复杂性，因为它需要实现冲突解决逻辑。
第二， 【服务器：版本】 成对出现在向量时钟中的可能迅速增长。为了解决这个问题，我们为长度设置了一个阈值，如果它超过了限制，最早的对将被删除。这可能导致协调效率低下，因为后代关系无法准确确定。但是基于迪纳摩纸业[4]，亚马逊在生产中还没有遇到这个问题；所以，对于大多数公司来说，大概是可以接受的解决方案。
处理故障
正如任何大规模的大型系统一样，故障不仅不可避免，而且很常见。处理故障场景非常重要。在本节中，我们首先介绍检测故障的技术。然后，我们回顾常见的故障解决策略。
故障检测
在一个分布式系统中，仅仅因为一个服务器说另一个服务器关闭了，就认为这个服务器关闭了是不够的。通常，至少需要两个独立的信息源来标记服务器停机。
如图 6-10 所示，所有对所有的多播是一个简单的解决方案。然而，当系统中有许多服务器时，这是低效的。
更好的解决方案是使用分散式故障检测方法，如 gossip 协议。八卦协议的工作原理如下：
每个节点维护一个节点成员列表，其中包含成员 id 和心跳计数器。
每个节点周期性地递增其心跳计数器。
每个节点周期性地向一组随机节点发送心跳，心跳又传播到另一组节点。
一旦节点接收到心跳，成员列表将更新为最新信息。
如果心跳没有增加超过预定义的时间段，则该成员被视为离线。
如图 6-11 所示：
节点s0维护左侧显示的节点成员列表。
节点s0注意到节点 s2(成员ID = 2)的心跳计数器长时间没有增加。
节点s0向一组随机节点发送包含s0信息的心跳。一旦其他节点确认【s0】的心跳计数器长时间没有更新，节点s0被标记为下线，这个信息被传播到其他节点。
处理临时故障
通过 gossip 协议检测到故障后，系统需要部署某些机制来确保可用性。在严格仲裁方法中，读写操作可能会被阻止，如仲裁共识部分所示。
一种被称为“草率法定人数”的技术[4]被用来提高可用性。系统选择第一个 W 健康服务器进行写操作，第一个 R 健康服务器进行哈希环上的读操作，而不是强制执行定额要求。脱机服务器被忽略。
如果一个服务器由于网络或服务器故障而不可用，另一个服务器将临时处理请求。当关闭的服务器启动时，更改将被推回以实现数据一致性。这个过程被称为提示切换。由于s2在图 6-12 中不可用，读写将暂时由s2处理。当s2重新上线时，s2会将数据交还给s2。
处理永久性故障
提示切换用于处理临时故障。如果副本永久不可用怎么办？为了处理这种情况，我们实现了一个反熵协议来保持副本同步。反熵包括比较副本上的每一条数据，并将每个副本更新到最新版本。Merkle 树用于不一致性检测和最小化传输的数据量。
引自维基百科[7]:“哈希树或 Merkle 树是 中的树，其中每个非叶节点都用其子节点的标签或值(在叶的情况下)的哈希来标记。哈希树允许高效和安全地验证大型数据结构的内容”。
假设密钥空间从 1 到 12，下面的步骤展示了如何构建 Merkle 树。突出显示的方框表示不一致。
步骤 1:将键空间划分成桶(在我们的例子中是 4 个),如图 6-13 所示。一个存储桶被用作根级节点，以保持树的有限深度。
步骤 2:一旦创建了存储桶，使用统一的哈希方法对存储桶中的每个关键字进行哈希(图 6-14)。
第三步：为每个桶创建一个哈希节点(图 6-15)。
第四步：通过计算子节点的哈希值，向上构建树直到根节点(图 6-16)。
要比较两个 Merkle 树，先从比较根哈希开始。如果根哈希匹配，两台服务器具有相同的数据。如果根哈希不一致，则先比较左边的子哈希，然后比较右边的子哈希。您可以遍历树来查找哪些存储桶没有同步，并只同步那些存储桶。
使用 Merkle 树，需要同步的数据量与两个副本 、 之间的差异成正比，而与它们包含的数据量无关。在现实世界的系统中，桶的大小相当大。例如，一种可能的配置是每十亿个键有一百万个存储桶，所以每个存储桶只包含 1000 个键。
处理数据中心故障
停电、网络中断、自然灾害等都可能导致数据中心中断。要构建能够处理数据中心停机的系统，跨多个数据中心复制数据非常重要。即使一个数据中心完全离线，用户仍然可以通过其他数据中心访问数据。
系统架构图
既然我们已经讨论了设计键值存储时不同的技术考虑，我们可以把注意力转移到架构图上，如图 6-17 所示。
该架构的主要特点如下：
客户端通过简单的 API 与键值存储进行通信： get(key) 和 put(key，value) 。
协调器是充当客户端和键值存储之间的代理的节点。
使用一致哈希法将节点分布在环上。
系统是完全分散的，因此添加和移动节点可以是自动的。
数据在多个节点复制。
没有单点故障，因为每个节点都有相同的职责。
由于设计是分散的，每个节点执行许多任务，如图 6-18 所示。
写路径
图 6-19 解释了写请求指向特定节点后会发生什么。请注意，建议的写/读路径设计主要基于 Cassandra [8]的架构。
1。写请求保存在提交日志文件中。
2。数据保存在内存缓存中。
3。当内存缓存已满或达到预定义的阈值时，数据将被刷新到磁盘上的 SSTable [9]中。注意：排序字符串表(SSTable)是一个由键值对组成的排序列表。对于有兴趣了解 SStable 更多信息的读者，请参考参考资料[9]。
阅读路径
将读取请求定向到特定节点后，它首先检查数据是否在内存缓存中。如果是，数据将返回给客户端，如图 6-20 所示。
如果数据不在内存中，将从磁盘中检索。我们需要一种有效的方法来找出哪个表包含密钥。布鲁姆过滤器[10]通常用于解决这个问题。
当数据不在内存中时，读取路径如图 6-21 所示。
1。系统首先检查数据是否在内存中。如果没有，请转到步骤 2。
2。如果数据不在内存中，系统会检查布隆过滤器。
3。布隆过滤器用于确定哪些表可能包含该密钥。
4。SSTables 返回数据集的结果。
5。数据集的结果被返回给客户端。
系统设计面试的行家指南（上）（4）https://developer.aliyun.com/article/1481934
