设计一个键值数据库，支持以下操作：

• put(key, value)
• get(key)

其中key是唯一的，value可以是任何类型。

明确需求

这里以满足以下要求为例设计键值数据库：

• 每个键值对大小不超过10KB
• 能够存储海量的键值对
• 高可用性：响应迅速，即使服务端出现错误
• 高可扩展性：可扩展以支持海量数据
• 自动扩展：可根据流量自动增加或删除服务器
• 可调整的数据一致性
• 低延迟

单服务器的键值数据库

单服务器的设计比较简单，使用一个大的哈希表即可，所有数据存储在内存中。由于内存不可能无限大，所以要进行优化，比如使用数据压缩技术，或是将不常使用的数据存储到磁盘。

即使应用优化措施，单服务器也难以应对海量数据的存储，必须要使用分布式设计来支持海量数据。

分布式键值数据库

也称为分布式哈希表，使用分布式环境来存储键值。设计分布式系统时，需要了解CAP原则。CAP是指一致性（Consistency）、可用性（Availability）、部分容错性（Partition Tolerance）。

CAP原则描述的是一个分布式系统最多只能同时满足CAP中的两项，不可能同时满足三项。根据侧重点的不同，分布系统可以有以下几种类型：

CP系统：满足一致性和部分容错能力，以牺牲可用性为代价。

AP系统：满足可用性和部分容错能力，以牺牲一致性为代价。

CA系统：满足一致性和可用性，不支持部分容错。因为现实环境中系统总有可能出现异常情况，所以这种系统在现实世界并不存在。

以下面的分布式系统为例，这里有n1~n3三个结点，数据需要同时在n1~n3上复制存储：

理想情况下，网络分区（network partiton）不会发生。写向n1的数据可以自动复制到n2和n3，一致性和可用性都能满足。

现实场景中，网络分区无法避免，当某个结点发生网络分区时（并不一定是宕机和停止服务，也可能只是单纯因为网络问题导致与其他结点无法通信，而结点本身仍然是处于正常状态的），系统必须在高可用性和高一致性之间作出选择，这里以n3出现故障为例进行说明：

当n3出现故障时，如果客户端写n1和n2，那么数据不能被同步到n3，如果客户端写n3，那n1和n2无法从n3同步数据，即n1和n2的数据有可能过时。

如果系统优先考虑一致性，那当n3出现故障后，系统应该立即停止任何对n1和n2的读写操作，以避免数据不一致，这就导致可用性无法满足。

如果系统优先考虑可用性，则n3出现故障后，n1和n2仍旧可供读写，但数据有可能是过时的，这就导致一致性无法满足。

应该根据实际应用场景来选择合适的CAP策略。

系统组件

讨论分布式键值数据库的核心组件：

• 数据分区
• 数据复制
• 一致性
• 非一致性问题处理
• 容错处理
• 系统架构图
• 写过程
• 读过程

数据分区

指的是将数据拆分成几部分存储在不同的服务器上，因为单个的服务器无法满足存储海量数据的需求。数据拆分有以下几项挑战：

• 将数据平均分布到各个服务器
• 在增加或删除服务器时，尽量减少数据的移动

前一章节讨论的一致性哈希可用于解决上述问题，这里简要描述一下过程：

1. 服务器按哈希值映射到哈希环上，下面的例子包含s0~s7共8个服务器
2. 将key也按相同的哈希算法映射到哈希环上，并将数据存储在顺时钟方向上第一个相邻的服务器，这里key0存储在s1中。

根据负载情况，服务器可自动增加或删除。可按服务器的存储能力比例分配虚拟结点的数量，比如大容量的服务器可分配较多的虚拟结点。

数据复制

为提高可用性和可靠性，数据一般会通过异步复制技术存储在N台服务器上，N是一个可配置的参数。这里的N台服务器可以用下面的方式来选择：

• 当把key映射到哈希环上后，按顺时针方向选择前N个服务器进行存储，比如在下面的示例中，N=3，key0被存储在s1,s2,s3中。

如果使用了虚拟结点，则在选择前N个服务器时应跳过属于同一个服务器的虚拟结点。

一致性

数据在多个结点之间复制时必须保证同步。Quorum机制（参考Quorum (分布式系统) - 维基百科，自由的百科全书）可用于保证在读写时的一致性。以下是一些相关的定义：

N = 复制数

W = 写票数，写操作需要至少收到W份写成功的响应才算写成功

R = 读票数，读操作需要至少收到R份读成功的响应才算写成功

以下面的示例来说明Quorum机制，这里N = 3。

W = 1并不是表示数据只会存储在一个服务器上，而是指在写s0~s2时，只要收到至少一个写成功的响应，就认为已写入成功，换句话说，数据有可能在s0~s2上都写成功了，但只要收到了其中一个的响应，写操作就会成功返回，而不再等待另外两个结点的响应。

对W, R, N的配置决定了系统的响应延迟和数据一致性。如果W=1或N=1，则任何读写操作都会快速返回，因为只要收到1个成功响应就认为操作成功。如果W或R大于1，则响应会慢一些，因为要等多个结点响应操作成功，但一致性会更好。

如果W + R > N, 则系统有较强的一致性，因为可以保证系统至少有一个重叠的结点存储的数据是最新的。以下是一些可能的W,N, R配置及其效果：

• 如果R = 1并且W = N，则系统优化为支持快速读取。
• 如果W = 1并且 R = N，则系统优化为支持快速写入。
• 如果W + R > N，则系统保证了较强的一致性（通常是N=3, W = R = 2）。
• 如果 W + R < N，则系统并不保证强一致性。

根据实际场景，可灵活配置W,R,N以适应需求。

关于一致性模型：

强一致性：总是保持所有数据最新，客户端不会读到过时数据

弱一致性：客户端有可能读到过时的数据

最终一致性：客户端有可能读到过时数据，但给予系统足够的时间，所有数据会最终同步到最新

强一致性一般是通过在更新数据之前屏蔽所有的读写操作来实现的，不适合高可用性系统。如果使用最终一致性模型，则客户端有可能读到两份不同的数据，这里需要由客户端处理冲突。

非一致性问题处理：版本管理

数据复制在提供了高可用性的同时也导致了数据在各备份结点不一致的问题，版本管理和向量时钟算法（vector clock）可用于解决该问题。版本管理的意思是把每次对数据的修改当成一个新的版本来对待，而向量时钟算法则是一种生成版本信息和判断版本冲突的算法，参考vector clock向量时钟算法简介 - 简书。

容错

错误检测

分布式环境，仅凭一台服务器的反馈并不足以判断某个服务器是否宕机。通常，至少需要两台服务器独立上报消息才能判断某个服务器确实已出现错误。

服务器集群之间可以通过心跳保活来保持在线，但当系统规模较大时，维持所有服务器之间都相互保活是比较困难的，因此，更常见的做法是一台服务器只与某几个服务器进行保活，然后通过八卦协议（gossip protocol）来判断某个服务器是否已下线。

八卦协议工作流程如下：

• 每个结点维护一个伙伴结点列表（部分结点即可，不需要全部结点），其中记录每个伙伴的ID和保活计数。
• 每个结点都定期对自己的保活计数进行自增。
• 每个结点都周期性地将自己的保活计数（只发自己的保活计数，不包括伙伴结点的保活计数）发送给随机的几个结点（随机发送，不是发送给伙伴结点），这些结点收到后也会再随机选几个结点广播自己的保活计数
• 一旦一个结点收到了伙伴结点的保活计数，马上更新自己的伙伴结点列表。
• 如果发现列表中的某个结点长时间未更新保活计算，则认为这个节点已下线。

关于gossip协议的具体内容可参考P2P 网络核心技术：Gossip 协议 - 知乎。

处理临时错误

当通过八卦协议检测到错误结点后，应该立即处理该错误。在严格的Quorum机制下，应该立刻限制对其他结点的读写操作，但这样会降低可用性。一种被称为“松散Quorum机制”的方法可用于提高可用性。不同于严格执行Quorum投票算法，系统可以选择前W个可用的服务器用于写操作，选择前R个可用的服务器用于读操作，忽略下线的服务器。

当服务器因为网络问题或服务器问题掉线时，另一个服务器会暂时代替该服务器处理用户请求。当掉线的服务器再次上线时，临时服务器会将修改同步回去，以保证数据一致性，这个过程称为提示交接（hinted handoff）。

处理永久错误

提示交接可用于处理临时错误，但当结点永久下线时，该如何处理呢？当结点下线时，剩余结点应该进行数据同步，同步的原理和上面的八卦协议一样，都是通过结点间自发的交换数据来实现数据一致。这里可以使用哈希树（hash tree；Merkle tree）算法来检测数据是否一样并将数据搬移量降到最低。

哈希树的生成过程如下，这里以两台服务器，每台服务器存储了12个数据为例，标记为红色的结点是两台服务器上不一致的数据：

Step 1：把每台服务器上的数据都按顺序分成4组，每组包含3个数据

Step 2：计算所有数据的哈希值

Step 3：计算每组数据的哈希值

Step 4：从下往上构造哈希树，直到根结点
 

构造好两台服务器的哈希树之后，接下来在数据同步时，只需要从根结点开始，依次往下比较各个结点的哈希值是否一致，再将不致的结点进行同步即可。以上面的两棵哈希树为例，如果根结点相同，则表示两个服务器上的数据完全一致不需要同步。如果根结点不致，则比较左右子结点，同样跳过哈希值一致的结点，只从哈希值冲突的结点开始，递归进行比较，直到找到数据不一致的数据分组，再进行数据同步即可。

处理数据中心宕机

在各数据中心之间维护数据备份，处理方式和前面描述的一样，这样，一个数据中心宕机，只需要把请求转向另一个服务器即可。

系统架构设计

主要特性如下：

• 只提供get(key)和put(key, value)两个API接口供客户使用
• 客户端通过代理与整个键值数据库进行通信
• 存储结点通过哈希一致性算法分布在环上
• 系统使用去中心化设计，节点可自动增加或删除
• 数据在多个结点上复制存储
• 不存在单点故障问题，每个节点都是对等的，当代理节点出现问题时，客户端可以转换到另一个节点进行通信

由于使用去中心化设计，所以每个节点都要具备相同的功能，如下：

写过程

步骤如下：

1. 写请求首先保存到日志上，以供后续查询
2. 数据保存在服务器的内存缓存中
3. 通过缓存淘汰策略将被淘汰的缓存写到磁盘上，通过排序字符串表（sorted-string table）进行存储，方便快速查找。

读过程

读过程分两种情况讨论，一是数据保存在缓存中，则直接从缓存返回结果即可。

如果数据不在缓存中，则要从磁盘中查找，可使用布隆过滤器来提高查找效率，整个过程如下：

1. 首先判断查找的key是否在内存缓存中，如果不在，则执行步骤2
2. 查找布隆过滤器，找到目的key在哪个排序字符串表上
3. 排序字符串表返回结果
4. 结果返回给客户端

总结