Partitioning & Sharding

Secondary indexes under partitioning: local indexes make every index read a fan-out to all shards (tail amplification, Module 02); global indexes make reads targeted but turn one logical write into multi-shard writes. Pick per access pattern.

shard = hash(key) % N looks obviously right and fails catastrophically at the worst moment: change N and almost every key remaps — a self-inflicted cache avalanche or a full-cluster data migration, triggered by adding capacity. Consistent hashing fixes it: nodes and keys hash onto a ring; a key belongs to the next node clockwise; adding a node steals only ~1/N of the keyspace, from its neighbors alone. Virtual nodes (100–256 tokens per physical node) smooth the statistical imbalance and let heterogeneous hardware take proportional load.

Production systems mostly don't hash straight to nodes — they hash to a fixed pool of partitions, then map partitions → nodes. Rebalancing becomes moving whole partitions, and the key→partition mapping never changes:

• Redis Cluster: 16,384 hash slots; CRC16(key) % 16384 → slot; slots assigned to nodes; resharding = migrating slots live. Hash tags {user42}:profile / {user42}:sessions force related keys into one slot — the prerequisite for multi-key ops and Lua across them.
• Kafka: partitions are the parallelism unit; consumers rebalance partition ownership. Partition count is quasi-permanent — changing it breaks key→partition affinity and thus per-key ordering, so over-provision partitions on day one.
• Dynamic splitting (HBase/Mongo/Dynamo): partitions split when hot or large; handles growth automatically, but a split of a hot partition happens during the heat.

Rules regardless of system: rebalancing must be throttled (moving data competes with serving it — untuned rebalancing is a self-inflicted incident), resumable, and never automatic on mere node-unreachability — a GC pause misread as node death triggers a data-movement storm that causes the real outage.

Perfect key distribution ≠ perfect load distribution: keys aren't equally popular. One live-final manifest, one trending series — Zipfian reality means one shard melts while others idle. Salting spreads a hot key across shards at the cost of read-side aggregation:

• Write salting: append rand(0,K) to the hot key; reads fan to all K and merge. Trades one hot shard for K-way read amplification — apply only to identified hot keys.
• Read replication: copy the hot value to K suffixed keys; read one at random. For read-hot/write-rare data (manifests) this is usually the right first move.
• The layered answer (from Module 01): the best fix for a read-hot key is not sharding at all — L1/CDN absorbs it before the shard sees it. Salting is for write-hot or uncacheable keys.
• Detection first: per-key traffic metrics (Redis --hotkeys, per-slot QPS). You can't salt what you haven't spotted, and the World Cup won't wait while you add instrumentation.

• Scatter-gather: query all shards, merge. p99 = max over shards → Module 02's 1−(1−p)ᴺ applies to your own database.
• Joins: co-locate rows that join (same partition key) or denormalize at write time. Cross-shard joins in the request path are how sharded systems die slowly.
• Transactions: single-shard ACID survives; cross-shard needs 2PC (blocking, coordinator SPOF) or Sagas with compensation — full module in Week 3.
• IDs: auto-increment dies with sharding; use Snowflake-style (timestamp | node | sequence) or UUIDv7 for index-friendly ordering.

public class ConsistentHashRing<N> {
  private final TreeMap<Long, N> ring = new TreeMap<>();
  private final int vnodes;                       // 100–256 in practice

  public void addNode(N node) {
    for (int v = 0; v < vnodes; v++)
      ring.put(hash(node + "#" + v), node);      // murmur3/xxHash — NOT hashCode()
  }
  public void removeNode(N node) {
    for (int v = 0; v < vnodes; v++) ring.remove(hash(node + "#" + v));
  }
  public N nodeFor(String key) {
    var e = ring.ceilingEntry(hash(key));          // next node clockwise…
    return (e != null ? e : ring.firstEntry()).getValue(); // …wrapping the ring
  }
}

// Redis Cluster co-location: hash tags force one slot → multi-key ops legal
redis.opsForValue().multiSet(Map.of(
    "{user:42}:profile",  profileJson,
    "{user:42}:sessions", sessionsJson));   // same slot: only {user:42} is hashed

Fast trackStep 2 only (~40 min): building the ring and measuring 80% vs 20% remap with your own code makes the argument permanent.

Self-check