On this path · Distributed Primitives 4. Partitioning, Sharding, and Consistent Hashing
Partitioning, Sharding, and Consistent Hashing
Hash rings, Postgres hash versus list partitioning, and the UUID dedup-table benchmark.
Learning outcomes
A brokerage accumulates tables that grow without bound: a deduplication table that records every idempotency key ever seen, a trades table that records every fill, an outbox that records every event. A single table on a single machine eventually cannot hold or serve that data, so you split it. How you split it is a decision with real tradeoffs, and Trade Republic published a benchmark that overturns a common intuition: for partitioning a UUID table, the boring built-in hash beat the hand-rolled list approach on every axis. This concept teaches why, and then climbs from database partitioning to the consistent hashing rings that distribute keys across caches and clusters.
After studying this page, you can:
- Explain why a growing table forces partitioning and what partitioning buys (and costs).
- Contrast hash and list partitioning in PostgreSQL, and reproduce the Trade Republic benchmark result that hash beat list for a UUID dedup table.
- Explain why list partitioning on a computed expression forfeits the parent primary key, and why that matters for logical replication.
- Describe the size versus speed tradeoff of hash indexes versus b-tree.
- Build a consistent hashing ring with virtual nodes and prove its minimal-movement property.
- Distinguish consistent hashing from fixed hash slots (Redis Cluster) and name when each applies.
Before we dive in
An idempotency table is the memory of a brokerage’s API. Every request that must not be replayed carries an idempotency key, and the service records that key in a table so a retried request is recognized and not double-applied. At Trade Republic’s scale, this table grows by millions of rows a day and never shrinks, because a key, once seen, must be remembered forever (or for a very long time) to defeat a late retry. A single PostgreSQL table holding years of these keys becomes too large to query efficiently, too large to vacuum in a maintenance window, and too large to keep in memory. The index and the heap both bloat, and every lookup pays for the table’s entire history.
The response is partitioning: split the one logical table into many physical pieces, each holding a slice of the data, so that a query touches only the slice it needs. PostgreSQL supports this natively, and the choice of how to split, by what key and with what function, determines the performance. Trade Republic benchmarked two approaches, hash and list, and the result was a lesson in not trusting intuition: the hand-rolled fancy approach lost to the optimized built-in. That result is the entry point to this concept, because understanding why hash won teaches you what partitioning actually does at the storage layer.
From there, the same problem appears at a different scale: distributing keys across a cluster of machines, where machines join and leave. Database partitioning is static (you define partitions in advance), but cluster sharding must handle membership change without moving the whole world. That is where consistent hashing enters, and the concept closes by connecting the database partitioning decision to the consistent hashing rings used in caches and distributed stores.
Why partition at all
A table that grows without bound eventually hits three walls. The first is query performance: an index on a huge table is itself huge, and lookups traverse more pages, so latency rises. The second is maintenance: PostgreSQL’s vacuum, index rebuilds, and backups all scale with table size, and a multi-terabyte table cannot be maintained in the same window as a multi-gigabyte one. The third is operational: a single table on a single machine is a single point of capacity; it cannot use the resources of a second machine.
Partitioning breaks the table into smaller physical pieces that share a logical schema. A query with the partition key in its predicate lets the planner prune: it reads only the partition that could hold matching rows and ignores the rest. Vacuum runs per partition, so a small, hot partition is maintained quickly. And partitions can, in some setups, live on different storage or be moved to spread load. The cost is planning overhead (the planner must decide which partitions to scan) and the discipline of always including the partition key in queries, because a query without it scans every partition.
Once a table is partitioned, every query must include the partition key in its predicate, or the planner cannot prune and scans all partitions. The partition key becomes the axis along which the table is organized, and queries that ignore it pay the full price. Choose the key you will always filter on.
Hash versus list partitioning
PostgreSQL offers several partitioning strategies, and the two that matter here are list and hash. List partitioning assigns a row to a partition based on an explicit mapping: this set of key values goes to partition one, that set to partition two. Hash partitioning assigns a row by hashing the key and taking a modulo over the partition count, distributing rows roughly evenly without an explicit map.
The UUID dedup table is the case where the choice is non-obvious. You want to spread UUIDs evenly across, say, sixteen partitions. List partitioning seems flexible: compute a partition number from each UUID and route by it. Hash partitioning seems rigid but simple: let the database hash the UUID and assign by modulo. The intuition many engineers bring is that list partitioning, being explicit, must be more controllable and therefore faster. The benchmark showed the opposite.
The reason hash won is in the diagram. PostgreSQL’s hash partitioning uses a hash function implemented in C, run inside the database engine, which is fast. List partitioning on a computed key requires deriving the partition number in SQL, which for a UUID means casting it to text and running functions like LEFT and LOWER to extract a routing prefix. That per-row computation is more expensive than the native hash, and at high insert volume the difference compounds into measurably lower throughput and higher latency.
The UUID dedup benchmark
Trade Republic partitioned a UUID deduplication table into sixteen partitions and benchmarked hash against list partitioning on inserts. Hash partitioning won on both axes: higher transactions per second and lower latency. The gap was not subtle, and it overturns the intuition that a hand-rolled explicit scheme beats a generic built-in.
The lesson is about where the work happens. Hash partitioning pushes the routing decision into the database’s native code path, which is optimized and runs close to the storage. List partitioning on a computed key pushes the routing decision into a SQL expression that the database must evaluate per row, involving a type cast and string manipulation. The benchmark’s value is not that hash is always better; it is that the boring, optimized built-in deserves measurement before you assume a fancier scheme wins. Intuition about partitioning is often wrong because the cost lives in details, the function implementations and type conversions, that are invisible until you measure.
Why list on a computed key forfeits primary keys
There is a second, structural reason hash won for this table, and it matters beyond performance. A primary key on a partitioned table must include the partition key. This is a PostgreSQL constraint: because each partition is its own physical table with its own index, the uniqueness of a primary key can only be enforced within a partition if the partition key is part of the key. If you partition by list on a computed expression, the partition key is an expression, and PostgreSQL cannot include an expression in a primary key, so the parent table cannot have a primary key at all.
A partitioned table’s primary key must contain the partition key as a real column. Partitioning by an expression (a computed partition number derived from a UUID) means the partition key is not a column, so no primary key can be declared on the parent. You lose global uniqueness enforcement and you complicate logical replication.
This matters for two reasons. The first is uniqueness. A dedup table exists to enforce that an idempotency key appears once. Without a primary key on the parent, uniqueness must be enforced per partition, which means the partition function must route identical keys to the same partition every time, or duplicates can slip across partitions. A hash on the UUID itself routes deterministically, so identical UUIDs always land together, and a unique constraint per partition is sufficient. A list scheme on a computed prefix must guarantee the same, which adds fragility.
The second reason is logical replication. PostgreSQL logical replication publishes changes by table, and it relies on a primary key to identify rows for updates and deletes. A partitioned table without a primary key cannot be logically replicated cleanly, because the replication slot has no way to address a changed row. Hash partitioning keeps the primary key (the UUID column is the partition key, and it is in the primary key), so the table remains replicable. List partitioning on an expression forfeits the primary key, which closes off logical replication as an option. For a brokerage that may need to stream changes to a warehouse or a downstream system, losing that option is a real cost.
Hash indexes and b-tree, size versus speed
A separate but related decision is the index type. The default PostgreSQL index is a b-tree, which supports equality and range queries and uniqueness. PostgreSQL also offers a hash index, which supports only equality. The intuition is sometimes that a hash index, being simpler, must be faster for equality lookups. The benchmark found otherwise: hash indexes were not faster than b-tree for the dedup table’s lookups, but they were slightly smaller, by under five percent.
The takeaway is that the default b-tree is highly optimized in PostgreSQL, and a hash index does not beat it on speed for typical equality workloads. The only measurable advantage was a small index size reduction, which rarely justifies the loss of range queries and uniqueness support. The benchmark reinforced the same lesson as the partitioning result: measure the boring optimized default before assuming a specialized structure wins.
Consistent hashing
Database partitioning is static: you define a fixed set of partitions and they stay. Cluster sharding is dynamic: machines join and leave, and the system must keep running through the change. If you shard by a simple modulo over the node count, then adding or removing a node changes the modulo for every key, moving nearly the whole dataset. That is catastrophic for a cache, where a re-shard would evict everything and rebuild from scratch.
Consistent hashing solves the minimal-movement problem. Instead of modulo over the node count, you place nodes on a ring defined by a hash of their identifier. A key is hashed to a position on the same ring and is assigned to the first node clockwise from its position. When a node joins, it takes over only the keys whose ring position falls between it and its predecessor, so only a fraction of keys move. When a node leaves, its keys move to its successor, again a fraction.
Virtual nodes refine this. A single node’s position on the ring is one point, which can lead to uneven load if positions cluster. To balance, each physical node is placed on the ring multiple times at pseudo-random positions, as several virtual nodes. A key still goes to the next virtual node clockwise, but because each physical node owns many arcs spread around the ring, load is balanced and the departure of one physical node spreads its keys across many successors rather than dumping them all on one.
Consistent hashing versus fixed hash slots
Consistent hashing is not the only dynamic sharding strategy. Redis Cluster uses fixed hash slots: the keyspace is divided into 16384 slots, a key is assigned to a slot by a hash function, and each node owns a contiguous range of slots. Re-sharding moves slots between nodes, which is more controlled than ring arcs but requires explicit slot migration.
The difference is in how change propagates. With consistent hashing, adding a node changes the assignment of keys in an arc determined by the new node’s ring position, and the moved set is implicit. With fixed slots, adding a node means reassigning a chosen set of slots to it, and the moved set is explicit and administratively chosen. Consistent hashing is simpler to reason about for caches and content-addressed stores where any balanced assignment is fine. Fixed slots give finer control over placement, which matters when slots have different sizes or when migration must be staged.
Consistent hashing fits when you want balanced, automatic redistribution and any roughly-even assignment is acceptable, as in a cache or a Dynamo-style store. Fixed hash slots fit when you need explicit control over which data lives where and staged migration, as in Redis Cluster. Both achieve minimal movement compared to naive modulo, but they distribute the bookkeeping differently.
For a brokerage, the database partitioning decision (hash on a real key) and the cluster sharding decision (consistent hashing for a cache) are related but separate. The database partition key is chosen for query pruning and is static; the consistent hash ring is chosen for minimal movement and is dynamic. A senior engineer knows which question they are answering: am I splitting one database, or distributing load across many machines that change?
Partition pruning and the discipline of the partition key
Partitioning only pays off when queries let the planner prune. Pruning is the planner’s act of reading a query’s predicate, matching it against each partition’s definition, and scanning only the partitions that could hold matching rows. A query that filters on the partition key lets the planner eliminate every partition whose range or list cannot match, so a sixteen-partition table is read as if it were one. A query that omits the partition key forces the planner to scan all partitions, which is slower than scanning one unpartitioned table, because it pays sixteen index seeks and merges sixteen result sets.
This is why the partition key must be the column the workload always filters on. For the dedup table, every lookup is by the UUID key, so the UUID is the partition key and every lookup prunes to one partition. For the outbox, the partition key is the publication marker, and the publisher always filters on it, so the publisher reads one partition. A mismatch between the partition key and the query pattern is worse than no partitioning, because the planning overhead is paid with no pruning benefit.
A partitioned table scanned without the partition key touches every partition, which is slower than one unpartitioned table of the same size, because the planner pays per-partition planning and execution overhead and then merges results. Partitioning is a win only when the query pattern matches the partition key. Measure the actual queries before partitioning, and choose the key they all share.
How many partitions, and where partitioning hurts
The partition count is a tradeoff between pruning granularity and planning overhead. More partitions mean each one is smaller and faster to scan, vacuum, and back up, and a query prunes to a smaller slice. But more partitions also mean the planner does more work to decide which to scan, and PostgreSQL has a soft limit (currently around two thousand partitions in recent versions) beyond which planning time degrades noticeably even with pruning. Trade Republic chose sixteen for the dedup table, a number large enough to bound each partition’s size and small enough to keep planning cheap.
Partitioning also has costs that surprise engineers who reach for it prematurely. A unique constraint on a partitioned table must include the partition key, which means a globally unique identifier that does not include the partition key cannot be enforced. Foreign keys referencing a partitioned table are restricted. Cross-partition updates, which change the partition key, physically move the row (a delete plus insert), which is more expensive than an in-place update and can bloat the table if it happens often. These are the reasons partitioning is a response to a table that has genuinely outgrown one piece, not a default schema choice.
The outbox revamp from the first concept is the clearest example of partitioning used as a cure for a specific operational disease. The partial index bloat and visibility-map collapse were not solvable by tuning the index; they were structural, caused by the working set churning against a growing majority. Partitioning by the publication marker separated the churning working set from the stable history, and the disease disappeared because the structure changed. That is when partitioning earns its costs: when the problem is structural, not parametric.
Common mistakes candidates make
The first mistake is trusting intuition over measurement on partitioning. A candidate declares that list partitioning must be faster because it is explicit, without measuring the per-row cost of the computed key. The benchmark shows the optimized built-in hash wins, and the lesson is to measure before assuming.
The second mistake is partitioning by an expression and losing the primary key. A candidate computes a partition number from a UUID without realizing that the partition key becomes an expression, which PostgreSQL cannot include in a primary key, forfeiting global uniqueness and logical replication. The fix is to partition by a real column.
The third mistake is assuming hash indexes are faster than b-tree. The benchmark shows they are not faster for equality, only slightly smaller, and they lose range and uniqueness support. The default b-tree is highly optimized and usually the right choice.
The fourth mistake is using naive modulo for cluster sharding and moving the whole world on a re-shard. A candidate who shards by taking the hash of the key modulo the node count will, on adding a node, rehash nearly every key and evict the entire cache. The fix is consistent hashing with virtual nodes, which moves a fraction.
The fifth mistake is confusing database partitioning with cluster sharding. They solve different problems at different layers: database partitioning splits one logical table for query pruning and maintenance, with a static partition set; cluster sharding distributes keys across machines that change membership, with dynamic redistribution. The right tool depends on which problem you face.
The sixth mistake is choosing the partitioning strategy without checking whether the key distributes evenly. Hash partitioning spreads a uniform key well, but a key with hot values (one account generating most of the traffic) still concentrates load in one partition regardless of strategy. Partitioning balances storage, not access; a hot key defeats both hash and list, and the fix for a hot key is application-level sharding or caching, not a different partition function.
Range partitioning and when the key is time
Hash and list are not the only strategies, and a brokerage has tables where the natural axis is neither a UUID nor a category but time. A trades table accumulates rows by the day, and nearly every query is for a recent window: today’s trades, last week’s fills, a quarter of history. The partition key that matches that query pattern is the trade date, and the strategy is range partitioning, which assigns rows to partitions by a value range (one partition per day or per month).
Range partitioning gives two benefits hash cannot. The first is time-based pruning: a query for today’s trades prunes to one day’s partition and ignores years of history, which is exactly the access pattern. The second is cheap retention: dropping old data is dropping an old partition, which is a file deletion, not a row-by-row delete that generates vacuum work. A brokerage that must retain seven years of trades for regulatory reasons can keep recent partitions hot and archive old ones to cold storage, all by partition.
The choice between them is driven by the query pattern, not by preference. A dedup table is keyed and looked up by UUID, so hash fits. A trades table is queried by time window, so range fits. The outbox is queried by publication state, so list (NULL versus default) fits. The unifying principle is that the partition key must be the axis the workload filters on, and the strategy must be the one whose pruning matches that axis. A senior engineer reads the query pattern first and lets it choose the partitioning, rather than picking a favorite strategy and forcing the queries to match.
Defending the design
When an interviewer asks how you would partition a fast-growing dedup table, the defense starts with the goal: even distribution and query pruning on the key you always filter by, which is the UUID. Then the choice: hash partitioning on the UUID column, because the native C hash function is faster than a computed list key, and because partitioning by a real column preserves the primary key, which keeps global uniqueness and logical replication. Then the size: sixteen partitions balances pruning granularity against planning overhead, and can grow.
The follow-up on indexes is: b-tree unique on the id, because the benchmark showed hash indexes are not faster and lose uniqueness and range support. The default is the right call here, measured.
The follow-up on scale is: if the table must be distributed across machines rather than partitions of one database, use consistent hashing with virtual nodes so that adding or removing a node moves a fraction of keys, not all of them. And if the system needs explicit control over placement, as a Redis-style cluster does, use fixed hash slots with staged migration.
The unifying principle is that partitioning and sharding decisions live in the details of function cost, key constraints, and movement semantics. The benchmark is the evidence, the primary-key constraint is the structural guardrail, and the movement property is the scaling criterion. A senior engineer defends each choice with the specific reason it wins for this workload, not with a generic preference.
Mastery Questions
Question
In the Trade Republic UUID dedup benchmark, why did hash partitioning beat list partitioning on a computed key for inserts?
Answer
Hash partitioning uses a hash function implemented in C inside the database engine, which is fast. List partitioning on a computed key requires deriving the partition number in SQL per row, which for a UUID means casting it to text and running LEFT and LOWER string functions. That per-row expression cost is higher than the native hash, so at high insert volume hash partitioning delivered higher TPS and lower latency.
Sources & evidence7 claims · 1 cited
Hash-vs-list benchmark, primary-key forfeiture, and hash-index size claims backed by Trade Republic partitioning source; consistent hashing rings, virtual nodes, and fixed-slot comparison is internal-reasoning.
- For a UUID dedup table partitioned into 16 partitions, hash partitioning outperformed list partitioning on inserts with higher TPS and lower latency, because hash uses a C-implemented hash function while list on a computed key requires a UUID-to-text cast plus LEFT and LOWER functions per row.verified
- List partitioning on a computed partition key forfeits the ability to put a primary key on the parent table because PostgreSQL partition keys cannot include expressions; hash partitioning on the real UUID column keeps the primary key, which matters for global uniqueness and logical replication.verified
- Using hash indexes (EXCLUDE USING hash) instead of b-tree was not faster for equality lookups but reduced index size by under 5 percent; the benchmark reinforced that the optimized built-in b-tree default deserves measurement before assuming a specialized structure wins.verified
- Consistent hashing places nodes on a ring by hashing their identifiers and assigns a key to the first node clockwise, so adding or removing one node moves roughly one over N of keys rather than nearly all; virtual nodes balance load by placing each physical node many times.internal reasoning
- Consistent hashing redistributes keys implicitly and balanced on membership change, fitting caches and Dynamo-style stores, while fixed hash slots (Redis Cluster) divide the keyspace into a fixed slot count and reassign explicit slots, fitting systems needing placement control and staged migration.internal reasoning
- Once a table is partitioned, every query must include the partition key in its predicate or the planner cannot prune and scans every partition, so the partition key must be the column the workload always filters on.internal reasoning
- Sharding by hash of key modulo the node count is catastrophic for a cache because adding or removing one node changes the modulo for nearly every key, evicting the whole dataset; consistent hashing limits movement to a fraction.internal reasoning
Cited sources
- Postgres partitioning performance: Hash vs. List · Trade Republic Engineering (Sadeq Dousti)