Local vs global secondary indexes in a sharded database: an interactive simulator

A sharded table can only find rows quickly by the key it is sharded on. To look rows up by anything else you need a secondary index, and it can be sharded two ways. A local index lives next to the data on each shard, so writes stay on one shard but every query must ask all of them. A global index is sharded by the indexed value, so a query asks one index shard, but every write now touches two shards and the index usually lags behind.

The playground looks up orders by customer on a table sharded by order id. Each shard usually answers in about 2 ms, but 1% of requests hit a stall of 20 to 60 ms.

What the trade-off looks like

• Local indexes scatter reads. At 16 shards every query is 16 shard requests, 34,000 a second for 2,000 queries plus the writes, and 15% of queries wait on at least one slow shard. At 64 shards it is 130,000 requests a second and nearly half of all queries are delayed: adding shards makes these queries slower and more expensive, not faster.
• Global indexes keep reads narrow. One index shard and the shard holding the order: 2 requests per query whatever the cluster size, and only 2% of queries delayed.
• But writes pay. Each new order also writes the customer’s index shard, a second request, often on another machine. Doing that in the same transaction needs a distributed commit; most systems update the index asynchronously, so a query can miss an order written moments ago.
• Big results erode the advantage. If a query returns 20 orders spread across the cluster, a global index still has to fetch them from up to 20 shards. With only 4 shards that is no better than asking all of them, which is why many designs store the needed fields in the index itself.

Where you meet them

-- local (document-partitioned): each shard indexes its own rows
--   Elasticsearch, MongoDB, Cassandra secondary indexes, DynamoDB local secondary indexes
SELECT * FROM orders WHERE customer_id = 812;   -- scatter to every shard, gather

-- global (term-partitioned): the index is its own table, sharded by the indexed value
--   DynamoDB global secondary indexes, Spanner and CockroachDB indexes
orders_by_customer:  PK (customer_id, order_id) -> order shard
SELECT order_id FROM orders_by_customer WHERE customer_id = 812;  -- one shard
-- then fetch those orders by id from wherever they live

In a system design interview

When a sharded design needs a second access path, say which kind of index it is: “Orders are sharded by order id, and the order history page queries by customer, so we keep a global index sharded by customer id that includes the fields the page shows. It is updated asynchronously from the change stream, so a new order can take a fraction of a second to appear; the confirmation page reads the order by id instead. Rare admin searches by status can scatter-gather across shards.” Expect the follow-ups: what happens to the index when a write fails halfway, and whether the data could be sharded by customer in the first place.

Read the guide to sharding and partitioning or database indexing, see choosing a shard key and tail latency, or watch a strong candidate design DoorDash.

Questions people ask