Partitioning & Load

Why this module exists

Scaling a distributed database requires two things at the same time:

• stable key placement as cluster membership changes,
• balanced load so no node becomes a hotspot.

Many systems get one right and the other wrong.

Problem decomposition

Partitioning and balancing are related but different:

1. Placement: given a key, which node owns it?
2. Replication placement: which additional nodes hold replicas?
3. Rebalancing: how do we move data when load drifts?

This module builds these layers progressively.

Consistent hashing refresher

Map tokens and keys onto the same ring. Primary owner for a key is first token clockwise (>= key), wrapping to smallest position when needed.

Why this helps:

• node join/leave moves only a subset of keys,
• no global remap like modulo hashing.

Token freshness and determinism

Real rings contain duplicates and unsorted token lists (virtual nodes, metadata replay, control-plane races).

You need deterministic tie-breaking rules for:

• duplicate positions,
• duplicate node entries,
• wrap-around boundaries.

Without deterministic behavior, clients can disagree on ownership.

Replica-set selection

Primary ownership is not enough; production systems replicate. Replica selection on ring walk must satisfy:

• distinct nodes,
• deterministic order,
• optional failure-domain spread (rack/zone awareness).

If you pick replicas naively, you can place multiple copies in one failure domain and lose availability during zonal outages.

Virtual nodes and skew

Virtual nodes improve balance by spreading each physical node across ring points. But skew still happens due to:

• non-uniform key popularity,
• uneven shard sizes,
• temporal hotspots.

Result: ring balance and runtime load balance can diverge.

Rebalancing as constrained optimization

Rebalancing is not "move largest shard repeatedly" in production. It is constrained by:

• move cost (network and I/O),
• move budget per interval,
• immovable/pinned shards,
• diminishing returns (avoid oscillation).

A practical planner chooses moves that improve imbalance monotonically and stops when no safe improvement exists.

Tradeoffs you must manage

• Fast rebalancing vs service disruption.
• Aggressive hotspot mitigation vs excessive data churn.
• Strict domain diversity vs latency/placement constraints.

Good systems expose these as explicit policies, not hidden heuristics.

Common implementation mistakes

• ring lookup without wrap-around correctness,
• replica selection that repeats same node under virtual tokens,
• deterministic tie-break violations across processes,
• rebalancing that increases global gap after a move,
• infinite or oscillating rebalance loops.

What you will build (progressive sequence)

1. Consistent-hash ownership resolver Deterministic owner lookup with wrap and tie semantics.
2. Failure-domain-aware replica planner Ring walk selection of distinct replica nodes with zone preference.
3. Constrained rebalance planner (capstone) Generate shard moves under budgets and constraints while monotonically improving global imbalance.

By the end, you should be able to reason about placement and balancing as policy-driven planners rather than ad-hoc ring tricks.