Design a Leaderboard System

Redis Sorted Set: Core 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

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

Implementation: Encode timestamp into the score
  score_key = score × 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

Approach 1: Single Redis Sorted Set (recommended up to ~100M)
  100M × 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

Friends Leaderboard

Fetch all friend IDs from social graph, ZSCORE lb:weekly {friend_id} for each friend (pipelined), sort in application. Cost: O(F) where F = friend count.

Percentile Rank at Scale

Approach 1: ZCARD + ZREVRANK (exact, two Redis calls). Approach 2: Maintain 1000 score buckets, each tracking count. percentile = sum(buckets above user's score) / total_users. O(1) lookup, refreshed every 1 minute.

Event Bus Design (Kafka)

Topic: leaderboard_system-events
  Partitions: 64 (scale consumers horizontally)
  Partition key: entity_id (user_id / order_id — preserves per-entity ordering)
  Retention: 7 days (compliance) or 24h (high-volume telemetry)
  Replication factor: 3, min.insync.replicas: 2

Producer: idempotent producer enabled (enable.idempotence=true)
Consumer: consumer group "leaderboard_system-processors"
  - At-least-once delivery + idempotent handlers (dedup by event_id)
  - DLQ topic: leaderboard_system-events-dlq (poison messages after 3 retries)
  - Lag alert: consumer lag > 60s → scale workers

Design a Leaderboard System: async side effects MUST NOT block the synchronous API response.
  Sync path: validate → persist source of truth → publish event → return 201
  Async path: consumers update caches, indexes, notifications, aggregates