Lesson 15.4• 10 min read

Serving reads: caching, hot keys and sharding

The primer’s scaled design, how much each cache layer absorbs under skew (λT/(1+λT)), hot keys, and which ways of sharding counts give the right top N.

What you will learn

  • Scale reads with the primer's cache, replicas and warehouse.
  • Work out how much each cache layer absorbs from a page's request rate and TTL.
  • Handle a hot category, and shard rankings without merging partial counts wrongly.

Scaling reads (the primer)

The primer's scaled design:

  • A memory cache handles "traffic for popular content (and their sales rank)", which also absorbs uneven traffic and spikes. With so many reads, "the SQL Read Replicas might not be able to handle the cache misses", so further SQL scaling patterns may be needed.
  • 400 writes per second on average "might be tough for a single SQL Write Master-Slave". The primer points to federation, sharding, denormalization and SQL tuning, and to moving some data to NoSQL.
  • An analytics database (a warehouse such as Redshift or BigQuery) for the computation. Raw data beyond a limited period stays in the object store, which "can comfortably handle" 40 GB a month.

Layers of caching

Rankings change at most hourly in the primer's design, so cached copies stay valid for a long time. You can cache them at several layers:

  1. CDN or shared HTTP cache: send Cache-Control: public, max-age=60 on the category page (RFC 9111, chapter 9).
  2. In-process cache on each app server, with a short TTL.
  3. Redis holding the rankings.
  4. The database with read replicas.

How much does each layer absorb? Suppose a page is requested λ times a second, and each miss caches it for TTwhat its symbols mean seconds. Then each miss is followed by about λT\lambda Twhat its symbols mean hits, so the hit ratio is

λT1+λT\frac{\lambda T}{1 + \lambda T}what its symbols mean

Popular categories are requested often, so they nearly always hit. Rarely viewed ones mostly miss. The visual applies this over the primer's 1,000 categories, with popularity that follows Zipf's law (a few categories get most of the requests), so you can see how skew, TTLs and the number of app servers change the load that reaches Redis. Every cache layer adds staleness of up to its TTL. With hourly rankings, a TTL of a minute costs little.


Hot keys and sharding

A single very popular category is a hot key: all its reads land on the one Redis node that holds it. Caches in front (above) take most of that load, and Redis replicas can share the reads.

Writes can also concentrate: a purchase updates every category the product belongs to. If one category's updates are too many for one node, split them, but think about what each shard holds:

  • Split by product: each product lives in exactly one shard, holding its full count. A category's top NNwhat its symbols mean is then the top NN of the merged per-shard top-NN lists.
  • Split writes for the same product across shards: each shard holds only partial counts. Merging the shards' top lists is now wrong. A product could be just outside the top NN in every shard yet first overall. You must sum each product's counts first (ZUNIONSTORE does this) and then rank. The visual's tests include a case where the shortcut picks the wrong winner.

How much each cache layer absorbs

Reads for 1,000 category pages, with popularity that follows Zipf's law. A TTL cache serving a key requested λ times a second for T seconds hits λT/(1+λT) of the time; each app server has its own in-process cache.

Answered by the CDN39,983 RPS (100.0%)
Answered by app-server caches0 RPS (0.0%)
Reaching Redis17 RPS (0.0%)
The most-requested category still sends 0 RPS to the single Redis node that holds it. With short TTLs, users can see a ranking up to that many seconds old.
Shoppers1× instanceDNS2× instancesCDN (category pages)2× instancesLoad balancer2× instancesRead API9× instancesSales API2× instancesMemory cache2× instancesSQL read replicas2× instancesSQL leader(sales_rank)2× instancesObject store (log files)1× instanceSales Rank Service2× instancesAnalytics database2× instancesShoppers1× instanceDNS2× instancesCDN (category pages)2× instancesLoad balancer2× instancesRead API9× instancesSales API2× instancesMemory cache2× instancesSQL read replicas2× instancesSQL leader(sales_rank)2× instancesObject store (log files)1× instanceSales Rank Service2× instancesAnalytics database2× instances
Figure 4

The primer’s scaled design: a CDN and a memory cache answer most reads, read replicas take the misses, and an analytics database holds the computation.

Follow a read. DNS sends the shopper to the CDN, which answers popular category pages from its copies and passes the rest to the load balancer. The Read API looks the ranking up in the memory cache, and only misses reach the SQL read replicas, which copy the leader. Purchases go to the Sales API, which writes its logs to the object store, and the Sales Rank Service computes the rankings in the analytics database and writes them to the leader. The Read API is counted at the lab’s 1,000 requests a second a server for the reads the CDN leaves, about a fifth of 40,000, plus one spare; the memory cache at 12,000 a second a node, plus one spare. The primer gives no counts for the rest, so each is drawn with two.

  • Shoppers: 1 × Users
  • DNS: 2 × DNS
  • CDN (category pages): 2 × CDN
  • Load balancer: 2 × Load balancer
  • Read API: 9 × App server
  • Sales API: 2 × App server
  • Memory cache: 2 × Cache
  • SQL read replicas: 2 × Read replica
  • SQL leader (sales_rank): 2 × Relational database
  • Object store (log files): 1 × Object store
  • Sales Rank Service: 2 × App server
  • Analytics database: 2 × Relational database
  • Shoppers sends requests to DNS
  • DNS sends requests to CDN (category pages)
  • CDN (category pages) sends requests to Load balancer
  • Load balancer sends requests to Read API
  • Load balancer sends requests to Sales API
  • Read API sends requests to Memory cache
  • Memory cache sends requests to SQL read replicas
  • SQL read replicas keeps a copy of SQL leader (sales_rank)
  • Sales API sends requests to Object store (log files)
  • Sales Rank Service sends requests to Object store (log files)
  • Sales Rank Service sends requests to Analytics database
  • Sales Rank Service sends requests to SQL leader (sales_rank)

Key takeaways

  • Rankings change at most hourly, so cache them at the CDN, in each app server, in Redis and in the database.
  • A page requested λ\lambdawhat its symbols mean times a second and cached for TTwhat its symbols mean seconds hits λT1+λT\frac{\lambda T}{1 + \lambda T}what its symbols mean of the time: popular categories nearly always hit.
  • A hot category's reads land on one Redis node; the caches in front and Redis replicas share them.
  • Splitting by product keeps full counts, so merged top-NNwhat its symbols mean lists are right; splitting one product's counts across shards makes that merge wrong.
Sources4