深入理解NoSQL数据库分布式算法及策略

wangfans

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

wangfans

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

wangfans

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

wangfans

wangfans

Cassandra用类似的方法计数[11]。利用基于状态的或是基于操作的复制理论也可以设计出更复杂的最终一致的数据结构。例如，[1]中就提及了一系列这样的数据结构，包括：
　　·计数器(加减操作)
　　·集合(添加和移除操作)

wangfans

　·图(增加边或顶点，移除边或顶点)
　　·列表(插入某位置或者移除某位置)
　　最终一致数据类型的功能通常是有限的，还会带来额外的性能开销。

wangfans

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

wangfans

均衡数据
　　我们还是从一个简单的协议开始，它可以提供集群节点间无缝的数据迁移。这常发生于像集群扩容(加入新节点)，故障转移(一些节点宕机)或是均衡数据(数据在节点间的分布不均衡)这样的场景。如下图A中所描绘的场景 – 有三个节点，数据随便分布在三个节点上(假设数据都是key-value型)。

wangfans

wangfans

如果数据库不支持数据内部均衡，就要在每个节点上发布数据库实例，如上面图B所示。这需要手动进行集群扩展，停掉要迁移的数据库实例，把它转移到新节点上，再在新节点上启动，如图C所示。尽管数据库能够监控到每一条记录，包括MongoDB, Oracle Coherence, 和还在开发中的 Redis Cluster 在内的许多系统仍然使用的是自动均衡技术。