What you will learn
- How sorted sets order members by score, and their complexity.
- A leaderboard with ranks and score ranges.
- A sliding-window rate limiter using timestamps as scores.
Sorted sets
A sorted set (ZSET) maps unique members to floating-point scores and keeps them ordered by score. Internally it combines a hash table (member → score) with a skip list (ordered by score), so:
- Add, update, remove, rank lookup: O(log n).
- Range by rank or score: O(log n + m) for m results.
Anything “ordered by a number” fits: leaderboards, priority queues, time-ordered indexes, delayed jobs (score = run-at timestamp).
The code
"""Sorted sets: a leaderboard and a sliding-window rate limiter."""
import os
import time
import redis
r = redis.Redis(port=int(os.getenv("REDIS_PORT", 6379)), decode_responses=True)
r.flushdb()
# Leaderboard: score = points, member = player
r.zadd("lb:weekly", {"asha": 120, "ravi": 95, "meera": 140, "john": 95})
r.zincrby("lb:weekly", 30, "ravi") # ravi scores 30 more
print("top 3:", r.zrevrange("lb:weekly", 0, 2, withscores=True))
print("ravi rank (0 = first):", r.zrevrank("lb:weekly", "ravi"))
print("players with 100-130 points:", r.zrangebyscore("lb:weekly", 100, 130))
def allow(user, limit=5, window_s=1.0):
"""Sliding-window log: keep request timestamps in a sorted set."""
key = f"rl:{user}"
now = time.time()
pipe = r.pipeline() # MULTI/EXEC: these run atomically, in one round trip
pipe.zremrangebyscore(key, 0, now - window_s) # forget requests outside the window
pipe.zadd(key, {f"{now}": now})
pipe.zcard(key)
pipe.expire(key, int(window_s) + 1)
_, _, count, _ = pipe.execute()
return count <= limit
results = [allow("u1") for _ in range(7)]
print("7 quick requests:", results)
time.sleep(1.05)
print("after the window passes:", allow("u1"))
Output:
top 3: [('meera', 140.0), ('ravi', 125.0), ('asha', 120.0)]
ravi rank (0 = first): 1
players with 100-130 points: ['asha', 'ravi']
7 quick requests: [True, True, True, True, True, False, False]
after the window passes: True
Leaderboard
ZINCRBYupdates a score atomically; no read-modify-write in the app.ZREVRANGE 0 2 WITHSCORESreturns the top three;ZREVRANKgives a player’s position (0-based) in O(log n), even with millions of players.ZRANGEBYSCOREanswers “who’s between 100 and 130 points?”.- Ties are ordered by member name. For “earlier achiever wins”, encode time into the score (for example
points * 1e10 - timestamp).
Newer Redis versions also offer the unified ZRANGE ... REV BYSCORE LIMIT syntax; the older commands above still work.
Sliding-window rate limiter
Each request adds its timestamp as both member and score. Before counting, ZREMRANGEBYSCORE drops timestamps older than the window. If the count exceeds the limit, reject. A pipeline with transaction=True wraps the four commands in MULTI/EXEC, so they run atomically and in one round trip.
Two details to know:
- This version records rejected requests too, so a client that keeps hammering stays blocked. If you only want to count accepted requests, the check-then-add must be atomic, which needs a Lua script (next module).
- Members must be unique: two requests in the same microsecond would collide. Production code appends a random suffix or a request id.
Memory is O(limit) per user. For very high limits, a fixed-window counter (INCR + EXPIRE) or the token bucket from lesson 6 is cheaper. The System Design course’s rate limiter lesson compares the algorithms.
Key takeaways
- Sorted sets keep members ordered by score with O(log n) updates and rank lookups.
- Leaderboards:
ZINCRBY,ZREVRANGE,ZREVRANK,ZRANGEBYSCORE. - A sorted set of timestamps gives an exact sliding-window rate limiter.
- Wrap multi-step updates in
MULTI/EXEC(or Lua) so they’re atomic.
Exercises
- Show “players around me”: the two players above and below a given player.
- Build a delayed job queue: score = run-at time; a worker polls
ZRANGEBYSCORE 0 now LIMIT 0 10. - Change the rate limiter to only record accepted requests, using a Lua script.
Quiz
- What’s the complexity of
ZREVRANK? - Why does the rate limiter remove old timestamps first?
- How would you break ties so the player who reached a score first ranks higher?
Show answers
- O(log n).
- So the count only includes requests inside the current window.
- Encode time into the score, for example
points * 1e10 - timestamp, so for equal points the earlier time has the higher score.