Find the owner of a key

Replication gives multiple copies of the same data. It does not necessarily let each copy hold less data or do less total write work. To divide that work, assign different keys to different owners.

A partition, often called a shard, is a subset of the data with an ownership rule. For the first example, use three non-overlapping ranges of product identifiers. Assume each request touches one product; cross-partition transactions come next.

Route one key through a directory

Partition P1
Keys 0–99
Owner A
Partition P2
Keys 100–199
Owner B
Lookup 127 goes here.
Partition P3
Keys 200–299
Owner C

The directory maps a key range to its current owner. A client finds product 127 without asking every server.

The client consults a directory and sends GET 127 to B. A range query from 90 through 110 crosses P1 and P2, so its execution needs both owners. A point lookup and a range lookup therefore have different routing costs.

Another design assigns hash(key) mod N to one of N partitions. Hashing can spread neighboring identifiers across owners, but a range of identifiers then loses the convenient correspondence to a few contiguous owners. Neither rule guarantees equal load: one very popular key still lands in one partition.

Move ownership without creating two writers

Suppose P2 must move from B to D. Copying its rows while B continues accepting writes produces a moving target. D needs both the initial state and the changes that occurred during the copy.

A simple teaching migration pauses writes to P2, copies a consistent final state, updates ownership, and resumes writes at D. This costs an interruption. A more elaborate migration copies first and catches up a change stream, but still needs a coordinated cutover.

Cached routing creates another problem. A client may send an old request to B after D becomes owner. The old owner must reject or safely redirect it; it must not keep accepting independent writes. An ownership version, checked at the server, helps distinguish stale requests. As with fencing, issuing a number is insufficient without enforcement and safe coordination of the ownership change.

Predict the uneven workload

P1 and P3 each receive 100 requests per second. P2 receives 1,000, of which 900 target product 127. Would splitting P2 into 100–149 and 150–199 necessarily halve the busy owner’s work?

Follow the popular key

No. All 900 requests for key 127 still belong to the same new partition. Splitting can redistribute other keys but does not divide one key’s operations. Caching reads, changing the data model, or serializing a genuinely shared update each involves different promises and tradeoffs.

We can now find one row’s owner. A purchase touching stock and an order on different owners needs a further decision: whether both changes commit together.

Further study: MIT’s distributed-systems course and sharded-service exercises. The ranges and migration procedure above are educational examples.

Extended reference

The extended chapter preserves the original technical coverage, additional examples, and citations. The explanation above supplies the concepts needed for this page; the reference develops the specialist cases.

Find a section from the original chapter