TTL caches and time-based key-value stores: expiry and timestamps, step by step

In this article

1. Before you start
2. Why interviewers ask this
3. TTL caches and time-based key-value stores from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page belongs to the industry coding and machine coding rounds guide, where the usual round format is explained.

Why interviewers ask this

Candidates report being asked to build a TTL cache, and to explain what happens when expired entries are never evicted, in senior-level coding loops at large tech companies. The same shelf holds versioned-data drills: a snapshot array, a document store that keeps versions, and the time-based key-value store of LeetCode problem 981.

The question separates people who can write a get and a set from people who ask what the cache costs after days of running with many distinct keys. A weak answer stores a value and a deadline and stops. A strong answer states the expiry rule and its boundary, says when the memory is released, and names a second mechanism for entries nobody reads. A Staff-level answer also chooses a clock on purpose and knows the time-based store is the same idea with history kept instead of discarded.

TTL caches and time-based key-value stores from first principles

TTL cache

A TTL cache is a key-value store that attaches an expiry time to each entry, computed as the current time plus a time to live, and treats the entry as absent once the clock reaches that time, so stale data stops being served even though nobody deletes it explicitly.

Time-based key-value store

A time-based key-value store is a key-value store that keeps every value ever written to a key together with its timestamp, so a read supplies a key and a time and gets back the value that was current then, the one with the largest timestamp not after the read time.

Lazy expiry

Lazy expiry is a cleanup policy that checks an entry's expiry time only when the entry is read and deletes it then, which costs nothing between reads but never frees an entry that nobody reads again, so memory can grow without bound.

In plain words

Think of milk in a fridge with a date on the carton. Nobody throws it away at midnight. You look at the date when you reach for it, and you bin it if it is past. The analogy breaks in one place: a cache has no one cleaning the fridge, so a carton you never reach for stays there forever unless you add a cleaner.

A time-based store is a diary instead. You never throw an entry away. You write each value with its date, and later you ask what the latest entry on or before a given date said.

In one precise sentence, a TTL cache stores (value, expires_at) per key and answers only while the clock is before expires_at, while a time-based store stores a sorted list of (timestamp, value) per key and binary searches it.

Step 1: Store an expiry time with every entry

The set operation computes expires_at = now + ttl and stores it next to the value. The cachetools TTLCache documentation, read on 2026-10-26, states the same rule: the expression timer() + ttl "at the time of insertion defines the expiration time of a cache item".

Input: a key, a value and the current time. Output: one hash map entry holding the value and a deadline. Writing the same key again replaces both, which restarts the clock for that key.

Choose the clock deliberately. The cachetools default is time.monotonic(), a monotonic clock, which is a timer that only moves forward and is not set back when the system date is corrected. Passing the clock into the constructor, as the code below does, also lets a test move time by hand. You now know where the deadline lives; the next step uses it.

Step 2: Check the expiry on every read

The get operation looks up the entry, compares the clock with expires_at, and returns the value only if the deadline has not been reached. If it has, the entry counts as absent.

Pick the boundary rule out loud, because the problem rarely states it. This page uses the convention that an entry is expired when now >= expires_at. With a time to live of 10 (illustrative) set at time 0, a read at time 9 is a hit and a read at time 10 is a miss.¹

import time

class TTLCache:
    def __init__(self, ttl, clock=time.monotonic):
        self.ttl, self.clock = ttl, clock
        self.data = {}                      # key -> (value, expires_at)

    def set(self, key, value):
        self.data[key] = (value, self.clock() + self.ttl)

    def get(self, key, default=None):
        item = self.data.get(key)
        if item is None:
            return default
        value, expires_at = item
        if self.clock() >= expires_at:
            del self.data[key]              # lazy cleanup on read
            return default
        return value

Input: a key. Output: the value or a miss, in constant time on average. This code frees an expired entry only when someone reads it, which is the weakness the next step addresses.

Step 3: Cleanup decides when expired entries leave memory

Expired is not the same as deleted. The cachetools documentation says expired items "will be removed from a cache lazily, e.g. when __setitem__() is next called, and therefore may still claim memory", and it offers an explicit expire() call to remove them. The Redis documentation, read on 2026-10-26, describes two mechanisms in undefined: removal when a client touches an expired key, and a background process that samples keys with a time to live.

The code in Step 2 uses lazy expiry only. A key written once and never read stays. In the illustrative workload of the worked example, one new key per tick and no reads, the lazy-only cache holds 100 entries after 100 ticks, while a sweep holds 10.¹

Three fixes exist. A periodic sweep scans and deletes expired entries. A min-heap ordered by expires_at finds only the entries due, at the price of stale heap records when a key is rewritten. A size cap evicts the least recently used entry when full; cachetools does this too: "If no expired items are there to remove, the least recently used items will be discarded first". Mechanisms are often combined.

Step 4: Keep a sorted history to answer questions about time

A time-based store changes one decision: set(key, value, timestamp) appends instead of replacing. Each key holds a list of timestamps and a parallel list of values. The LeetCode problem 981, Time Based Key-Value Store, read on 2026-10-26, defines get(key, timestamp) as returning the value with the largest earlier-or-equal timestamp, or an empty string if none exists.

The same statement says the set timestamps are strictly increasing, so appending keeps each list sorted and binary search is valid. In the problem's limits, at most 200,000 calls are made; searching 200,000 entries by binary search takes at most 18 probes, against 200,000 for a linear scan.¹

from bisect import bisect_right

class TimeMap:
    def __init__(self):
        self.times, self.values = {}, {}    # key -> sorted list, key -> list

    def set(self, key, value, timestamp):
        self.times.setdefault(key, []).append(timestamp)
        self.values.setdefault(key, []).append(value)

    def get(self, key, timestamp):
        i = bisect_right(self.times.get(key, []), timestamp)
        return self.values[key][i - 1] if i else ""

bisect_right returns the position after every timestamp equal to or below the query, so index i - 1 is the latest entry not after it.

1 · Store expiry2 · Check on read3 · Clean up4 · Keep historyReplay

Step-by-step description

1. Set saves now plus the time to live.
2. Get misses once the clock reaches expiry.
3. A sweep or size cap frees unread entries.
4. Binary search finds the value at a time.

• Each entry stores its expiry time, the current time plus the time to live.
• A read compares the clock with the expiry and treats a reached expiry as a miss.
• A sweep or a size cap frees entries that nobody reads again.
• A time-based store keeps a sorted history per key and binary searches it.

Worked example

The traces below come from a script that runs both classes on small inputs.¹ The inputs are illustrative: a time to live of 10, a key set at time 0, and a time-based store with two writes. For the leak, one new key is written per tick for 100 ticks and none is ever read.

Walk through get(k,3). The timestamp list is [1, 4]. The position after every value at or below 3 is index 1, so the answer sits at index 0, which holds "a". For get(k,0) that position is index 0, nothing qualifies, and the answer is empty.¹

Text description of the diagram

• The lazy-only cache holds 100 entries after 100 unread writes.
• A sweep holds 10 entries after the same writes.

Trade-offs and edge cases

Every cleanup policy frees memory at a different moment. Lazy expiry is free between reads but leaks unread entries. A periodic sweep bounds memory but costs scan work, and a full scan of a large map blocks the caller unless it is done in small batches. A size cap bounds memory regardless of time, but it may evict a live entry to make room. Real systems combine them, as cachetools does with expiry first and least-recently-used eviction second.

Text description of the diagram

• Lazy expiry frees an entry only when it is read.
• A size cap can drop live entries when the cache is full.

Edge cases to name aloud:

• Boundary: decide whether now == expires_at is a hit or a miss and state it.
• Reads and the clock: cachetools fixes the deadline at insertion, so a read does not extend it. A sliding deadline that resets on read is a different design, and you should say which one you build.
• Many keys expiring together: if a batch of entries is written at the same moment with the same time to live, they expire together and the backing store sees a burst of misses. Adding a small random amount to each time to live spreads them out; this is common engineering advice rather than a measured figure.
• Out-of-order timestamps: the binary search needs sorted lists. LeetCode 981 promises increasing timestamps; if yours do not, insert with bisect.insort, which shifts elements, or use a balanced tree.
• Concurrency: two threads touching one dictionary need a lock or a per-key lock; mention it, then ask whether the round expects it.

The low level design interview guide covers how to scope a class like this in a round, and the CodeSignal in-memory database assessment uses the same ideas with expiry and history added level by level.

How to answer it in an interview

The spoken structure: store the deadline, check it on read, name the leak, give two fixes, then mention the history variant.

Common mistakes

• "Expired means deleted." (wrong) Expired entries stop being returned but may still hold memory until something removes them. (right) "Expiry stops the entry being returned by reads; cleanup frees its memory."
• "A TTL cache is an LRU cache." (wrong) Time expiry and capacity eviction are separate rules. (right) "I use a time to live for staleness and a size cap for memory."
• "I'll scan the whole list for the right timestamp." (wrong) That is linear per read. (right) "Timestamps are sorted, so I binary search."
• "I compute the deadline when I read." (wrong) The deadline moves forward with every read and the entry never expires. (right) "I compute now + ttl once, at write."
• "I use the wall clock." (wrong) Corrections to the system date can shift every deadline. (right) "I take a monotonic timer, injected so tests can control it."

Follow-up questions

Build a TTL cache. What happens if you keep everything in memory?

Memory grows with the number of distinct keys written, whether or not they are still valid. Without expiry and a size bound, the process eventually runs out of memory, so a TTL cache needs both a deadline and a cleanup path.

You're evicting the cache lazily — what happens if you don't evict?

Entries that are never read again are never checked, so they stay in memory forever. The cache returns correct answers but its footprint only grows, as the 100-versus-10 comparison in the worked example shows.

What are some ways to get around that?

Run a periodic sweep, keep a min-heap of deadlines to remove only due entries, or cap the size and evict the least recently used entry. Most production caches combine two of them.

How do you implement a snapshot array?

Keep, for each index, a sorted list of (snapshot_id, value) pairs and binary search it for the latest snapshot not after the one requested. It is the time-based store with snapshot numbers in place of timestamps.

What if the timestamps do not arrive in increasing order?

Insert each new pair at its sorted position with bisect.insort, which costs a shift per insert, or switch to a balanced tree. Say which you choose and why.

Should reading an entry reset its time to live?

It depends on the product. A fixed deadline, as in cachetools, bounds how stale a value can be; a sliding deadline keeps popular entries alive but can serve very old data. For a different drill in the same round format, see nested list weight sum.

Sources

1. cachetools: Extensible memoizing collections and decorators (TTLCache) — cachetools project documentation (accessed 2026-10-26), 26 Oct 2026
2. 981. Time Based Key-Value Store — LeetCode (accessed 2026-10-26), 26 Oct 2026
3. EXPIRE command — Redis documentation (accessed 2026-10-26), 26 Oct 2026