Gaming Leaderboard (Top K)

# Gaming Leaderboard (Top K)

0) Problem Restatement

Design a real-time leaderboard system for a massively multiplayer online game that displays the top K players (e.g., top 100) based on scores. Core challenges include handling millions of score updates per second, maintaining sorted rankings efficiently, supporting multiple leaderboard types (global, regional, daily, weekly), and serving read requests with low latency (< 100ms).

---## 1) Requirements

1.1 Functional

• Update scores: Players earn points, update their scores in real-time.
• Top K leaderboard: Display top 100 players globally.
• Player rank: Show a specific player's current rank.
• Neighboring ranks: Show players ranked around a specific player (e.g., rank 95-105 for player at rank 100).
• Multiple leaderboards: Support global, regional (by country), and time-based (daily, weekly, monthly).
• Historical leaderboards: View past leaderboards (e.g., last month's top 100).
• Rewards: Distribute rewards to top K players at end of period.

1.2 Non-Functional

• Low Latency:

- Read (get top K): < 100ms.

- Write (update score): < 50ms.

• Scalability: Handle 100M active players, 1M score updates/sec.
• Accuracy: Rankings must be correct (strong consistency for writes, eventual consistency for reads acceptable).
• Availability: 99.9% uptime.
• Real-Time: Leaderboard updates within 1-2 seconds of score change.

1.3 Scale Estimates

• Active players: 100 million.
• Concurrent players: 10 million at peak.
• Score updates: 1M updates/sec (players complete matches, earn points).
• Leaderboard reads: 10M reads/sec (players check rankings).
• Leaderboard types:

- 1 global.

- 200 regional (countries).

- 3 time-based per type (daily, weekly, monthly).

• Total leaderboards: 1 + 200 + (3 × 201) = 804 leaderboards.

1.4 API Design

The core APIs required for the service:

• Update Score: POST /v1/score - Update player score.
• Get Top K: GET /v1/leaderboard/:id/top - Get top K players.
• Get Rank: GET /v1/leaderboard/:id/rank/:player_id - Get player rank.
• Get Neighbors: GET /v1/leaderboard/:id/neighbors/:player_id - Get surrounding ranks.

2) High-Level Architecture

2.1 Overview

• Write Path: Score Update → Score Service → Update Leaderboard (Sorted Set) → Cache.
• Read Path: Client → API Gateway → Leaderboard Service → Cache/DB → Return Top K.
• Key components: Redis Sorted Sets for rankings, sharding for scale, caching for reads.

2.2 Architecture Diagram

---
config:
  layout: elk

flowchart TB
    %% Game Clients
    Player["Player
(Game Client)"] -->|"1. Score Update"| AG["API Gateway"]
    Player -->|"6. Get Top 100"| AG
    
    %% Score Update Flow
    AG -->|"2. POST /score"| ScoreService["Score Service"]
    ScoreService -->|"3. Validate & Dedupe"| Redis1["Redis
(Idempotency)"]
    ScoreService -->|"4. ZADD Score"| LeaderboardDB["Leaderboard DB
(Redis Sorted Set)"]
    
    %% Update Multiple Leaderboards
    LeaderboardDB -->|"5a. Global"| GlobalLB["Global Sorted Set"]
    LeaderboardDB -->|"5b. Regional"| RegionalLB["Regional Sorted Set
(country-based)"]
    LeaderboardDB -->|"5c. Time-Based"| TimeLB["Time-Based Sorted Set
(daily/weekly/monthly)"]
    
    %% Read Flow (Top K)
    AG -->|"7. GET /leaderboard/top100"| LBService["Leaderboard Service"]
    LBService -->|"8. Check Cache"| ReadCache["Read Cache
(Redis)"]
    ReadCache -->|"9a. Cache Hit"| Player
    ReadCache -->|"9b. Cache Miss"| Query["Query Sorted Set"]
    Query -->|"10. ZREVRANGE 0 99"| LeaderboardDB
    LeaderboardDB -->|"11. Top 100"| LBService
    LBService -->|"12. Cache Result"| ReadCache
    LBService -->|"13. Return Top 100"| Player
    
    %% Player Rank Query
    AG -->|"R1. GET /rank/{player_id}"| LBService
    LBService -->|"R2. ZREVRANK"| LeaderboardDB
    LeaderboardDB -->|"R3. Rank"| Player
    
    %% Analytics
    ScoreService -->|"A1. Log Event"| Analytics["Analytics Service"]
    Analytics -->|"A2. Store Events"| AnalyticsDB[(Analytics DB)]
    
    %% Archival
    TimeLB -->|"E1. End of Period"| Archival["Archival Service"]
    Archival -->|"E2. Snapshot"| ArchiveDB[(Archive DB)]
    Archival -->|"E3. Rewards"| Rewards["Reward Service"]
    
    %% Styling
    classDef client fill:#e3f2fd,stroke:#1976d2,stroke-width:2px;
    classDef service fill:#c8e6c9,stroke:#388e3c,stroke-width:2px;
    classDef storage fill:#fff9c4,stroke:#f57f17,stroke-width:2px;
    classDef lb fill:#f3e5f5,stroke:#7b1fa2,stroke-width:2px;
    
    class Player client;
    class AG,ScoreService,LBService,Analytics,Archival,Rewards service;
    class Redis1,ReadCache,AnalyticsDB,ArchiveDB storage;
    class LeaderboardDB,GlobalLB,RegionalLB,TimeLB lb;

3) Components (what & why)

Game Client

• Send score updates when player earns points.
• Request leaderboard data (top K, player rank).
• Display rankings in game UI.

API Gateway

• Route requests to appropriate services.
• Rate limiting (prevent abuse).
• Authentication.

Score Service

• Responsibilities:

- Validate score updates (anti-cheat).

- Deduplicate updates (idempotency).

- Update all relevant leaderboards (global, regional, time-based).

• Anti-Cheat: Verify score changes are legitimate (not too large).

Leaderboard DB (Redis Sorted Sets)

• Structure: Sorted set with player_id as member, score as value.
• Operations:

- ZADD leaderboard player_id score: Add/update player score.

- ZREVRANGE leaderboard 0 99: Get top 100 players (descending).

- ZREVRANK leaderboard player_id: Get player's rank.

- ZSCORE leaderboard player_id: Get player's score.

• Why Redis: In-memory, O(log n) operations, atomic updates.

Read Cache (Redis)

• Cache top K leaderboard results.
• TTL: 1-5 seconds (balance freshness vs load).
• Cache Key: leaderboard:global:top100.

Leaderboard Service

• Responsibilities:

- Fetch top K from cache or DB.

- Fetch player rank.

- Fetch neighboring ranks.

• Optimization: Batch queries, parallel fetches.

Analytics Service

• Log all score updates for analytics.
• Detect anomalies (cheating, bugs).

Archival Service

• Snapshot leaderboards at end of period (daily, weekly, monthly).
• Store in Archive DB for historical queries.
• Trigger reward distribution.

Reward Service

• Calculate rewards for top K players.
• Distribute in-game currency, items, badges.

4) Data Model

Leaderboard (Redis Sorted Set)

leaderboard:global -> {
  player_123: 95000,
  player_456: 89000,
  player_789: 87500,
  ...
}

Player

Player(
  player_id,
  username,
  country,
  total_score,
  created_at
)

Score Event (Analytics)

ScoreEvent(
  event_id,
  player_id,
  score_delta,
  new_score,
  timestamp,
  match_id
)

Archived Leaderboard

ArchivedLeaderboard(
  leaderboard_id,
  type,  -- GLOBAL, REGIONAL, DAILY, WEEKLY, MONTHLY
  region,
  start_date,
  end_date,
  top_k_snapshot  -- JSON: [{player_id, score, rank}, ...]
)

5) Key Flows

5.1 Update Score Flow

- Global: ZADD leaderboard:global player_123 95000.

- Regional: ZADD leaderboard:us player_123 95000.

- Daily: ZADD leaderboard:daily:2023-10-20 player_123 5000.

5.2 Get Top K Flow

- Query: ZREVRANGE leaderboard:global 0 99 WITHSCORES.

- Redis returns top 100 players with scores.

- Fetch player usernames from Player DB (batch query).

- Cache result with 2-second TTL.

5.3 Get Player Rank Flow

5.4 Get Neighboring Ranks Flow

- Get player rank: ZREVRANK leaderboard:global player_123 → 1245.

- Fetch range: ZREVRANGE leaderboard:global 1240 1250 WITHSCORES.

5.5 End-of-Period Flow (Daily Leaderboard)

- Fetches entire daily leaderboard: ZREVRANGE leaderboard:daily:2023-10-20 0 -1 WITHSCORES.

- Saves snapshot to Archive DB.

- Distributes rewards to top 100 players.

6) Deep Dive A: Efficient Data Structures for Top K (~10 mins)

Problem

Store and rank 100M players efficiently. Need O(log n) updates and O(K) Top K queries.

Solution: Redis Sorted Set

#### Why Redis Sorted Set?

• In-Memory: Ultra-fast reads/writes.
• Sorted: Automatically maintains sorted order by score.
• Atomic Operations: ZADD, ZREVRANGE are atomic.
• Logarithmic Complexity: O(log n) for insert/update.

#### Key Operations

# Add/update player score
ZADD leaderboard:global 95000 player_123

# Get top 100 (descending by score)
ZREVRANGE leaderboard:global 0 99 WITHSCORES

# Get player's rank (0-indexed)
ZREVRANK leaderboard:global player_123

# Get player's score
ZSCORE leaderboard:global player_123

# Get count of players
ZCARD leaderboard:global

#### Time Complexity

• Insert/Update: O(log n).
• Get Top K: O(log n + K).
• Get Rank: O(log n).
• Get Score: O(1).

Alternative: Min Heap (In-Memory)

#### Approach

• Maintain min heap of size K (top K players).
• When new score comes:

- If score > heap min: Replace min with new score, heapify.

- Else: Ignore.

#### Pros

• Space Efficient: Only store K items (vs all players).
• Fast Reads: O(1) to get top K.

#### Cons

• Slow Writes: O(n) to find player for update.
• No Full Ranking: Can't get rank for players outside top K.

#### When to Use

• Only need top K (no full ranking).
• K is small (e.g., 100).

Hybrid Approach (Sharding + Sorted Set)

#### Problem

Redis Sorted Set limited to single-node memory (~100 GB).

#### Solution

• Shard by Score Range:

- Shard 1: Scores 0-1M.

- Shard 2: Scores 1M-2M.

- Shard 3: Scores 2M+.

• Top K Query: Query top K from each shard, merge results.

Data Structure Comparison

flowchart TD
    Problem["Top K Problem
(100M players)"]
    
    Problem --> RS["Redis Sorted Set"]
    Problem --> Heap["Min Heap"]
    Problem --> Shard["Sharded Sorted Set"]
    
    RS --> RSPros["✅ O(log n) ops
✅ Full ranking
✅ Atomic"]
    RS --> RSCons["❌ Single-node limit
❌ Memory intensive"]
    
    Heap --> HeapPros["✅ Space efficient
✅ O(1) top K read"]
    Heap --> HeapCons["❌ No full ranking
❌ Slow updates"]
    
    Shard --> ShardPros["✅ Horizontal scale
✅ Full ranking"]
    Shard --> ShardCons["❌ Complex merging
❌ Cross-shard queries"]
    
    classDef pros fill:#c8e6c9,stroke:#388e3c,stroke-width:2px;
    classDef cons fill:#ffcdd2,stroke:#c62828,stroke-width:2px;
    
    class RSPros,HeapPros,ShardPros pros;
    class RSCons,HeapCons,ShardCons cons;

7) Deep Dive B: Sharding Strategies (~10 mins)

Problem

Single Redis instance can't hold 100M players (memory limit, throughput limit).

Sharding Strategies

#### Strategy 1: Shard by Player ID (Hash-Based)

player_123 -> Shard 0 (hash(123) % 10 = 3)
player_456 -> Shard 6 (hash(456) % 10 = 6)

##### Top K Query

• Query top K from each shard.
• Merge results globally.
• Example: Top 100 global.

- Fetch top 100 from each of 10 shards.

- Merge 1000 results, select top 100.

##### Pros:

• Even distribution of players.
• Parallel queries.

##### Cons:

• Must query all shards for top K (expensive).
• Merge overhead.

#### Strategy 2: Shard by Score Range

Score 0-10K    -> Shard 0
Score 10K-100K -> Shard 1
Score 100K+    -> Shard 2

##### Top K Query

• Start with highest score shard (Shard 2).
• Fetch top K from Shard 2.
• Optimization: If Shard 2 has ≥ K players, done.

##### Pros:

• Top K query very fast (only query top shards).
• Natural sharding by performance tier.

##### Cons:

• Uneven distribution (top shard may be hot).
• Need to rebalance as score distribution changes.

#### Strategy 3: Geo-Sharding (Regional Leaderboards)

US players     -> US Shard
EU players     -> EU Shard
Asia players   -> Asia Shard

##### Use Case:

• Regional leaderboards (no global merge needed).

##### Pros:

• Perfect for regional leaderboards.
• Low latency (geo-distributed).

##### Cons:

• Global leaderboard requires merging all regions.

Recommended: Hybrid (Player ID + Score Range)

• Regional Leaderboards: Shard by region.
• Global Leaderboard: Shard by player ID, merge top K.
• Optimization: Cache global top K (refresh every 2 seconds).

Sharding Architecture

flowchart TB
    TopK["Top K Query"] --> Coord["Query Coordinator"]
    
    Coord -->|"parallel query"| S1["Shard 1
(players 1-10M)"]
    Coord -->|"parallel query"| S2["Shard 2
(players 10M-20M)"]
    Coord -->|"parallel query"| S10["Shard 10
(players 90M-100M)"]
    
    S1 -->|"top 100"| Merge["Merge Results"]
    S2 -->|"top 100"| Merge
    S10 -->|"top 100"| Merge
    
    Merge -->|"global top 100"| Cache["Cache Result
(2s TTL)"]
    Cache --> TopK
    
    classDef shard fill:#fff9c4,stroke:#f57f17,stroke-width:2px;
    classDef merge fill:#c8e6c9,stroke:#388e3c,stroke-width:2px;
    
    class S1,S2,S10 shard;
    class Coord,Merge,Cache merge;

8) Deep Dive C: Real-Time Updates & Caching (~8 mins)

Problem

1M score updates/sec, 10M leaderboard reads/sec. Need low latency without overwhelming DB.

Write Optimization

#### Batching

• Accumulate score updates for 1-2 seconds.
• Batch update Redis in single operation.
• Trade-off: Slight delay (1-2s) acceptable for leaderboard.

#### Idempotency

• Use idempotency key (match_id + player_id).
• Store in Redis with TTL (5 minutes).
• Check: Before applying update, check if already processed.

Read Optimization

#### Multi-Layer Caching

##### L1: Application Cache (In-Memory)

• Cache top K in application memory (each API server).
• TTL: 2 seconds.
• Benefit: Serve reads without Redis query.

##### L2: Redis Cache

• Cache top K results in Redis.
• TTL: 5 seconds.
• Key: cache:leaderboard:global:top100.

##### L3: Redis Sorted Set (Source of Truth)

• Authoritative leaderboard data.

#### Cache Invalidation Strategy

##### Time-Based (TTL)

• Cache expires after TTL (e.g., 2 seconds).
• Next read refreshes cache.
• Pros: Simple, works well for high-read scenarios.

##### Write-Through

• On score update, invalidate cache immediately.
• Cons: High write rate → constant cache invalidation.

##### Hybrid (Recommended)

• Use TTL (2-5 seconds).
• Accept slightly stale data (eventual consistency).

Read/Write Flow Optimization

# Write (Score Update)
def update_score(player_id, score_delta):
    # Check idempotency
    if is_duplicate(player_id, score_delta):
        return
    
    # Update Redis Sorted Set
    redis.zadd("leaderboard:global", {player_id: new_score})
    
    # Update regional and time-based leaderboards
    redis.zadd(f"leaderboard:{region}", {player_id: new_score})
    redis.zadd(f"leaderboard:daily:{date}", {player_id: daily_score})
    
    # No cache invalidation (TTL handles it)

# Read (Top K)
def get_top_k(k=100):
    # Check L1 cache (app memory)
    if app_cache.has("top100"):
        return app_cache.get("top100")
    
    # Check L2 cache (Redis)
    if redis.exists("cache:top100"):
        result = redis.get("cache:top100")
        app_cache.set("top100", result, ttl=2)
        return result
    
    # Query source (Redis Sorted Set)
    result = redis.zrevrange("leaderboard:global", 0, 99, withscores=True)
    
    # Cache result
    redis.setex("cache:top100", 5, result)
    app_cache.set("top100", result, ttl=2)
    
    return result

Caching Architecture

flowchart LR
    Read["Read Request"] --> L1["L1: App Cache
(2s TTL)"]
    L1 -->|"miss"| L2["L2: Redis Cache
(5s TTL)"]
    L2 -->|"miss"| L3["L3: Redis Sorted Set
(Source of Truth)"]
    
    L1 -->|"hit"| Return["Return Result
(~1ms)"]
    L2 -->|"hit"| Return2["Return Result
(~10ms)"]
    L3 -->|"query"| Return3["Return Result
(~50ms)"]
    
    classDef cache fill:#c8e6c9,stroke:#388e3c,stroke-width:2px;
    
    class L1,L2,L3 cache;

9) Scaling & Performance (~5 mins)

Horizontal Scaling

• Score Service: Stateless, scale with load balancer.
• Leaderboard Service: Stateless, scale horizontally.
• Redis: Shard across multiple instances.

Performance Metrics

• Write latency: 10-50ms (Redis ZADD).
• Read latency: 1-10ms (cached), 50-100ms (cache miss).
• Throughput: 1M writes/sec, 10M reads/sec.

Bottlenecks & Mitigations

• Redis Memory: Shard by player ID or score range.
• Read Load: Multi-layer caching (app cache + Redis cache).
• Write Load: Batch updates, async processing.

10) Failure Modes & Recovery

Redis Failure

• Impact: Leaderboard unavailable.
• Mitigation: Redis Cluster with replication (3× replicas).

Cache Invalidation Storm

• Impact: Cache expires for popular leaderboard → all requests hit DB.
• Mitigation: Probabilistic early expiration (jitter in TTL).

Score Update Loss

• Impact: Player score not updated.
• Mitigation: Log all updates to Kafka, replay on failure.

11) Trade-offs & Alternatives

Redis vs Database

• Redis: In-memory, fast, limited durability.
• Database: Persistent, slower, complex indexing.
• Choice: Redis for hot data, DB for archival.

Strong vs Eventual Consistency

• Strong: All players see same leaderboard immediately.
• Eventual: Slight delays acceptable (1-2 seconds).
• Choice: Eventual (caching with TTL).

Real-Time vs Batch Processing

• Real-Time: Update leaderboard immediately.
• Batch: Update every 5 minutes.
• Choice: Real-time with 1-2 second caching.

12) Security & Anti-Cheat

Score Validation

• Verify score changes are within expected range.
• Flag suspicious updates (e.g., 100K points in 1 second).

Rate Limiting

• Limit score updates per player (e.g., max 10/minute).

Audit Logs

• Log all score updates for forensic analysis.

13) Interview Time Allocation (45 min)

• 5 min: Requirements & scope (functional, non-functional, scale).
• 10 min: HLD & architecture diagram (write + read paths).
• 5 min: Data model & key flows (update, top K, rank).
• 10 min: Deep dive on efficient data structures (Redis Sorted Set vs Min Heap).
• 10 min: Deep dive on sharding strategies (player ID, score range, geo).
• 5 min: Real-time updates, caching, scaling, failure handling.

14) Summary

• Core Challenges: Efficiently rank 100M players, handle 1M writes/sec and 10M reads/sec, real-time updates with low latency.
• Key Components:

- Sharding: Partition by player ID, merge results for global Top K.

- Multi-Layer Caching: App cache (2s) + Redis cache (5s) + Sorted Set.

- Idempotency: Prevent duplicate updates.

• Scaling Strategy: Shard Redis, cache aggressively, batch updates.
• Performance: 10-50ms writes, 1-10ms cached reads, 1M writes/sec, 10M reads/sec.

This design supports real-time leaderboards for massive multiplayer games with millions of players and billions of score updates daily.