Algo | Raft一致性算法

分布式系统中如何确保各个分布式节点的数据一致性一直是一个难题,它不仅要考虑到数据的一致,还要考虑到系统的容错性和性能。常见的一致性算法有Paxos、Raft等,本文就简单介绍一下Raft一致性算法。(其实是我学习Raft的笔记)

本文学习内容来自Raft官网以及The Secret Lives of Data

Raft与Consensus

Raft是一个易于理解的一致性算法,它在容错性和性能方面与Paxos相当。不同之处是,Raft被分解为相对独立的子问题,并且能干净利落地解决实际系统所需的所有主要部分。

Consensus即为一致性、共识,是分布式系统的一个基本问题。首先,它要保证所有节点最终能达到相同的状态,即数据一致性。其次,它要保证部分节点出现故障时,其它节点还能正常运行。

Raft算法概述

Raft通过选举领袖的方式来实现一致性算法。

在Raft实现的分布式系统中,节点拥有三个状态:

  • Follower:追随者
  • Candidate:候选人
  • Leader:领袖

所有的节点一开始都是追随者。

如果追随者并不知道谁是领袖,那么它们就可以成为候选人。候选人可以向其它节点发起投票请求,其它节点将对投票请求作出答复。如果候选人获得大多数节点的选票,那么候选人将成为领袖,这一过程就是领袖选举。

分布式系统的所有写操作都要通过领袖来执行,每一个写操作都会新增一个节点日志的条目。当日志条目未提交时,节点的值不会被更新。在提交日志条目之前,领袖节点必须将条目复制到它的追随者节点上,然后等待大多数节点都写入条目时,领袖节点才能提交日志条目,并且通知追随者该条目已在领袖节点提交。现在各个节点就保证了一致性,这一过程称为日志复制。

##Leader Election - 领袖选举

在Raft中有两个超时设置来控制选举:

  • 选举超时:追随者等待成为候选人的时间,随机设置为150ms到300ms之间。
  • 心跳超时:集群进入选举状态的时间。

选举超时后,追随者将成为候选人,然后开始新的领袖选举周期。首先,它会为自己投票,然后再发起投票请求。如果接收到投票请求的节点再该周期内还没有投票,那它将会把票投给候选人,然后重置该节点的选举超时时间。

当领袖被选举出来之后,领袖将以固定时间发送心跳数据包给追随者,让追随者知道领袖还在运作。如果一段时间没有收到领袖的心跳数据包,那么将心跳超时,然后集群就重新进入选举状态。

如果同时存在两个候选人,那么选票可能会被分散到两个候选人上。如果两个候选人的票数一样,那么将等待选举超时,然后开启下一轮选举。

Log Replication - 日志复制

写条目的复制并不是通过单独的数据包发送给追随者的,而是在领袖发给追随者的心跳数据包中一同发送过去。当大多数节点都复制完写条目的时候,领袖节点就会提交日志条目同时执行写操作,并且通知客户端写入成功了。

结语

本文简单地了解了一下Raft一致性算法的内容,不过一致性算法考虑的并不仅仅是这些,比如像新节点加入的数据同步等也是要考虑的。

土豪与Zhenly通道
0%