This crate is used at the core of Quickwit for
- cluster membership
- failure detection
- sharing configuration, and extra metadata values
The idea of relying on scuttlebutt reconciliation and phi-accrual detection is borrowed from Cassandra, itself borrowing it from DynamoDB.
A anti-entropy gossip algorithm called scuttlebutt is in charge of spreading a common state to all nodes.
This state is actually divided into namespaces associated to each node. Let's call them node state.
A node can only edit its own node state.
Rather than sending the entire state, the algorithm makes it possibly to only transfer updates or deltas of the state. In addition, delta can be partial in order to fit a UDP packet.
All nodes keep updating an heartbeat key, so that any node should keep receiving updates from about any live nodes.
Not receiving any update from node for a given amount of time can therefore be regarded as a sign of failure. Rather than using a hard threshold, we use phi-accrual detection to dynamically compute a threshold.
The resulting failure detection timeout is specific to each remote node and
adapts to its observed heartbeat intervals. Clients can inspect the current
timeout with Chitchat::failure_detection_timeout. The returned duration is
measured from the last received heartbeat; the actual liveness transition takes
place during a subsequent gossip round. This adaptive timeout is distinct from
dead_node_grace_period, which controls how long state is retained after a node
has been declared dead.
We also abuse chitchat in Quickwit and use it like a reliable broadcast,
with different caveats.
- ScuttleButt paper: https://www.cs.cornell.edu/home/rvr/papers/flowgossip.pdf
- Phi Accrual error detection: https://www.researchgate.net/publication/29682135_The_ph_accrual_failure_detector
- Cassandra details: https://www.youtube.com/watch?v=FuP1Fvrv6ZQ
- https://docs.datastax.com/en/articles/cassandra/cassandrathenandnow.html
- https://github.com/apache/cassandra/blob/f5fb1b0bd32b5dc7da13ec66d43acbdad7fe9dbf/src/java/org/apache/cassandra/gms/Gossiper.java#L1749
In order to get a constant flow of updates to feed into phi-accrual detection,
chitchat's node state includes a key-value called heartbeat. The heartbeat of a given node, starts at 0, and is incremented once after each round of gossip initiated.
Nodes then report all heartbeat updates to a phi-accrual detector to assess the liveness of this node. Liveness is a local concept. Every single node computes its own vision of the liveness of all other nodes.
The deletion of a KV is a just another type of mutation: it is associated with a version, and replicated using the same mechanism as a KV update.
The library will then interpret this versioned tombstone before exposing kv to the user.
To avoid keeping deleted KV indefinitely, the library includes a GC mechanism. Every tombstone is associated with a monotonic timestamp. It is local in the sense that it is computed locally to the given node, and never shared with other servers.
All KVs with a timestamp older than the configured
marked_for_deletion_grace_period are garbage-collected during periodic gossip
rounds. GC can happen at different times on different nodes. ChitchatConfig
requires callers to configure this value explicitly; the recommended value is
15 minutes.
This yields the following problem. If a node was disconnected for more than
marked_for_deletion_grace_period, they could have missed the deletion of a KV and never be aware of it.
To address this problem, nodes keep a record of the version of the last KV they have GCed. Here is how it works:
Let's assume a Node A sends a Syn message to a Node B. The digest expresses that A want for updates about Node N with a version stricly greater than V.
Node B will compare the version V of the digest with its max_gc_version for the node N.
If V > max_gc_version, Node B knows that no GC has impacted Key values with a version above V. It can safely emit a normal delta to A.
If however V is older, a GC could have been executed. Instead of sending a delta to Node A, Node B will instruct A to reset its state.
Node A will then wipe-off whatever information it has about N, and will start syncing from a blank state.
In Quickwit, we also use chitchat as a "reliable broadcast with caveats". The idea of reliable broadcast is that the emission of a message is supposed to eventually be received by all or none of the correct nodes. Here, a node is called "correct" if it does not fail at any point during its execution.
Of course, if the emitter starts failing before emitting its message, one cannot expect the message to reach anyone. However, if at least one correct nodes receives the message, it will eventually reach all correct nodes (assuming the node stays correct).
For this reason, we keep emitting KVs from dead nodes too.
To avoid keeping the state of dead nodes indefinitely, we make a very important trade off.
If a node is marked as dead for more than dead_node_grace_period, we assume
that its state can be safely removed from the system. The grace period is
computed from the last time we received an update from the dead node. It is
configured through FailureDetectorConfig and defaults to 24 hours.
Just deleting the state is of course impossible. After the given
dead_node_grace_period / 2, we will mark the dead node as
ScheduledForDeletion.
We first stop sharing data about nodes in the ScheduledForDeletion state,
and we stop including them in our digests.
We also ignore any updates received about the dead node. For simplification, we do not even keep track of the last update received. Eventually, all the nodes of the cluster will have marked the dead node as ScheduledForDeletion.
After another dead_node_grace_period / 2 has elapsed since the last update
received, we delete the dead node state.
It is important to set dead_node_grace_period to a value such that
dead_node_grace_period / 2 is much greater than the period it takes to detect
a faulty node.
Note that we are here breaking the reliable broadcast nature of chitchat.
New nodes joining after dead_node_grace_period, for instance, will never know
about the state of the dead node.
Also, if a node was disconnected from the cluster for more than
dead_node_grace_period / 2 and reconnects, it is likely to spread information
about the dead node again. Worse, it could not know about the deletion
of some specific KV and spread them again.
The chitchat library does not include any mechanism to prevent this from
happening. They should however eventually get deleted (after a bit more than
dead_node_grace_period) if the node is really dead.
If the node is alive, it should be able to fix everyone's state via reset or regular delta.