Online resharding — adding and removing nodes at runtime

skaidb places keys on a consistent-hash ring (vnodes). The ring is held behind a lock so membership can change while the cluster serves traffic: a node can join or leave online and the keyspace rebalances without a restart or a full reload.

Why a single join moves so little

Consistent hashing is the whole point: when one node joins, the only keys that change owner are the ones whose hash now lands on the joiner's vnodes. Every other key keeps its current placement. So a join moves roughly 1/(N+1) of the keyspace onto the new node and disturbs nothing else — no global reshuffle. (Contrast hash-modulo-N sharding, where bumping N remaps almost every key.)

Versioned, persisted membership

The ring carries a monotonically increasing epoch. Every SetMembership broadcast carries the new epoch, and a node applies it only if it is newer than the one it holds — so a stale or out-of-order broadcast can't move a node's ring backward, and two concurrent topology changes can't both win (the higher epoch supersedes; a losing orchestrator must retry at the next epoch). The membership + epoch are persisted to a small topology file in the data directory, so a node that restarts rejoins with the live ring (the one in effect when it went down) instead of its original bootstrap config. See Node::membership_epoch / member_ids.

How a join works

Node::add_member(id, addr) can be driven from any existing member. It runs three broadcast steps over the internode RPC (internode.rs):

Re-ring everyone. The coordinator computes the new membership (current members + the joiner) and broadcasts SetMembership { members }. Each recipient — and the joiner — rebuilds the identical ring + peer table from the list. Placement is deterministic from the member set, so every node now agrees on who owns what.
Bootstrap the joiner's schema. The coordinator replays its catalog as CREATE DDL (Database::schema_ddl() — tables, then secondary indexes, then vector indexes) to the joiner via ApplyDdl, so the joiner can accept rows and build the same local + vector indexes over its shard.
Migrate the keys. The coordinator broadcasts Rebalance { joiner }. Each existing member scans every table and, for each row whose key the joiner now owns (recomputed against the new ring) and that it is the elected sender for, pushes it to the joiner with the row's original (value | tombstone, HLC) preserved. Tombstones migrate too, so a delete that hasn't compacted away still wins after the move. The push is throttled and resumable: rows are sent in batches (set_migration_throttle(batch, pause_ms) — an engine-internal setting, not an operator one; the operator's knob is the live cluster.bootstrap_duty_pct on each serving member — rate-limits so a large move doesn't saturate the cluster), and a per-joiner checkpoint records progress so an interrupted migration resumes where it left off instead of re-sending from the start (it's idempotent either way). A batch the joiner does not ack is re-sent with backoff (1, 2, 4, 8, 15, 30 s, then once a minute, about five minutes in all; the re-sends go on fresh breaker-bypassing connections with a 30 s deadline each) before the push — and with it the join — fails; the rollback names the attempts. The coordinator waits for every member's push for as long as it takes (an hour's deadline per member, not the ten-second internode one), so step 4 never runs while a member is still pushing; a member whose push failed fails the join, one that does not answer at all is left to repair.
Finalize. The coordinator broadcasts the settled ring (no previous ring unioned in); from then on the joiner is an ordinary replica of its keys.

After step 3 the joiner holds (and indexes) every key the ring assigns it, and reads route to it normally. Because pushed rows keep their original HLC, any write that happened before the move stays correctly ordered under last-writer-wins.

// On a running cluster member:
node.add_member("c", "10.0.0.3:7100")?;   // c joins; its share is migrated to it

How a graceful leave works

Node::remove_member(id) is the inverse of a join and can be driven from any member — including the leaving node itself (self-decommission). It is the same two-phase transition as a join, run in the other direction:

Open the window. The orchestrator broadcasts SetMembership with the smaller ring as the new membership and the current ring as the previous one, to every member including the leaving node. From here a key's owners are the union of both rings: a write that arrives while the drain runs is written to the key's new owner as well as its old ones, and a read consults both — so nothing written mid-drain is missing from the new owner when the node is gone.
Drain. The orchestrator sends the leaving node a Drain carrying the post-removal membership. The leaving node walks every local row and, for each key, computes its owners under the smaller ring; for any owner that was not already a replica under the pre-removal ring (i.e. a node that must pick up this key now), it pushes the row — HLC and tombstone preserved. So every key keeps its full replica set before the node disappears. The drain advances the leaving node's rows_moved counter as it goes.
Finalize. The orchestrator broadcasts the settled smaller ring, so the survivors stop routing to the leaving node, and tells the leaving node it is out. A drain that fails rolls the removal back instead: everyone returns to the old ring at a new epoch and the call returns the drain's error.

After this the leaving node still has its (now unowned) data on disk but serves no key, so it is safe to shut down. Because consistent hashing only reassigns the departing node's keys, a single leave moves about 1/N of the keyspace and touches nothing else. Removing an id that is not a member changes nothing and returns false (the admin response says removed: false, not_a_member: <id>).

node.remove_member("c")?;   // c drains its keys to their new owners, then leaves

Anti-entropy (keeping replicas converged)

Three mechanisms drive replicas toward agreement, so a write that reached only a minority — or a replica that was briefly down — doesn't leave a permanent divergence:

Read-repair. A quorum point read compares the version each replica returned; the winning (highest-HLC) version is written back to any replica that answered with an older or missing one. Reads themselves heal the data.
Hinted handoff. When a replicated write can't reach a replica (it's down), the coordinator buffers the write as a hint (per replica, bounded) and replays it once that replica is reachable again — opportunistically on the next write, or via flush_hints. Faster recovery than waiting for a full repair.
Active anti-entropy (Node::repair / repair_cluster). A background pass reconciles each pair of co-replicas: a merge-join over two paged, key-ordered scans (2,000 rows/page per side) copies the newer version in both directions (tombstones included), so repair memory stays O(page) regardless of table size. This is the durable backstop that converges replicas even with no reads and even if hints were lost. A pass first exchanges each table's content digest (4,096 hash buckets of key ‖ stamp fingerprints, maintained by the engine, compared as of a common cutoff): an equal digest ends the pair in one small RPC, and a differing one restricts the compare to the buckets that differ — both sides walk their shard, but only those buckets' rows cross the wire and enter the merge-join, so a few divergent keys cost a few buckets (about table/4096 rows each) rather than the whole table. The full every-key compare remains as the fallback when the digest exchange fails or the peer predates the verb.

Reclaiming space after a move

A join or leave leaves the former owner holding copies of keys it no longer owns. Node::reclaim frees that space: it walks each local key, and for any key this node is no longer a replica of, it physically purges the key — but only after an actual current owner confirms it holds that key at a version at least as new (the ack-gate, so a key whose migration never completed is never dropped from its last copy). reclaim_cluster fans the cleanup out to every node.

The purge is a real physical drop (Engine::retain), not a tombstone: it rewrites the table keeping only retained keys and discards the rest, so dropped keys vanish from every scan and never resurrect via compaction. With PITR on, the table's sealed WAL segments are archived before the rewrite; a copy the archive refuses defers the purge (the table is left as it was and RECLAIM returns the error — run it again once the archive takes copies) rather than leaving a gap in the archive. That matters because a tombstone would carry a newer HLC than the migrated copy and could (a) re-enter a later migration and delete the key on its new owner, or (b) win an LWW merge and mask the live value elsewhere — a physical purge does neither. Secondary-index entries for purged rows are left dangling; reads already skip an index entry whose row is absent, and they compact away.

node.reclaim()?;          // this node drops keys it no longer owns
node.reclaim_cluster()?;  // …and tells every peer to do the same

Correctness model

LWW is preserved. Migrated rows carry their original HLC, so they neither shadow nor are shadowed by concurrent writes incorrectly — the newest stamp wins as always.
Stale copies are harmless, then reclaimed. Until reclamation runs the former owner keeps its physical copy, but with rf=1 a point read routes only to the new owner via the ring, and with rf>1 a cluster/index read merges by HLC, so the migrated copy (equal or newer) wins or ties — no read returns a lost or resurrected row. Node::reclaim (below) then frees the space.
Idempotent. Rebalance can be re-sent; re-pushing a row at the same HLC is a no-op under LWW. A join that half-completes can be retried.

Assumptions & limitations

Live migration (pending ranges). A join runs as a two-phase transition: it first broadcasts the new ring with the old ring unioned in, so while data is migrating every coordinator treats a migrating key's owners as both its old and new node — writes dual-write to both and reads consult both — then finalizes to drop the old ring. So concurrent writes during a join stay consistent, not just on a quiescent cluster. A graceful removal runs the same transition around its drain. (A node that restarts mid-transition reloads only the finalized-shape ring, since the pending state isn't persisted; the heal below, or re-running add_member, settles an interrupted change.)
Reclamation is a manual pass. reclaim/reclaim_cluster are explicit calls run after a move, not automatic — until then the former owner keeps the (harmless) stale copies. It is a full-table scan with a point-read ack-gate per key; fine after a single reshard, heavier on a very large dataset.
Migration memory is bounded. Rebalance, drain, and reclaim page through each shard (2,000 rows at a time — the same paging as repair and distributed gathers) and stream out in throttled batches, so a topology change against a multi-GB table costs one page plus the in-flight batch, not the shard. The rebalance checkpoint doubles as the page cursor on resume.
Membership has no consensus. Data converges via anti-entropy, but membership changes (SetMembership/Rebalance/Drain) are still best-effort broadcasts. The epoch stops a node from regressing to an older ring and persistence reloads the live ring on restart. A member that missed a broadcast converges by the membership pull: every member's host stats carry its epoch, whether its window is open and its member list, and a node that sees a peer on a newer settled epoch adopts that ring on its next probe of it — the routine host-stats refresh, or the heal tick while it still holds a window — so a rollback or finalize a busy or partitioned member never received reaches it within seconds of its next contact. A peer mid-change (window open) is never adopted from, and an older epoch never is. Concurrent topology changes converge to the highest epoch, but the losing change is dropped.
A persisted ring that does not list the node is foreign. A data directory restored from another member's backup carries that member's topology and hint logs; at start-up a node whose own identity is absent from the persisted ring sets the file aside (topology.foreign), starts from its configured seeds at epoch 0 and discards the hint logs addressed to nodes outside those seeds — it never proposes membership to the cluster the backup came from. See CLUSTER_OPERATIONS.md, "Restoring a backup onto other hosts".
Single sender per key. Only the key's primary under the pre-join ring pushes it during a join, so rf > 1 does not re-send each key from every replica. The trade-off: if that one sender is unreachable mid-join the key isn't migrated until the join is retried (an all-replicas push would be more redundant but more resilient).

Tested

online_resharding_migrates_keys_to_a_joining_node (rf=1, CL=ONE) fills a table on a two-node cluster, joins a third node online, and asserts every row is still readable from every coordinator (so the rows the new node now owns were migrated to it), the secondary index bootstrapped onto the joiner serves a distributed lookup, and a write after the join routes under the new ring.
graceful_decommission_drains_keys_before_leaving (rf=1, CL=ONE) removes a node from a three-node cluster and asserts every key it owned was drained to its new owner (all rows stay readable from the survivors) and that writes after the leave route under the smaller ring.
reclaim_drops_unowned_keys_after_join (rf=1) joins a node, then has the former owners reclaim; it asserts space is actually freed (rows dropped > 0), no row is lost, and a second pass is a no-op (idempotent). The storage-level retain_physically_drops_keys_without_resurrection checks the purge leaves no tombstone and survives reopen.
membership_persists_across_restart_and_rejects_stale_epoch joins a node, then restarts a peer from its data dir with the stale bootstrap config and asserts it reloads the live ring at the right epoch, and that a stale (lower-epoch) SetMembership is ignored.
rf2_join_migrates_via_single_sender (rf=2) joins a third node and verifies every row is readable, exercising migration under replication.
read_repair_and_anti_entropy_converge_replicas (rf=3) injects divergence on specific replicas and checks that a quorum read repairs the missing one, and that repair reconciles both push and pull directions.
hinted_handoff_replays_to_a_recovered_replica (rf=3, CL=ALL) writes while a replica is down (buffering a hint), then recovers it and checks flush_hints hands the write off.
pending_ranges_dual_write_to_old_and_new_owner (rf=1, CL=ALL) imposes a ring transition and checks a write to a migrating key lands on both its old and new owner.
throttled_migration_completes_and_clears_checkpoint joins a node with a tiny batch size + pause and checks everything migrates and the resume checkpoint is removed; migrate_checkpoint_roundtrips covers the checkpoint codec.
join_rides_out_unacked_migration_batches_and_reports_the_retries_when_it_gives_up (rf=1) joins a node that refuses the first three batches and asserts the join still completes; then one that never acks, and asserts the rollback names the attempts.
writes_during_a_graceful_removals_drain_reach_the_keys_new_owner (rf=1, QUORUM writes) writes continuously while a slowed drain runs and asserts every acked row is readable at ONE from both survivors the moment remove_member returns, and that the survivors' counts agree.
an_abandoned_removal_window_is_rolled_back_by_a_survivor opens a removal window with no coordinator and asserts a survivor rolls it back past the grace while the leaving node never heals its own departure.
heal_progress_clock_keeps_a_peers_last_good_reading_through_a_missed_probe asserts a busy peer's failed stats probe does not re-arm the heal's grace.
a_member_that_missed_a_broadcast_adopts_the_newer_settled_ring_from_a_peer covers the membership pull: a stale dual ring adopts a peer's rollback from the heal tick, a missed finalize from the host-stats refresh, and nothing is adopted from a peer mid-change or at an older epoch.
announcer_keeps_announcing_after_a_join_it_was_admitted_through_rolls_back asserts a joiner listed by the begin broadcast announces again after the rollback and ends in a finalized ring.
wiped_member_is_resyncing_before_serving_and_never_answers_partial_counts (rf=3) starts a member on an empty directory and asserts it is resyncing before serving, that count(*) through it at ONE, QUORUM and ALL equals the true count throughout its backfill, and that the flag clears when the catch-up completes.
a_data_dir_restored_from_another_clusters_member_ignores_its_topology_and_hints starts a node on a directory holding another cluster's topology and hint logs and asserts the source cluster's ring is never touched.
backup_cluster_is_refused_while_a_membership_change_is_in_flight asserts the refusal on the coordinator's view and on a member's.

Driving ring changes from an orchestrator

POST /admin/add-node / POST /admin/remove-node are synchronous — the HTTP response returns after the migration completes and the membership finalizes — but an orchestrator should not rely on holding one HTTP connection through a long migration. Poll GET /admin/resharding (ADMIN): {active, epoch, rows_moved}. active is the dual-ring transition window — open for a join's migration and for a graceful removal's drain alike; active:false is the reliable "resharding finished" edge, and epoch is the membership version that committed. rows_moved is the answering node's cumulative migrated-row counter — rows it pushed to joiners plus rows it drained as a leaving node (no byte totals are tracked).

Idempotency contract: re-adding an existing member is a no-op — and when the open window is that node's OWN stuck join (it is the one node the window adds), the re-add finalizes it. While a DIFFERENT membership change is open (another joiner, a removal) the re-add is refused with HTTP 400, <id> is already a member; another membership change is in progress …: an orchestrator's reconcile loop should treat that as "retry later", not as fatal. Removing an absent id is Ok and answers removed: false, not_a_member: <id>. A change whose coordinator died after its begin broadcast is also healed without an operator: once the window has been open for ten minutes with no migration progress on any member — each member's rows_moved counter, read from its host stats and judged on its last good reading, so a busy member's missed probe is not progress — a surviving member re-drives a join (schema bootstrap, migration, finalize, each step idempotent) if the joiner still answers, rolls it back to the old ring if it does not, and rolls an abandoned removal back (the leaving node still holds every key it owned; run the removal again). A member that sits on a stale window because it missed the rollback or finalize adopts the newer settled epoch from the first peer it probes (the membership pull) rather than waiting out the grace. A change in progress never looks abandoned: it moves rows or finishes well inside that grace. A new add or remove while a transition window is open is refused with resharding in progress (epoch N) — poll until active:false, then retry. BACKUP CLUSTER is refused for the same window (cluster backup refused: …).

Failure contract: an add-node that fails after its begin broadcast (joiner unreachable, its schema bootstrap refused after the busy retries, a migration batch unacked after its ~5 minutes of re-sends, a member's push failed, a current member that did not take the begin broadcast or did not answer right before the finalize) rolls back — every member returns to the previous ring at a new epoch, the joiner is told it is out, and the error says so (… — join rolled back (epoch N), naming the attempts when a batch was the cause). active is therefore false again as soon as the call returns; retry the add when the cause is fixed (a retried join resumes from its migration checkpoint).

Every current member must answer before a join finalizes. Before it opens the window, add-node probes every member of the current ring (5 s, concurrently, on connections that bypass an open circuit breaker); if any is silent the join is refused with nothing changed anywhere: join of <id> refused: member <m> did not answer a liveness probe; every current member must answer before a join finalizes. Bring it back and retry, or remove it first with ALTER CLUSTER REMOVE NODE '<m>' FORCE (nothing was changed) (one REMOVE NODE command per silent member). A member that does not take the begin broadcast rolls the join back with the same naming, and the probe runs again right before the finalize (a member lost during the migration rolls it back too). A member whose share of the migration push did not answer is handled as before: its keys reach the joiner by repair. Once the coordinator has adopted the finalize the join is committed and never rolled back (from then on writes place by the new ring, at rf=1 possibly on the joiner alone): a member that misses or acks the finalize late adopts the settled ring by the membership pull. A survivor healing an abandoned join (above) does not run the pre-finalize probe — it completes the join as before. A joiner's auto-announce keeps retrying, so it is admitted on its own once the member is back (or force-removed). Witnesses are not ring members (they pull from a member and own no placement), so they are not probed and a down witness never blocks a join. remove-node refuses a node it cannot drain (leaving node unreachable) and rolls its window back; pass {"force":true} to drop it without draining — allowed even while a transition is open (it closes it) or while a graceful removal of the same node is parked on its drain (that one returns aborted by a forced removal). Follow a forced removal with /admin/repair.