Hey {{first name | there}}. Every Kubernetes cluster keeps its entire state in etcd, every pod, secret, and ConfigMap you have ever created lives there. The API server is really just a nice front end over that one key-value store. And etcd keeps its copies in agreement across its members using Raft.

So the first time I actually cared about Raft was not from a paper. It was from learning about the datastore that powers Kubernetes.

In today’s issue, I wanted to go over an interesting paper I came across last week and why I think you should care.

Raft exists because Paxos is famously hard to reason about. The Raft paper's actual goal, stated up front, was understandability. It breaks consensus into parts you can hold in your head: elect one leader, replicate a log from that leader, and keep everyone's log consistent.

That clarity is why Raft ended up inside etcd, Consul, TiKV, CockroachDB, and plenty of other systems people trust with real data.

The trade is performance. When you optimize a design so a human can understand it, you usually leave some speed on the table. The improved-Raft paper I want to talk about says this plainly: Raft "is always compromised in terms of performance as a trade-off" for comprehensibility. 

Two places make that trade very visible. The first is leader election. The second is how the log gets written, which is what the paper actually attacks.

Raft has no clock it can trust and no oracle that announces "the leader is dead." It uses timeouts instead.

The leader sends heartbeats. Each follower keeps an election timeout, which is a randomized countdown. If a follower does not hear a heartbeat before its countdown hits zero, it assumes the leader is gone, becomes a candidate, and starts an election.  The randomization is what stops everyone from nominating themselves at once.

The catch is that a timeout cannot tell "the leader crashed" apart from "the heartbeat is just late." If your network round trip ever creeps close to the election timeout, followers start timing out on a leader that is perfectly alive. 

This is why the timeout has to be comfortably larger than your worst round trip. etcd's own tuning guidance is to set the election timeout to at least ten times the round-trip time between members. On a LAN, round trips are well under a millisecond, so the defaults (a 100ms heartbeat, a 1000ms election timeout) have enormous headroom. 

Stretch the same cluster across regions, where round trips run tens to hundreds of milliseconds, and you have to widen the timeout, which makes real failures slower to detect. On top of that, every write already pays the cross-member latency, because a write is not committed until a majority has acknowledged it.

The paper is An Improved Raft Consensus Algorithm Based on Asynchronous Batch Processing by Hao Li, Zihua Liu, and Yaqin Li, from WCNA 2021. Its target is throughput under high concurrency, not elections.

To see what they change, walk the normal Raft write path. A client sends a command. The leader appends it to its log, then flushes that entry to disk so it survives a crash, then sends it to the followers, waits for a majority to persist and acknowledge, marks the entry committed, applies it to the state machine, and finally answers the client.

Two steps in that path are expensive and, in plain Raft, happen one entry at a time. Flushing to disk means an fsync, and fsync is slow because it waits for the storage to actually confirm the write. Replicating means a round of RPCs to the followers. Doing that per request means you pay those fixed costs over and over, and under high concurrency they become the ceiling.

The paper adds a pre-proposal stage in front of the formal Raft proposal. Incoming requests collect there and get grouped, so instead of proposing one command, the leader proposes a batch. Then it does two things asynchronously: it replicates the batch to followers without blocking request by request, and it flushes to disk in batches rather than forcing a separate fsync per entry.

Batching is one of the oldest tricks in systems work, and it applies cleanly here because the costs it amortizes, the disk sync and the replication round trip, are fixed per operation rather than per byte. Group a hundred requests into one flush and one replication round, and each request's share of that overhead drops sharply.

The reported numbers back that up. The improved Raft raises system throughput by 2 to 3.6 times, and processing efficiency for parallel requests by 20 percent or more. That is a real gain for a change that leaves Raft's structure recognizable.

Honestly, I think it is an interesting take on probably one of the easier distributed consensus algorithms, and in due time I would be even more interested to see if it gains any adoption.

Know an engineer who would find this interesting? Share this link with them

Jubril Oyetunji
CTO, EverythingDevOps