Databases at Scale

Sharding & Partitioning

Splitting a dataset across multiple machines so no single node has to hold — or serve — all of it. The entire discipline reduces to one question: which key decides where a row lives, and does that choice spread load evenly?

Range partitioning: contiguous key ranges per shard — great for range scans, terrible when writes cluster at the "current" end (e.g. timestamps)
Hash partitioning: hash(key) mod N spreads keys evenly but destroys range-scan locality and makes resharding expensive without consistent hashing
Consistent hashing minimizes data movement on resharding — adding a node only reshuffles ~1/N of the keys instead of nearly everything
A poorly chosen shard key creates a hot shard: one celebrity user, one viral post, or one popular SKU can overload a single node while the rest sit idle
Cross-shard queries (joins, transactions, aggregates) are the recurring cost — they either fan out to every shard or are designed away entirely

A request routed to its shard by hashed key

The router (or a client-side library) must apply the exact same hash function everywhere

A minimal consistent-hashing ring

class ConsistentHashRing {
    private final TreeMap<Long, String> ring = new TreeMap<>();
    private final int vnodesPerNode = 100; // virtual nodes smooth the distribution

    void addNode(String node) {
        for (int i = 0; i < vnodesPerNode; i++) {
            ring.put(hash(node + "#" + i), node);
        }
    }

    String nodeFor(String key) {
        long h = hash(key);
        var entry = ring.ceilingEntry(h);           // first node clockwise from h
        return entry != null ? entry.getValue() : ring.firstEntry().getValue();
    }

    private long hash(String s) {
        return java.util.zip.CRC32C.class.hashCode() ^ s.hashCode(); // stand-in for a real 64-bit hash
    }
}

Virtual nodes (vnodes) prevent one physical node from owning a disproportionate arc of the ring