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)O(1)what its symbols mean.
  • 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 ppwhat its symbols mean per level; Redis uses p=1/4p = 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: a special encoding that uses much less memory, which Redis converts to the ordinary one once the set outgrows either limit.


Commands and their cost (Redis documentation)

Command What it does Complexity
ZADD key score member Insert or set a score O(log⁡N)O(\log N)what its symbols mean per member
ZINCRBY key incr member Add to a score O(log⁡N)O(\log N)
ZRANGE key 0 9 REV WITHSCORES Top 10 O(log⁡N+M)O(\log N + M)what its symbols mean, MMwhat its symbols mean returned
ZREVRANK key member A member's rank from the top O(log⁡N)O(\log N)
ZSCORE key member A member's score O(1)O(1)what its symbols mean
ZUNIONSTORE dest n k1 k2 … Sum scores across sets O(N)+O(Mlog⁡M)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/4p = 1/4what its symbols mean, a node has 1/(1−p)≈1.331/(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 table gives each member's score directly.

L4head——————————
L3head——————————
L2head———230—————420
L1head120150210230260290310340380420
ChargerWebcamEarbudsTabletPower bankMouseKeyboardSpeakerMonitorHeadphones
Finding “Keyboard” passes 3 nodes (shaded), against 7 on level 1 alone.
ZRANGE electronics 0 4 REV WITHSCORES
  1. Headphones: 420
  2. Monitor: 380
  3. Speaker: 340
  4. Keyboard: 310
  5. 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).
Shoppers1× instanceWeb server (reverseproxy)10× instancesRead API41× instancesRedis (a sorted setper category)5× instancesMessage queue(purchase events)2× instancesStream processor2× instancesShoppers1× instanceWeb server (reverseproxy)10× instancesRead API41× instancesRedis (a sorted setper category)5× instancesMessage queue(purchase events)2× instancesStream processor2× instancesShoppers1× instanceWeb server (reverseproxy)10× instancesRead API41× instancesRedis (a sorted setper category)5× instancesMessage queue(purchase events)2× instancesStream processor2× instances
Figure 3

Rankings kept continuously in Redis sorted sets: the stream processor adds each sale to its product’s score, and the Read API reads the top of each set.

Follow a purchase and a read. The stream processor takes each purchase event from the message queue and adds its quantity to the product’s score in its category’s sorted set. A shopper’s request for a category goes through the web server to the Read API, which reads the top of that set. The Read API is counted at the lab’s 1,000 requests a second a server for the primer’s 40,000 reads a second, plus one spare; the web server at 5,000 a second, plus one spare; and Redis at 12,000 a second a node, plus one spare. The queue and the stream processor are drawn with two each, as the primer gives no count.

  • Shoppers: 1 × Users
  • Web server (reverse proxy): 10 × Load balancer
  • Read API: 41 × App server
  • Redis (a sorted set per category): 5 × Cache
  • Message queue (purchase events): 2 × Queue
  • Stream processor: 2 × App server
  • Shoppers sends requests to Web server (reverse proxy)
  • Web server (reverse proxy) sends requests to Read API
  • Read API sends requests to Redis (a sorted set per category)
  • Message queue (purchase events) sends requests to Stream processor
  • Stream processor sends requests to Redis (a sorted set per category)

Key takeaways

  • A sorted set pairs a hash table, so ZSCORE is O(1)O(1)what its symbols mean, with a skip list ordered by score, so rank queries are O(log⁡N)O(\log N)what its symbols mean and range queries O(log⁡N+M)O(\log N + M)what its symbols mean.
  • 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.
Sources6