Shard Routing and Ownership Metadata: The Directory That Must Not Disagree

Every partitioned system needs to answer one question before it can answer any other: which machine owns this key. The answer lives in metadata, and the metadata is itself a distributed object that can be stale, partitioned, or contradictory. A routing table that is one epoch behind sends a write to a machine that has already handed the range away. That machine may still have the data and may still accept the write, and the two copies then diverge with no error reported anywhere. The design of the ownership metadata is therefore not bookkeeping; it is the mechanism that makes the boundary between two owners unambiguous.

Three places the routing table can live

The lookup can be performed at three points, and each moves the staleness problem somewhere different.

Client-side caching. The client fetches the mapping and holds it. Lookups cost nothing after the first fetch, which matters when a request path performs thousands of lookups. The cost is that every client’s cache is a copy that can be wrong, and the wrongness persists until the client refreshes. Refresh is triggered either by a periodic poll or by an error returned from a server that knows it is no longer the owner.

A routing tier. A stateless service holds the mapping and answers lookups, with clients addressing the tier by key. The tier’s copies are refreshed centrally, so staleness is bounded by one refresh interval rather than by every client’s cache lifetime. It adds a network hop to every request that misses its own cache, and it adds a service that must be kept available.

A coordination service. The mapping is stored in a strongly consistent store — the role Chubby plays for Bigtable’s tablet locations, and the role of similar services in other designs. Reads are linearizable, so no client ever sees a mapping that was never the current one. The cost is that every lookup is a round trip to a service whose availability is now on the critical path of every request, which is why this pattern is usually paired with caching at one of the two layers above.

The practical combination is a strongly consistent source of truth, a cached copy at the routing tier, and a per-client cache with an error-driven invalidation path. Each layer reduces load on the one below, and each adds a staleness window that the layer above must be able to detect.

Ownership must be a lease, not an assignment

An assignment says “machine B owns range [a, c)”. A lease says “machine B owns it until time T”. The difference appears when the assignment changes: an assignment has no way to tell B that it has been replaced, because B holds the same record it always held. A lease expires on its own, so B stops acting as owner at a known time without needing to hear anything.

This is the same argument as leader fencing, applied per range rather than per cluster. The lease duration must exceed the maximum time the owner needs to notice expiry — including any pause it might take — and it must be renewed against a clock that both sides agree on within a bounded skew. A lease that outlives its own validity on the owner’s clock is worse than no lease, because the owner believes it still holds a right it has lost.

Renewal is a write to the metadata store, so the lease mechanism converts a per-range liveness property into a steady stream of small writes. A cluster with a hundred thousand ranges renewing every few seconds is a metadata workload in its own right, which is why lease durations are chosen long relative to the renewal cost and short relative to the desired failover time.

Epochs make the race detectable

Leases bound the window; they do not eliminate it. Between the moment the new owner is granted the range and the moment the old owner’s lease expires, both may believe they own it. The old owner has the data, the new owner is fetching it, and a client with a stale cache may write to either.

An epoch, or generation number, closes this. Each grant of a range carries a number that increases on every change of owner. Servers reject any request whose epoch is lower than the highest they have seen for that range. The new owner, having received the range with epoch 11, refuses a request carrying epoch 10. A client with a stale cache gets an explicit rejection and refreshes, rather than a silent write to a machine that no longer owns the data.

The property this provides is worth stating precisely: it is not that stale clients cannot reach the old owner, it is that the old owner cannot act on their requests. The rejection is the signal the client needs, and it is the reason the client-side cache design above is workable at all.

range [a, c): epoch 10 -> node-3   (lease until 12:00:05)
range [a, c): epoch 11 -> node-8   (granted 12:00:04)

client with cached epoch 10 -> node-3
node-3 sees epoch 10 < 11 -> rejects with "stale epoch, current is 11"
client refetches, retries against node-8

Two implementation details decide whether this works. The rejection must be distinguishable from a transient error, because the client’s response differs: a stale epoch means refresh and retry, a timeout means retry the same target. And the epoch must be stored with the range’s data, not only in the metadata service, so that a node that has been partitioned from the metadata service still knows what epoch it last held. A node that loses its memory of the epoch has to be treated as untrusted for that range and re-onboarded.

The metadata is a consensus problem in disguise

The routing table is small, read constantly, and written rarely, which tempts a design where it lives in a single server. That server’s failure stops every lookup, and its recovery must reconstruct the table from somewhere. In practice the table is stored in a replicated log with a leader, so that a write to it is a majority-acknowledged append and a read can be served either from the leader or from a follower whose position the client specifies.

The consequence is that range ownership changes are serialised by the metadata log, which is what makes epochs well defined: there is exactly one order of grants, and an epoch number is a position in that order. A design where two metadata servers could independently grant the same range has no total order, and no epoch scheme can repair it.

The metadata’s size matters for a different reason. Every range has a record: boundaries, owner, epoch, replica set. A cluster with a million ranges has a million records that must be replicated and watched by every routing tier. Keeping the table small is therefore a design pressure toward larger ranges, which conflicts with the pressure toward finer granularity for load balancing described in hash and range partitioning. The resolution in most systems is a two-level hierarchy: a small table maps coarse key ranges to metadata shards, and each metadata shard holds the fine-grained records for its own range. The top level is tiny and changes rarely; the second level scales with the data.

When the mapping and the data disagree

The hardest failure is not a stale cache but a metadata record that is correct and a data state that does not match it. Two cases produce this.

A range is granted to a new owner before the old owner’s data has been transferred. The new owner serves reads from an incomplete copy, and writes that arrive during the transfer go only to the new owner. The old owner’s remaining data is then stale. The protocol that avoids this is the one described in online resharding: the new owner catches up from the log, then a cutover is ordered by the metadata log, and only after the cutover do clients with the new epoch reach it. The epoch is what makes the ordering observable.

A range is granted, the new owner accepts writes, and the metadata write is lost because the metadata store failed over and the entry was on the losing side. This is the same durability question as any other write, and it is answered the same way: the grant must be majority-acknowledged before the new owner acts on it. A new owner that begins serving on an unacknowledged grant is a split owner, and the epoch it invents may collide with the real one.

The second case has a subtler variant. The metadata store’s leader fails after the grant is acknowledged by a majority but before the new owner learns of it. The range now has an owner recorded in the metadata and a machine that does not know it owns it. Reads routed to it fail until it discovers the grant, which it does by watching the metadata. This is why the routing design needs a push path as well as a pull path: a client that polls will eventually learn, and a server that watches learns immediately, and the interval between them is an availability gap rather than a correctness one.

What the client must be told

The last piece is the contract with the client, and it is usually under-specified. A client needs to know, for each error, whether to retry the same target, refresh the mapping, or fail. Three signals are enough:

• Not the owner, here is the current owner. A redirect, safe to follow. The server knows the mapping is different from what the client used.
• Stale epoch. The client’s mapping is older than the range’s current grant. Refresh, then retry. This is distinct from the redirect because the client may have the right owner and the wrong epoch, or neither.
• Transient failure. Retry the same target after a delay. Refreshing on a transient error turns a brief overload into a metadata stampede, which is the failure mode that turns a routing tier into a bottleneck.

Collapsing these into one generic error forces the client to guess, and the guesses are wrong in opposite directions: refreshing on every error overloads the metadata store, and never refreshing leaves the client pinned to a dead owner indefinitely. The distinction costs a few bytes in the protocol and removes an entire class of operational failure.