Partitioning: splitting data across machines

A subset of the data such that every record, row or document belongs to exactly one partition.

Partitioning exists for scalability: different partitions live on different nodes, so data volume and query load are spread over many disks and CPUs. It is usually combined with replication, so each partition has copies on several nodes.

Some partitions get more data or queries than others.

With skew, adding nodes stops helping: with 10 nodes but all load on one, you have the throughput of one node. The goal of partitioning is an even spread of both data and load.

A partition with disproportionately high load.

Hot spots come from the access pattern, not only the data size: sequential keys like timestamps send all of today's writes to one partition, and a celebrity's key is hot no matter how you hash it.

Each partition owns a contiguous range of keys, like volumes of an encyclopedia; keys are kept sorted within a partition.

Range scans are cheap because neighbouring keys live together. But boundaries must adapt to the data, and access patterns that cluster on adjacent keys (timestamps) create hot spots.

A hash function maps each key to a number; each partition owns a range of hashes.

A good hash spreads even skewed keys uniformly, avoiding hot spots for many patterns. The cost is losing the sort order: a range query has to be sent to all partitions.

A key with several columns where only the first is hashed to pick the partition and the rest are kept sorted within it.

A middle ground between hash and range: e.g. (user_id, timestamp) spreads users across partitions but still allows an efficient range scan over one user's updates.

Append a random number (say two digits) to a very hot key so its writes spread over many sub-keys and partitions.

It relieves the hot partition, but every read must now fetch all sub-keys and combine them, and you need bookkeeping to know which keys are split. Most databases leave this to the application.

Each partition maintains a secondary index covering only the documents stored in that partition.

Writes stay on one partition and the index is updated synchronously. But a query by secondary key must be sent to every partition and the results merged.

Send a query to all partitions in parallel and combine their answers.

The query is only as fast as the slowest partition, so tail-latency amplification makes scatter/gather reads expensive, even when they run in parallel.

A secondary index that covers all data but is itself partitioned by the indexed term, separately from the documents.

A read needs only the partition holding that term. A single document write may now touch several partitions, so in practice the index is updated asynchronously and may briefly miss recent writes.

Moving load from one node to another as data, query rate or the set of machines changes.

Afterwards load should be fair, the database should keep serving reads and writes during the move, and no more data should move than necessary.

Pick the node as hash(key) mod number-of-nodes.

Don't: when N changes, most keys map to a different node (going from 4 to 5 nodes moves about 80% of keys), making rebalancing very expensive.

Create many more partitions than nodes up front (e.g. 1,000 for 10 nodes); a new node steals whole partitions from existing ones.

The key-to-partition mapping never changes, only partition-to-node does, so moves are minimal. But the count is fixed at setup: too few and partitions grow huge, too many and overhead adds up.

Key-range partitions split in two when they exceed a size threshold and merge with a neighbour when they shrink, like a B-tree's top level.

The number of partitions adapts to the data volume. An empty database starts with one partition, so all writes hit one node until the first split; pre-splitting helps if you know the key distribution.

Configure an initial set of partition boundaries on an empty database.

It avoids the single-partition bottleneck at the start, but only works if you can predict the key distribution in advance.

A fixed number of partitions per node; a joining node splits a random selection of existing partitions and takes half of each.

Partition size stays stable as the cluster grows. Random split points can be unfair, but with enough partitions per node (Cassandra used 256) the load averages out.

Place randomly chosen tokens on a hash ring; a key belongs to the next token clockwise, so adding or removing a node moves only nearby keys.

It was designed for distributed caches. The book notes the name is confusing and the scheme is rarely used as originally described; in databases, think 'hash partitioning with random boundaries'.

How a client finds the node that holds the key it wants: ask any node, go through a partition-aware routing tier, or use a partition-aware client.

It is service discovery for partitions. The hard part is everyone agreeing on the assignment while partitions move; a stale view sends requests to the wrong node.

A separate, consistent store of the partition-to-node mapping that nodes register with and routers subscribe to.

It gives one authoritative assignment and notifies subscribers when it changes, so routing can catch up. Many systems rely on it instead of building their own consensus.

Analytic (MPP) databases break complex queries into stages that run on many partitions at once.

Key-value style single-partition reads are the simple case; warehouses push joins, filters and aggregations down to partitions in parallel (the topic returns in chapter 10).