Database Partitioning and Sharding: When One Node Is Not Enough

TL;DR: Sharding splits a single logical database across many physical nodes so you can scale past one machine's CPU, IOPS, and connection limits. Pick a partition key with high cardinality and even distribution. Use hash-based routing unless you need range scans. Pre-shard into many logical partitions (Notion chose 480 for its divisibility^[1]) so you can grow physical capacity without re-bucketing data. Shard only when vertical scaling is truly exhausted: Figma called horizontal sharding "an order of magnitude more complex than our previous scaling efforts"^[2] and took nine months to ship the first table.

Learning Objectives#

After this module, you will be able to:

• Choose between range, hash, and consistent-hash partitioning for a workload
• Pick a partition key that avoids hot spots
• Design a shard-routing layer (client-side, proxy, or vtgate-style)
• Plan a resharding operation with minimal downtime
• Recognize when partitioning is premature and vertical scaling still wins

Intuition#

Imagine a city with one giant central library. Every resident drives downtown to borrow books, return books, and ask questions. At 50,000 residents the parking lot is full, the librarians are overwhelmed, and the building physically cannot hold more shelves.

The city council opens branch libraries. Each branch holds books for a specific set of zip codes. A resident walks into their local branch and finds everything they need without crossing town. The central catalog still knows which branch has which book, but day-to-day traffic is local.

This is sharding. The "zip code" is your partition key. The "central catalog" is your routing layer. The hard part is choosing zip-code boundaries that spread residents evenly, handling the person who visits multiple branches (cross-shard queries), and opening a new branch without closing the others for renovation (online resharding).

Now imagine one zip code contains a stadium. On game day, that branch is crushed while others sit idle. That is a hot partition, and it is the single most common failure mode in sharded systems.

Theory#

Why shard#

A single database node has hard ceilings: CPU cores, disk IOPS, RAM for the buffer pool, and connection slots. Postgres creates a dedicated OS process per connection; between shared memory mappings, work_mem allocations, and per-process overhead, raw Postgres practically tops out in the low hundreds of connections before contention and memory pressure dominate.^[3] Notion hit the largest available RDS instance, faced VACUUM stalls threatening transaction-ID wraparound, and could no longer run safe migrations under load.^[1:1] Figma's tables reached several terabytes and billions of rows, with vacuums causing reliability impact and write rates projected to exceed the IOPS ceiling.^[2:1]

Sharding removes these ceilings by distributing the keyspace across independent nodes. Each shard handles a fraction of the traffic, has its own buffer pool, its own VACUUM schedule, and its own connection budget. But it is a one-way door: you lose cross-shard joins, cross-shard transactions, and globally unique indexes. Make sure vertical scaling and read replicas are truly exhausted first.

Partitioning vs sharding#

The terms overlap but carry different connotations in practice. Partitioning usually means splitting rows across tables or child tables inside one database instance (Postgres PARTITION BY RANGE, MySQL PARTITION BY HASH). Sharding means splitting rows across independent database instances that share nothing at the storage layer.^[4] The two coexist: Notion's 480 logical shards are Postgres schemas inside 32 (later 96) physical RDS instances, which is partitioning inside sharding.^[1:3][5]

Sharding strategies#

Three partitioning families: range preserves locality, hash ensures even distribution, consistent hashing minimizes data movement on membership changes.

Range partitioning. Rows sorted by key are split at boundary values. Good for range scans; pathological for append-heavy workloads where the latest shard becomes a hot partition. Citus explicitly advises: "Do not choose a timestamp as the distribution column."^[6]

Hash partitioning. shard = hash(key) % N. Even distribution by construction; destroys range-scan locality on the hashed column. Figma uses this approach: "As long as we picked a sufficiently random hash function, we would ensure a uniform distribution of data."^[2:3] The downside: hash % N remaps nearly every key when N changes.

Consistent hashing. Karger et al. (1997) map both keys and nodes to a unit circle. Each key is assigned to the first node clockwise. Adding a new node steals only ~1/N of keys instead of nearly all.^[7] Virtual nodes (multiple points per physical node) smooth out variance. The bounded-loads extension (Mirrokni et al., 2016) caps each node at (1+e) times the average load, moving at most O(1/e^2) keys per event.^[8] Vimeo reported an ~8x reduction in shared cache bandwidth after deploying it in HAProxy.^[9][10]

Directory-based. An external lookup table maps keys to shards. Flexible per-tenant placement; the directory is a single point of failure and adds a network hop. Notion uses application-level directory routing from workspace_id to (database, schema).^[1:4]

Geographic. Data partitioned by user region for GDPR data residency or latency. Instagram scaled to multiple data centers this way in 2015-2016.^[11]

Choosing a partition key#

The partition key is the single most important design decision in a sharded system. Every production source converges on the same criteria:

• High cardinality. Enough distinct values to spread evenly across shards.
• Even distribution. No single value dominates traffic.
• Stability. The key does not change after creation (UUIDs, not usernames).
• Present in hot-path queries. If the key is not in the WHERE clause, every query becomes a scatter-gather.

Notion chose workspace_id: UUID-typed, high-cardinality, and naturally scopes the vast majority of reads because users almost always work inside one workspace.^[1:5] Discord chose (channel_id, bucket) where bucket is a static time window so partitions do not grow unboundedly.^[12] Figma chose multiple keys (UserID, FileID, OrgID) because no single column existed in their model, then colocated related tables under each key into a "colo."^[2:4]

The industry pattern for multi-tenant systems is a compound key: (tenant_id, local_id) where tenant_id partitions and local_id is unique inside the tenant. This gives a single unique index per shard that is globally unique without cross-shard coordination.^[6:1]

Resharding#

The dominant pattern is replication-based online resharding: set up new shards, stream data from old to new via logical replication, verify with dark reads, then flip the router.

Notion's 2023 re-shard is the cleanest reference.^[5:1] They moved from 32 to 96 physical databases:

1. Provision 96 new RDS instances
2. Start Postgres logical replication (3 publications per source, 5 schemas each)
3. Copy without indexes (reducing sync from 3 days to 12 hours)
4. Rebuild indexes on new shards
5. Verify with dark reads (1-second setTimeout to wait for replication)
6. Pause traffic at PgBouncer, verify replication caught up, update routing, resume

User-visible impact: "about a second of a 'saving' loading spinner" per shard.^[5:2] Reverse replication was armed the entire time as a rollback escape hatch.

Online resharding: replicate, verify with dark reads, pause briefly at the proxy, flip routing, keep reverse replication as an escape hatch.

Cross-shard queries#

When a query includes the shard key in WHERE, the router sends it to one shard. When it does not, the router must scatter the query to every shard and gather results. Figma's analogy: "like a database-wide game of hide-and-seek: You send out your query to every shard (scatter), then piece together answers from each (gather)."^[2:5]

Scatter-gather latency is bounded by the slowest shard (tail amplification). At scale, "having too many scatter-gathers would impact horizontal sharding scalability. Because the queries have to touch every single database, each scatter-gather contributes the same amount of load as it would if the database was unsharded."^[2:6]

A query with the shard key hits one shard directly; without it, the router scatters to all shards and gathers, bounded by the slowest.

Cross-shard joins require either colocation (both tables share the shard key so rows live on the same shard), reference tables (small tables replicated to every shard), or a distributed join plan (proxy pulls rows from multiple shards and joins in memory).^[6:2]

Cross-shard transactions are the hardest problem. Both Figma and Shopify explicitly removed them rather than rely on two-phase commit. Figma: "we chose not to support atomic cross-shard transactions because we could work around cross-shard transaction failures."^[2:7] Shopify: "We opted to remove all cross shard transactions to avoid any issues."^[14]

Hot keys and multi-tenancy#

Real-world traffic follows a power law. Discord observed hot partitions when a large server with hundreds of thousands of members shared a partition with small servers: "reads are more expensive than writes... Lots of concurrent reads as users interact with servers can hotspot a partition."^[12:1]

Mitigations:

• Request coalescing. Discord's Rust data services layer: "If multiple users are requesting the same row at the same time, we'll only query the database once."^[12:2]
• Compound partition keys. Discord's (channel_id, bucket) splits a single channel's messages across many partitions as it ages.^[12:3]
• Write sharding. DynamoDB pattern: append a random suffix to the hot key (user#42#001 through user#42#099) so writes spread across 100 partitions; reads query all suffixes.^[15]
• Per-key rate limiting. Cap the rate any one key can demand from the database.

For multi-tenant SaaS, three canonical patterns exist: silo (one database per tenant, strongest isolation, highest cost), pool (all tenants share tables with a tenant_id column, lowest cost, noisy-neighbor risk), and bridge (shared database, schema per tenant, middle ground).^[16] Shopify's pod architecture is a pragmatic hybrid: pods are silos of datastores (MySQL + Redis + Memcached + cron) with pooled stateless compute. A pod failure affects only that pod's shops, not the platform.^[17]

Real-World Example#

Figma: from one Postgres instance to horizontal sharding in nine months.

Figma's database stack grew approximately 100x between 2020 and 2024.^[2:8] By end of 2022, they had 12 vertically partitioned Postgres databases, but some tables had billions of rows and several terabytes, approaching the RDS IOPS ceiling.

In late 2022, Figma committed to horizontal sharding. They built DBProxy, a Go service that sits between the application and PgBouncer. DBProxy parses SQL into an AST, extracts the shard key from the WHERE clause, looks up the physical database in a topology stored in S3 and etcd, rewrites the query to target the correct shard's view, and streams the result.^[2:9]

The key innovation was logical sharding via Postgres views:

CREATE VIEW table_shard1 AS
  SELECT * FROM table
  WHERE hash(shard_key) >= min_range
    AND hash(shard_key) <  max_range;

This let Figma test shard routing with a config-flag rollback (seconds) before committing to the riskier physical split. Related tables are grouped into "colos" that share a shard key, so cross-table joins inside a colo remain single-shard.

Figma's logical-to-physical shard mapping: views act as logical shards on a single database, then physical splits move views to dedicated instances without changing application code.

The first horizontally sharded table went live in September 2023 with 10 seconds of partial primary-availability impact and zero replica impact.^[2:10] Figma explicitly rejected CockroachDB, TiDB, Spanner, and Vitess because migrating an existing Postgres stack was deemed riskier than building DBProxy in-house under a hard deadline.

Open problems Figma documents: globally unique ID generation, atomic cross-shard transactions, global unique indexes, and fully automated reshard operations.^[2:11]

Trade-offs#

Common Pitfalls#

Exercise#

Your single Postgres primary hits 85% CPU on writes at 30K WPS and the dataset is 2 TB. You project 5x growth in 18 months. Design a sharding plan: partition key, number of shards, routing layer, resharding strategy, and how you will keep cross-tenant reports working during the migration.

Key Takeaways#

• Sharding is a one-way door. Exhaust vertical scaling, read replicas, and vertical partitioning first.
• Pick the partition key for the worst access pattern, not the average one. High cardinality, even distribution, stable, present in hot-path queries.
• Hash-based routing is the default for OLTP. Use consistent hashing only when the shard set is dynamic.
• Pre-shard into many logical partitions (pick a highly divisible number like 480 or 360). You can grow physical capacity without re-bucketing data.
• Cross-shard joins and transactions are expensive or impossible. Colocate related data under the same shard key.
• Hot partitions will find you. Design so you can add request coalescing, write sharding, or split on short notice.
• Online resharding via logical replication, dark reads, and proxy-level pause-and-flip is the industry standard pattern.

Further Reading#

• Herding elephants: Lessons learned from sharding Postgres at Notion - The canonical "first-time sharder" post-mortem: 480 shards, workspace_id, audit-log migration, and why 480 has many factors.
• The Great Re-shard: adding Postgres capacity (again) with zero downtime - How to reshard live at 32 to 96 Postgres instances using logical replication and a sharded PgBouncer.
• How Figma's databases team lived to tell the scale - DBProxy, logical-vs-physical sharding, colos, views-as-logical-shards, and shadow planning; one of the most detailed sharding write-ups in the industry.
• Sharding & IDs at Instagram - Still the clearest explanation of logical-vs-physical shards and Snowflake-style sharded IDs (41 bits time + 13 bits shard + 10 bits sequence).
• How Discord Stores Trillions of Messages - Hot partitions, data services with request coalescing, Cassandra to ScyllaDB migration, and the (channel_id, bucket) partitioning pattern.
• Partitioning GitHub's relational databases to handle scale - Schema domains, SQL linters, Vitess adoption, and a write-cutover process for 130 tables at 950K QPS.
• Consistent Hashing and Random Trees (Karger et al., STOC 1997) - The original paper; read at least the theorem statement on balance and spread.
• Designing Data-Intensive Applications, Ch. 6 - Kleppmann's canonical textbook treatment of partitioning strategies, rebalancing, and request routing.

Flashcards#

References#