Four more types

Where we are going

$ redis-cli hset user name Subash city Kathmandu
(integer) 2
$ redis-cli hgetall user
1) "name"
2) "Subash"
3) "city"
4) "Kathmandu"

$ redis-cli zadd leaderboard 100 alice 250 bob 175 carol
(integer) 3
$ redis-cli zrange leaderboard 0 -1
1) "alice"
2) "carol"
3) "bob"

flowchart LR
    A[Part 8<br/>pub/sub and streams] --> B[Stage 28<br/>hashes and sets]
    B --> C[Stage 29<br/>sorted sets]
    C --> D[Stage 30<br/>SCAN]
    D --> E([Part 10<br/>persistence])

Stage 28, hashes and sets

Goal. HSET, HGET, HGETALL, HKEYS, HVALS, HLEN, HEXISTS, HDEL, and the set family: SADD, SREM, SMEMBERS, SISMEMBER, SCARD.

The idea

This is the easy stage, and the reason is the interesting part.

Lists cost a redesign back in Part 6. Entry became Object, WRONGTYPE had to be invented, and every existing command learned to check its type. Hashes and sets cost none of that. They slot into machinery that already exists:

Map<String,String>  →  "hash"
Set<String>         →  "set"

instanceof already distinguishes them. compute() already makes them atomic. live() already expires them. The version counter from Part 7 already invalidates WATCH. Adding a type is now a case in type() and an accessor on Entry.

That is what a good abstraction looks like from the inside, and it is worth naming. The second type was expensive. The third and fourth were nearly free.

Thirteen commands, and the shape repeats. Each family has a writer that returns a delta, readers that return a copy, and a remover that deletes the key when the collection empties.

return switch (entry.value()) {
    case RedisStream ignored -> "stream";
    case Map<?, ?> ignored -> "hash";
    case Set<?> ignored -> "set";
    case List<?> ignored -> "list";
    default -> "string";
};

Counting semantics

Both families return how many things changed, not how many you named:

HSET h a 1 b 2   →  :2      two new fields
HSET h a 9       →  :0      overwrote, added nothing
SADD s a b       →  :2
SADD s a         →  :0      already a member
SADD s a a a     →  :1      duplicates within one command count once

The reply is a delta, which is what makes SADD usable as “did I win the race”. A :1 means you were the one who inserted it.

HDEL and SREM mirror it. Only members that were actually there count.

The code

The pattern is identical for both, so here is the hash version:

// returns how many fields were new rather than overwritten
public long hset(String key, List<String> fieldValuePairs) {
    long now = clock.getAsLong();
    long[] added = new long[1];

    data.compute(key, (k, existing) -> {
        boolean usable = existing != null && !existing.isExpired(now);
        Map<String, String> hash = usable ? existing.asHash() : new LinkedHashMap<>();

        for (int i = 0; i < fieldValuePairs.size(); i += 2) {
            if (hash.put(fieldValuePairs.get(i), fieldValuePairs.get(i + 1)) == null) {
                added[0]++;
            }
        }

        long expiry = usable ? existing.expiresAtNanos() : NEVER;
        return new Entry(hash, expiry);
    });

    touch(key);
    return added[0];
}

// a copy taken inside compute, so callers never hold the live map
private Map<String, String> readHash(String key) {
    long now = clock.getAsLong();
    Map<String, String>[] copy = new Map[1];

    data.computeIfPresent(key, (k, existing) -> {
        if (existing.isExpired(now)) {
            return null;
        }
        copy[0] = new LinkedHashMap<>(existing.asHash());
        return existing;
    });
    return copy[0];
}

Reads copy inside the compute lambda before returning. Handing back the live collection would leak a mutable object out of the store, where another thread could iterate it while a writer mutates it. The same trap LRANGE avoided in Part 6.

One arity check, thirteen commands

HKEYS, HVALS, HLEN, SMEMBERS, and SCARD all take exactly one key and all report the same error. Repeating that check thirteen times is noise, so they share one:

// the single-key commands all look the same, so they share the arity check
private static String argument(String[] command, String name) {
    if (command.length != 2) {
        throw new ArityException(name);
    }
    return command[1];
}

ArityException is a tiny unchecked exception carrying the command name, caught once beside WrongTypeException in execute. Same pattern, same reason: a failure that has to travel out of a helper without poisoning its return type.

} catch (ArityException e) {
    return RespWriter.error("ERR wrong number of arguments for '" + e.getMessage() + "' command");
}

I got this wrong the first time by putting the catch on the wrong try, so HGETALL a b threw out of the dispatcher instead of replying. One test caught it.

Empty collections do not exist

Same rule as lists. HDEL on the last field, or SREM on the last member, removes the key:

$ redis-cli hset h a 1
$ redis-cli hdel h a
$ redis-cli exists h
(integer) 0

Returning null from the compute lambda handles it.

HGETALL is flat

*4  "name"  "Subash"  "city"  "Kathmandu"

Not an array of pairs, and not a RESP3 map, because RESP2 has no map type. Field and value alternate. Same shape as CONFIG GET, and clients unpack it in twos.

Insertion order is preserved here because the store uses LinkedHashMap and LinkedHashSet. Real Redis makes no such promise for either type, so relying on it in a client would be a bug. I use ordered collections purely so the tests can assert on exact bytes.

Run it

$ redis-cli hset user name Subash city Kathmandu   # (integer) 2
$ redis-cli hget user name                          # "Subash"
$ redis-cli hexists user city                       # (integer) 1
$ redis-cli hkeys user
1) "name"
2) "city"
$ redis-cli hvals user
1) "Subash"
2) "Kathmandu"
$ redis-cli hdel user city                          # (integer) 1
$ redis-cli hlen user                               # (integer) 1

$ redis-cli sadd tags java redis                    # (integer) 2
$ redis-cli sadd tags java                          # (integer) 0
$ redis-cli smembers tags
1) "java"
2) "redis"
$ redis-cli sismember tags java                     # (integer) 1
$ redis-cli srem tags java                          # (integer) 1
$ redis-cli scard tags                              # (integer) 1
$ redis-cli type user                               # hash
$ redis-cli type tags                               # set

Notice that

The second sadd tags java returned 0. Nothing changed, and the count says so. That is the difference between a delta and an acknowledgement.

Try it yourself

Run SADD s a a a and predict the reply before you press enter.
Mutate what HGETALL or SMEMBERS returned and then read the key again. Unchanged, because the store handed you a copy.
HSET on a key holding a string. WRONGTYPE, without you writing a single line for it.

Stage 29, sorted sets

Goal. Members ordered by score. ZADD, ZREM, ZSCORE, ZRANK, ZCARD, ZRANGE.

The idea

The last core Redis type, and the only one where ordering is the feature.

A sorted set has to answer two different questions quickly. What is this member’s score, which is a lookup. And who is in score order, which is an ordering. One structure cannot do both well. A map gives lookup and no order. A sorted list gives order and O(n) lookup.

So the type keeps both, pointing at the same members:

flowchart LR
    subgraph RedisSortedSet
        M["HashMap&lt;String, Double&gt;<br/>member → score"]
        T["TreeSet&lt;String&gt;<br/>ordered by (score, member)"]
    end
    Z1[ZSCORE] --> M
    Z2[ZRANGE] --> T
    Z3[ZRANK] --> T

Real Redis does the same thing with a hash table plus a skip list. A TreeSet is the java.util equivalent for our purposes. The same O(log n), less code, and the skip list only wins on range operations we do not implement.

The comparator trap

The TreeSet’s comparator reads scores out of the HashMap:

private final NavigableSet<String> ordered = new TreeSet<>((a, b) -> {
    int byScore = Double.compare(scores.get(a), scores.get(b));
    return byScore != 0 ? byScore : a.compareTo(b);
});

That coupling makes ordering easy and mutation dangerous. A TreeSet finds an element by comparing, so if a member’s score changes while it sits in the set, the set can no longer locate it. remove walks to the wrong place, silently fails, and leaves a ghost entry that never goes away.

The rule that avoids it:

adding     write the score first, then insert       (the comparator needs the score)
rescoring  remove first, then change the score, then re-insert

// true when the member is new rather than rescored
public boolean add(String member, double score) {
    boolean isNew = !scores.containsKey(member);
    if (!isNew) {
        ordered.remove(member);
    }
    scores.put(member, score);
    ordered.add(member);
    return isNew;
}

Get that order wrong and the bug is invisible until a member appears twice in ZRANGE.

Ties break lexicographically

ZADD z 1 banana 1 apple 1 cherry
ZRANGE z 0 -1   →  apple banana cherry

Byte order of the member, not insertion order. That is what makes a sorted set totally ordered, which in turn is what makes ZRANK well defined. With ties broken arbitrarily, a member’s rank could change without anything being written.

Score formatting

Scores are doubles, and Redis prints them as short as possible:

1.0   →  "1"
2.5   →  "2.5"

A client that stores 1 and reads back 1.0 sees a different string, and string comparison is how most clients check.

// redis prints whole scores without a decimal point, so 1.0 comes back as "1"
private static String formatScore(double score) {
    if (score == Math.rint(score) && !Double.isInfinite(score)) {
        return Long.toString((long) score);
    }
    return Double.toString(score);
}

Scores come back as bulk strings, not RESP integers, because a score is a float and RESP2’s : type is integers only.

ZRANK’s nil

ZRANK z alice    →  :0      alice is first
ZRANK z nobody   →  $-1     not a member

Rank 0 is a real answer, so absent cannot also be 0. It has to be a different type, a null bulk string. The same shape of decision as TTL’s -2 in Part 5, solved differently because the useful range here includes zero.

Run it

$ redis-cli zadd leaderboard 100 alice 250 bob 175 carol
(integer) 3
$ redis-cli zrange leaderboard 0 -1
1) "alice"
2) "carol"
3) "bob"
$ redis-cli zrange leaderboard 0 -1 withscores
1) "alice"
2) "100"
3) "carol"
4) "175"
5) "bob"
6) "250"
$ redis-cli zrank leaderboard bob        # (integer) 2
$ redis-cli zscore leaderboard alice     # "100"

$ redis-cli zadd leaderboard 999 alice
(integer) 0
$ redis-cli zrange leaderboard 0 -1
1) "carol"
2) "bob"
3) "alice"

Notice that

The rescore returned 0, because alice was not new. And she moved from first to last. That exercises the remove-then-reinsert path, which is where the comparator trap bites.

Also zscore printed "100", not "100.0".

Try it yourself

Break the rescore order: change the score first, then try to remove and re-add. Watch a member appear twice in ZRANGE.
Add three members with the same score and confirm they come back alphabetically.
Run ZRANK z nobody and ZRANK z <first member>. One is (nil), the other is (integer) 0. Work out why they cannot share a representation.

Stage 30, SCAN

Goal. Walk the keyspace in pages instead of all at once.

The idea

KEYS * builds the entire keyspace into one reply. On a server with ten million keys that is a multi-second pause, and real Redis is single-threaded, so during it nobody is served. It is the classic way to take down a production instance with a command that looks like a read.

Your server is threaded, so KEYS blocks only one connection. The lesson still holds. It is the command you must not teach people to use.

SCAN replaces it with paging. Each call does a bounded amount of work and hands back a cursor.

The cursor is the whole design

A naive implementation would keep server-side iterator state per client. That fails immediately, because clients disconnect mid-scan and a server tracking abandoned iterators leaks.

So the cursor is stateless, an opaque token the client hands back:

sequenceDiagram
    participant C as Client
    participant S as Server
    C->>S: SCAN 0
    S-->>C: cursor 12, ten keys
    C->>S: SCAN 12
    S-->>C: cursor 27, ten keys
    C->>S: SCAN 27
    S-->>C: cursor 0, three keys. done

The server remembers nothing between calls. A client that vanishes costs nothing. Zero starts a scan and zero ends one.

What SCAN guarantees, and what it does not

A key present for the whole scan is returned at least once. That is the guarantee.

Not guaranteed: keys added or removed mid-scan may or may not appear, a key may be returned more than once so clients must deduplicate, and COUNT is a hint rather than a promise.

That is the price of a stateless cursor over a mutating keyspace, and it is the honest trade. Weak guarantees in exchange for never blocking and never leaking.

Our page can come back short for a specific reason worth knowing. An expired key still consumes a step but is not returned, so a COUNT 10 page might hold seven keys and a non-zero cursor. A client that stops scanning because a page was short has a bug. Only cursor 0 ends a scan.

The deviation from real Redis

Mine sorts the keyspace and uses an index as the cursor. Real Redis walks hash buckets in reverse binary order, which has a property sorting does not. It stays correct while the hash table grows or shrinks, without rescanning or missing keys.

Sorting per call is O(n log n), so this implementation is not actually cheaper than KEYS on a large keyspace. It just returns less at a time. The ponytail: comment in the store names that ceiling. The interface is right, which is what the stage is about. The bucket walk is an optimisation with a real algorithm behind it.

Being explicit about a simplification beats quietly shipping one.

The cursor is a bulk string

*2
$2
12          ← the cursor, as a string
*10
...         ← the keys

Not a RESP integer. Real cursors are 64-bit unsigned values that do not fit in a signed integer reply, so Redis sends them as strings. Copying that keeps clients working.

Run it

$ for i in $(seq 1 25); do redis-cli set key$i v > /dev/null; done

$ redis-cli scan 0
1) "10"
2)  1) "key1"
    2) "key10"
    ...

$ redis-cli scan 0 match 'key1*' count 100
$ redis-cli scan 0 count 5

Follow the cursor by hand until it comes back 0 and check you saw all 25.

Notice that

The first element of the reply is the cursor, and it is quoted, because it is a bulk string. The second is the array of keys. Every SCAN reply has that shape, including the last one, where the cursor is "0".

Try it yourself

Write the loop: call SCAN, collect the keys, feed the cursor back, stop at 0. Count what you saw. It should be 25 regardless of the COUNT you use.
Use COUNT 1. It still terminates, just with more round trips.
Set a key with PX 100, wait, then scan. It never appears, and the page containing its slot may come back short.

What usually goes wrong

The scan never terminates. You are not feeding the returned cursor back, or you restart from 0 each time.

The scan stops early. You treated a short page as the end. Only cursor 0 ends it.

Go deeper: reverse binary iteration

Redis increments the cursor by adding one to the most significant bit and propagating carries downward, which visits buckets in an order that stays valid across table resizes. A key that was in bucket 3 of a 4-bucket table will be in bucket 3 or 7 of an 8-bucket table, and the traversal order guarantees both are visited after the cursor passes 3.

Redis SCAN, the guarantees section
Redis sorted sets
Skip lists, Pugh 1990, what real Redis uses instead of a TreeMap

What you built

Every core Redis data type: strings, lists, hashes, sets, sorted sets, and streams. Plus a safe way to walk the keyspace.

Checkpoint

Why did adding lists cost a redesign while hashes and sets cost almost nothing?
Why does SADD return a count rather than OK?
What exactly goes wrong if a member’s score changes while it sits in the TreeSet?
Why can ZRANK not report an absent member as -1 the way TTL does?
Why may SCAN return the same key twice, and what must a client do about it?

Resources

The unglamorous commands a real client reaches for, and the flag that lets you run two servers at once, which the last two posts both need.

Part 10: The Commands That Make It Usable →

You will build

You will understand

Where we are going

Stage 28, hashes and sets

The idea

Counting semantics

The code

One arity check, thirteen commands

Empty collections do not exist

HGETALL is flat

Run it

Notice that

Try it yourself

Stage 29, sorted sets

The idea

The comparator trap

Ties break lexicographically

Score formatting

ZRANK’s nil

Run it

Notice that

Try it yourself

Stage 30, SCAN

The idea

The cursor is the whole design

What SCAN guarantees, and what it does not

The deviation from real Redis

The cursor is a bulk string

Run it

Notice that

Try it yourself

What usually goes wrong

What you built

Checkpoint

Resources

Next