一篇文了解分布式队列编程：从模型、实战到优化(7)

令人遗憾的是,除非工程师们自己在消费者实例里面实现Paxos等算法,并在每次消息处理之前都执行领导人选举.否则,理论上讲,没有方法可以保障在同一个时刻只有一个领导者.而对每个消息都执行一次领导人选举,显然性能不可行.

实际工作中,最容易出现的问题时机发生在领导人交接过程中,即前任领导人实例变成辅助实例,新部署实例开始承担领导人角色.为了平稳过渡,这两者之间需要有一定的通讯机制,但是,无论是网络分区(Network partition)还是原领导人服务崩溃都会使这种通讯机制变的不可能.

对于完整性和一致性要求很高的系统,我们需要在选举制度和交接制度这两块进行优化.

领导人选举架构

典型的领导人选举算法有Paxos、ZAB( ZooKeeper Atomic Broadcast protocol).为了避免重复造轮子,建议采用ZooKeeper的分布式锁来实现领导人选举.典型的ZooKeeper实现算法如下：

Let ELECTION be a path of choice of the application. To volunteer to be a leader:

1.Create znode z with path “ELECTION/guid-n_” with both SEQUENCE and EPHEMERAL flags;

2.Let C be the children of “ELECTION”,and i be the sequence number of z;

3.Watch for changes on “ELECTION/guid-n_j”,where j is the largest sequence number such that j < i and n_j is a znode in C;

Upon receiving a notification of znode deletion:

1.Let C be the new set of children of ELECTION;

2.If z is the smallest node in C,then execute leader procedure;

3.Otherwise,watch for changes on “ELECTION/guid-n_j”,where j is the largest sequence number such that j < i and n_j is a znode in C;

领导人交接架构

领导人选举的整个过程发生在ZooKeeper集群中,各个消费者实例在这场选举中只充当被告知者角色(Learner).领导人选举算法,只能保证最终只有一个Leader被选举出来,并不保障被告知者对Leader的理解是完全一致的.

本质上,上文的架构里,选举的结果是作为令牌(Token)传递给消费者实例,消费者将自身的ID与令牌进行对比,如果相等,则开始执行消费操作.所以当发生领导人换届的情况,不同的Learner获知新Leader的时间并不同.

例如,前任Leader如果因为网络问题与ZooKeeper集群断开,前任Leader只能在超时后才能判断自己是否不再承担Leader角色了,而新的Leader可能在这之前已经产生.另一方面,即使前任Leader和新Leader同时接收到新Leader选举结果,某些业务的完整性要求迫使前任Leader仍然完成当前未完成的工作.

以上的讲解非常抽象,生活中却给了一些更加具体的例子.众所周知,美国总统候选人在选举结束后并不直接担任美国总统,从选举到最终承担总统角色需要一个过渡期.对于新当选Leader的候选人而言,过渡期间称之为加冕阶段(Inauguration).对于即将卸任的Leader,过渡期称为交接阶段(HandOver).

所以一个基于领导人选举的消费者从加冕到卸任经历三个阶段：Inauguration、Execution、HandOver.在加冕阶段,新领导需要进行一些初始化操作.Execution阶段是真正的队列消息处理阶段.在交接阶段,前任领导需要进行一些清理操作.

类似的,为了解决领导人交接问题,所有的消费者从代码实现的角度都需要实现类似ILeaderCareer接口.这个接口包含三个方发inaugurate(),handOver()和execute().某个部署实例(Learner)在得知自己承担领导人角色后,需要调用inaugurate()方法,进行加冕.主要的消费逻辑通过不停的执行execute()实现,当确认自己不再承担领导人之后,执行handOver()进行交接.

如果承担领导人角色的消费者,在执行execute()阶段得知自己将要下台,根据消息处理的原子性,该领导人可以决定是否提前终止操作.如果整个消息处理是一个原子性事务,直接终止该操作可以快速实现领导人换届.否则,前任领导必须完成当前消息处理后,才进入交接阶段.这意味着新的领导人,在inaugurate()阶段需要进行一定时间的等待.

排重优化

频次控制是一个经典问题.对于分布式队列编程架构,相同请求重复出现在队列的情况并不少见.如果相同请求在队列中重复太多,排重优化就显得很必要.分布式缓存更新是一个典型例子,所有请求都被发送到队列中用于缓存更新.如果请求符合典型的高斯分布,在一段时间内会出现大量重复的请求,而同时多线程更新同一请求缓存显然没有太大的意义.

排重优化是一个算法,其本质是基于状态机的编程,整个讲解通过模型、构思和实施三个步骤完成.

模型

进行排重优化的前提是大量重复的请求.在模型这一小节,我们首先阐述重复度模型、以及不同重复度所导致的消费模型,最后基于这两个模型去讲解排重状态机.

重复度模型

首先我们给出最小重复长度的概念.同一请求最小重复长度：同一请求在队列中的重复出现的最小间距.例如,请求ri第一次出现在位置3,第二次出现在10,最小重复长度等于7.

是否需要进行排重优化取决于队列中请求的重复度.由于不同请求之间并不存在重复的问题,不失一般性,这里的模型只考了单个请求的重复度,重复度分为三个类：无重复、稀疏重复、高重复.

• 无重复：在整个请求过程,没有任何一个请求出现一次以上.

• 稀疏重复：主要的请求最小重复长度大于消费队列长度.
• 高重复：大量请求最小重复长度小于消费队列长度.

对于不同的重复度,会有不同的消费模型.

无重复消费模型

在整个队列处理过程中,所有的请求都不相同,如下图：

稀疏重复消费模型

（编辑：ASP站长网）