Redis
An in-memory data-structure server: strings, sets, hashes, sorted sets, streams.
Redis keeps every value in memory as one of several purpose-built data structures and answers commands on a single thread. Persistence is optional and log-structured: an append-only file of write commands plus point-in-time RDB snapshots. Sorted sets are skip lists — the same probabilistic structure LSM memtables use.
Purpose-built structures
Strings, lists, sets, hashes, sorted sets, streams: each command is O(1) or O(log N) against a structure designed for it, instead of rows in a general engine.
AOF + RDB persistence
The append-only file records every write command; RDB snapshots dump a point-in-time binary image. Redis rewrites the AOF compactly in the background.
Single-threaded core
Commands execute on one thread — no locks, no context switches per key. I/O and slow operations are the scaling limits, not contention.
Sorted sets are skip lists
ZSET encodes members in a skip list ordered by score plus a hash map for O(1) score lookup — the same probabilistic structure LSM memtables use.
Data structures, not tables
A Redis key maps to one typed structure. A leaderboard is a sorted set (a skip list plus a hash); a queue is a list; a rate limiter is a counter on a string. Choosing the structure is the schema design — the server exposes operations on the structure itself, not a query language.
Because everything lives in memory and commands run single-threaded, latency is predictable to the microsecond. The engine is deliberately not a database of record: durability comes from the persistence settings you choose, and datasets must fit (or be sharded) in RAM.
ZADD leaderboard 950 "ann" 870 "bob"
ZINCRBY leaderboard 10 "ann"
ZRANGE leaderboard 0 2 REV WITHSCORES
Durability is a dial, not a default
AOF every-command fsync is the safest and slowest setting; everysec trades one second of loss for throughput; RDB alone can lose everything since the last snapshot. Replicas and Redis Sentinel or Cluster turn that dial into a failover story.
The walkthrough below shows the skip list that powers sorted sets: level-by-level search, a coin-flip node height, and pointer swaps instead of tree rotations.
Diagrams
static storyboard — WebGPU animates when available
A live WebGPU particle field tinted to this exhibit. Plays only with WebGPU and no reduced-motion preference; a static storyboard renders for everyone else.
[caption] No query planner, no pages: the structure IS the index.
A command executes on the single-threaded event loop, mutates the in-memory structure, and appends to the AOF. RDB snapshots fork the process for point-in-time images.
| search path | head → L2:12 → L1:34 → L0: gap (34, 45) |
| nodes visited | 5 of 7 |
| new node 42 | height 2 (levels 0 + 1) |
| pointer swaps | 4 |
| flush | memtable → sorted SST run |
All steps
- Search 42 — start at the top — The search enters at the highest level. Greedy rule: move right while the next key is smaller than 42. From the head, node 12 is the first (and only) stop on L2.
- L2 exhausted — drop to L1 — 42 > 12 and nothing follows 12 on L2, so the search drops to L1 at node 12. Each drop multiplies the candidates considered — this is where the logarithmic search comes from.
- L1: hop 12 → 34, stop before 56 — 34 < 42 so advance; 56 > 42 so stop. Node 34 is the closest key below 42 on L1 — the insertion point is somewhere right of it.
- L0: 34 → 45 finds the gap — On the base level 45 > 42 stops the scan: the gap is (34, 45). Base-level scans are short because higher levels did the coarse work.
- insert(42) — coin flips say height 2 — The new node gets a height from repeated coin flips: 42 lands on levels 0 and 1. Expected O(log n) search comes precisely from these random heights — no rebalancing, ever.
- Link at both levels — L0: 34 → 42 → 45. L1: 34 → 42 → 56. Two pointer swaps per level. The memtable stays sorted, so a later flush emits one sorted run directly.
- Result — Search visited 5 nodes across 3 levels instead of scanning 7. The zset stays a live sorted structure — persistence is the AOF/RDB story at the server level, not a flush.
A Redis sorted set is a skip list: members held at random heights ordered by score, so ZRANGE and ZRANK hop right on high levels and drop down only when they must. Teaching model: 3 levels, six members, fixed heights; the real engine draws heights from coin flips.
Same structure LSM memtables use — Redis uses it as the live sorted-set index, not a staging buffer.
[caption] Same structure LSM memtables use — Redis uses it as the live sorted-set index, not a staging buffer.
Search and insert in the skip list behind ZSET: greedy hops on high levels, a coin-flip node height, and pointer swaps instead of rotations.