Build a Cache with Pluggable EvictionStep 2 of 5

The LRU Policy

12345

Step 2: The LRU Policy

LRU (least-recently-used) keeps the hot keys and evicts whatever has gone untouched the longest, the policy behind CPU caches and most application caches. The difference from FIFO is a single method: a read must mark the key as fresh.

  • LRUPolicy.on_access(key): move key to the most-recently-used position (the end)

Eviction still removes from the front, but now the front is the least recently used, because accesses keep bumping live keys to the back.

Hints
Starter code
class EvictionPolicy:
    def on_insert(self, key):
        raise NotImplementedError

    def on_access(self, key):
        raise NotImplementedError

    def evict(self):
        raise NotImplementedError


class LRUPolicy(EvictionPolicy):
    def __init__(self):
        self._order = []            # least-recent first, most-recent last

    def on_insert(self, key):
        self._order.append(key)

    def on_access(self, key):
        """Mark key as most-recently-used."""
        # TODO: recency lives in self._order, least-recent at the front. Make
        # this key the freshest by pulling it out of wherever it currently sits
        # and putting it back at the very end. A key that was never inserted
        # must be handled without raising.
        pass

    def evict(self):
        return self._order.pop(0)
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousNext step