分布式键值系统的核心组件与技术

数据分区

有两个挑战：

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

使用一致性哈希进行数据分区。

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

数据复制
为了实现高可用性和可靠性，数据必须在N个服务器上异步复制。N是一个可配置的参数。
当一个键被映射到哈希环上的某个位置后，从这个位置开始顺时针遍历环，找到先遇到的N个服务器来存储副本。使用虚拟节点时，最先找到的N个节点对应的物理服务器数量有可能小于N，针对该问题，在执行遍历逻辑时，只选择不重复的服务器。

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

N: 代表副本的数量
W: 代表写操作的Quorum大小。一个写操作要被认为成功，必须获得W个副本的确认
R: 代表读操作的Quorum大小。一个读操作要被认为成功，必须获得R个副本的响应。

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， 不能保证强一致性。

一致性模型：

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

强一致性模型通常是通过强调一个副本在当前写操作成功之前不再接收新读写操作来实现的。它可能会阻塞新的操作，对于高可用系统不完美。
推荐最终一致性模型，Dynamo和Cassandra也是采用该模型。

不一致性的解决方案
版本控制和向量时钟用来解决这些不一致问题。

版本控制：每次修改数据都生成一个新的不可变的数据版本。
向量时钟：是与数据项相关联的[服务器，版本]对。
向量时钟缺点：

• 增加了客户端的复杂性，客户端需要实现冲突解决逻辑。
• 向量时钟中的[服务器，版本]数据可能会迅速增长。针对该问题设定一个长度阈值，超过阈值移除最老的数据对。¹

处理故障

• 故障检测：通常，至少需要两个独立的信息源才能标记一个服务器出故障了。
  • 全对全多播，是一个简单明了的方案。如果系统中服务器很多，效率较低。
  • 去中心化的故障检测方法，如Gossip协议，是更好的方案。

    Gossip协议工作原理

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

• 处理临时故障
  Gossip协议发现故障后，系统需要采取某种机制来确保可用性。
  一种叫**“松散仲裁”(Sloppy Quorum)¹的技术被用来提高可用性。这种技术选择在哈希环上最先发现的W个正常工作的服务器进行写操作，并选择在哈希环上最先发现的R个正常工作的服务器进行读操作。忽略发生故障的服务器。
  如果一个服务器因为网络或故障不可用，另一个服务器会临时处理请求，当该服务器恢复运行时，变更会被推送回来以实现数据一致性。这个过程叫暗示性传递**(Hinted Handoff)。
• 处理永久故障
  如果副本永久不可用了，通过实现反熵协议(Anti-entropy Protocol)来保持副本同步。反熵需要比较副本上的每条数据并将每个副本更新到最新的版本。Merkle树用来检测不一致性并最小化数据传输量。
• 处理数据中心故障
  在多个数据中心之间复制数据至关重要。

写路径
基于Cassandra架构：

• 写请求在提交日志(Commit Log)文件中被持久化；
• 数据写入内存缓存中；
• 内存已满或是达到阈值，数据刷新到硬盘上的SSTable²,

读路径
基于Cassandra架构：

1. 检查数据是否在内存缓存中，如果不在转2；
2. 检查布隆过滤器；
3. 通过布隆过滤器确定在哪个SSTable可能包含这个键；
4. SSTabel返回结果数据；
5. 结果数据返回给客户端。

系统架构图

• 客户端与KV系统之间通过简单的API通信：get(key)和put(key, value)。
• 协调者是一个节点，在客户端与KV系统之间充当代理。
• 节点通过一致性哈希分布在哈希环上。
• 系统完全去中心化
• 数据复制到多个节点上。
• 每个节点有同样的职责，没有单点故障。