Caching Links

Every variant has more reads than writes. That alone does not mean a cache helps. In the caching chapter, we judged a cache by its hit ratio. A cache helps when the same entries are read again and again.

Which variants benefit

t.co. Readers of a viral post can send millions of requests to one link. A small number of links receive most of the requests. Those links stay in the cache, so the hit ratio is high. A cache helps.

Drive. A shared document is opened by a team or a class, so each link receives few requests. The 5,000 requests per second are spread across millions of different links. Most requests would miss, so the hit ratio is low. A cache does not help.

O’Reilly. It receives under one request per second. The database handles that, so a cache is not needed.

So we put a cache in front of the database only for t.co. The cache maps each code to its long URL. We use cache-aside: on a miss, the API instance reads the link from the database and stores it in the cache.

Suppose X blocks a link that is in our cache. The link must stop redirecting within minutes during normal operation. The requirements make an exception during a partition. We use both techniques from the caching chapter:

  • Invalidation: when we write the block to the database, we delete the link’s entry from the cache. The next request misses and reads the link’s status from the database.
  • Expiry: we give each entry a time to live of a few minutes. If an invalidation is missed, the entry is still removed when its time to live runs out.

What the server sends for a blocked link is a product decision. X shows a warning page. Any response other than the redirect meets the requirement.

How long a block takes

Browsers also cache the redirect for up to 5 minutes, because the response carries Cache-Control: max-age=300. So there are two places a blocked link can still redirect from: our cache and the browser’s cache. Replication adds another delay, because cache misses read from replicas.

First, assume every replica serving reads has received the block, and no earlier read can still put an old active record into the cache. Under that assumption, once we delete the entry, the API instances stop sending new redirects. A browser may have received a redirect just before we deleted the entry, and it can reuse that redirect for up to 5 minutes. So the remaining delay is at most 5 minutes.

Under the same assumption, if the invalidation is missed, the API instances can keep sending redirects from an old cache entry for up to one time to live. A browser that receives a redirect at the end of that time keeps it for another 5 minutes. With a cache time to live of 5 minutes, the remaining delay is at most 10 minutes.

Those two bounds hold only under the assumption. They do not tell us how long a block takes from the moment we write it to the primary. After we delete the entry, a replica that is behind can return the old active record, and the API instance puts that record back in the cache. An earlier read can also finish after we delete the entry and put the old record back. Expiry does not prevent this: the next miss can reload the same stale record.

To estimate the total delay, include the time until all replicas serving reads have received the block and all earlier reads that could refill the cache have finished. An old entry put in the cache at the end of that period can stay for another 5 minutes. A browser can then keep the redirect for another 5 minutes. So we meet the normal-operation requirement only if the replicas receive the block quickly and the earlier reads finish quickly. During a partition, replicas may keep refilling the cache with the old record, so there is no fixed bound on the total delay. We accept this for t.co because we chose availability.