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^[1]. Range partitioning preserves order and makes those scans cheap, but sequential writes (timestamps, autoincrement IDs) pile onto the newest range, creating a hot tail^[2][3].

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^[4]. 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^[5].

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

Each scheme trades one axis for another; no single approach dominates across all workloads.

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^[13]. 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^[7:2]. 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^[1:2].

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^[7:3].

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^[8:1]. But if you are using naive modulo without pre-sharding, adding a node remaps almost everything^[14].

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^[15].

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^[2:2][3:2].

Automatic splitting adapts to growth. CockroachDB splits ranges at 512 MiB^[16]; TiKV at 96 MB^[3:3]; HBase at 10 GB^[17]. 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^[10:1].

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^[4:2][18].

You need minimal disruption during scale-out. Adding a node to a 100-node Cassandra cluster moves roughly 1% of data, not 99%^[14:1].

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

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^[5:1].

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^[6:1]. 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^[1:3]. Cassandra assigns vnodes per physical node on a consistent-hash ring (256 in 3.x, 16 in 4.0+)^[8:3]. Vitess uses a directory (VSchema) to map rows to shards via a configurable vindex, with keyrange-based routing^[6:2].

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^[15:1].

Composite keys hash the partition key for even distribution, then keep sort keys ordered within each partition for cheap range scans.

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^[15:2]. 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^[1:4]. The documented mitigation is write sharding: append a random suffix (1 to 200) to the partition key^[11:1].

CockroachDB range-partitions the entire keyspace into 512 MiB ranges, each a Raft group with three replicas^[16:1][9:1]. 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^[10:2]. A February 2026 advisory documented a race between MVCC garbage collection and range splits that could delete live data under specific conditions^[21].

Redis Cluster fixes 16,384 hash slots at install time. Nodes own subsets of slots; resharding moves slots one at a time via MIGRATE^[7:4]. 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^[7:5].

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?

Decision flowchart: start with your dominant query pattern, then factor in membership dynamics and tenant isolation needs.

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#