Raft

作者： 京东物流 郭益如 导读在分布式系统中， 什么是拜占庭将军问题？产生的场景和解决方案是什么？什么是 Raft 共识算法？Raft 算法是如何解决拜占庭将军问题的？其外围原理和算法逻辑是什么？除了 Raft，还有哪些共识算法？共识问题作为分布式系统的一大难点和痛点，本文次要介绍了其产生的背景、起因，以及通用的 Raft 算法解决方案。 01 拜占庭将军问题【分布式对等网络中的通信容错问题。 在分布式计算中，不同的计算机通过通信替换信息达成共识依照一套合作策略口头。有时候，零碎中的成员计算机可能出错而发送谬误的信息，用于传递信息的通信网络也可能导致信息损坏，使得网络中不同的成员对于整体合作的策略得出不同论断，从而毁坏零碎一致性，这就是拜占庭将军问题。 拜占庭将军问题被认为是容错性问题中最难的问题类型之一。】 9 位将军兵分 9 路去打仗，他们各自有势力观测敌情并做出口头判断 —— 防御或撤退，他们必须口头统一，即所有军队一起防御或者一起撤退，否则局部防御局部撤退会造成灾难性结果。 前提： 将军之间只能通过信使互相联系，每位将军将本人的判断发送给其余将军，并接管其余将军发送的判断；收到信息的将军综合所有的判断，当超过半数都抉择防御时，就决定防御，当超过半数都抉择撤退时就决定撤退；问题是，将军两头可能呈现叛徒，他可能会抉择相同的后果进行通信（投票），也可能选择性的发送信息，叛徒要达成的指标是： 选择性的发送信息，坑骗某些将军采取防御的口头；促成一个谬误的决定，比方将军们不心愿防御时防御；蛊惑某些将军，使得他们无奈做出决定；如果叛徒达成了其中之一，任何的攻打后果都是注定要失败的，只有齐全达成统一的致力能力获得胜利。 比方，可能 9 位将军中有 8 位虔诚的将军和一名叛徒，8 位将军中 4 位抉择防御，4 位抉择撤退，叛徒别离给抉择防御的将军发送防御的信息，给抉择撤退的将军发送撤退信息。这样一来，在4 位抉择防御的将军看，共 5 位将军抉择防御，从而发动防御；而在 4 位抉择撤退的将军看，共 5 位将军抉择撤退，从而发动撤退，这样各个将军的一致性就受到了毁坏。 并且，叛徒将军可能会伪造其余将军的身份发送函件； 拜占庭将军问题形容的是，在存在信息失落的不牢靠信道上试图通过消息传递的形式达到一致性是不可能的，在零碎中除了存在的音讯提早或不可送达故障外，还可能包含音讯篡改、节点解决异样等潜在性异样。 1.1 拜占庭容错在晚期的解决方案中，一种是 “拜占庭容错” ，它遵循“多数遵从少数”的共识机制，即便呈现了谬误或伪造的信息，只有有问题的将军数量不到 1/3，仍能够达到“拜占庭容错”，使整个零碎便能够失常运作。 为什么是 1/3呢？ 其原理是这样的，假如将军总数是 N，其中耿直的将军数量是 S，叛变的将军数量是 T， 那么 N=S+T； 为了保障即便叛变的将军都不去投票也能产生最终的后果，那么 S 必须要超过半数，这种状况下，S 都做出雷同的抉择，仍然能够达成共识，即 S>T； 如果叛徒给一半反对防御的将军发送防御信息，给一半反对撤退的将军发送撤退信息，这种状况要保障也能产生最终的投票后果，则 X > S/2 + E； 综合以上关系，能够失去： N = S + T ...

【摘要】 共识算法入门之raft和pbft aft算法算法动画演示：http://thesecretlivesofdata.c... 节点的三种角色：跟随者（follower）、候选人（candidate）、领导者（leader） 最大容错故障节点：（N - 1）/ 2 选举超时（election timeout）：一个节点在成为候选节点（candidate）之前期待的工夫，150ms到300ms之间的随机值 心跳超时（heartbeat timeout）：心跳超时 \ pbft算法最大容错节点数：3f + 1 <= N 算法根本流程： 客户端发送申请给主节点主节点播送申请给其余节点，节点执行pbft算法三阶段共识流程节点解决完三阶段流程后，返回音讯给客户端客户端收到来自f + 1个节点的雷同音讯后，代表共识曾经实现pbft算法外围三阶段流程： v：视图编号 d：客户端音讯摘要 m：音讯内容 n：在[h，H]区间之间，申请编号 i：节点编号 <PRE-PREPARE，v，n，d>进行主节点签名 Pre-prepare 阶段：节点收到 pre-prepare 音讯后，会有两种抉择，一种是承受，一种是不承受。什么时候才不承受主节点发来的 pre-prepare 音讯呢？一种典型的状况就是如果一个节点承受到了一条 pre-pre 音讯，音讯里的 v 和 n 在之前收到里的音讯是已经呈现过的，然而 d 和 m 却和之前的音讯不统一，或者申请编号不在高下水位之间（高下水位的概念在下文会进行解释），这时候就会拒绝请求。回绝的逻辑就是主节点不会发送两条具备雷同的 v 和 n ，但 d 和 m 却不同的音讯。Prepare 阶段：节点批准申请后会向其它节点发送 prepare 音讯。这里要留神一点，同一时刻不是只有一个节点在进行这个过程，可能有 n 个节点也在进行这个过程。因而节点是有可能收到其它节点发送的 prepare 音讯的。在肯定工夫范畴内，如果收到超过 2f 个不同节点的 prepare 音讯，就代表 prepare 阶段曾经实现。Commit 阶段：于是进入 commit 阶段。向其它节点播送 commit 音讯，同理，这个过程可能是有 n 个节点也在进行的。因而可能会收到其它节点发过来的 commit 音讯，当收到 2f+1 个 commit 音讯后（包含本人），代表大多数节点曾经进入 commit 阶段，这一阶段曾经达成共识，于是节点就会执行申请，写入数据。 ...

说到raftexample，很多人可能很生疏，我晓得raft，我也晓得example，哪来的raftexample？这里做下简略的介绍，raftexample是etcd外面 raft模块实现的简略示例，它实现了一个简略的基于raft协定的kvstore存储集群零碎，并提供了rest api以供应用 而raftexample仅有以下几个文件，几百行代码，通过浏览，能够帮忙咱们更好的了解raft协定，投入产出比超大 演示动画官网举荐的动画演示地址：http://thesecretlivesofdata.c... leader选举 日志同步 概念解析逻辑时钟逻辑时钟其实是一个定时器 time.Tick，每隔一段时间触发一次，是推动raft选主的外围，在这外面有几个属性先理解下 electionElapsed：逻辑时钟推动计数，follower和leader没推动一次逻辑时钟，这个数值就会+1；follower收到leader的心跳音讯后会重置为0；leader则在每次发送心跳前重置为0 heartbeatElapsed：leader的逻辑时钟推动计数，不仅仅会减少electionElapsed计数，还会减少heartbeatElapsed的计数 heartbeatTimeout：当leader的heartbeatElapsed计数达到heartbeatTimeout预约义的值的时候，就会向各个节点发送一次心跳 electionTimeout：当leader的electionElapsed的逻辑时钟推动次数超过这个值的时候，如果leader同时开启了checkQuorum来判断以后集群各节点的存活状态时，这时候leader就会进行探活（探活不会发动网络申请，靠本身存储的各个节点状态） randomizedElectionTimeout：随机生产的一个值，当follower的electionElapsed计数达到这个值的时候，就会开始发动新一轮选举 所以，能够看进去，逻辑时钟次要是推动leader心跳和探活、follower的选举的 follower发动选举的条件：electionElapsed >= randomizedElectionTimeout leader发送心跳的条件：heartbeatElapsed >= heartbeatTimeout leader发动集群节点探活的条件：electionElapsed > electionTimeout 这里就有一个问题了，leader节点为什么会有electionElapsed 和 heartbeatElapsed 两个计数，一个不就能够了吗？ 其实是因为，当leader发动探活或者计数满足探活条件的时候，electionElapsed 就会被置为0，所以对于leader而言，electionElapsed 跟 heartbeatElapsed 的值并不统一，也不同步 raft.PeerPeer: 集群中的节点，每一个退出集群的利用过程，都是一个节点 type Peer struct { ID uint64 Context []byte}ID: 节点的id，过程初始化的时候，会给集群中的每个节点调配一个ID Context: 上下文 raftpb.MessageMessage: 这是raftexample（前面简称raft来代替）中的一个重要的构造体，是所有音讯的形象，包含且不限于选举/增加数据/配置变更，都是一种音讯类型 type Message struct { Type MessageType To uint64 From uint64 Term uint64 LogTerm uint64 Index uint64 Entries []Entry Commit uint64 Snapshot Snapshot Reject bool RejectHint uint64 Context []byte }Type: 音讯类型，raft中就是依据不同的音讯类型来实现不同的逻辑解决的 ...

引言在 Paxos、Raft 这类一致性算法的形容里，常常会看到 Majority、Quorum 这两个词，在以前我认为都是表白“半数以上”的含意，最近才发现两者有不小的区别。本文介绍这两者的区别，以及在 Raft 中实际中的问题。有了 Quorum 的视角，能更好得了解一致性算法。 Read-Write Quorum System首先来在数学上给出 Read-Write Quorum System 的定义。 一个 Read-Write Quorum System（读写法定零碎）是两个汇合组成的元组，即Q=（R,W），其中： • 汇合 R 被称为 Read Quorum（读法定汇合），即能够认为读操作都是读的汇合 R 中的元素； • 汇合 W 被称为 Write Quorum（写法定汇合），即能够认为写操作都是写入到汇合 W 中的元素。 • $r∈R, w∈W,r∩w≠0 $，即任从读汇合中取一个成员 r，以及任从写汇合中取一个成员 w，这两个汇合肯定有交加。 都晓得在分布式系统中，一个写入操作要达成统一，读写操作肯定要有肯定的冗余度，即： • 写入多份数据胜利能力认为写入胜利， • 从多个节点读到同一份数据才认为读取胜利。 在 Majority 零碎中，这个冗余度就是零碎内半数以上节点。因为依据抽屉原理1，当写入到至多半数以上节点时，读操作与写操作肯定有重合的节点。 然而在一个 Read-Write Quorum System 中，这个条件变的更宽泛了，在这类零碎中，只须要满足以下条件即可认为读写胜利： $r∈R, w∈W,r∩w≠0 $ 用直观的大白话来说：在 Read-Write Quorum System 中，只有读、写汇合中的任意元素有重合即可。 咱们来具体看看 Majority 和 Read-Write Quorum System 这两个零碎的区别在哪里。 首先，Majority 零碎并没有辨别读、写两类不同的汇合，因为在它的视角里，读和写操作都要到半数以上节点能力达到统一。然而在 Read-Write Quorum System 零碎里，是严格辨别了读、写汇合的，只管可能在很多时候，这两类汇合是一样的。 ...

Raft角色一个Raft集群蕴含若干节点，Raft将这些节点分为三种状态：Leader、Follower、Candidate，每种状态负责的工作也不一样。失常状况下，集群中的节点只存在Leader与follower两种状态。 Leader(领导者)：负责日志的同步治理，解决来自客户端的申请，与follower放弃心跳Follower(追随者)：响应Leader的日志同步申请，响应Candidate的邀票申请，以及将客户端申请到Follower的事务转发给LeaderCandidate(侯选者)：负责选举投票，集群刚启动或者Leader宕机时，状态为Follower的节点将转为Candidate并发动选举，选举胜出后，从Candidate转为Leader状态。Raft三个子问题Raft实现了和Paxos雷同的性能，它将一致性合成为多个子问题：Leader选举、日志同步、安全性、日志压缩、成员变更。这里重点看下选举、日志同步与安全性： 选举：当Leader宕机或集群启动时，一个新的Leader须要被选举进去日志同步：Leader接管来自客户端的申请并将其以日志条目标模式同步到集群中的其它节点，并且强制要求其它节点的日志和本人保持一致安全性：如果有任何的服务器节点曾经利用了一个确定的日志条目到它的状态机中，那么其它节点不能在同一个日志索引地位利用一个不同的指令。1. 选举原理 依据Raft协定，一个利用Raft协定的集群在刚启动时，所有节点的状态都是Follower。因为没有Leader，Follower无奈与Leader放弃心跳，因而，Follower会认为Leader曾经下线，进而转为Candidate状态。而后，Candidate将向集群中其它节点申请投票，批准本人降级为Leader。如果Candidate收到超过半数节点的投票(N/2+1)，它将成为Leader。 第一阶段：所有节点都是Follower在筹备选举时，所有节点状态都是Follower，并且初始任期为0，同时启动选举定时器，每个节点的选举定时器超时工夫都在100-500毫秒之间且不统一，防止同时发动选举。 第二阶段：Follower转为Candidate并发动投票节点启动后在一个选举定时器周期内未收到心跳和投票申请，则状态转为候选者Candidate状态，且Term自增，并向集群中所有节点发送投票申请并且重置选举定时器。每个节点的选举定时器超时工夫都不统一，所以最先转为Candidate的节点最有可能成为Leader。 第三阶段：投票阶段节点收到投票申请后会依据以下状况决定是否承受投票申请： 申请节点的Term大于本人的Term，且本人还未投票给其它节点，则承受申请，将票投给它申请节点的Term小于本人的Term，且本人琮未投票，则拒绝请求，将票投给本人第四阶段：Candidate转为Leader一轮选举过后，失常状况下会有一个Candidate收到超过半数节点（N/2+1）的投票，它将胜出并降级为Leader。而后定时发送心跳给其它节点，其它节点会转为Follower并与Leader放弃同步，至此，选举完结；如果未过半数会进行下一轮选举。 2. Raft日志同步 在一个Raft集群中，只有Leader节点可能解决客户端申请（如果申请到了Follower，它会将申请转发到Leader），客户端的每个申请都蕴含一条被复制状态机执行的指令。Leader将这条指令作为一条新的日志条目（Entry）附加到日志中去，而后并行地将附加条目发送给各个Followers，让它们复制这条上场条目。当这条日志条目被各个Followers平安复制，Leader会将这条上场条目利用到它的状态机中，而后将执行后果返回给客户端。如果Follower解体或者运行迟缓，或者网络丢包，Leader会一直尝试附加日志条目直到所有的Follower都最终存储所有的日志条目，确保强一致性。 第一阶段：客户端申请提交到LeaderLeader在收到客户端申请后会将其作为日志条目（Entry）写入本地日志中，须要留神的是该Entry的状态是未提交（uncommitted），Leader并不会更新本地数据，因而它是不可读的。 第二阶段：Leader将Entry发送到其它FollowerLeader与Follower之间放弃着心跳分割，随心跳Leader将追加的Entry(AppendEntries)并行地发送给其它的Follower，并让它们复制这条上场条目，这一过程称为复制（Replicate）。 Leader向Follower发送的Entry是AppendEntries. 在一个心跳周期内，Leader可能会接管到多条客户端的申请，因而，Leader发送给Follower也会是多个Entry也就是AppendEntriesLeader在向Follower发送追加的Entry外，还会将上一条日志条目标索引地位(prevLogIndex)，Leader的任期号（Term）也一并发送。如果Follower在它的日志中找不到蕴含雷同索引地位和任期号的条目，那么它就会回绝接管新的日志条目，呈现这样的状况阐明Follower与Leader数据不统一了。解决Leader与Follower数据不统一的问题。因为某些起因Leader上数据可能比Follower上的数据多也可能少。要使二者数据放弃雷同，Leader会找到最初两者达成统一的中央，而后将那个点之后的日志条目删除并发送本人的日志给Follower，所有这些操作都在进行附加日志的一致性查看时实现。Leader还会为每个Follower保护一个nextIndex，它示意下一个须要发送给Follower日志条目标索引地址。当一个Leader刚被选举进去的时候，它会初始化所有的nextIndex值，并给本人最初一条日志的index加1。如果一个Follower的日志和Leader不统一，那么在下一次附加日志一致性查看会失败。在被Follower回绝之后，Leader会减小该Follower对应的nextIndex值并进行重试。最终nextIndex会在某个地位使得Leader和Follower的日志达成统一，这时会将Follower抵触的日志条目全副删除并再加上Leader的日志，这样Follower的日志就会和Leader保持一致。第三阶段：Leader期待Follower回应Follower接管到Leader发来的复制申请后，可能会有两种回应： 写入本地日志中，返回Success;一致性查看失败，回绝写入，返回False（解决形式见第二阶段）须要留神的是，此时该Entry的状态在Leader中仍是未提交状态，当Leader收到大多数Follower Success回应后，会将第一阶段写入的Entry标记为提交状态，并此日志条目利用到它的状态机中。 第四阶段：Leader回应客户端实现前三个阶段后，Leader会向客户端回应OK，示意写操作胜利。 第五阶段：Leader告诉Followers Entry已提交Leader回应客户端后，将随着下一个心跳告诉各Follower， 各Folloer收到告诉后会将Entry标记为提交状态，至此，Raft集群超过半数节点曾经达到统一状态，能够确保强一致性。因为网络等起因可能会有局部Follower在某个工夫点内与Leader不统一，但最终还是会统一。 3. Raft算法之安全性Raft如何保障对于给定的任期号（Term），Leader都领有之前任期的所有被提交的日志条目（也就是Leader的完整性）呢？1) 为了保障所有之前的任期号中曾经提交的日志条目在选举的时候都会呈现在新的Leader中，Raft采纳的是日志条目单向传递，只从Leader传给Follower，并且Leader从不会笼罩本身本地日志中曾经存在的条目。2) 一个Candidate只有蕴含了最新的已提交的log entry，并且取得了集群中大部分节点的认可才有可能博得选举，这也意味着每一个曾经提交的日志条目必定存在于至多一个服务器节点上。 Candidate在发送RequestVote RPC时，要带上本人的最初一条日志的term和log index，其余节点收到音讯时，如果发现自己的日志比申请中携带的更新，则回绝投票。日志比拟的准则是，如果本地的最初一条log entry的term更大，则term大的更新，如果term一样大，则log index更大的更新。3) Leader能够复制后面任期的日志，然而不会被动提交后面任期的日志，而是通过提交以后任期的日志来间接地提交后面任期内的日志(这一点有些不太了解) 参考的文章：分布式算法 - Raft算法Raft协定安全性保障

前言本篇是对于 2022-MIT 6.828 的对于 Fault-tolerant Key/Value Service 的试验记录；如果发现内容上的纰漏，请不要悭吝您的键盘。一点点的背景常识In this lab you will build a fault-tolerant key/value storage service using your Raft library from lab 2. Your key/value service will be a replicated state machine, consisting of several key/value servers that use Raft for replication. Your key/value service should continue to process client requests as long as a majority of the servers are alive and can communicate, in spite of other failures or network partitions. After Lab3, you will have implemented all parts (Clerk, Service, and Raft) shown in the diagram of Raft interactions. ...

简介： SOFAJRaft已开源 作者 | 家纯起源 | 阿里技术公众号 一 分布式共识算法 (Consensus Algorithm)1 如何了解分布式共识? 多个参与者针对某一件事达成完全一致：一件事，一个论断。 已达成统一的论断，不可颠覆。 2 有哪些分布式共识算法? Paxos：被认为是分布式共识算法的基本，其余都是其变种，然而 paxos 论文中只给出了单个提案的过程，并没有给出复制状态机中须要的 multi-paxos 的相干细节的形容，实现 paxos 具备很高的工程复杂度（如多点可写，容许日志空洞等）。Zab：被利用在 zookeeper 中，业界应用宽泛，但没用形象成通用 library。Raft：以容易了解著称，业界也涌现出很多 raft 实现，比方 etcd、braft、tikv 等。 二 Raft 介绍1 特点：Strong Leader 零碎中必须存在且同一时刻只能有一个 leader，只有 leader 能够承受 clients 发过来的申请。Leader 负责被动与所有 followers 通信，负责将“提案”发送给所有followers，同时收集多数派的 followers 应答。Leader 还需向所有 followers 被动发送心跳维持领导位置（放弃存在感）。另外，身为 leader 必须放弃始终 heartbeat 的状态。 2 复制状态机 对于一个有限增长的序列a[1, 2, 3…]，如果对于任意整数i， a[i]的值满足分布式一致性， 这个零碎就满足一致性状态机的要求。 基本上所有的实在零碎都会有源源不断的操作，这时候独自对某个特定的值达成统一显然是不够的。为了让实在零碎保障所有的正本的一致性，通常会把操作转化为 write-ahead-log(WAL)。而后让零碎中所有正本对 WAL 保持一致，这样每个正本依照程序执行 WAL 里的操作，就能保障最终的状态是统一的。 ...

简介： 成员变更是一致性零碎实现绕不开的难题，对于晋升运维能力以及服务可用性都有很大的帮忙。 本文从Raft成员变更实践登程，介绍了Raft成员变更和单步成员变更的问题，其中包含Raft驰名的Bug。 对于Raft成员变更的工程实现上须要思考的问题，本文给出了一些工程实践经验。 一  引言 成员变更是一致性零碎实现绕不开的难题，对于晋升运维能力以及服务可用性都有很大的帮忙。 本文从Raft成员变更实践登程，介绍了Raft成员变更和单步成员变更的问题，其中包含Raft驰名的Bug。 对于Raft成员变更的工程实现上须要思考的问题，本文给出了一些工程实践经验。 二  Raft成员变更简介 分布式系统运行过程中节点常常会呈现故障，须要反对节点的动静减少和删除。 成员变更是在集群运行过程中扭转运行一致性协定的节点，如减少、缩小节点、节点替换等。成员变更过程不能影响零碎的可用性。 成员变更也是一个一致性问题，即所有节点对新成员达成统一。然而成员变更又有其特殊性，因为在成员变更的过程中，参加投票的成员会发生变化。 如果将成员变更当成个别的一致性问题，间接向Leader节点发送成员变更申请，Leader同步成员变更日志，达成多数派之后提交，各节点提交成员变更日志后从旧成员配置（Cold）切换到新成员配置（Cnew）。 因为各个节点提交成员变更日志的时刻可能不同，造成各个节点从旧成员配置（Cold）切换到新成员配置（Cnew）的时刻不同。可能在某一时刻呈现Cold和Cnew中同时存在两个不相交的多数派，进而可能选出两个Leader，造成不同的决定，毁坏安全性。 图1 成员变更的某一时刻Cold和Cnew中同时存在两个不相交的多数派 如图1是3个节点的集群扩大到5个节点的集群，间接扩大可能会造成Server1和Server2形成老成员配置的多数派，Server3、Server4和Server5形成新成员配置的多数派，两者不相交从而可能导致决定抵触。因为成员变更的这一特殊性，成员变更不能当成个别的一致性问题去解决。为了解决这个问题，Raft提出了两阶段的成员变更办法Joint Consensus。 1  Joint Consensus成员变更 Joint Consensus成员变更让集群先从旧成员配置Cold切换到一个过渡成员配置，称为联结统一成员配置（Joint Consensus），联结统一成员配置是旧成员配置Cold和新成员配置Cnew 的组合Cold,new，一旦联结统一成员配置Cold,new提交，再切换到新成员配置Cnew 。 图2 Joint Consensus成员变更 Leader收到成员变更申请后，先向Cold和Cnew同步一条Cold,new日志，尔后所有日志都须要Cold和Cnew两个多数派的确认。Cold,new日志在Cold和Cnew都达成多数派之后能力提交，尔后Leader再向Cold和Cnew同步一条只蕴含Cnew的日志，尔后日志只须要Cnew的多数派确认。Cnew日志只须要在Cnew达成多数派即可提交，此时成员变更实现，不在Cnew中的成员主动下线。 成员变更过程中如果产生Failover，老Leader宕机，Cold,new中任意一个节点都可能成为新Leader，如果新Leader上没有Cold,new日志，则持续应用Cold，Follower上如果有Cold,new日志会被新Leader截断，回退到Cold，成员变更失败；如果新Leader上有Cold,new日志，则持续将未实现的成员变更流程走完。 Joint Consensus成员变更比拟通用且容易了解，然而实现比较复杂，之所以分为两个阶段，是因为对 与 的关系没有做任何假如，为了防止 和 各自造成不相交的多数派而选出两个Leader，才引入了两阶段计划。 如果加强成员变更的限度，假如Cold与Cnew任意的多数派交加不为空，Cold与Cnew就无奈各自造成多数派，则成员变更就能够简化为一阶段。 2  单步成员变更实现单步的成员变更，关键在于限度Cold与Cnew，使之任意的多数派交加不为空。办法就是每次成员变更只容许减少或删除一个成员。 图3 减少或删除一个成员 减少或删除一个成员时的情景，如图3所示，能够从数学上严格证实，只有每次只容许减少或删除一个成员，Cold与Cnew不可能造成两个不相交的多数派。因而只有每次只减少或删除一个成员，从Cold可间接切换到Cnew，无需过渡成员配置，实现单步成员变更。 单步成员变更一次只能变更一个成员，如果须要变更多个成员，能够通过执行屡次单步成员变更来实现。 单步成员变更实践尽管简略，但却埋了很多坑，理论用起来并不是那么简略。 三  Raft单步成员变更的问题 Raft单步成员变更的问题，最驰名的莫过于Raft驰名的正确性问题，另外单步成员变更还有潜在的可用性问题。 1  Raft单步成员变更的正确性问题 Raft单步变更过程中如果产生Leader切换会呈现正确性问题，可能导致曾经提交的日志又被笼罩。Raft作者（Diego Ongaro）早在2015年就发现了这个问题，并且在Raft-dev具体的阐明了这个问题[1]。 上面是一个Raft单步变更出问题的例子, 初始成员配置是abcd这4节点，节点u和V要退出集群, 如果两头呈现Leader切换, 就会失落已提交的日志： 图4 Raft单步成员变更的正确性问题 t0：节点abcd的成员配置为C0；t1 ：节点abcd在Term 0选出a为Leader，b和c为Follower；t2：节点a同步成员变更日志Cu，只同步到a和u，未胜利提交；t3：节点a宕机；t4：节点d在Term 1被选为Leader，b和c为Follower；t5：节点d同步成员变更日志Cv，同步到c、d、V，胜利提交；t6：节点d同步一般日志E，同步到c、d、V，胜利提交；t7：节点d宕机；t8：节点a在Term 2从新选为Leader，u和b为Follower;t9：节点a同步本地的日志Cu给所有人，造成已提交的Cv和E失落。为什么会呈现这样的问题呢？根本原因是上一任Leader的成员变更日志还没有同步到多数派就宕机了，新Leader一上任就进行成员变更，应用新的成员配置提交日志，之前上一任Leader从新上任之后可能造成另外一个多数派汇合，产生脑裂，将已提交的日志笼罩，造成数据失落。 ...

一、客户端如何找到Leader Raft算法规定客户端将所有申请发送给Leader。客户端启动的时候，如何晓得哪一个节点是Leader呢？具体办法是客户端随机筛选一个服务器进行通信，如果客户端选的服务器不是领导人，那么被筛选的服务器会回绝客户端的申请，并且提供它最近接管到的领导人的信息，即通过收到Leader发送的心跳的RPC失去Leader的网络地址。 还有一种状况，如果领导人曾经解体了，那么客户端的申请就会超时，客户端之后会再次重试随机筛选服务器的过程。 二、如何确保命令只执行1次 Raft算法是可能屡次执行同一条命令的，官网也举了一个例子： 如果领导人在提交了这条日志之后，然而在响应客户端之前解体了，那么客户端会和新的领导人重试这条指令，导致这条命令就被再次执行了，因为日志曾经提交，只是这个响应没有被发送到客户端。 解决方案 客户端对于每一条指令都赋予一个惟一的序列号，状态机跟踪每条指令最新的序列号和相应的响应。如果接管到一条指令，它的序列号曾经被执行了，那么就立刻返回后果，而不从新执行指令。 即由状态机来保障不反复执行，因为这不是Raft算法中的内容，而是如何保障幂等性了，行业内也有很多计划，大略原理都是为申请生成惟一ID，而后服务端判重，这里不详述了。 三、如何100%保障不脏读后面说了所有读、写申请都发送Leader，那是不是意味着从Leader发动读申请的时候就不必做什么解决，能够间接返回了？这里可能有脏读的状况，咱们来举个例子： 以后集群有5个节点：A、B、C、D、E 假如以后Leader是A，当初因为网络起因导致网络分区，变成如下： 当初分成2个网络：A、B所在网络与C、D、E的网络不通，因为C、D、E与A所在网络不通，因而C、D、E会触发选举，并且节点数为3，满足集群节点少数的条件，因而能够选举出Leader； 如果此时客户端有新的申请发到左边的新集群，假如是一个批改key为test的操作并且提交了，而此时同样一个客户端申请发到A，读取key也为test，因为左边集群曾经有新操作了，间接从A的状态机里返回数据就是旧的了。 针对这个问题，官网给的计划是须要额定2个额定的措施来保障： 1、领导人必须有对于被提交日志的最新信息 即在它的任期里必须马上提交一条空白的日志条目，即心跳； 这段话的意思是在一个节点成为Leader之前，至多向少数节点发送一次心跳来进行确认日志状况，在没收到心跳响应之前是不能响应客户端的； 2、领导人在解决只读的申请之前必须查看本人是否曾经被破除了 具体实现是Leader在响应只读申请之前，先和集群中的大多数节点替换一次心跳信息来解决这个问题，即发送一次心跳的RPC，收到响应无误之后能力返回给客户端，即每次读申请要和少数成员做一次心跳以确认本人依然是 Leader。 回到下面的案例，因为网络分区了，客户端申请A的时候，A向成员发送心跳时，只有B能响应，没有达到少数成员的要求，因而不能响应给客户端。 下面这种状况也叫ReadIndex，有趣味的同学能够理解下相干实现。 四、一次申请残缺交互 最初以一次残缺的客户端申请来总结整个过程，包含客户端发送申请和Leader在什么时候响应；假如集群有3个节点：A、B、C，其中A以后为Leader，一次残缺的申请的过程如下： 1、客户端提交到申请至Leader； 2、Leader本人先保留日志，留神这里不提交； 3、Leader将日志同步给Follower，这里只画了1条线，即只同步给C，实际上是都会同步； 4、Follower收到日志后保留日志并响应给Leader； 5、Leader只有收到一个Follower的响应后马上将这条日志提交并利用到状态机中； 6、Leader利用到状态机实现后就能够返回给客户端了； 上图中后续的流程没有画，即Follower在什么时候提交日志，答案是Leader在下一次心跳的时候会将最新的commitIndex带上，Follower因而提交日志并利用到状态机中。

一、集群成员变动可能带来的问题 集群成员变动是一个常见操作，次要是减少、删除节点，次要的场景有降级、服务器老化等，当然如果咱们对服务的SLA没太大要求，间接敞开集群是最简略的方法。但如果要保证系统的可用性而动静地增加、删除节点并且保障不会脑裂等问题则须要一个平安的算法，所以Raft算法把这一部分也纳入其中。 间接将集群成员配置从旧配置切到新配置会有脑裂问题，举个例子： 上图中集群原来有3个节点：Server1、Server2、Server3，当初要减少2个节点：Server4、Server5，咱们来构想下具体的操作步骤： 1、Server4和Server5是新节点，所以这2台机器启动的时候认为集群中有5个节点； 2、而后批改Server3的配置，改成5节点； 这时产生选举，即上图中红色箭头所指的地位，这时候每个节点看到的集群成员如下，为了不便形容，对立将Server字样去掉，即只保留1、2、3、4、5，1示意Server1： 1：1、2、3 2：1、2、3 3：1、2、3、4、5 4：1、2、3、4、5 5：1、2、3、4、5 这时1通过2的投票能够被选举为Leader，因为1和2认为集群只有1、2、3总共3个节点； 3通过3，4，5这3个节点的投票被选举为Leader； 这样集群同时存在1和3两个Leader了。 二、变更计划 官网给的计划是二阶段变更： 集群先从旧成员配置Cold切换到一个过渡成员配置，称为独特统一（joint consensus），独特统一是旧成员配置Cold和新成员配置Cnew的组合Cold U Cnew，一旦独特统一Cold U Cnew被提交，零碎再切换到新成员配置Cnew。 具体过程如下： Leader收到从Cold切成Cnew的成员变更申请，Leader分两步操作： 1、提交配置Cold U Cnew Leader在本地生成一个新的日志，这个日志的类型是成员配置，其内容是Cold∪Cnew，代表以后时刻新旧成员配置共存，写入本地日志，但并不提交； Leader同时将该日志复制至Cold∪Cnew中的所有正本，在此之后新的日志同步须要保障失去Cold和Cnew两个多数派的确认； Follower收到Cold∪Cnew的日志后更新本地日志，并且马上就以该配置作为本人的成员配置； 如果Cold和Cnew中的两个多数派确认了Cold U Cnew这条日志，Leader就提交这条日志； 2、提交Cnew 接下来Leader生成一条新的日志条目，类型也是成员变更，其内容是新成员配置Cnew，同样将该日志条目先写入本地日志，同时复制到Follower上； Follower收到新成员配置Cnew后，将其写入日志，并且马上就以该配置作为本人的成员配置，并且如果发现自己不在Cnew这个成员配置中会主动退出。 能够看到，Raft算法将成员配置的变动也作为一条日志，须要通过一轮Raft过程像利用操作一样只有大多数节点确认了就必定不会出出脑裂了。留神Follower收到配置后马上就变更，而不须要等Leader下次发送commitIndex的时候才提交，这点是和失常利用提交不一样的中央。 这里不去做具体的证实，官网有具体阐明，咱们能够看下几个异样，还是以下面的例子，以后集群有3个节点：1、2、3，当初要减少2个节点：4、5，假如以后Leader为1，具体过程如下： 1）节点1收到成员变更的申请，生成一条日志类型为成员变更，内容为：1、2、3、4、5，节点1将这条日志先保留到本地，但不马上更改成员配置； 2）节点1将上述日志同步给2，3，4，5四个节点； 3）2、3、4、5节点收到配置后做2件事：追加日志，马上变更本人的成员配置为：1、2、3、4、5； 4）节点1只有收到2个以上节点回复马上将本人成员配置为：1、2、3、4、5. 咱们看有哪些异样： 如果有1-2过程中失败了，则整个过程就算失败，则须要管理员从新发动成员变更操作； 如果第3步只有1个节点即不是集群少数节点收到变更，这个时候节点1挂了，如果收到日志的先发动选举则有可能推动这条日志，否则就不胜利，即有可能失落； 如果在第4步节点1挂了的话，新集群必定是有这个配置的，因为依据日志最新准则，新选举进去的Leader必定蕴含下面成员变更的日志。 三、其它问题 1、新加的成员入无日志 一开始的时候新的服务器可能没有任何日志条目，如果它们在这个状态下退出到集群中，那么它们须要一段时间来更新追赶，在这个阶段它们还不能提交新的日志条目，这个时候节点没有投票权，有的文章说叫Catch-Up。 2、移除不在 Cnew 中的服务器可能会扰乱集群 次要是移除的状况，构想一个集群有5个节点：1，2，3，4，以后Leader是2，当初要把1移除掉，如果2曾经将新的成员配置：2，3，4曾经同 步给3和4了，如果配置不发给1，因为2认为集群中1不存在了，所以不会向1发心跳，而1没收到2的心跳，会减少本人的Term发动选举，其它成员收到后会进化成Follower，不过不会给1投票，因为1的日志不是最新的，不过这会影响集群的可用性。 针对这个问题，官网给的是PreVote，即在发动投票的RequestVote RPC申请之前再发一个PreVote申请，只有通过这个才正式发动RequestVote，这样能够大大晋升零碎的可用性。其实还有1个更简略的方法，间接将1关机或者将服务程序Kill掉。

一、什么是快照 快照（snapshot）是最简略的压缩形式。在快照中，全副的以后零碎状态都被写入到快照中，存储到长久化的存储中，而后在那个时刻之前的全副日志都能够被抛弃。 打个比方，像Redis这样的KV零碎，零碎的以后状态就是以后所有key的值及过期工夫，把这些信息全副写入到磁盘中就是快照。 二、Raft算法中为什么须要快照 Raft算法是通过日志来保障节点最终统一的，而日志是继续减少的，对于一个7*24小时运行的零碎，日志会始终减少，这样导致几个问题： 1、磁盘占用空间过大； 2、新的节点退出进来后，须要同步的日志太多，进一步影响零碎的可用性； 还有1点不是Raft算法中自身的性能，就是复原数据，即一个误操作须要回滚，则须要回放从前到后所有日志，这个工夫会十分长，这时如果有快照就能够疾速复原了。 mysql binlog、Redis的aof文件其实就相当于快照，只不过这些零碎没有实现Raft算法。 三、与快照相干的RPC 1、装置快照 RPC（InstallSnapshot RPC） 对于接管方规定如下 如果term < currentTerm立即回复如果是第一个分块（offset 为 0）则创立新的快照在指定的偏移量写入数据如果 done为 false，则回复并持续期待之后的数据保留快照文件，抛弃所有存在的或者局部有着更小索引号的快照如果现存的日志领有雷同的最初任期号和索引值，则前面的数据持续保留并且回复抛弃全副日志可能应用快照来复原状态机（并且装载快照中的集群配置）这些规定大部分应该好了解，局部规定解释下： 5、保留快照文件，抛弃所有存在的或者局部有着更小索引号的快照 如果说Follower曾经有快照了，并且快照最初索引为1000，而新的快照的索引为2000，则将后面的快照抛弃 6、如果现存的日志领有雷同的最初任期号和索引值，则前面的数据持续保留并且回复 意思说接管节点如果有相应的日志了，则前面的日志保留，此音讯能够间接回复。 打个比方，如果Follower B的索引曾经到2002，此索引对应的term为102，其中2000索引的term为101，如果这时收到一个装置快照的音讯，最初1条的term为101，最初1条的索引为2000，通过比照发现此日志曾经存在节点上，并且Term也对的上，因而2001之后的日志保留。 7、抛弃全副日志 下面条件满足后，将快照保留到本地，本地所有日志全副抛弃。 当然前提是后面的条件都不满足，具体不细述。 8、可能应用快照来复原状态机（并且装载快照中的集群配置） 复原状态机就不用说了，间接拿快照复原状态机的数据，举例来说KV零碎，发送的快照如果只有a=1, b=2这样的状态，即把所有数据清空，只保留下面2条数据。 并且装载快照中的集群配置，意思是说快照还蕴含集群配置信息，主是要为了反对集群成员更新； 所以快照必须以下信息： 最初一条日志的Index； 最初一条日志的Term； 生成快照时的集群配置信息； 状态机数据； 四、其它细节 1、何时生成快照 这个Raft算法并没有规定，看利用本人实现，像etcd是10000日志后产生1次快照，须要依据理论条件抉择。 2、谁生成日志快照 Raft算法并没有规定谁能够生成，即谁都能够生成，即符合条件1就能够生成，次要是为了切换为Leader的时候能够疾速应答新节点增加数据的状况。因为只有数据统一，谁生成都是一样的。

一、日志存储 每条日志存储内容如下： term：领导人所在任期 利用操作内容：由客户端发送的申请，须要被复制状态机（replicated state machine）执行的命令，如上是一个KV零碎，每一次的操作是对某个key的内容。 二、日志状态 日志大略分以下几个状态： 1、初始化 即刚被退出到零碎中 2、被提交 如果一条日志被少数节点收到，则该日志会被转为被提交，即能够被利用到状态机。 3、已利用 即曾经利用到状态机了，能够返回给客户端了。 三、与日志相干的音讯 1、AppendEntries RPC 这个音讯由Leader收回，有2个作用： A、将客户端发送的命令而产生的日志发送给Follower，从而推动日志达到统一的状态； B、心跳，表明集群中存在Leader，不必发动选举； 第一个场景是承受客户端命令后收回，并且等大部分Follower接管到才返回给客户端； 第二个场景由Leader定时收回； 相干规定如下： 1、对于Leader 于一个追随者来说，如果上一次收到的日志索引大于将要收到的日志索引（nextIndex）：通过AppendEntries RPC将 nextIndex 之后的所有日志条目发送进来如果发送胜利：将该追随者的 nextIndex和matchIndex更新如果因为日志不统一导致AppendEntries RPC失败：nextIndex递加并且从新发送（5.3 节）如果存在一个满足N > commitIndex和matchIndex[i] >= N并且log[N].term == currentTerm的 N，则将commitIndex赋值为 N下面一条规定好了解，以下面的举例来说： 假如节点从上到下别离是A、B、C、D、E，以后Leader是节点A，后面说过Leader针对每一个Follower会记录nextIndex和matchIndex，咱们假如最现实的状况，即A针对B记录的nextIndex是9，matchIndex是8，所以心跳音讯中的nextIndex是9，B收到音讯会查看nextIndex之前的日志是否在本地存在，因6-8的日志不存在，因而返回false，A因而将nextIndex回退至6才匹配上，而后将6-8的日志发送给B，并且将matchIndex和nextIndex也一并更新。 规定2比拟难了解： 如果存在一个满足N > commitIndex和matchIndex[i] >= N并且log[N].term == currentTerm的 N，则将commitIndex赋值为 N 重点是加粗的内容，说简略点以后Leader不能间接提交日志的term不为本人的，即不能间接提交后任的日志，举个例子： 这是5个节点的集群，服务器编号别离是 S1-S5，最下面是日志索引，每个框内的数字示意日志的term，最底下的字母示意场景，别离为a-e。 场景a：S1是Leader，term为2，并且将index为2的日志复制到S2上； 场景b：S1挂了，S5入选为Leader，term增长为3，S5在index为2的地位上接管到了新的日志； 场景c：S5挂了，S1入选为Leader，term增长为4，S1将index为2、term为2的日志复制到了S3上，此时曾经满足过半数了。 问题就在场景c：此时term为4，之前term为2的日志达到过半数了，S1是提交该日志呢还是不提交？ 如果S1提交的话，则index为2、term为2的日志就被利用到状态机中了，就不可吊销了； 此时S1如果挂了，来到场景d，S5是能够被选为leader的，因为依照之前的log比对策略来说，S5的最初一个log的term是3，比S2、S3、S4的最初一个log的term都大。 一旦S5被选举为leader，即场景d，S5会复制index为2、term为3的日志到上述机器上，这时候就会造成之前S1曾经提交的index为2的地位被从新笼罩，因而违反了一致性。 如果S1不提交，而是等到term4中有过半的日志了，而后再将之前的term的日志一起提交，即处于e场景，S1此时挂的话，S5就不能被选为leader了，因为S2、S3的最初一个log的term为4，比S5的3大，所以S5获取不到投票，进而S5就不可能去笼罩上述的提交。 总结下：Leader不能间接提交后任的日志，哪怕后任日志曾经被少数节点收到了，而是等等以后任期的日志被大多数节点接管后做提交后，间接的提交了后任的日志。 四、其它技术细节 ...

后面咱们介绍了Raft算法，接下来会分篇讲述每一个局部，明天讲述选举的细节。 在讲述选举之前，先介绍下Raft算法根底。 一、Raft根底 1、节点角色 在Raft中，在任意时刻，服务器节点只能是以下3个角色之一： Follower（跟随者）：系统启动时默认的角色，一般来说不参加客户端读、写申请，承受Leader发送过去的心跳追加日志，在Leader挂了之后转变为Candidate； Candidate（候选人）：如果以后没有Leader，Follower就转变为这个角色，这个角色会向其它节点发动投票申请，如果少数节点批准投票，则晋升为Leader； Leader（领导人）：承受客户端的读、写申请，协调整个日志的长久化和推动； 上面讲节点角色时对立用英文形容。 2、节点角色状态迁徙图 系统启动时，大家都是Follower，而后启动定时器，如果在指定工夫没有收到Leader的心跳，则将本人变成Candidate，而后向其它成员发动投票申请，如果收到过半以上成员的投票则Candidate晋升为Leader； Leader发送心跳给其它成员时如果收到的响应中term比本人的大，则进化成Follower； 3、逻辑时钟(term) 选举过程有个term参数，这个参数就是逻辑时钟，这是一个整数，全局递增；Raft 把工夫宰割成任意长度的任期，用term来标识每一届leader的任期，这样能够保障在一个任期内只有一个Leader。 逻辑时钟规定如下： Candidate发动选举时就将本人的term加1，而后发动投票申请； 收到投票申请的节点比拟申请的term和本人的term，如果申请的term比本人的大，则更新本人的term； 这样在即便每个节点的工夫不一样的状况下也能够推动逻辑时钟； 4、状态 下面的状态是所有节点都要保留的，并且要长久化的，即每次变更马上要写入磁盘。 下面的状态是保留在内在中，每次重启后都0开始，即不须要长久化到磁盘上。 上述只有在Leader节点才会须要保留，并且是也是保留在内存中，不须要长久化，重启后从0开始。 二、领导人选举 领导人选举产生的条件为Follower没收到Leader的心跳，具体场景个别如下： 1、系统启动时 2、Leader挂了或网络分区了 具体细节如下： 1、申请投票 RPC 由候选人发动 返回值 接管申请投票的节点响应规定如下： 如果term < currentTerm返回 false；如果 votedFor 为空或者为 candidateId，并且候选人的日志至多和本人一样新，那么就投票给他；第1条规定好了解，第2条规定后面局部是为了保障在一个任期内每个节点只投1票，后面也说过这个信息是要长久化的； 候选人的日志至多和本人一样新：这里说的就比拟抽象了，这里的意思是要看下各自最初1条日志，即两者的索引号和term都对的上，咱们看一个理论的例子： 下面的例子从上往下假如别离为A、B、C、D、E节点，A以后为Leader，各节点日志索引如下： A：8 B：5 C：8 D：2 E：7 如果这时候A挂了，如果D最先降级为Candidate，B、C、E收到申请后都不会为D投票，拿B来说，B发现D的最初一条日志索引为2，而本人的日志索引为8，因而回绝B的申请。 对于选举还有其它一些规定： 1、针对Follower 如果在超过选举超时工夫的状况之前都没有收到Leader的心跳，或者是Candidate申请投票的，就本人变成Candidate; 2、针对Candidate 开始选举后的动作如下： 自增以后的任期号（currentTerm）; 给本人投票; 重置选举超时计时器; 发送申请投票的 RPC 给其余所有服务器; ...

一、Raft算法介绍 Raft是一种“共识”算法，共识的含意是保障所有的参与者都有雷同的认知，简略来说就是如何做到强统一。 “共识”蕴含服务器之间及客户端和服务端两方面： 1、服务器之间 指的是所有服务器要达成“共识”，打个比方一个KV零碎像Redis，如果服务端是3个节点：A、B、C的集群，客户端先收回一个set key1 a的命令落在A节点上，而后收回 set key1 b落在B节点上，最初应该在所有服务器上执行get key1都应该失去b； 2、 客户端和服务端之间 还是回到下面的例子，客户端执行 set key1 a的命令，服务端返回胜利了，客户端就认为这里是胜利了，两头不能因为网络或其它起因导致客户端取key1的时候返回空或不为a的状况。 “共识”算法次要解决分布式系统的一致性的问题，目前相干的算法有： 1、Paxos算法 这个是最早的，也是非常复杂的，说实话我看了好多文章，也只是大略懂了，细节还是不太分明，还是要观看一些实现代码能力加深了解； 2、Raft算法 就是咱们明天要介绍的，由斯坦福大学的Diego Ongaro和John Ousterhout在2014年提出，在证实了算法的正确性之外，还提供了相干实现及参考代码，所以媒体始终宣传这个算法比Paxos要更容易了解； 3、ZAB算法 Zookeeper应用的算法，算是Paxos算法的一个变种，有趣味的能够到 Apache官网学习下，联合Zookeeper源码学习下。 二、Raft算法利用场景及案例 下面介绍了分布式相干算法，Raft相对来说比拟容易上手，如果要深入研究，Paxox是防止不了的；留神是绝对简略，因为进入剖析之后你会发现远没你想像的简略，以我目前学习进度看，学习快3周工夫才大略理解了一些细节。 学习的形式是先看官网的介绍，以下是其官方网站： https://raft.github.io/raft.pdf 还有个动画介绍的： http://thesecretlivesofdata.c... 当然还有中文版的，搜寻下raft paper中文版就能够了。 目前开源的实现也不少： Etcd(Go语言实现） PingCAP(Rust语言，Codis作者所在公司) Soft-Jraft(Java语言，阿里开源) 下面几个都是大公司实现的，能够用在生产上，性能也比拟全，代码相对来说简单些，如果先只想简略搞个Demo剖析下，能够看以下几个： 1、百度工程师开源的Java实现 https://github.com/wenweihu86... 2、支付宝工程师实现 也是Java写的，不过性能比拟少，没有PreVote等性能，作者还出了本书：《分布式一致性算法开发实战》，倡议带着书学习下： https://github.com/xnnyygn/xraft 以下是集体学习路线仅供参考：先看论文，即实践，而后跑代码，而后再反过来看实践，最初到了你不必看论文就晓得相应规定就能够熟练掌握了。 三、Raft算法整体介绍 因Raft算法内容比拟多，前面会分几篇介绍，这篇先大略介绍下整体的货色。 官网将Raft算法分为以下几块：选举、日志复制、安全性3大块，从实现的角度分：选举、日志、新节点退出。 另外如果要实现一个残缺的利用的话，还要实现状态机的局部；什么是状态机呢，状态机指零碎/对象自身有多种状态，而后各种状态分产生切换、转变，其实大部分分布式系统都能够转移为状态机，而后各节点之间以统一的步骤转换状态，大家的状态就是统一了，对利用来说就是强统一了。 还是以后面的redis为例，假如客户端发过来的命令流如下： set key1 a 状态：key1:a set key2 b 状态：key1:a, key2:b 即客户端每1次操作都会引起服务端状态的扭转，而后把整个批改当成一个序列，则整个就是状态机了。 回到Raft算法，咱们看下每块要解决的问题： 1、选举 Raft算法只反对单主，即任何时候只能从主上进行证读写操作，所以选举要解决以下问题： 以后谁是主节点； 如何保障肯定会只选出一个主节点； ...

摘要：简略介绍Raft协定的原理、以及存储节点(Pinetree)如何利用 Raft实现复制的一些工程实践经验。1、引言在华为分布式数据库的工程实际过程中，咱们实现了一个计算存储拆散、 底层存储基于Raft协定进行复制的分布式数据库系统原型。上面是它的架构图。 计算节点生成日志通过封装后通过网络下发到存储节点，在Raft层达成统一后日志被利用到状态机wal Engine,实现日志的回放和数据的存储管理。 上面简略介绍一下Raft的原理、以及存储节点(Pinetree)如何利用 Raft实现复制的一些工程实践经验。 2、Raft的原理 2.1 Raft的基本原理Raft 算法所有以领导者为准，实现一系列值的共识和各节点日志的统一。上面重点介绍一下Raft协定的Leader选举、log复制 和 成员变更。 Raft的选举机制: 协定为每个节点定义了三个状态：Leader、Candidate、Follower，将工夫定义为Term，每个Term有一个ID。Term相似逻辑时钟，在每个Term都会有Leader被选举进去。 Leader负责解决所有的写申请、发动日志复制、定时心跳，每个Term期间最多只能有一个Leader，可能会存在选举失败的场景，那么这个Term内是没有Leader。 Follower 处于被动状态，负责解决Leader发过来的RPC申请，并且做出回应。 Candidate 是用来选举一个新的Leader，当Follower超时，就会进入Candidate状态。 初始状态，所有的节点都处于Follower状态，节点超时后，递增current Term进入Candidate，该节点发送播送音讯RequestVote RPC给其余Follower申请投票。当收到少数节点的投票后，该节点从Candidate进入Leader。Follower在收到投票申请后，会首先比拟Term，而后再比拟日志index，如果都满足则更新本地Current Term而后回应RequestVote RPC为其投票。每个Term期间，follower只能投一次票。 Raft的日志同步机制: 当Leader被选举进去后，就能够承受写申请。每个写申请即代表了用户须要复制的指令或Command。Raft协定会给写申请包装上Term和Index，由此组成了Raft的Log entry. Leader把Log entry append到日志中，而后给其它的节点发AppendEntries RPC申请。当Leader确定一个Log entry被大多数节点曾经写入日志当中，就apply这条Log entry到状态机中而后返回后果给客户端。 Raft成员变更机制: 成员变更就意味着集群节点数的减少或缩小以及替换。Raft协定定义时思考了成员变更的场景，从而防止因为集群变动引起的零碎不可用。Raft是利用下面的Log Entry和一致性协定来实现该性能。成员的变更也是由Leader发动的，Leader会在本地生成一个新的Log entry，同时将Log entry推送到其余的Follower节点。 Follower节点收到Log entry后更新本地日志，并且利用该log中的配置关系。少数节点利用后，Leader就会提交这条变更log entry。还要思考新就配置的更替所带来的问题。更具体的不再赘述。 2.2 Raft的开源实现Raft的实现有coreos的etcd/raft、kudu、consul、logcabin、cockroach等。 Etcd 、LogCabin 、Consul 实现的是单个Raft环，无奈做到弹性伸缩。而kudu和cockroach实现了多个raft环。kudu的consensus 模块实现了正本的数据复制一致性，kudu将数据分片称之为Tablet, 是kudu table的程度分表，TabletPeer就是在Raft环外面的一个节点. 一个Tablet相当于一个Raft环，一个Tablet对应一个Raft Consensus，这些对应Raft外面的一个环，Consensus Round相当于同步的音讯，一个环之间会有多个Consensus Round做同步。而cockroach则是基于etcd/raft实现的多Raft环，它保护了多个Raft实例，被称之为multiraft。 因为Etcd的Raft是目前性能较全的Raft实现之一，最早利用于生产环境，并且做到了很好的模块化。其中Raft内核局部实现了Raft大部分协定，而对外则提供了storage和transport所用的interface，对于使用者能够独自实现灵活性较高，用户还能够自主实现 snapshot、wal ，Raft十分便于移植和利用，因而存储节点Pinetree采纳了开源的Etcd中的Raft实现来构建咱们的原型零碎，也便于前期向Multiraft演进。。 3、工程实际3.1 实现Raft的存储接口和网络传输Raft存储局部指的是raft- log的存储，是对日志条目进行长久化的存储，通过benchmark测试发现，raft-log引擎性能是影响整体ops的次要瓶颈，为了更灵便的反对底层存储引擎的疾速替换，减少可插拔的存储引擎框架，咱们对底层存储引擎进行解耦。Pinetree封装了第三方独立存储接口来适配etcd raft的log存储接口； 通信局部即Raft Transport、snapShot传输等，采纳GRPC+Protobuf来实现，心跳、日志传输AppendEntries RPC、选举RequestVote RPC等利用场景将GRPC设置为简略式，snapShot设置为流式的模式。 ...

在互联网的高速倒退下，如果服务器不应用个集群模式，本人都不好意思进来面试。目前所知的大部分集群模式都是基于中心化思维来部署，而中心化的思维是建设在服务器选举Leader规定之上，驰名的一致性算法Raft能够实现集群的选举工作，不过Raft算法也不是个别程序员能够把握的。 集群的选举次要是为了能让集群失常工作，在不应用Raft等简单算法的前提下，是否能够搞定集群的选举工作呢？当然能够，不过要借助其余技术，明天就来说一说，如何利用zookeeper来搞定集群选举Leader的工作。 ZookeeperZooKeeper是一个分布式的，开放源码的分布式应用程序协调服务，是Google的Chubby一个开源的实现，是Hadoop和Hbase的重要组件。它是一个为分布式应用提供一致性服务的软件，提供的性能包含：配置保护、域名服务、分布式同步、组服务等。Zookeeper的节点相似于UNIX文件系统，是一个简略目录树结构的数据模型，在这棵树中，每个节点都能够作为一个ZNode，每一个ZNode都能够通过惟一门路来标识 临时性节点在Zookeeper中，节点（ZNode）分为几个类型，其中有一个类型为临时性节点，它有个特点：它的生命周期和创立这个节点的客户端Session绑定，一旦这个客户端掉线或者down机，这个节点就会主动删除。 WatchZookeeper提供了节点变动告诉机制，即Watch机制。每个客户端能够抉择任意的节点进行监听，如果被监听的节点或者子节点发生变化，便会告诉所有监听的客户端，基于这个原理就能实现集群服务器的主动发现机制。 集群的选举一个分布式的集群服务，最重要的就是不间断的提供服务，或者说是容错性。当一个节点因为故障起因退出集群或者一个新节点退出集群，不会影响集群的服务能力。当Leader节点呈现故障，能实现主动选举性能，而不必人工干预，那利用Zookeeper怎么做到呢？ 首先必须要有几个约定： 所有的集群服务器监听雷同的Zookeeper节点，这个节点充当集群信息的存储集群中的服务器能够利用ip或者机器名作为节点名称，不容许有反复的节点名称集群默认采纳名称排序最小的服务器作为Leader具体的过程如下： 当集群的第一个服务器启动，注册本人的信息到Zookeeper固定节点下，并监听此节点的变动。发现只有本人一个服务器，则默认入选Leader。当其余服务器启动并注册信息到雷同节点下，并监听此节点信息变动。发现曾经有Leader，默认作为follower进行工作。当Leader因为故障掉线，信息会主动从Zookeeper删除，其余节点会收到告诉，而后把Leader节点踢除，进入下一个Leader选举流程。存活的服务器中，依据约定，名字最小的服务器入选Leader，并向其余服务器发送告诉，这个时候集群能够持续失常工作。如果是非Leader节点掉线，流程和以上相似，然而少了选举的过程。就算是在选举过程中继续有客户端掉线也没有关系，因为Zookeeper能保障最终的数据一致性，在加上咱们约定的名字最小的为Leader的束缚，最终集群的状态将达到稳固。 这里提出一个新问题，利用Zookeeper来进行集群的选举，会不会呈现脑裂问题呢？ 更多精彩文章 分布式大并发系列架构设计系列趣学算法和数据结构系列设计模式系列

1. Raft是一种易于理解的共识算法。 运行分布式系统的一个基本问题是确保当节点故障时它们是可靠的。通常，CPU可能会过热，HDD可能会损坏，网络可能不可靠，可能会发生电源中断，并且这种情况还会持续下去。至关重要的是要假设会发生故障，并且我们需要一种方法来确保分布式系统可以承受故障。共识算法用于确保分布式系统具有容错能力，还用于确保节点在值上达成一致。例如，即使其中2台服务器发生故障并且它们的状态/值一致，由5台服务器组成的集群仍将可操作。 由图灵奖获得者莱斯利·兰波特（Leslie Lamport）创建的一种称为Paxos的共识协议因难以理解而闻名。 Lamport的描述主要是关于单Paxos。他勾画出了实现多Paxos的可能方法，但是缺少许多细节。即使存在Neo4j，Google Spanner和Cassandra等基于多Paxos的著名应用程序，它们与Paxos几乎没有相似之处。 Raft的创建易于理解且性能卓越。它旨在让大量读者轻松地理解算法，系统构建者可以在现实世界中进行不可避免的扩展。 2.Raft使用基于领导者的方法. Raft共识协议是一种基于领导者的方法，与Paxos等对等（P2P）方法相反。 Raft通过首先选举一位杰出的领导者，然后赋予领导者完全责任来管理复制日志来实现共识。您一定想知道什么是复制日志。 共识算法本质上是复制状态机的实现，用于解决分布式系统中的各种容错问题。通常使用每个服务器中都存在的复制日志（命令序列）来实现复制状态机。共识模块的工作是确保复制的日志在整个群集中保持一致。因此，状态机是确定性的，即每个状态机计算相同的状态和相同的输出序列。 3.每个节点在任何给定时间处于三种可能状态之一。 在Raft中，有三种可能的状态：领导者，候选人和追随者。 领导者负责将日志复制到关注者。它通过发送心跳消息定期通知跟随者其存在。 每个跟随者都有一个超时（通常在150到300毫秒之间），在该超时中，期望跟随者的心跳。收到心跳后，超时将重置。 如果未收到心跳，则追随者将其状态更改为候选者，并开始进行领导者选举。 4.Raft的安全性能保证。 Raft保证以下安全属性： 选举安全：在给定的任期内最多可以选举一位领导人。仅领导者追加：领导者只能将新条目追加到其日志中（既不能覆盖也不能删除条目）。日志匹配：如果两个日志包含具有相同索引和术语的条目，则直到给定索引的所有条目中的日志都是相同的。领导者完整性：如果在给定期限内提交了日志条目，则自该术语以来，它将出现在领导者的日志中状态机安全性：如果服务器已将特定的日志条目应用于其状态机，则没有其他服务器可以对同一日志应用不同的命令。5.Kubernetes的数据存储基于Raft。 Kubernetes由名为etcd的分布式键值存储支持，该存储用于存储和复制集群的状态。在内部，etcd使用Raft来确保一致性和容错能力。没有etcd，Kubernetes将无法在所有群集上协调任务，例如配置，部署，服务发现，负载平衡，作业调度和运行状况监视，这些群集可以在多个位置的多台机器上运行。 PS: 本文属于翻译，原文

原文地址: https://qeesung.github.io/202... Raft 集群成员变更在前面三个章节中，我们介绍了Raft的： 领导人选举日志复制安全性上面的讨论都是基于Raft集群成员恒定不变的，然而在很多时候，集群的节点可能需要进行维护，或者是因为需要扩容，那么就难以避免的需要向Raft集群中添加和删除节点。最简单的方式就是停止整个集群，更改集群的静态配置，然后重新启动集群，但是这样就丧失了集群的可用性，往往是不可取的，所以Raft提供了两种在不停机的情况下，动态的更改集群成员的方式： 单节点成员变更：One Server ConfChange多节点联合共识：Joint Consensus动态成员变更存在的问题在Raft中有一个很重要的安全性保证就是只有一个Leader，如果我们在不加任何限制的情况下，动态的向集群中添加成员，那么就可能导致同一个任期下存在多个Leader的情况，这是非常危险的。 如下图所示，从Cold迁移到Cnew的过程中，因为各个节点收到最新配置的实际不一样，那么肯能导致在同一任期下多个Leader同时存在。 比如图中此时Server3宕机了，然后Server1和Server5同时超时发起选举： Server1：此时Server1中的配置还是Cold，只需要Server1和Server2就能够组成集群的Majority，因此可以被选举为LeaderServer5：已经收到Cnew的配置，使用Cnew的配置，此时只需要Server3，Server4，Server5就可以组成集群的Majority，因为可以被选举为Leader换句话说，以Cold和Cnew作为配置的节点在同一任期下可以分别选出Leader。 所以为了解决上面的问题，在集群成员变更的时候需要作出一些限定。 单节点成员变更所谓单节点成员变更，就是每次只想集群中添加或移除一个节点。比如说以前集群中存在三个节点，现在需要将集群拓展为五个节点，那么就需要一个一个节点的添加，而不是一次添加两个节点。 这个为什么安全呢？很容易枚举出所有情况，原有集群奇偶数节点情况下，分别添加和删除一个节点。在下图中可以看出，如果每次只增加和删除一个节点，那么Cold的Majority和Cnew的Majority之间一定存在交集，也就说是在同一个Term中，Cold和Cnew中交集的那一个节点只会进行一次投票，要么投票给Cold，要么投票给Cnew，这样就避免了同一Term下出现两个Leader。 变更的流程如下： 向Leader提交一个成员变更请求，请求的内容为服务节点的是添加还是移除，以及服务节点的地址信息Leader在收到请求以后，回向日志中追加一条ConfChange的日志，其中包含了Cnew，后续这些日志会随着AppendEntries的RPC同步所有的Follower节点中当ConfChange的日志被添加到日志中是立即生效（注意：不是等到提交以后才生效）当ConfChange的日志被复制到Cnew的Majority服务器上时，那么就可以对日志进行提交了以上就是整个单节点的变更流程，在日志被提交以后，那么就可以： 马上响应客户端，变更已经完成如果变更过程中移除了服务器，那么服务器可以关机了可以开始下一轮的成员变更了，注意在上一次变更没有结束之前，是不允许开始下一次变更的可用性可用性问题在我们向集群添加或者删除一个节点以后，可能会导致服务的不可用，比如向一个有三个节点的集群中添加一个干净的，没有任何日志的新节点，在添加节点以后，原集群中的一个Follower宕机了，那么此时集群中还有三个节点可用，满足Majority，但是因为其中新加入的节点是干净的，没有任何日志的节点，需要花时间追赶最新的日志，所以在新节点追赶日志期间，整个服务是不可用的。 在接下来的子章节中，我们将会讨论三个服务的可用性问题： 追赶新的服务器移除当前的Leader中断服务器追赶新的服务器在添加服务器以后，如果新的服务器需要花很长时间来追赶日志，那么这段时间内服务不可用。 如下图所示： 左图：向集群中添加新的服务器S4以后，S3宕机了，那么此时因为S4需要追赶日志，此时不可用右图：向集群中添加多个服务器，那么添加以后Majority肯定是包含新的服务器的，那么此时S4，S5，S6需要追赶日志，肯定也是不可用的 新加入集群中的节点可能并不是因为需要追赶大量的日志而不可用，也有可能是因为网络不通，或者是网速太慢，导致需要花很长的时间追赶日志。 在Raft中提供了两种解决方案： 在集群中加入新的角色Leaner，Leaner只对集群的日志进行复制，并不参加投票和提交决定，在需要添加新节点的情况下，添加Leaner即可。加入一个新的Phase，这个阶段会在固定的Rounds（比如10）内尝试追赶日志，最后一轮追赶日志的时间如果小于ElectionTimeout, 那么说明追赶上了，否则就抛出异常下面我们就详细讨论一下第二种方案。 在固定Rounds内追赶日志如果需要添加的新的节点在很短时间内可以追赶上最新的日志，那么就可以将该节点添加到集群中。那要怎么判断这个新的节点是否可以很快时间内追赶上最新的日志呢？ Raft提供了一种方法，在配置变更之前引入一个新的阶段，这个阶段会分为多个Rounds（比如10）向Leader同步日志，如果新节点能够正常的同步日志，那么每一轮的日志同步时间都将缩短，如果在最后一轮Round同步日志消耗的时间小于ElectionTimeout，那么说明新节点的日志和Leader的日志已经足够接近，可以将新节点加入到集群中。但是如果最后一轮的Round的日志同步时间大于ElectionTimeout，就应该立即终止成员变更。 移除当前的Leader如果在Cnew中不包含当前的Leader所在节点，那么如果Leader在收到Cnew配置以后，马上退位成为Follower，那么将会导致下面的问题： ConfChange的日志尚未复制到Cnew中的大多数的节点马上退位成为Follower的可能因为超时成为新的Leader，因为该节点上的日志是最新的，因为日志的安全性，该节点并不会为其他节点投票为了解决以上的问题，一种很简单的方式就是通过Raft的拓展Leadership transfer首先将Leader转移到其他节点，然后再进行成员变更，但是对于不支持Leadership transfer的服务来说就行不通了。 Raft中提供了一种策略，Leader应该在Cnew日志提交以后才退位。 中断的服务器如果Cnew中移除了原有集群中的节点，因为被移除的节点是不会再收到心跳信息，那么将会超时发起一轮选举，将会造成当前的Leader成为Follower，但是因为被移除的节点不包含Cnew的配置，所以最终会导致Cnew中的部分节点超时，重新选举Leader。如此反反复复的选举将会造成很差的可用性。 一种比较直观的方式是采用Pre-Vote方式，在任何节点发起一轮选举之前，就应该提前的发出一个Pre-Vote的RPC询问是否当前节点会同意给当前节点投票，如果超过半数的节点同意投票，那么才发生真正的投票流程的，有点类似于Two-Phase-Commit，这种方式在正常情况下，因为被移除的节点没有包含Cnew的ConfChange日志，所以在Pre-Vote情况下，大多数节点都会拒绝已经被移除节点的Pre-Vote请求。 但是上面只能处理大多数正常的情况，如果Leader收到Cnew的请求后，尚未将Cnew的ConfChange日志复制到集群中的大多数，Cnew中被移除的节点就超时开始选举了，那么Pre-Vote此时是没有用的，被移除的节点仍有可能选举成功。顺便一说，这里的Pre-Vote虽然不能解决目前的问题，但是针对脑裂而产生的任期爆炸式增长和很有用的，这里就不展开讨论了。 就如下图所示，S4收到Cnew成员变更的请求，立马将其写入日志中，Cnew中并不包含S1节点，所以在S4将日志复制到S2，S3之前，如果S1超时了，S2，S3中因为没有最新的Cnew日志，仍让会投票给S1，此时S1就能选举成功，这不是我们想看到的。 Raft中提供了另一种方式来避免这个问题，如果每一个服务器如果在ElectionTimeout内收到现有Leader的心跳（换句话说，在租约期内，仍然臣服于其他的Leader），那么就不会更新自己的现有Term以及同意投票。这样每一个Follower就会变得很稳定，除非自己已经知道的Leader已经不发送心跳给自己了，否则会一直臣服于当前的leader，尽管收到其他更高的Term的服务器投票请求。 任意节点的Joint Consensus上面我们提到单节点的成员变更，很多时候这已经能满足我们的需求了，但是有些时候我们可能会需要随意的的集群成员变更，每次变更多个节点，那么我们就需要Raft的Joint Consensus, 尽管这会引入很多的复杂性。 Joint Consensus会将集群的配置转换到一个临时状态，然后开始变更： Leader收到Cnew的成员变更请求，然后生成一个Cold,new的ConfChang日志，马上应用该日志，然后将日志通过AppendEntries请求复制到Follower中，收到该ConfChange的节点马上应用该配置作为当前节点的配置在将Cold,new日志复制到大多数节点上时，那么Cold,new的日志就可以提交了，在Cold,new的ConfChange日志被提交以后，马上创建一个Cnew的ConfChange的日志，并将该日志通过AppendEntries请求复制到Follower中，收到该ConfChange的节点马上应用该配置作为当前节点的配置一旦Cnew的日志复制到大多数节点上时，那么Cnew的日志就可以提交了，在Cnew日志提交以后，就可以开始下一轮的成员变更了为了理解上面的流程，我们有几个概念需要解释一下： Cold,new：这个配置是指Cold，和Cnew的联合配置，其值为Cold和Cnew的配置的交集，比如Cold为[A, B, C]， Cnew为[B, C, D]，那么Cold,new就为[A, B, C, D]Cold,new的大多数：是指Cold中的大多数和Cnew中的大多数，如下表所示，第一列因为Cnew的C, D没有Replicate到日志，所以并不能达到一致ColdCnewReplicate结果是否是MajorityA, B, CB, C, DA+, B+, C-, D-否A, B, CB, C, DA+, B+, C+, D-是A, B, CB, C, DA-, B+, C+, D-是由上可以看出，整个集群的变更分为几个过渡期，就如下图所示，在每一个时期，每一个任期下都不可能出现两个Leader： ...

作者：黄梦龙 背景知识TiKV 使用 Raft 算法来提供高可用且具有强一致性的存储服务。在 Raft 中，Snapshot 指的是整个 State Machine 数据的一份快照，大体上有以下这几种情况需要用到 Snapshot： 正常情况下 leader 与 follower/learner 之间是通过 append log 的方式进行同步的，出于空间和效率的考虑，leader 会定期清理过老的 log。假如 follower/learner 出现宕机或者网络隔离，恢复以后可能所缺的 log 已经在 leader 节点被清理掉了，此时只能通过 Snapshot 的方式进行同步。Raft 加入新的节点的，由于新节点没同步过任何日志，只能通过接收 Snapshot 的方式来同步。实际上这也可以认为是 1 的一种特殊情形。出于备份/恢复等需求，应用层需要 dump 一份 State Machine 的完整数据。TiKV 涉及到的是 1 和 2 这两种情况。在我们的实现中，Snapshot 总是由 Region leader 所在的 TiKV 生成，通过网络发送给 Region follower/learner 所在的 TiKV。 理论上讲，我们完全可以把 Snapshot 当作普通的 RaftMessage 来发送，但这样做实践上会产生一些问题，主要是因为 Snapshot 消息的尺寸远大于其他 RaftMessage： Snapshot 消息需要花费更长的时间来发送，如果共用网络连接容易导致网络拥塞，进而引起其他 Region 出现 Raft 选举超时等问题。构建待发送 Snapshot 消息需要消耗更多的内存。过大的消息可能导致超出 gRPC 的 Message Size 限制等问题。基于上面的原因，TiKV 对 Snapshot 的发送和接收进行了特殊处理，为每个 Snapshot 创建单独的网络连接，并将 Snapshot 拆分成 1M 大小的多个 Chunk 进行传输。 ...

通过阅读NACOS的源码，了解其心跳与选举机制。开始阅读此篇文章之前，建议先阅读如下两篇文章： Spring Cloud Alibaba Nacos（功能篇） Spring Cloud Alibaba Nacos（源码篇） 一、心跳机制只有NACOS服务与所注册的Instance之间才会有直接的心跳维持机制，换言之，这是一种典型的集中式管理机制。 在client这一侧是心跳的发起源，进入NacosNamingService，可以发现，只有注册服务实例的时候才会构造心跳包： @Override public void registerInstance(String serviceName, String groupName, Instance instance) throws NacosException { if (instance.isEphemeral()) { BeatInfo beatInfo = new BeatInfo(); beatInfo.setServiceName(NamingUtils.getGroupedName(serviceName, groupName)); beatInfo.setIp(instance.getIp()); beatInfo.setPort(instance.getPort()); beatInfo.setCluster(instance.getClusterName()); beatInfo.setWeight(instance.getWeight()); beatInfo.setMetadata(instance.getMetadata()); beatInfo.setScheduled(false); beatReactor.addBeatInfo(NamingUtils.getGroupedName(serviceName, groupName), beatInfo); } serverProxy.registerService(NamingUtils.getGroupedName(serviceName, groupName), groupName, instance); }没有特殊情况，目前ephemeral都是true。BeatReactor维护了一个Map对象，记录了需要发送心跳的BeatInfo，构造了一个心跳包后，BeatReactor.addBeatInfo方法将BeatInfo放入Map中。然后，内部有一个定时器，每隔5秒发送一次心跳。 class BeatProcessor implements Runnable { @Override public void run() { try { for (Map.Entry<String, BeatInfo> entry : dom2Beat.entrySet()) { BeatInfo beatInfo = entry.getValue(); if (beatInfo.isScheduled()) { continue; } beatInfo.setScheduled(true); executorService.schedule(new BeatTask(beatInfo), 0, TimeUnit.MILLISECONDS); } } catch (Exception e) { NAMING_LOGGER.error("[CLIENT-BEAT] Exception while scheduling beat.", e); } finally { executorService.schedule(this, clientBeatInterval, TimeUnit.MILLISECONDS); } } }通过设置scheduled的值来控制是否已经下发了心跳任务，具体的心跳任务逻辑放在了BeatTask。 ...

共识：一致同意，完整（只决定一次），有效，终止（宕机不回来）。要多数都同意，很慢。paxos完全符合，单raft,zap考虑的是宕机还会回来的情况，用日志保证。能解决诸如以下问题： 全序广播相当于重复多伦共识：但raft和zap等直接实现全序广播内有一次一值的共识。单领导者选取：1选出一位领导者，2对领导者的提议进行表决（防止1，一个节点相信自己是领导）投票是同步的，动态成员扩展难，依靠超时检测节点失效，若只有一条特定网络不可靠，会进入领导频繁二人转局面共识算法raft数据一致性是通过日志复制的方式，client发给leader(写只发给leader，follower备份恢复用),leader写入日志，同步给follower，当多数follower写入日志并返回给leader时，leader提交数据，返回给客户端确认消息, 发给follower数据已提交，follower提交数据，发回确认给leader。所有的发送都随着调频发过去。raft中所有server之间的通信都是RPC调用，并且只有两种类型的RPC调用：第一种是RequestVote，用于选举leader；第二种是AppendEntries。日志和投票结果都需要持续化写在磁盘中，保证宕机后重启任然正常。 leader(有任期字段term)，candidate, follower.每个节点有在T到2T之间随机选择超时时间。leader和follower通过跳频联系。当一个follower收不到leader的跳频超时时将发起投自己的票。任何一个follower只能投一票。当一轮投票结束有多个候选者时，这几个候选者重新分配随机的超时时间。 当确认提交后，leader会一直不断地重试提交的rpc给follower、重试，直到请求成功；即使follower宕机了，重启后leader仍会接着发请求，直到请求成功，当leader宕机，如何向follower继续发；1.leader的日志只能增加，=》所以在选择时选term大,log长的 2.leader会把自己的log复制到其他机器，如果新达到多数并且此任期已有数据过半（挂前的一次数据不会被重复提交）就提交，只提交新任期的，同步还是要同步。为了恢复log一致性，leader为集群中所有follower都保存一个状态变量，即nextIndex：1）nextIndex是leader准备向某个follower发送的下一个log entry的index；2）当leader刚刚即位后，nextIndex的初始值是（1+leader's last index）；当leader看到请求被拒绝时，其动作非常简单：只需将nextIndex-1，再次尝试。 term需要存盘任意一个server在一个term内只能投出一票；一旦已经投给了一个candidate，它必须拒绝其他candidate的投票请求；其实server根本不在意把票投给谁，它只会把票投给最先到请求到它的candidate；为了保证这一点，必须把投票信息持久保存到磁盘上，这样可以保证即使该server投完票后宕机，稍后又立即重启了，也不会在同一个term内给第二个candidate投票了。每个日志entry：iterm+index.每次发送AppendEntries时需要带上一次的，检查是否一样，一样才接受来保证所有机器log一致， paxosbasic paxos 这里有个错误。第二阶段若N>=ResN,接受提案，若N<ResN不接受。实际上这里的proposal是leader。共识算法正常是proposor,leader,accepter,leaner（先忽略），用来决议proposer的提议号和是否成功的。每次proposal先到leader(可随机选取，不重要)，leader发给accepter若没有冲突返回any否则返回已选的，继续上述过程。 问题：多个Proposal可能出现死锁一直循环递增N的情况： 上面这个是https://www.microsoft.com/en-... 为了方便理解，去除了实现细节。实时上再应用中，客户端不会自己处理冲突+1再次投票和发送给其他leaner，这些应该由另一个角色，在basic中，由一群c协调者，可以和acceptor一样，或者是其中的部分构成，每轮随机一个c作为leader，负责收集本轮结果和通知leaner。proposal->leader(每个client随机发就可以作为本轮leader)->pre->acceptors返回最大N的值V->带N请求->acceptors->leader->返回给proposal->client失败或者成功或再次投票->投票成功后发给leaner。此过程中CLIENT2再次发送是另一个leader。 fast paxos 若proposal和acceptor,leader,leaner都是分布式，且要持久化，持久化+发送来回的代价就多了，若leader发现没有冲突，不再参与，proposal直接提交给acceptor（同一轮只投给先到的），直接发送给leaner，可以理解为基于乐观锁的思想，leaner和CLIENT都自行决议， 若proposal没有决策成功（先到的就是投票，没有半数以上的），1.重新引入leader，异步发送给协调者，协调者选择（因为acceptor只投一次）,发给proposal结果。（再次引入leader）2.无leader，在acceptor决议后发送给所有acceptor，其他acceptor收到此消息后对i+1轮的可以比较投票（即使同时刻一个一半也可以再比较投一次）。https://www.microsoft.com/en-...muti-paxos 当leader稳定，可以省去prepare阶段 具体做法如下：　① 当某个副本节点通过选举成为Master后，就会使用新分配的编号N来广播一个Prepare消息，该Prepare消息会被所有未达成一致的Instance和目前还未开始的Instance共用。 ② 当Acceptor接收到Prepare消息后，必须对多个Instance同时做出回应，这通常可以通过将反馈信息封装在一个数据包中来实现，假设最多允许K个Instance同时进行提议值的选定，那么： -当前之多存在K个未达成一致的Instance，将这些未决的Instance各自最后接受的提议值封装进一个数据包，并作为Promise消息返回。 -同时，判断N是否大于当前Acceptor的highestPromisedNum值（当前已经接受的最大的提议编号值），如果大于，那么就标记这些未决Instance和所有未来的Instance的highestPromisedNum的值为N，这样，这些未决Instance和所有未来Instance都不能再接受任何编号小于N的提议。 ③ Master对所有未决Instance和所有未来Instance分别执行Propose->Accept阶段的处理，如果Master能够一直稳定运行的话，那么在接下来的算法运行过程中，就不再需要进行Prepare->Promise处理了。但是，一旦Master发现Acceptor返回了一个Reject消息，说明集群中存在另一个Master并且试图使用更大的提议编号发送了Prepare消息，此时，当前Master就需要重新分配新的提议编号并再次进行Prepare->Promise阶段的处理。 可见chubby就是一个典型的Muti-Paxos算法应用，在Master稳定运行的情况下，只需要使用同一个编号来依次执行每一个Instance的Promise->Accept阶段处理。 raft和paxos区别raft要有一个leader。在选主时每个follower只能投一次，不成功随机时间下一次。有主时的共识由主来给日志编号，比较就好。follower保证稳定可替换即可。paxos leader不能那么重要（fast paxos在无冲突时甚至无leader参与），每次可以随机选，只是汇总投票，prososol是否通过由多数决定，prososol回复客户端和同步其他leaner。算是无主的模型。zap还是有leader的。zap在无主的时候选举算法和fast paxos很像，有最大xid（类似pre阶段，只不过是上次存好的），每次投票直接给acceptor并且无协调者的冲突处理。在有主时，用paxos的思想先pre收集并同步信息保证一致，主处理写，多数处理成功后回复。 优势就是单主能不能抗住了。 zookeeperZookeeper对于每个节点QuorumPeer的设计相当的灵活，QuorumPeer主要包括四个组件：客户端请求接收器(ServerCnxnFactory)、数据引擎(ZKDatabase)、选举器(Election)、核心功能组件（Leader/Follower/Observer不同） 采用了递增的事务id号（zxid）来标识事务。所有的提议（proposal）都在被提出的时候加上了zxid。实现中zxid是一个64位的数字，它高32位是epoch用来标识leader关系是否改变，每次一个leader被选出来，它都会有一个新的epoch，标识当前属于那个leader的统治时期。低32位用于递增计数。 本身的数据组织以文件形式。 作用1.单独zk集群元数据的可靠性和一致性保证，元数据保存在zk所有副本中（少量完全可以放在内存中数据）路由，选择数据库，调度程序2.单独zk集群，锁，防护令牌，获取锁或者zxid 3.变更通知，每个变更都会发送到所有节点watch机制4.用于检测，服务发现session:每个ZooKeeper客户端的配置中都包括集合体中服务器的列表。在启动时，客户端会尝试连接到列表中的一台服务器。如果连接失败，它会尝试连接另一台服务器，以此类推，直到成功与一台服务器建立连接或因为所有ZooKeeper服务器都不可用而失败。只要一个会话空闲超过一定时间，都可以通过客户端发送ping请求（也称为心跳）保持会话不过期。ping请求由ZooKeeper的客户端库自动发送，因此在我们的代码中不需要考虑如何维护会话。这个时间长度的设置应当足够低，以便能档检测出服务器故障（由读超时体现），并且能够在会话超时的时间段内重新莲接到另外一台服务器。 zookeeper数据同步过程：zab protocol Leader election leader选举过程，electionEpoch自增，在选举的时候lastProcessedZxid越大，越有可能成为leaderDiscovery： 第一：leader收集follower的lastProcessedZxid，这个主要用来通过和leader的lastProcessedZxid对比来确认follower需要同步的数据范围 第二：选举出一个新的peerEpoch，主要用于防止旧的leader来进行提交操作（旧leader向follower发送命令的时候，follower发现zxid所在的peerEpoch比现在的小，则直接拒绝，防止出现不一致性）Synchronization： follower中的事务日志和leader保持一致的过程，就是依据follower和leader之间的lastProcessedZxid进行，follower多的话则删除掉多余部分，follower少的话则补充，一旦对应不上则follower删除掉对不上的zxid及其之后的部分然后再从leader同步该部分之后的数据Broadcast 正常处理客户端请求的过程。leader针对客户端的事务请求，然后提出一个议案，发给所有的follower，一旦过半的follower回复OK的话，leader就可以将该议案进行提交了，向所有follower发送提交该议案的请求，leader同时返回OK响应给客户端实际上zookeeper中算法三阶段：FSE=>Recovery=>Broadcast(广播和上面的一致) fast leader election基于fast paxos。发送给所有的节点。没有随机leader参与收集。 LOOKING：进入leader选举状态FOLLOWING：leader选举结束，进入follower状态LEADING：leader选举结束，进入leader状态OBSERVING：处于观察者状态1.serverA首先将electionEpoch自增，然后为自己投票2 serverB接收到上述通知，然后进行投票PK如果serverB收到的通知中的electionEpoch比自己的大，则serverB更新自己的electionEpoch为serverA的electionEpoch如果该serverB收到的通知中的electionEpoch比自己的小，则serverB向serverA发送一个通知，将serverB自己的投票以及electionEpoch发送给serverA，serverA收到后就会更新自己的electionEpoch在electionEpoch达成一致后，就开始进行投票之间的pk，优先比较proposedEpoch，然后优先比较proposedZxid，最后优先比较proposedLeaderpk完毕后，如果本机器投票被pk掉，则更新投票信息为对方投票信息，同时重新发送该投票信息给所有的server。如果本机器投票没有被pk掉，如果是looking，过半更改状态,如果FOLLOWING/LEADING说明落后，加速收敛Recovery略：https://my.oschina.net/pingpa...follower读写过程图： ectd

由于郁白之前写的关于Multi-Paxos 的文章流传非常广, 具体地址: http://oceanbase.org.cn/?p=111 原文提出了一个叫"幽灵复现" 的问题, 认为这个是一个很诡异的问题, 后续和很多人交流关于一致性协议的时候, 也经常会提起这个问题, 但是其实这个问题我认为就是常见的"第三态"问题加了一层包装而已.幽灵复现问题来自郁白的博客:使用Paxos协议处理日志的备份与恢复，可以保证确认形成多数派的日志不丢失，但是无法避免一种被称为“幽灵复现”的现象，如下图所示： LeaderABC第一轮A1-101-51-5第二轮B宕机1-6,201-6,20第三轮A1-201-201-20第一轮中A被选为Leader，写下了1-10号日志，其中1-5号日志形成了多数派，并且已给客户端应答，而对于6-10号日志，客户端超时未能得到应答。第二轮，A宕机，B被选为Leader，由于B和C的最大的logID都是5，因此B不会去重确认6-10号日志，而是从6开始写新的日志，此时如果客户端来查询的话，是查询不到6-10号日志内容的，此后第二轮又写入了6-20号日志，但是只有6号和20号日志在多数派上持久化成功。第三轮，A又被选为Leader，从多数派中可以得到最大logID为20，因此要将7-20号日志执行重确认，其中就包括了A上的7-10号日志，之后客户端再来查询的话，会发现上次查询不到的7-10号日志又像幽灵一样重新出现了。对于将Paxos协议应用在数据库日志同步场景的情况，幽灵复现问题是不可接受，一个简单的例子就是转账场景，用户转账时如果返回结果超时，那么往往会查询一下转账是否成功，来决定是否重试一下。如果第一次查询转账结果时，发现未生效而重试，而转账事务日志作为幽灵复现日志重新出现的话，就造成了用户重复转账。为了处理“幽灵复现”问题，我们在每条日志的内容中保存一个generateID，leader在生成这条日志时以当前的leader ProposalID作为generateID。按logID顺序回放日志时，因为leader在开始服务之前一定会写一条StartWorking日志，所以如果出现generateID相对前一条日志变小的情况，说明这是一条“幽灵复现”日志（它的generateID会小于StartWorking日志），要忽略掉这条日志。第三态问题第三态问题也是我们之前经常讲的问题, 其实在网络系统里面, 对于一个请求都有三种返回结果成功失败超时未知前面两种状态由于服务端都有明确的返回结果, 所以非常好处理, 但是如果是第三种状态的返回, 由于是超时状态, 所以服务端可能对于这个命令是请求是执行成功, 也有可能是执行失败的, 所以如果这个请求是一个写入操作, 那么下一次的读取请求可能读到这个结果, 也可能读到的结果是空的就像在 raft phd 那个论文里面说的, 这个问题其实是和 raft/multi-paxos 协议无关的内容, 只要在分布式系统里面都会存在这个问题, 所以大部分的解决方法是两个对于每一个请求都加上一个唯一的序列号的标识, 然后server的状态机会记录之前已经执行过序列号. 当一个请求超时的时候, 默认的client 的逻辑会重试这个逻辑, 在收到重试的逻辑以后, 由于server 的状态机记录了之前已经执行过的序列号信息, 因此不会再次执行这条指令, 而是直接返回给客户端由于上述方法需要在server 端维护序列号的信息, 这个序列号是随着请求的多少递增的, 大小可想而知(当然也可以做一些只维护最近的多少条序列号个数的优化). 常见的工程实现是让client 的操作是幂等的, 直接重试即可, 比如floyd 里面的具体实现那么对应于raft 中的第三态问题是, 当最后log Index 为4 的请求超时的时候, 状态机中出现的两种场景都是可能的所以下一次读取的时候有可能读到log Index 4 的内容, 也有可能读不到, 所以如果在发生了超时请求以后, 默认client 需要进行重试直到这个操作成功以后, 接下来才可以保证读到的写入结果. 这也是工程实现里面常见的做法对应于幽灵问题, 其实是由于6-10 的操作产生了超时操作, 由于产生了超时操作以后, client 并没有对这些操作进行确认, 而是接下来去读取这个结果, 那么读取不到这个里面的内容, 由于后续的写入和切主操作有重新能够读取到这个6-10 的内容了, 造成了幽灵复现, 导致这个问题的原因还是因为没有进行对超时操作的重确认.回到幽灵复现问题那么Raft 有没有可能出现这个幽灵复现问题呢?其实在早期Raft 没有引入新的Leader 需要写入一个包含自己的空的Entry 的时候也一样会出现这个问题Log Index 4,5 客户端超时未给用户返回, 存在以下日志场景然后 (a) 节点宕机, 这个时候client 是查询不到 Log entry 4, 5 里面的内容在(b)或(c) 成为Leader 期间, 没有写入任何内容, 然后(a) 又恢复, 并且又重新选主, 那么就存在一下日志, 这个时候client 再查询就查询到Log entry 4,5 里面的内容了那么Raft 里面加入了新Leader 必须写入一条当前Term 的Log Entry 就可以解决这个问题, 其实和之前郁白提到的写入一个StartWorking 日志是一样的做法, 由于(b), (c) 有一个Term 3的日志, 就算(a) 节点恢复过来, 也无法成了Leader, 那么后续的读也就不会读到Log Entry 4, 5 里面的内容那么这个问题的本质是什么呢?其实这个问题的本质是对于一致性协议在recovery 的不同做法产生的. 关于一致性协议在不同阶段的做法可以看这个文章 http://baotiao.github.io/2018/01/02/consensus-recovery/也就是说对于一个在多副本里面未达成一致的Log entry, 在Recovery 需要如何处理这一部分未达成一致的log entry.对于这一部分log entry 其实可以是提交, 也可以是不提交, 因为会产生这样的log entry, 一定是之前对于这个client 的请求超时返回了.常见的Multi-Paxos 在对这一部分日志进行重确认的时候, 默认是将这部分的内容提交的, 也就是通过重确认的过程默认去提交这些内容而Raft 的实现是默认对这部分的内容是不提交的, 也就是增加了一个当前Term 的空的Entry, 来把之前leader 多余的log 默认不提交了, 幽灵复现里面其实也是通过增加一个空的当前Leader 的Proposal ID 来把之前的Log Entry 默认不提交所以这个问题只是对于返回超时, 未达成一致的Log entry 的不同的处理方法造成的.在默认去提交这些日志的场景, 在写入超时以后读取不到内容, 但是通过recovery 以后又能够读取到这个内容, 就产生了幽灵复现的问题但是其实之所以会出现幽灵复现的问题是因为在有了一个超时的第三态的请求以后, 在没有处理好这个第三态请求之前, 出现成功和失败都是有可能的.所以本质是在Multi-Paxos 实现中, 在recovery 阶段, 将未达成一致的Log entry 提交造成的幽灵复现的问题, 本质是没有处理好这个第三态的请求。一站式开发者服务，海量学习资源0元起！阿里热门开源项目、机器学习干货、开发者课程/工具、小微项目、移动研发等海量资源；更有开发者福利Kindle、技术图书幸运抽奖，100%中–》https://www.aliyun.com/acts/product-section-2019/developer?utm_content=g_1000047140本文作者：陈宗志阅读原文本文为云栖社区原创内容，未经允许不得转载。 ...

Raft作为Paxos的简化版本，在工程领域有着更加广泛的应用。本文转载的几篇文章对Raft的工作原理、实现方式进行了详细的介绍。分布式系统的Raft算法总结：目前几乎所有语言都已经有支持Raft算法的库包，具体可参考：raftconsensus.github.io英文动画演示RaftCAP原理和BASE思想分布式Paxos算法分布式事务 => 分布式系统事务一致性解决方案

作者：屈鹏本文为 TiKV 源码解析系列的第二篇，按照计划首先将为大家介绍 TiKV 依赖的周边库 raft-rs 。raft-rs 是 Raft 算法的 Rust 语言实现。Raft 是分布式领域中应用非常广泛的一种共识算法，相比于此类算法的鼻祖 Paxos，具有更简单、更容易理解和实现的特点。分布式系统的共识算法会将数据的写入复制到多个副本，从而在网络隔离或节点失败的时候仍然提供可用性。具体到 Raft 算法中，发起一个读写请求称为一次 proposal。本文将以 raft-rs 的公共 API 作为切入点，介绍一般 proposal 过程的实现原理，让用户可以深刻理解并掌握 raft-rs API 的使用， 以便用户开发自己的分布式应用，或者优化、定制 TiKV。文中引用的代码片段的完整实现可以参见 raft-rs 仓库中的 source-code 分支。Public API 简述仓库中的 examples/five_mem_node/main.rs 文件是一个包含了主要 API 用法的简单示例。它创建了一个 5 节点的 Raft 系统，并进行了 100 个 proposal 的请求和提交。经过进一步精简之后，主要的类型封装和运行逻辑如下：struct Node { // 持有一个 RawNode 实例 raft_group: Option<RawNode<MemStorage>>, // 接收其他节点发来的 Raft 消息 my_mailbox: Receiver<Message>, // 发送 Raft 消息给其他节点 mailboxes: HashMap<u64, Sender<Message>>,}let mut t = Instant::now();// 在 Node 实例上运行一个循环，周期性地处理 Raft 消息、tick 和 Ready。loop { thread::sleep(Duration::from_millis(10)); while let Ok(msg) = node.my_mailbox.try_recv() { // 处理收到的 Raft 消息 node.step(msg); } let raft_group = match node.raft_group.as_mut().unwrap(); if t.elapsed() >= Duration::from_millis(100) { raft_group.tick(); t = Instant::now(); } // 处理 Raft 产生的 Ready，并将处理进度更新回 Raft 中 let mut ready = raft_group.ready(); persist(ready.entries()); // 处理刚刚收到的 Raft Log send_all(ready.messages); // 将 Raft 产生的消息发送给其他节点 handle_committed_entries(ready.committed_entries.take()); raft_group.advance(ready);}这段代码中值得注意的地方是：RawNode 是 raft-rs 库与应用交互的主要界面。要在自己的应用中使用 raft-rs，首先就需要持有一个 RawNode 实例，正如 Node 结构体所做的那样。RawNode 的范型参数是一个满足 Storage 约束的类型，可以认为是一个存储了 Raft Log 的存储引擎，示例中使用的是 MemStorage。在收到 Raft 消息之后，调用 RawNode::step 方法来处理这条消息。每隔一段时间（称为一个 tick），调用 RawNode::tick 方法使 Raft 的逻辑时钟前进一步。使用 RawNode::ready 接口从 Raft 中获取收到的最新日志（Ready::entries），已经提交的日志（Ready::committed_entries），以及需要发送给其他节点的消息等内容。在确保一个 Ready 中的所有进度被正确处理完成之后，调用 RawNode::advance 接口。接下来的几节将展开详细描述。Storage traitRaft 算法中的日志复制部分抽象了一个可以不断追加写入新日志的持久化数组，这一数组在 raft-rs 中即对应 Storage。使用一个表格可以直观地展示这个 trait 的各个方法分别可以从这个持久化数组中获取哪些信息：方法描述initial_state获取这个 Raft 节点的初始化信息，比如 Raft group 中都有哪些成员等。这个方法在应用程序启动时会用到。entries给定一个范围，获取这个范围内持久化之后的 Raft Log。term给定一个日志的下标，查看这个位置的日志的 term。first_index由于数组中陈旧的日志会被清理掉，这个方法会返回数组中未被清理掉的最小的位置。last_index返回数组中最后一条日志的位置。snapshot返回一个 Snapshot，以便发送给日志落后过多的 Follower。值得注意的是，这个 Storage 中并不包括持久化 Raft Log，也不会将 Raft Log 应用到应用程序自己的状态机的接口。这些内容需要应用程序自行处理。RawNode::step 接口这个接口处理从该 Raft group 中其他节点收到的消息。比如，当 Follower 收到 Leader 发来的日志时，需要把日志存储起来并回复相应的 ACK；或者当节点收到 term 更高的选举消息时，应该进入选举状态并回复自己的投票。这个接口和它调用的子函数的详细逻辑几乎涵盖了 Raft 协议的全部内容，代码较多，因此这里仅阐述在 Leader 上发生的日志复制过程。当应用程序希望向 Raft 系统提交一个写入时，需要在 Leader 上调用 RawNode::propose 方法，后者就会调用 RawNode::step，而参数是一个类型为 MessageType::MsgPropose 的消息；应用程序要写入的内容被封装到了这个消息中。对于这一消息类型，后续会调用 Raft::step_leader 函数，将这个消息作为一个 Raft Log 暂存起来，同时广播到 Follower 的信箱中。到这一步，propose 的过程就可以返回了，注意，此时这个 Raft Log 并没有持久化，同时广播给 Follower 的 MsgAppend 消息也并未真正发出去。应用程序需要设法将这个写入挂起，等到从 Raft 中获知这个写入已经被集群中的过半成员确认之后，再向这个写入的发起者返回写入成功的响应。那么， 如何能够让 Raft 把消息真正发出去，并接收 Follower 的确认呢？RawNode::ready 和 RawNode::advance 接口这个接口返回一个 Ready 结构体：pub struct Ready { pub committed_entries: Option<Vec<Entry>>, pub messages: Vec<Message>, // some other fields…}impl Ready { pub fn entries(&self) -> &[Entry] { &self.entries } // some other methods…}一些暂时无关的字段和方法已经略去，在 propose 过程中主要用到的方法和字段分别是：方法/字段作用entries（方法）取出上一步发到 Raft 中，但尚未持久化的 Raft Log。committed_entries取出已经持久化，并经过集群确认的 Raft Log。messages取出 Raft 产生的消息，以便真正发给其他节点。对照 examples/five_mem_node/main.rs 中的示例，可以知道应用程序在 propose 一个消息之后，应该调用 RawNode::ready 并在返回的 Ready 上继续进行处理：包括持久化 Raft Log，将 Raft 消息发送到网络上等。而在 Follower 上，也不断运行着示例代码中与 Leader 相同的循环：接收 Raft 消息，从 Ready 中收集回复并发回给 Leader……对于 propose 过程而言，当 Leader 收到了足够的确认这一 Raft Log 的回复，便能够认为这一 Raft Log 已经被确认了，这一逻辑体现在 Raft::handle_append_response 之后的 Raft::maybe_commit 方法中。在下一次这个 Raft 节点调用 RawNode::ready 时，便可以取出这部分被确认的消息，并应用到状态机中了。在将一个 Ready 结构体中的内容处理完成之后，应用程序即可调用这个方法更新 Raft 中的一些进度，包括 last index、commit index 和 apply index 等。RawNode::tick 接口这是本文最后要介绍的一个接口，它的作用是驱动 Raft 内部的逻辑时钟前进，并对超时进行处理。比如对于 Follower 而言，如果它在 tick 的时候发现 Leader 已经失联很久了，便会发起一次选举；而 Leader 为了避免自己被取代，也会在一个更短的超时之后给 Follower 发送心跳。值得注意的是，tick 也是会产生 Raft 消息的，为了使这部分 Raft 消息能够及时发送出去，在应用程序的每一轮循环中一般应该先处理 tick，然后处理 Ready，正如示例程序中所做的那样。总结最后用一张图展示在 Leader 上是通过哪些 API 进行 propose 的：本期关于 raft-rs 的源码解析就到此结束了，我们非常鼓励大家在自己的分布式应用中尝试 raft-rs 这个库，同时提出宝贵的意见和建议。后续关于 raft-rs 我们还会深入介绍 Configuration Change 和 Snapshot 的实现与优化等内容，展示更深入的设计原理、更详细的优化细节，方便大家分析定位 raft-rs 和 TiKV 使用中的潜在问题。 ...

前言本文旨在讲述如何使用 Java 语言实现基于 Raft 算法的，分布式的，KV 结构的存储项目。该项目的背景是为了深入理解 Raft 算法，从而深刻理解分布式环境下数据强一致性该如何实现；该项目的目标是：在复杂的分布式环境中，多个存储节点能够保证数据强一致性。项目地址：https://github.com/stateIs0/l…欢迎 star ：）什么是 Java 版 Raft 分布式 KV 存储Raft 算法大部分人都已经了解，也有很多实现，从 GitHub 上来看，似乎 Golang 语言实现的较多，比较有名的，例如 etcd。而 Java 版本的，在生产环境大规模使用的实现则较少；同时，他们的设计目标大部分都是命名服务，即服务注册发现，也就是说，他们通常都是基于 AP 实现，就像 DNS，DNS 是一个命名服务，同时也不是一个强一致性的服务。比较不同的是 Zookeeper，ZK 常被大家用来做命名服务，但他更多的是一个分布式服务协调者。而上面的这些都不是存储服务，虽然也都可以做一些存储工作。甚至像 kafka，可以利用 ZK 实现分布式存储。回到我们这边。此次我们语言部分使用 Java，RPC 网络通信框架使用的是蚂蚁金服 SOFA-Bolt，底层 KV 存储使用的是 RocksDB，其中核心的 Raft 则由我们自己实现（如果不自己实现，那这个项目没有意义）。 注意，该项目将舍弃一部分性能和可用性，以追求尽可能的强一致性。为什么要费尽心力重复造轮子小时候，我们阅读关于高可用的文章时，最后都会提到一个问题：服务挂了怎么办？通常有 2 种回答：如果是无状态服务，那么毫不影响使用。如果是有状态服务，可以将状态保存到一个别的地方，例如 Redis。如果 Redis 挂了怎么办？那就放到 ZK。很多中间件，都会使用 ZK 来保证状态一致，例如 codis，kafka。因为使用 ZK 能够帮我们节省大量的时间。但有的时候，中间件的用户觉得引入第三方中间件很麻烦，那么中间件开发者会尝试自己实现一致性，例如 Redis Cluster， TiDB 等。而通常自己实现，都会使用 Raft 算法，那有人问，为什么不使用"更牛逼的" paxos 算法？对不起，这个有点难，至少目前开源的、生产环境大规模使用的 paxos 算法实现还没有出现，只听过 Google 或者 alibaba 在其内部实现过，具体是什么样子的，这里我们就不讨论了。回到我们的话题，为什么重复造轮子？从 3 个方面来回答：有的时候 ZK 和 etcd 并不能解决我们的问题，或者像上面说的，引入其他的中间件部署起来太麻烦也太重。完全处于好奇，好奇为什么 Raft 可以保证一致性（这通常可以通过汗牛充栋的文章来得到解答）？但是到底该怎么实现？分布式开发的要求，作为开发分布式系统的程序员，如果能够更深刻的理解分布式系统的核心算法，那么对如何合理设计一个分布式系统将大有益处。好，有了以上 3 个原因，我们就有足够的动力来造轮子了，接下来就是如何造的问题了。编写前的 Raft 理论基础任何实践都是理论先行。如果你对 Raft 理论已经非常熟悉，那么可以跳过此节，直接看实现的步骤。Raft 为了算法的可理解性，将算法分成了 4 个部分。leader 选举日志复制成员变更日志压缩同 zk 一样，leader 都是必须的，所有的写操作都是由 leader 发起，从而保证数据流向足够简单。而 leader 的选举则通过比较每个节点的逻辑时间（term）大小，以及日志下标（index）的大小。刚刚说 leader 选举涉及日志下标，那么就要讲日志复制。日志复制可以说是 Raft 核心的核心，说简单点，Raft 就是为了保证多节点之间日志的一致。当日志一致，我们可以认为整个系统的状态是一致的。这个日志你可以理解成 mysql 的 binlog。Raft 通过各种补丁，保证了日志复制的正确性。Raft leader 节点会将客户端的请求都封装成日志，发送到各个 follower 中，如果集群中超过一半的 follower 回复成功，那么这个日志就可以被提交（commit），这个 commit 可以理解为 ACID 的 D ，即持久化。当日志被持久化到磁盘，后面的事情就好办了。而第三点则是为了节点的扩展性。第四点是为了性能。相比较 leader 选举和 日志复制，不是那么的重要，可以说，如果没有成员变更和日志压缩，也可以搞出一个可用的 Raft 分布式系统，但没有 leader 选举和日志复制，是万万不能的。因此，本文和本项目将重点放在 leader 选举和日志复制。以上，就简单说明了 Raft 的算法，关于 Raft 算法更多的文章，请参考本人博客中的其他文章（包含官方各个版本论文和 PPT & 动画 & 其他博客文章），博客地址：thinkinjava.cn实现的步骤实现目标：基于 Raft 论文实现 Raft 核心功能，即 Leader 选举 & 日志复制。Raft 核心组件包括：一致性模块，RPC 通信，日志模块，状态机。技术选型：一致性模块，是 Raft 算法的核心实现，通过一致性模块，保证 Raft 集群节点数据的一致性。这里我们需要自己根据论文描述去实现。RPC 通信，可以使用 HTTP 短连接，也可以直接使用 TCP 长连接，考虑到集群各个节点频繁通信，同时节点通常都在一个局域网内，因此我们选用 TCP 长连接。而 Java 社区长连接框架首选 Netty，这里我们选用蚂蚁金服网络通信框架 SOFA-Bolt（基于 Netty），便于快速开发。日志模块，Raft 算法中，日志实现是基础，考虑到时间因素，我们选用 RocksDB 作为日志存储。状态机，可以是任何实现，其实质就是将日志中的内容进行处理。可以理解为 Mysql binlog 中的具体数据。由于我们是要实现一个 KV 存储，那么可以直接使用日志模块的 RocksDB 组件。以上。我们可以看到，得益于开源世界，我们开发一个 Raft 存储，只需要编写一个“一致性模块”就行了，其他模块都有现成的轮子可以使用，真是美滋滋。接口设计：上面我们说了 Raft 的几个核心功能，事实上，就可以理解为接口。所以我们定义以下几个接口：Consensus， 一致性模块接口LogModule，日志模块接口StateMachine， 状态机接口RpcServer & RpcClient， RPC 接口Node，同时，为了聚合上面的几个接口，我们需要定义一个 Node 接口，即节点，Raft 抽象的机器节点。LifeCycle， 最后，我们需要管理以上组件的生命周期，因此需要一个 LifeCycle 接口。接下来，我们需要详细定义核心接口 Consensus。我们根据论文定义了 2 个核心接口： /** * 请求投票 RPC * * 接收者实现： * * 如果term < currentTerm返回 false （5.2 节） * 如果 votedFor 为空或者就是 candidateId，并且候选人的日志至少和自己一样新，那么就投票给他（5.2 节，5.4 节） / RvoteResult requestVote(RvoteParam param); /* * 附加日志(多个日志,为了提高效率) RPC * * 接收者实现： * * 如果 term < currentTerm 就返回 false （5.1 节） * 如果日志在 prevLogIndex 位置处的日志条目的任期号和 prevLogTerm 不匹配，则返回 false （5.3 节） * 如果已经存在的日志条目和新的产生冲突（索引值相同但是任期号不同），删除这一条和之后所有的 （5.3 节） * 附加任何在已有的日志中不存在的条目 * 如果 leaderCommit > commitIndex，令 commitIndex 等于 leaderCommit 和 新日志条目索引值中较小的一个 / AentryResult appendEntries(AentryParam param);请求投票 & 附加日志。也就是我们的 Raft 节点的核心功能，leader 选举和 日志复制。实现这两个接口是 Raft 的关键所在。然后再看 LogModule 接口，这个自由发挥，考虑日志的特点，我定义了以下几个接口：void write(LogEntry logEntry);LogEntry read(Long index);void removeOnStartIndex(Long startIndex);LogEntry getLast();Long getLastIndex();分别是写，读，删，最后是两个关于 Last 的接口，在 Raft 中，Last 是一个非常关键的东西，因此我这里单独定义了 2个方法，虽然看起来不是很好看 ：）状态机接口，在 Raft 论文中，将数据保存到状态机，作者称之为应用，那么我们也这么命名，说白了，就是将已成功提交的日志应用到状态机中： /* * 将数据应用到状态机. * * 原则上,只需这一个方法(apply). 其他的方法是为了更方便的使用状态机. * @param logEntry 日志中的数据. / void apply(LogEntry logEntry); LogEntry get(String key); String getString(String key); void setString(String key, String value); void delString(String… key); 第一个 apply 方法，就是 Raft 论文常常提及的方法，即将日志应用到状态机中，后面的几个方法，都是我为了方便获取数据设计的，可以不用在意，甚至于，这几个方法不存在也不影响 Raft 的实现，但影响 KV 存储的实现，试想：一个系统只有保存功能，没有获取功能，要你何用？。RpcClient 和 RPCServer 没什么好讲的，其实就是 send 和 receive。然后是 Node 接口，Node 接口也是 Raft 没有定义的，我们依靠自己的理解定义了几个接口： /* * 设置配置文件. * * @param config / void setConfig(NodeConfig config); /* * 处理请求投票 RPC. * * @param param * @return / RvoteResult handlerRequestVote(RvoteParam param); /* * 处理附加日志请求. * * @param param * @return / AentryResult handlerAppendEntries(AentryParam param); /* * 处理客户端请求. * * @param request * @return / ClientKVAck handlerClientRequest(ClientKVReq request); /* * 转发给 leader 节点. * @param request * @return */ ClientKVAck redirect(ClientKVReq request);首先，一个 Node 肯定需要配置文件，所以有一个 setConfig 接口，然后，肯定需要处理“请求投票”和“附加日志”，同时，还需要接收用户，也就是客户端的请求（不然数据从哪来？），所以有 handlerClientRequest 接口，最后，考虑到灵活性，我们让每个节点都可以接收客户端的请求，但 follower 节点并不能处理请求，所以需要重定向到 leader 节点，因此，我们需要一个重定向接口。最后是生命周期接口，这里我们简单定义了 2 个，有需要的话，再另外加上组合接口： void init() throws Throwable; void destroy() throws Throwable;好，基本的接口定义完了，后面就是实现了。实现才是关键。Leader 选举的实现选举，其实就是一个定时器，根据 Raft 论文描述，如果超时了就需要重新选举，我们使用 Java 的定时任务线程池进行实现，实现之前，需要确定几个点：选举者必须不是 leader。必须超时了才能选举，具体超时时间根据你的设计而定,注意，每个节点的超时时间不能相同，应当使用随机算法错开（Raft 关键实现），避免无谓的死锁。选举者优先选举自己,将自己变成 candidate。选举的第一步就是把自己的 term 加一。然后像其他节点发送请求投票 RPC，请求参数参照论文，包括自身的 term，自身的 lastIndex，以及日志的 lastTerm。同时，请求投票 RPC 应该是并行请求的。等待投票结果应该有超时控制，如果超时了，就不等待了。最后，如果有超过半数的响应为 success，那么就需要立即变成 leader ，并发送心跳阻止其他选举。如果失败了，就需要重新选举。注意，这个期间，如果有其他节点发送心跳，也需要立刻变成 follower，否则，将死循环。具体代码，可参见 https://github.com/stateIs0/l…上面说的，其实是 Leader 选举中，请求者的实现，那么接收者如何实现呢？接收者在收到“请求投票” RPC 后，需要做以下事情：注意，选举操作应该是串行的，因为涉及到状态修改，并发操作将导致数据错乱。也就是说，如果抢锁失败，应当立即返回错误。首先判断对方的 term 是否小于自己，如果小于自己，直接返回失败。如果当前节点没有投票给任何人，或者投的正好是对方，那么就可以比较日志的大小，反之，返回失败。如果对方日志没有自己大，返回失败。反之，投票给对方，并变成 follower。变成 follower 的同时，异步的选举任务在最后从 condidate 变成 leader 之前，会判断是否是 follower，如果是 follower，就放弃成为 leader。这是一个兜底的措施。具体代码参见 https://github.com/stateIs0/l…到这里，基本就能够实现 Raft Leader 选举的逻辑。注意，我们上面涉及到的 LastIndex 等参数，还没有实现，但不影响我们编写伪代码，毕竟日志复制比 leader 选举要复杂的多，我们的原则是从易到难。：）日志复制的实现日志复制是 Raft 实现一致性的核心。日志复制有 2 种形式，1种是心跳，一种是真正的日志，心跳的日志内容是空的，其他部分基本相同，也就是说，接收方在收到日志时，如果发现是空的，那么他就是心跳。心跳既然是心跳，肯定就是个定时任务，和选举一样。在我们的实现中，我们每 5 秒发送一次心跳。注意点：首先自己必须是 leader 才能发送心跳。必须满足 5 秒的时间间隔。并发的向其他 follower 节点发送心跳。心跳参数包括自身的 ID，自身的 term，以便让对方检查 term，防止网络分区导致的脑裂。如果任意 follower 的返回值的 term 大于自身，说明自己分区了，那么需要变成 follower，并更新自己的 term。然后重新发起选举。具体代码查看：https://github.com/stateIs0/l…然后是心跳接收者的实现，这个就比较简单了，接收者需要做几件事情：无论成功失败首先设置返回值，也就是将自己的 term 返回给 leader。判断对方的 term 是否大于自身，如果大于自身，变成 follower，防止异步的选举任务误操作。同时更新选举时间和心跳时间。如果对方 term 小于自身，返回失败。不更新选举时间和心跳时间。以便触发选举。具体代码参见：https://github.com/stateIs0/l…说完了心跳，再说说真正的日志附加。简单来说，当用户向 Leader 发送一个 KV 数据，那么 Leader 需要将 KV数据封装成日志，并行的发送到其他的 follower 节点，只要在指定的超时时间内，有过半几点返回成功，那么久提交（持久化）这条日志，返回客户端成功，否者返回失败。因此，Leader 节点会有一个 ClientKVAck handlerClientRequest(ClientKVReq request) 接口，用于接收用户的 KV 数据，同时，会并行向其他节点复制数据，具体步骤如下：每个节点都可能会接收到客户端的请求，但只有 leader 能处理，所以如果自身不是 leader，则需要转发给 leader。然后将用户的 KV 数据封装成日志结构，包括 term，index，command，预提交到本地。并行的向其他节点发送数据，也就是日志复制。如果在指定的时间内，过半节点返回成功，那么就提交这条日志。最后，更新自己的 commitIndex，lastApplied 等信息。注意，复制不仅仅是简单的将这条日志发送到其他节点，这可能比我们想象的复杂，为了保证复杂网络环境下的一致性，Raft 保存了每个节点的成功复制过的日志的 index，即 nextIndex ，因此，如果对方之前一段时间宕机了，那么，从宕机那一刻开始，到当前这段时间的所有日志，都要发送给对方。甚至于，如果对方觉得你发送的日志还是太大，那么就要递减的减小 nextIndex，复制更多的日志给对方。注意：这里是 Raft 实现分布式一致性的关键所在。具体代码参见：https://github.com/stateIs0/l…再来看看日志接收者的实现步骤：和心跳一样，要先检查对方 term，如果 term 都不对，那么就没什么好说的了。如果日志不匹配，那么返回 leader，告诉他，减小 nextIndex 重试。如果本地存在的日志和 leader 的日志冲突了，以 leader 的为准，删除自身的。最后，将日志应用到状态机，更新本地的 commitIndex，返回 leader 成功。具体代码参见：https://github.com/stateIs0/l…到这里，日志复制的部分就讲完了。注意，实现日志复制的前提是，必须有一个正确的日志存储系统，即我们的 RocksDB，我们在 RocksDB 的基础上，使用一种机制，维护了 每个节点 的LastIndex，无论何时何地，都能够得到正确的 LastIndex，这是实现日志复制不可获取的一部分。验证“Leader 选举”和“日志复制”写完了程序，如何验证是否正确呢？当然是写验证程序。我们首先验证 “Leader 选举”。其实这个比较好测试。在 idea 中配置 5 个 application 启动项,配置 main 类为 RaftNodeBootStrap 类, 加入 -DserverPort=8775 -DserverPort=8776 -DserverPort=8777 -DserverPort=8778 -DserverPort=8779 系统配置, 表示分布式环境下的 5 个机器节点.依次启动 5 个 RaftNodeBootStrap 节点, 端口分别是 8775，8776， 8777, 8778, 8779.观察控制台, 约 6 秒后, 会发生选举事件,此时,会产生一个 leader. 而 leader 会立刻发送心跳维持自己的地位.如果leader 的端口是 8775, 使用 idea 关闭 8775 端口，模拟节点挂掉, 大约 15 秒后, 会重新开始选举, 并且会在剩余的 4 个节点中,产生一个新的 leader. 并开始发送心跳日志。然后验证 日志复制，分为 2 种情况：正常状态下在 idea 中配置 5 个 application 启动项,配置 main 类为 RaftNodeBootStrap 类, 加入 -DserverPort=8775 -DserverPort=8776 -DserverPort=8777 -DserverPort=8778 -DserverPort=8779依次启动 5 个 RaftNodeBootStrap 节点, 端口分别是 8775，8776， 8777, 8778, 8779.使用客户端写入 kv 数据.杀掉所有节点, 使用 junit test 读取每个 rocksDB 的值, 验证每个节点的数据是否一致.非正常状态下在 idea 中配置 5 个 application 启动项,配置 main 类为 RaftNodeBootStrap 类, 加入 -DserverPort=8775 -DserverPort=8776 -DserverPort=8777 -DserverPort=8778 -DserverPort=8779依次启动 5 个 RaftNodeBootStrap 节点, 端口分别是 8775，8776， 8777, 8778, 8779.使用客户端写入 kv 数据.杀掉 leader （假设是 8775）.再次写入数据.重启 8775.关闭所有节点, 读取 RocksDB 验证数据一致性.Summary本文并没有贴很多代码，如果要贴代码的话，阅读体验将不会很好，并且代码也不能说明什么，如果想看具体实现，可以到 github 上看看，顺便给个 star ：）该项目 Java 代码约 2500 行，核心代码估计也就 1000 多行。你甚至可以说，这是个玩具代码，但我相信毕玄大师所说，玩具代码经过优化后，也是可以变成可在商业系统中真正健壮运行的代码（http://hellojava.info/?p=508） ：）回到我们的初衷，我们并不奢望这段代码能够运行在生产环境中，就像我的另一个项目 Lu-RPC 一样。但，经历了一次编写可正确运行的玩具代码的经历，下次再次编写工程化的代码，应该会更加容易些。这点我深有体会。可以稍微展开讲一下，在写完 Lu-RPC 项目后，我就接到了开发生产环境运行的限流熔断框架任务，此时，开发 Lu-RPC 的经历让我在开发该框架时，更加的从容和自如：）再回到 Raft 上面来，虽然上面的测试用例跑过了，程序也经过了我反反复复的测试，但不代表这个程序就是 100% 正确的，特别是在复杂的分布式环境下。如果你对 Raft 有兴趣，欢迎一起交流沟通 ：）项目地址：https://github.com/stateIs0/l… ...