Alex Xu V2 - 10 Real time Gaming Leaderboard


The Problem

Leaderboards are common in gaming and elsewhere to show who is leading a particular tournament

Step 1 - Understand the Problem and Establish Design Scope

How is score calculated for leaderboard?

Are all players on the leaderboard?

Do we only care about the top 10 users?

How many users are there?

How many matches are palyed during a tournament

How do we determine the rank if two players have the same score?

Is leaderboard real-time?

Functional Requirements

Display top 10 players on the leaderboard Show user’s specific rank Display players who a four places above and below a desired user (Bonus)

Non Functional Requirements

Real time updates Score update in real time on leaderboard General scalability, availability and reliability requirements

Back of Envelope Calculations

There’s likely going to be peak hours for gameplay, not all over 24 hours

5M DAU x 10 games? -> 50 x 10 ^ 6 / 10 ^ 5 -> 500 QPS

High Level Design and Get Buy-In

/v1/scores -> Add new score

/v1/scores -> Get top 10 players Sample Response:

![[Pasted image 20240217081914.png]]

GET /v1/scores/{:user_id}

get rank of specific user

High Level Architecture

![[Pasted image 20240217082204.png]]

Should client talk to leaderboard service directly instead of going through game service?

Do we need a message queue?

Data Models


If scale is small we can do SQL

Relational database can’t handle the number of reads that we need

Relational can’t work with millions of rows

We could use batch operations, but then it’s not a real-time leaderboard

Redis Solution

Key, Value store Also has sorted Set

Implementation using Redis Sorted Sets

ZADD -> Inserts or Updates for O(logN)

ZINCRBY -> increment score, assume it starts at 0. O(logN)

ZRANGE / ZREVRANGE -> fetch range of users (logN + M)

ZRANK -> Fetch position of user in ascending / descendin in logarithmic time

Workflow within sorted sets

![[Pasted image 20240218082734.png]]

User fetches top 10 ranks ![[Pasted image 20240218082821.png]]

![[Pasted image 20240218082840.png]]

Storage Requirement

25 MAU storing 26 bytes is -»> 25 x 10^6 x 26 -> 650 MB

More than enough for a single redis server

2500 QPS is easily handled by Redis


Use a SQL table along with the Redis so we can story match history and other things

Step 3 -> Design Deep Dive

Cloud Provider vs. Own Servers

![[Pasted image 20240218083547.png]]

Using AWS Lambda + AWS Gateway

![[Pasted image 20240218083719.png]]

Benefit is that it autoscales. Xu recommends the Lambda way instead of building own servers like AWS EC2

Scaling Redis

Fixed vs. Hash Partitions

Partition by the number of points won, from 1 to 100, 100 to 200, etc. Query the final partition to get the winners

Hash users and put them into random buckets

Alternative solution: NoSQL

Optimized for writes

Efficiently sorting items

![[Pasted image 20240218084414.png]]

Ah and now he mentions DynamoDB

Stuff about a “global secondary index” that’s apparently completely made up from a non-technical AWS Salesperson

Wrapping up

System failure recovery