Fixed Slot Sharding Design

[seonWKim]

Concept

Pre-define N stable shard IDs (ShardId(u16), e.g. 0..1023 or bigger). The existing vNode ring does not define shards — it only resolves which physical node currently hosts each shard.

Resource → hash(key) % N → ShardId   (stable, permanent)
ShardId  → ring walk      → NodeId   (dynamic, changes with cluster membership)

Shards are named buckets that float across physical nodes. The bucket identity is fixed; its physical location is not.

Resources (topics, ranges, segments) store a ShardId at creation time and never need to update it — only the hosting node changes.

---

Node Add / Remove Scenario

Node D joins

1. D's vNodes are inserted into the ring at deterministic positions (hash(D_id + replica_index)).
2. Some shards now resolve to D via the clockwise ring walk — D becomes their new leader.
3. D pulls state for those shards from the previous leader or an existing replica.
4. Resources referencing those ShardIds require no update — only the physical host changed.

Node A leaves (or is declared Dead by SWIM)

1. A's vNodes are removed from the ring.
2. Affected shards promote the next clockwise replica to leader automatically.
3. No ShardId changes, no resource metadata updates required.

---

Resharding (Changing N)

This is the primary operational risk of the fixed slot model.

shard_for(key) = hash(key) % N

When N changes, the modulo changes — nearly all keys remap to different shards:

4 → 5 shards: ~83% of keys remap
8 → 9 shards: ~89% of keys remap

But we can mitigate it by overprovisioning at init time and never resize. We need to discuss whether this constraint is OK.

---

Pros and Cons

Pros

• Resources reference a stable ShardId — no updates needed when nodes join or leave.
• Clean operational story: "Shard 42 migrated from Node A to Node D."
• The existing vNode ring handles all physical owner resolution unchanged.
• Simple to reason about shard placement and replication.

Cons

• Modulo hashing makes post-launch resharding catastrophic without a mitigation strategy.
• N must be chosen carefully at cluster initialization.
• Adds an abstraction layer on top of vNodes — slightly more indirection.

---

Relation to Existing Topology

The vNode ring (TokenRing, Topology) is reused as-is. A new ShardTable wraps it:

ShardTable {
    num_shards: u16,
    topology: Topology,
    replication_factor: usize,
}

ShardTable::shard_for(key)    → ShardId          // hash(key) % num_shards
ShardTable::shard_info(sid)   → ShardInfo {       // ring walk from hash(sid)
    leader: NodeId,
    replicas: Vec<NodeId>,
}

token_owners_for in Topology continues to drive leader + replica resolution.
ShardTable is the only new type needed to implement this model.