Design a Key-Value Store with TTL in Java (Low-Level Design)

An in-memory key-value store with TTL (time to live) lets each entry carry a lifetime after which it stops existing. Sessions, one-time codes, rate limit counters and caches all need this. The object design question is small but rich: how does a store that is driven by time stay testable, and how does it reclaim memory for entries nobody reads again?

This article designs the store, and it is a companion to design an LRU cache, which bounds a cache by size where this one bounds entries by time. For the distributed system version (partitioning, replication) see design a key-value store. The approach follows the LLD interview framework.

Requirements

Functional

set(key, value, ttl) stores a value. A TTL is optional. A zero or negative TTL is invalid.
get(key) returns the value only if it has not expired.
ttl(key) reports one of: missing, no expiry, or time remaining.
expire(key, ttl) sets a new lifetime on an existing key, and persist(key) removes it.
delete(key) removes an entry.
Expired entries must be reclaimed even if nobody reads them.

Non-functional

Reads and writes are O(1) on average. Scheduling an expiry is O(log n).
Behavior is deterministic in tests: no test may sleep or depend on the wall clock.
An expired entry is never returned, even if it has not been physically removed yet.

Entities and class diagram

The varying part is the source of time, so it becomes an interface. Everything else is concrete.

classDiagram
    class Ticker {
        <<interface>>
        +nowMillis() long
    }
    class SystemTicker
    class ManualTicker {
        -now: AtomicLong
        +advance(Duration)
    }
    class Store {
        -ticker: Ticker
        -data: HashMap~String,Entry~
        -expirations: TreeMap~Long,TreeSet~String~~
        +set(key, value, ttl)
        +get(key) Optional~String~
        +ttl(key) TtlStatus
        +sweep(budget) int
    }
    class Entry {
        <<record>>
        value: String
        expiresAt: long
    }
    class TtlStatus {
        <<sealed interface>>
        Missing
        Persistent
        Remaining
    }
    Ticker <|.. SystemTicker
    Ticker <|.. ManualTicker
    Store --> Ticker : reads time from
    Store *-- Entry : owns
    Store ..> TtlStatus : returns

The store keeps two structures in step. data answers "what is the value of this key" in O(1). expirations answers "which keys are due next" and is ordered by deadline, so the earliest deadline is always first. Both must always agree, and only Store can touch them, which is the invariant that private fields protect (encapsulation and invariants).

API

Java

@FunctionalInterface
interface Ticker {
    long nowMillis();
}

final class Store {
    Store(Ticker ticker);
    void set(String key, String value);                  // no expiry
    void set(String key, String value, Duration ttl);    // throws IllegalArgumentException if ttl <= 0
    Optional<String> get(String key);
    TtlStatus ttl(String key);
    boolean expire(String key, Duration ttl);            // false if the key is missing
    boolean persist(String key);                         // true if a deadline was removed
    boolean delete(String key);
    int sweep(int budget);
}

The signatures above are a summary and are not compiled. get removes an expired entry when it finds one (lazy expiry), so it changes the store even though it is a read. ttl never removes anything, so an expired entry reports Missing. Time values are milliseconds as long inside, and callers pass java.time.Duration, which makes units impossible to confuse. Optional is used only as a return type, and set has two overloads so that "no TTL" is never passed as null.

Design decisions

Inject the clock. A store that reads the system clock directly cannot be tested without sleeping, and sleeping tests are slow and flaky. A Ticker interface with a real implementation and a manual one turns time into an input. This is constructor injection (testability and dependency injection). The store depends on the small Ticker interface and not on java.time.Clock because TTLs need a monotonic source: Clock.systemUTC() follows the wall clock, which can be adjusted, while System.nanoTime() only moves forward.

Two expiry mechanisms, because each alone fails.

Mechanism	How it works	What it guarantees	What it cannot do
Lazy expiry	Check the deadline on every access and remove the entry if due	Callers never see an expired value	Memory of keys never read again is never freed
Active expiry	Periodically pop due keys from the deadline index	Memory is reclaimed even for unread keys	Between sweeps, expired entries still occupy memory

Together they give a correctness guarantee (lazy) and a memory guarantee (active). Redis makes the same split.

A TreeMap from deadline to keys. The sweeper needs "everything due by now". A TreeMap<Long, TreeSet<String>> keeps deadlines sorted, so firstEntry() returns the earliest one in O(log n). Grouping keys per deadline handles two keys expiring in the same millisecond. A PriorityQueue also works, but removing a key whose TTL changed is O(n) in a heap, whereas a map supports direct removal. See design a task scheduler for the heap version.

Deadlines, not durations. The entry stores an absolute expiresAt, computed once from now + ttl. Checking expiry is then one comparison and does not accumulate error.

Boundary rule. An entry is expired when expiresAt <= now. A TTL of 10 seconds means the value is visible for exactly the half-open interval [set, set + 10s).

Sweep with a budget. An unbounded sweep after a long pause could stall callers. sweep(budget) removes at most budget entries and returns the count, so the caller decides how much work to do per tick.

Full implementation

The clock comes first. A test keeps a reference to the same ManualTicker object that the store holds, so no wrapper is needed to share it. The counter inside is an AtomicLong so the same class can be read from a sweeper thread later.

Java

import java.time.Duration;
import java.util.concurrent.atomic.AtomicLong;

@FunctionalInterface
interface Ticker {
    long nowMillis();
}

/** Real time, measured from the moment of construction. Monotonic. */
final class SystemTicker implements Ticker {
    private final long startNanos = System.nanoTime();

    @Override
    public long nowMillis() {
        return (System.nanoTime() - startNanos) / 1_000_000;
    }
}

/** Time that moves only when told to. */
final class ManualTicker implements Ticker {
    private final AtomicLong now = new AtomicLong();

    void advance(Duration d) {
        now.addAndGet(d.toMillis());
    }

    @Override
    public long nowMillis() {
        return now.get();
    }
}

public class Main {
    public static void main(String[] args) {
        var real = new SystemTicker();
        long a = real.nowMillis();
        long b = real.nowMillis();
        System.out.println("system ticker never goes backwards: " + (b >= a));

        var manual = new ManualTicker();
        Ticker shared = manual;
        System.out.println("t = " + shared.nowMillis());
        manual.advance(Duration.ofMillis(1500));
        System.out.println("t = " + shared.nowMillis());
    }
}

Output

system ticker never goes backwards: true
t = 0
t = 1500

The expiry rule is one function, so it can be pinned down by checks. A deadline of Long.MAX_VALUE stands for "no deadline", so the rule tests for it first.

Java

public class Main {
    static final long NO_DEADLINE = Long.MAX_VALUE;

    static boolean isExpired(long expiresAt, long now) {
        return expiresAt != NO_DEADLINE && expiresAt <= now;
    }

    public static void main(String[] args) {
        assert !isExpired(NO_DEADLINE, Long.MAX_VALUE);
        System.out.println("no deadline never expires");

        assert !isExpired(100, 99);
        assert isExpired(100, 100);
        assert isExpired(100, 101);
        System.out.println("expires exactly at the deadline");
    }
}

Output

no deadline never expires
expires exactly at the deadline

Now the store. It keeps data and expirations in step through two private helpers, schedule and unschedule, so no other method touches the index directly.

Java

import java.time.Duration;
import java.util.HashMap;
import java.util.Map;
import java.util.Optional;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.concurrent.atomic.AtomicLong;

@FunctionalInterface
interface Ticker {
    long nowMillis();
}

final class ManualTicker implements Ticker {
    private final AtomicLong now = new AtomicLong();

    void advance(Duration d) {
        now.addAndGet(d.toMillis());
    }

    @Override
    public long nowMillis() {
        return now.get();
    }
}

sealed interface TtlStatus {
    record Missing() implements TtlStatus {}
    record Persistent() implements TtlStatus {}
    record Remaining(Duration left) implements TtlStatus {}
}

record Stats(long lazyExpired, long swept) {}

final class Store {
    private static final long NO_DEADLINE = Long.MAX_VALUE;

    private record Entry(String value, long expiresAt) {
        boolean hasDeadline() {
            return expiresAt != NO_DEADLINE;
        }
    }

    private final Ticker ticker;
    private final Map<String, Entry> data = new HashMap<>();
    private final TreeMap<Long, TreeSet<String>> expirations = new TreeMap<>();
    private long lazyExpired;
    private long swept;

    Store(Ticker ticker) {
        this.ticker = ticker;
    }

    private long deadline(Duration ttl) {
        if (ttl.isZero() || ttl.isNegative()) {
            throw new IllegalArgumentException("ttl must be positive: " + ttl);
        }
        return Math.addExact(ticker.nowMillis(), ttl.toMillis());
    }

    private void schedule(String key, long at) {
        expirations.computeIfAbsent(at, k -> new TreeSet<>()).add(key);
    }

    private void unschedule(String key, long at) {
        var keys = expirations.get(at);
        if (keys != null) {
            keys.remove(key);
            if (keys.isEmpty()) {
                expirations.remove(at);
            }
        }
    }

    private boolean isExpired(Entry e) {
        return e.hasDeadline() && e.expiresAt() <= ticker.nowMillis();
    }

    /** Removes the entry and its scheduled deadline. Returns whether an entry was removed. */
    private boolean removeEntry(String key) {
        var entry = data.remove(key);
        if (entry == null) {
            return false;
        }
        if (entry.hasDeadline()) {
            unschedule(key, entry.expiresAt());
        }
        return true;
    }

    /** Lazy expiry: drop the entry if it is due, so callers never see it. */
    private void expireIfDue(String key) {
        var entry = data.get(key);
        if (entry != null && isExpired(entry)) {
            removeEntry(key);
            lazyExpired++;
        }
    }

    void set(String key, String value) {
        store(key, value, NO_DEADLINE);
    }

    void set(String key, String value, Duration ttl) {
        store(key, value, deadline(ttl));
    }

    private void store(String key, String value, long expiresAt) {
        removeEntry(key); // overwriting clears the old deadline
        data.put(key, new Entry(value, expiresAt));
        if (expiresAt != NO_DEADLINE) {
            schedule(key, expiresAt);
        }
    }

    Optional<String> get(String key) {
        expireIfDue(key);
        return Optional.ofNullable(data.get(key)).map(Entry::value);
    }

    TtlStatus ttl(String key) {
        var entry = data.get(key);
        if (entry == null || isExpired(entry)) {
            return new TtlStatus.Missing();
        }
        if (!entry.hasDeadline()) {
            return new TtlStatus.Persistent();
        }
        return new TtlStatus.Remaining(Duration.ofMillis(entry.expiresAt() - ticker.nowMillis()));
    }

    boolean expire(String key, Duration ttl) {
        long at = deadline(ttl);
        expireIfDue(key);
        var old = data.get(key);
        if (old == null) {
            return false;
        }
        if (old.hasDeadline()) {
            unschedule(key, old.expiresAt());
        }
        data.put(key, new Entry(old.value(), at));
        schedule(key, at);
        return true;
    }

    boolean persist(String key) {
        expireIfDue(key);
        var old = data.get(key);
        if (old == null || !old.hasDeadline()) {
            return false;
        }
        unschedule(key, old.expiresAt());
        data.put(key, new Entry(old.value(), NO_DEADLINE));
        return true;
    }

    boolean delete(String key) {
        expireIfDue(key);
        return removeEntry(key);
    }

    /** Active expiry: remove up to {@code budget} due entries, earliest deadline first. */
    int sweep(int budget) {
        long now = ticker.nowMillis();
        int removed = 0;
        while (removed < budget) {
            var slot = expirations.firstEntry();
            if (slot == null || slot.getKey() > now) {
                break;
            }
            var key = slot.getValue().pollFirst();
            if (slot.getValue().isEmpty()) {
                expirations.remove(slot.getKey());
            }
            data.remove(key);
            removed++;
        }
        swept += removed;
        return removed;
    }

    /** Entries physically stored, including expired ones not yet reclaimed. */
    int stored() {
        return data.size();
    }

    /** Entries a caller could still read. */
    long live() {
        return data.values().stream().filter(e -> !isExpired(e)).count();
    }

    Stats stats() {
        return new Stats(lazyExpired, swept);
    }
}

public class Main {
    static String attempt(Runnable action) {
        try {
            action.run();
            return "ok";
        } catch (IllegalArgumentException e) {
            return "IllegalArgumentException: " + e.getMessage();
        }
    }

    public static void main(String[] args) {
        var clock = new ManualTicker();
        var store = new Store(clock);

        store.set("a", "1", Duration.ofSeconds(10));
        store.set("b", "2", Duration.ofSeconds(20));
        store.set("c", "3");
        System.out.println("ttl a: " + store.ttl("a") + ", c: " + store.ttl("c") + ", x: " + store.ttl("x"));
        System.out.println("zero ttl: " + attempt(() -> store.set("z", "0", Duration.ZERO)));

        clock.advance(Duration.ofSeconds(4));
        System.out.println("t=4s ttl a: " + store.ttl("a"));

        clock.advance(Duration.ofSeconds(6));
        System.out.println("t=10s get a: " + store.get("a") + " (deadline is exclusive)");
        System.out.println("stored " + store.stored() + " live " + store.live() + " lazy " + store.stats().lazyExpired());

        clock.advance(Duration.ofSeconds(10));
        System.out.println("t=20s stored " + store.stored() + " live " + store.live() + " (b is expired but still in memory)");
        System.out.println("swept " + store.sweep(10));
        System.out.println("stored " + store.stored() + " live " + store.live());

        System.out.println("expire c: " + store.expire("c", Duration.ofSeconds(5)));
        System.out.println("ttl c: " + store.ttl("c"));
        System.out.println("persist c: " + store.persist("c"));
        System.out.println("ttl c: " + store.ttl("c"));
        System.out.println("expire missing: " + store.expire("nope", Duration.ofSeconds(5)));
        System.out.println("delete c: " + store.delete("c") + ", again: " + store.delete("c"));
        System.out.println(store.stats());
    }
}

Output

ttl a: Remaining[left=PT10S], c: Persistent[], x: Missing[]
zero ttl: IllegalArgumentException: ttl must be positive: PT0S
t=4s ttl a: Remaining[left=PT6S]
t=10s get a: Optional.empty (deadline is exclusive)
stored 2 live 2 lazy 1
t=20s stored 2 live 1 (b is expired but still in memory)
swept 1
stored 1 live 1
expire c: true
ttl c: Remaining[left=PT5S]
persist c: true
ttl c: Persistent[]
expire missing: false
delete c: true, again: false
Stats[lazyExpired=1, swept=1]

The run shows both mechanisms. At t=10s the entry a is exactly at its deadline, so get removes it lazily. At t=20s entry b is dead to callers (live is 1) yet still occupies memory (stored is 2) until sweep runs. Overwriting or persisting a key always clears the old deadline from the index, so a stale deadline can never delete a newer value.

A background sweeper

In a real server, sweep runs on a timer thread. The store is shared by several threads, so every method that touches it must be guarded: the simplest form is synchronized methods, and the clock must be safe to read from another thread, so the manual clock is built on an AtomicLong. To keep the demo deterministic, the sweeper is driven by messages on a BlockingQueue instead of a real timer. The example uses a minimal store that contains only the deadline index.

Java

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.Executors;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.concurrent.atomic.AtomicLong;

final class MiniStore {
    private final Map<String, Long> data = new HashMap<>();                 // key -> deadline
    private final TreeMap<Long, List<String>> index = new TreeMap<>();      // deadline -> keys

    synchronized void set(String key, long deadline) {
        data.put(key, deadline);
        index.computeIfAbsent(deadline, d -> new ArrayList<>()).add(key);
    }

    synchronized int sweep(long now) {
        var due = index.headMap(now, true); // a live view of the deadlines <= now
        int removed = 0;
        for (var keys : due.values()) {
            for (var key : keys) {
                data.remove(key);
                removed++;
            }
        }
        due.clear();
        return removed;
    }

    synchronized int size() {
        return data.size();
    }
}

enum Msg { TICK, STOP }

public class Main {
    public static void main(String[] args) throws Exception {
        var clock = new AtomicLong();
        var store = new MiniStore();
        var keys = List.of("a", "b", "c", "d", "e");
        for (int i = 0; i < keys.size(); i++) {
            store.set(keys.get(i), (i + 1) * 10L);
        }

        BlockingQueue<Msg> queue = new LinkedBlockingQueue<>();
        try (var pool = Executors.newSingleThreadExecutor()) {
            var sweeper = pool.submit(() -> {
                int total = 0;
                while (queue.take() == Msg.TICK) {
                    total += store.sweep(clock.get());
                }
                return total;
            });

            clock.set(25);
            queue.put(Msg.TICK);
            clock.set(100);
            queue.put(Msg.TICK);
            queue.put(Msg.STOP);

            System.out.println("swept in total: " + sweeper.get());
        }
        System.out.println("left in store: " + store.size());
    }
}

Output

swept in total: 5
left in store: 0

The sweeper task ends when it takes STOP, because the loop only continues on TICK. Waiting on sweeper.get() before printing makes the output independent of thread timing, and queue.put happens before the matching take, so the sweeper always sees the clock value that was set before the message. In production the TICK source is a timer (a ScheduledExecutorService running every 100 ms, for example) and the budget from sweep(budget) keeps each lock hold short, so readers are not starved. See thread-safe components and blocking queue and producer-consumer.

Extensions

Follow-up question	Answer
Add a text command interface (`SET k v EX 10`)	Model commands as a sealed interface of records, parse each line into one, and have one `execute(Store, Command)` method that is a `switch` over the command.
Bound the memory as well as the time	Combine with an eviction policy; see design an LRU cache and cache eviction policies.
Sweep cost after a long pause	The budget caps work per call. The next tick continues where the last stopped, because due entries stay at the front of the index.
Sliding TTL (refresh on access)	On `get`, unschedule the old deadline and schedule `now + ttl`. Store the original TTL in `Entry`.
Expiry notifications	Return the removed keys from `sweep` and publish them on an event bus; see event bus and observers.
Wall clock jumps	Use a monotonic clock for TTLs, as `SystemTicker` does with `System.nanoTime()`. A wall clock can move backwards.
Millions of keys with the same TTL	Deadlines arrive in increasing order, so an `ArrayDeque` of `(deadline, key)` replaces the tree.
Persistence	Store absolute deadlines in wall-clock time on disk and convert on load.

Summary

A store with expiry is a function of time, so make time an injected Ticker interface and test with a manual ticker. No test sleeps.
Store absolute deadlines, and define expiry as expiresAt <= now so the boundary is unambiguous and testable.
Use both lazy expiry (correctness on read) and active expiry (memory reclaimed for unread keys).
Keep a TreeMap from deadline to keys next to the hash map, and update both only through private schedule and unschedule helpers so they never disagree.
Bound sweep work with a budget so a backlog cannot stall callers.
Validate at the boundary: a zero or negative TTL throws IllegalArgumentException, and results such as TtlStatus are a sealed interface rather than sentinel numbers.
In a threaded server, guard the store with a lock, use an atomic clock, and drive the sweeper through a BlockingQueue so tests stay deterministic.