Zhang Yanpo (drdr.xp)

Zhang Yanpo (drdr.xp)

I write codes, by hands

The Pitfalls of Raft Membership Change

50 minute read

Article link: https://blog.openacid.com/distributed/raft-bug/

The Problem

A while back, over coffee, a friend described a problem their team had hit with Raft in production. It looks like a small detail. It cost them a whole cluster.

Their implementation uses single-server change: to change the replica set, you add or remove one node at a time. Moving from abc to bcd takes two steps. First add d, which gives abcd. Then remove a, which gives bcd.

The trouble lives in the middle step. While the cluster has four nodes, a network split of the shape ad | bc leaves it unable to elect a leader. That shape of split is easy to get when the nodes live in different datacenters. Say a, b and c each sit in their own datacenter:


 a      b      c
----   ----   ----
DC-1   DC-2   DC-3

        | add `d` in DC-1
        v

 a      b      c     partitioned     a   |  b      c
 d                   no leader!      d   |
----   ----   ----   ------------>  ---- | ----   ----
DC-1   DC-2   DC-3                  DC-1 | DC-2   DC-3

        | remove `a`,
        | healthy again
        v

        b      c
 d
----   ----   ----
DC-1   DC-2   DC-3

  • In the steady state, the cluster has three nodes. If any one datacenter loses contact with the outside, the other two still hold a majority. They elect a leader and keep serving.

  • In the middle state, DC-1 holds two nodes, a and d. A majority of four nodes needs three nodes. DC-1 has only two, so it cannot elect a leader on its own. DC-2 and DC-3 together also have only two, so they cannot either. One datacenter going quiet now stops the whole cluster.

Look at what happened to DC-1. In the four-node middle state, every majority has to include a node from DC-1. DC-1 became a single point of failure, and only because a membership change was in progress.

The root cause is that single-server change is rigid about one thing: a quorum is always a majority, and never anything else. Once we let go of that rule, the problem dissolves. So we will look at membership change through quorum sets, and that view leads us straight to joint consensus.

If quorum sets are new to you, my earlier article A Minority Implementation of Majority Read/Write introduces the way of thinking we use below.

Looking at the Problem Through Quorum Sets

Instead of describing a cluster by its nodes, describe it by its quorums. A quorum is a group of nodes that is allowed to commit something. The list of all such groups is the quorum set.

One rule keeps a quorum set safe: any two groups in it must share at least one node. That shared node is what stops two different values from both being committed, and it is the only thing Paxos and Raft really need from a quorum.

Here are the quorum sets in our story:

  • The starting state abc uses every majority of abc: M(abc) = {ab, ac, bc}. The full group abc is a quorum too, but it already contains ab, and any group that contains a quorum is a quorum. So listing the bigger groups adds nothing, and we list only the smallest ones.

  • The final state bcd uses M(bcd) = {bc, cd, bd}.

  • The middle state abcd of a single-server change is again a majority set: M(abcd) = {abc, abd, acd, bcd}.

So a single-server change is a walk through three quorum sets:

M(abc) → M(abcd) → M(bcd)

Now the availability problem has a one-line explanation. Every quorum in the middle set needs three nodes. When the network splits into ad | bc, neither side has three nodes. Neither side can elect a leader, and the cluster stops.

A First Patch: Let

bc Commit

The middle set is where it hurts, so let us change the middle set. Suppose we also allow bc to commit. The middle quorum set becomes:

Q(abcd) = M(abcd) ∪ {bc}

In plain words: an entry is committed once it reaches bc, or any three of the four nodes.

This is safe, and the check is quick. bc shares a node with every group in M(abcd), because bc has two nodes, each three-node majority leaves out only one node, and it cannot leave out both b and c. So the sharing rule still holds across the whole set. Paxos and Raft run on this middle state exactly as before, and consistency is untouched.

The change now reads: M(abc) → M(abcd) ∪ {bc} → M(bcd).

It is also still a legal membership change. Raft’s safety argument for a single-server change asks for one thing: every quorum of the old node set must share a node with every quorum of the new one. Our added group bc meets ab at b, meets ac at c, and meets bc at both. So if Raft is safe for M(abc) → M(abcd), it is equally safe for M(abc) → M(abcd) ∪ {bc}. The same check passes for the second step, M(abcd) ∪ {bc} → M(bcd).

That treats the symptom. The cluster now survives the ad | bc split while the change is running.

Why Majority Runs Out of Room

The four-node state has this weakness for a reason worth naming: M(abcd) is not the largest safe quorum set for four nodes.

With an odd number of nodes, majority is the best you can do. Take three nodes abc: you cannot add any smaller group to {ab, ac, bc}, because a single node such as a fails to meet bc. Majority is already maximal, so nothing is lost.

With an even number of nodes, majority leaves quorums on the table. A four-node system has four three-node majorities. On top of those, it can safely hold three more two-node groups:

Q’(abcd) = M(abcd) ∪ {ab, bc, ac}

Every pair in Q’(abcd) shares a node. ab and bc share b. ab and ac share a. bc and ac share c. Each two-node group also meets each three-node group, because two plus three is more than four. Paxos and Raft run on Q’(abcd) with no changes at all, and it tolerates strictly more failures than M(abcd).

Majority is the first weak spot in Raft’s design. By writing majority into the algorithm, Raft gives away availability that an even-sized cluster could have had.

How to Expand a Majority

Here is the general recipe. Let the node set be C, for example C = {a,b,c}.

  • For an odd node count, n = 2k+1, keep the majorities. They are already maximal:

    Q_{odd}(C) = M(C) = \{ q : q \subseteq C, |q| \gt |C|/2 \}\\

  • For an even node count, n = 2k, notice that any n/2 nodes must share a node with any n/2+1 nodes: together they count n+1 nodes in a cluster of only n. So we may add groups of size n/2 to M(C). The only extra thing to check is that the added groups share nodes with each other.

    In our four-node example:

    • Q’ = M(abcd) ∪ {ab, bc, ca} works: the three added groups pairwise share a node.
    • Q’ = M(abcd) ∪ {bc, cd, bd} works for the same reason.
    • Q’ = M(abcd) ∪ {ab, bc, cd} does not work: ab and cd share nothing, so two leaders could be elected at the same time.

    There is an easy way to produce a good one. Treat the even cluster as an odd cluster C plus one extra node x:

    D = C \cup \{x\} \\

    Then the quorum set for the even cluster can be an expansion of M(D):

    Q_{even}(D)_x = M(D) \cup M(D \setminus \{x\})\\

    In words: keep every majority of the four nodes, and also accept every majority of the three nodes left when you ignore x. Picking x = d produces the first example above, and picking x = a produces the second. Both hold more quorums than M(abcd), so both are more available, and both survive the datacenter split we started with.

What the Middle State Really Needs

Those examples make one thing clear. The middle state of a membership change does not have to be a majority set. It only has to be safe, and for our datacenter problem it has to contain bc.

Several middle states qualify:

  • M(abcd) ∪ {ab, bc, ac},
  • {abc, abd, acd, bcd, bc},
  • and even {abd, acd, bcd, bc}, with abc dropped.

Joint consensus qualifies too. It looks complicated on paper, and it turns out to be the simplest of all.

The Correctness Conditions

Before comparing algorithms, let us write down what a membership change has to guarantee. Describe each state by its quorum set, the way we have been doing, and let the change go from Q₁ to Q₂. It has to meet three conditions:

  • A committed change stays visible. If one change is already committed, every uncommitted change must be recognizable as uncommitted. Otherwise a new leader cannot tell which of them to keep.

  • Concurrent changes exclude each other. Only one of several concurrent changes may succeed, so every process proposing a change must commit it against the same quorum set. The only thing all processes already agree on is Q₁. So a change must be committed to Q₁, or to an expansion of Q₁ that every process derives in the same way.

  • The change reaches the new configuration. It must also be committed to a quorum of Q₂. Otherwise a leader elected under Q₂ may never see it.

Raft’s original single-server change misses the first condition. The author fixed it later, and we will come back to that.

Joint Consensus Gives Us Exactly That

Joint consensus meets all three conditions. It also handles our datacenter problem, without anyone designing it for that.

In a change from abc to bcd, the joint middle state is the product of the two majority sets:

Q = M(abc) x M(bcd)

A joint quorum is any group that contains one quorum of M(abc) and one quorum of M(bcd) at the same time. With M(abc) = {ab, bc, ca} and M(bcd) = {bc, cd, bd}, the product is:

M(abc) x M(bcd) = {
    ab ∪ bc,
    ab ∪ cd,
    ab ∪ bd,
    bc ∪ bc,
    bc ∪ cd,
    bc ∪ bd,
    ac ∪ bc,
    ac ∪ cd,
    ac ∪ bd,
} = {
    abc,
    abcd,
    abd,
    acd,
    bc,
    bcd,
}

That is exactly M(abcd) ∪ {bc} — the very quorum set we built by hand a few sections ago.

So joint consensus hands us everything we were after:

  • It tolerates one node failure.
  • It always contains bc, so it survives the ad | bc split that started this article.
  • The whole change finishes with two committed log entries, whether or not the leader changes along the way.

The Bug in Single-Server Change

Single-server change has a second problem, and this one is heavier than availability. As first published, it was simply incorrect.

The bug appears when a leader change and a membership change run at the same time. The author announced it in 2015:

Unfortunately, I need to announce a bug in the dissertation version of membership changes (the single-server changes, not joint consensus). The bug is potentially severe, but the fix I’m proposing is easy to implement.

Here is how it goes wrong. The cluster starts with the four nodes abcd. One process wants to add u, another wants to add v. A leader change in the middle loses a committed entry:

C₀ = {a, b, c, d}
Cᵤ = C₀ ∪ {u}
Cᵥ = C₀ ∪ {v}

Lᵢ: Leader in term `i`
Fᵢ: Follower in term `i`
☒ : crash

    |
 u  |         Cᵤ                  F₂  Cᵤ
--- | ----------------------------------
 a  | C₀  L₀  Cᵤ  ☒               L₂  Cᵤ
 b  | C₀  F₀          F₁          F₂  Cᵤ
 c  | C₀  F₀          F₁  Cᵥ          Cᵤ
 d  | C₀              L₁  Cᵥ  ☒       Cᵤ
--- | ----------------------------------
 v  |                     Cᵥ                  time
    +-------------------------------------------->
          t₁  t₂  t₃  t₄  t₅  t₆  t₇  t₈
  • t₁: the four nodes abcd elect a as leader in term 0, with followers b and c.
  • t₂: a appends a change entry Cᵤ and switches to the new config Cᵤ right away. The entry reaches only a and u, so it is not committed.
  • t₃: a crashes.
  • t₄: d is elected leader in term 1, with followers b and c.
  • t₅: d appends another change entry Cᵥ and switches to Cᵥ. The entry reaches c, d and v, which is a majority of the five nodes in Cᵥ, so it is committed.
  • t₆: d crashes.
  • t₇: a comes back and is elected leader in term 2. It runs under Cᵤ, the config it sees in its own log, and collects votes from u and b.
  • t₈: a replicates its own log to everyone, and the committed Cᵥ is gone.

Read t₅ and t₈ together, because that is where the damage is. Cᵥ was committed under every rule Raft gives us, and then it was overwritten. The reason is that a was allowed to run an election under a configuration nobody else had ever committed.

The author’s fix is short, and it echoes a rule Raft already has for ordinary entries:

The solution I’m proposing is exactly like the dissertation describes except that a leader may not append a new configuration entry until it has committed an entry from its current term.

In our timeline, d must commit a no-op entry in term 1 before it may append Cᵥ. Once b and c hold that no-op, a can no longer win the term-2 election: b sees that a’s log is behind and refuses to vote for it. So a never becomes L₂, and the committed Cᵥ survives.

Look Closely at That Fix

The fix quietly turns single-server change into joint consensus.

Both end up doing the same job. A change has to pass through a quorum of the old configuration first, so that only one change out of several concurrent ones can be considered committed. Single-server change reaches that point with an extra entry: an ordinary application entry if one is handy, or a no-op if not. Joint consensus reaches it directly, because its middle state already is the old configuration and the new configuration at the same time.

A correct single-server change costs two log commits, every time.

Single-server change was proposed to make things simpler, and it does not. Changing abc to bcd costs 2 to 4 log entries with single-server change. With joint consensus it costs 2.

There is a fair objection here: single-server change often needs only 2 entries, since the leader usually has a committed entry of its own term already and no no-op is required. That is true, and it does not help. Code is not a bet on probability. Every branch that can run has to be written, tested and maintained, including the one that fires once in ten thousand changes. So a correct single-server change carries almost the same logic as joint consensus, implements a two-step change anyway, and wins nothing at runtime.

Closing Thoughts

Raft is a beautiful bridge from theory to working code, and that beauty is exactly why one design mistake in it travelled so far.

If you are building or maintaining a Raft implementation, the advice is short: use joint consensus. It closes the availability hole in the middle state, it removes the bug, and it is less code than a correct single-server change.

Reference:

Article link: https://blog.openacid.com/distributed/raft-bug/

openacid

Leave a comment

You may also enjoy