Multithreaded scoreboard for different levels

Question

For an assignment I had to create a highly multi-threaded scoreboard for a multi level game. So every time a user adds a score if the level doesn't exist, it gets created ad-hoc.

Important point: a user CANNOT appear twice in the 15 best score. No database or disk persistence was permitted (so everything in memory). The score board has 2 function (put score, and get score). The scoreboard return the 15 top high scores.

Because the goal of this assignment is to produce the most "scalable" solution. I have to be careful on my data structure and design choices.

I have to say I'm far of being a Guru in multi-threading and multi-threading best practices. I'm posting my code here for people that have more experience than me in this field to give me some advice, pointers on what is considered good or bad practices.

First the assignment didn't specify if I had to keep ALL users score or only 15 scores per users (it was only specified the score board must return the 15 best scores). In the doubt I designed my structure to keep ALL scores (with a ConcurentSkipListSet).

//This is a map of Llevel containing a Set of score of each users of that level
private ConcurrentMap<Integer, ConcurrentMap<Integer, SortedSet<Integer>>> scoreData
      = new ConcurrentHashMap<>(8, 0.9f, 1);

//This is a map of HighScore list that is maintained everytime a score is subitted
  private ConcurrentMap<Integer, String> HighScoreList = new ConcurrentHashMap<>();

private void insertScore(ScoreData scoreInfo) {
    ConcurrentMap<Integer, NavigableSet<Integer>> userScores = scoreData.get(scoreInfo.getLevel());
    NavigableSet<Integer> scores;
    if (userScores == null) {
      userScores = new ConcurrentHashMap<>();
      ConcurrentSkipListSet<Integer> newScores = new ConcurrentSkipListSet<>();
      newScores.add(scoreInfo.getScore());
      scores = userScores.putIfAbsent(scoreInfo.getUserId(), newScores);
      if (scores != null) {
        //a thread came before and already set a list of score for that user
        scores.add(scoreInfo.getScore());
      }
      scoreData.put(scoreInfo.getLevel(), userScores);
    } else {
      scores = userScores.get(scoreInfo.getUserId());
      if (scores == null) {
        ConcurrentSkipListSet<Integer> newScores = new ConcurrentSkipListSet<>();
        scores = userScores.putIfAbsent(scoreInfo.getUserId(), newScores);
        if (scores == null) {
          scores = newScores;
        }
      }
      scores.add(scoreInfo.getScore());
    }

    //This is the part where I'm very not sure its the best solution..
    sychronized(userScores) { 
      String scoresSnapshotList = generateScoreList(userScores, level);
      HighScoreList.put(level, scoresSnapshotList);
    }
  }

public void getHighScoreList(int level) {
return scoreData.get(level)
}

Because I have to keep scalability in mind, I have chosen to maintain a separate map to keep the 15th best score for each level. But I had a concurrency problem before adding the synchronise block. If a thread created the score Snapshot and then was put in in hold just before inserting it in the map and an other thread inserted a score in the same level then the thread that was on hold wakes up and overwrite the snapshot with the snapshot he created and that doesn't contain the score of the thread that came just after.

Is having this synchronised block correct? Does it make the code less... concurrent? What would have been an other alternative to avoid this concurrent problem? Any advice on my general data structure(scoreData)?

This is a bonus question: In the eventuality that I only have to keep 15 score per level. I thought of using a PriorityQueue: ConcurentMap<Integer, PriorityQueue<UserScore>> scoreData.

Basically for every level a queue of 15 scores is kept and on score insertion I would just fill the queue check if the user inserting the score is not already there, if here is, check the scores. Otherwise if the queue is full I would just check if the .peek() score is smaller that the score being inserted and just swap these two.

What do you think?

EDIT:

Here is the generateScoreList method:

private String generateScoreList(
      ConcurrentMap<Integer, SortedSet<Integer>> allscores, int level) {

    SortedSet<ScoreInfo> finalResult = new TreeSet<>();
    Set<Integer> userIds = allscores.keySet(); 
    for (Integer userId : userIds) {
      SortedSet<Integer> userScores = allScoresForLevel.get(userId);
      if (!userScores.isEmpty() {
         ScoreInfo scoreInfo = new ScoreData(userId, userScores.last(), level);
         finalResult.add(scoreInfo);
      }

    }
    return createStringResult(finalResult);
  }

If I do not add the check if (!userScores.isEmpty() I will end up with userScores being empty because of the synchronised block. A simple scenario would be Thread1 gets pre-empted just before calling generateScoreList, then a bunch of other thread add new user's score to the same level, when Thread1 wake up and will call allScoresForLevel.keySet() it will return all the user's score list which are empty because the .add is in the sync block.

Does doing this design is good practice ? Or the does fact that I'm force to make that check show that the design could be improved?

Thanks!

Answer 1

This code is broken from a concurrency perspective:

ConcurrentMap<Integer, NavigableSet<Integer>> userScores = scoreData.get(scoreInfo.getLevel());
NavigableSet<Integer> scores;
if (userScores == null) {
  userScores = new ConcurrentHashMap<>();
  ConcurrentSkipListSet<Integer> newScores = new ConcurrentSkipListSet<>();
  newScores.add(scoreInfo.getScore());
  scores = userScores.putIfAbsent(scoreInfo.getUserId(), newScores);
  if (scores != null) {
    //a thread came before and already set a list of score for that user
    scores.add(scoreInfo.getScore());
  }
  scoreData.put(scoreInfo.getLevel(), userScores);
} else {
  scores = userScores.get(scoreInfo.getUserId());
  if (scores == null) {
    ConcurrentSkipListSet<Integer> newScores = new ConcurrentSkipListSet<>();
    scores = userScores.putIfAbsent(scoreInfo.getUserId(), newScores);
    if (scores == null) {
      scores = newScores;
    }
  }
  scores.add(scoreInfo.getScore());
}

What's interesting, is that, in part, you have the concept right for the inner-map... This code is OK:

  scores = userScores.get(scoreInfo.getUserId());
  if (scores == null) {
    ConcurrentSkipListSet<Integer> newScores = new ConcurrentSkipListSet<>();
    scores = userScores.putIfAbsent(scoreInfo.getUserId(), newScores);
    if (scores == null) {
      scores = newScores;
    }
  }
  scores.add(scoreInfo.getScore());

That inner code gets the scores, if it does not exist, it creates a new scores, puts the new scores back (if absent), and if some other thread already did it, it defaults back to the winning thread's scores.. so, it works.

But, the same concept is not checked on the outer map... the outer map handling is, summarized:

ConcurrentMap<Integer, NavigableSet<Integer>> userScores = scoreData.get(scoreInfo.getLevel());
....
if (userScores == null) {
  userScores = new ConcurrentHashMap<>();
  ....
  scoreData.put(scoreInfo.getLevel(), userScores);
} else {
  scores = userScores.get(scoreInfo.getUserId());
  ....
}

That code has the same vulnerability, but you don't check the put with putIfAbsent.

Note that, in Java 8, you can make that logic all a whole lot simpler with:

ConcurrentMap<Integer, NavigableSet<Integer>> userScores = scoreData.computeIfAbsent(
      scoreInfo.getLevel(), level -> new ConcurrentHashMap<>());
NavigableSet<Integer> scores = userScores.computeIfAbsent(
      scoreInfo.getUserId(), user -> new ConcurrentSkipListSet<>());
scores.add(scoreInfo.getScore());