Raft of distributed consistency protocol

Recently RocketMQ When , come to know v4.5.0 after ,broker Adopt the following raft Protocol replication group to achieve data consistency . Tiger body one earthquake ,raft The agreement has become familiar and strange in my mind now …

No big problem , Brush it again raft.

Post the official website first ：The Raft Consensus Algorithm

Then post an animated demonstration ：Raft: Understandable Distributed Consensus

ps： The moving picture inside is very interesting

brief introduction

ps: From wikipedia

Raft Is an alternative to Paxos Of Consensus Algorithm . Compared with Paxos,Raft The goal of is to provide a clearer logical division of labor so that the algorithm itself can be better understood , At the same time, it is more secure , And can provide some additional features .[1][2]:1Raft Can be in Computer cluster Deployment between Finite state machine Provide a general method , And ensure that any node in the cluster is consistent in some state transition .Raft There are many open source implementations of the algorithm , stay Go、C++、Java as well as Scala There are complete code implementations in .Raft The name comes from "Reliable, Replicated, Redundant, And Fault-Tolerant"（“ reliable 、 Replicable 、 Redundant 、 Fault tolerance ”） An acronym for .[3]

All nodes in the cluster trust the elected leaders , therefore Raft It's not a kind of byzantine fault tolerance Algorithm .[2]

Raft Use Elect leaders The way to do consensus algorithm . A typical Raft cluster Generally speaking, there are 5 Servers , This can cope with two failures .

In a Raft cluster in , The server has three identities ：

1. Leader （leader）
2. follower （follower）
3. The candidate （candidate）

leader There will only be one at a time , But not invariable . The remaining servers are follower.

leader Will handle all external requests , If a server is not leader, Then this request will be forwarded to leader Handle .

leader Will give... In a fixed period of time follower Send a heartbeat （heartbeat）, tell follower：hi boys ! I am alive !

Every follower Each has its own timeout window （ Every follower Of timeout It may not be the same ）, When you don't receive it after a certain time leader Of heartbeat after , The cluster will enter the election state .

Learn from the following three aspects raft

• Leader election （Leader Election）
• Record replication （Log Replication）
• Security （Safety）

Leader election （leader election）

As you can see from the picture above , All nodes are follower role , If you don't receive it within a period of time leader The heart of （times out）, Then switch to candidate role , And then the election （starts election）; If you receive a majority of votes , Then switch to leader role ;

There are two Timeout time （timeout） It will affect leader election:

election timeout

follower Wait to become candidate Time for , This time is 150ms~300ms The range of is random .

If you exceed this timeout The time has not been received leader The heart of , So this follower I can do the following two things ：

1. Switch to candidate Role
2. its Term : 0->1 and Vote Count : 0 ->1

then , It will send messages to all other nodes （nodes） Send a Request to vote （Request Vote）. If the node that accepts the request is in this tenure （Term） I haven't voted yet , Then I will vote for this Request Vote Sponsor of , And will own election timeout Reset .

When one candidate When the node has a majority of votes , Then switch with this node to leader node .

heartbeat timeout

leader The node starts sending Append Entries Information to all follower node , This information is in accordance with heartbeat timeout Send at the specified time interval .followers received Append Entries After the request It will reset itself election timeout And respond .

thus , This term of office （Term） There will always be , Until one follower Don't get leader And switched to candidate role .

NOTE

1. In an even number raft cluster Once leader Unavailable , The rest candidate There may be at the same time “ Split brain ”（split vote） The risk of . Of course case The probability of occurrence is still extremely low , Only in leader Is not available , The rest candidate There are two remaining nodes in election time It will happen when it is completely consistent . So the official suggests one raft cluster There must be at least five nodes .
2. for fear of split vote,raft Introduced randomized election timeouts Avoid flat case happen .
3. raft It's a leader-based Consensus algorithm , Try to have an odd number of nodes , In this way, we can try our best to ensure majority Appearance .

Record replication （log replication）

When in a cluster leader After being elected , All requests from the client will be sent to leader,leader To schedule the order of these requests , And make sure that leader And followers Consistency of state .

Replicated state machines

Consensus algorithm is generally based on replication state machine （Replicated state machines） Realized .

ps： It doesn't unfold , If you have time, write another article ‍*️‍*️

raft in ,leader Will the client request (command) Packaged one by one log entry, And then put these log entries Copy （replicate） To all the follower node , Then all nodes are applied in order log entry Medium command, Then everyone's final state is the same .

Request flow

1. client Sent a request to leader,leader take “ change ”（change） add to （appended） To your own log in .
2. leader The next time heartbeat when , take “ change ”（change） Send to all followers
3. Once most follower Admitted this entry （entry）, Then the entry will be submitted （committed）
   1. similar 2PC, The difference is that leader There is no need to reply from all nodes , In this way, as long as more than half of the nodes are working, the system is available
4. leader The request response Send to client

NOTE

• Raft You can partition in the network （network partitions） Keep consistent
• raft Algorithm to ensure high availability , Not strongly consistent , It's ultimately consistent

Security （safety）

There's no time , Next time …‍*️