theMossYouNeed's blog

Tech-Init: How does CodeForces maintain friends leaderboard in realtime so efficiently?
By theMossYouNeed, history, 4 years ago, In English

You all might have seen that we can see our friend group's rank list on codeforces in real-time. It makes me wonder how this feature is implemented at the BackEnd? I surely know that they initialize these customised lists at the time of registration because we can see registered friends too. Can anyone from the tech-team or anyone who has an idea help me know this. Do they keep a sorted-set kind of thing to implement this friends-ranklist and also is the score updation event-driven? MikeMirzayanov

  • Vote: I like it
  • +85
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +31 Vote: I do not like it

Let me preface this with I'm not by any means a DB expert and I don't know how CF works. But I do have a decent amount of experience making stuff on the internet.

From a theoretical point of view, this is quite an interesting question. In practice (abusing properties of the real world), I would guess the naive check every time the page is refreshed is fine. For instance, I probably have more friends than ~90% of CF users (and I only have 154). In the last div2, only 16 of my friends either competed during the contest or have yet VP'd it.

So I would imagine the performance would be pretty much fine if you just did a DB query generally like:

  • get my list of friends
  • left join the relevant contest info to determine who is registered/has submitted
  • take rows WHERE that person is actually competing
  • take the correct page of the 20 of those that we are interested in, sorted by current place
  • left join all 'expensive' data that needs to be shown to the user

Since almost everyone on CF has a very small number of friends competing in any given contest live, this probably isn't more than an order of magnitude harder than just displaying any particular individual's score.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

this might be helpful .

→ Reply