learning-it by example

#278 How it works, by example 6.4 min

Why Redis Is Fast: Build a Cache with Expiry and Eviction

A cache of 100 keys out of about 1,000 answered 58% of made-up requests.

1. A small Python cache built to explain how a cache like Redis works shows two ideas behind any cache. Which two ideas?
2. In a small Python cache test with 20000 made-up requests over about 1,000 keys, what share of the requests did a least-recently-used cache holding 100 keys answer?
3. In a small Python cache with expiry and LRU eviction, how does a key with a time to live of 30 seconds expire?
4. A least-recently-used cache holds at most 2 keys. Tea was added first, then jam, then tea was read, then oat was added. Which key is pushed out?
5. A small Python cache with expiry and LRU eviction is not Redis. Which difference from Redis is stated?

Practice only: nothing is saved and no score counts towards anything. Each answer comes with the reason.

  1. Make the session last longer

    Copy the code folder first. In run.py change the time to live of session:1 from 30 to 60 and run it. Predict what the third and fourth lines will say before you look. You should see the session still returned after 31 seconds, and price:tea now missing, because the cache holds 2 keys and tea became the least recently used. The printed text (expired after 30 s) is now stale, because the session did not expire, so ignore it. Change the time to live back to 30 afterwards, because the next exercise starts from the original file.

    A hint

    Read the session after the clock moves, then count which key is at the front when jam is added.

  2. Give the small cache more room

    In run.py change max_keys=2 to max_keys=3 and run it. Predict the counts of hits, misses, expired and evicted. You should see evicted 0 and all three keys left in the cache.

    A hint

    Eviction only happens while there are more keys than max_keys.

  3. Flatten the skew

    In workload.py change skew=1.0 to skew=0.5, so popular keys are less popular, then run python run.py. Predict whether the hit rate for 100 keys will go up or down. You should see it fall far below the 58 percent from the video, which fits the video's remark that the made-up skew sets the hit rates.

    A hint

    A lower skew spreads requests over more keys.

  4. Try tiny and huge cache sizes

    Change the sizes in run.py from (10, 50, 100, 200, 500) to (1, 5, 20, 1000). Predict the LRU hit rate for size 1000 before you run it, then compare. You should see 95 percent against 100 percent for the top keys. Why is the LRU rate not 100 percent when the cache can hold every key?

    A hint

    Think about the very first request for each key, when the cache is still empty.

These tasks are for you to try on your own machine. Nothing is checked or saved.

What this does not show

This toy is not Redis: no network, no persistence, exact LRU. The workload is made up, and its skew sets the hit rates.

Up next in How it works, by example

More in How it works, by example

All How it works, by example videos

Related videos