In my current company, we do something like... users play a quiz, top users win something. To show live leaderboard, we tell user to wait 1 minute, and each minute we run a crob to calculate the leaderboard by sorting the data, calculate rank of each user and save it somewhere, and everyone will see live leaderboard from that data, since sorting and calculating rank for each request will be too heavy.
Now I'm wondering, if I had to made that feature, I don't want to tell user to wait 1 minute to see his/her rank, but I'm unable to think an efficient approach. Then I remembered codeforces do it very well.
If I have to do it in C++, I will simply use ordered_set. But how will I do it if my data is stored in a database like MongoDB?
To be specific, I have only three requirements: 1) Each user can see their live rank 2) Rank of users on some page. Let's assume that page size is 20. 3) Insert in database
You can use Redis DB for that. Redis caches data in RAM, so access is faster and you can use sockets to provide two-way communication to the front end to display live changes. Do tell if you find a better way, curious about it.
Thanks! I guess that's the best way, just have to throw more money. And cache should be large enough to store data of all my users (even if they are in Billions?), and should also have a backup server in case master goes down. I wonder how Mike does this...
You have billions of users in a single contest?
You simply run a process wich updates all the time. If it takes 3 seconds, the updates comes after 3 seconds.
The best deal is to use a global cache like Redis. If you don't want to use cache, I am not sure if it's the right way, but here is what I thought:
create an index on quiz score (secondary index in case of Mongo). Now update and search query will be O(log(n)), instead of O(n). That means you can calculate the user at some rank in O(log(n)).
So now for point 2, for page size of 20... time complexity will be O(20*log(n)) or O(20+log(n)) because index is always sorted and you can go to first record in log(n) then linearly traverse it. Depends on how database internally handles it.
For point 1, you can use binary search to find rank, as you can calculate the quiz score of a user at some particular rank, so if your quiz score is less, your rank should be lower. Time complexity: O(log(n) network calls * log(n)). But this is inefficient since for 1 million users, you will have to do 20 network calls. And while doing this, your data might change by some other source. Not sure if there is a better way to calculate rank.