Why Partition at All

The replication series spent fifteen posts on one idea: keep a copy of the same data on several machines. Every technique in it — leaders, quorums, version vectors — is a different answer to the question of how those copies stay in agreement.

None of them make the data smaller. If your dataset does not fit on one machine, replication gives you several machines that each cannot hold it. If your write throughput exceeds what one machine can absorb, replication gives you several machines all absorbing the same overflow. For those two problems you need to break the data up instead, into partitions.

One Record, One Partition

The word is not settled. What this series calls a partition is a shard in MongoDB, Elasticsearch and SolrCloud; a region in HBase; a tablet in Bigtable; a vnode in Cassandra and Riak; and a vBucket in Couchbase. They are the same idea wearing six labels.

It is also unrelated to a network partition — the netsplit kind, where machines can’t reach each other. That is a fault. This is a deliberate design choice, and the collision of names is unfortunate.

The defining property is exhaustive and exclusive: every record belongs to exactly one partition. Each partition is effectively a small database of its own, with its own slice of the keys, even though a query may end up touching several of them at once.

That is what buys scalability. Put partitions on different nodes in a shared-nothing cluster and a large dataset spreads across many disks, while the query load spreads across many processors. Queries that touch a single partition run independently on their own node, so throughput grows by adding nodes.

Partitioning Is Not Replication

The two are almost always used together, and they are almost entirely independent.

Partitioning and replication are independent

Four nodes hold four partitions. Each partition has a leader on one node and followers on two others, so every node is a leader for some partitions and a follower for others. Choosing how to partition and choosing how to replicate are separate decisions.

Each partition’s leader lives on one node and its followers on others. Because the assignment is per-partition, a single node ends up leader for some partitions and follower for others — there is no such thing as “the leader” of the cluster any more, only the leader of partition 3.

Everything from the replication series still applies, unchanged, to each partition individually. That is the useful part: the choice of partitioning scheme is largely independent of the choice of replication scheme, so the two can be reasoned about separately. The rest of this sub-series takes that permission and ignores replication entirely.

Skew and Hot Spots

The goal is not just to spread the data. It is to spread the data and the query load.

Even load, and the same cluster with one hot partition

Two four-partition clusters drawn as bar charts of share of load. On the left every partition carries about a quarter. On the right one partition carries eighty-five percent while the other three sit near idle — the bottleneck is that single busy partition, and adding nodes does not move it.

If it works, ten nodes hold ten times the data and serve ten times the reads and writes of one. If the distribution is unfair — some partitions holding far more data or fielding far more queries than others — the partitioning is skewed, and a partition carrying disproportionate load is a hot spot.

Skew is not a rounding error. In the extreme case every request lands on one partition, nine nodes sit idle, and the cluster’s throughput is exactly one node’s throughput. You have paid for ten machines and bought a more complicated single machine.

The Strawman

There is an easy way to guarantee an even spread: assign each record to a node at random.

It works perfectly, and it is useless. To read one record you have no idea which node holds it, so you have to ask all of them and wait for the slowest. Random placement optimises distribution by destroying lookup.

So the real problem is narrower than “spread the data evenly”. It is: spread the data evenly while keeping it findable from the key alone. Every scheme in the next three posts is a different bargain between those two, and each one gives something up.

The running example throughout will be an activity-feed store — posts keyed on (user_id, timestamp), written constantly and read in time-ordered slices. It is small enough to hold in your head and large enough to break in all the interesting ways.

Key Takeaways

Partitioning solves what replication cannot: a dataset or a write rate too large for one machine.
A partition is a shard, a region, a tablet, a vnode, a vBucket. Every record lives in exactly one.
Partitioning and replication are independent choices. A node is typically leader for some partitions and follower for others.
The target is an even spread of data and load; unfairness is skew, and a partition with disproportionate load is a hot spot.
Random placement spreads perfectly and is unusable, because you can no longer find a record from its key.

Next: assign each partition a continuous range of keys, and see what that costs.

References

Martin Kleppmann, Designing Data-Intensive Applications, chapter 6 — the treatment of partitioning this sub-series works through.
Fay Chang et al., Bigtable: A Distributed Storage System for Structured Data — where the term tablet comes from.
Giuseppe DeCandia et al., Dynamo: Amazon’s Highly Available Key-value Store — where vnode comes from, and the origin of much of the vocabulary in this post.
Couchbase — vBuckets — one more name for the same idea.
Apache HBase Reference Guide — regions, and how partitioning and replication are configured independently of each other.