Data partitioning and sharding

01Partitioning and sharding: definitions

Data partitioning divides a dataset into smaller parts. Sharding is horizontal partitioning across separately managed storage groups. Horizontal means dividing records rather than splitting fields of each record. Each shard owns a subset of rows or records; ownership means that a designated storage group is responsible for those records and decides which writes it accepts. Replication instead creates copies of the same records. You can shard orders by customer and also replicate each shard; one choice divides ownership and the other protects each owner's data.

Suppose a shop stores one billion orders and its single database cannot meet the required storage or throughput. Before splitting, inspect inefficient queries and unused indexes; sharding adds routing, movement, and cross-shard complexity. When splitting is justified, choose a partition key: a field or combination of fields used to determine ownership.

Our example has customers C12, C27, and C44, and orders O1 through O6. Most screens ask for one customer's recent orders. That query suggests keeping a customer's records together rather than scattering every order randomly.

02Horizontal, vertical, functional and directory partitioning

Dividing a dataset involves two choices: what to separate, and how to find each part. Horizontal, vertical and functional partitioning describe what is separated. A directory describes how requests find the owner of a part.

Horizontal partitioning divides rows of the same kind: some customers' orders on shard A and others on B. Range partitioning, which groups rows by intervals of a key, is one horizontal method, not another name for all horizontal partitioning.

Vertical partitioning divides columns or attributes. A frequently read account profile might be separate from large optional biography data. Functional partitioning separates different responsibilities or datasets, such as orders, catalog, and billing. Both can reduce unnecessary work, but a user operation that needs separated data must combine it somewhere.

Directory-based placement keeps a lookup from a logical group to its physical owner. For example, a directory can map tenant T7, a customer organization sharing the service, to shard B, allowing T7 to move later without changing its identity. The directory becomes important routing metadata: cache it carefully, version it, and make stale routes detectable rather than treating it as an infallible box.

03Worked example: place and query six orders

Now apply horizontal partitioning to the orders example: keep every order for one customer on the same shard, so that customer’s order history can be read locally. The router needs a rule that turns a customer number into a shard destination.

For a two-shard example, use customerNumber mod 2. The modulo operation returns the remainder after division by two: even customers go to A, odd customers to B. This simple function is for demonstrating placement, not the final resharding scheme.

A query for C27’s last ten orders computes shard B, then uses a local index on (customerId, createdAt, orderId). It contacts one owner. A report over all customers’ orders cannot identify one shard from that key; it requires fanout, meaning subqueries to the relevant shards followed by a merge, or a separate analytical/read model organized for reporting.

04Choose a shard key and a placement rule

The previous example chose customerNumber as the shard key and used mod 2 as the placement rule. The key supplies the value used for routing; the rule determines its destination. Choosing a rule affects which records stay together and which queries must contact several shards.

Range, hash and list partitioning choose a destination from key values. Round-robin placement cycles through destinations for new records. All four assign whole records to partitions, so they are approaches to horizontal partitioning. Each row below is a separate placement example.

A composite shard key combines fields, such as (tenantId, customerId); it is a choice of key, not a fifth placement algorithm. A system can apply range or hash placement to that combined key. It can also combine rules in stages: choose a tenant's shard group, then hash the customer ID within that group. This gives control over tenant placement while distributing its customers; routing to one customer needs both dimensions.

A further question is how placement changes when machines are added or removed. Separating logical groups of records from physical servers makes those moves easier to manage.

A logical bucket is a named group of keys independent of a physical server. Use many logical buckets and a versioned bucket-to-machine map when machines must change. Directly applying key mod numberOfMachines changes many assignments when the machine count changes. Consistent hashing is another way to reduce membership-related movement, but still requires actual data migration and hot-key handling.

Also inspect cardinality, the number of distinct key values, and frequency, how often each value occurs. Hashing a two-value status field still leaves only two groups; it does not manufacture independently movable keys. Check whether a key grows monotonically, whether one value dominates bytes or traffic, and whether its value can change. Updating a customer’s shard-key value can require moving its records rather than changing one local field. Prefer a stable key when it fits the access patterns.

05Cross-shard joins, transactions and denormalization

A shard key that makes one query local can separate records needed by another operation. This affects both reading related data (joins) and updating related data together (transactions); the examples below show where extra coordination or a stored copy becomes necessary.

Suppose O3 and its order items share C27's partition. A local transaction can update them together on B. If an order also changes globally shared inventory, the customer key does not co-locate that inventory. You now need an explicit transaction or workflow across owners, or a different ownership design.

A foreign key requires a referenced record to exist, such as an order referring to an existing customer. Foreign keys enforce relationships inside the database scope that supports them; do not assume an arbitrary cross-shard reference gets the same automatic enforcement. A deleted customer and retained order may require a clear retention and deletion workflow.

Denormalization stores a useful copy of related data, such as the product name at purchase time. That can avoid a cross-shard catalog join and may correctly preserve the historical receipt. For a field that must reflect the latest value, however, copied data needs updates or a freshness contract. Explain why that copy's meaning is suitable, instead of adding denormalization to every design by reflex.

06Resharding: copy, catch up and transfer ownership

Resharding changes how records are distributed among shards, for example to add capacity or relieve an overloaded owner. For the bucket-based scheme above, a move has two jobs: transfer the data and transfer permission to accept writes. Clients may still use an old route during the change, so the handover needs an explicit protocol.

Imagine bucket 17, containing C27, must move from B to C. A safe outline is:

1. Copy a consistent snapshot from B to C while B remains the write owner. Bind the snapshot to a committed change-log position L0 and retain all subsequent changes, so there is no gap between snapshot contents and replay.
2. Replay subsequent changes so C catches up. Verify record counts/checksums appropriate to the storage model.
3. Briefly coordinate the ownership cutover, fencing the old owner so it cannot keep accepting writes after transfer. Fencing means the storage owner rejects commands whose authority is obsolete; merely updating clients does not stop a paused old writer. Publish routing epoch 9, a numbered ownership version, pointing bucket 17 to C.
4. A client with epoch 8 reaches B. B rejects or redirects the stale route. The client refreshes metadata and retries the same logical operation safely.
5. Retain the old copy until the recovery and stale-client window is closed, then reclaim it.

To switch bucket 17 from B to C, first stop new writes at B and finish or reject writes already running. Record B’s final committed log position; C must apply all changes through it before routing version (epoch) 9 permits writes at C. B then rejects writes using old epoch 8. If the coordinator cannot prove B has stopped accepting writes, it must not enable C. Briefly pausing writes avoids two conflicting histories. A database may use its own consensus or transfer protocol to enforce this handover.

07Interview example: defend a customer shard key

Interviewer: “Why shard orders by customer?”

Candidate: “Most interactive requests list one customer’s orders, so I keep those orders on one shard and route by customer ID. Global reports must query several shards or use an analytical copy. One large customer can still overload a shard, so I measure customer traffic and can split that customer’s data or give it dedicated capacity. To move data, I copy it, apply changes made during copying, then switch write ownership using a new routing version.”

This answer explains placement, the read path, an unfavorable query, and how the system evolves. Merely saying “hash the key” leaves all four undecided.

Choose implementation scope deliberately. PostgreSQL declarative table partitioning can improve pruning and retention management within a database; it does not by itself create a cluster of independently writable servers. If document workloads justify distributed sharding, MongoDB provides mongos routing, configuration metadata and replica-set shards. Its range/hashed placement and zones are product features, while the epoch cutover above is a conceptual protocol to explain ownership—not a claim that MongoDB implements those exact steps or exposes those epoch numbers. Verify supported transactions and constraints for the selected deployment. See PostgreSQL partitioning and MongoDB sharding.

Recall the key ideas

Answer from memory before opening each card. Explain why the choice works and what it costs. Revisit missed cards tomorrow.