分布式强一致性算法

news

新闻资讯

行业新闻

分布式强一致性算法

发布时间： 2022-11-10

分布式强一致性算法以Raft算法为基础进行设计，在保证分布式节点状态一致的前提下，相比其他算法逻辑简单、实现方便，能够保证控制器集群实现的简单性，产生错误的概率大为降低。

Raft是一种基于Paxos的分布式一致性协议，相比于Paxos，它更加容易理解和实现，并且能够保证正确性和算法性能。Raft在最初就是从工程的角度设计的，充分考虑了在现实中实现时可能存在的问题，并予以优化或规避。当集群系统内某个节点出现故障时，只要集群内仍存在多数节点，就能保证分布式系统的可用性和数据一致性。

Raft将分布式数据库系统的节点进行抽象，称为复制状态机（Replicated State Machine）。假设状态机的初始状态相同，在系统运行期间，只要每个状态机按照完全相同的序列执行同样的操作，那么它们的最终状态就是一致的。如果映射到网络操作系统中，操作即网络状态变化、流表变化，操作序列即网络状态变化、流表增删的顺序。因此，保证操作和操作序列的一致性，就能保证状态机节点数据的一致性。

在分布式系统中，每个节点均对设备具有感知、管控的权利，针对每个设备，弹性通信网络操作系统或为Master角色或为Slave角色，由弹性通信网络操作系统之间协商针对设备的角色状态，Master角色的弹性通信网络操作系统具有对设备的资源管控、状态获取的权利，而Slave角色的弹性通信网络操作系统只有状态获取的权利。

弹性通信网络操作系统之间采用单点更新的方式实现集群节点数据的一致性。集群节点之间通过选举产生一个主节点，该主节点只作为集群节点之间的数据提交决策节点，所有变化的数据均需要通过该主节点进行决策是否满足集群内的同步状态，完成系统内的数据同步。集群节点的状态分为三种：主节点（Leader）、从节点（Follower）、候选节点（Candidate）。

每个节点在同一时刻只能担任其中一个角色，但在算法运行过程中角色可以发生改变。分布式系统处于非选举状态时，弹性通信网络操作系统只存在两种角色的节点，即主节点和从节点。整个算法的实现流程包括主节点选举（Leader Election）和信息复制（Log Replication）两个阶段。主节点选举就是通过选举确定集群的主节点，并在后面的信息复制阶段中承担起主节点的工作。

图1展示了选举过程中三种节点角色状态的转换情况，这是一个不确定性有限自动机（Non-deterministic Finite Automation，NFA）。随着选举的推进，节点可能转变为任一角色。

选举算法的本质是多数派决议。节点在选举开始时会向所有节点提出预案，即希望自己能成为新任期内的主节点，各个节点会对预案进行投票，如果该预案获得包括自己在内的半数以上节点的认可，那么该节点就能成功当选。

选举过程中，任何一个节点都可能收到多个节点的预案投票请求（Request Vote），最终节点会投票给任期编号最大的预案。另外，选举算法规定在同一任期内，每个节点只有一次投票权，优先到达的预案将得到选票，而后来的预案将被该节点否决。可以看出，在不考虑日志的情况下，节点对预案进行投票依据两个因素：预案的任期编号和节点已投票情况。下面根据图1简要介绍选举算法的第一轮选举流程。

图1　角色状态转换图

（1）一开始，所有的弹性通信网络操作系统节点都是从节点，此时它们并没有所属的主节点。

（2）当从节点在一段时间内未收到主节点的心跳消息，则定时器超时，变为候选节点。

（3）候选节点为自己投一票，同时向所有从节点发起请求投票。

（4）从节点收到请求投票消息，如果发现自己在这个任期还没有投票，就同意投票，否则不投票，即先到先得的原则。

（5）候选节点收到来自大多数（过半）从节点的投票后，则成为新的主节点。

为保证集群内弹性通信网络操作系统拓扑信息、流表信息的一致性，需要实现上述信息的同步，其具体的信息同步流程如下。

（1）某一节点发现拓扑改变或流表改变，向主节点发送写请求。

（2）主节点收到写请求后，首先在本地日志中增加一条写操作记录，但不提交，接着主节点把该条日志记录发送至分布式系统中的所有节点。

（3）主节点等待收到过半其他节点的写日志记录成功的回复，然后响应请求节点一个写请求成功的回复。

（4）主节点在本地提交日志记录，同时向所有其他节点发起提交日志的请求。

（5）各节点在本地提交日志记录。

通过以上步骤保证弹性通信网络操作系统集群内的拓扑状态、流表状态的一致性。

当一个节点从故障中恢复或刚启动时，其角色为从节点，同时启动一个定时器（Follower Timer）。若从节点接收到主节点发送的心跳消息，会重置定时器，保持从节点角色状态不变。否则，定时器最终会超时，而从节点认为此时集群中没有有效的主节点存在，因此，它将转变为候选节点，准备竞争成为新的主节点。

候选节点首先提升自己的任期编号，重置自己的定时器，然后向其他节点发出投票请求并等待回复。之后，候选节点将可能出现三种情况：

（1）获得同一任期内的过半节点选票，成为主节点。

（2）等待期间接收到心跳消息，说明集群中已经有节点当选，此时转变为从节点。

（3）如果前面两种情况都没有发生，候选节点将持续等待，直到定时器超时，然后重新发起新一轮选举。

某一节点成为主节点后，便开始发送日志信息，并重置其他节点的定时器。只要主节点没有在与其他节点通信时发现具有更大任期编号的节点，会一直保持主节点这一角色。

QQ空间新浪微博腾讯微博人人网微信更多

上一篇：分布式最终一致性算法

下一篇：可重构网络基础设施架构

软件开发

华为认证

思科认证

微软认证

数据认证

红帽认证

Cloudera

其他课程

首页

学习天地

师资力量

学员活动

新闻资讯

关于我们

新闻资讯

行业新闻

热点新闻

友情链接