深入解析NoSQL数据库的分布式算法

上面分析中的一些权衡有必要再强调一下

• 一致性与可用性。 严密的权衡已经由CAP理论给出了。在网络隔离的情况下，数据库要么将数据集中，要么既要接受数据丢失的风险。
• 一致性与扩展性。 看得出即使读写一致性保证降低了副本集的扩展性，只有在原子写模型中才可以以一种相对可扩展的方式处理写冲突。原子读改写模型通过给数据加上临时性的全局锁来避免冲突。这表明， 数据或操作之间的依赖，即使是很小范围内或很短时间的，也会损害扩展性。所以精心设计数据模型，将数据分片分开存放对于扩展性非常重要。
• 一致性与延迟。 如上所述，当数据库需要提供强一致性或者持久性的时候应该偏向于读写所有副本技术。但是很明显一致性与请求延迟成反比，所以使用若干副本技术会是比较中允的办法。
• 故障转移与一致性/扩展性/延迟。有趣的是容错性与一致性、扩展性、延迟的取舍冲突并不剧烈。通过合理的放弃一些性能与一致性，集群可以容忍多达 up to 的节点失效。这种折中在两阶段提交与 PAXOS 协议的区别里体现得很明显。这种折中的另一个例子是增加特定的一致性保障，比如使用严格会话进程的“读己所写”，但这又增加了故障转移的复杂性。

反熵协议， 谣言传播算法

　　让我们从以下场景开始：

　　有许多节点，每条数据会在其中的若干的节点上面存有副本。每个节点都可以单独处理更新请求，每个节点定期和其他节点同步状态，如此一段时间之后所有的副本都会趋向一致。同步过程是怎样进行的？同步何时开始？怎样选择同步的对象？怎么交换数据？我们假定两个节点总是用较新版本的数据覆盖旧的数据或者两个版本都保留以待应用层处理。

　　这个问题常见于数据一致性维护和集群状态同步（如集群成员信息传播）等场景。虽然引入一个监控数据库并制定同步计划的协调者可以解决这个问题，但是去中心化的数据库能够提供更好的容错性。去中心化的主要做法是利用精心设计的传染协议，这种协议相对简单，但是提供了很好的收敛时间，而且能够容忍任何节点的失效和网络隔离。尽管有许多类型的传染算法，我们只关注反熵协议，因为NoSQL数据库都在使用它。

　　反熵协议假定同步会按照一个固定进度表执行，每个节点定期随机或是按照某种规则选择另外一个节点交换数据，消除差异。有三种反风格的反熵协议：推，拉和混合。推协议的原理是简单选取一个随机节点然后把数据状态发送过去。在真实应用中将全部数据都推送出去显然是愚蠢的，所以节点一般按照下图所示的方式工作。

　　节点A作为同步发起者准备好一份数据摘要，里面包含了A上数据的指纹。节点B接收到摘要之后将摘要中的数据与本地数据进行比较，并将数据差异做成一份摘要返回给A。最后，A发送一个更新给B，B再更新数据。拉方式和混合方式的协议与此类似，就如上图所示的。

　　反熵协议提供了足够好的收敛时间和扩展性。下图展示了一个在100个节点的集群中传播一个更新的模拟结果。在每次迭代中，每个节点只与一个随机选取的对等节点发生联系。

　　可以看到，拉方式的收敛性比推方式更好，这可以从理论上得到证明。而且推方式还存在一个“收敛尾巴”的问题。在多次迭代之后，尽管几乎遍历到了所有的节点，但还是有很少的一部分没受到影响。与单纯的推和拉方式相比， 混合方式的效率更高，所以实际应用中通常使用这种方式。反熵是可扩展的，因为平均转换时间以集群规模的对数函数形式增长。

　　尽管这些技术看起来很简单，仍然有许多研究关注于不同约束条件下反熵协议的性能表现。其中之一通过一种更有效的结构使用网络拓扑来取代随机选取 。在网络带宽有限的条件下调整传输率或使用先进的规则来选取要同步的数据 。摘要计算也面临挑战，数据库会维护一份最近更新的日志以有助于摘要计算。

最终一致数据类型Eventually Consistent Data Types

　　在上一节我们假定两个节点总是合并他们的数据版本。但要解决更新冲突并不容易，让所有副本都最终达到一个语义上正确的值出乎意料的难。一个众所周知的例子是Amazon Dynamo数据库中已经删除的条目可以重现。

　　我们假设一个例子来说明这个问题：数据库维护一个逻辑上的全局计数器，每个节点可以增加或者减少计数。虽然每个节点可以在本地维护一个自己的值，但这些本地计数却不能通过简单的加减来合并。假设这样一个例子：有三个节点A、B和C，每个节点执行了一次加操作。如果A从B获得一个值，并且加到本地副本上，然后C从B获得值，然后C再从A获得值，那么C最后的值是4，而这是错误的。解决这个问题的方法是用一个类似于向量时钟的数据结构为每个节点维护一对计数器：

[js] view plaincopy

1. 1 class Counter {  
2. 2     int[] plus   
3. 3     int[] minus   
4. 4     int NODE_ID   
5. 5   
6. 6     increment() {   
7. 7         plus[NODE_ID]++   
8. 8     }   
9. 9   
10. 10    decrement() {   
11. 11        minus[NODE_ID]++   
12. 12    }   
13. 13   
14. 14    get() {   
15. 15        return sum(plus) – sum(minus)   
16. 16    }   
17. 17   
18. 18    merge(Counter other) {   
19. 19        for i in 1..MAX_ID {   
20. 20            plus[i] = max(plus[i], other.plus[i])   
21. 21            minus[i] = max(minus[i], other.minus[i])   
22. 22        }  
23. 23    }   
24. 24 } 
    

　　Cassandra用类似的方法计数。利用基于状态的或是基于操作的复制理论也可以设计出更复杂的最终一致的数据结构。例如，中就提及了一系列这样的数据结构，包括：

• 计数器（加减操作）
• 集合（添加和移除操作）
• 图（增加边或顶点，移除边或顶点）
• 列表（插入某位置或者移除某位置）

　　最终一致数据类型的功能通常是有限的，还会带来额外的性能开销。

数据放置

　　这部分主要关注控制在分布式数据库中放置数据的算法。这些算法负责把数据项映射到合适的物理节点上，在节点间迁移数据以及像内存这样的资源的全局调配。