Partitioning strategies

There are three commonly used strategies for deciding how to split data across charts: lookup, range, and hash.

Imagine a global social media platform called FaceTool, similar to Facebook. As user traffic grows, the system can no longer store all user data on a single database server. To scale, the team decides to partition data across three charts. More charts can be added later.

Each user’s data must be moved to one of these three charts. The question becomes: how do we assign a user to a chart?

The lookup strategy uses a mapping where each key is assigned to a specific chart.

In a user table, a new column—chart identifier—is added. This column is populated for all existing users, historical data, and new users during sign-up.

For example, a random chart is assigned to every user. This assignment is applied consistently across all data.

The strategy offers strong control over chart assignment.

We can assign charts randomly, which often results in a nearly even distribution of data.

Or we can implement intelligent assignment—such as measuring each chart’s capacity and assigning users to the least utilized chart.

This idea will be explored further in the course under cell-based architecture.

A key drawback is the hard dependency on the mapping.

Every read or write request must perform a lookup to determine which chart holds the user data.

This is where the strategy gets its name—due to the required lookups.

In practice, teams often build a dedicated lookup service to cache the mapping.

This service speeds up lookups but introduces new challenges:

• How to ensure the lookup service is always available?
• How to make it fast?
• How to scale it?
• How to maintain consistency?

These questions relate to availability, performance, scalability, and consistency.

The mapping itself can grow large over time and may require partitioning.

This is a common issue in large-scale systems.

While these technical challenges can be solved, they highlight the trade-offs of the lookup strategy.

The range strategy assigns each chart a continuous range of keys.

For simplicity, use the user’s last name as a key.

In reality, a unique user ID would be used.

Each chart is responsible for a range of last names.

For example:

• First chart: last names starting with A to H
• Second chart: last names from I to Q
• Third chart: last as needed

With this setup, no lookup service is needed.

If we know the user’s last name and the partition boundaries, we can directly identify the correct chart.

The range strategy is easy to implement.

It is especially effective for applications that frequently perform range queries.

A system often needs to retrieve all orders placed in a specific month.

Each chart stores data for one month.

When a range query is issued, the system retrieves data from a single chart only.

If data is partitioned by order ID, orders from the same month are spread across multiple charts.

This makes range queries inefficient because data must be fetched from many charts.

Partitioning by order ID creates imbalance.

One chart may handle significantly more load than others.

This leads to the hot chart problem.

Partition data by user's last name.

Instead of using only the first letter, use the full last name string.

Compute a hash value from the string.

Assign ranges of hash values to each chart.

• Evenly space hash boundaries
• Use consistent hashing (discussed later)

Each chart stores users whose hash value falls within its assigned range.

This structure resembles the range strategy.

The hash function distributes data more evenly.

Two last names starting with the same letter may produce different hash values.

In range partitioning, such users end up on the same chart.

In hash partitioning, they are likely assigned to different charts.

This results in more uniform data distribution.

Hash strategy eliminates efficient range queries.

Computing the hash adds overhead.

This overhead may become critical in high-load systems.