Async & consensus algorithm

Say you have to implement consensus algorithm.

The moment you receive request, you run parse and analyze query, write the log and finally propagate the log and wait until majority votes is made, hence consensus.

And as you can imagine, this is arguably the most critical section that requires pretty good performance.

Sequential call

If you run IO operation sequentially to get votes as follows:

// self.replicas() returns the mutable reference to each replica
for replica in self.replicas() {
    let _ = replica.write_io(message.clone()).await;

}

the latency will be N(number of replicas) x (avg. latency of IO).

Generally under high load, effect of each async call gets normalized, so these sequential approach may even be encouraged but just not this time. There should be some way to allocate more time to the given subroutine.

Join - ordered

One way to solve these particular problem is generate the iterater and run all the asynchronous call in one-go as follows:

join_all(self.replicas().into_iter().map(|rep| rep.write_io(message.clone()))).await;

Okay, this works perfectly fine and will be encouraged if you want to achieve concurrent behaviour.

But when it comes to majority votes, order of execution is not of your concern and it turns out, respecting order actually comes with slight a bit of cost.

There comes the last option.

Unordered execution: Faster Completion as Results Arrive

let mut tasks = self
    .replicas()
    .into_iter()
    .map(|rep| repl.write_io(message.clone()))
    .collect::<FuturesUnordered<_>>();

while let Some(result) = tasks.next().await { 
    // Process results as soon as they arrive
}

This final version doesn't respect the order. Some characteristic of this implementation is

• Execution: Fully concurrent, processes each future as soon as it completes.
• Latency: Closer to max(latency of any single write_io), since results don’t wait for others.
• Advantage: If one request takes significantly longer, it doesn’t block processing of faster responses.

You can see the actual implementation of this.