Design a Leaderboard System

Redis Sorted Set: Core Data Structure

Redis sorted sets are the canonical leaderboard primitive, and leading with ZADD and ZINCRBY semantics anchors every subsequent design choice to this data structure.

ZADD lb:weekly {score} {user_id}           → O(log N) insert/update
ZREVRANK lb:weekly {user_id}               → O(log N) get user's rank
ZREVRANGE lb:weekly 0 99 WITHSCORES        → O(log N + K) top K
ZINCRBY lb:weekly {delta} {user_id}        → O(log N) atomic increment
ZREVRANGE lb:weekly rank-5 rank+5          → O(log N + K) neighbors

Internal: Skip List (balanced probabilistic data structure)
  10M members: ~20 operations per query (log₂(10M) ≈ 23)
  Each operation: ~1µs → total: ~20µs per query
  Memory: ~1.5 GB for 10M entries (key + score + overhead)

Tie-Breaking Mechanism

Once scores tie, the interviewer will ask who ranks higher. Encoding the achievement timestamp into the score makes ordering deterministic without requiring a secondary sort pass.

Problem: Two users have score=1000 → who ranks higher?
Rule: Earlier achievement = higher rank

Implementation: Encode timestamp into the score
  score_key = score x 10^10 + (MAX_TIMESTAMP - actual_timestamp)

Example (MAX_TIMESTAMP = 9999999999, must be < 10^10 so it never
         disturbs the score ordering):
  User A: score=1000 at t=100 → key = 1000_0000000000 + 9999999899
  User B: score=1000 at t=200 → key = 1000_0000000000 + 9999999799
  User A's key > User B's key → User A ranks higher ✓

Scaling Beyond 100M Members

When a single board outgrows one Redis node or hot-key limits, evaluate sharding strategies such as score-range shards, global heap merge, or Fenwick trees for percentile-only queries.

Approach 1: Single Redis Sorted Set (recommended up to ~100M)
  100M x 150 bytes = 15 GB → fits in single large Redis instance
  All operations still O(log N) ≈ O(27)

Approach 2: Sharded by Score Range (for > 100M)
  Shard 0: scores 0-999 → Redis instance 0
  Shard N: scores 9000-9999 → Redis instance N
  Top-K: query highest shard → get top from that shard
  Rank: sum counts in all higher shards + ZREVRANK within shard

Approach 3: Fenwick Tree / Binary Indexed Tree (for percentile rank)
  Score range [0, MAX_SCORE] → array of counts
  rank(score) = prefix_sum(MAX_SCORE) - prefix_sum(score)
  O(log S) where S = max score range, regardless of user count

Global board merge at 100M players: heap-merge top-K from 16 shards costs O(K x 16) ≈ 1.6K ZREVRANGE ops every 60s, requiring ~27ms compute compared to 15 GB RAM if held in one ZSET. Exact global ZREVRANK at 100M is O(log 100M) ≈ 27 hops x 200K lookups/sec, which is Redis CPU bound; use Count-Min Sketch for approximate rank on the global board only. Async merge every 60s trades 60s staleness for a sub-second read path, which is acceptable for display boards though not for payout-critical ranks.

Friends Leaderboard

Friends leaderboards are a filtered read rather than a separate data structure. The service fetches friend IDs from the social graph, pipelines ZSCORE calls for each friend, and sorts the results in application memory. The query cost scales as O(F) where F represents friend count.

Percentile Rank at Scale

Percentile rank ("top 5%") is a common staff-level follow-up at massive scale. While exact ZREVRANK works up to roughly 100M members, maintaining 1,000 score count buckets yields O(1) lookup with negligible error, calculated as the sum of buckets above the user's score divided by total users and refreshed every minute.

Event Bus Design (Kafka)

Kafka acts as the durability layer behind Redis. If a Redis shard fails, score events are replayed to rebuild the leaderboard without losing player progress.

Topic: score-events
  Partitions: 64 (partition by leaderboard_id)
  Partition key: leaderboard_id (per-board ordering for replay)
  Retention: 7 days (Redis rebuild buffer after failover)
  Producers: Score Writer after ZINCRBY/ZADD succeeds
  Payload: {lb_id, user_id, delta, new_score, tiebreak_key, timestamp}
  Consumers: analytics pipeline, cross-region sync, PostgreSQL audit log

Topic: leaderboard-snapshots
  Low volume; emitted on weekly rotation
  Consumers: History Service → PostgreSQL archive of top 10K

Score update path: validate → Redis ZINCRBY (< 1ms) → publish score-events → 200
  Rank reads never touch Kafka; Kafka enables rebuild if Redis shard is lost