Learn

Architecture & pattern guides

Read the idea, build it on a Grid, prove it in a challenge. Short, practical guides — illustrated with RodGrid's own nodes — on system design, design patterns, flow modeling, and how to get the most out of the app.

All articles

Shard routing and the shard map

Where the decision from key to shard is made (in a client library, a proxy tier or a directory service), a computed map versus a lookup directory that moves one tenant by changing one row, how routers learn that the map changed, why a shard must refuse keys it no longer owns, and the router as one more hop that can fail.

A lookup before every query

A help-desk product serves 38,000 companies, each a tenant with its own agents and tickets, and its ticket store is split across 12 PostgreSQL shards by tenant_id. Why it was split, and why by that key, belongs to Sharding & partitioning. Once it is split, every request carries a question it never had before: which shard is this tenant on? It is answered thousands of times a second, before a single ticket is read, by the shard router.

The router needs two things: the key, which every request must carry (here every URL and API token names the tenant), and a shard map, the data that turns a key into a shard. Where the router runs and what the map is are separate decisions, and both decide what happens when the map changes.

Three places to put the decision

  • Inside the client library. The application's driver holds the map and connects straight to the right shard. No extra hop, but every process keeps its own copy of the map, and changing how routing works means upgrading every service. Redis Cluster clients work this way, caching which node serves each of the 16,384 hash slots.
  • In a proxy tier. The application connects to a router process that looks like one database and forwards each query to the shard that owns it, as MongoDB's mongos and Vitess's VTGate do. The map has a handful of holders instead of thousands, at the price of a network hop on every query and one more fleet to run.
  • Behind a lookup service. The router, wherever it runs, asks a directory where a key lives, and caches the answer.

These combine. The help desk runs six router instances in a proxy tier, and they consult a directory.

One request, one shard

The router finds tenant 4471's shard in the directory, usually from its cache, and sends the query to that shard alone. The other shards serve other tenants.

A formula or a table

The map can be a formula: a short list of range boundaries (tenants 1 to 3,200 on shard 1, and so on), or a hash of the tenant_id into a fixed number of slots plus a small table of which shard holds each slot. Either way every router holds the whole map and routes without asking anyone. Which split suits which queries is in Sharding & partitioning; why plain hash % N moves most keys when a shard joins, in Consistent hashing.

The help desk chose a directory instead: one row per tenant naming its shard, 38,000 rows that every router caches. It paid off when a telecom with 900 agents outgrew the other 3,000 tenants on its shard together. Under a hash formula, moving one tenant means moving its slot and every tenant in it; with the directory, the team copied the telecom's tickets to a shard of its own and changed one row. (The copy and the cutover are the hard part of any move; Sharding & partitioning walks through them.) The price is one more piece of state that must be right and readable whenever anything routes, and that grows with the number of keys: a row per tenant is cheap, a row for each of hundreds of millions of end users is a database of its own. Directories suit coarse keys such as tenants, often as a short list of overrides on top of a formula.

One copy of the map is old

At 02:10 a page reaches the on-call engineer: agents at tenant 4471 say the replies they write keep vanishing on refresh, and some come back a minute later. The tenant had been moved that evening, from shard 07 to a new shard 12.

  1. At 01:55 the migration finishes copying tenant 4471 to shard 12, and the directory row changes from 07 to 12.
  2. Five routers receive the change notification and drop their cached entry.
  3. The sixth router missed the notification; its cache says 07 until the entry expires an hour later.
  4. About one request in six from the tenant's agents reaches that router, which sends it to shard 07.
  5. Shard 07 still holds the old copy of the tenant's tickets, not yet deleted, and serves the request, so a reply written through that router lands in a copy no other router reads.

The map was right; one copy of it was old. Cached in six routers, or in thousands of client processes, some copy will sooner or later be old, so routers need ways to hear about a change, and the system has to stay correct when one does not. They can poll the directory every few seconds, which keeps a copy at most about one interval behind while the polls succeed. They can subscribe to changes, for example by watching a coordination store such as ZooKeeper or etcd, which usually updates sooner and leaves exactly the gap above if a router whose watch broke does not re-read the map when it reconnects. Or they can learn on error, from the shard itself.

The third is what makes a stale map safe instead of merely rare. Each shard knows which keys it owns and refuses the rest. Had shard 07 answered "not mine, try shard 12" instead of serving the old copy, the stale router would have refreshed its entry and retried. Redis Cluster does this with its MOVED reply, which names the node that now serves the slot. MongoDB's routers attach a routing version to the operations they send, and a shard that detects stale routing can reject the operation, so the router refreshes its table and retries. The router's map becomes a fast guess; the shard's check of what it owns keeps the data correct whatever any router still believes, provided ownership changes in step with the cutover.

The fix that night was to restart one router; the fix the following week was the ownership check, so a router that misses a notification now costs a redirect and a retry, not a split copy of a customer's tickets. The same check lets routers ride out a directory outage: they keep routing from their last copy, even past its usual expiry, and a stale entry is refused instead of served, though the retry finds the new shard only if the refusal names it, as MOVED does. What a directory outage still stops is a router with no copy, such as one that has just restarted, so the directory is replicated and a new router loads the whole map before it takes traffic. A proxy tier also adds a hop to every query; holding only cached state, its routers run behind a load balancer, and losing one loses capacity, not data.

No router can place a request that does not carry the key. The help desk's inbound email gateway receives a message to support@clinic.example and has to find which tenant owns that address. It can ask every shard and merge the answers (Scatter-Gather), or first look the address up in a table keyed by address; that table, and keeping it in step, is Index Table.

Drawing the router

The Sharding Challenge's first requirement is this article's subject: "Model the shard router that maps a shard key to its partition". Put the Sharding node between a Client and the Data Store shards and decide what its map is: ranges or slots written on each shard's edge, or a directory Data Store beside the router. Then answer "Note how a hot or oversized shard is split or rebalanced" from the router's side: add the shard that takes over part of the load, mark the range or tenant it now serves, and work out where a router holding the old map would send that key, and what stops the request there. For the rest of the brief, from choosing the key to the replicas behind a shard, go back to Sharding & partitioning.

Practice this