Directory Sharding

A lookup table, the directory, records which shard holds each key. Nothing about the key decides its shard, so data can be placed and moved however you like: one user at a time, by load, or by any rule. The price is the directory itself: every request needs a lookup, and every copy of the table must be kept up to date. Below, add shards, rebalance a few heavy users, and turn on caching to see a stale copy.

directory: user → shard#1012Shard 1#1029Shard 2#1248Shard 1#1443Shard 2#1506Shard 1#1667Shard 2#1883Shard 1#1900Shard 2#1984Shard 1#2153Shard 2#2242Shard 1#2404Shard 2#2574Shard 1#2752Shard 2#2869Shard 1#3058Shard 2#3128Shard 1#3300Shard 2#3496Shard 1#3625Shard 2#3753Shard 4#3924Shard 4#3928Shard 4#4022Shard 4#4092Shard 4#4303Shard 4#4376Shard 3#4431Shard 4#4493Shard 3#4613Shard 3#4690Shard 3#4754Shard 3#4854Shard 3#4922Shard 3#5097Shard 3#5255Shard 3#5362Shard 3#5513Shard 4#5644Shard 4#5746Shard 4outlined entries were just editedAppShard 1Shard 2Shard 3Shard 4

The panel is the directory: one entry per user, coloured by the shard it points to. Each dot in a shard is one user record, coloured by country. Edit the directory and the records it moves glide to their new shard, ringed so you can count them. A shard turns red when it serves well above its share of requests.

How big the directory gets, and how busy
B
%

  1. 1. One entry per user

    users x bytes per entry = 500M x 16 B = 7.45 GB

  2. 2. One entry per virtual shard

    users hash into 16.4K virtual shards, and the directory maps those: 16.4K x 16 B = 256 KB, small enough for every app to cache

  3. 3. Lookups with no cache

    every request asks the directory: 100K/s

  4. 4. Lookups with a cache

    only misses ask: 100K x 1% = 1,000/s
  5. One entry per user gives full control, down to moving a single user, but the table is large and every change must reach every copy. Mapping virtual shards keeps the table small and cacheable, at the cost of moving users in groups.
Where these formulas come from

Steps 1 and 2 are the storage estimate from the back-of-the-envelope chapter of Alex Xu's System Design Interview, Vol. 1, applied to the directory instead of the data; 16 bytes is roughly a key and a shard number. The 16.4K virtual shards are an example count; mapping virtual shards to physical ones is the approach Azure's sharding guidance describes. Steps 3 and 4 are plain arithmetic.

Limits of directory sharding

Every request needs a lookup

Before reading a record, something must ask where it lives. That is an extra step on every request, unless the answer is cached.

The directory must not fail

If the directory is down, no shard can be found, even though every shard is healthy. It needs replicas and its own care, like any other critical database.

Copies go stale

Caching the directory removes most lookups, but after a move a copy can point at the old shard. Every move must also refresh or invalidate the copies.

Moving data is still work

Editing an entry is instant; copying the records it points to is not. The directory only makes the move possible one user at a time.

How Azure and Vitess use lookups

Azure documents the lookup strategy for whole shards; Vitess uses lookup tables to find rows by a second key.

Azure: the lookup strategy

Azure's sharding guidance describes "the lookup strategy, also called the directory-based strategy", in which "the sharding logic implements a map". It "provides more control over shard configuration", while "Looking up shard locations adds overhead." Moving data includes the step "Invalidate or refresh any caches that hold this data."

Azure SQL: the shard map manager

Azure SQL's elastic database tools keep the directory in a database: "The shard map manager is a special database that maintains global mapping information about all shards". "Each application instance accessing a ShardMapManager object maintains a local in-memory cache of its mappings."

Vitess: lookup vindexes

Vitess usually places rows by a function such as a hash, and adds lookup tables for other columns: "A Lookup Vindex is implemented as a MySQL lookup table that maps a column value to keyspace IDs." The cost, in its words: "an extra write to the lookup table for insert and delete operations, and an extra lookup for read operations."
Sources and credibility

All are official documentation from Microsoft and the Vitess project. Quoted phrases are short attributed quotations; everything else is described in our words.