Lesson 15.3• 10 min read

Redis sorted sets and skip lists

Redis sorted sets: a skip list with random levels (p = 1/4) plus a hash table, listpacks for small sets, command costs, and memory.

What you will learn

Keep a continuously updated ranking in a Redis sorted set.
Explain the hash table and skip list behind a sorted set, and the listpack used for small ones.
Know what each sorted-set command costs, in time and memory.

Why keep rankings in a sorted set

The primer serves rankings from the precomputed sales_rank table, with an index on category_id, through a memory cache. Computing a ranking live with GROUP BY … ORDER BY over a week of transactions on every read would repeat the same work tens of thousands of times a second.

If rankings are updated continuously, as in lesson 2, Redis sorted sets fit well. Redis lists leaderboards as a typical use: "you can use sorted sets to easily maintain ordered lists of the highest scores".

How Redis implements a sorted set

Redis's documentation describes sorted sets as "a dual-ported data structure containing both a skip list and a hash table":

The hash table maps each member to its score, so ZSCORE is $O(1)$ .
The skip list keeps members ordered by score (ties by member), so rank and range queries are fast.

Skip lists. Every node is on the bottom level, which is an ordinary sorted linked list. Each node is also on higher levels with probability $p$ per level; Redis uses $p = 1/4$ and up to 32 levels (server.h). The level is drawn at random when the node is inserted, and never depends on its score. A search starts at the top level and moves forward while the next node is smaller, then drops a level. Each Redis node also stores, per level, the span it skips, which is how ranks are computed quickly.

Small sets are different. Below zset-max-listpack-entries (128 members by default) and zset-max-listpack-value (64 bytes), Redis stores a sorted set as a compact listpack instead.

Commands and their cost (Redis docs)

Command	What it does	Complexity
`ZADD key score member`	Insert or set a score	$O(\log N)$ per member
`ZINCRBY key incr member`	Add to a score	$O(\log N)$
`ZRANGE key 0 9 REV WITHSCORES`	Top 10	$O(\log N + M)$ , $M$ returned
`ZREVRANK key member`	A member's rank from the top	$O(\log N)$
`ZSCORE key member`	A member's score	$O(1)$
`ZUNIONSTORE dest n k1 k2 …`	Sum scores across sets	$O(N) + O(M \log M)$

ZREVRANGE still works with the same complexity; newer code writes ZRANGE … REV.

Memory

A skip list node holds a pointer to the member string, the score, a backward pointer, and a forward pointer plus span for each level (zskiplistNode in server.h). With $p = 1/4$ , a node has $1/(1-p) \approx 1.33$ levels on average. Add the hash-table entry and the member string itself, and a member costs on the order of 100 bytes. Even 1,000 categories × 1,000 products is a few hundred megabytes. Measure the real figure with MEMORY USAGE rather than relying on an estimate.

A sorted set as a skip list

Members are kept in score order on level 1; each node also appears on higher levels with probability 1/4 per level, chosen at random when it is inserted. A hash map gives each member's score directly.

L4	head	—	—	—	—	—	—	—	—	—	—
L3	head	—	—	—	—	—	—	—	—	—	—
L2	head	—	—	—	230	—	—	—	—	—	420
L1	head	120	150	210	230	260	290	310	340	380	420
		Charger	Webcam	Earbuds	Tablet	Power bank	Mouse	Keyboard	Speaker	Monitor	Headphones

Finding “Keyboard” passes 3 nodes (shaded), against 7 on level 1 alone.

ZRANGE electronics 0 4 REV WITHSCORES

Headphones: 420
Monitor: 380
Speaker: 340
Keyboard: 310
Mouse: 290

ZINCRBY adds sales; the member moves to its new position.

Redis stores a sorted set this small as a compact listpack; it switches to a skip list plus hash table above 128 members by default (zset-max-listpack-entries).

Figure 3: Redis Sorted Set dual data structure: Hash Table for O(1) member-to-score lookup and Multi-Level Skip List with forward pointers for O(log N) rank ordering.

Key takeaways

A sorted set pairs a hash table, so ZSCORE is $O(1)$ , with a skip list ordered by score, so rank queries are $O(\log N)$ and range queries $O(\log N + M)$ .
A skip list node appears on each higher level with probability 1/4, drawn at random at insert, which gives fast search.
Sets under 128 members of up to 64 bytes are stored as a compact listpack instead.
A precomputed sales_rank table read through a cache is enough when rankings change hourly.

Sources

Adapted from The System Design Primer by Donne Martin, licensed under CC BY 4.0. Changes were made.