分布式一致性算法:可能比你想象得更复杂

1.分布式系统的难题

张大胖遇到了一个难题。

他们公司的有个服务器,上面保存着宝贵的数据,领导Bill 为了防止它挂掉, 要求张大胖想想办法把数据做备份。

张大胖发挥了抽象的能力,在脑海里浮出了这么一个画面, 这个唯一的机器可以成为一个节点:

为了提高可用性,可以增加几台机器,通过局域网连接起来,形成一个了分布式的系统:

数据在每个节点上都存放一份不就可以高枕无忧了?

可张大胖很快发现这不是一件容易的事情,比如每个节点都保存着一个账户的余额100元,现在有人通过节点A向该账户增加了20元, 还有人通过节点B向该账户减去了30元。

现在余额到底是多少呢?

为了保持一致性, 节点A得把"余额加上20"这样的消息发给B, C , 节点B得把“余额减去30”这样的消息发送到A, C, 如果网络出了问题,消息没有发送到别的节点, 或者某个节点干脆坏掉了,那数据极有可能出现不一致。

如果用户在这个不一致的系统上继续操作,很快就会陷入混乱。

2.谁来当老大?

张大胖想了半天,觉得不能这么无序地操作,得给这三个节点找个“老大”。

所有的操作都通过“老大”来进行,然后让老大把消息发给各个“小弟”。

可是谁来当老大呢?  还有,这个老大如果挂掉了怎么办?

可以手工地调整, 例如节点A挂掉了, 就手工地让节点B当“老大” , 让节点C当“小弟”。

但是这就有点麻烦了,能不能自动化地来实现?

这个问题很有意思, 张大胖入了迷,继续深入思考: 建立一个竞选的机制, 就让他们竞争上岗吧。

初始情况下,每个节点都是候选人, 都可以向其他节点发起投票邀请,让大家投自己,如果获得的投票数过半,就可以当“老大”了。

为了避免大家同时发起投票邀请,可以给每个节点都分配一个随机的“选举超时时间”(election timeout),通俗来讲就是一个等待时间,在这段时间内,一个节点必须耐心等待,过了这段时间,才可以竞争上岗,争当老大。

每个节点都有一个计时器,从0开始计时,谁的等待时间到了, 就率先发起竞选,给其他节点打电话,要求他们投票让自己成为老大。

比如节点A等待170ms , 节点B等待200ms ,  节点C等待250ms 。

由于节点A的等待时间最短, 会捷足先登, 它先增加自己的任期(Term),这是一个整数,初始值为0 , 然后给自己投了一票,然后打电话给节点B和节点C,要求他们都投它。

节点B和节点C收到了投票要求,如果自己还没有发起竞选投票(等待时间未到),那只好同意节点A当老大,与此同时要重置自己的计时器,重新从0开始计时,也就是说重新开始新一轮的等待。

节点A得知其他两个节点同意了,投票计数变为3,已经过了半数, 就明白自己可以当老大了。

节点A成为老大后,开始向节点B和节点C定时发送消息,B,C收到消息后也要回应,维持心跳。

B和C每次收到心跳消息,都得重置自己的计时器, 重新从0开始计数。

此时节点B和节点C就成了“小弟”。

如果节点A 不幸挂掉,节点B和节点C在自己的等待时间内收不到心跳消息,他们两个就会重新竞争上岗。