Implementing Simple Paxos Consensus Algorithm With Rust
12 February 2024 tagged distsys, rust 4 min read · 5 links out
What Is Consensus?
I would say that one of the core properties of a system is the agreement on which data
are right at a given moment.
At that moment, one of the more important aspects of a distributed system shows up:
the consensus. Where every participant agrees on a single state, even if some actor
fails.
Some use cases where consensus brings a strong advantage are network agreement in a
server cluster, database replicati ons, and even in blockchain networks.
The Simple Paxos
The Simple Paxos algorithm is the most simple implementation of the Paxos Protocol family.
As presented by Leslie Lamport on the The Part-Time Parliament
and Paxos Made Simple,
the idea of the Simple Paxos is simple:
Your node can assume 3 different roles: proposers, acceptors and learners.
Your node can be all these roles at the same time.
An acceptor will accept the first value that is received as a proposal.
A proposer will receive a promise from every acceptor, that promise let
the proposer knows that the node will accept the proposed value.
A proposer reach the quorum, that is, the majority, when receive a promise
of where is the number of nodes in the system.
After reach the quorum, the learners will receive the accepted value from
the acceptors. The learners will put the accepted value into their state
machines.
(This is a simple sequence diagram coming from Wikipedia, but it’s a good representation)
Preparing the proposal for a new value
A proposer is the node that will propose a new value to reach the consensus
around their system. In this case, each proposal follows this pattern: (id, v),
where the id is an incrementally natural number, and v is the proposed value,
for our implementation, we will assume v as a string.
First things first. We need to start our server. In this case, using Rust, I will
use Axum to do all the work for me:
Now, we have a server running on the port that we want. You can test it by running:
cargo run -- --id 1 --port 3000
We will implement the proposer logic on the /prepare endpoint. The proposer
will send a prepare message to all acceptor messages and wait
for the promises.
In this first phase, we will only send the prepare message to all acceptors. The
prepare message is a simple message with the id of the proposal. The acceptor will
receive this message and will send a promise to the proposer.
implProposer{// ...
pub async fnprepare(&mutself, state:&AppState, value: String)->Result<Proposal, String>{let client =Client::new();self.id +=1;let nodes = state.nodes.lock().await;let reqs = nodes.iter().map(|node|{
client.post(format!("http://{}/handle-prepare", node.addr))
.json(&self.id)
.send()});let responses =futures::future::join_all(reqs).await;letmut promises =Vec::with_capacity(responses.len());for response in responses.into_iter().flatten(){
promises.push(response.json::<HandleProposalPayload>().await.unwrap());}let quorum =(nodes.len()/2)+1;if promises.len()< quorum {returnErr(String::from("Proposal does not receive promises of the entire quorum"));}let accepted_promise = promises
.into_iter()
.filter(|promise|promise.value.is_some())
.max_by_key(|promise|match&promise.value {None=>0,Some(value)=> value.id,});// Sorry, I'm not proud of it, but it's the best that I can do for now. :(
// Feel free to improve it (PLEASE!).
let value =match accepted_promise {None=>Some(value),Some(payload)=>{match payload.value {None=>Some(value),Some(proposal)=>{match proposal.value {None=>Some(value),
b => b,}},}}};let proposal = Proposal { id:self.id, value };Ok(proposal)}}
We implement the proposer.prepare method to send the prepare message to all acceptors. What
this is doing is:
Calling the /handle-prepare endpoint of all nodes in the system.
Waiting for the promises of the acceptors.
Checking if the proposer received the quorum of promises.
If the proposer received the quorum, it will check if there is a value that was accepted
by the acceptors. If there is, the proposer will use this value as the proposed value. If
not, the proposer will use the value that it wants to propose.
Return the proposal.
Receiving the prepared value and sending the promise
Cool. We’re coming to what we can call the phase 1b. The acceptor will receive
the prepare message and need to send a promise if everything is OK. In this case, which
things do we need to check?
If the proposal number is greater than the last proposal number that the acceptor
received.
If the acceptor already accepted a value, if yes, it needs to send the accepted
value to the proposer.
We improved the handle-prepare function to handle all the logic of the acceptor
receiving the prepare message, instead of just a todo!(). If everything is OK,
the acceptor will return a promise to the proposer. If not, it will return an error
message.
Receiving the promise and handling the acceptance message
Now that the proposer received the promise, we need to start with the phase 2a.
The proposer will send the accept message to all acceptors. The accept message needs
to contain the proposal and their identifier.
Then, the first part of our implementation will be improving the implementation of our
Proposer struct. In this case, we will need to add a new function called propose.
#[derive(Serialize, Deserialize, Debug)]structHandleAcceptPayload{error:Option<String>,
value:Option<Proposal>,
}implProposer{// ...
pub async fnpropose(&self, state:&AppState, proposal:&Proposal)->Result<(), String>{let client =Client::new();let nodes = state.nodes.lock().await;let reqs = nodes.iter().map(|node|{
client.post(format!("http://{}/handle-accept", node.addr))
.json(&proposal)
.send()});let responses =futures::future::join_all(reqs).await;letmut accepted_promises =Vec::with_capacity(responses.len());for response in responses.into_iter().flatten(){
accepted_promises.push(response.json::<HandleAcceptPayload>().await.unwrap());}let quorum =(nodes.len()/2)+1;if accepted_promises.len()+1< quorum {returnErr(String::from("Proposal not accepted by majority"));}Ok(())}}
This propose function will send the accept message to all acceptors and wait for the
acceptance of the proposal. If the proposer receives the quorum of acceptances, it will
return Ok(()). If not, it will return an error message.
Now, we need to implement the /handle-accept endpoint to handle the accept message.
async fnhandle_accept(State(state): State<AppState>, propose:Json<Proposal>)->(StatusCode, Json<HandleAcceptPayload>){letmut acceptor = state.acceptor.lock().await;if acceptor.last_proposal_number != propose.id {let payload = HandleAcceptPayload {
error:Some(String::from("Node received a proposal with a proposal ID different!")),
value:None,};return(StatusCode::BAD_REQUEST, Json(payload));}
acceptor.accepted_proposal = propose.value.clone();let payload = HandleAcceptPayload {
error:None,
value:Some(Proposal { id: propose.id, value: propose.value.clone()}),};(StatusCode::OK, Json(payload))}
Now, we have the acceptor receiving the accept message and handling it. If everything
is OK, the acceptor will accept the proposal and return an acceptance message to the
proposer.
We will need to add the proposer.propose call on the /prepare endpoint.
async fnprepare(State(state): State<AppState>, value: String)->(StatusCode, String){// ...
match proposer.propose(&state,&proposal).await {Err(e)=>(StatusCode::BAD_REQUEST, e),Ok(_)=>{let client =Client::new();let nodes = state.nodes.lock().await;let reqs = nodes.iter().map(|node|{
client.post(format!("http://{}/handle-learn", node.addr))
.json(&proposal)
.send()});futures::future::join_all(reqs).await;(StatusCode::OK,String::from("Proposal accepted by the majority!"))},}}
Removing that old todo!() and putting the proposer.propose call on the /prepare,
we have the proposer sending the accept message to all acceptors and waiting for
the acceptance of the proposal. If the proposer receives the quorum of acceptances,
it will send the accepted value to all learners.
Learning the accepted value
The last part of our implementation is the /handle-learn endpoint. The learner
will receive the accepted value and put it into their state machines.
After learning the accepted value, the learner will put it into their state machines. And
then we have the consensus around the system. The acceptor will
send the accepted value to the learner, but I think it’s easier to implement
just sending the accepted value to the learner via proposer.
Conclusion
This is the most simple implementation of Paxos Protocol consensus algorithm.
You have some variants that brings some improvements to the Paxos, like the
Multi-Paxos and EPaxos. All of these have some properties that are best for
specific use cases.
If you want to see the repo with the implementation of this algorithm, you can
access it here.
Thanks to hnrbs, one of my inspirations to write this
code and learn more about Paxos and consensus.
You can see his implementation here.
…that I could do it better, but I have some great works this year, like: Increasing Your Friction Area, Implementing Simple Paxos Consensus Algorithms With Rust and RSS and why I love it.
/blog/2024-in-review/2024 in Review30 December 2024 · reviewFollowing the tradition, writing my annual review. This year, being from ups and downs, a lot of things happened. I can consider 2024 a good year looking from the macro perspective, but far from what I would like. I was able to conclude my biggest objective…Linked from 1 note
/blog/embrace-the-chaos-of-your-life/Embrace The Chaos of Your Life4 February 2024 · self-improvement, thinkingThe last weeks were too hard for me. I need to spend too much time doing things in my personal life and ensure that I can bring good work to my professional life.
/blog/set-up-nix-on-macos-using-flakes-nix-darwin-and-home-manager/Set up Nix on macOS using flakes, nix-darwin and home-manager3 March 2024 · nixAbout three years ago, I started using NixOS on my personal laptop. In those days, I needed a config that would allow me to have a stable system, that could be reproducible over all my machines, and that would allow me to have a development environment that…Linked from 1 note
github.comhis implementation herecited in 1 note
github.comPaxos From Scratchcited in 2 notes
↗ githubhnrbscited in 1 note
lamport.azurewebsites.netThe Part-Time Parliamentcited in 1 note
lamport.azurewebsites.netPaxos Made Simplecited in 1 note