SyntaxPilot
Courses/Low-Level Design/Lesson 70
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Low-Level Design · Lesson 70 of 90

Design an in-memory key-value store

key-value storeget put deletetyped valuesTTL and expirylazy vs active expirytransactions BEGIN COMMIT ROLLBACKnested transactionssnapshotswrite-ahead log ideaConcurrentHashMap-based storecommand parser

These are the notes for Low-Level Design (LLD) episode 70: designing an in-memory key-value store, the idea behind Redis and one of the most common machine-coding problems. We start with the simplest store we can write, watch it return a wrong value, and fix one problem at a time: a HashMap for get, put and delete, typed values, TTL and expiry (lazy and active), transactions with BEGIN, COMMIT and ROLLBACK, nested transactions, a command parser, a ConcurrentHashMap-based store for many threads, and a write-ahead log with snapshots so the data survives a restart.

How the code was run: every program was saved as Main.java in a fresh folder and run with javac Main.java && java -cp . Main on OpenJDK 21. Every output below is the real output, pasted exactly. Millisecond timings and the lost-update count change from run to run. Users, carts and wallets are made up for teaching.

1. The problem: the temple shoe stand

At the shoe stand In a key-value store
You hand over your shoes and get token 47 put(47, shoes): save a value under a key
You show token 47; he goes straight to slot 47 get(47): look up by the key, without searching every shelf
Shoes left overnight are cleared at closing TTL: a key may live only for a while
He writes every token in a register book first A write-ahead log: the data can be rebuilt after a mix-up

2. The words

  • Key: a unique name you look things up by, e.g. cart:asha. Writing type:id (with a colon) is a common habit, so keys of different kinds never clash.
  • Value: the data saved under the key: text ("5 items"), a number (41), a list.
  • Key-value store: a program that saves values under keys and gives them back. Three basic operations:
  • put(key, value) saves (or replaces) a value,
  • get(key) reads it back (null if there is none),
  • delete(key) removes it.
  • In-memory: everything is kept in RAM, the computer's fast working memory, not on the disk. RAM is very fast, but it is wiped when the program stops.

3. Attempt 1: a list of pairs

The obvious way: keep a list of [key, value] pairs. put adds a pair; get walks the list from the start.

import java.util.*;
class ListStore {                                    // attempt: a list of key-value pairs
    private final List<String[]> pairs = new ArrayList<>();
    void put(String key, String value) { pairs.add(new String[]{key, value}); }
    String get(String key) {                         // walk the list from the start
        for (String[] p : pairs) if (p[0].equals(key)) return p[1];
        return null; }
}
public class Main { public static void main(String[] args) {
    ListStore s = new ListStore();
    s.put("cart:asha", "2 items");
    s.put("cart:asha", "5 items");                   // Asha adds 3 more to her cart
    System.out.println("cart:asha = " + s.get("cart:asha"));
    for (int i = 0; i < 100_000; i++) s.put("user:" + i, "name " + i);
    long t = System.nanoTime();
    for (int i = 0; i < 2_000; i++) s.get("user:" + (99_000 + i % 1000));
    System.out.printf("2,000 gets took %d ms%n", (System.nanoTime() - t) / 1_000_000); } }

Output:

cart:asha = 2 items
2,000 gets took 1599 ms

Why it failed

  • Wrong value: put never checked for an existing key, so the cart got a second pair, and get found the old one first: 2 items, not 5 items.
  • Slow: get is a linear search: it looks at the items one by one, so its cost is O(n) (it grows with the number of items n). 2,000 gets over 100,000 pairs took over a second.

Big-O is a way to say how the work grows with the input: O(1) means "about the same time whatever the size", O(n) means "twice the data, twice the time".

4. The fix: a HashMap, and typed values

A HashMap turns the key into a number called a hash ("cart:asha".hashCode()), and that number picks a bucket, a slot in an array. So put, get and remove are O(1) on average, and put replaces the old value of a key. That is the shoe stand's trick: go straight to slot 47.

Typed values: real values have different types (a cart is text, a visit counter is a number). We store them as Object, the base type of every Java class. Reading one back needs a cast (a conversion to the real type, (Integer) v). A wrong cast crashes, so we add a typed get that checks the type first with Class.isInstance and gives a clear message.

import java.util.*;
class KVStore {                                      // a HashMap: key -> value, O(1) on average
    private final Map<String, Object> data = new HashMap<>();
    void put(String key, Object value) { data.put(key, value); }    // replaces the old value
    Object get(String key) { return data.get(key); }
    boolean delete(String key) { return data.remove(key) != null; }
    <T> T get(String key, Class<T> type) {           // typed get: check the type, then cast
        Object v = data.get(key);
        if (v == null) return null;
        if (!type.isInstance(v)) throw new IllegalArgumentException(key + " holds "
            + v.getClass().getSimpleName() + ", wanted " + type.getSimpleName());
        return type.cast(v); }
}
public class Main { public static void main(String[] args) {
    KVStore s = new KVStore();
    s.put("cart:asha", "2 items");  s.put("cart:asha", "5 items");
    System.out.println("cart:asha = " + s.get("cart:asha"));
    for (int i = 0; i < 100_000; i++) s.put("user:" + i, "name " + i);
    long t = System.nanoTime();
    for (int i = 0; i < 2_000; i++) s.get("user:" + (99_000 + i % 1000));
    System.out.printf("2,000 gets took %d ms%n", (System.nanoTime() - t) / 1_000_000);
    s.put("visits", 41);                             // values of different types
    int visits = s.get("visits", Integer.class) + 1;
    System.out.println("visits = " + visits);
    System.out.println("delete user:7 -> " + s.delete("user:7") + ", again -> " + s.delete("user:7"));
    try { s.get("cart:asha", Integer.class); }
    catch (IllegalArgumentException e) { System.out.println("typed get: " + e.getMessage()); }
    int items = (Integer) s.get("cart:asha");        // a raw cast: no check at all
} }

Output:

cart:asha = 5 items
2,000 gets took 1 ms
visits = 42
delete user:7 -> true, again -> false
typed get: cart:asha holds String, wanted Integer
Exception in thread "main" java.lang.ClassCastException: class java.lang.String cannot be cast to class java.lang.Integer (java.lang.String and java.lang.Integer are in module java.base of loader 'bootstrap')
    at Main.main(Main.java:28)
  • cart:asha = 5 items: put replaced the value.
  • 2,000 gets: a few milliseconds instead of more than a second.
  • delete returns true the first time and false the second: nothing was left to remove.
  • The typed get explains the problem; the raw cast (Integer) s.get("cart:asha") throws ClassCastException.

<T> T get(String key, Class<T> type) is a generic method: T is a type parameter, filled in by the caller (Integer.class makes T = Integer), so the result needs no cast.

5. TTL: lazy and active expiry

An OTP (one-time password, the code a bank texts you) must stop working after, say, 30 seconds. In our store a value lives forever. The fix is a TTL (time to live): how long a key may live. We store expiresAt = now + ttl with the value.

When is an expired key removed?

  • Lazy expiry (Redis calls it passive): whenever someone reads a key, check expiresAt; if it has passed, delete it and return nothing. Cheap, but a key nobody reads again stays in memory forever.
  • Active expiry: a sweep, a cleaner, looks for dead keys and removes them, even if nobody reads them.

To test time without waiting, we use a fake clock: a clock object we move forward by hand (clock.now = 31_000), so every test is exact and instant. In real code you inject the clock (pass it in), just like in episode 53.

import java.util.*;
class Clock { long now = 0; }                        // a fake clock we move by hand (milliseconds)
record Entry(Object value, long expiresAt) {}        // expiresAt = -1 means: never expires
class KVStore {
    final Map<String, Entry> data = new HashMap<>();  final Clock clock;
    KVStore(Clock clock) { this.clock = clock; }
    void put(String k, Object v) { data.put(k, new Entry(v, -1)); }
    void put(String k, Object v, long ttlMs) { data.put(k, new Entry(v, clock.now + ttlMs)); }
    boolean expired(Entry e) { return e.expiresAt() != -1 && clock.now >= e.expiresAt(); }
    Object get(String k) {                           // LAZY expiry: check it when someone reads
        Entry e = data.get(k);  if (e == null) return null;
        if (expired(e)) { data.remove(k);  return null; }
        return e.value(); }
    int sweep() {                                    // ACTIVE expiry: a cleaner removes dead keys
        int before = data.size();
        data.values().removeIf(this::expired);
        return before - data.size(); }
}
public class Main { public static void main(String[] args) {
    Clock clock = new Clock();  KVStore s = new KVStore(clock);
    s.put("otp:ravi", "111111");                     // attempt: no expiry at all
    s.put("otp:asha", "482913", 30_000);             // TTL: valid for 30 seconds
    System.out.println("at 0 s:  asha " + s.get("otp:asha") + ", ravi " + s.get("otp:ravi"));
    clock.now = 31_000;
    System.out.println("at 31 s: asha " + s.get("otp:asha") + ", ravi " + s.get("otp:ravi"));
    for (int i = 0; i < 100_000; i++) s.put("otp:" + i, "code", 60_000);
    clock.now = 200_000;                             // all expired, but nobody reads them
    System.out.println("at 200 s: " + s.data.size() + " entries still in memory");
    System.out.println("sweep removed " + s.sweep() + ", left " + s.data.size()); } }

Output:

at 0 s:  asha 482913, ravi 111111
at 31 s: asha null, ravi 111111
at 200 s: 100001 entries still in memory
sweep removed 100000, left 1
  • At 31 s, Asha's OTP is null (lazy expiry), but Ravi's OTP, stored with no TTL, still works: a security hole.
  • At 200 s, 100,001 entries are still in memory, 100,000 of them dead. The sweep removes them; Ravi's is left.
  • data.values().removeIf(this::expired) removes entries safely while going through the map. Removing with map.remove inside a for (String k : map.keySet()) loop throws ConcurrentModificationException (see the mistakes table).

How Redis does it

From the Redis documentation of EXPIRE ("How Redis expires keys"):

  • Passive: "A key is passively expired simply when some client tries to access it, and the key is found to be timed out."
  • Active: "periodically Redis tests a few keys at random among keys with an expire set." Ten times per second it tests 20 random keys that have an expiry, deletes the expired ones, and if more than 25% were expired it starts again.

Sampling random keys, instead of scanning all of them like our sweep, means a huge store never freezes while it cleans. The mini project below has a sampled sweep.

6. Attempt: a transfer as two separate writes

import java.util.*;
public class Main {
    static Map<String, Integer> data = new HashMap<>();
    static void transfer(String from, String to, int amount) {   // two separate writes
        data.put(from, data.get(from) - amount);                 // step 1: take the money out
        data.put(to, data.get(to) + amount);                     // step 2: put it in
    }
    public static void main(String[] args) {
        data.put("wallet:asha", 500);  data.put("wallet:ravi", 200);
        System.out.println("before: " + data);
        try { transfer("wallet:asha", "wallet:rvai", 100); }      // a typo in the key
        catch (Exception e) { System.out.println("transfer failed: " + e.getMessage()); }
        System.out.println("after:  " + data);
        int total = data.values().stream().mapToInt(Integer::intValue).sum();
        System.out.println("total money: " + total + " (was 700)");
    }
}

Output:

before: {wallet:asha=500, wallet:ravi=200}
transfer failed: Cannot invoke "java.lang.Integer.intValue()" because the return value of "java.util.Map.get(Object)" is null
after:  {wallet:asha=400, wallet:ravi=200}
total money: 600 (was 700)

Step 1 ran, step 2 crashed (the misspelled key wallet:rvai returned null, and unboxing null throws NullPointerException). Asha lost 100, Ravi got nothing, and 100 rupees vanished. Half a change is worse than no change.

7. Transactions: BEGIN, COMMIT, ROLLBACK

A transaction is a group of changes that happens all together or not at all (this property is called atomicity).

  • BEGIN starts a transaction.
  • COMMIT keeps all its changes.
  • ROLLBACK undoes all its changes, as if they never happened.

How do we undo?

  • A snapshot: a full copy of all the data at BEGIN. Simple, but copying a million keys for one change is costly.
  • An undo log: before a key changes for the first time in the transaction, save its old value (or "absent" if it did not exist). ROLLBACK puts every old value back. Only changed keys are copied.

Nested transactions: a BEGIN inside a BEGIN. We keep a stack (a Deque, last in, first out) of undo logs, one per open BEGIN.

  • ROLLBACK pops and undoes only the innermost one.
  • An inner COMMIT pops its undo log and merges it into the parent's (putIfAbsent, so the parent keeps the oldest value). The outer transaction can still roll everything back.

The command parser

A command parser turns a line of text ("SET asha 400") into a method call: split into words, then switch on the first word. An unknown word gives an error message, not a crash. This is the shape of most machine-coding versions of this problem.

import java.util.*;
class TxStore {
    private static final String ABSENT = new String("(absent)");       // "the key did not exist"
    private final Map<String, String> data = new HashMap<>();
    private final Deque<Map<String, String>> undo = new ArrayDeque<>(); // one undo log per BEGIN
    private void remember(String k) {                 // keep the OLD value, once per transaction
        if (!undo.isEmpty()) undo.peek().putIfAbsent(k, data.getOrDefault(k, ABSENT)); }
    String rollback() {                               // put every old value back
        if (undo.isEmpty()) return "NO TRANSACTION";
        undo.pop().forEach((k, old) -> { if (old == ABSENT) data.remove(k); else data.put(k, old); });
        return "OK"; }
    String commit() {                                 // keep the changes; a parent can still undo them
        if (undo.isEmpty()) return "NO TRANSACTION";
        Map<String, String> inner = undo.pop();  if (!undo.isEmpty()) inner.forEach(undo.peek()::putIfAbsent);
        return "OK"; }
    String run(String line) {  String[] p = line.trim().split("\\s+");   // the command parser: text -> a call
        return switch (p[0].toUpperCase()) {
            case "SET"      -> { remember(p[1]);  data.put(p[1], p[2]);  yield "OK"; }
            case "DELETE"   -> { remember(p[1]);  data.remove(p[1]);  yield "OK"; }
            case "GET"      -> data.getOrDefault(p[1], "NULL");
            case "BEGIN"    -> { undo.push(new HashMap<>());  yield "OK"; }
            case "ROLLBACK" -> rollback();
            case "COMMIT"   -> commit();
            default         -> "ERR unknown command '" + p[0] + "'"; }; } }
public class Main { public static void main(String[] args) {
    TxStore s = new TxStore();
    String script = "SET asha 500|SET ravi 200|BEGIN|SET asha 400|DELETE ravi|GET ravi|ROLLBACK|GET asha|GET ravi"
        + "|BEGIN|SET asha 400|BEGIN|SET ravi 300|COMMIT|GET ravi|ROLLBACK|GET asha|GET ravi|ROLLBACK|SAVE x";
    for (String cmd : script.split("\\|")) System.out.printf("%-12s -> %s%n", cmd, s.run(cmd)); } }

Output:

SET asha 500 -> OK
SET ravi 200 -> OK
BEGIN        -> OK
SET asha 400 -> OK
DELETE ravi  -> OK
GET ravi     -> NULL
ROLLBACK     -> OK
GET asha     -> 500
GET ravi     -> 200
BEGIN        -> OK
SET asha 400 -> OK
BEGIN        -> OK
SET ravi 300 -> OK
COMMIT       -> OK
GET ravi     -> 300
ROLLBACK     -> OK
GET asha     -> 500
GET ravi     -> 200
ROLLBACK     -> NO TRANSACTION
SAVE x       -> ERR unknown command 'SAVE'
  • First transaction: after DELETE ravi, GET ravi is NULL; ROLLBACK brings back asha 500 and ravi 200.
  • Nested: the inner COMMIT keeps ravi 300 for now; the outer ROLLBACK undoes both changes.
  • ROLLBACK with nothing open: NO TRANSACTION. SAVE x: ERR unknown command 'SAVE'.
  • ABSENT = new String("(absent)") is a sentinel: a special object compared with ==, so no real value can be mistaken for it.

Real-world fact: Redis's documentation says "Redis does not support rollbacks of transactions since supporting rollbacks would have a significant impact on the simplicity and performance of Redis." Its MULTI queues commands, EXEC runs them all, and DISCARD throws the queue away. The undo-log design above is what interviewers usually ask you to build.

8. Many threads: ConcurrentHashMap

A real store serves many clients at once, on many threads (a thread is one line of work running inside a program). HashMap is not thread-safe: put(k, get(k) + 1) is three steps (read, add, write), so two threads can both read 41 and both write 42: a lost update.

ConcurrentHashMap is a map built for many threads, and its merge(key, 1, Integer::sum) does read-add-write as one atomic step (no other thread can get in between).

import java.util.*;  import java.util.concurrent.*;
public class Main { public static void main(String[] args) throws Exception {
    Map<String, Integer> plain = new HashMap<>();             // attempt: a plain HashMap
    Map<String, Integer> safe = new ConcurrentHashMap<>();    // the fix: built for many threads
    plain.put("views", 0);  safe.put("views", 0);
    ExecutorService pool = Executors.newFixedThreadPool(4);   // 4 threads at the same time
    for (int t = 0; t < 4; t++)
        pool.submit(() -> {
            for (int i = 0; i < 250_000; i++) {
                plain.put("views", plain.get("views") + 1);   // read, add, write: 3 separate steps
                safe.merge("views", 1, Integer::sum);         // one atomic step
            } });
    pool.shutdown();  pool.awaitTermination(1, TimeUnit.MINUTES);
    System.out.printf("%-18s %d%n", "expected", 4 * 250_000);
    System.out.printf("%-18s %d%n", "HashMap", plain.get("views"));
    System.out.printf("%-18s %d%n", "ConcurrentHashMap", safe.get("views"));
} }

Output (one run; the HashMap number changes every run):

expected           1000000
HashMap            879648
ConcurrentHashMap  1000000

ConcurrentHashMap does not allow null keys or values: put("k", null) throws NullPointerException. For a whole transaction (several keys), one atomic method is not enough: lock the store or the keys the transaction touches (episodes 46 to 50).

9. Surviving a restart: the write-ahead log and snapshots

Everything lives in RAM, so a restart empties the store. The fix is the shoe stand's register book:

  • A write-ahead log (WAL): before changing memory, append the change to a file on disk. "Write ahead" means the log is written first; if we crash after writing it, the change is safe.
  • Replay: on start, read the log line by line and apply each change again.
  • Snapshot: the log grows forever, so now and then save a full copy of the data to disk and keep only the log written after it. On start: load the snapshot, then replay the short log.
import java.nio.file.*;  import java.util.*;
class DurableStore {
    final Map<String, String> data = new HashMap<>();  final Path wal;
    DurableStore(Path wal) throws Exception {
        this.wal = wal;
        if (Files.exists(wal))                               // on start: REPLAY the log
            for (String line : Files.readAllLines(wal)) apply(line);
    }
    private void apply(String line) {
        String[] p = line.split(" ", 3);
        if (p[0].equals("SET")) data.put(p[1], p[2]);  else data.remove(p[1]); }
    void write(String line) throws Exception {
        Files.writeString(wal, line + "\n", StandardOpenOption.CREATE, StandardOpenOption.APPEND);  // 1. log
        apply(line); }                                       // 2. then change memory
}
public class Main { public static void main(String[] args) throws Exception {
    Map<String, String> memoryOnly = new HashMap<>(Map.of("cart:asha", "5 items"));
    memoryOnly = new HashMap<>();                            // attempt: the process restarts...
    System.out.println("memory only, after restart: " + memoryOnly);
    Path wal = Path.of("store.wal");  Files.deleteIfExists(wal);
    DurableStore s = new DurableStore(wal);
    s.write("SET cart:asha 5 items");  s.write("SET cart:ravi 1 item");  s.write("DEL cart:ravi");
    s = null;                                                // crash: everything in memory is gone
    DurableStore again = new DurableStore(wal);              // restart: read the log back
    System.out.println("with a WAL, after restart:  " + again.data);
    System.out.println("the log on disk: " + Files.readAllLines(wal)); } }

Output:

memory only, after restart: {}
with a WAL, after restart:  {cart:asha=5 items}
the log on disk: [SET cart:asha 5 items, SET cart:ravi 1 item, DEL cart:ravi]

The memory-only map is empty after the restart. The durable store replays three lines; Ravi's cart is gone because the DEL was replayed too. (Real databases also call fsync so the operating system really writes the file to the disk before saying OK.)

10. The class diagram

Client ──"SET cart:asha 5"──▶ CommandParser ──▶ KVStore
KVStore: Map<String, Entry>  (ConcurrentHashMap for many threads)
  Entry(value, expiresAt)   get() = lazy expiry · sweep() = active expiry
  put / get / delete: O(1) on average      typed get(key, Class<T>)
Transactions: Deque<undo log>  BEGIN push · ROLLBACK pop + restore
              COMMIT pop + merge into the parent's undo log (nested)
Durability: write-ahead log (append, then apply) + replay on start
            snapshot = full copy at a moment; then only the log since

11. Interview follow-ups

Question Answer
Memory is full An eviction policy, e.g. LRU (least recently used, episode 65)
Transactions with many threads Lock the keys a transaction touches, or one lock for the store
Too much data for one machine Sharding: split keys across machines by hash(key) % machines
A machine dies Replicas: copies of the data on other machines
The log is huge Snapshots plus a short log; or rewrite the log from the current data
Expire many keys without freezing Sample random keys a few times a second (Redis-style)

12. Common mistakes

Mistake What you see (real message) Why Fix
A list of pairs cart:asha = 2 items, and 2,000 gets take over a second Duplicates, linear search A HashMap
Raw cast of a stored value java.lang.ClassCastException: class java.lang.String cannot be cast to class java.lang.Integer The value is another type A typed get with isInstance
Unboxing a missing value java.lang.NullPointerException: Cannot invoke "java.lang.Integer.intValue()" because the return value of "java.util.Map.get(Object)" is null get returned null Check for null, or getOrDefault
Removing while looping over keySet() java.util.ConcurrentModificationException The map changed under the loop map.values().removeIf(...) or an Iterator.remove()
Only lazy expiry at 200 s: 100001 entries still in memory Nobody reads dead keys Add an active sweep
Two writes, no transaction total money: 600 (was 700) Half a change BEGIN / ROLLBACK
HashMap with many threads HashMap far below 1000000, different every run Lost updates ConcurrentHashMap.merge
null in a ConcurrentHashMap java.lang.NullPointerException at ConcurrentHashMap.putVal It forbids null keys and values Use a sentinel, or remove
A switch expression with no default error: the switch expression does not cover all possible input values A String switch can't list every value Add default ->
GET typed with no key java.lang.ArrayIndexOutOfBoundsException: Index 1 out of bounds for length 1 The parser read p[1] Check the word count; reply with an error

Mini project: MiniRedis

SET, GET, DEL, INCR, EXPIRE, TTL, nested BEGIN/COMMIT/ROLLBACK, lazy expiry plus a Redis-style sampled sweep, a write-ahead log that records only committed changes, and replay on restart. TTL answers like Redis: seconds left, -1 for no expiry, -2 for a missing key.

import java.nio.file.*;
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;

// Mini project: a small Redis-like store. SET, GET, DEL, INCR, EXPIRE, TTL, BEGIN, COMMIT, ROLLBACK,
// lazy + sampled active expiry, typed integer values, a write-ahead log and replay on start.
class Clock { long now = 0; }

record Entry(String value, long expiresAt) {              // expiresAt = -1: never expires
    boolean expired(long now) { return expiresAt != -1 && now >= expiresAt; }
}

class MiniRedis {
    private static final Entry ABSENT = new Entry(null, -1);
    private final Map<String, Entry> data = new ConcurrentHashMap<>();
    private final Deque<Map<String, Entry>> undo = new ArrayDeque<>();
    private final Clock clock;
    private final Path wal;
    private final Random random = new Random(7);
    private boolean replaying = false;

    MiniRedis(Clock clock, Path wal) throws Exception {
        this.clock = clock;
        this.wal = wal;
        if (Files.exists(wal)) {                             // replay the log on start
            replaying = true;
            for (String line : Files.readAllLines(wal)) run(line);
            replaying = false;
        }
    }

    private Entry live(String k) {                            // lazy expiry
        Entry e = data.get(k);
        if (e != null && e.expired(clock.now)) { data.remove(k); return null; }
        return e;
    }

    private void remember(String k) {
        if (!undo.isEmpty()) undo.peek().putIfAbsent(k, data.getOrDefault(k, ABSENT));
    }

    private void log(String line) throws Exception {
        if (!replaying && undo.isEmpty())                     // only committed changes reach the log
            Files.writeString(wal, line + "\n", StandardOpenOption.CREATE, StandardOpenOption.APPEND);
    }

    private final Deque<List<String>> pending = new ArrayDeque<>();  // log lines of each open transaction

    private void change(String line) throws Exception {
        if (replaying) return;
        if (undo.isEmpty()) log(line); else pending.peek().add(line);
    }

    int sweep(int sample) {                                   // Redis-style: test random keys, repeat if > 25% expired
        int removed = 0;
        while (true) {
            List<String> withTtl = new ArrayList<>();
            for (var e : data.entrySet()) if (e.getValue().expiresAt() != -1) withTtl.add(e.getKey());
            if (withTtl.isEmpty()) return removed;
            int expired = 0, n = Math.min(sample, withTtl.size());
            for (int i = 0; i < n; i++) {
                String k = withTtl.get(random.nextInt(withTtl.size()));
                Entry e = data.get(k);
                if (e != null && e.expired(clock.now)) { data.remove(k); expired++; }
            }
            removed += expired;
            if (expired * 4 <= n) return removed;            // 25% or fewer expired: stop
        }
    }

    String run(String line) throws Exception {
        String[] p = line.trim().split("\\s+");
        String cmd = p[0].toUpperCase();
        try {
            switch (cmd) {
                case "SET": {
                    remember(p[1]);
                    data.put(p[1], new Entry(p[2], -1));
                    change(line);
                    return "OK";
                }
                case "GET": { Entry e = live(p[1]); return e == null ? "(nil)" : e.value(); }
                case "DEL": {
                    remember(p[1]);
                    boolean had = live(p[1]) != null;
                    data.remove(p[1]);
                    change(line);
                    return had ? "1" : "0";
                }
                case "INCR": {
                    Entry e = live(p[1]);
                    long v;
                    try { v = e == null ? 0 : Long.parseLong(e.value()); }
                    catch (NumberFormatException x) { return "ERR value is not an integer"; }
                    remember(p[1]);
                    data.put(p[1], new Entry(Long.toString(v + 1), e == null ? -1 : e.expiresAt()));
                    change(line);
                    return Long.toString(v + 1);
                }
                case "EXPIRE": {                              // EXPIRE key seconds (absolute time is logged)
                    Entry e = live(p[1]);
                    if (e == null) return "0";
                    long at = replaying ? Long.parseLong(p[2]) : clock.now + Long.parseLong(p[2]) * 1000;
                    remember(p[1]);
                    data.put(p[1], new Entry(e.value(), at));
                    change("EXPIRE " + p[1] + " " + at);
                    return "1";
                }
                case "TTL": {
                    Entry e = live(p[1]);
                    if (e == null) return "-2";
                    if (e.expiresAt() == -1) return "-1";
                    return Long.toString((e.expiresAt() - clock.now + 999) / 1000);
                }
                case "BEGIN": undo.push(new HashMap<>()); pending.push(new ArrayList<>()); return "OK";
                case "ROLLBACK": {
                    if (undo.isEmpty()) return "ERR no transaction";
                    undo.pop().forEach((k, old) -> { if (old == ABSENT) data.remove(k); else data.put(k, old); });
                    pending.pop();                                   // rolled-back changes never reach the log
                    return "OK";
                }
                case "COMMIT": {
                    if (undo.isEmpty()) return "ERR no transaction";
                    Map<String, Entry> inner = undo.pop();
                    List<String> lines = pending.pop();
                    if (!undo.isEmpty()) { inner.forEach(undo.peek()::putIfAbsent); pending.peek().addAll(lines); }
                    else for (String l : lines) log(l);            // outermost commit: write to the log
                    return "OK";
                }
                default: return "ERR unknown command '" + p[0] + "'";
            }
        } catch (ArrayIndexOutOfBoundsException e) {
            return "ERR wrong number of arguments for '" + cmd + "'";
        }
    }
}

public class Main {
    public static void main(String[] args) throws Exception {
        Path wal = Path.of("mini.wal");
        Files.deleteIfExists(wal);
        Clock clock = new Clock();
        MiniRedis r = new MiniRedis(clock, wal);
        String[] script = {
            "SET cart:asha 5", "INCR cart:asha", "INCR visits", "INCR visits", "SET name Asha", "INCR name",
            "SET otp:asha 482913", "EXPIRE otp:asha 30", "TTL otp:asha", "TTL name", "TTL nothing",
            "BEGIN", "SET cart:asha 0", "BEGIN", "DEL name", "COMMIT", "ROLLBACK", "GET cart:asha", "GET name",
            "BEGIN", "SET coupon SAVE10", "BEGIN", "SET coupon FREE", "ROLLBACK", "COMMIT", "GET coupon",
            "GET", "FLY away"
        };
        for (String s : script) System.out.printf("%-20s -> %s%n", s, r.run(s));
        clock.now = 31_000;
        System.out.printf("%-20s -> %s%n", "(31 s later) GET otp", r.run("GET otp:asha"));
        for (int i = 0; i < 1000; i++) { r.run("SET tmp:" + i + " x"); r.run("EXPIRE tmp:" + i + " 10"); }
        clock.now = 60_000;
        System.out.println("sampled sweep removed " + r.sweep(20) + " expired keys");
        MiniRedis again = new MiniRedis(clock, wal);            // restart: replay the log
        System.out.println("after restart: cart:asha=" + again.run("GET cart:asha") + " visits="
            + again.run("GET visits") + " name=" + again.run("GET name") + " coupon=" + again.run("GET coupon"));
        System.out.println("log lines: " + Files.readAllLines(wal).size());
    }
}

Output:

SET cart:asha 5      -> OK
INCR cart:asha       -> 6
INCR visits          -> 1
INCR visits          -> 2
SET name Asha        -> OK
INCR name            -> ERR value is not an integer
SET otp:asha 482913  -> OK
EXPIRE otp:asha 30   -> 1
TTL otp:asha         -> 30
TTL name             -> -1
TTL nothing          -> -2
BEGIN                -> OK
SET cart:asha 0      -> OK
BEGIN                -> OK
DEL name             -> 1
COMMIT               -> OK
ROLLBACK             -> OK
GET cart:asha        -> 6
GET name             -> Asha
BEGIN                -> OK
SET coupon SAVE10    -> OK
BEGIN                -> OK
SET coupon FREE      -> OK
ROLLBACK             -> OK
COMMIT               -> OK
GET coupon           -> SAVE10
GET                  -> ERR wrong number of arguments for 'GET'
FLY away             -> ERR unknown command 'FLY'
(31 s later) GET otp -> (nil)
sampled sweep removed 1000 expired keys
after restart: cart:asha=6 visits=2 name=Asha coupon=SAVE10
log lines: 2008

Practice

1. Add EXPIRE key seconds and TTL key commands to the parser.

Answer

EXPIRE finds the live entry and replaces it with new Entry(value, now + seconds * 1000); TTL returns the seconds left, -1 for no expiry and -2 for no key. See MiniRedis.run: EXPIRE otp:asha 30 -> 1, TTL otp:asha -> 30, TTL name -> -1, TTL nothing -> -2.

2. Make the sweep test 20 random keys, Redis-style.

Answer

Collect the keys with an expiry, test up to 20 random ones, delete the expired ones, and repeat while more than 25% of the sample was expired. See MiniRedis.sweep: sampled sweep removed 1000 expired keys.

3. Write transactions to the WAL correctly.

Answer

Keep a list of log lines per open transaction. ROLLBACK drops the list; an inner COMMIT adds it to the parent's list; only the outermost COMMIT writes the lines to the file. A crash in the middle of a transaction then leaves nothing half-written in the log. In the mini project, SET coupon FREE was rolled back and never reached the log (grep coupon mini.wal shows only SET coupon SAVE10).

4. Add a snapshot every 1,000 log lines.

Answer

Count lines written. At 1,000: write every live key as SET key value (plus EXPIRE key at) into snapshot.tmp, rename it to snapshot (a rename is all-or-nothing on most file systems), then empty the log. On start: replay snapshot, then the log.

5. Why does EXPIRE write an absolute time (EXPIRE key 1700000) to the log, not "30 seconds"?

Answer

Replay happens later. "30 seconds" replayed after a restart would give the key a fresh 30 seconds; an absolute time keeps the original deadline.

Quick quiz

SET a 1
BEGIN
SET a 2
BEGIN
SET a 3
COMMIT
ROLLBACK
GET a

What does GET a print? (a) 1 (b) 2 (c) 3 (d) NULL

Answer

(a) 1. The inner COMMIT merges its undo log into the outer transaction's; the outer ROLLBACK then undoes both changes. Real run of TxStore:

SET a 1      -> OK
BEGIN        -> OK
SET a 2      -> OK
BEGIN        -> OK
SET a 3      -> OK
COMMIT       -> OK
ROLLBACK     -> OK
GET a        -> 1

Interview questions

  1. Why a HashMap and not a list or a TreeMap? A HashMap gives O(1) average get/put/delete; a list is O(n); a TreeMap is O(log n) but keeps keys sorted (useful only if you need range queries).
  2. Lazy vs active expiry? Lazy checks on read (cheap, but dead keys pile up); active sweeps in the background (frees memory). Real stores use both.
  3. How do you test expiry without waiting? Inject a clock and move it by hand in tests.
  4. How does ROLLBACK work? An undo log of old values per transaction; ROLLBACK restores them, removing keys that were absent.
  5. How do nested transactions work? A stack of undo logs; inner COMMIT merges into the parent; ROLLBACK affects only the innermost.
  6. Snapshot vs undo log? A snapshot copies everything (simple, costly); an undo log copies only changed keys.
  7. Why ConcurrentHashMap? HashMap loses updates under concurrent writes; ConcurrentHashMap is thread-safe and offers atomic merge, compute, putIfAbsent.
  8. What is a write-ahead log? Append each change to disk before applying it in memory; replay it on start.
  9. Why snapshots? To keep the log short: load the snapshot, replay only the log written after it.
  10. Does Redis roll back transactions? No: its documentation says it does not support rollbacks; MULTI/EXEC run a queued group, DISCARD drops it.

Glossary

Term Meaning, with an example
Key-value store Saves values under unique keys and returns them: Redis, or our KVStore
Key The unique name you look up by: cart:asha
Value The data saved under a key: "5 items", 41
put / get / delete Save or replace / read / remove a key's value
In-memory Kept in RAM (fast working memory), lost when the program stops
RAM The computer's fast working memory, wiped on restart
Linear search Looking at items one by one until a match
Big-O, O(1), O(n) How the work grows with the data: constant / grows with n
HashMap A map that uses the key's hash to jump to a bucket: O(1) on average
Hash A number computed from a key: "cart:asha".hashCode()
Bucket One slot of a hash map's internal array
Typed value A value of a specific type: String, Integer
Object The base type of every Java class
Cast Converting a reference to a more specific type: (Integer) v
ClassCastException The error thrown when a cast is to the wrong type
Generic method, type parameter <T> T get(String k, Class<T> t): T is filled in by the caller
TTL (time to live) How long a key may live: 30 seconds for an OTP
OTP One-time password: a short code sent to your phone
expiresAt The moment a key stops being valid: now + TTL
Lazy (passive) expiry Removing an expired key when someone reads it
Active expiry A background sweep that removes expired keys
Sweep One pass of the cleaner: removeIf(expired)
Fake clock A clock moved by hand in tests: clock.now = 31_000
Transaction A group of changes that is all-or-nothing
Atomicity The all-or-nothing property
BEGIN / COMMIT / ROLLBACK Start / keep all / undo all
Snapshot A full copy of the data at one moment
Undo log The old values of the keys a transaction changed
Nested transaction A transaction started inside another
Stack, Deque Last in, first out; ArrayDeque with push/pop/peek
Sentinel A special marker object compared with ==: ABSENT
Command parser Turns a text line into a method call: "SET a 1" → set("a", "1")
switch expression switch that returns a value, with -> and yield
Thread One line of work running inside a program
Thread-safe Works correctly when many threads use it at once
Lost update Two threads both read 41 and write 42: one +1 is lost
Atomic Done as one step no other thread can interrupt
ConcurrentHashMap A thread-safe map with atomic merge, compute, putIfAbsent
merge map.merge(k, 1, Integer::sum): add 1 atomically, or insert 1
Thread pool A fixed set of threads that run submitted tasks
Write-ahead log (WAL) A file each change is appended to before it is applied
Replay Re-applying the log on start to rebuild memory
fsync Asking the OS to really write a file to disk
Eviction policy Which key to drop when memory is full: LRU
Sharding Splitting keys across machines by hash
Replica A copy of the data on another machine
Redis A widely used open-source in-memory key-value store
MULTI / EXEC / DISCARD Redis commands: queue commands / run them / drop the queue

Summary

  • A list of pairs returned the old value and took over a second for 2,000 gets; a HashMap made put, get, delete O(1) on average, and put replaced the value.
  • Typed values: store Object, read with a typed get that checks first; a raw cast throws ClassCastException.
  • TTL: expiresAt = now + ttl; lazy expiry on read plus an active sweep (Redis samples 20 random keys, 10 times a second).
  • Transactions: an undo log per BEGIN on a stack; ROLLBACK restores, inner COMMIT merges into the parent, so nested transactions work. A command parser turns text into calls.
  • ConcurrentHashMap + merge stopped lost updates (the plain HashMap lost tens of thousands of the 1,000,000 updates).
  • A write-ahead log, replayed on start, survived a restart; snapshots keep the log short.
  • Next episode: design a task scheduler.