System Design Interview

Wrap Up

Wrap up 2 min readLesson 4 of 4

In this chapter, we have created a solution for building a real-time game leaderboard with the scale of millions of DAU. We explored the straightforward solution of using a MySQL database and rejected that approach because it does not scale to millions of users. We then designed the leaderboard using Redis sorted sets. We also looked into scaling the solution to 500 million DAU, by leveraging sharding across different Redis caches. We also proposed an alternative NoSQL solution.

In the event you have some extra time at the end of the interview, you can cover a few more topics:

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:

  1. 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.

  2. 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.

System failure recovery

The Redis cluster can potentially experience a large-scale failure. Given the design above, we could create a script that leverages the fact that the MySQL database records an entry with a timestamp each time a user won a game. We could iterate through all of the entries for each user, and call ZINCRBY once per entry, per user. This would allow us to recreate the leaderboard offline if necessary, in case of a large-scale outage.

Congratulations on getting this far! Now give yourself a pat on the back. Good job!

Chapter Summary

Figure — this diagram isn't included in the course export.

Reference Material

  1. Redis Sorted Set source code: https://github.com/redis/redis/blob/unstable/src/t_zset.c
  2. Geekbang: https://static001.geekbang.org/resource/image/46/a9/46d283cd82c987153b3fe0c76dfba8a9.jpg
  3. Building real-time Leaderboard with Redis: https://medium.com/@sandeep4.verma/building-real-time-leaderboard-with-redis-82c98aa47b9f
  4. Build a real-time gaming leaderboard with Amazon ElastiCache for Redis: https://aws.amazon.com/blogs/database/building-a-real-time-gaming-leaderboard-with-amazon-elasticache-for-redis
  5. How we created a real-time Leaderboard for a million Users: https://levelup.gitconnected.com/how-we-created-a-real-time-leaderboard-for-a-million-users-555aaa3ccf7b
  6. Leaderboards: https://redislabs.com/solutions/use-cases/leaderboards/
  7. Lambda: https://aws.amazon.com/lambda/
  8. Google Cloud Functions: https://cloud.google.com/functions
  9. Azure Functions: https://azure.microsoft.com/en-us/services/functions/
  10. Info command: https://redis.io/commands/INFO
  11. Why redis cluster only have 16384 slots: https://stackoverflow.com/questions/36203532/why-redis-cluster-only-have-16384-slots
  12. Cyclic redundancy check: https://en.wikipedia.org/wiki/Cyclic_redundancy_check
  13. Choosing your node size: https://docs.aws.amazon.com/AmazonElastiCache/latest/red-ug/nodes-select-size.html
  14. How fast is Redis?: https://redis.io/topics/benchmarks
  15. Using Global Secondary Indexes in DynamoDB: https://docs.aws.amazon.com/amazondynamodb/latest/developerguide/GSI.html.
  16. Leaderboard & Write Sharding: https://www.dynamodbguide.com/leaderboard-write-sharding/

Finished reading?

Mark it complete to track your progress.

PreviousDesign Deep DiveReal-time Gaming LeaderboardNext Understand the ProblemPayment System