Partitioning and sharding
When data outgrows one machine, it must be split across many. Partitioning, also called sharding, spreads both data and load, if keys are chosen well.
Why partition
A single server has limits on storage, memory, and write throughput. Partitioning splits a dataset so each partition, or shard, lives on a different node, and each node handles a share of the queries. Combined with replication, each partition is usually copied to several nodes for fault tolerance.
Range partitioning
Range partitioning assigns contiguous key ranges to partitions, such as customer names A to F on one node and G to M on another, or one partition per month of dates. Range queries are efficient because neighbouring keys are together. But skewed access creates hot spots: if keys are timestamps, all of today's writes land on a single partition.
Hash partitioning
Hash partitioning applies a hash function to the key and assigns hash ranges to partitions, spreading keys evenly and avoiding many hot spots. The cost is that range queries on the key must ask every partition. Some systems, such as Cassandra, combine the approaches: hash on one part of a compound key to choose the partition, then sort by the rest within it.
Choosing a partition key
The partition key decides where data lives, so it should spread load evenly and keep data that is queried together on the same partition. Partitioning orders by customer_id keeps each customer's orders together; partitioning by order date makes per-customer queries touch every partition. Extremely popular keys, such as a celebrity's account, can still overload one partition and may need special handling.
Rebalancing
As data grows or nodes are added, partitions must move. Using hash mod N is a poor scheme, because changing N moves almost every key. Better approaches create many more partitions than nodes and move whole partitions between nodes, or use consistent hashing, so only a small fraction of data moves. Rebalancing should be gradual so it does not overload the cluster.
Secondary indexes and routing
Secondary indexes complicate partitioning. A local index on each partition indexes only that partition's rows, so a query by the indexed column must ask all partitions (scatter-gather). A global index is itself partitioned by the indexed value, making reads efficient but writes more complex. A routing layer or partition-aware client sends each query to the right nodes.
Cross-partition transactions
Transactions touching several partitions need coordination. Two-phase commit (2PC) has a coordinator ask every participant to prepare, then, if all vote yes, tell them to commit; otherwise all abort. 2PC guarantees atomicity but blocks if the coordinator fails at the wrong moment, and adds latency, so designs try to keep most transactions within one partition.
Worked example
A messaging app with 400 million users shards messages by hash of conversation_id into 4,096 partitions spread over 64 nodes, 64 partitions each. Loading one conversation touches one partition. Adding 16 nodes means each existing node hands about 13 partitions to the newcomers, which end up with about 51 each: roughly 819 partitions, about 20% of the data, move instead of everything being reshuffled. A global search by sender, however, needs either a global index or a query to all 4,096 partitions.
Key takeaways
Partitioning splits data across nodes for storage and throughput, usually combined with replication. Range partitioning supports range queries but risks hot spots; hash partitioning spreads load but scatters ranges; compound keys combine both. Partition keys should balance load and co-locate data queried together. Rebalance by moving many fixed partitions or using consistent hashing, not hash mod N. Local secondary indexes need scatter-gather; global indexes complicate writes. Cross-partition transactions use two-phase commit, which guarantees atomicity but can block and adds latency.
Flashcard
Subset of data on one node
Check your understanding
Why is partitioning a sensor table by timestamp range likely to create a hot spot?