Skip lists and sorted sets
How Redis sorted sets and other ordered in-memory structures work: skip lists versus balanced trees, operations and complexity, ranking with ZRANK, range queries by score and lexicographic order, memory costs, and using sorted sets for leaderboards, rate limiters, time-ordered feeds and scheduling.
Reading is half of it. See this used in a real interview: walk through Design a Real-Time Leaderboard →
Leaderboards, sliding-window rate limiters, delayed job queues and time-ordered feeds all need the same thing: a collection kept sorted by a score, with fast inserts, updates, rank lookups and range scans. Redis provides it as the sorted set, built on a skip list plus a hash map. Knowing how it works explains its performance and limits when you put one in a design.
The skip list
A skip list is a sorted linked list with express lanes:
- The bottom level links every element in order.
- Each element is also promoted to higher levels with probability (for example) 1/2 or 1/4 per level, chosen randomly at insert.
- Higher levels link fewer elements, so a search starts at the top, moves right while the next element is smaller than the target, then drops a level.
On average, search, insert and delete take O(log N), like a balanced tree, but the code is much simpler and concurrent variants are easier to build. LevelDB and RocksDB memtables also use skip lists. See storage engines.
How Redis sorted sets work
A sorted set stores members with a numeric score:
- A hash map from member to score gives O(1) score lookups and membership tests.
- A skip list ordered by (score, member) supports ordered operations.
- Each skip list node stores span counts (how many elements each link skips), which makes computing a member's rank O(log N): sum the spans along the search path.
- Small sets use a compact listpack encoding instead, switching to the skip list as they grow.
Operations and costs
| Operation | Command | Cost |
|---|---|---|
| Add or update a score | ZADD, ZINCRBY | O(log N) |
| Score of a member | ZSCORE | O(1) |
| Rank of a member | ZRANK, ZREVRANK | O(log N) |
| Top or bottom K | ZRANGE ... REV LIMIT | O(log N + K) |
| Members in a score range | ZRANGEBYSCORE | O(log N + K) |
| Count in a score range | ZCOUNT | O(log N) |
| Remove a range | ZREMRANGEBYSCORE | O(log N + removed) |
| Lexicographic ranges (equal scores) | ZRANGEBYLEX | O(log N + K) |
Memory is the main cost: each member carries the string, the score, hash table entries and skip list pointers, often around 100 bytes or more per member beyond the member itself. A sorted set with 100 million members needs many gigabytes; estimate before choosing. See back-of-envelope estimation.
Uses in designs
- Leaderboards: score = points; top-K and "my rank" are single commands. See Design a Leaderboard.
- Sliding-window rate limiting: score = request timestamp; remove old entries, count the rest. See rate limiting algorithms.
- Delayed jobs: score = due time; poll the range up to now. See delayed jobs and distributed cron.
- Time-ordered feeds: score = timestamp or ranking score; page with score ranges. See fan-out on write vs read.
- Autocomplete on small sets: equal scores with lexicographic ranges for prefix lookup. See tries and autocomplete.
- Priority queues:
ZPOPMINandZPOPMAX, including blocking variants.
Scaling beyond one set
A single sorted set lives on one Redis shard, so very large or very hot sets need care:
- Shard by entity: one leaderboard per game, region or season, rather than one global set.
- Score-range sharding: split a huge leaderboard into score buckets on different shards; a global rank becomes the count of members in higher buckets (kept as counters) plus the rank within the bucket.
- Approximate ranks for the long tail ("top 15 %") from a histogram of scores, exact ranks only for the top N.
- Ties: equal scores are ordered by member name; encode a tie-breaker (such as earlier achievement time) into the score if fairness matters.
See hot keys and skew.
Alternatives
- Database indexes (B-trees) give ordered queries with durability; ranking requires counting rows, which is slower for deep ranks. See database indexing.
- Order-statistic trees in application memory, for custom engines.
- Search engines for ranking with many criteria rather than one score.
In the interview
"Scores live in a Redis sorted set per leaderboard: ZINCRBY on each score event, ZREVRANGE for the top 100 and ZREVRANK for a player's rank, all logarithmic. For a global board with hundreds of millions of players, we shard by score range and compute exact ranks only for the top tier, approximate percentiles below, with the database as the durable source of scores."
Checklist
- Skip list plus hash map: O(log N) updates, ranks and range starts.
- Member-to-score lookups in O(1).
- Memory per member estimated before scale.
- Per-entity sets; score-range sharding for huge boards.
- Tie-breaking encoded deliberately.
- Durable source of truth elsewhere when data matters.