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

wangfans

`假定到达时间的分布已知(下图包括一个正态分布的公式)，我们可以计算心跳延迟(当前时间t_now和上一次到达时间Tc之间的差值) 的概率，用这个概率来判断是否发生故障。如参考资料[12]中所建议的，可以使用对数函数来调整它以提高可用性。在这种情况下，输出1意味着判断错误(认为节点失效)的概率是10%，2意味着1%，以此类推。

wangfans

wangfans

根据重要程度不同来分层次组织监控区，各区域之间通过谣言传播协议或者中央容错库同步，这样可以满足扩展性的要求，又可以防止心跳信息在网络中泛滥[14]。如下图所示(6个故障检测器组成了两个区域，互相之间通过谣言传播协议或者像ZooKeeper这样的健壮性库来联系)：

wangfans

wangfans

协调者竞选
　　协调者竞选是用于强一致性数据库的一个重要技术。首先，它可以组织主从结构的系统中主节点的故障恢复。其次，在网络隔离的情况下，它可以断开处于少数的那部分节点，以避免写冲突。

wangfans

Bully 算法是一种相对简单的协调者竞选算法。MongoDB 用了这个算法来决定副本集中主要的那一个。Bully 算法的主要思想是集群的每个成员都可以声明它是协调者并通知其他节点。别的节点可以选择接受这个声称或是拒绝并进入协调者竞争。被其他所有节点接受的节点才能成为协调者。节点按照一些属性来判断谁应该胜出。这个属性可以是一个静态ID，也可以是更新的度量像最近一次事务ID(最新的节点会胜出)。

wangfans

下图的例子展示了bully算法的执行过程。使用静态ID作为度量，ID值更大的节点会胜出：
　　1.最初集群有5个节点，节点5是一个公认的协调者。
　　2.假设节点5挂了，并且节点2和节点3同时发现了这一情况。两个节点开始竞选并发送竞选消息给ID更大的节点。
　　3.节点4淘汰了节点2和3，节点3淘汰了节点2。

wangfans

.这时候节点1察觉了节点5失效并向所有ID更大的节点发送了竞选信息。
　　5.节点2、3和4都淘汰了节点1。
　　6.节点4发送竞选信息给节点5。
　　7.节点5没有响应，所以节点4宣布自己当选并向其他节点通告了这一消息。

wangfans

wangfans

者竞选过程会统计参与的节点数目并确保集群中至少一半的节点参与了竞选。这确保了在网络隔离的情况下只有一部分节点能选出协调者(假设网络中网络会被分割成多块区域，之间互不联通，协调者竞选的结果必然会在节点数相对比较多的那个区域中选出协调者，当然前提是那个区域中的可用节点多于集群原有节点数的半数。如果集群被隔离成几个区块，而没有一个区块的节点数多于原有节点总数的一半，那就无法选举出协调者，当然这样的情况下也别指望集群能够继续提供服务了)。