2

I am building a webapp (Angular frontend, Groovy/Spring/Hibernate/MySQL backend) that will allow users to compete against each other over certain activities. Each activity will have 1 winner and 1 loser. I want a live user ranking system that ranks users (1st to last place) depending on their win/loss record/history. The scoring & ranking is actually based on the ELO rating system and is very similar to the flavor of ELO used by the Chess community. I only mention this because calculating each user's individual performance rating/ELO score is a fairly involved computation and is not as simple as merely adding up the number of wins they've score to date or anything simple like that.

It's also important to mention that a user's ranking is something that needs to be stored in the database and can't simply be something achieved by: (1) sorting all users based on their performance ratings score, (2) finding a particular user in the sorted list, (3) ranking == position in sorted list. Ranking needs to be persisted to the DB and updated frequently.

So this live user ranking system needs to:

  1. Trigger any time any two users compete against each other and the activity determines a winner/loser; and then
  2. Take the results of that activity/competition and apply a fairly mathematically complex algorithm to determine the new performance rating (overall score) of both users; and then
  3. Update their ranking in some DB table (by sorting; highest performance rating ranks 1st, lowest performance rating ranks last, etc.). This process is called a re-ranking and affects all users (shifting them up/down).

The first two items above are pretty straight forward: I can handle them easily in the backend/middleware layer. Because re-ranking could take, say, 30 - 60 seconds if we have a large number of users, I'll likely make the reporting of competiton/activity results asynchronous from the re-ranking of all the users. Meaning the backend receives competition results and stores them, then publishes a messages to a broker that a re-ranking must take place. A consumer listening to that broker then reacts to the message by triggering a re-ranking.

But the 3rd item, performing the re-ranking, is where I foresee possible performance issues. This is because if my app has hundreds of thousands of users and again re-ranking takes, say, up to 60 seconds to run, then anytime any two of those users compete against each other the rankings of all users will be affected and all users will get shifted up/down by some number of rankings. It's also totally possible that 2 sets of users compete against each other around the same point of time, and trigger multiple re-rankings around the same point in time).

In this scenario I'm worried about write/lock contention when the DB is updating all the rankings of all the users, but in the meantime the app can't be in a wait state (waiting for rankings to update) and will need to be reading the user/ranking tables, even if they are being written to.

So I ask: what tricks can I employ (either table structure or optimizations, or perhaps programming tricks in a stored procedure, or perhaps something at the JPA/Hibernate/JDBC data layer, etc.) so that a re-ranking can take place at any time (live user rankings) without locking the user/rankings tables? In other words, its perfectly OK if the rankings table reports that User 12345 has a rank of 45 (45th place) even if a re-ranking is in progress that, when complete, will bump User 12345 up to rank 44. I just don't want blocking/contention.

  • For example is optimistic locking a potential solution here? – smeeb Nov 21 '17 at 18:04
  • 2
    According to this post, ratings are achieved on a game-by-game basis, not on a per-season basis. Are you sure that you have to recalculate everyone's performance rating, every time? It seems to me like you only need to make new point calculations based on new game results. Obtaining the ranking results is unremarkable; it's a simple sorting query. – Robert Harvey Nov 21 '17 at 18:16
  • Thanks @RobertHarvey (+1): a few things (1) ratings ("ELO score") is recalculated after each game/competition/activity, not at the end of a "season" or over the course of some period of time, like a month, etc. So yes, I need to make new point calculations based on each and every game result in real-time (users will be "playing" games all day long, every day). – smeeb Nov 21 '17 at 18:30
  • (2) Yes, ranking/re-ranking is a sorting query, but I'm trying to avoid re-sorting hundreds of thousands of user ratings/ELO scores each time the frontend asks for their ranking. Yes I could employ caching, but then I have to manage the cache. And it will change constantly, because each and every new game will have a ripple affect (shifting up/down rankings) on everyone's rankings. – smeeb Nov 21 '17 at 18:30
  • 3
    You don't need to retrieve hundreds of thousands of user ratings, nor will mysql sort that many. That's not how database engines work. You will ask for the top 10 (or a single player) at any given moment, and the query optimizer will work out the best way to give you those top 10. Relax and let the database engine do this work; that's what it is designed for. Your job will be to write the query and create sensible table indexes so that the database engine can run your query efficiently. – Robert Harvey Nov 21 '17 at 18:39
5

Before guessing that it will be slow you actually have to demonstrate that it's slow. This is in the fundamentals of performance optimization

Hundreds of thousands of users, times game count for each will take very well under a second with the proper indexes in place

Build a dummy structure, write the query, post some benchmarks, and we can then have a look at how we can improve the stats

  • Unless there's a fundamental problem with the design. See my comment below the question. – Robert Harvey Nov 21 '17 at 18:22
  • @RobertHarvey I agree with you, and I also agree that if it's fast enough there won't really be a case for calculating in an async fashion. Thus eliminating whatever concurrency issue was detailed in the question – Silviu-Marian Nov 21 '17 at 18:26
  • 1
    Thanks @Silviu-Marian (+1) I catch what you're saying: don't pre-emptively optimize, I get that. But I do want to prevent totally re-architecting things to handle scale, if I can just do a bit of due diligence up front and build a solution that will scale nicely then I have much less to worry about down the road! – smeeb Nov 21 '17 at 18:33
  • This isn't really an answer to the question. This is general advice that could apply to many types of questions. – JimmyJames Nov 22 '17 at 16:37
1

There is some question as to whether you need to worry about this before you have benchmarked the performance. I kind of agree but it's also the case that contention issues such as deadlocks could occur based on your explanation. That is, this isn't just a performance concern. It can be difficult to test for and debug these kinds of problems. I don't think it's a bad idea to design this to make that a non-issue.

I'm not familiar with MySQL so I won't talk about locking details but you should familiarize yourself with cursor isolation levels. The key is that the less strict the isolation level, the less contention you will have but you could also have subtle issues that result. I would recommend you stick with the most strict level you can manage.

You mention optimistic locking. This is something that I highly recommend in high contention situations. One thing you will need to determine on your own is whether your algorithm is deterministic irrespective of order of application or if you care. Optimistic locking will allow for high concurrency so you need to understand how that might change the results.

The basic approach that I use is to add a timestamp or version number to each record. The latter is more bulletproof but the former will work as long as the time resolution is fine enough. Then when you go to update a record, you read it and then update it like so:

UPDATE table_name
SET version = [incremented record version], ...
WHERE key = [surrogate key] and version = [current record version];

And check how many records were updated. If you get zero records updated, something else updated the record and you need to start over. It's also possible on some databases/isolation levels for this to succeed but then have the commit fail.

If you execute these updates one record at a time you will only lock each one for the time it takes to execute the update. You would probably rarely (if ever) have collisions but you need to make sure your code will start over on that record if the update doesn't update any rows or the commit fails.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.