Ranking is a very common function, which is mostly used to motivate users to be active and attract new content. For example, the weekly ranking implemented by CSDN platform ranks the total number of articles read each week, and encourages users to continuously output high-quality content on the platform with ranking and prizes.

Recently, I also made a leaderboard feature, in some cases we need to deal with the same score ranking problem.

For example, the scores of Zhang SAN, Li Si and Wang Wu are all 100. We need to rank them according to the order that they reach 100 points first, that is, they need to rank by time.

It is not difficult to use Redis to implement real-time updated leaderboards. The ZSet data structure provided by Redis is very suitable for implementing leaderboards. However, how to implement the same points and then support sorting by time?

Implementation approach

Maybe the author just realized the Base Service generated by distributed ID before this, and subconsciously thought of the principle of distributed ID snowflake algorithm, which uses a variable of type long to store multiple information. The length of a long type is 8 bytes (64bit). The Snowflake algorithm uses 41 bits to record the timestamp, and the other bits store the machine room ID, machine ID, and serial number.

Redis ZSet supports double, also 8 bytes, so we can also use 41 bits to store the timestamp, real bits to store the user’s actual score.

In the Snowflake algorithm, the highest digit is not used in order to not allow negative ids to be generated, and there is no such limitation in implementing leaderboards because ultimately we only want the user’s score, not the timestamp score. But it also requires that the highest bits be either all zeros or all ones to avoid ordering errors. For example, the highest digit can be set to 1 when implementing the integral reverse ranking. However, ZSet already supports the reverse ranking, so there is no need to do anything else, so we still do not use the highest digit.

After removing the highest bit and the 41 bits used to store the timestamp, the remaining 22 bits represent the integral. At this time, we also need to consider the business. If 22bit is not enough to represent the integral, we can continue to compress the bits occupied by the timestamp.

Since leaderboards are periodic, such as weekly or monthly leaderboards, it is not necessary to store the full timestamp. We can take the number of milliseconds between the current time and the start of the cycle, which can reduce the number of bits from 41bit to 32bit, 16bit, or lower. The exact number of bits is up to the reader.

If the timestamp is 41bit and the score is 22bit, the score looks like this: Don’t 0 (highest) |, 0000000, 00000000, 0000000 (22 bit integral) | 0, 00000000, 00000000, 00000000, 00000000, 00000000 (41 bit timestamp)

Because the sort is sorted first by integral and then by time, the integral is in the high order and the timestamp is in the low order, so that no matter what the timestamp value is, the larger the integral, the larger the value represented by 64bit.

But that’s not the end of it.

With the same integrals, does the larger the timestamp, the larger the number of bits? What we need is the ascending order by time, that is, the user who reaches xx score first is ranked first. Therefore, we cannot simply use 41bit to store the timestamp, but should store a value that decreases as time goes by.

Since the leaderboard will have a cycle, such as weekly leaderboard is a week, and monthly leaderboard is a month, so we use 41bit to store the difference between the end time of a cycle YYY-MM-DD 23:59:59 corresponding timestamp and the timestamp of the user’s integral update time, this value will become smaller as time goes by, and there will not be a negative case. Just enough to do the trick.

Implement key code

1. Realize the conversion of integral + timestamp difference value to score

// periodEndTimestamp: Indicates the timestamp of the end time of the current period
// Make sure that point does not exceed 22bit: 2097151
private static long toScore(int point, long periodEndTimestamp) {
    long score = 0L;
    score = (score | point) << 41;
    score = score | (periodEndTimestamp - TimestampUtils.currentTimeMillis());
    return score;
}
Copy the code

2. Obtain points from Score

private static int getPoint(long score) {
     return (int) (score >> 41);
}
Copy the code

3. Update the score

@Override
public void updateRanking(Integer periodId, Long accountId, Integer addPoint) {
    String key = String.format(RankingCacheKeys.REALTIME_POINT_RANKING_KEY, periodId);
    Double score = redisTemplate.opsForZSet().score(key, String.valueOf(accountId));
    score = (score == null)?0d : score;
    int curPoint = getPoint(score.longValue());
    long newScore = toScore(curPoint + addPoint, getCurPeriodEndDateTimestamp(periodId));
    redisTemplate.opsForZSet().add(key, String.valueOf(accountId), newScore);
}
Copy the code

conclusion

Based on Redis ZSet to achieve the leaderboard (in reverse order) and support by time (in ascending order) sorting principle and notes:

  • 1. Split the 8 bytes of score and use them, the highest bit is not used, the rest part stores the actual score and the other part stores the time stamp;
  • 2. Sort by integral first and then by time, so it is necessary to store the score in the higher order and the timestamp in the lower order, so as to ensure that the higher the score is, the higher the score is;
  • 3. When the same score is sorted in ascending order by time, the score with the earliest time of the current score will inevitably be larger;
  • 4. Avoid the integral or timestamp overflow, for example, the maximum of 8bit can represent 255, if the integral can exceed 255, then you need to consider adding the integral to 9 bits…
  • 5. Since score needs to be recalculated every time user score is updated, atomic operation command of ZSet cannot be used, so there may be concurrent data consistency problem, which needs to be considered.

Here’s a thought question: If you add another conditional sort, do you think it can be done?

ZSet uses several commands to implement leaderboards

1. Get inverted rankings:

ZREVRANGEBYSCORE key min max offset count
Copy the code

2. Get a user’s score:

ZSCORE key member
Copy the code

3. Total number of participants (participants of this period) :

ZCARD key
Copy the code

4. Get a user’s current ranking (in reverse order, from largest to smallest) :

ZREVRANK key member
Copy the code