Dynamic Group Membership Improvements

[jkosh44]

Hi, my team and I have been building a system using openraft (I've opened some discussions and issues before). Recently we've been implementing dynamic membership and I think there are some improvements that openraft can make around this feature. I'm opening this discussion to see what people think.

Unique Node IDs

This one is maybe obvious in hindsight, but it is not valid to reuse node IDs. I.e. callers should avoid doing something like

1. Add node n1.
2. Remove node n1.
3. Add node n1.

unless the n1 in step (3) has the exact same log contents as the n1 from step (1). Otherwise it's as if n1 had reverted its log which can lead to split brain situations. For example here's a split brain scenario:

0. At some point in the past group membership was {n3}.
1. Currently, Group membership is {n1, n2, n3}, n1 is the leader.
2. n1 removes n3 from group making membership {n1, n2}.
3. n3 confirms that it has been removed and wipes its disk.
4. n1 adds a new n3 to group making membership {n1, n2, n3}.
5. n3, starting with an empty disk, replays log up to the point where membership was {n3}.
6. At this point two independent quorums can be made, {n1, n2} and {n3}. Each can start committing writes leading to a split brain.

I don't actually think any code changes are needed here, but it would be helpful to explicitly call this out somewhere in the documentation. It's maybe implicit in the FAQ when it says not to wipe the data of a node, but it would be helpful if this was explicitly stated in the dynamic membership docs

Rejecting Stale Membership Changes

As it turns out, it's actually a bit difficult to avoid re-adding a removed node. Imagine that I'm a human or computer operator and I want to change the membership of my cluster. Then consider the following series of events:

1. I create a new physical node with ID n, initialize the on-disk state, and start an openraft engine.
2. I send a message to the current leader to add node n. This message times out, maybe it's lost in the network.
3. I send a second message to the current leader to add node n. This message arrives successfully.
4. Leader updates group membership to include n.
5. I send a message to the current leader to remove node n.
6. Leader updates group membership to remove n.
7. I send a message to n to stop its openraft engine and delete its on-disk state.
8. My message from step (2) finally arrives at the leader. The leader then adds n back into the group membership. n is still running, it still has log entries, so nothing blocks it from being promoted from a learner to a voter.
9. My message from step (7) arrives at n. n stops its openraft engine and deletes its on-disk state.

We've now entered a really bad scenario. n is part of the group membership, but it is dead. Its log is deleted and it will not respond to any heartbeats. If the group membership only had two members, the group can no longer achieve a quorum. For larger group membership numbers, you can repeat the above multiple times to also get into a stuck position.

How can I prevent this situation? I spent a lot of time trying to figure this out, and I don't think there's a simple solution with the current API. So here are some possible updates to the API to help with this. I'm curious if you agree that this is a problem, if the current API makes this hard/impossible to solve, what you think about the following proposals, and if you have any other ideas?

Previous Log Index

This approach adds an optional field to all membership change requests of the log index of the previous membership change. Callers would include this field when they send a membership change request. openraft then rejects the request if log index is not accurate, i.e. there has been a new membership change since the index provided in the field.

A drawback of this approach is that it may be difficult for callers to actually get the value of the log index of the previous membership change.

This is the approach that Hashicorp Raft takes:

• https://github.com/hashicorp/raft/blob/80648832372a6458fdecd505d87be1cf68161491/api.go#L986-L994
• https://github.com/hashicorp/raft/blob/80648832372a6458fdecd505d87be1cf68161491/configuration.go#L224-L227

Opaque Configuration Version

This approach is similar to the "Previous Log Index" approach, but instead of adding a log index to requests, an opaque version number is added to every request. Each membership change is appended to the log with this opaque version number. openraft then rejects the request if the version is less than or equal to the previously appended version number.

A drawback of this approach is that callers are responsible for generating monotonically increasing version numbers somehow.

This is roughly the approach that TiKV takes:

• https://github.com/tikv/pd/wiki/Metadata-Management#region-metadata-cache-in-tidb
• https://github.com/tikv/tikv/blob/v8.5.7/components/raftstore/src/store/util.rs#L307-L345

Removed ID Set

This approach involves storing a set of removed IDs somewhere in the log. Every time a remove node is appended to the log, it updates this set. openraft then rejects add node requests if it's a member of the removed set.

There are a couple of drawbacks with this approach. First of all the set strictly grows and I don't think it's ever safe to clean it up. Also, callers may have a legitimate reason for re-adding a node, as long as the log hasn't reverted. This prevents them from doing that. For those reasons I don't think it's a good fit for openraft, but I wanted to mention it anyway.

This is the approach etcd takes:

• https://github.com/etcd-io/etcd/blob/f744d457f484e9f748a0700b48ef96dcf792df33/server/etcdserver/api/membership/cluster.go#L54-L56
• https://github.com/etcd-io/etcd/blob/f744d457f484e9f748a0700b48ef96dcf792df33/server/etcdserver/server.go#L1988-L1992
• https://github.com/etcd-io/etcd/blob/f744d457f484e9f748a0700b48ef96dcf792df33/server/etcdserver/api/membership/cluster.go#L306-L316

Deterministic Node IDs

This is an interesting approach, I don't think it's a good fit for openraft, but it's interesting enough to mention.

This approach stores a next_node_id field somewhere in the log. Add node requests DO NOT contain any node ID. When openraft receives an add node request, it assigns it the node ID of next_node_id and increments next_node_id in the same log entry. That way all nodes can deterministically derive the node ID from the log.

The drawbacks are that this would be a really big breaking change and it would prevent callers from supplying their own node IDs, which they may want to do for some reason.

This is the approach CockroachDB takes:

• https://github.com/cockroachdb/cockroach/blob/master/docs/RFCS/20150729_replica_tombstone.md

[jkosh44]

Between the previous log index and opaque config version approaches, I personally much prefer the opaque conf versions. It's roughly equivalent to the previous log index approach but strictly more general. Callers could use the log index of the previous membership change as a version and it would work the same.

[jkosh44]

One potential answer might be, just have the application solve this issue by implementing one of the above ideas in the application. I've thought about that, but still can't figure out how to do it correctly. Basically all of the above approaches boil down to the following two steps:

1. Validate a membership change.
2. Append the membership change to the log if valid.

If I'm understanding correctly, those two steps MUST be done atomically, otherwise there's a race where the change is invalidated before it's appended. A solution to that could be for the application to handle all membership changes sequentially, maybe on a single task/thread. However, that just eliminates the race from happening on a single node, not across nodes. In-between steps (1) and (2), the node could lose leadership, the change becomes invalidates, then the node regains leadership and appends it to the log.

I think the only way for (1) and (2) to be done atomically is form within openraft itself.

[drmingdrmer]

Both of the problems you raise, unique node IDs and stale membership changes, come from one root cause: a node rejoining the cluster under an ID it already used, after its state was reverted.

Unique node IDs. Raft assumes a node never loses state it has already acknowledged. Wiping a node's disk and letting it rejoin under the same ID is a state reversion dressed up as a membership change, and after such a reversion the protocol guarantees nothing: the split brain you describe is one symptom, silent loss of committed logs is another symptom. No code change is needed. I am adding the rule that a node ID must never be reused to the dynamic membership guide and to the FAQ.

Stale membership changes. Your step-8 sequence, where a delayed duplicate re-adds a node that then wipes itself, is real, and only openraft itself can prevent that sequence, since validating a membership change and appending it must be one atomic step.

Of your four proposals I would take Previous Log Index. Your objection to Previous Log Index, that a caller cannot easily obtain the log index of the previous membership change, does not apply to openraft: RaftMetrics::membership_config holds the effective membership as a StoredMembership, whose log_id() returns exactly that index for the caller to pass back with the next membership change. openraft already stores that log id alongside the membership, so the engine-side check that rejects a request carrying a stale log id is small. Opaque Configuration Version instead has to travel inside the membership config entry, and the membership type reaches into many parts of openraft.

Previous Log Index only removes the stranded cluster of your step 8, which is an availability failure. Previous Log Index does not make ID reuse safe: a node that rejoins under a used ID with reverted state still breaks consensus, because a precondition orders membership changes but does not restore the log that the node erased.

Allocating node IDs. To obtain an ID that no node has ever held, write a blank entry to the cluster and use the log index returned for that blank entry. The Raft log is the one counter every node already agrees on, and no committed log index is handed out twice. A small project of mine allocates node IDs this way: ezraft server.rs.

If openraft enforces that a node ID never rejoins the membership once it has left, that enforcement also covers your step 8: the delayed add for n is rejected on arrival, before it can strand the cluster. Left to the operator instead, "never re-add a node ID that has been removed" does not cover step 8, because in your sequence you never chose to re-add n. The duplicate add message you sent in step 2 re-added n on its own, long after you had removed n.

[jkosh44]

Than you for your in-depth reply!

Allocating node IDs.

This is a very interesting approach and similar in spirit to the approach CRDB takes. Just to clarify, does doing this remove the need to include a previous log index check?

If openraft enforces that a node ID never rejoins the membership once it has left, that enforcement also covers your step 8

Are you saying that openraft should implement this? I think it's fairly difficult for openraft to enforce that node IDs are not reused. It would either need to track all previously added node IDs or enforce that node IDs are monotonically increasing and track a lower bound.

[drmingdrmer]

does doing this remove the need to include a previous log index check?

A previous config log index is still needed to avoid duplicated membership-config-change write requests.
I think this is the same as an at-most-once approach for writing.

Are you saying that openraft should implement this? I think it's fairly difficult for openraft to enforce that node IDs are not reused. It would either need to track all previously added node IDs or enforce that node IDs are monotonically increasing and track a lower bound.

AFAIK it's not very easy to get it done inside OpenRaft. And such requirement is usually implemented with another Raft group to allocate the node ID.
What I mean is that the application using openraft should not use a duplicated node-id.

[jkosh44]

It sounds like the previous log index approach is the right way forward. Do you plan on making the change? If not I'd be happy to submit a PR myself.

[drmingdrmer]

I'd do it. Please help me review to make sure it meet your requirements

[jkosh44]

Allocating node IDs. To obtain an ID that no node has ever held, write a blank entry to the cluster and use the log index returned for that blank entry. The Raft log is the one counter every node already agrees on, and no committed log index is handed out twice. A small project of mine allocates node IDs this way: ezraft server.rs.

Here's an interesting alternative idea that could work after the previous Log Index check is implemented. Applications can use the log index of the previous membership change as both the node ID and as the validation. That would guarantee unique node IDs and avoid writing blank entries.

[drmingdrmer]

yes if only one node is added to the membership. a second node need another unique log index as its log id