Data Partitioning

Data partitioning is process of dividing a large database (DB) into smaller, more manageable parts called partitions or shards. Each partition is independent and contains a subset of the overall data.

In data partitioning, the dataset is typically partitioned based on a certain criterion, such as data range, data size, or data type. Each partition is then assigned to a separate processing node, which can perform operations on its assigned data subset independently of the others.

Data partitioning can help improve performance and scalability of large-scale data processing applications, as it allows processing to be distributed across multiple nodes, minimizing data transfer and reducing processing time. Secondly, by distributing the data across multiple nodes or servers, the workload can be balanced, and the system can handle more requests and process data more efficiently.

Data partitioning can be done in several ways, including horizontal partitioning, vertical partitioning, and hybrid partitioning.

1. Partitioning Methods

Designing an effective partitioning scheme can be challenging and requires careful consideration of the application requirements and the characteristics of the data being processed. Below are three of the most popular schemes used by various large-scale applications.

a. Horizontal Partitioning: Also known as sharding, horizontal data partitioning involves dividing a database table into multiple partitions or shards, with each partition containing a subset of rows. Each shard is typically assigned to a different database server, which allows for parallel processing and faster query execution times.

For example, consider a social media platform that stores user data in a database table. The platform might partition the user table horizontally based on the geographic location of the users, so that users in the United States are stored in one shard, users in Europe are stored in another shard, and so on. This way, when a user logs in and their data needs to be accessed, the query can be directed to the appropriate shard, minimizing the amount of data that needs to be scanned.

The key problem with this approach is that if the value whose range is used for partitioning isn’t chosen carefully, then the partitioning scheme will lead to unbalanced servers. For instance, partitioning users based on their geographic location assumes an even distribution of users across different regions, which may not be valid due to the presence of densely or sparsely populated areas.

b. Vertical Partitioning: Vertical data partitioning involves splitting a database table into multiple partitions or shards, with each partition containing a subset of columns. This technique can help optimize performance by reducing the amount of data that needs to be scanned, especially when certain columns are accessed more frequently than others.

For example, consider an e-commerce website that stores customer data in a database table. The website might partition the customer table vertically based on the type of data, so that personal information such as name and address are stored in one shard, while order history and payment information are stored in another shard. This way, when a customer logs in and their order history needs to be accessed, the query can be directed to the appropriate shard, minimizing the amount of data that needs to be scanned.

c. Hybrid Partitioning: Hybrid data partitioning combines both horizontal and vertical partitioning techniques to partition data into multiple shards. This technique can help optimize performance by distributing the data evenly across multiple servers, while also minimizing the amount of data that needs to be scanned.

For example, consider a large e-commerce website that stores customer data in a database table. The website might partition the customer table horizontally based on the geographic location of the customers, and then partition each shard vertically based on the type of data. This way, when a customer logs in and their data needs to be accessed, the query can be directed to the appropriate shard, minimizing the amount of data that needs to be scanned. Additionally, each shard can be stored on a different database server, allowing for parallel processing and faster query execution times.

2. Partitioning Criteria

Data partitioning criteria are the factors or characteristics of data that can be used to divide a large dataset into smaller parts or partitions. Here are some of the most common criteria used for data partitioning:

a. Key or Hash-based Partitioning: Under this scheme, we apply a hash function to some key attributes of the entity we are storing; that yields the partition number. For example, if we have 100 DB servers and our ID is a numeric value that gets incremented by one each time a new record is inserted. In this example, the hash function could be 'ID % 100', which will give us the server number where we can store/read that record. This approach should ensure a uniform allocation of data among servers. The fundamental problem with this approach is that it effectively fixes the total number of DB servers, since adding new servers means changing the hash function which would require redistribution of data and downtime for the service. A workaround for this problem is to use 'Consistent Hashing'.

b. List partitioning: In this scheme, each partition is assigned a list of values, so whenever we want to insert a new record, we will see which partition contains our key and then store it there. For example, we can decide all users living in Iceland, Norway, Sweden, Finland, or Denmark will be stored in a partition for the Nordic countries.

c. Round-robin partitioning: This is a very simple strategy that ensures uniform data distribution. With 'n' partitions, the 'i' tuple is assigned to partition (i mod n).

d. Composite Partitioning: Under this scheme, we combine any of the above partitioning schemes to devise a new scheme. For example, first applying a list partitioning scheme and then a hash-based partitioning. Consistent hashing could be considered a composite of hash and list partitioning where the hash reduces the key-space to a size that can be listed.

3. Common Problems of Data Partitioning

On a partitioned database, there are certain extra constraints on the different operations that can be performed. Most of these constraints are due to the fact that operations across multiple tables or multiple rows in the same table will no longer run on the same server. Below are some of the constraints and additional complexities introduced by Partitioning:

a. Joins and Denormalization: Performing joins on a database that is running on one server is straightforward, but once a database is partitioned and spread across multiple machines it is often not feasible to perform joins that span database partitions. Such joins will not be performance efficient since data has to be compiled from multiple servers. A common workaround for this problem is to denormalize the database so that queries that previously required joins can be performed from a single table. Of course, the service now has to deal with denormalization's perils, such as data inconsistency.

b. Referential integrity: As we saw that performing a cross-partition query on a partitioned database is not feasible; similarly, trying to enforce data integrity constraints such as foreign keys in a partitioned database can be extremely difficult.

Most RDBMS do not support foreign keys constraints across databases on different database servers. This means, applications that require referential integrity on partitioned databases often have to enforce it in application code. Often in such cases, applications have to run regular SQL jobs to clean up dangling references.

c. Rebalancing: There could be many reasons we have to change our partitioning scheme:

1. The data distribution is not uniform, e.g., there are a lot of places for a particular ZIP code that cannot fit into one database partition.
2. There is a lot of load on a partition, e.g., there are too many requests being handled by the DB partition dedicated to user photos.

In such cases, either we have to create more DB partitions or have to rebalance existing partitions, which means the partitioning scheme changed and all existing data moved to new locations. Doing this without incurring downtime is extremely difficult. Directory-based partitioning keeps an explicit lookup service mapping each key (or key range) to its shard, so moving data only means updating the directory — at the cost of an extra hop on every request and a component that must itself be highly available. Using a scheme like directory-based Partitioning does make rebalancing a more palatable experience at the cost of increasing the complexity of the system and creating a new single point of failure (i.e. the lookup service/database).

d. Secondary indexes: A partitioned table has no free global index. A local (document-partitioned) secondary index lives on each shard and covers only that shard's rows, so any query on the indexed field that is not also the partition key must scatter-gather across every shard. A global (term-partitioned) secondary index is itself partitioned by the indexed term, which makes reads single-shard but turns every write into a distributed write (the row goes to one shard, its index entries to others) that must be kept consistent, usually asynchronously. Choosing between them is the same single-shard-read vs cheap-write trade-off the partition key itself forces.

Worked example: hot shard and resharding cost

Suppose you have 100 million users partitioned across 4 shards by user_id % 4. Under a uniform distribution each shard holds ~25M users and ~25% of traffic. Now imagine one celebrity user drives 40% of all reads; that user's shard now serves 40% + (60%/4) = 55% of total read load. The other three shards sit idle while one is saturated.

This is why modulo partitioning by a skewed key fails in practice. Consistent hashing (with virtual nodes) spreads a skewed key range's load across many physical nodes instead of pinning that whole range to one shard. Know the limit, though: a single hot key still hashes to one point on the ring — virtual nodes cannot split one celebrity key's traffic. That case needs salting (append a random suffix to fan writes across N sub-keys) or dedicated placement for the hot key.

Now consider adding one shard (4 → 5) — the incremental scaling event that happens most often:

• With modulo hashing, the mapping changes from key % 4 to key % 5. A key keeps its shard only if key % 4 == key % 5, which holds for just the residues below the new count — so roughly n/(n+1) = 4/5 = 80% of keys must move. For 100M users that is ~80M moved records.
• With consistent hashing, the new node only steals one arc of the ring from its clockwise neighbor. Roughly 1/(n+1) = 1/5 = 20% of keys move. For 100M users that is ~20M moved records.

At 100 nodes the gap is starker still: adding one node moves ~99% of keys under modulo (100/101) versus ~1% (1/101) under consistent hashing. That difference is the difference between an all-night migration and a routine cluster expansion. (A power-of-two doubling like 4→8 is the one case where modulo is kinder — exactly half the keys stay — but incremental single-node growth, the common case, is where consistent hashing earns its keep.)

Sharding strategy decision table

Choosing a partitioning strategy is a design decision, not a default. The right choice depends on access patterns, key distribution, and operational tolerance.

Hot-partition mitigation

A hot partition is not a theory problem — it is an on-call incident. If one key or one range dominates traffic, the owning node becomes the bottleneck regardless of how many other nodes are idle. Common mitigations:

• Salting. Append a random suffix to a hot key so writes spread across several shards. Reads must then query all salted variants and merge, which trades read cost for write distribution.
• Local caching. Put the hot key in a small in-process or nearby cache with a short TTL. A celebrity profile may be requested millions of times per minute; serving it from memory offloads the shard.
• Read replicas. Direct read traffic for the hot partition to one or more replicas while writes still go to the primary.
• Key redesign. If the hot key is an aggregate (e.g., a global counter), shard by a finer-grained attribute and aggregate at read time.

Resharding trace: from 4 to 8 shards

Suppose a keyspace of user IDs 0–99 is range-partitioned into four shards of 25 IDs each. To go to 8 shards, each shard splits in place into two contiguous halves: the lower half stays where it is, and only the upper half migrates to a newly added node. No key ever jumps between the old shards.

The after-state is 8 shards with ranges 0–12, 13–24, 25–37, 38–49, 50–62, 63–74, 75–87, 88–99. Exactly 48 of 100 keys move (~50%), and that is the floor when the node count doubles: the four new nodes start empty and must end up owning half of all data, so at least half the keys have to cross the wire no matter how clever the scheme. The way to dodge even that is to pre-split into many fixed logical partitions (e.g., 256 partitions spread over 4 nodes, 64 each): keys never change partition, so rebalancing is just moving whole partitions to the new nodes and updating ownership — no split operation, no rehashing, and the move can be throttled partition by partition. This is how Redis Cluster (16384 hash slots), Riak, and Cassandra (vnodes) rebalance.

In a real system resharding is done in phases to avoid downtime: create new shards, backfill data with dual-write, verify consistency, switch reads, then retire old shards. The cutover is the risky step; it is usually coordinated through a routing service or directory.

Cross-shard query example

Consider a query that must count orders placed by users in Europe during the last day. If users are sharded by user_id, the query fan-out looks like this:

1. The router receives the query and identifies the shards that may contain European users.
2. It sends the same filtered query to each relevant shard in parallel.
3. Each shard returns a local count.
4. The router aggregates the partial counts into the final result.

This fan-out is why cross-shard queries are slower and harder to optimize than single-shard queries. If the filter is selective (only a few users), it may be cheaper to look up each user individually by key rather than scanning shards. The general rule: design your partition key so the common queries are single-shard.

When NOT to partition

The first interview follow-up is not "which strategy?" but "would you shard at all?" — and the honest answer is usually not yet. Don't shard when/until:

• One primary still fits with headroom. A single modern node with read replicas comfortably carries low-single-digit-TB datasets and tens of thousands of OLTP queries per second. If your dataset and working set fit that envelope with room to grow, sharding buys you nothing but operational tax.
• Your workload leans on cross-entity transactions or joins. Sharding turns single-node ACID transactions and joins into distributed problems (two-phase commit, fan-out, application-side integrity checks). If those operations are core to the product, sharding breaks more than it fixes.
• The team can't yet operate it. Sharding is a permanent commitment to running a router, a rebalancing process, and cross-shard monitoring. If nobody on call can execute a live reshard, adopting one is adopting an outage.

Exhaust the cheaper levers in order first: cache → read replicas → vertical scaling → partition. Each earlier lever is reversible and operationally simple; partitioning is neither. Shard only when the write volume or dataset size defeats the first three.

Takeaways

• Partitioning buys horizontal scale, but it adds routing, rebalancing, and cross-shard complexity.
• Hash spreads keys; range preserves order; list fits stable categories. Consistent hashing is the usual compromise when nodes join and leave.
• Hot partitions are the first failure mode at scale; cache, salt, or redesign before re-sharding.
• Cross-shard queries require fan-out and aggregation; prefer partition keys that keep hot queries local.