Staggered sharding: misalign the failure domains.

Put a cache in front of a database and the cache absorbs the read load. The question staggered sharding answers is: when a piece of the cache fails, where does its load go?

The naive design shards the cache the same way the database is sharded. It feels clean — Redis cluster k fronts Docstore shard k, the mapping is one to one, a key’s cache home and its database home are found the same way. The problem appears only on failure. If Redis cluster k goes down, every read that would have hit it now misses and falls through to Docstore — and because the sharding is aligned, all of that traffic lands on the one Docstore shard k that backed it. That shard now carries its own normal load plus the entire missed load of the cache cluster in front of it.

It becomes a hot shard: an overloaded database shard, a correlated failure that can take the database shard down too, which makes more of the cache miss, which piles more onto the shard. Aligned sharding makes the cache and the database fail together, one region of the keyspace at a time.

Uber’s design refuses the alignment. The Redis cluster is sharded by a scheme different from the database’s, so the set of keys held by one Redis cluster does not correspond to the set of keys on one database shard. When a Redis cluster goes down, the keys it held are scattered — by the database’s own scheme — across many database shards. The missed load fans out instead of concentrating. No single Docstore shard inherits the whole failure; each absorbs a fraction it can carry.

The principle is general: decorrelate the failure domains. A cache cluster and a database shard are two failure domains; if their boundaries line up, a failure in one maps directly onto a failure in the other. Stagger the boundaries — make the two sharding functions independent — and a failure in one domain disperses across the other instead of striking a single matching unit.

The BCS bus places keys with a scheme too, and it is worth being precise about what that scheme is and is not. EchoMQ pins a queue’s keys to one Valkey hash slot with a hashtag. Every key of a queue is built as emq:{q}:<type> — the queue name sits inside the braces — and Valkey hashes a key only over the substring between the first { and }. So every emq:{orders}:* key hashes to the same slot, one of 16384, decided by the queue name. EchoMQ.Keyspace computes the slot client-side:

The known vector on disk is slot("123456789") == 12739. The full derivation — CRC16 over the braced substring, mod 16384, the cluster-spec algorithm — is R8.03.1; this dive reuses the result, it does not re-derive it.

The connection to staggered sharding is a contrast, not an equivalence. Uber decorrelates two schemes — the cache’s sharding and the database’s are deliberately different, so a cache failure disperses across database shards. EchoMQ correlates one scheme on purpose — a queue’s keys are deliberately pinned to one slot by the {q} hashtag, so a multi-key Lua script over one queue is always a single-slot operation and the queue’s state is co-located.

Staggered sharding is one move with a clear root: do not let the cache’s failure domains line up with the database’s. Shard the cache by a different scheme, and a cache cluster’s failure disperses across many database shards instead of striking one as a hot shard. The BCS bus makes the opposite placement choice with the same kind of deliberateness — the {q} hashtag gathers a queue’s keys onto one slot for atomic scripts. The next dive stops the bus from hammering a node that is failing: the sliding-window circuit breaker, and the connector’s backpressure cousin.