Redis data structures

Most applications use Redis as a place to put a string under a key and get it back. That is a fraction of it. Redis is a server of data structures — hashes, lists, sets, sorted sets, streams, probabilistic counters — each with operations that run atomically inside the server, and each of which turns a problem that would need a table, a query and a transaction into a single command.

Every transcript below is from Redis 7.4.

#Why commands, not get-and-set

Start with the property that matters more than any structure. Eight clients each increment a page-view counter 2,500 times — 20,000 increments. Half the code reads the value, adds one, and writes it back; the other half uses INCR:

8 clients × 2,500 increments = 20,000 expected
GET then SET: 5547
INCR:         20000

GET-then-SET lost 72% of the increments. Two clients read 41, both write 42, and one increment disappears — the same lost update as count++ on a shared field in Java, now across a network. INCR is one command, and Redis executes commands one at a time, so it cannot be interleaved.

That is the model to hold: a Redis command is atomic; a sequence of commands from the client is not. When an operation needs several steps — check, then change — it belongs in a single command if one exists, or in a Lua script, which Redis also runs atomically. MULTI/EXEC transactions queue commands to run together, but they cannot use one command's result to decide the next, which is usually what the logic needs.

#Strings and hashes

Strings hold any bytes up to 512 MB: serialised objects, counters (INCR, INCRBY), flags, and short-lived tokens with an expiry (SET key value EX 600 NX).

Hashes hold field–value pairs under one key — a user's profile, a cart — and let you read or update one field without rewriting the whole value. They also show a detail of how Redis stores small things:

hash of 10 fields:    encoding listpack   memory     168 bytes (16 bytes per field)
hash of 1,000 fields: encoding hashtable  memory  56,304 bytes (56 bytes per field)
hash-max-listpack-entries = 512

A small hash is stored as a listpack — a compact, contiguous block — at 16 bytes per field here. Past 512 entries (the configured threshold) it converts to a real hash table at 56 bytes per field, three and a half times more. Lists, sets and sorted sets have the same two-tier encoding. Millions of small objects stored as small hashes use far less memory than the same data as one big hash or as millions of string keys.

#Lists: queues

A list is a sequence with fast pushes and pops at both ends. LPUSH plus BRPOP is a simple work queue: producers push, workers block until an item arrives. It is simple, and it has a gap: once a worker pops an item, the item is gone from Redis. A worker that crashes mid-job loses it. LMOVE into a per-worker "processing" list closes the gap by hand; streams, below, close it properly.

#Sets and sorted sets

A set holds unique members with membership tests, intersections and unions — who follows whom, which features a user has, deduplication of recent event ids.

A sorted set holds unique members, each with a score, kept in score order. It is the structure behind most things ranked:

> ZADD leaderboard:weekly 1200 asha 950 ravi 1430 meera 800 kabir
(integer) 4
> ZINCRBY leaderboard:weekly 300 ravi
"1250"
> ZREVRANGE leaderboard:weekly 0 2 WITHSCORES
1) "meera"
2) "1430"
3) "ravi"
4) "1250"
5) "asha"
6) "1200"
> ZREVRANK leaderboard:weekly kabir
(integer) 3

ZINCRBY moved Ravi from third to second in one atomic step. ZREVRANGE returns the top N and ZREVRANK a member's position, each in logarithmic time — a leaderboard of millions answers "top 10" and "where am I" without a sort. The same structure, with timestamps as scores, is a time-ordered index: delayed jobs scheduled by time, recent activity, and the rate limiter below.

#A rate limiter in one script

A sliding-window limiter: allow 10 requests per rolling second per user. Each request is added to a sorted set with its timestamp as the score; entries older than the window are removed; if 10 remain, the request is refused. Those three steps must happen together, so they run as a Lua script:

local now = tonumber(ARGV[1]) local window = tonumber(ARGV[2]) local limit = tonumber(ARGV[3])
redis.call('ZREMRANGEBYSCORE', KEYS[1], 0, now - window)
local count = redis.call('ZCARD', KEYS[1])
if count >= limit then return 0 end
redis.call('ZADD', KEYS[1], now, ARGV[4])
redis.call('PEXPIRE', KEYS[1], window)
return 1

Fifteen requests 10 ms apart, with a one-second pause after the twelfth:

15 requests, limit 10 per rolling second, a 1 s pause after the 12th:
✓✓✓✓✓✓✓✓✓✓✗✗✓✓✓

Ten allowed, the eleventh and twelfth refused, and after the pause the window has emptied and requests are allowed again. Run outside a script — ZCARD in one round trip, ZADD in another — two concurrent requests could both see nine and both be allowed. A sorted set stores one member per request, which is precise and uses memory in proportion to the limit; a fixed-window counter with INCR and EXPIRE uses one integer and allows bursts at window edges. The REST course's rate limiting lesson compares the algorithms.

#Streams: a log with consumer groups

A stream is an append-only log of entries, each with an id and fields — a small, in-memory relative of a Kafka topic. Consumer groups let several workers share it, and Redis tracks which entries each worker has been given and not yet acknowledged.

> XGROUP CREATE orders:events invoicing $ MKSTREAM
OK
> XADD orders:events * orderId 1041 type PLACED
"1789325417034-0"
> XREADGROUP GROUP invoicing worker-1 COUNT 2 STREAMS orders:events >
1) 1) "orders:events"
   2) 1) 1) "1789325417034-0"
         2) 1) "orderId"
            2) "1041"
            3) "type"
            4) "PLACED"
      2) 1) "1789325417057-0"
         2) 1) "orderId"
            2) "1042"
            3) "type"
            4) "PLACED"

Worker 1 received both orders. It acknowledges the first, then crashes before finishing the second:

> XACK orders:events invoicing 1789325417034-0
(integer) 1
> XPENDING orders:events invoicing
1) (integer) 1
2) "1789325417057-0"
3) "1789325417057-0"
4) 1) 1) "worker-1"
      2) "1"

The pending entries list shows exactly one unacknowledged entry — order 1042 — still assigned to worker-1. Unlike a popped list item, it is not lost. Another worker claims entries that have been pending longer than a threshold:

> XAUTOCLAIM orders:events invoicing worker-2 1000 0-0 COUNT 10
1) "0-0"
2) 1) 1) "1789325417057-0"
      2) 1) "orderId"
         2) "1042"
         3) "type"
         4) "PLACED"
3) (empty array)

Worker 2 now owns order 1042, one second after worker 1 went silent. That is at-least-once delivery, with the same obligation as Kafka: processing must be idempotent, because a worker that crashed after doing the work but before XACK will have its entry processed again.

Streams fit work queues and event fan-out within one system. They are bounded by memory, so trim them (XADD … MAXLEN ~ 100000), and they do not replace Kafka for long retention or very high volume.

#HyperLogLog: counting without remembering

How many distinct visitors did a page have today? A set of visitor ids answers exactly — and remembers every id. A HyperLogLog answers approximately, in a fixed, tiny amount of memory. The same million distinct visitor ids added to both:

distinct visitors added: 1,000,000
SCARD visitors:set   = 1,000,000   MEMORY USAGE = 48,388,720 bytes
PFCOUNT visitors:hll = 1,003,993   MEMORY USAGE = 14,392 bytes

The set: exact, 48 MB. The HyperLogLog: 1,003,993 — 0.4% high — in 14 KB, about 3,400 times less memory, and it would still be 14 KB at a billion visitors. Its standard error is 0.81%, which is fine for dashboards and analytics and wrong for anything that must be exact, like billing.

#Memory is the limit

Everything Redis holds is in memory, so every structure choice is a memory choice:

• Measure with MEMORY USAGE key and INFO memory, as above, rather than estimating.
• Set maxmemory and an eviction policy that matches the use: allkeys-lfu or allkeys-lru for a pure cache; noeviction for data that must not silently disappear, such as queues and locks — where a full Redis should fail writes loudly.
• Do not mix a cache that may evict with data that must not in one instance with one policy; an eviction under memory pressure will not distinguish them.