How Caching works

Before you start

• Interfaces

  The redirect is a primary-key read. That lesson writes the API and the row these blocks serve.

  Open lesson

Why it matters

Short codes are opened hundreds of times a second, but traffic is uneven: a few codes receive most requests and their mappings rarely change. Sending every repeat across the network to the mappings table wastes its limited read capacity and makes visitor latency depend on that table. The database must see well under 10% of redirects even when a handful of codes become hot.

Short codes are looked up hundreds of times a second, and a handful of codes are looked up far more than the rest. The mapping row rarely changes.

Input

capacity = 2, db = {"a": "/docs", "b": "/blog", "c": "/jobs"}, requests = ["a", "b", "a", "a", "c", "a", "b"]

Output

["miss", "miss", "hit", "hit", "miss", "hit", "miss"]

Instead of querying the mappings table for every redirect, cache a → /docs beside the API; in the two-entry example, LRU keeps hot “a” while evicting the least recent code, so only misses reach the database.

The API looks up code “a” in its cache. The first request misses, reads “/docs” from the mappings table, and stores a → /docs; later requests return that value without touching the database. If the cache is unavailable, the API can fall back to the table rather than fail the redirect.

The two-entry example orders keys from least to most recently used. A hit on “a” moves it to the end. When “c” arrives after “a” and “b,” the least recent key is evicted. This bounds memory, but a miss still pays for one database read and a fill.