CSE Roadmap

Core tier · about 4 hours · 8 parts

Part 7 of 8 · 4 min read

Review checklist and living with the choice

Questions to ask of any shard key, what to do when it is wrong, and cross-shard work.

Review checklist and living with the choice

Think of a pilot's checklist: nothing in it is clever, and everything on it has been the cause of an accident.

A checklist for any shard key:

  1. List the queries. Write the five most frequent reads and writes, with rates.
  2. Check locality. For each, does it name the key? How many shards does it touch?
  3. Check spread. Does the key have high cardinality? Will any value dominate? Do writes arrive in key order?
  4. Look for hot keys. Which entities could become very popular? What is the plan (cache, sub-keys, dedicated shard)?
  5. Check immutability. Can the key change? If so, what happens to the record?
  6. Check size growth. How big can one key's data grow? Is a bucket needed?
  7. Plan cross-shard work. Joins, secondary indexes, reports, transactions that span shards.
  8. Plan for change. How many partitions at the start, and how will data move (module 5 and 6)?

Cross-shard joins and transactions. A query that joins data on different shards needs one of three answers: denormalise so the data sits together; run the join in the application with several calls; or use a warehouse for analytic queries. A transaction touching two shards is much more costly than one on a single shard, since it needs coordination (Level 5 covers this). A good key makes most transactions single-shard: put an order and its lines together, and a user and their settings together.

Resharding. If the key proves wrong, the cost is large: all data must be re-read and rewritten under a new key while the system runs. A common way is to build the new layout beside the old, copy and keep in step with the change log (module 1), switch reads, then writes, then retire the old copy. It can take weeks. The cheaper fix is to choose well at the start and to allow room (many partitions).

A worked example of choosing for a ride-sharing app.

Data Main queries Key Reason
Rider and driver profiles By id Hash of user_id Even, local
Trips A rider's history, a driver's history, trip by id (rider_id, trip_id), with driver history in a second table keyed by driver Two histories need two keys, so keep a copy
Driver location Latest location of drivers in an area Geographic cell id, with time bucket Nearby search is by area; popular cells (a stadium) need splitting
Payments By trip, by user trip_id; user view via a secondary table Keep a payment with its trip

The trips row shows that sometimes the best answer is a second copy of the data under another key (denormalisation), kept in step by the application or by a change feed.

Interview angle

Answer in your head first, then open it.

What would you use as the shard key?

Name the key, then the five main queries and how many shards each touches. Mention cardinality and write spread.

What if one customer is huge?

The celebrity problem: cache, sub-keys, or a dedicated shard. Give the numbers.

How do you handle a query that does not use the shard key?

A global secondary index or lookup table, a second copy keyed differently, or scatter/gather for rare queries.

How do you handle joins and transactions?

Choose the key so that related data is together. Denormalise. Avoid cross-shard transactions where possible.

What if the key turns out wrong?

Resharding by building a new layout beside the old, copying with the change log and cutting over. Avoid it by starting with many partitions and a careful key.

Chat history: how do you shard it?

Partition by channel id and sort by message id, with time buckets for giant channels.

Check yourself:

  • Why can a second copy of the data under a different key be the right answer?
  • Name three things on the checklist that would have caught a timestamp-first key.

Words you will meet

Word Plain meaning
Shard key, partition key The field whose value decides the shard
Cardinality The number of distinct values a field takes
Sort key (clustering key) The field that orders records inside a partition
Compound key A key of several parts: the first picks the shard, the rest sort
Time bucket A slice of time (day, week) put in the key to bound a partition
Celebrity problem A very popular key overloads its shard
Denormalisation Storing copies of related data together to avoid joins
Lookup table A small separate store mapping one field to another, such as email to id
Resharding Changing the key or the number of shards and moving the data
Roll-up Summarising old detailed data into coarser data
Retention How long data is kept before deletion