Loading...
List functional requirements for the system (Ask the chat bot for hints if stuck.)...
List non-functional requirements for the system...
Estimate the scale of the system you are going to design...
Define what APIs are expected from the system...
GET v1/scores/{event_id}
sample response:
{
{
"rank": 1,
"score": 700,
"player": "xxxx"
},
{
"rank": 2,
"score": 67,
"player": "xxxx"
},
...
}
GET v1/players/{player_id}
{
{
"rank": 1,
"score": 23,
"event_id": "xxxx"
},
{
"rank": 10,
"score": 34
"event_id": "xxxx"
},
...
}
Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...
We should have a separate table for each sports event.
And we should have separate table for each age group, and each country.
The schema we really need is:
user_id
score
The player schema should be:
user_id: uuid
player: str
event_ids: list[] (list of event_id)
country: [] country_id
age_group: age_group_id
You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...
When an event occurs during a game—such as a goal being scored—the Event Detection Service captures this event and generates an update request. This request is then sent to the Game Server, which acts as the central authority for maintaining the state of the game. The Game Server processes the event, updates the current game state accordingly, and might also check for any conflicts or older updates that need to be resolved to maintain data integrity. Once the game state is updated, the server broadcasts the changes to the Data Streaming Service, which efficiently streams this updated information to all connected clients. The Real-Time Notification Service further aids this flow by pushing notifications to client applications to inform them of the changes. This system ensures that all viewers—whether on websites, mobile applications, or scoreboards—receive live updates simultaneously, enhancing the overall experience of watching a sporting event.
Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...
We can use Redis sorted set. Internally, a sorted set is implemented by two data structures: a hash table and a skip list. The hash table maps users to scores and the skip list maps scores to users. In sorted sets, users are sorted by scores. A skip list is a list structure that allows for fast search. It consists of a base sorted linked list and multi-level indexes. The time complexity of insertion, removal, and search operations is O(n).
1. A user scores a point
When a user wins a match, they score 1 point; so we call ZINCRBY to increment the user’s score by 1 i
ZINCRBY
ZINCRBY leaderboard_feb_2021 1 'mary1934'
2. A user fetches the top 10 global leaderboard
We will call ZREVRANGE to obtain the members in descending order because we want the highest scores, and pass the ‘WITHSCORES’ attribute to ensure that it also returns the total score for each user, as well as the set of users with the highest scores. The following command fetches the top 10 players.
ZREVRANGE leaderboard 9 WITHSCORES
This returns a list like this:
[(user2,score2),(user1,score1),(user5,score5)...]
3. A user wants to fetch their leaderboard position
To fetch the position of a user in the leaderboard, we will call ZREVRANK to retrieve their rank on the leaderboard. Again, we call the rev version of the command because we want to rank scores from high to low.
ZREVRANK leaderboard_feb_2021 'mary1934'
Redis doesn't have persistence so we need to have a database to persist all our data. We can just use a relational database here given the number of different tables we have for age group/category/country.
Workflow for data synchronization:
We can use a change data capture which will dump changed data from Redis to a Kafka queue. Then we can use a data streaming service like Spark to update our relational database in the background. And since it's a relational database, we shouldn't run into concurrency issue given that relational database supports atomic operation.
Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...
Data Sharing:
We consider sharding in one of the following two ways: fixed or hash partitions.
One way to understand fixed partitions is to look at the overall range of points on the leaderboard. Let’s say that the number of points won in one month ranges from 1 to 1000, and we break up the data by range. For example, we could have 10 shards and each shard would have a range of 100 scores.
For this to work, we want to ensure there is an even distribution of scores across the leaderboard. Otherwise, we need to adjust the score range in each shard to make sure of a relatively even distribution.
When we are inserting or updating the score for a user, we need to know which shard they are in. We could do this by calculating the user’s current score from the MySQL database. This can work, but a more performant option is to create a secondary cache to store the mapping from user ID to score. We need to be careful when a user increases their score and moves between shards. In this case, we need to remove the user from their current shard and move them to the new shard.
To fetch the top 10 players in the leaderboard, we would fetch the top 10 players from the shard (sorted set) with the highest scores.
To fetch the rank of a user, we would need to calculate the rank within their current shard (local rank), as well as the total number of players with higher scores in all of the shards. Note that the total number of players in a shard can be retrieved by running the “info keyspace” command in O(1) .
A second approach is to use the Redis cluster, which is desirable if the scores are very clustered or clumped. Redis cluster provides a way to shard data automatically across multiple Redis nodes. It doesn’t use consistent hashing but a different form of sharding, where every key is part of a hash slot.
This approach has a few limitations:
When we need to return top K results (where K is a very large number) on the leaderboard, the latency is high because a lot of entries are returned from each shard and need to be sorted.
Latency is high if we have lots of partitions because the query has to wait for the slowest partition.
Another issue with this approach is that it doesn’t provide a straightforward solution for determining the rank of a specific user.
Explain any trade offs you have made and why you made certain tech choices...
Database trade off:
We can use a traditional relational database which can work for a small set using just a simple query:
SELECT (@rownum := @rownum + 1) AS rank, user_id, score
FROM leaderboard
ORDER BY score DESC;
To update a record:
UPDATE leaderboard set score=score + 1 where user_id='mary1934';
But for a large dataset with millions of rows, this will give us a very high latency.
We have heavy writes and heavy reads and given this requirement, is makes sense to use Redis, which will give us a sorted set data structure which is perfect for our usecase. Since it works in memory, it allows for fast reads and writes.
Try to discuss as many failure scenarios/bottlenecks as possible.
The Redis cluster can potentially experience a large-scale failure. When a Redis cluster fail, Redis will promote a replica. But if it fails completely, we can use our time series database to recreate the Redis tables.
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?
Faster retrieval and breaking tie
A Redis Hash provides a map between string fields and values. We could leverage a hash for 2 use cases:
To store a map of the user id to the user object that we can display on the leaderboard. This allows for faster retrieval than having to go to the database to fetch the user object.
In the case of two players having the same scores, we could rank the users based on who received that score first. When we increment the score of the user, we can also store a map of the user id to the timestamp of the most recently won game. In the case of a tie, the user with the older timestamp ranks higher.