Skip to main content

Partitioning of Key-Value Data

Adapted from: Martin Kleppmann, Designing Data-Intensive Applications (O'Reilly, 2017), Chapter 6 — rewritten and condensed for teaching.

Leaders and Followers and the lessons after it covered replication — multiple copies of the same data. That solves availability and read throughput, but not raw scale: once a dataset (or its query load) outgrows what any single machine can hold or serve, replication alone can't help, because every replica still has to hold the entire dataset. The fix is partitioning (also called sharding): splitting the data itself into pieces, so each piece — each partition — lives on a different node, and together the partitions cover the whole dataset with no overlap.

One term, many names

The same idea goes by different names depending on the database: shard in MongoDB/Elasticsearch/SolrCloud, region in HBase, tablet in Bigtable, vnode in Cassandra/Riak, vBucket in Couchbase. This series sticks with the more universally recognized term: partition.

Partitioning and replication are normally combined, not competing choices — each partition typically has its own leader and followers, spread across different nodes, so a single node commonly acts as leader for some partitions and follower for others simultaneously. Everything from the previous four lessons about replication applies identically at the level of a single partition; this lesson (and the next two) can therefore set replication aside and focus purely on how the data itself gets split up.

The Goal: Spread Load Evenly, Avoid Hot Spots​

The entire point of partitioning is to spread both data and query load evenly enough that adding nodes actually buys you proportional capacity — ten nodes handling roughly ten times the data and throughput of one, replication aside. When the split isn't even, it's called skewed, and skew directly undermines the whole point of partitioning — in the worst case, virtually all load lands on one overloaded partition (a hot spot) while every other node sits idle, and your entire cluster's throughput is bottlenecked by that one busy node.

The simplest possible fix for skew — assign records to nodes randomly — actually works reasonably well for even distribution, but it has a fatal flaw for reads: with no rule connecting a key to its location, finding any particular record means querying every node in parallel, every single time. A far better approach, assuming records are looked up by a primary key (the common case): make the key itself determine which partition it lives on, deterministically — the same idea as looking up a word in a paper encyclopedia by its first letter, rather than checking every volume on the shelf.

Partitioning by Key Range​

Assign each partition a contiguous range of keys — exactly like the encyclopedia's per-volume alphabetical ranges. Knowing the boundaries tells you instantly which partition (and therefore which node) owns any given key, letting you route a request directly rather than guessing. Bigtable, HBase, RethinkDB, and pre-2.4 MongoDB all use this scheme.

Crucially, those ranges don't have to be evenly sized by key — an encyclopedia volume spanning A–B is much thinner than one spanning T–Z, precisely because English words aren't evenly distributed across the alphabet. Getting an even data distribution means letting boundaries adapt to the actual data, whether chosen by an administrator or computed automatically. A real bonus of range partitioning: keys within a partition can be kept sorted (exactly the SSTable structure from Hash Indexes and LSM-Trees), making range scans cheap — genuinely useful for something like sensor readings keyed by timestamp, where "give me every reading from March" is a natural, frequent query.

That same timestamp-as-key design is also the textbook way key-range partitioning backfires: if each partition covers one day, then every single write — for every sensor, all day — lands on today's partition while every other partition sits completely idle. The fix isn't abandoning range partitioning; it's choosing a better key. Prefixing the timestamp with a sensor name (so partitioning happens first by sensor, then by time) spreads simultaneous writes from many active sensors across many partitions — at the cost that fetching several sensors' data over a time range now needs a separate range query per sensor instead of one combined query.

Check: partitioning goals and key range partitioning​

Quiz

Why partition, and key range partitioning

1 / 3

Why does replication alone fail to solve the problem that partitioning addresses?

Pick an answer to see if you are right.

Partitioning by Hash of Key​

Key range partitioning's Achilles' heel — access patterns clustering around nearby keys — is exactly what hash partitioning avoids. Run each key through a hash function first, then partition by ranges of the hash output instead of the key itself. A good hash function takes even badly skewed real-world keys and spreads their hashes uniformly across its output range — Cassandra and MongoDB use MD5 for this, Voldemort uses Fowler–Noll–Vo; the hash doesn't need to be cryptographically secure, just evenly distributing. (Watch out for language built-in hash functions here — Java's Object.hashCode() and Ruby's Object#hash can return different values for the same key across different process runs, which is exactly wrong for something that needs to durably determine where data lives.)

"Consistent hashing" is a term worth using carefully

Consistent hashing technically refers to a specific rebalancing-friendly technique (Karger et al.) originally built for internet-wide CDN caches, using randomly-chosen partition boundaries to avoid centralized coordination — it has nothing to do with replica consistency or ACID consistency, despite the shared word. As the next lesson covers, this specific technique doesn't actually work especially well for databases in practice, even though plenty of database documentation still loosely (and often inaccurately) uses the term. Calling the general technique hash partitioning avoids the confusion entirely.

The trade-off hash partitioning makes: it destroys key ordering. Keys that used to sit right next to each other scatter randomly across every partition, so range queries — the one thing range partitioning was genuinely good at — become expensive or outright unsupported (MongoDB has to fan a range query out to every partition under hash-based sharding; Riak, Couchbase, and Voldemort don't support primary-key range queries at all).

Cassandra strikes a real compromise using a compound primary key: only the first column gets hashed to pick the partition; the remaining columns act as a concatenated sort key within that partition. You lose the ability to range-scan across the first column's values, but given a fixed value for it, range scans across the rest are still efficient. This maps beautifully onto one-to-many data: a primary key of (user_id, update_timestamp) scatters different users' posts across different partitions (good load spreading) while keeping any one user's posts sorted by time within their own single partition (efficient "show me this user's recent activity" queries).

Check: hash partitioning​

Quiz

Partitioning by hash of key

1 / 3

What is the fundamental trade-off hash partitioning makes compared to key range partitioning?

Pick an answer to see if you are right.

Practice: hash-based partition assignment​

Implement the core mechanic directly: a function that deterministically maps any key to one of n partitions using a hash of the key.

Skewed Workloads and Relieving Hot Spots​

Hashing fixes skew coming from clustered keys — but it can't rescue you from skew caused by one key getting hammered. If every read and write targets the same key, hashing that key still always produces the same hash, landing every single request on one partition regardless. This isn't purely academic: a celebrity's post going viral can direct an enormous concentrated burst of writes at one specific key (the celebrity's user ID, or the ID of whatever post everyone's suddenly commenting on) — and hashing that ID doesn't spread the load out even slightly, since it's still just one ID being hashed to one place, over and over.

Most systems today can't automatically detect or fix this kind of skew — it falls to the application to intervene. A workable technique: append a small random number (say, two decimal digits) to a known-hot key, effectively splitting it into 100 different keys spread across potentially 100 different partitions. The catch: reads now have to fetch and combine data from all 100 split-key variants instead of one straightforward lookup — real added cost, and one you'd never want to pay for the vast majority of keys that aren't hot. That means the application also needs a way to track which keys are currently being split this way, so the technique gets applied only where it's actually earning its cost.

Check: skewed workloads​

Quiz

Relieving hot spots

1 / 2

Why doesn't hash partitioning help when a single specific key receives a disproportionate share of all reads and writes (e.g. a viral celebrity post)?

Pick an answer to see if you are right.

Key takeaways
  • Partitioning splits a dataset itself (not just copies of it) across nodes — the only real fix once data or query load outgrows a single machine, and it's typically combined with, not replaced by, replication at the level of each partition.
  • The goal is always even distribution of data and load; an uneven split is skew, and its worst form — nearly all traffic on one partition — is a hot spot.
  • Key range partitioning keeps keys sorted and supports efficient range scans, but is vulnerable to hot spots whenever real access patterns cluster around nearby keys (like "right now" in a timestamp-keyed dataset).
  • Hash partitioning spreads keys evenly by discarding their natural ordering — a real trade-off against range query efficiency — with Cassandra's compound-key design offering a practical middle ground.
  • Neither technique rescues you from a single key receiving disproportionate traffic — that requires an application-level fix like randomly suffix-splitting the hot key, accepting more expensive multi-key reads in exchange for spread-out writes.

Further Reading​