Partitioning and the partition count

How many partitions should a system have, and why does no partition count fix one hot key?

Partitioning is uncontroversial in principle. Its whole design space comes from one derived quantity: the partition count.

Every partition has a fixed cost: an open set of files, an in-memory write buffer, a share of a compaction (background merge) thread, a heartbeat, and, in systems where each partition is its own replicated group, a whole consensus instance with its own periodic traffic. Call this cost f per partition.

Against it stands the granularity cost. The partition is the unit of movement and the unit of ownership, so partition size is the floor on achievable imbalance and the quantum of every rebalance. With P partitions over N nodes, the unavoidable imbalance falls roughly as 1/P (more precisely, it depends on the variance of the load over P/N partitions per node). Minimise f·P + c/P and you get the familiar interior optimum: the total cost is lowest at some middle value of P. This is "fixed cost gives a natural batch size" in a new form, with "granularity mismatch" supplying the other term.

Real systems land in the same place from very different architectures: tens of partitions per node, partition sizes in the 1–100 GB range.

• Cassandra moved its vnode default (virtual nodes per machine) from 256 down to 16, because the per-partition cost in repair and gossip metadata proved higher than the benefit of better balance.
• Elasticsearch's guidance of roughly 20 shards per GB of heap is the same inequality, expressed in the currency that binds there (memory).
• HDFS's 128 MB block with about 150 bytes of NameNode state per object is the same trade at four orders of magnitude finer granularity, with the metadata term collected in one machine's RAM. That is why the small-file problem is a distribution problem and not only an I/O problem.

Hash versus range

How a key is mapped to a partition is a routing function. The part that belongs here is an informational asymmetry. With hash partitioning, the distribution of keys in the output space is known in advance, so the boundaries can be fixed at creation and never revisited. With range partitioning (partition 1 holds keys A–F, partition 2 holds G–M, and so on), the boundaries depend on the data, which is not known in advance and changes. So the system must be able to split and merge partitions at runtime.

That single difference, and not scan performance, is why range-partitioned systems (HBase, TiKV, CockroachDB, Spanner) all carry dynamic split/merge machinery, and hash-partitioned ones (Kafka, Cassandra, most sharded caches) mostly do not. You can precompute a partitioning of a known distribution; you must adapt one over an unknown distribution.

The impossibility that returns

No partitioning function separates a key from itself. If one single key is hot, it lands in one partition, and increasing P does nothing for it. The same fact appears in several settings: a single grouping key larger than memory that recursive repartitioning cannot rescue; the head of a Zipf distribution that consistent hashing cannot split; and here, the hot partition that no increase in P fixes. The escapes (replicate the key, salt it, or change the algebra so it need not be together) are the same each time, and are taught with skew.

The shard key: keep each transaction with one owner

Partitioning decides who owns each key, so it also decides how often several owners must agree. A transaction confined to one partition has one owner deciding it. One that spans partitions needs two-phase commit or a saga, which is coordination bought on every such transaction. The main design goal of most sharded systems is therefore to make cross-shard transactions unnecessary by choosing a shard key that keeps transactional units together.

Shard by customer_id and a customer's orders, addresses and payments are co-located: single-shard transactions and single-shard reads. Shard by order_id and every customer-level operation is a scatter-gather. The data is identical. The key decided whether it works.

The tension you will meet: the transactional key and the analytical key are usually different. Customer sharding is right for OLTP (the many small read/write transactions of the live application) and terrible for "revenue by product this month", which touches every shard. The answer is not a compromise key. It is separate systems with different partitioning, connected by change data capture. That is a large part of why a separate analytical system exists at all.

(The number of partitions of a stream is a different decision, set by consumer parallelism and ordering scope: Choosing N.)

Compression: partition count is a fixed-cost-versus-granularity optimum. Hashing lets you fix boundaries in advance, ranges force you to learn them, nothing fixes one hot key, and the shard key decides how often owners must agree.