原文地址

• idea：可扩展、一致性的分布式key-value 存储（evaluation of Scatter, a scalable and consistent distributed key-value storage system）
• key insight：基于DHT 的一致性组
• DHT 功能简介：传统DHT 中，应用数据和节点ID 都哈希为键值key，数值保存在先于或紧接着键值key 的那个节点
• 为什么会发生一致性问题：1.Assignment violation 节点加入或者离开时对keyID 范围的声明的重叠。2.节点加入和离开对临近指针的影响。

Scatter Design

goal：一致性，可扩展性，自适应性

方法：用组来代替单个节点，RSM 基于paxos 一致性算法，组内使用一致性协议维持内部一致性，但是如静态指定组会存在一些问题：

1. 当大量nodes 离开或者加入会使得该组失效
2. 健壮性、可扩展性问题
3. 当组内节点增多，一致性算法性能下降
4. 热点问题

因此Scatter 允许多组操作：

1. split       组一分为二
2. merge   两临近组合二为一
3. migrate 将组员从一组移动到另一组
4. repartition 临近两组交换键值空间

强一致性在拓扑结构不是原子变化的情况下是很难保证的，因此文章引出“自创”的nested consensus 老保证原子性，但实际上nested consensus 就是组内的paxos 算法保证强一致性，组间两阶段提交保证弱一致性。

接着文章从发起方coordinator group，参与方participant group 解释了nested consensus 过程，实际上就是两阶段提交，文章也指出这样的交互过程需要大量的广播和消息，可以作为future work 进行改进。

整个Scatter 系统对外提供存储服务，每个组中会利用paxos 算法选举出一个master，组间交互只通过master，而具体数据时存在组内所有成员，存储对应数据的称为primary。文章谈到了所做的一些性能优化，lease，diskless paxos（信息不用存盘）、relaxed reads 等。

最后进行了测试并与openDHT 比较了consistency。

个人体会：

文章主要是提出了可扩展和一致性的key-value 存储系统，最大的创新在于把传统DHT 中单个节点的方法改成了一个组，节点的加入和退出就限制在了组内，对外这个组的状态和功能还是不变的。为了满足可扩展性，组可以进行分裂合并操作，通过形式上说明和实验组操作的OPs/sec、延时说明这个方法是可行、高效的。一致性是通过paxos 算法和两阶段提交实现，也不能说有新意。文章通过与openDHT 的比较，说明Scatter 不损失性能和可用性的情况下，一致性上比openDHT要好。但我有个小问题，组操作如果是手动的话就谈不上adaptive 了，如果是自动的话，这种组操作在节点加入和离开的时候频不频繁，虽然文章也给出了组操作的thoughput 和latency ，但我觉得这个应该同时进行读写操作才能说明问题，如果在现实情况中组操作严重干扰了用户的正常读写的话，试验中的高性能和可用性就不好说了。