A database, and time

Where we are going

$ redis-cli set name Subash
OK
$ redis-cli get name
"Subash"
$ redis-cli set session abc123 px 100
OK
$ sleep 0.2
$ redis-cli get session
(nil)

flowchart LR
    A[Part 4<br/>commands, no memory] --> B[Stage 14<br/>RedisStore]
    B --> C[Stage 15<br/>SET and GET]
    C --> D[Stage 16<br/>expiry]
    D --> E([Part 6<br/>atomicity])

Everything so far has been stateless. Each command was a pure function of its arguments. This post adds the state, and with it every concurrency problem the project will have.

Stage 14, the store

Goal. One store, shared by every connection.

The idea

The first decision is ownership, and the tempting shape is wrong.

flowchart TD
    subgraph WRONG
        SH[SetHandler] --> M1[(HashMap)]
        GH[GetHandler] --> M2[(a different HashMap)]
    end
    subgraph RIGHT
        MA[main] --> ST[(RedisStore)]
        SET2[SET] --> ST
        GET2[GET] --> ST
    end

Ownership runs downward. main creates one store, hands it to the dispatcher, and every client thread shares that instance. Commands use the store. They never own it.

Concretely, CommandDispatcher stops being all-static and becomes an instance holding a RedisStore. That is not ceremony. It is what lets each test create a fresh dispatcher with an empty store. Static state leaks between tests and produces failures that depend on execution order.

Which map

Three options here, and the reasoning is more useful than the answer.

A plain HashMap is unsafe. Two threads resizing it concurrently can corrupt it outright: lost writes, and historically infinite loops on lookup. Not theoretical.

Wrapping a HashMap in synchronized is the reflex answer and wrong twice over. Every operation takes one global lock, so a hundred clients reading a hundred different keys queue behind each other. It also fails to solve the harder problem:

if (!store.containsKey(k)) store.put(k, v);   // two threads can both pass the check

Wrapping each call in a lock does not make the pair atomic.

ConcurrentHashMap makes single-key operations atomic for free, lets unrelated keys proceed without contending, and exposes atomic compound operations you need within two stages:

Method	Used by
`putIfAbsent`	`SETNX` in Part 9
`compute`	`INCR` in Part 6, expiry in this post
`computeIfPresent`	every read that must check expiry

Choose it for the compound operations, not because “thread safe” appears in the docs.

Null is not allowed, and that helps

ConcurrentHashMap rejects null keys and values. That maps exactly onto Redis semantics:

map.get(key) == null   ⟺   the key is absent

No ambiguity between “stored a null” and “not there”. Redis needs that distinction sharp:

SET k ""   then  GET k  →  $0\r\n\r\n    stored, empty
                 GET x  →  $-1\r\n       absent

Your writer already tells those apart. Now the store must not blur them.

The code

src/main/java/com/example/redis/RedisStore.java:

package com.example.redis;

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

// Shared key-value state. One instance per server, used by every client thread.
public class RedisStore {

    // ConcurrentHashMap over a synchronized map: unrelated keys don't contend,
    // and it gives us atomic compound operations we need shortly
    private final Map<String, String> data = new ConcurrentHashMap<>();

    public void set(String key, String value) {
        data.put(key, value);
    }

    // null means the key is absent, the map refuses to store nulls so there's no ambiguity
    public String get(String key) {
        return data.get(key);
    }
}

The dispatcher becomes an instance:

private final RedisStore store;

public CommandDispatcher(RedisStore store) {
    this.store = store;
}

with execute, ping, and echo losing their static.

In Main, one store for the whole server, created before the accept loop:

// one store for the whole server, shared by every client thread
CommandDispatcher dispatcher = new CommandDispatcher(new RedisStore());

while (true) {
    Socket clientSocket = serverSocket.accept();
    new Thread(() -> handleClient(clientSocket, dispatcher)).start();
}

That parameter on handleClient is the whole ownership story in one signature. Created once at the top, passed down, never constructed per connection.

What usually goes wrong

I wrote it wrong first, and it compiled:

public static RedisStore store = null;
public CommandDispatcher(RedisStore store) { CommandDispatcher.store = store; }

Every new CommandDispatcher(...) overwrites the store for every dispatcher that already exists, including ones on other threads. It is the anti-pattern the stage warns about, moved up one level.

Two tests pin the fix:

@Test
void freshDispatcherStartsEmpty() {
    reply("SET", "name", "Subash");

    // a separate dispatcher must not see the other one's data
    CommandDispatcher other = new CommandDispatcher(new RedisStore());
    assertEquals("$-1\r\n", replyFrom(other, "GET", "name"));
}

@Test
void storeIsSharedAcrossDispatchersUsingTheSameStore() {
    RedisStore shared = new RedisStore();
    CommandDispatcher writer = new CommandDispatcher(shared);
    CommandDispatcher reader = new CommandDispatcher(shared);

    writer.execute(new String[]{"SET", "shared", "hello"});
    assertEquals("$5\r\nhello\r\n", replyFrom(reader, "GET", "shared"));
}

Stage 15, SET and GET

Goal. Store a value on one connection, read it on another.

The code

case "SET" -> set(command);
case "GET" -> get(command);

private byte[] set(String[] command) {
    if (command.length != 3) {
        return RespWriter.error("ERR wrong number of arguments for 'set' command");
    }
    store.set(command[1], command[2]);
    return RespWriter.simpleString("OK");
}

private byte[] get(String[] command) {
    if (command.length != 2) {
        return RespWriter.error("ERR wrong number of arguments for 'get' command");
    }
    // bulkString turns a null into $-1 for us
    return RespWriter.bulkString(store.get(command[1]));
}

SET overwrites unconditionally and always replies +OK. There is no “already existed” signal.

Options like EX, PX, and NX come next stage. For now treat extra arguments as an arity error rather than ignoring them. Silently ignoring an option a client sent is worse than refusing it, because the client believes the expiry was set.

Run it

$ redis-cli set name Subash
OK
$ redis-cli get name
"Subash"
$ redis-cli get nothing
(nil)

Notice that

Each of those is a separate redis-cli invocation, so each opened its own TCP connection. Writing on one and reading on another is the entire point of Stage 14. If get name returns (nil), your store is per connection rather than per server.

Empty and missing stay distinct:

$ redis-cli set empty ""
OK
$ redis-cli get empty
""
$ redis-cli get ghost
(nil)

Try it yourself

Run 20 SETs concurrently and read them back:

for i in $(seq 1 20); do (redis-cli set key$i val$i >/dev/null &) ; done
redis-cli get key20

Move new RedisStore() inside handleClient, so each connection makes its own. Now set then get from two terminals returns (nil). Undo it. That is the bug the design prevents.
Run redis-cli set k v EX 10. An arity error today. Note it, because the next stage makes it valid.

Stage 16, expiry

Goal. SET foo bar PX 100 and the key is gone 100 milliseconds later.

The idea

Every previous command was a pure function of its arguments plus the map. This one depends on when it runs, and time is the hardest dependency to test. Four decisions follow, each with a wrong answer that looks fine.

Which clock

System.currentTimeMillis() is wrong. It is wall-clock time, and wall-clock time moves backwards: NTP corrections, daylight saving, someone setting the clock. A key due to expire in 100ms can outlive its expiry by an hour if the clock jumps back.

System.nanoTime() is right. It is monotonic, so it only moves forward and ignores clock adjustments. Its absolute value is meaningless, and you never need the absolute value. You need to know whether now is past a particular instant.

Wall clock for timestamps you show a human. Monotonic clock for durations.

Lazy or active expiry

Redis does both. You need only the first.

Lazy expiry checks on read. If the key is expired, remove it and report a miss. It costs nothing while nobody reads.

Active expiry runs a background thread sampling random keys. Redis needs it because a key nobody ever reads again would otherwise hold memory forever. You do not have that problem, and adding a sweeper thread solves nothing you have.

Lazy expiry has one consequence worth saying out loud. GET becomes a write, because a read can remove a key.

Making the check atomic

The obvious code races:

sequenceDiagram
    participant A as Thread A (GET)
    participant M as the map
    participant B as Thread B (SET)
    A->>M: read entry, it is expired
    B->>M: SET key newvalue
    A->>M: remove(key)
    Note over M: B's fresh write is gone

computeIfPresent fixes it. The function runs atomically for that key, and returning null removes the mapping:

// the only place expiry is decided, every command goes through this
private Entry live(String key) {
    long now = clock.getAsLong();
    return data.computeIfPresent(key, (k, e) -> e.isExpired(now) ? null : e);
}

This is the payoff for choosing ConcurrentHashMap in Stage 14. A synchronized map could only have done this by holding a global lock across both operations.

Testing time without sleeping

If the store calls System.nanoTime() directly, every expiry test needs Thread.sleep(120). Slow, and flaky on a loaded CI box.

Take the clock as a LongSupplier instead, defaulting to System::nanoTime. Tests pass a mutable fake and move time by assignment. Three lines of production code, and it is the one place so far where an injected dependency clearly earns its keep.

The code

The store gains an entry type, a clock, and expiry-aware reads:

private static final long NEVER = Long.MAX_VALUE;

private record Entry(String value, long expiresAtNanos) {
    boolean isExpired(long now) {
        return now >= expiresAtNanos;
    }
}

private final Map<String, Entry> data = new ConcurrentHashMap<>();

// nanoTime is monotonic, wall clock jumps backwards and would resurrect expired keys
private final LongSupplier clock;

public RedisStore() {
    this(System::nanoTime);
}

// package-private so tests can move time without sleeping
RedisStore(LongSupplier clock) {
    this.clock = clock;
}

public void set(String key, String value) {
    data.put(key, new Entry(value, NEVER));
}

public void set(String key, String value, long ttlMillis) {
    data.put(key, new Entry(value, expiryFrom(ttlMillis)));
}

public String get(String key) {
    Entry entry = live(key);
    return entry == null ? null : entry.value();
}

private long expiryFrom(long ttlMillis) {
    long ttlNanos = ttlMillis * 1_000_000L;
    long expiry = clock.getAsLong() + ttlNanos;

    // an absurd ttl would wrap past Long.MAX_VALUE and land in the past
    return expiry < 0 ? NEVER : expiry;
}

Using Long.MAX_VALUE as “never” means one comparison handles both cases. No Optional, no null check, no special branch.

The two-argument set writes NEVER, which is what makes a plain SET over an expiring key clear its TTL. No extra code. Just do not carry the old entry forward.

The dispatcher parses the options:

long multiplier = switch (command[3].toUpperCase(Locale.ROOT)) {
    case "PX" -> 1L;
    case "EX" -> 1000L;
    default -> 0L;
};
if (multiplier == 0L) {
    return RespWriter.error("ERR syntax error");
}

long amount;
try {
    amount = Long.parseLong(command[4]);
} catch (NumberFormatException e) {
    return RespWriter.error("ERR value is not an integer or out of range");
}
if (amount <= 0) {
    return RespWriter.error("ERR invalid expire time in 'set' command");
}

store.set(command[1], command[2], amount * multiplier);
return RespWriter.simpleString("OK");

The tests

private long now = 0;
private final RedisStore store = new RedisStore(() -> now);

private static long millis(long ms) {
    return ms * 1_000_000L;
}

@Test
void valueIsReadableBeforeExpiry() {
    store.set("foo", "bar", 100);
    now = millis(99);
    assertEquals("bar", store.get("foo"));
}

@Test
void valueIsGoneAtTheExpiryInstant() {
    store.set("foo", "bar", 100);
    now = millis(100);
    assertNull(store.get("foo"));
}

@Test
void plainSetClearsAnExistingTtl() {
    store.set("temp", "v", 100);
    store.set("temp", "v2");
    now = millis(5000);
    assertEquals("v2", store.get("temp"));
}

@Test
void expiredKeyIsRemovedNotJustHidden() {
    store.set("foo", "bar", 100);
    now = millis(200);
    assertNull(store.get("foo"));

    // a hidden-but-present entry would come back when the clock rewinds
    now = 0;
    assertNull(store.get("foo"));
}

Instant, deterministic, and testing the exact boundary rather than “roughly a tenth of a second”. That last one is a neat trick. Winding the clock backwards distinguishes removed from hidden with no extra API.

Run it

$ mvn test
[INFO] Tests run: 65, Failures: 0, Errors: 0

$ redis-cli set foo bar px 100
OK
$ redis-cli get foo
"bar"
$ sleep 0.25
$ redis-cli get foo
(nil)

Plain SET clears the TTL:

$ redis-cli set temp v px 100
$ redis-cli set temp v2
$ sleep 0.25
$ redis-cli get temp
"v2"

Notice that

The key with no TTL survived, the one with a TTL did not, and overwriting removed the deadline. Three behaviours from one Entry record and one comparison.

Try it yourself

Change expiryFrom to use System.currentTimeMillis() and set your system clock back a minute. The key comes back from the dead. Put it back afterwards.
Replace computeIfPresent with a plain get followed by remove, then run the concurrency tests from Part 6 when you reach them. This is the race the atomic version prevents.
Set PX 0 and PX -1. Both are errors in Redis, not “expire immediately”.

What usually goes wrong

Two bugs I shipped, which cancelled each other out:

long ttlNanos = ttlMillis / 1_000_000;              // should be *
return expiry > 0 ? NEVER : expiry;                 // should be < 0

Divide instead of multiply, and every TTL becomes zero nanoseconds, so everything expires instantly. Inverted overflow guard, and every positive expiry becomes NEVER, so nothing expires at all. Together they produced something plausible, and a test asserting only “the key is still there” would have passed.

What caught them was asserting the boundary, present at 99ms and gone at exactly 100ms, plus a test named absurdTtlSaturatesInsteadOfWrapping that pins which way the overflow guard points.

One more, found only by comparing against the real client:

$ redis-cli expire k 5
(integer) 1
$ redis-cli ttl k
(integer) 4        ← real redis says 5

Integer division truncating 4999ms. Redis rounds seconds up:

return RespWriter.integer((millis + divisor - 1) / divisor);

Unit tests never caught it, because they used exact multiples.

Go deeper: how real Redis expires keys

Redis uses both strategies. Lazy expiry on access, plus an active cycle that samples 20 random keys with a TTL, deletes the expired ones, and repeats if more than a quarter were expired. A probabilistic sweep that keeps memory bounded without scanning the keyspace.

It also has to propagate expiry to replicas explicitly, because a replica must not expire keys on its own clock. That comes up in Part 11.

Redis key expiration
System.nanoTime Javadoc, which states plainly that it has no relation to wall time
ConcurrentHashMap Javadoc, the class notes on atomicity

What you built

A real database. Shared state, correct under concurrency, with keys that disappear on schedule.

Checkpoint

Why is synchronized around a HashMap both slower and insufficient?
Why is it useful that ConcurrentHashMap refuses to store nulls?
Why is currentTimeMillis wrong for expiry, given it is what a human would use?
Why does lazy expiry make GET a mutating operation?
Write the interleaving where a naive check-then-remove destroys a fresh write.

Resources

The commands where reading a value, changing it, and writing it back stops being safe. A test with two threads finds what a single-threaded test never will.

Part 6: Atomic or Wrong →

You will build

You will understand

Where we are going

Stage 14, the store

The idea

Which map

Null is not allowed, and that helps

The code

What usually goes wrong

Stage 15, SET and GET

The code

Run it

Notice that

Try it yourself

Stage 16, expiry

The idea

Which clock

Lazy or active expiry

Making the check atomic

Testing time without sleeping

The code

The tests

Run it

Notice that

Try it yourself

What usually goes wrong

What you built

Checkpoint

Resources

Next