Expanding Your Key-Value Store

Why this lesson matters

In Designing a Simple Key-Value Store, we turned the datastore contract from Data Store Fundamentals into a small Python API: SET, GET, DELETE, and basic expiring keys.

Now we move from "a dictionary with commands" toward a primitive Redis-like cache.

We'll focus on two production-shaped ideas:

• Time-based lifecycle: keys can expire predictably and cheaply.
• Memory pressure: when the store is too full, it can evict less useful data.

This is the jump from "it stores things" to "it behaves like infrastructure."

What are we adding?

We are not rebuilding all of Redis. Instead, we'll implement the subset that explains why Redis is so useful as an in-memory datastore.

A practical Redis-like key-value store needs:

• SET key value — write a value
• GET key — read a value
• DEL key — remove a value
• EXPIRE key seconds — attach a timeout
• TTL key — inspect remaining lifetime
• PERSIST key — remove the timeout
• Eviction policy — decide what to remove when memory is constrained

Conceptually, every key has two separate concerns:

key ──> value
key ──> optional expiration timestamp

That separation keeps the core store simple while letting us attach lifecycle rules.

Make expiration explicit

The previous lesson introduced expiring keys. Here we tighten the behavior into Redis-style semantics.

Common return values:

• TTL(key) > 0: key exists and has that many seconds left
• TTL(key) == -1: key exists but has no expiration
• TTL(key) == -2: key does not exist

Why these details matter:

• Application code can distinguish permanent data from missing data.
• Expired keys don't need to be physically deleted immediately, as long as reads treat them as gone.
• Tests become deterministic if time is injectable instead of directly calling time.time() everywhere.

Let's build that version.

```python
import math

class FakeClock:
    def __init__(self):
        self.now_seconds = 0

    def now(self):
        return self.now_seconds

    def advance(self, seconds):
        self.now_seconds += seconds


class MiniKVWithTTL:
    def __init__(self, clock):
        self.values = {}
        self.expires_at = {}
        self.clock = clock

    def _is_expired(self, key):
        deadline = self.expires_at.get(key)
        return deadline is not None and self.clock.now() >= deadline

    def _delete_if_expired(self, key):
        if self._is_expired(key):
            self.values.pop(key, None)
            self.expires_at.pop(key, None)
            return True
        return False

    def set(self, key, value, ex=None):
        self.values[key] = value
        self.expires_at[key] = None if ex is None else self.clock.now() + ex

    def get(self, key):
        self._delete_if_expired(key)
        return self.values.get(key)

    def delete(self, key):
        existed = key in self.values and not self._delete_if_expired(key)
        self.values.pop(key, None)
        self.expires_at.pop(key, None)
        return existed

    def expire(self, key, seconds):
        if self.get(key) is None:
            return False
        self.expires_at[key] = self.clock.now() + seconds
        return True

    def persist(self, key):
        if self.get(key) is None:
            return False
        self.expires_at[key] = None
        return True

    def ttl(self, key):
        self._delete_if_expired(key)
        if key not in self.values:
            return -2
        deadline = self.expires_at.get(key)
        if deadline is None:
            return -1
        return max(0, math.ceil(deadline - self.clock.now()))


clock = FakeClock()
db = MiniKVWithTTL(clock)

db.set("quote:AAPL", 189.50, ex=3)
print("initial:", db.get("quote:AAPL"), "ttl=", db.ttl("quote:AAPL"))

clock.advance(2)
print("after 2s:", db.get("quote:AAPL"), "ttl=", db.ttl("quote:AAPL"))

clock.advance(2)
print("after 4s:", db.get("quote:AAPL"), "ttl=", db.ttl("quote:AAPL"))

db.set("portfolio:user42", {"cash": 1000, "risk": "medium"})
print("permanent ttl:", db.ttl("portfolio:user42"))

db.expire("portfolio:user42", 10)
print("with expiry:", db.ttl("portfolio:user42"))

db.persist("portfolio:user42")
print("persisted ttl:", db.ttl("portfolio:user42"))
```

Your store contains 100,000 keys. Many expired overnight, but only a few are read the next morning.

Which strategy most directly prevents expired keys from sitting in memory forever?

Two expiration paths

A Redis-like store usually combines two cleanup strategies.

Lazy expiration

When a key is accessed, check whether it is expired. If so, delete it before returning.

Pros:

• Simple
• No background process required
• Work happens only for touched keys

Cons:

• Unread expired keys can occupy memory

Active expiration

Periodically inspect some expiring keys and delete the stale ones.

Pros:

• Reclaims memory without waiting for reads
• Keeps long-running servers healthier

Cons:

• Requires scheduling
• Can compete with normal traffic if too aggressive

A good cache balances both: lazy correctness plus active memory hygiene.

True or false: key expiration and LRU eviction are the same mechanism because both remove keys from the store.

Least Recently Used caching

Expiration answers: "Is this key too old by time?"

LRU answers: "If we are out of room, which key is least useful based on recent access?"

The rule:

When capacity is full, evict the key that has gone the longest without being read or written.

A common implementation combines:

• A hash map for O(1) key lookup
• A recency list for moving recently used keys to the end

Python's OrderedDict gives us both behaviors in a compact form.

least recent                         most recent
    ↓                                      ↓
[ user:1 ] -> [ quote:MSFT ] -> [ session:9 ]

After GET user:1:

least recent                         most recent
    ↓                                      ↓
[ quote:MSFT ] -> [ session:9 ] -> [ user:1 ]

Capacity-aware storage

Now we'll implement a tiny LRU cache.

This is separate from TTL expiration. In a fuller Redis-like system, both can exist together:

• Expiration removes keys whose lifetime has ended.
• LRU removes keys when capacity is exceeded.

For this example, focus on recency and eviction.

```python
from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self.capacity = capacity
        self.items = OrderedDict()

    def get(self, key):
        if key not in self.items:
            return None
        self.items.move_to_end(key)  # mark as most recently used
        return self.items[key]

    def set(self, key, value):
        evicted = None

        if key in self.items:
            self.items[key] = value
            self.items.move_to_end(key)
            return evicted

        if len(self.items) >= self.capacity:
            evicted = self.items.popitem(last=False)  # least recent

        self.items[key] = value
        return evicted

    def keys_by_recency(self):
        return list(self.items.keys())


cache = LRUCache(capacity=3)

print("evicted:", cache.set("quote:AAPL", 189.50))
print("evicted:", cache.set("quote:MSFT", 420.10))
print("evicted:", cache.set("quote:NVDA", 875.30))
print("order:", cache.keys_by_recency())

print("read AAPL:", cache.get("quote:AAPL"))
print("order:", cache.keys_by_recency())

print("evicted:", cache.set("quote:TSLA", 175.25))
print("order:", cache.keys_by_recency())
```

In the Python implementation, the built-in class used to maintain key order while still supporting dictionary-like lookup was __________.

Recap

You expanded the simple key-value store into a more realistic cache engine.

You now have the building blocks for:

• Redis-like command semantics
• Explicit TTL return values
• Lazy expiration on access
• Active expiration as a background cleanup idea
• LRU eviction under capacity pressure

The deeper lesson is architectural: production datastores often start with simple data structures, then layer on lifecycle rules, operational constraints, and predictable command behavior.

Next, we'll shift from flat key-value records to richer nested objects when we begin Creating a Document-Oriented Database.