Memory Management

Why a key/value store needs eviction

Real Redis is an in-memory database, which means its dataset is bounded by RAM, not disk. Once you set a maxmemory limit, Redis has to make a decision every time a write would push it over that limit: refuse the write, or delete something to make room. The default (and most common) policy is LRU — Least Recently Used — throw away the key nobody has touched in the longest time, on the theory that keys used recently are likely to be used again soon (temporal locality).

In this lesson you'll build a simplified version of that eviction engine, scoped to a maxkeys count instead of raw bytes (the mechanics are identical — only the "is there room?" check differs).

Tracking "recently used"

LRU needs a notion of time. Since your server already exposes a simulated clock via WAIT, reuse it: every key gets an access_time stamped with the current clock value.

access_time = {}   # key -> last-touched tick

def touch(key, clock):
    access_time[key] = clock

Every command that reads or writes a key counts as an access: GET, SET (even when overwriting), LPUSH, HSET, etc. A brand-new key is stamped with the clock value at creation time. WAIT itself only advances the clock — it is not an access to any key.

The simplest correct implementation is a hash map from key to timestamp, updated on every touch, with eviction implemented as a linear scan for the minimum timestamp. That's O(n) per eviction, which is completely fine for this exercise — real Redis instead maintains an intrusive doubly-linked list (or, since Redis 3, an approximated LRU using random sampling) so eviction is O(1)/O(k), but correctness first, cleverness later.

The eviction check

Eviction is not a background sweep — it happens synchronously, right before a write that would grow the keyspace:

def before_insert(new_key):
    if maxkeys > 0 and new_key not in store and len(store) >= maxkeys:
        victim = min(access_time, key=access_time.get)
        del store[victim]
        del access_time[victim]

Note the new_key not in store guard: overwriting an existing key (SET a 2 when a already exists) never grows the keyspace, so it should never trigger eviction — it's just a touch.

MAXKEYS and INFO memory

MAXKEYS <n> just sets the limit and replies +OK\r\n. Setting it to 0 should be treated as "unlimited" (never evict) per the spec — check for > 0 before enforcing.

INFO memory reports the two numbers Redis exposes for capacity planning, formatted as a single bulk string:

keys:<count>,maxkeys:<limit>\r\n

Remember it's a bulk string, so the wire format is $<len>\r\n<payload>\r\n, not a simple string.

Edge cases to watch

• Evicting exactly when the store is at the limit (>=), not only when it would exceed it — off-by-one here is the most common bug.
• Ties in access time: pick any one of the oldest deterministically (e.g., insertion order as a tiebreaker) so tests are reproducible.
• MAXKEYS set after the store already exceeds the new limit — real Redis evicts opportunistically on the next write; you only need to enforce it going forward, on the next insert.
• Don't let read commands that error out (e.g., GET on wrong type) still count as an access — only successful touches should update access_time.

This is the same building block that powers Redis's maxmemory-policy allkeys-lru in production — replace "key count" with "estimated memory bytes" and the algorithm is unchanged.