Partitioning Schemes: Range, Hash, Consistent Hash, Directory

TL;DR. Every horizontal-scale database partitions data, and the scheme it picks determines which queries are cheap, which are expensive, and how painful rebalancing is. Hash partitioning (DynamoDB, Redis Cluster) spreads load uniformly but kills range scans. Range partitioning (CockroachDB, HBase, TiKV) makes range scans cheap but creates hot tails on sequential writes. Consistent hashing (Cassandra, Dynamo) minimizes data movement when nodes join or leave. Directory-based (Vitess) gives per-tenant placement flexibility at the cost of a lookup hop. Default to hash with a composite key (partition key + sort key) for most workloads; escalate to range only when range scans dominate, and add a directory layer when whale tenants need isolation.

Learning Objectives

• Compare range, hash, consistent hash, and directory partitioning across query support, rebalance cost, and hot-spot risk.
• Identify the workload characteristics that favor each scheme.
• Justify a composite-key hybrid that combines hash distribution with in-partition range locality.
• Evaluate real systems (DynamoDB, CockroachDB, Redis Cluster, Vitess) and explain why each chose its scheme.

The Core Trade-off

The fundamental tension is even distribution versus locality. Hash partitioning destroys key ordering to spread load uniformly, so range scans like “all events in the last hour” must fan out to every partition¹. Range partitioning preserves order and makes those scans cheap, but sequential writes (timestamps, autoincrement IDs) pile onto the newest range, creating a hot tail²³.

A secondary tension is rebalance cost. Naive hash(key) % N remaps nearly every key when N changes. Consistent hashing moves only K/N keys when one node joins or leaves⁴. Directory-based schemes move nothing until you explicitly reassign a tenant, but add a lookup hop and a critical-path dependency on the directory service⁵.

No scheme wins on all axes. The decision depends on whether your dominant access pattern is point lookups, range scans, or dynamic membership changes.

flowchart TD
    Key["Incoming key"] --> Scheme{"Partitioning scheme?"}
    Scheme -->|Range| R["Lookup sorted range,<br/>route to owning node"]
    Scheme -->|Hash + fixed slots| H["slot = CRC16(key) mod 16384"]
    Scheme -->|Consistent hash| C["Walk ring clockwise<br/>to successor node"]
    Scheme -->|Directory| D["Query lookup service<br/>for tenant placement"]
    R --> Pro1["Pro: cheap range scans<br/>Con: hot tail"]
    H --> Pro2["Pro: uniform spread<br/>Con: no range queries"]
    C --> Pro3["Pro: minimal rebalance<br/>Con: variance without vnodes"]
    D --> Pro4["Pro: per-tenant flexibility<br/>Con: lookup hop + SPOF"]

Side-by-Side Comparison

The table understates one thing: rebalance cost is never zero. Even CockroachDB’s metadata-only split is followed by replica rebalancing that streams Pebble data to new nodes during Raft reconfiguration¹³. And consistent hashing’s K/N guarantee means that adding one node to a 10-node cluster still moves 10% of all data, which at petabyte scale is terabytes of network transfer.

The “scale ceiling” row matters more than it appears. Redis Cluster’s specification recommends a maximum of roughly 1,000 nodes, though the 16,384 slots set a theoretical upper bound of 16,384 masters⁷. If you need more, you need a different scheme or a tiered architecture.

When to Pick Hash Partitioning

Point lookups dominate and range queries are rare or report-only. User profiles by ID, session stores, key-value caches. DynamoDB’s partition key hash gives uniform distribution across millions of operations per second¹.

You need predictable write distribution. Hash destroys ordering, which means sequential timestamps do not pile onto one partition. Redis Cluster’s CRC16 mod 16,384 spreads keys evenly regardless of input pattern⁷.

The cluster size is stable. Fixed-slot schemes (Redis Cluster’s 16,384 slots, Cassandra’s vnodes) handle membership changes gracefully because slots, not keys, are reassigned⁸. But if you are using naive modulo without pre-sharding, adding a node remaps almost everything¹⁴.

Composite keys give you the best of both. DynamoDB’s partition key + sort key hashes the first to pick a partition, then keeps the second in sorted order within it. Point lookups and in-partition range scans are both cheap¹⁵.

When to Pick Range Partitioning

Range scans are first-class queries. Time-series data (“all events between 09:00 and 10:00”), lexicographic prefix scans (“all users whose name starts with ‘Sm’”), and ordered pagination. CockroachDB and TiKV serve these from one or two ranges without fan-out²³.

Automatic splitting adapts to growth. CockroachDB splits ranges at 512 MiB¹⁶; TiKV at 96 MB³; HBase at 10 GB¹⁷. No operator intervention needed as data grows.

You can mitigate the hot tail. Prefix the timestamp with a tenant ID or bucket number so writes spread across ranges. CockroachDB offers hash-sharded indexes as an opt-in escape hatch for sequential workloads¹⁰.

Caution: If your primary key is a monotonic timestamp with no prefix, every write lands on the last range. This is the single most common partitioning mistake in production.

When to Pick Consistent Hashing

Dynamic membership is the norm. Cache clusters where nodes join and leave hourly. CDN edge servers. Dynamo-style storage where nodes churn. Consistent hashing moves only K/N keys per membership change⁴¹⁸.

You need minimal disruption during scale-out. Adding a node to a 100-node Cassandra cluster moves roughly 1% of data, not 99%¹⁴.

Virtual nodes smooth the variance. Without vnodes, some nodes get roughly 2x the average load¹⁹. Cassandra 3.x defaulted to 256 vnodes per node; Cassandra 4.0+ defaults to 16⁸. Jump consistent hash (Lamping and Veach, 2014) achieves perfect balance in O(ln N) time with zero memory²⁰. Bounded-load consistent hashing caps any node at (1 + epsilon) times the mean¹².

When to Pick Directory-Based Partitioning

Per-tenant placement flexibility is non-negotiable. Multi-tenant SaaS where a whale customer needs a dedicated shard, or where compliance requires data residency in a specific region. The directory maps tenant_id to a shard with full freedom⁵.

Heterogeneous shards are acceptable. Some shards are larger, some have more replicas, some run on beefier hardware. The directory encodes all of this without constraining the hash function.

You can tolerate the operational weight. The directory is itself a critical service. It must be highly available, cached aggressively, and consistent. Vitess’s vtgate consults the VSchema on every query⁶. If the directory is down, routing is down.

The Hybrid Path

Most production systems combine two or more schemes. The dominant pattern is pre-sharded virtual partitions mapped by consistent hashing, with a directory for known heavy tenants.

DynamoDB hashes the partition key to pick one of many internal partitions, uses adaptive capacity to redistribute headroom, and splits hot partitions automatically¹. Cassandra assigns vnodes per physical node on a consistent-hash ring (256 in 3.x, 16 in 4.0+)⁸. Vitess uses a directory (VSchema) to map rows to shards via a configurable vindex, with keyrange-based routing⁶.

The composite-key pattern (hash the partition key, sort within it) is the most broadly applicable hybrid. It gives you hash-level load spreading for writes and range-level locality for reads within a logical group¹⁵.

flowchart LR
    subgraph Hybrid["Composite key: hash + sort"]
        PK["Partition key<br/>(hashed for distribution)"]
        SK["Sort key<br/>(ordered within partition)"]
        PK --> Partition["Partition N"]
        SK --> Partition
    end
    subgraph Within["Within partition N"]
        direction TB
        R1["sk=2026-01-01"] --> R2["sk=2026-01-02"] --> R3["sk=2026-01-03"]
    end
    Partition --> Within

Real-World Examples

DynamoDB hashes partition keys to spread millions of ops/sec across internal partitions, each capped at 3,000 RCUs and 1,000 WCUs¹⁵. When a partition overheats, split-for-heat divides it, but only if the sort key has enough cardinality to benefit. An ever-increasing sort key with a low-cardinality partition key caps throughput at 1,000 WCUs regardless of adaptive behavior¹. The documented mitigation is write sharding: append a random suffix (1 to 200) to the partition key¹¹.

CockroachDB range-partitions the entire keyspace into 512 MiB ranges, each a Raft group with three replicas¹⁶⁹. Splits are metadata operations on the Pebble store. For sequential workloads, hash-sharded indexes scatter writes across many ranges at the cost of range-scan locality¹⁰. A February 2026 advisory documented a race between MVCC garbage collection and range splits that could delete live data under specific conditions²¹.

Redis Cluster fixes 16,384 hash slots at install time. Nodes own subsets of slots; resharding moves slots one at a time via MIGRATE⁷. Hash tags ({user1000}.followers) force related keys to the same slot for multi-key operations. The 16,384 limit exists because the gossip heartbeat carries the full slot bitmap; doubling slots would double gossip bandwidth⁷.

Common Mistakes

Decision Checklist

• Are range scans first-class queries, or report-only (can tolerate fan-out)?
• Is the partition key monotonic (timestamps, autoincrement)? If yes, hash it or prefix it.
• Will cluster membership change frequently (weekly scale-out, node churn)?
• Is any tenant large enough to warrant a dedicated shard?
• Have you pre-sharded into enough virtual partitions to grow for 3 to 5 years?
• Can you state the per-partition throughput ceiling (DynamoDB: 1,000 WCUs)?
• Does your composite key have enough partition-key cardinality to avoid hot partitions?

flowchart TD
    Start["Choose partitioning scheme"]
    Q1{"Range scans are<br/>first-class queries?"}
    Q2{"Cluster membership<br/>changes frequently?"}
    Q3{"Need per-tenant<br/>placement control?"}
    Q4{"Sequential key<br/>pattern?"}
    Range["Range partitioning<br/>CockroachDB / TiKV / HBase"]
    ConsHash["Consistent hashing<br/>Cassandra / Dynamo"]
    Directory["Directory-based<br/>Vitess / custom"]
    Hash["Hash + composite key<br/>DynamoDB / Redis Cluster"]
    Hybrid["Hybrid: hash + sort key<br/>+ hash-sharded index"]
    Start --> Q1
    Q1 -->|yes| Q4
    Q4 -->|yes| Hybrid
    Q4 -->|no| Range
    Q1 -->|no| Q2
    Q2 -->|yes| ConsHash
    Q2 -->|no| Q3
    Q3 -->|yes| Directory
    Q3 -->|no| Hash

Key Takeaways

• Hash partitioning is the safe default for point-lookup workloads. Add a sort key for in-partition range locality.
• Range partitioning is correct when range scans dominate, but you must mitigate the hot tail on sequential keys.
• Consistent hashing solves rebalance cost (K/N movement), not query routing. Use it when nodes churn.
• Directory-based partitioning is for whale-tenant isolation and heterogeneous placement, not general-purpose routing.
• The decision is per-table, not per-database. One system can use hash for user lookups and range for time-series.

Further Reading

• Scaling DynamoDB: partitions, hot keys, and split for heat: definitive tour of DynamoDB’s internal partitioning, adaptive capacity, and the split-for-heat mechanism.
• Karger et al., “Consistent Hashing and Random Trees”, STOC 1997: the original paper; still the clearest explanation of the ring idea and the K/N movement guarantee.
• Lamping and Veach, “A Fast, Minimal Memory, Consistent Hash Algorithm”, 2014: jump consistent hash in five lines of code; fundamental reading for anyone implementing partitioning.
• How CockroachDB Automates Operations: automatic rebalance and repair mechanics with concrete range-size and dead-node-timeout numbers.
• Redis Cluster specification: the 16,384-slot design, MOVED/ASK redirects, gossip protocol, and hash tags.
• How Discord Stores Trillions of Messages: Cassandra hot-partition pain at scale and the migration to ScyllaDB with request coalescing.

Flashcards

References