Details
-
Improvement
-
Status: Triage Needed
-
Normal
-
Resolution: Unresolved
-
None
-
None
-
All
-
None
Description
This ticket presents a practical protocol for performing safe ring membership updates in Cassandra. This protocol will enable reliable concurrent ring membership updates.
The proposed protocol is composed of the following macro-steps:
PROPOSE: An initiator node wanting to make updates to the current ring structure (such as joining, leaving the ring or changing token assignments) must propose the change to the other members of the ring (cohort).
ACCEPT: Upon receiving a proposal the other ring members determine if the change is compatible with their local version of the ring, and if so, they promise to accept the change proposed by the initiator. The ring members do not accept proposals if they had already promised to honor another proposal, to avoid conflicting ring membership updates.
COMMIT: Once the initiator receives acceptances from all the nodes in the cohort, it commits the proposal by broadcasting the proposed ring delta via gossip. Upon receiving these changes, the other members of the cohort apply the delta to their local version of the ring and broadcast their new computed version via gossip. The initiator concludes the ring membership update operation by checking that all nodes agree on the new proposed version.
ABORT: A proposal not accepted by all members of the cohort may be automatically aborted by the initiator or manually via a command line tool.
For simplicity the protocol above requires that all nodes are up during the proposal step, but it should be possible to optimize it to require only a quorum of nodes up to perform ring changes.
A python pseudo-code of the protocol is available here.
With the abstraction above it becomes very simple to perform ring change operations:
Token Ring Data Structure
The token ring data structure can be seen as a Delta State Replicated Data Type (Delta CRDT) containing the state of all (virtual) nodes in the cluster where updates to the ring are operations on this CRDT.
Each member publishes its latest local accepted state (delta state) via gossip and the union of all delta states comprise the global ring state. The delta state must be commutative and idempotent to ensure all nodes will eventually reach the same global state no matter the order received.
The content-addressed fingerprint of the global ring state uniquely identifies the ring version and provides a simple way to verify agreement between nodes in the cluster. Any change to the ring membership must be agreed using the described protocol, ensuring that both conditions are met:
- All nodes have the same current view of the cluster before the update (verified via the ring version fingerprint).
- All nodes have agreed to make the exact same update and not accept any other update before the current proposed update is committed or aborted.
Ring Convergence Time
Assuming there are no network partitions, the ring membership convergence time will be dominated by the commit step since that is performed via gossip broadcast.
The gossip broadcast is performed by sending the ring delta to the seed nodes, since other nodes will contact seed nodes with a #seeds / #nodes probability. This will define an upper bound for the maximum time it takes to propagate a ring update that was accepted by all members of the ring.
On a cluster with 10% of the nodes as seeds, it’s guaranteed that a ring membership update operation will not take much longer than 10 seconds with the current gossip interval of 1 second. A simple way to reduce this upper bound is to make cohort acceptors gossip more frequently with seeds when there are pending ring membership updates.
Failure Modes
- Concurrent Proposals:
- Concurrent initiators will not gather sufficient promises from all cohort members, and thus, will not succeed. Unsuccessful proposals may be cleaned up manually or automatically via the ABORT step.
- Single proposal: Initiator Failure
- Initiator is partitioned before sending proposal
- Initiator will not gather sufficient promises from all cohort members, and thus, the ring membership update will not succeed.
- Initiator is partitioned after proposal is accepted by a subset of cohort members:
- Initiator will not gather sufficient promises from all cohort members. No other proposal will succeed before the partition is healed or it’s manually ABORTED.
- Initiator is partitioned after proposal is accepted by all cohort members
- No other proposal will succeed before the partition is healed or it’s manually ABORTED.
Initiator is partitioned after proposal is committed - If a single member of the cohort committed the proposal, all other members will eventually commit it since they will receive the update via gossip. No other proposal will be accepted before all nodes commit the current proposal.
- No other proposal will succeed before the partition is healed or it’s manually ABORTED.
- Initiator is partitioned before sending proposal
- Single proposal: Cohort member Failure
- Cohort member is partitioned before receiving proposal
- Initiator will not gather sufficient promises from all cohort members. No other proposal will succeed before the partition is healed because they will not be able to reach this cohort member.
- Cohort member is partitioned after accepting proposal
- If all other members of the cohort accepted the proposal, the initiator will COMMIT the proposal. No other proposal will succeed before the partition is healed because they will not be able to reach this cohort member.
- Cohort member is partitioned after committing proposal
- If a single member of the cohort committed the proposal, all other members will eventually commit it since they will receive the update via gossip from the initiator. No other proposal will be accepted before all nodes commit the current proposal.
- Cohort member is partitioned before receiving proposal
Attachments
Issue Links
- is required by
-
CASSANDRA-16141 Enable Adding and Removing Tokens to a Node (Dynamic Virtual Nodes)
-
- Triage Needed
-
-
-
- Triage Needed
-
- relates to
-
-
- Open
-
- requires
-
-
- Triage Needed
-