现在主流的分布式集群一致性问题大多都吸收了PAXOS算法的思想。然而,如果完全按照Leslie Lamport的论文,实现复杂度比较高。因此,大多数实现都采用PAXOS的某种变形。Lamport的重要贡献,献是把分布式一致性的问题,形式化并给出了证明,给出了理论指导。

为简化实现,常见的分布式系统或者是采用Master-Slaves结构,或者是采用某种随机算法,防止破坏一致性。例如,传统的以太网CSMA/CD的算法实际上就是一种解决分布式一致性的随机算法。一般来说,有Master的集群,结构更简单。下面是我整理出来的一种的Master节点选举算法,除了PAXOS外,还借鉴了OSPF协议的设计。

说明:

每个服务器都有一个“标识-纪元”对:(id, epoch)

其中,id是启动节点时的统一分配的数字标识。Epoch是集群数据的版本,每次修改集群中的数据,epoch都递增1。

Master从epoch最大的节点中选出。如果epoch相等,则选择id最小的节点。

 

与每个节点建立连接后,首先会得到对方(id, epoch, master_id)。

 

节点启动时,epoch设置为0,master_id和candidate_id都设为无效值。

算法描述:

与每个节点建立连接后,首先会得到对方(id, epoch)。

I.        启动选举超时定时器。

若以前有定时器,则重启。若超过时间t,则转到V。

II.       Master发现。

若超时时间内发现Master可用,则取消定时器,转到VI。

III.     更新Candidate。

找出所有节点中(id, epoch)符合Master候选条件的节点,标记为候选者Candidate。若Candidate发生变化,则转到I。

IV.     候选阶段。

等待候选计时器超时,如果期间有节点加入或离开,则转到II。

V.       标记阶段

标记Candidate为Master。

VI.     Master选举完成。

其中,引入超时t,可以避免多个服务器同时启动时,导致Master选举抖动。第II步和第IV步可以用于处理节点崩溃的情况。

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注