Scalability issues, storing scores for users on a particular level for later retrieval

Question

I recently handed in a test assignment for a job application, which I was declined, with the motivation that it had scalability issues.

The test was to setup a REST-like backend for a hypothetical game, with three methods:

1. create session with a given user id (implicitly creating the user if it did not exist).
2. register scores for a given user (through a session created earlier) and a given level. Each score had to be stored, not just the top score.
3. retrieve a high score listing for a given level (max fifteen entries). If a single user had more than one of the top fifteen scores for a level, then only the highest score for that user would count.

No persistence was required.

The session and user handling was done using service layers, aptly called SessionService and UserService. Both services used concurrent hashmaps to store information.

The session service did not assume any invalidation of sessions previously associated with the given user (and no requirements suggested anything to that effect) but simply put an entry into the concurrent hashmap. The entry key was the external representation and the value was an internal representation which contained the user id, thus on validation, no information was retrieved from the external representation.

The user service was similar to the session service. The exception being that it used putIfAbsent rather than just put, I don't see issues here either, but include the relevant code just in case:

User user = users.get(userId);
if (null == user) {
    long creationTime = timeProvider.getCurrentTimeMillis();
    user = new User(userId, creationTime);
    User previouslyStoredUser = users.putIfAbsent(userId, user);
    if (null != previouslyStoredUser) {
        user = previouslyStoredUser;
    }
}

Finally the ScoreService in which I suspect the scalability issues are most likely to have occurred and include in its entirety:

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;

public class ConcurrentMapScoreService implements ScoreService {
    private final ConcurrentMap<ScoreKey, List<Score>> scores;

    public ConcurrentMapScoreService() {
        scores = new ConcurrentHashMap<>();
    }

    ConcurrentMapScoreService(ConcurrentMap<ScoreKey, List<Score>> scores) {
        this.scores = scores;
    }

    @Override
    public void registerScore(long userId, long level, long score) {
        ScoreKey key = new ScoreKey(userId, level);
        Score userScore = new Score(userId, score, level);

        List<Score> emptyScoreList = new ArrayList<>();
        List<Score> scoreList = scores.putIfAbsent(key, emptyScoreList);
        if (null == scoreList) {
            scoreList = emptyScoreList;
        }
        synchronized (scoreList) {
            scoreList.add(userScore);
        }
    }

    @Override
    public List<Score> getHighScoresForLevel(long level) {
        Map<Long, Score> highestScoreForLevelByUserId = new HashMap<>();
        for (Map.Entry<ScoreKey, List<Score>> entry : scores.entrySet()) {
            if (entry.getKey().getLevel() == level) {
                List<Score> userScores;
                synchronized (entry.getValue()) {
                    userScores = new ArrayList<>(entry.getValue());
                }
                if (userScores.size() > 0) {
                    Collections.sort(userScores);
                    Score highScore = userScores.get(0);
                    highestScoreForLevelByUserId.put(highScore.getUserId(), highScore);
                }
            }
        }

        List<Score> highScores = new ArrayList<>(highestScoreForLevelByUserId.values());
        Collections.sort(highScores);
        return highScores.subList(0, Math.min(MAX_NUMBER_OF_HIGH_SCORE_RESULTS, highScores.size()));
    }
}

I decided to not use a CopyOnWriteArrayList because it seemed like overkill, especially given my own scenario, in which a user gets a score on a level (which is registered) and then the high score for the level is displayed. This, however, might have been the issue.

I chose to use the userId and level as a key, because it seemed the least likely to require synchronization in the absence of concurrency handling. A user would be unlikely to get two scores at the same time at all, but in particular for a given level. Furthermore, I chose to include the level as part of the key, to be able to determine if a given entry was at all interesting when compiling the high score list for a given level. Thus avoiding scores for a user on other levels.

So my primary question is if anyone can spot obvious scalability issues, given the code (I'll include more code if needed/the code doesn't seem to be bad for scaling) or if, as I sort of hope, it was a lack of communication from my side, not clearly stating the reasons for the choices I made.

If there are obvious scalability issues in the code I've included, please suggest improvements!

Answer 1

This looks like a dreadful scalability problem:

    List<Score> highScores = new ArrayList<>(highestScoreForLevelByUserId.values());
    Collections.sort(highScores);
    return highScores.subList(0, Math.min(MAX_NUMBER_OF_HIGH_SCORE_RESULTS, highScores.size()));

You are sorting the list of scores first, and constraining it to the number you need second. This means that you are sorting a bunch of entries that you subsequently throw away. A good sort algorithm is O(n log n) but that's still a lot for large n.

Since you only need to keep 15 scores in the end, you should be looking for a scalable data structure that can keep track of the 15 scores you need at any given time. Ideally, it would give you a way to compare the score you are looking at with the 15th best you have seen so far.

In other words, a heap. The hands in the air explanation is that the heap property keeps an extreme value at the root, so you only need to do one compare to see if the next value you encounter should replace one of the values you have in the heap. When you find a higher score, you replace the root with the new score, then rebalance the ordering to restore the heap property. Once you have iterated through all the scores, you can either sort the scores in the heap, or pop them out of it as you prefer.

java.util.PriorityQueue is an unbounded queue based on a priority heap, with the lowest entry at the root. Therefore, you can add() the first 15 high scores you find into it. After that, you can use peek() to compare your next score with the lowest score you have stored. If the new score is higher, poll() to remove the old value, and add() the new value.

It might be better to implement the priority heap yourself - if you were to store the high scores in an array, and apply the heap properties to it by hand, then replacing the low score with another would save a siftUp operation that you don't need. That said, it's more complicated code to address a hypothetical additional performance concern. One possible compromise would be to write an interface that shows how you really want to interact with the heap, an implementation that relies on PriorityQueue, and then a comment to the effect that hand rolling the heap would be a possibility if the PriorityQueue were too slow.

Additionally, your design could have been improved by recognizing that the scores for the individual users could also be stored in a heap. This is hidden in the problem statement - you are expected to store all of a users scores, but you only ever need to retrieve the best score. Maintaining a heap for each user makes saving a new score slower (because the heap properties need to be maintained), but makes creating the high score list much faster (you only need the best score for each user - that O(1) in a heap).

Or better still - instead of a heap, simply maintain the invariant that the list always has the highest score in at index = 0. List.add(int,E) would be one option, but List.set(int,E) is probably better, provided you remember to append the previous best score.

Furthermore, the problem statement tells you that when retrieving data, you only need to consider high scores for the requested level. That means that any time spent iterating through scores for other levels is wasted. You can get around this by stratifying the scores by level first, and then breaking them down by user. That is to say, the basic idea for your database should be

Map<Level, Map<User, Heap<Score>> database;

Other notes:

You'd normally prefer to avoid creating array lists that you don't need. A better design would use a cache with a CacheLoader, so that the new parts are created only when needed. The Guava library has a lot of Shiny! hidden in it. Well worth a read.

My local coding conventions very sternly frown upon wildcards in import statements.

Your class has two different constructors, which is a bad idea. Having a constructor that can accept any kind of ConcurrentMap you want is good; but if you are also going to provide a default constructor, it should create the map and then pass it to the previous constructor.

Iterating over Map.Entries is good - my preferred style is to then copy the key/value to local variables, rather than using getKey() over and over again.

Bare variable declarations often indicate that there is a method that you haven't written.

  List<Score> userScores;
  synchronized (entry.getValue()) {
        userScores = new ArrayList<>(entry.getValue());
  }

looks as though it should be

  List<Score> userScores = copy(entry.getValue());

Answer 2

The only unscalable portion I see is the getHighScoresForLevel() method, which has to scan the entire table of existing scores (which becomes more of a burden with each new score, of course). Couldn't you store a Map<Long, List<Score>> of the current 15 high scores for each level and update it every time a new score is posted? That would give you constant time high-score lookup instead of linear time.