Unlock Redis Sorted Sets: How Skiplist & Listpack Power Real-Time Leaderboards

Introduction

I am Su San. Today I will briefly discuss the underlying implementation principles of Redis Sorted Set data type and a practical game leaderboard example. The explanation is simple and not deep, illustrated with a few diagrams.

1. What is a Sorted Set?

Sorted Sets are similar to Sets: they contain unique members. Each element consists of a member and a score . The score is a double value, and the set is ordered from low to high scores; if scores are equal, members are ordered lexicographically.

Common usage scenarios:

Leaderboards, e.g., top‑10 rankings in online games.

Rate limiters built with sliding windows.

Delay queues where the score stores expiration time.

2. Implementation Details

Sorted Sets are stored in two ways:

Before Redis 7.0, a ziplist was used; later it was replaced by listpack. When the number of elements is ≤ zset-max-listpack-entries (default 128) and the member size is < zset-max-listpack-value (default 64), a listpack is used, storing member and score compactly.

Otherwise, a combination of skiplist and dict (hash table) is used, inserting data into both structures for O(1) single‑element lookup and O(log n) range queries.

MySQL: “listpack is suitable for scenarios with few and small elements.”

The skiplist enables efficient range queries such as the ZRANGE command, whose time complexity is O(log(n)) + m (n = number of members, m = number of returned elements). The hash table provides O(1) lookup for commands like ZSCORE.

Skiplist Structure

The core source files are server.h (structure definitions) and t_zset.c (implementation).

typedef struct zset { dict *dict; zskiplist *zsl; } zset;

typedef struct zskiplist { struct zskiplistNode *header, *tail; unsigned long length; int level; } zskiplist;

Each skiplist node is defined as:

typedef struct zskiplistNode { sds ele; double score; struct zskiplistNode *backward; struct zskiplistLevel { struct zskiplistNode *forward; unsigned long span; } level[]; } zskiplistNode;

The ele stores the member, score stores its weight, backward enables reverse traversal, and level[] holds forward pointers and spans for each level.

Listpack Storage

MySQL: “The zset structure uses both dict and skiplist; listpack is not visible here.”

Listpack stores elements as a contiguous memory block of member/score pairs. It saves memory but requires O(n) linear search, suitable for small datasets.

void zaddGenericCommand(client *c, int flags) { /* ... */ if (server.zset_max_listpack_entries == 0 || server.zset_max_listpack_value < sdslen(c->argv[scoreidx+1]->ptr)) { zobj = createZsetObject(); } else { zobj = createZsetListpackObject(); } /* ... */ }

3. Practical Example: Game Leaderboard

Use a Sorted Set where score stores the player's game points and member stores the player ID. To break ties when scores are equal, incorporate a timestamp into the score:

private double calcScore(int playerScore, long playerScoreTime) { return playerScore + (BASE_TIME - playerScoreTime) * 1.0 / BASE_TIME; }

Commands to update the leaderboard:

redis> ZADD leaderboard:339 2500.994707057989 player:1
redis> ZADD leaderboard:339 500.99470705798905 player:2
redis> ZADD leaderboard:339 500.9947097814618 player:3
redis> ZADD leaderboard:339 987770.994707058 player:4

Retrieve the top 3 players: ZRANGE leaderboard:339 0 2 REV WITHSCORES Get a specific player's rank:

ZREVRANK leaderboard:339 player:4