Partitioning

In the previous page, we moved ShortLink's files close to users with a CDN. But the data behind ShortLink keeps growing, and one big table is starting to hurt. In this page, we fix that by splitting the data into smaller parts. This is partitioning.

Definition

Partitioning means splitting one big set of data into smaller parts, called partitions. Each row of data goes to exactly one partition.

Analogy: a library with one giant shelf of books. Finding anything takes forever. So the library splits books into sections: A-F, G-M, N-Z. To find a book, you go to one section only.

To the application, it still looks like one table. Inside, the data is split.

Click to zoom

Let's see why one big table breaks.

Need for Partitioning

Here is what breaks. ShortLink now stores 2 billion short links. Each row is about 500 bytes.

12,000,000,000 rows × 500 bytes = 1,000,000,000,000 bytes = 1 TB

One terabyte in one table causes real problems:

• Slow lookups. Even with an index, a huge index may not fit in memory, so the database reads from disk.
• Slow maintenance. Backups, index rebuilds, and deleting old data take hours.
• One machine limit. The whole table must fit on one disk, and one server must handle every query.

Splitting helps. With 8 partitions, each one is small:

11 TB / 8 partitions = 125 GB per partition
22 billion rows / 8 = 250 million rows per partition

Each partition has a smaller index, a faster backup, and less data to search. Old data can also be removed by dropping a whole partition, instead of deleting rows one by one.

Next, let's see how a row finds its partition.

How Partitioning Works

The idea has two steps:

1. Choose a rule that decides which partition owns a row.
2. Route every read and write to the right partition using that rule.

1Write: "abc123" → rule → Partition 2 → save there
2Read:  "abc123" → same rule → Partition 2 → read from there

The rule is the heart of partitioning. The same input must always give the same partition. Otherwise we write a row in one place and look for it in another.

A router (a small piece of logic, in the database or in our app) applies the rule on every request.

The rule needs something to look at. That something is the partition key.

Partition Key

The partition key is the column the rule looks at to pick a partition. Choosing it is the most important decision in partitioning.

ShortLink's links table has these columns:

1short_code | long_url | user_id | created_at | click_count

Any of these could be the key. Each one gives a different result:

A good partition key has three qualities:

• Spreads data evenly. No partition becomes much bigger than the others.
• Spreads traffic evenly. No partition gets most of the requests.
• Matches the common query. The most frequent query should know the key, so it visits one partition.

For ShortLink, the most common query is the redirect: "given abc123, find the long link." So short_code is the best key.

Now, where do these partitions actually live?

Types of Partitioning

Partitions can live in two different places.

Partitioning inside one database. The database splits a table into parts, but everything stays on one machine. Most databases support this by themselves. It helps with speed and maintenance, but it does not remove the one-machine limit.

Partitioning across many machines. Each partition lives on a different machine. Now both data and traffic are shared by many machines. This is called sharding, and it is our next page.

1Inside one database:   [ One machine: Partition 1 | Partition 2 | Partition 3 ]
2Across machines:       [ Machine 1: Partition 1 ] [ Machine 2: Partition 2 ] [ Machine 3: Partition 3 ]

Partitioning is also used outside databases. Kafka splits a topic into partitions, and caches split keys across servers. The idea is always the same: split by a key.

Next, we need to know which way to cut the data.

Horizontal vs. Vertical Partitioning

There are two ways to cut a table.

Horizontal partitioning splits by rows. Each partition has the same columns, but different rows.

Vertical partitioning splits by columns. Each part has the same rows, but different columns.

1Original:
2short_code | long_url | user_id | created_at | description (large text)
3 
4Horizontal (split rows):
5Partition 1: rows for short codes a-m   (all columns)
6Partition 2: rows for short codes n-z   (all columns)
7 
8Vertical (split columns):
9Table A: short_code | long_url | user_id | created_at
10Table B: short_code | description

When people say "partitioning" in system design, they almost always mean horizontal partitioning. This page continues with that meaning.

Now, how do we choose which rows go to which partition?

Partitioning Strategies

A strategy is the rule that turns a key into a partition. There are four common ones. Each has its own page:

• Range Partitioning

  Each partition owns a range of key values. For example, short codes starting with a-f go to Partition 1, g-m to Partition 2, and so on. Range queries are easy, but traffic can pile up on one range.

• Hash Partitioning

  Run the key through a hash function (a formula that turns any input into a number), then use the number to pick a partition. For example, hash(short code) mod 4. Data spreads evenly, but range queries become hard.

• List Partitioning

  Assign fixed groups of values to partitions. For example, links from India go to Partition 1, and links from Europe go to Partition 2. Easy to understand, but groups can be uneven in size.

• Composite Partitioning

  Combine two strategies. For example, split by month first (range), then split each month by hash. Powerful, but more complex.

Here is the difference for ShortLink, using 4 partitions:

1Range (by first letter of short code):
2abc123 → starts with "a" → Partition 1
3mno456 → starts with "m" → Partition 2
4 
5Hash (hash mod 4):
6abc123 → hash 7  → 7 mod 4 = 3 → Partition 3
7mno456 → hash 10 → 10 mod 4 = 2 → Partition 2

Here is the hash idea in code:

public class PartitionRouter {
    private final int partitionCount;

    public PartitionRouter(int partitionCount) {
        this.partitionCount = partitionCount;
    }

    // Hash partitioning: same key always gives the same partition
    public int hashPartition(String shortCode) {
        return Math.floorMod(shortCode.hashCode(), partitionCount);
    }

    // Range partitioning: first letter decides the partition (a-z split into equal groups)
    public int rangePartition(String shortCode) {
        char first = Character.toLowerCase(shortCode.charAt(0));
        int position = Math.max(0, Math.min(25, first - 'a'));
        return position * partitionCount / 26;
    }
}

For ShortLink's redirects, hash on short code is the natural choice. Every lookup is an exact key, and we want even load.

Click to zoom

But even a good strategy can go wrong. Let's see how.

Hot Partitions and Skew

Skew means the data or traffic is spread unevenly. A hot partition is a partition that gets far more load than the others.

Here is what breaks. Say we partition by creation date using ranges, one partition per month:

1Partition: January   → old links, few clicks
2Partition: February  → old links, few clicks
3Partition: March     → today's partition: ALL new links are written here ✗

Every new link goes to the newest partition. It is overloaded, while the others sit idle. Having 12 partitions gives no benefit for writes.

Another case: partitioning by user_id. One company creates 50 million links through our API. Their partition becomes huge and busy, while other partitions are small.

Traffic can also be uneven with a perfect key. One viral link, sl.io/abc123, gets 100,000 clicks per second. Whatever partition holds abc123 is hot, however evenly we spread the rest.

1Even partitions:   25% | 25% | 25% | 25%   ← healthy
2Skewed partitions: 70% | 10% | 10% | 10%   ← one hot partition ✗

How to reduce skew:

• Pick a high-variety key. A key with many different values spreads better, like short_code instead of country.
• Use hash, not range, when the range keys follow time or growth.
• Add a random part to a hot key. For a famous key, store extra copies under names like abc123-1, abc123-2, and read from one at random.
• Cache hot keys. A viral link is better served from a cache or the CDN than from the partition.

Now, does the way we split affect how we read data?

Queries and Partitioning

Yes. Partitioning makes some queries faster and others slower.

Query that knows the key. It goes to exactly one partition.

1"Find the long link for abc123"
2→ hash(abc123) mod 4 = 3 → read only Partition 3 ✓

Query that does not know the key. It must ask every partition and combine the answers. This is called scatter-gather.

1"Show all links created by Alice"   (partitioned by short code)
2→ ask Partition 1, 2, 3, 4 → gather results → combine ✗

Here is the cost in numbers. Say one partition answers in 10 ms:

1One partition:     10 ms
2All 4 partitions:  the slowest one decides → 10 ms or more, plus 4× the work
3All 100 partitions: one slow partition slows the whole query

Scatter-gather uses more resources and gets slower as partitions grow. The more partitions, the worse it gets.

Ways to handle it:

• Choose the key for your main query. For ShortLink, redirects are 99% of traffic, so we optimize for them.
• Keep a second copy of the data, partitioned by another key. For example, a separate table partitioned by user_id for "show my links". The cost is extra storage and keeping both copies in sync.
• Avoid joins across partitions. A join between two tables with different keys must move data between partitions.

The rule: design the partitions around your most common queries.

And what happens when we need more partitions?

Rebalancing Partitions

Here is what breaks. ShortLink grows, and 4 partitions are not enough. We want 5. With hash mod N, changing N changes almost every answer:

1hash(abc123) = 7
2With 4 partitions: 7 mod 4 = 3 → Partition 3
3With 5 partitions: 7 mod 5 = 2 → Partition 2   ← moved ✗

How many keys stay in place when going from 4 to 5?

1A key stays only if (hash mod 4) equals (hash mod 5).
2This is true for 4 out of every 20 hash values → 20% stay.
3About 80% of all rows must move to a new partition ✗

Moving 80% of 1 TB means moving about 800 GB while users are reading and writing. That is slow, risky, and expensive.

There are two common fixes:

• Create many small partitions at the start. Make 64 partitions even if we have only 4 machines. Each machine holds 16 partitions. When we add a machine, we move whole partitions, not individual rows. The rule hash mod 64 never changes.
• Use consistent hashing. A method designed so that adding a part moves only a small share of the data. We cover it in its own page, after Sharding.

1Fixed 64 partitions, 4 machines:   16 partitions each
2Add a 5th machine:                 move about 3 partitions from each machine to the new one
3Rows are never re-hashed. Only whole partitions move ✓

So partitioning is powerful, but not free. Let's list the costs.

Limitations and Trade-offs of Partitioning

1. The key is hard to change. If we pick a bad key, fixing it means moving all data. Choose carefully at the start.

2. Some queries get slower. Queries without the key must visit every partition.

3. Hot partitions. Uneven data or traffic can make one partition a bottleneck.

4. Joins and multi-row updates get harder. Rows in different partitions are harder to join, and updating them together safely is difficult.

5. Rebalancing is painful. Adding partitions moves data, and a wrong rule can move almost everything.

6. More complexity. More parts to monitor, back up, and understand.

7. Partitioning alone does not fix everything. If all partitions sit on one machine, we still have the one-machine limit.

When to use it:

• Tables with hundreds of millions of rows or more.
• When old data should be dropped by time.
• When one machine can no longer hold the data or handle the traffic.

When to wait:

• Small tables. A normal index is simpler and enough.

Summary

1Partitioning → split a big set of data into smaller parts
2→ Needed because one huge table gets slow, hard to maintain, and too big for one machine
3→ A rule on the partition key sends each row to exactly one partition
4→ Good key: spreads data, spreads traffic, and matches the most common query
5→ Can live inside one database or across many machines (sharding)
6→ Horizontal splits rows, vertical splits columns
7→ Strategies: range, hash, list, composite
8→ Skew creates hot partitions, so avoid time-based keys and add caching for hot keys
9→ Queries without the key must visit every partition (scatter-gather)
10→ Hash mod N moves most rows when N changes, so use many fixed partitions or consistent hashing
11→ Limits: hard-to-change key, slower non-key queries, more complexity

ShortLink's data is now split into smaller parts, but they may all still sit on one machine. Putting each part on its own machine, so both storage and traffic scale, is sharding, our next topic.