Atomic or wrong

Where we are going

$ redis-cli set counter 10
$ redis-cli incr counter
(integer) 11
$ redis-cli rpush fruits apple banana
(integer) 2
$ redis-cli lrange fruits 0 -1
1) "apple"
2) "banana"
$ redis-cli get fruits
(error) WRONGTYPE Operation against a key holding the wrong kind of value

flowchart LR
    A[Part 5<br/>SET GET expiry] --> B[Stage 17<br/>inspection, one expiry check]
    B --> C[Stage 18<br/>INCR, atomically]
    C --> D[Stage 19<br/>lists and WRONGTYPE]
    D --> E([Part 7<br/>blocking and transactions])

Stage 17, inspecting keys

Goal. EXISTS, DEL, TYPE, and KEYS, all agreeing with GET about what exists.

The idea

Right now expiry lives inside get. Add three more commands naively and you have four copies of the same check, which will drift the first time you change one.

The drift is silent, which is what makes it dangerous:

SET k v PX 100
... 200ms later ...
GET k       →  (nil)     correct
EXISTS k    →  1         wrong, and the two now disagree

A key that does not exist but reports existing makes a client’s if (exists) get() return null and crash.

So this stage is really a refactor. One expiry-aware lookup that every command goes through.

flowchart TD
    L["live(key)<br/><i>the only place expiry is decided</i>"]
    GET --> L
    EXISTS --> L
    TYPE --> L
    KEYS --> L
    DEL -.->|checks existence first| L

The code

Extract the lookup, then build on it:

// 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);
}

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

public boolean exists(String key) {
    return live(key) != null;
}

// true only if a live key was removed, so an expired key doesn't inflate DEL's count
public boolean delete(String key) {
    boolean existed = exists(key);
    data.remove(key);
    return existed;
}

// everything is a string until lists arrive
public String type(String key) {
    return exists(key) ? "string" : "none";
}

Notice get collapsed to two lines. The refactor paid for itself immediately.

KEYS needs pattern matching. Support * and ?, and skip character classes:

private static Pattern globToRegex(String glob) {
    StringBuilder regex = new StringBuilder();
    for (char c : glob.toCharArray()) {
        switch (c) {
            case '*' -> regex.append(".*");
            case '?' -> regex.append('.');
            default -> regex.append(Pattern.quote(String.valueOf(c)));
        }
    }
    return Pattern.compile(regex.toString(), Pattern.DOTALL);
}

Pattern.quote on every other character means a key containing . or ( cannot inject regex syntax. Glob metacharacters are only the ones you translate.

Integer replies, and a surprise

EXISTS and DEL are the first commands returning :. Both take several keys, which is why the reply is a count rather than a boolean.

long count = 0;
// duplicates count more than once, that's real redis behaviour
for (int i = 1; i < command.length; i++) {
    if (store.exists(command[i])) {
        count++;
    }
}
return RespWriter.integer(count);

EXISTS k k returns :2 when k exists. It counts arguments that exist, not distinct keys. Surprising, documented, and easy to break by deduplicating into a set.

DEL k k returns :1, because the second delete removes nothing.

Run it

$ redis-cli exists name
(integer) 1
$ redis-cli exists name city missing
(integer) 2
$ redis-cli exists name name
(integer) 2
$ redis-cli type name
string
$ redis-cli type missing
none
$ redis-cli del name missing
(integer) 1

The check that matters:

$ redis-cli set temp v px 100
$ sleep 0.3
$ redis-cli get temp     # (nil)
$ redis-cli exists temp  # (integer) 0
$ redis-cli type temp    # none
$ redis-cli del temp     # (integer) 0
$ redis-cli keys '*'     # temp absent

Notice that

All five commands agree. Before the refactor, GET said “here is your value” while the others said “gone”. One live() is the difference.

Try it yourself

Make exists read data.get(key) directly, bypassing live(). Set a key with PX 100, wait, then compare GET and EXISTS. That disagreement is the bug this stage exists to prevent.
Run redis-cli keys 'user:*' after setting user:1, user:2, and other.
Remove Pattern.quote and run KEYS a.b against keys a.b and axb. Both match, because the dot became a wildcard.

What usually goes wrong

DEL counts keys that were already expired. You removed before checking existence.

KEYS returns expired keys. The filter uses the raw map instead of exists().

Stage 18, INCR, and the race that eats your data

Goal. INCR, DECR, INCRBY, and DECRBY, correct under concurrency.

The idea

Redis has no integer type. counter is stored as the string "10". INCR parses it, adds one, and writes "11" back. TYPE counter still says string.

That makes INCR a read-modify-write, and the obvious implementation is wrong:

sequenceDiagram
    participant A as Client A
    participant S as the store
    participant B as Client B
    A->>S: read counter → 10
    B->>S: read counter → 10
    A->>S: write 11
    B->>S: write 11
    Note over S: two increments,<br/>one result

Two clients, two increments, one result. Nothing throws, nothing logs, the counter is simply wrong. Only under concurrency, so it will never show up in manual testing.

This is the first command where thread per connection from Part 2 collides with shared state from Part 5. Every previous command was a single map operation, which ConcurrentHashMap made atomic for free. This one is not.

The code

compute() runs its function atomically for that key. Nothing can interleave.

// read-modify-write must happen inside compute(), or concurrent increments get lost.
// throws NumberFormatException if the stored value isn't an integer,
// ArithmeticException on overflow
public long increment(String key, long delta) {
    long now = clock.getAsLong();
    long[] result = new long[1];

    data.compute(key, (k, existing) -> {
        // an expired key is a missing key, so start from 0 rather than the stale value
        boolean usable = existing != null && !existing.isExpired(now);

        long current = usable ? Long.parseLong(existing.value()) : 0L;
        result[0] = Math.addExact(current, delta);

        // a live key keeps its ttl, incrementing must not make a counter immortal
        long expiry = usable ? existing.expiresAtNanos() : NEVER;
        return new Entry(Long.toString(result[0]), expiry);
    });

    return result[0];
}

The parse, the add, and the format all sit inside the lambda. Pull the parse out to keep the lambda simple and the race comes straight back.

The long[1] is unavoidable. compute returns the new Entry, not your number, and a lambda cannot assign to a local. A one-element array is the standard workaround.

Math.addExact throws on overflow rather than wrapping. Writing the bounds check by hand is easy to get wrong in a way that itself overflows.

The TTL is carried forward. Real Redis does not reset expiry on increment, so a counter set with PX 1000 still disappears a second later however many times you increment it. Getting this wrong makes a counter immortal, and nothing in a single-threaded test notices.

One useful property: if parseLong or addExact throws inside the lambda, compute propagates it and leaves the mapping untouched. A failed INCR does not corrupt the key.

The test that justifies the design

@Test
void concurrentIncrementsLoseNothing() throws InterruptedException {
    // fails reliably against a get-then-set implementation
    RedisStore shared = new RedisStore();
    int threads = 4;
    int perThread = 1000;

    Thread[] workers = new Thread[threads];
    for (int t = 0; t < threads; t++) {
        workers[t] = new Thread(() -> {
            for (int i = 0; i < perThread; i++) {
                shared.increment("counter", 1);
            }
        });
        workers[t].start();
    }
    for (Thread worker : workers) {
        worker.join();
    }

    assertEquals("4000", shared.get("counter"));
}

4,000 increments, asserted exactly. It fails reliably against get-then-set and passes against compute().

Run it

$ redis-cli set counter 10
$ redis-cli incr counter        # (integer) 11
$ redis-cli incrby counter 5    # (integer) 16
$ redis-cli decr counter        # (integer) 15
$ redis-cli incr fresh          # (integer) 1, missing key starts at 0
$ redis-cli set word hello
$ redis-cli incr word
(error) ERR value is not an integer or out of range

TTL survives increments:

$ redis-cli set tick 0 px 300
$ redis-cli incr tick      # (integer) 1
$ sleep 0.5
$ redis-cli get tick       # (nil), not immortal

Notice that

GET counter returns a bulk string, and TYPE counter says string. INCR is parse, add, and format on text rather than arithmetic on a number. That is why INCR on "abc" is an error rather than a type mismatch.

Try it yourself

Rewrite increment as get then set and run the concurrency test. Watch it fail, then watch it pass occasionally, which is what makes this class of bug unpleasant.
Drop the TTL carry-forward by writing long expiry = NEVER; and run the tick experiment above. The counter never expires.
redis-cli set c 9223372036854775807; redis-cli incr c gives an overflow error, and the value is unchanged.

What usually goes wrong

Four bugs from my own first attempt, all in one method:

delta.compute(key, ...)                              // should be data.compute
long current = usable ? Long.parseLong(...);         // missing : 0L
existing.expiredAtNanos()                            // typo for expiresAtNanos()

The first is the interesting one. delta.compute is a call on a long, so the compiler caught it. The shape of the bug, operating on the wrong thing inside an atomic block, is exactly what silently loses increments when it does compile.

Go deeper: what "atomic" actually means here

ConcurrentHashMap.compute holds the bin lock for that key for the duration of the function. It does not lock the whole map, so other keys proceed freely.

The Javadoc warns that the function should be short and must not modify the map itself. Both hold here.

ConcurrentHashMap.compute
java.util.concurrent package summary, the memory-consistency section
Redis INCR

Stage 19, lists, and the cost of a second type

Goal. RPUSH, LPUSH, LRANGE, LLEN, LPOP, and WRONGTYPE when you mix them up.

The idea

Every command so far added a case. This one changes the shape of the store, and the change ripples into commands that already work. The second data type is expensive in a way the first never hinted at.

A value is no longer a String. It is a string or a list. Every command must check what it got, so GET on a list becomes an error rather than a cast. And TYPE finally has something to say.

private record Entry(Object value, long expiresAtNanos) {

    String asString() {
        if (value instanceof String s) {
            return s;
        }
        throw new WrongTypeException();
    }

    @SuppressWarnings("unchecked")
    List<String> asList() {
        if (value instanceof List<?> list) {
            return (List<String>) list;
        }
        throw new WrongTypeException();
    }
}

get and increment change one line each. entry.value() becomes entry.asString(). Without that, a list key returns garbage instead of an error.

Never let an unchecked cast near this. (String) entry.value() on a list key throws ClassCastException, which escapes as a dead connection instead of a reply the client can handle.

WRONGTYPE

-WRONGTYPE Operation against a key holding the wrong kind of value

Exact wording, and no ERR prefix, because WRONGTYPE is itself the error code. Clients switch on it.

This is the first error that originates in the store rather than the dispatcher, which raises a design question. How does it travel? The store cannot write RESP, and returning a sentinel from every method poisons every signature.

A small unchecked exception is the right tool. The store throws, and the dispatcher catches it once:

try {
    return switch (name) { ... };
} catch (WrongTypeException e) {
    return RespWriter.error("WRONGTYPE Operation against a key holding the wrong kind of value");
}

One catch covers every command, present and future.

Thread safety, second time

ConcurrentHashMap made single-key operations atomic. The list inside an entry is a plain ArrayList, and the map knows nothing about it:

thread A: LRANGE reads the list        ← iterating
thread B: RPUSH mutates the same list  ← ConcurrentModificationException, or a torn read

The map protected the mapping, not the object it points at.

The fix is discipline rather than a different collection. Every access to a list, read or write, happens inside a compute() lambda for that key.

That means LRANGE runs inside compute too, which looks strange for a read. It is correct, and cheaper than the alternatives:

Approach	Cost
`CopyOnWriteArrayList`	copies the whole list on every push, O(n) writes
copy on every read	O(n) reads
`compute` plus copy the range	copies only what you return

Always return a copy of the range. Handing a caller a reference to the list that lives in the map is how a thread-safe store leaks a mutable object into unsynchronised code.

LRANGE index arithmetic

This is where the bugs are. LRANGE key start stop is inclusive at both ends, unlike almost every range API you have used.

list = [a, b, c, d, e]

LRANGE key 0 -1     →  everything          -1 is the last element
LRANGE key 0 2      →  a b c               inclusive stop
LRANGE key -2 -1    →  d e                 negatives count from the end
LRANGE key -100 100 →  a b c d e           out of range clamps, never errors
LRANGE key 3 1      →  (empty)             start past stop, not an error
LRANGE missing 0 -1 →  (empty)             missing key is an empty list, not nil

The rules in order. A negative index becomes length + index. Still negative, clamp to 0. A stop at or past length clamps to length - 1. A start greater than stop gives an empty result.

LPUSH reverses

RPUSH k a b   →  [a, b]
LPUSH k a b   →  [b, a]

That is what pushing each element onto the head means, and clients rely on it.

Empty lists do not exist

$ redis-cli rpush k a
(integer) 1
$ redis-cli lpop k
"a"
$ redis-cli exists k
(integer) 0

Redis has no empty collections. Returning null from the compute lambda gives you this for free:

popped[0] = list.removeFirst();

// redis has no empty lists, the key goes away with the last element
return list.isEmpty() ? null : existing;

Run it

$ redis-cli rpush fruits apple banana   # (integer) 2
$ redis-cli lpush fruits cherry         # (integer) 3
$ redis-cli lrange fruits 0 -1
1) "cherry"
2) "apple"
3) "banana"
$ redis-cli type fruits                 # list
$ redis-cli lpop fruits                 # "cherry"

$ redis-cli lpush order a b c
$ redis-cli lrange order 0 -1
1) "c"
2) "b"
3) "a"

Type errors both ways:

$ redis-cli set str hello
$ redis-cli lpush str x
(error) WRONGTYPE Operation against a key holding the wrong kind of value
$ redis-cli get fruits
(error) WRONGTYPE Operation against a key holding the wrong kind of value

Notice that

WRONGTYPE fires in both directions. A list command on a string key, and a string command on a list key. The second only works because get and increment were updated to call asString(). It is easy to add the new type and forget the old commands.

Try it yourself

Delete the LPOP empty-list check and pop the last element. EXISTS now returns 1 for a list with nothing in it, a value Redis cannot represent.
Make lrange return the live list instead of a copy, then have one thread iterate it while another pushes. ConcurrentModificationException.
Run LRANGE k 5 2, LRANGE k -100 100, and LRANGE missing 0 -1. All three return an empty array and none is an error. Work out why that is right for each.

What usually goes wrong

My LPOP was wrong twice in one statement:

popped[0] = list.get(list.size() - 1);   // takes the TAIL, and removes nothing

Wrong end, since that is RPOP, and no removal. The key never empties, LLEN never shrinks, and every LPOP returns the same element forever. It should be list.removeFirst().

Also, Entry still declared String value when the whole point was Object. Three compile errors, all downstream of one line.

What you built

Two data types, five inspection commands, atomic counters, and one expiry check serving all of them.

Checkpoint

Why does EXISTS k k return 2 but DEL k k return 1?
Write the interleaving where two concurrent INCRs produce one increment.
Why must the parse happen inside the compute() lambda?
Why does ConcurrentHashMap not make list mutation safe?
Why does LRANGE need to run inside compute() even though it only reads?

Resources

A command that does not answer immediately, and a transaction that can be told to give up.

Part 7: Waiting and Pretending →

You will build

You will understand

Where we are going

Stage 17, inspecting keys

The idea

The code

Integer replies, and a surprise

Run it

Notice that

Try it yourself

What usually goes wrong

Stage 18, INCR, and the race that eats your data

The idea

The code

The test that justifies the design

Run it

Notice that

Try it yourself

What usually goes wrong

Stage 19, lists, and the cost of a second type

The idea

WRONGTYPE

Thread safety, second time

LRANGE index arithmetic

LPUSH reverses

Empty lists do not exist

Run it

Notice that

Try it yourself

What usually goes wrong

What you built

Checkpoint

Resources

Next