设计键值存储系统

键值存储也称为键值数据库，是一种非关系型数据库。每个唯一的标识符作为键（Key）与其相关联的值（value）存储在一起。

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

  1. put(key, value) 插入值，并于键相关联
  2. get(key) 获取与键关联的值

理解问题并确定设计的边界

世上没有完美的设计，每一个键值存储系统的设计都是在读操作、写操作及内存使用之间进行权衡以达到某种平衡。另一种平衡则在一致性和可用性之间进行。

设计一个键值存储系统，其具有如下特点：

  1. 每个键值对都不打，小于10KB
  2. 可以存储大数据
  3. 高可用性，即使发生故障，系统也能迅速响应
  4. 高可扩展性，系统可以扩展以支持大数据集
  5. 自动伸缩，可以基于流量自动添加移除服务器
  6. 可调节的一致性
  7. 低延时

单服务器的键值存储

开发运行在单服务器上的键值存储系统很容易，直观方法就是将键值对存储在哈希表中，将所有数据都保存到内存里。空间有限，为了在单服务器上存储更多数据，可以从两方面优化：

  1. 压缩数据
  2. 只把频繁使用的数据存储在内存里，其他的则放在硬盘上

分布式键值存储

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

CAP 理论

CAP 理论提出，一个分布式系统最多只能同时满足下面三个特性的其中两个：一致性 Consistency、可用性 Availability、分区容错性 Partition Tolerance。

  1. 一致性：指的是所有的客户端在相同的时间点看到的是同样的数据，不管它们连接的是哪个节点。
  2. 可用性：指的是即便有节点发生故障，任意客户端发出的请求都能被响应
  3. 分区容错性：分区意味着两个节点之间的通信终端，分区容错性的意思是尽管网络被分区，系统依然可以继续运行。
图6-1
  1. CP 一致性和分区容错性 系统，支持一致性和分区容错性，但牺牲了可用性。
  2. AP 可用性和分区容错性 系统：支待可用性和分区容错性 ，但牺牲了一致性。
  3. CA 一致性和可用性 系统：支持一致性和可用性，但牺牲了分区容错性 。因为网络故障是无法避免的，所以分布式系统必须容忍网络分区。因此，在现实世界中 CA 系统不可能存在 。
图6-3

在分布式系统中，数据通常会被复制多次，假设数据在3个副本节点上 n1、n2、n3 被复制。

理想世界，网络分区从不发生，写入节点n1的数据会被自动复制到节点n2和n3，这样一致性和可用性都满足了。

真实世界，分区无法避免，必须在一致性和可用性之间做选择，n3 宕机 并且无法与节点n1 和 n2 通信，往 n1 和 n2 写数据，数据无法传递到n3。写数据到n3 但没传递到n1 、n2 那么n1 和 n2 上的数据就可能是旧的。

选择CP系统（一致性和分区容错性），要阻止向n1和n2的写操作，进而避免三个服务器之间的数据不一致。比如银行业务对一致性要求很高。因网络分区导致一致性问题发生，银行系统在不一致性问题被解决前会一直返回错误。

选择AP系统（可用性和分区容错性），系统可以继续接受读操作，尽管它返回的有可能是旧数据，节点n1和n2会继续接受写操作，当网络分区问题被解决后，数据会被同步到节点3。

系统组件

用来构建键值存储系统的核心组件和技术：

  1. 数据分区
  2. 数据复制
  3. 一致性
  4. 不一致性的解决方案
  5. 处理故障
  6. 系统架构图
  7. 写路径
  8. 读路径

数据分区

把数据分割为小的分区并把它们存储在多个服务器中，对数据分区时有两个挑战

  1. 将数据均匀地分布在多个服务器上
  2. 添加或者移除节点时，尽量减少数据的迁移

这可用上一章节学习到 一致性哈希 来进行数据分区，有以下好处

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

数据复制

为了实现高可用性和可靠性，数据必须在N个服务器上异步复制，这里N是一个可配置的参数。如：

当一个键被映射到哈希环上的某个位置后，从这个位置开始顺时针遍历哈希环，找到先遇到的N个服务器来存储数据副本（因为有虚拟节点，指选择不重复的服务器）。

即使一个数据中心发生故障，其他数据中心仍然可以提供服务，确保系统的可用性和容错性。

图6-5

一致性

因为数据被复制到多个节点上，所以副本之间必须同步，仲裁一致性（Quorum Consensus）可以保证读写操作的一致性。

W=1，并不意味着数据只被写入一个服务器。W=1 意味着协调者必须至少收到一 个副本的确认才会认为 写操作成 功。收到一个确认，不再等待其他确认，协调者起到 客户端和节点 之间代理人的作用。

图6-6

如果 W+R>N ，意味着在进行读或写操作时，至少会有一个共同的副本同时参与。这个共同的副本会包含最新的数据， 因此在这种情况下可以保证强一致性。

  1. R=1 W=N 则系统针对快速读进行了优化
  2. W=1 R=N 则系统针对快速写进行了优化
  3. W + R > N 则强一致性得到保证
  4. W + R <= N 则不一定能保证强一致性

一致性模型

一致性模型有多种不同类型，每种类型定义了数据一致性的程度。

  1. 强一致性模型：任何读操作返回的值都是最新写入的数据。客户端永远不会看到过时的数据。
  2. 弱一致性模型：随后的读操作返回的可能不是最新的值。
  3. 最终一致性模型：这是弱一致性的 一种特殊形态。经过足够长的时间，所有的数据更新都会传播开来，并且所有副本会变得一致 。

强一致性模型通常通过强制一个副本在当前写入操作成功之前，不再接收新的（读、写）操作来实现，可能会阻塞新的操作。

最终一致性模型，通过并行写，允许不一致的值进入系统，并强制客户端读取这些值来进行协调。

一致性复制副本版本控制

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

复制副本提供了高可用性但会导致副本之间的数据不一致。版本控制和向量时钟被用来解决这些不一致间题。

版本控制的意思是每次修改数据都生成一个新的不可变的数据版本。

图6-7

server1 把 name 的值修改，server2 也把 name 的值修改。同时改变形成了冲突。

图6-8

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

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

图6-9

例如 D([s0, 1], [s1, 1]) 就是 D([s0, 1], [s1, 2]) 的祖先，如 D([s0, 1], [s1, 2]) 和 D([s0, 2], [s1, 1]) 存在冲突。

处理故障

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

全对全多播（All-to-ALl Multicasting）是一个简单的解决方案。但有很多服务器时，方法效率很低。

图6-10

使用去中心化的故障检测方法，如 Gossip 协议，更好：

  1. 每个节点维护一个节点成员列表，其中包括成员 1D 和心跳计数。
  2. 每个节点定期地增加自己的心跳计数 。
  3. 每个节点定期地给一组随机节点发送心跳信号，这些节点又会将心跳信号接着传递给另一组节点。
  4. 一 旦节点 收到心跳信号，就会据此更新成员列表。
  5. 如果心跳计数在预定时间内没有增加，该成员就被认为宕机了 。
图6-11

处理临时故障

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

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

如果一个服务器因为网络或者服务器故障而不可用，另一个服务器会临时处理请求。 当该服务器恢复运行时，变更会被推送回来以实现数据一致性 。这个过程被称为暗示性传 递 ( Hinted Handoff) 。

图6-12

因为服务器s2不可用，读 写 操作将由服务器s3临时处理，当s2恢复在线时，s3会把数据发回s2

处理永久故障

暗示性传递被用来处理临时故障，一个副本永久不可用该怎么办？

反墒协议 较副本上的每条数据并将每个副本都更新到最新的版本。 Merkle 树被用来检测不一致性并最小化数据传输量。

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

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

图6-13

第二步，一旦创建了桶，把桶里的每个键都用一致性哈希方法计算哈希值。

图6-14

第三步，为每个桶创建一个哈希节点

图6-15

第四步，向上构建树，直到根节点，通过计算子节点的哈希值来得到父节点的哈希值

图6-16

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

处理数据中心故障

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

系统架构图

图6-17
  1. 客户端与键值存储系统之间通过简单API通信
  2. 协调者是一个节点，在客户端与键值存储系统之间充当代理
  3. 节点通过一致性哈希分布在哈希环上
  4. 系统完全去中心化，所以添加和移除节点的工作完全可以自动进行
  5. 数据被复制到多个节点
  6. 因为每个节点有同样的职责，所以没有单点故障

每个节点都需要执行下面任务，客户端API、故障检测、解决冲突、故障修复机制、复制、存储引擎 等等。

写路径

写请求被导向某个特定节点后会发生什么，面推荐的关千写／读路径的设计主要基千 Cassandra 的架构气

图6-19
  1. 写请求在提交日志（Commit Log）文件中被持久化
  2. 数据被保存在内存缓存中
  3. 当内存缓存已满或者达到预定的阙值时， 数据会被刷新到硬盘上的 SSTable。请注意，SSTable Sorted-String Table，有序字符串表是 一个排过序的 ＜键 ，值＞ 对列表。

读路径

在一个请求被导向某个特定节点后，系统会先检查数据是否在内存缓存中，如果是，数据被 返回给客户端。

图6-20

如果数据不在内存缓存中，系统会从硬盘检索数据 。用一个高效的方法来找出哪个 SSTable 包含所需的数据。 布隆过滤器 ( Bloom Filter ) 通常被用来解决这个问题。

图6-21