构建一个 Key-Value 存储系统需要考虑的技术问题

1）数据分离。一是如何让数据分布均衡（使用更多的虚拟节点），二是在节点增删时减少数据移动（使负载量大的机器有更多的虚拟节点）。具体实现参考一致性哈希那一章

2）数据复制。为了实现高可用性（始终可读），数据要同步复制到哈希环上首先遇到的 N 个节点上，N 是可配置的，而且要忽略指向相同物理节点的虚拟节点

3）一致性。通过法定人数共识（quorum consensus）控制，N 是副本数，W 是写共识数（必须有 W 次写入才算成功），R 是读共识数。若 R = 1 & W = N，系统为快速读取优化；若 W = 1 & R = N，系统为快速写入优化；若 W + R > N（通常是 N = 3, W = R = 2），系统为强一致性优化；若 W + R <= N，无强一致性保证

4）不一致性处理：记录版本。客户端读到两个不一样的值，单独靠值本身是没办法判断哪个是新值应该用哪个，所以引入版本号，每个值都对于每个服务器都有一个版本，这个叫 vector clock，比如读取到数据在两个节点上的 vector clock 分别为 ([s0, 1], [s1, 1]) 和 ([s0, 1], [s1, 2])，显然后者是新值，因此没有冲突；如果读到的是 ([s0, 1], [s1, 2]) 和 ([s0, 2], [s1, 1])，那就需要处理冲突

5）错误处理。

5.1）发现错误：我们需要多个信息源证实才能认为一个服务器是真的下线了，效率比较高的方式是 Gossip 分布式协议，大概思路是从某个节点开始随机 ping 其他数个节点，并维护一个 member list，其中有每个节点的心跳次数和更新时间，这个 member list 随后会扩散到其它节点，持续这个过程，通过 member list 便可以了解到当某个节点长时间心跳次数没有增长，意味着多个节点都 ping 不通，意味着它可以表现为下线了

5.2）解决临时错误：可以使用被称作 hinted handoff 的方式，比如 s2 被标记下线，就让哈希环上的下一个节点 s3 来接替它，等 s2 上线后再把数据交还给 s3

5.3）解决永久错误：如果对数据丢弃不敏感应该很简单，但这里假设不能丢弃数据。基本思路是做副本（备份），优化方向是副本如何同步，Merkle tree 用于非一致性检测以及使传输的数据最小化，就是把数据分为很小的区块（bucket），比如每个 bucket 有 1000 个键，一共有一百万个 bucket，每个 bucket 计算出一个哈希作为叶子节点，然后向上计算，直到有一个根节点。比较不同服务器上的数据时，就是从 Merkle tree 的根节点开始比较，相同就说明数据相同，不相同就依次递进比较左孩子和右孩子，如此就能够确定需要同步的有差异的数据

6）系统架构总览。本 k-v 存储架构的主要特性：提供 get 和 put 的 API；客户端与一个代理/协调节点交互；一致性哈希；完全去中心化；每个节点的职责相同，且可以自动伸缩

7+8）写入路径+读取路径。这里提供了 Cassandra 的架构介绍，概括来说，写入内存的同时，要将请求持久化（commit log），内存写满了还要持久化到 SSTable，读取则是优先从内存读取，如果内存没有，通过 Bloom Filter 找到数据在哪个 SSTable 里面

各类技术问题以及对应的解决方案