Lesson 0002 · Data structures & commands
Choosing string / hash / list / set / sorted set on cost — not habit.
In Lesson 0001 you learned the keystone: one thread, one queue, so a command's big-O is really shared latency. This lesson cashes that in. Redis gives you a handful of data structures, and picking between them is not an aesthetic choice — it decides which operations are O(1), which are O(log N), and which quietly become O(N) landmines on your hot path. You model so that the operations you run most are the cheapest ones.
Every entry below is quoted from the command's redis.io page — the same Time complexity field you met last lesson. — Redis Docs — Data types
| Type | Hot-path ops (complexity) | Model it for… |
|---|---|---|
| String | GET/SET O(1) · INCR O(1) · APPEND amortized O(1) |
Cached values, atomic counters, flags, bitmaps. |
| Hash | HGET/HSET O(1) per field · HGETALL O(N) |
A record with fields — read/write one field without touching the rest. |
| List | LPUSH/RPUSH O(1) · LPOP/RPOP O(1) · LINDEX O(N) · LRANGE O(S+N) |
Queues and stacks — cheap at the ends, costly in the middle. |
| Set | SADD O(1) · SISMEMBER O(1) · SMEMBERS O(N) · SINTER O(N·M) |
Unique membership, tags, de-duplication, relationships. |
| Sorted set | ZADD O(log N) · ZSCORE O(1) · ZRANK O(log N) · ZRANGE O(log N + M) |
Anything ordered by a score — leaderboards, priority queues, time indexes. |
Ask: what operation will I run thousands of times per second? Choose the structure that makes that operation O(1) or O(log N). Accept O(N) only on rare operations, or on collections you guarantee stay small.
You need "top 10 by score" and "what's this player's rank?", updated live. A
sorted set keeps members ordered by score for you: ZADD is
O(log N), ZRANK is O(log N), and ZREVRANGE 0 9 pulls the top ten
in O(log N + M). The naive alternative — a list you re-sort — is O(N log N) per update on
the single thread. Not close.
ZADD game:lb 4200 alice
ZADD game:lb 5100 bob
ZREVRANGE game:lb 0 9 WITHSCORES # top 10, O(log N + M)
ZREVRANK game:lb alice # her rank, O(log N)Store a user as a hash and you can HGET user:42 email or
HSET user:42 last_seen … in O(1) — touching one field. Pack the same user as
a single JSON string and every field read means GET the whole blob,
parse it in your app, and every field write is a read-modify-write of the entire value. The
hash lets Redis do field-level access; the string makes the whole record your unit of work.
To ask is user X already following Y?, a set answers with
SISMEMBER in O(1). The tempting wrong model — a list you scan — is O(N) per
check, and (per Lesson 0001) that O(N) is paid on the shared thread every single lookup.
Producer LPUSH, consumer RPOP (or blocking BRPOP) —
both O(1) because you only ever touch the ends of the list. The moment you find
yourself reaching into the middle with LINDEX (O(N)), that's a signal the list
is the wrong structure for what you're doing.
Three commands look harmless and are — until the key grows:
| Command | Complexity | Fine when… / dangerous when… |
|---|---|---|
HGETALL | O(N) over fields | Fine on a 10-field record; a stall on a 100k-field hash. |
SMEMBERS | O(N) set cardinality | Fine on a tiny tag set; blocks on a million-member set (use SSCAN). |
LRANGE k 0 -1 | O(S+N) | Fine on a short list; never dump a huge one in one call. |
A big key is a single key holding a huge collection. It hurts twice:
every O(N) command on it monopolizes the one thread (Lesson 0001), and deleting it with
DEL is itself O(N). Prefer bounded collections, iterate with the
*SCAN family, and free large keys with UNLINK.
Below configurable thresholds (e.g. hash-max-listpack-entries,
zset-max-listpack-entries), Redis stores hashes and sorted sets as a compact
listpack — a flat, cache-friendly array — instead of a hashtable/skiplist.
An O(N) scan of a 20-entry listpack is trivially fast and memory-cheap. Cross the
threshold and Redis transparently converts to the full structure. Check any key with
OBJECT ENCODING. This is a whole lesson later — for now: small collections are
cheap on every axis.
Answer from memory — the effortful recall is what builds retention. Feedback is immediate.
Live "top 10 by score" plus per-player rank is best served by:
Fetching one field of a user stored as a hash (HGET) costs:
"Is X in this 50-million-member collection?" answered cheapest by:
Which command is O(N) and can stall the server on a large key?
ZRANGE returning M elements from a set of N elements is:
You need a local Redis (redis-server or
docker run --rm -p 6379:6379 redis) and redis-cli.
redis-cli DEL game:lb
redis-cli ZADD game:lb 4200 alice 5100 bob 3300 carol 6000 dave
redis-cli ZREVRANGE game:lb 0 2 WITHSCORES # top 3
redis-cli ZREVRANK game:lb carol # carol's 0-based rank
redis-cli ZINCRBY game:lb 1000 carol # she scores — O(log N)
redis-cli ZREVRANK game:lb carol # rank moved, no re-sort neededredis-cli DEL h
redis-cli HSET h a 1 b 2 c 3
redis-cli OBJECT ENCODING h # -> "listpack" (compact)
redis-cli EVAL "for i=1,200 do redis.call('hset','h','f'..i,i) end" 0
redis-cli OBJECT ENCODING h # -> "hashtable" (converted)Before running step 2's last line: which encoding will a 203-field hash use, and why
does it matter for the cost of HGETALL? Commit, then check.
When you're done, redis-cli DEL game:lb h to clean up — and bring any
surprising OBJECT ENCODING result to your teacher.
Redis Docs — Data types. The canonical overview of every native type with links to each one's deep dive. Skim it with one question in mind: for each type, which operations are O(1) and which are O(N)? That table is the whole skill.