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. Writingtype: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 (
nullif 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:
putnever checked for an existing key, so the cart got a second pair, andgetfound the old one first:2 items, not5 items. - Slow:
getis a linear search: it looks at the items one by one, so its cost is O(n) (it grows with the number of itemsn). 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:putreplaced the value.- 2,000 gets: a few milliseconds instead of more than a second.
deletereturnstruethe first time andfalsethe second: nothing was left to remove.- The typed get explains the problem; the raw cast
(Integer) s.get("cart:asha")throwsClassCastException.
<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 withmap.removeinside afor (String k : map.keySet())loop throwsConcurrentModificationException(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 raviisNULL;ROLLBACKbrings backasha 500andravi 200. - Nested: the inner
COMMITkeepsravi 300for now; the outerROLLBACKundoes both changes. ROLLBACKwith 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
- 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).
- 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.
- How do you test expiry without waiting? Inject a clock and move it by hand in tests.
- How does ROLLBACK work? An undo log of old values per transaction; ROLLBACK restores them, removing keys that were absent.
- How do nested transactions work? A stack of undo logs; inner COMMIT merges into the parent; ROLLBACK affects only the innermost.
- Snapshot vs undo log? A snapshot copies everything (simple, costly); an undo log copies only changed keys.
- Why ConcurrentHashMap? HashMap loses updates under concurrent writes; ConcurrentHashMap is thread-safe and offers atomic
merge,compute,putIfAbsent. - What is a write-ahead log? Append each change to disk before applying it in memory; replay it on start.
- Why snapshots? To keep the log short: load the snapshot, replay only the log written after it.
- Does Redis roll back transactions? No: its documentation says it does not support rollbacks;
MULTI/EXECrun a queued group,DISCARDdrops 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
putreplaced the value. - Typed values: store
Object, read with a typed get that checks first; a raw cast throwsClassCastException. - 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 +
mergestopped 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.