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

wangfans

　`灵活性。乍看上去，故障检测只需要输出一个表明被监控进程是否处于工作状态的布尔值，但在实际应用中这是不够的。我们来看参考资料[12]中的一个类似MapReduce的例子。有一个由一个主节点和若干工作节点组成的分布式应用，主节点维护一个作业列表，并将列表中的作业分配给工作节点。主节点能够区分不同程度的失败

wangfans

如果主节点怀疑某个工作节点挂了，他就不会再给这个节点分配作业。其次，随着时间推移，如果没有收到该节点的心跳信息，主节点就会把运行在这个节点上的作业重新分配给别的节点。最后，主节点确认这个节点已经失效，并释放所有相关资源。

wangfans

　`可扩展性和健壮性。失败检测作为一个系统功能应该能够随着系统的扩大而扩展。他应该是健壮和一致的，也即，即使在发生通讯故障的情况下，系统中的所有节点都应该有一个一致的看法(即所有节点都应该知道哪些节点是不可用的，那些节点是可用的，各节点对此的认知不能发生冲突，不能出现一部分节点知道某节点A不可用，而另一部分节点不知道的情况)

wangfans

所谓的累计失效检测器[12]可以解决前两个问题，Cassandra[16]对它进行了一些修改并应用在产品中。其基本工作流程如下：
　　`对于每一个被监控资源，检测器记录心跳信息到达时间Ti。
　　`计算在统计预测范围内的到达时间的均值和方差。

wangfans

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

wangfans

wangfans

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

wangfans

wangfans

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

wangfans

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