Database Sharding — Where Single-Box Ends, Regret BeginsSharding: Hash vs Range, Consistent Hashing, Hot Spots, Resharding

The Problem

"Add a box, take 10× the traffic" — the rookie fantasy of sharding. The reality: sharding is irreversible architectural debt. Once you shard, you lose cross-shard transactions, you lose multi-table joins, you lose automatic secondary indexes. What you gain is "scale forever" and "every schema change is a nightmare."

So why do it? Because single boxes have hard ceilings: Postgres writes ~50k QPS at ~10TB; MySQL InnoDB buffer pool tops out at a few hundred GB; vertical CPU/RAM/SSD pricing curves go nonlinear (r6i.32xlarge runs ~$8k/month, and there's no SKU above that). When the single box won't do it, sharding becomes inevitable. The question isn't whether — it's when, how, and how you'll redo it.

Counter-examples: Foursquare 2010, a MongoDB shard ran out of space; a node OOMed during migration and the whole cluster cascaded — 11 hours down. Slack's first reshard in 2017 took 9 months (sharded by team_id; hot workspaces stayed skewed). Notion's 2021 split from one Postgres to 32 shards took half a year, and in 2023 they split again from 32 to 480.

Requirements and Constraints (the interview opener)

• Current scale and growth: data size, write QPS, read QPS, growth rate. If you won't exceed single-box limits within a year, don't shard.
• Dominant access pattern: which key does 90% of your queries use? That's your shard-key candidate.
• Cross-shard query fraction: if 30% of queries fan out to every shard, sharding barely helps.
• Data distribution: are tenants / users / orders uniform in size, or long-tailed? Long tail = hot-shard risk.
• Transaction requirements: many cross-user or cross-tenant transactions? Those have to become sagas or eventual consistency after sharding.
• Future resharding cost: can you accept 1–2 resharding rounds (months of engineering each), or do you want consistent hashing to dodge them from day one?
• Operational maturity: roll your own application-side sharding? Vitess (MySQL) or Citus (Postgres)? Or jump straight to distributed SQL (TiDB / CockroachDB)?

High-Level Architecture

graph TD
    APP["Application"]
    PROXY["Shard Router
Vitess vtgate / app layer / Citus coordinator"]
    META["Shard Metadata
ZK / etcd / config DB"]

    S1[("Shard 0
user_id % 16 == 0")]
    S2[("Shard 1
user_id % 16 == 1")]
    S3[("...")]
    SN[("Shard 15
user_id % 16 == 15")]

    R1[("Shard 0
Replica")]
    R2[("Shard 1
Replica")]

    APP --> PROXY
    PROXY -.read routing table.-> META
    PROXY --> S1
    PROXY --> S2
    PROXY --> S3
    PROXY --> SN
    S1 -.async repl.-> R1
    S2 -.async repl.-> R2

    classDef app fill:#1a2530,stroke:#64c8ff,color:#e8eef5
    classDef proxy fill:#2a1530,stroke:#ff7ab6,color:#e8eef5
    classDef meta fill:#1a1a30,stroke:#ffb450,color:#e8eef5
    classDef shard fill:#0e2030,stroke:#5eead4,color:#e8eef5
    class APP app
    class PROXY proxy
    class META meta
    class S1,S2,S3,SN,R1,R2 shard

Three layers: application → router (looks up metadata to pick a shard) → physical shards (each with its own primary/replica)

Key Technical Points

1. Hash Sharding vs Range Sharding: The Triangle of Performance, Hot Spots, and Cross-Shard Queries

Principle: the two basic strategies, deciding how data maps to physical nodes.

# Simple hash sharding (application layer)
import hashlib
NUM_SHARDS = 16

def shard_of(user_id: int) -> int:
    h = hashlib.md5(str(user_id).encode()).digest()
    return int.from_bytes(h[:4], 'big') % NUM_SHARDS

def get_conn(user_id):
    return shard_pool[shard_of(user_id)]

# ⚠️ don't use Python's built-in hash() — inconsistent across processes (PYTHONHASHSEED)
# ⚠️ don't do user_id % N directly — if user_id is monotonically generated and N is small,
#    new users cluster into a few shards

2. Consistent Hashing: So Adding a Node Doesn't Move Everything

Principle: naive hash(key) % N moves almost every key when N changes (N: 8→9 remaps ~88% of keys). Consistent hashing visualizes the hash space as a ring (0 to 2^32); nodes and keys both map onto it; a key walks clockwise to the first node. Adding or removing a node only affects the slice between two neighbors.

graph LR
    subgraph Ring["Hash Ring (2^32)"]
        direction LR
        N1["Node A
vnode 0..200"]
        N2["Node B
vnode 201..400"]
        N3["Node C
vnode 401..600"]
        N4["Node D (new)
only takes over
this slice"]
    end
    K1["key1 hash=150"] --> N1
    K2["key2 hash=350"] --> N2
    K3["key3 hash=480"] --> N3
    K4["key4 hash=270"] --> N4
    classDef node fill:#0e2030,stroke:#5eead4,color:#e8eef5
    classDef key fill:#1a1a30,stroke:#ffb450,color:#e8eef5
    classDef new fill:#2a1530,stroke:#ff7ab6,color:#e8eef5
    class N1,N2,N3 node
    class K1,K2,K3,K4 key
    class N4 new

But naive consistent hashing skews when nodes aren't evenly distributed. Virtual nodes (vnodes) fix this — each physical node owns 100–200 virtual points on the ring, statistically smoother; removing a node spreads its load evenly to all others rather than dumping on a single neighbor.

# Simplified consistent hashing (with vnodes)
import bisect, hashlib

class ConsistentHash:
    def __init__(self, nodes, vnodes=150):
        self.ring = []        # sorted list of (hash, node)
        self.vnodes = vnodes
        for n in nodes:
            self.add_node(n)

    def _h(self, key):
        return int(hashlib.md5(key.encode()).hexdigest(), 16)

    def add_node(self, node):
        for i in range(self.vnodes):
            h = self._h(f"{node}#{i}")
            bisect.insort(self.ring, (h, node))

    def get(self, key):
        h = self._h(key)
        i = bisect.bisect(self.ring, (h, ''))
        return self.ring[i % len(self.ring)][1]

# Add one node (N → N+1), remap ratio ≈ 1/(N+1)
# Naive mod: remap ratio ≈ N/(N+1)

3. Hot Spots: Why "Uniform" Sharding Still Gets Crushed

Principle: "statistically uniform" ≠ "uniform in production." Three classes of hot spot:

1. Key hot: one key takes too much traffic (a celebrity with 100M followers, a viral product at 100k QPS). No matter how good the hash, that key stays on one shard.
2. Range hot: under range sharding, "the newest data" concentrates (timestamp shard key → all writes go to the last shard).
3. Tenant hot: in multi-tenant systems, big customers (Salesforce in Slack, Adobe in Notion) take 90% of one shard.

Mitigations:

# Salting example: follower table for a write-heavy celebrity account
# Original schema:
#   follower(celebrity_id, follower_id, ts)  partition by celebrity_id
# Problem: celebrity_id=42 (Elon) writes at 50k QPS, far past the 1000 WCU per-partition cap

# Fix: append a hash suffix
shard_suffix = random.randint(0, 15)
write(table, partition=f"42#{shard_suffix}", row={...})

# On read, fan out
results = []
for i in range(16):
    results += query(partition=f"42#{i}")
return merge_sort_by_ts(results)

# Trade-off: 16× read amplification; but the write problem is solved
# Fits write >> read; not the reverse

4. Resharding: The Engineering Nightmare from 32 to 480 Shards

Principle: resharding is among the most painful distributed-systems operations because it must: (a) move data from the old topology to the new; (b) not interrupt the business; (c) be strongly consistent across cutover; (d) be reversible if it goes wrong. Any resharding without shadow read/write and a rollback plan is gambling.

sequenceDiagram
    participant App
    participant Router
    participant Old as Old Shard (16)
    participant New as New Shard (32)

    Note over Router: Phase 1 · dual write
    App->>Router: write k1
    Router->>Old: write k1 (primary)
    Router->>New: write k1 (shadow, async)

    Note over Router: Phase 2 · backfill history
    Router-->>New: background copy: snapshot + CDC

    Note over Router: Phase 3 · shadow-read validation
    App->>Router: read k1
    Router->>Old: read (returned to user)
    Router->>New: read (compare, not returned)
    Note right of Router: diff > threshold → halt cutover

    Note over Router: Phase 4 · cutover (gradual %)
    App->>Router: write k1
    Router->>New: write k1 (primary)
    Router->>Old: write k1 (mirror, backup)

    Note over Router: Phase 5 · teardown / drop old data

# Resharding key idea: idempotent dual write + version stamp
def write(key, value):
    version = current_ms()
    # dual write with version, so old values can't overwrite new ones
    write_old(key, value, version)
    if reshard_phase >= DUAL_WRITE:
        try:
            write_new(key, value, version)  # if-newer
        except Exception as e:
            log_drift(key, e)   # alert, do not block the main path

def read(key):
    if reshard_phase == SHADOW_READ:
        v_old = read_old(key)
        v_new = read_new(key)
        if v_old != v_new:
            metrics.diff_count.inc()
            log_diff(key, v_old, v_new)
        return v_old  # still return old until cutover
    elif reshard_phase >= CUTOVER:
        return read_new(key)
    else:
        return read_old(key)

Scaling Up: What to Do After Growth

• Picking the shard key matters more than picking the database. The wrong shard key is a debt you carry forever. Principles: high cardinality (good distribution), aligned with the dominant query pattern (90% of queries carry the key), stable over time (doesn't migrate from one value to another).
• Co-location: keep related data in the same shard. Pinterest co-locates boards and pins with the user shard; Citus uses colocation groups; Vitess uses keyspaces + sequences. User-dimension transactions and joins complete on a single shard.
• Cross-shard secondary indexes: either maintain a global index table at the app layer (synchronous dual write), or push to external search (Elasticsearch, a reverse-index service). Strongly consistent cross-shard indexes are expensive.
• Cross-shard joins / aggregation: give up real-time joins; analyze via CDC → warehouse; turn interactive APIs into fan-out + application-layer merge (cap at K shards).
• Capacity planning at 2× headroom: keep each shard under 50% utilization, otherwise resharding can't keep up. The Foursquare lesson.
• Many more logical shards than physical instances (1024 vs 32): scale by moving logical shards, never by changing the routing function, with zero application changes.

Common Pitfalls

Sample Interview Questions

1. Designing Twitter: how do you shard the tweets table — user_id or tweet_id? Why? What problem does each have?
2. Explain consistent hashing and vnodes; use an "adding a node" scenario to contrast mod hash vs consistent hash migration ratios.
3. A DynamoDB partition suddenly throttles (hot partition) and you can't change the schema. How many mitigations can you list?
4. Designing a multi-tenant SaaS, one customer spikes to 30% of platform traffic. How do you "move them out" invisibly?
5. What are the key phases of online resharding? How do you detect data drift during dual write?
6. Why provision many more logical shards than physical instances? Use a concrete scale-out scenario to show the benefit.

Key Resources

• Designing Data-Intensive Applications, Ch. 6 — Partitioning (Kleppmann): the canonical discussion of hash/range, secondary indexes, and resharding.
• Notion engineering blog, "Sharding Postgres" (2021) and "The Great Re-shard" (2023): full retrospective of single DB → 32 shards → 480 shards, including the logical-over-physical design.
• Vitess docs + Slack blog "Scaling Datastores at Slack with Vitess": an industrial reference for horizontal MySQL scale.

English Summary

Sharding is irreversible architectural debt — you trade away cross-shard transactions, joins, and global secondary indexes for unbounded horizontal scale. Two basic strategies: hash sharding distributes evenly but kills range scans; range sharding preserves locality but creates hotspots on monotonically increasing keys. Consistent hashing with virtual nodes minimizes data movement when adding/removing nodes — N→N+1 moves only 1/N of keys versus ~N/(N+1) with naive mod-hash. Hot spots are inevitable: celebrity accounts, tenant whales, and time-series tails all break statistical uniformity. Mitigations include salting, dedicated shards, adaptive capacity, and caching. Modern best practice is logical-over-physical sharding: provision many more logical shards (e.g., 1024) than physical instances, so scaling out is just migrating logical shards without changing the routing hash. Online resharding requires dual writes, shadow reads, and gradual cutover; expect 3–9 months of engineering. Default to vertical scale and read replicas first — only shard when you must.

Going Deeper (click to expand)