一、前言
不论是手游还是端游，貌似都离不开排行榜，没有排行榜的游戏是没有灵魂的游戏，因为排行榜能够让用户分泌多巴胺，这样日活才会上来，有了用户就有钱赚。产品千方百计的让用户留存，设计各种排行榜：集体段位排名、集体积分或金币排名、寰球榜单实时排名。如果用户量少的话，间接用 mysql 一张表存储着用户跟某个段位或者积分，而后查的时候再从高到低 order by 排序下。当然用户量很少的话是能够的，但随着用户量猛增，达到千万、亿级的话，这个必定行不通了。你可能说我加索引、再多的话分库分表总行了吧。思路是没错的，但这不是很好的计划，排行榜实时更新，亿级用户这 io 设想都怕。
接下来我就来说下我认为比拟好的设计方案。Redis 的 sorted set 数据结构，这几乎就是为了排行榜而生的数据结构呀。应用 Redis 排名非常简单对于百万级别的用户不必消耗太多内存即可实现高效疾速的排名，什么玩意，百万级别，题目不是亿级级别吗？客官稍安勿躁，这数据结构轻松应答百万是没问题的，与亿相差 100 倍的话，也会有性能瓶颈的。那咱们有啥优化计划吗？有的，那就是针对 sorted set 进行分桶。好了，接下来咱们就来看看如何设计。
二、设计方案
这种计划就能轻松应答亿级用户的游戏排行榜了，我这里是以积分排行榜来设计的，其它的相似。这里每个桶依照承载百万用户，而后分了 100 个桶，如果积分散布平均的话，那就能够轻松应答了。当然你可能会说，有很多老手比方玩了几次这个游戏就没玩了，在 [0,1000) 区间这个桶内有很多用户。是的，这里咱们履行之前，会有个预估。大一点的公司会有数据分析工程师来对游戏用户做个正当的预估，通过一系列高数、概率论的常识把这个分桶区间预估的尽可能准。小公司的话不须要分桶，不要适度设计了。当然也有小局部小公司也有这么大的体量的话，那只能本人预估了，而后后续动静的去调整。
对于查问 top 排名时，只有查看最高分区桶 sorted set 排名即可。
对于查问个体用户的排名，依据用户的积分判断看在哪个桶里，计算本桶该用户的排名与高于以后分桶范畴的分桶用户相加失去相干用户的排名。
三、代码实现
1、GameRanking 游戏排行榜类
@Data
@Builder
@EqualsAndHashCode(callSuper = false)
@Accessors(chain = true)
@TableName("game_ranking")
public class GameRanking {@TableId(value = "id", type = IdType.AUTO)
private Integer id;
/**
* 用户昵称
*/
private String nickName;
/**
* 排行榜分数
*/
private Double leaderboardScore;
/**
* 排行榜类型
*/
private Integer leaderboardType;
/**
* 名次
*/
private Long ranking;
/**
* 用户名称
*/
private String grade;
/**
* 用户编号
*/
private String userNo;
/**
* 创立工夫
*/
private LocalDateTime createTime;
/**
* 更新工夫
*/
private LocalDateTime updateTime;
}2、排行榜返回的 RankingInfo 类
@Data
public class RankingInfo {
private List<GameRanking> scoreList;
private GameRanking userSelf;
}3、实现类
@Service
@Slf4j
public class RankingServiceImpl implements RankingService {public CommonVO gameRanking(String userNo, String gameId, Integer leaderboardType, Long topN) {RankingInfo rankingInfo = new RankingInfo();
try {List<GameRanking> gameRankingList = doGameRanking(topN);
GameRanking gameRankingSelf = doGameRankingSelf(userNo);
rankingInfo.setScoreList(gameRankingList);
rankingInfo.setUserSelf(gameRankingSelf);
} catch (Exception e) {log.error("gameRanking exception", e);
return CommonVO.error(CommonVOCode.SERVER_ERROR, "gameRanking exception");
}
return CommonVO.success(rankingInfo);
}
public List<GameRanking> doGameRanking(Long topN) {List<Map<String, Object>> dataMapList = new ArrayList<>();
JSONArray jsonArray = JSONArray.parseArray(ConfigManager.get(GameConstant.USER_SCORE_RANKING_INTERVAL));
int size = jsonArray.size();
long totalNum = 0;
for (int i = size - 1; i >= 0; i--) {JSONObject jsonObject = jsonArray.getJSONObject(i);
String bucketName = jsonObject.getString("bucketName");
long unitBucketNum = redisUtil.zCard(bucketName);
totalNum += unitBucketNum;
if (totalNum <= topN && unitBucketNum != 0) {List<Map<String,Object>> one = commonScoreList(bucketName, topN);
dataMapList.addAll(one);
} else if (totalNum >= topN) {List<Map<String,Object>> two = commonScoreList(bucketName, unitBucketNum);
dataMapList.addAll(two);
break;
}
}
if (CollectionUtils.isEmpty(dataMapList)) {return Collections.emptyList();
}
Set<ZSetOperations.TypedTuple<String>> vals = dataMapList.stream().map(en -> new DefaultTypedTuple<>((String) en.get("userId"),
(Double) en.get("score"))).collect(Collectors.toSet());
// 计算排行榜前先将 topN 桶删除，避免之前进入桶的用户烦扰
redisUtil.delAndZaddExec(GameConstant.USER_SCORE_RANKING_TOPN, vals);
return doTopNScoreList(topN);
}
public List<Map<String, Object>> commonScoreList(String bucketValue, Long topN) {
Set<ZSetOperations.TypedTuple<String>> rangeWithScores
= redisUtil.zRevrangeWithScore(bucketValue, 0L, topN - 1);
List<ZSetOperations.TypedTuple<String>> userScoreTuples = new ArrayList<>(rangeWithScores);
return userScoreTuples.stream().map(tuple -> {String userId = tuple.getValue();
Double score = tuple.getScore();
Map<String,Object> map = new HashMap<>();
map.put("userId", userId);
map.put("score", score);
return map;
}).collect(Collectors.toList());
}
public List<GameRanking> doTopNScoreList(Long topN) {List<String> userIdList = new ArrayList<>();
Set<ZSetOperations.TypedTuple<String>> rangeWithScores
= redisUtil.zRevrangeWithScore(GameConstant.USER_SCORE_GENERAL_RANKING_TOPN, 0L, topN - 1);
List<ZSetOperations.TypedTuple<String>> userScoreTuples = new ArrayList<>(rangeWithScores);
List<GameRanking> collect = userScoreTuples.stream().map(tuple -> {String userId = tuple.getValue();
Double score = tuple.getScore();
userIdList.add(userId);
return GameRanking.builder()
.userNo(userId)
.leaderboardScore(score)
.ranking((long) (userScoreTuples.indexOf(tuple) + 1))
.build();}).collect(Collectors.toList());
List<Map<String,String>> nickNameList = gameRankingMapper.selectBatchByUserNo(userIdList);
collect.stream().forEach(gameRanking -> {Map<String,String> entity = nickNameList.stream()
.filter(map -> map.get("userNo").equals(gameRanking.getUserNo())).findFirst().orElse(null);
if (entity != null) {gameRanking.setNickName(entity.get("nickName"));
}
});
// 减少段位性能
long count = 0;
for (int i = 0; i < collect.size(); i++) {
count++;
collect.get(i).setGrade(getUserGrade(count));
}
return collect;
}
public GameRanking doGameRankingSelf(String userNo) {
Long selfRank = null;
Double score = null;
String nickName = null;
try {GameRanking gameRanking = gameRankingMapper.selectOneByUserNo(userNo);
if (Objects.isNull(gameRanking)) {nickName = getNickName(userNo);
} else {nickName = gameRanking.getNickName();
}
score = gameRanking.getLeaderboardScore();
// 看该用户是否在 topN 的排行里
GameRanking rankingSelf = rankingSelfInTopN(userNo);
if (rankingSelf != null) {return rankingSelf;}
String bucketName = getBucketNameParseFromConfigCenter(score);
Map<String, Object> map = Collections.synchronizedMap(new LinkedHashMap());
Map<String, String> rankingIntervalMap = getRankingIntervalMapFromConfigCenter();
// 桶地位比拟
for (Map.Entry<String, String> entry : rankingIntervalMap.entrySet()) {if (entry.getValue().compareTo(bucketName) >= 0) {Long perBucketSize = redisUtil.zCard(entry.getValue());
map.put(entry.getValue(), perBucketSize);
}
}
Long totalNum = 0L;
for (Map.Entry<String, Object> entry : map.entrySet()) {if (Objects.isNull(entry.getValue())) {continue;}
if (bucketName.equals(entry.getKey())) {
// 本身桶的排名
Long selfNum = redisUtil.zRevrank(bucketName, userNo) + 1;
// 本身桶排名与本身桶后面的总人数相加
totalNum += selfNum;
} else {totalNum += Long.parseLong(entry.getValue().toString());
}
}
selfRank = totalNum;
} catch (NullPointerException e) {
selfRank = null;
score = null;
log.warn("gameRanking userNo:{"+userNo+"} score is null", e);
}
return GameRanking.builder()
.userNo(userNo)
.leaderboardScore(score)
.nickName(nickName)
.ranking(selfRank)
.grade(getUserGrade(selfRank))
.build();}
public GameRanking rankingSelfInTopN(String userNo) {Double score = redisUtil.zScore(GameConstant.USER_SCORE_GENERAL_RANKING_TOPN, userNo);
if (score == null) {return null;} else {Long rank = redisUtil.zRevrank(GameConstant.USER_SCORE_GENERAL_RANKING_TOPN, userNo);
return GameRanking.builder()
.userNo(userNo)
.leaderboardScore(score)
.ranking(rank + 1)
.nickName(getNickName(userNo))
.grade(getUserGrade(rank + 1))
.build();}
}
public String getBucketNameParseFromConfigCenter(Double score) {JSONArray jsonArray = JSONArray.parseArray(ConfigManager.get(GameConstant.USER_SCORE_GENERAL_RANKING_INTERVAL));
int size = jsonArray.size();
boolean flag = false;
for (int i = 0; i < size; i++) {JSONObject jsonObject = jsonArray.getJSONObject(i);
String bucketInterval = jsonObject.getString("bucketInterval");
String bucketName = jsonObject.getString("bucketName");
String[] split = bucketInterval.substring(1, bucketInterval.length() - 1).split(",");
if ((score >= Double.parseDouble(split[0]) && "+endless".equals(split[1])) ||
(score >= Double.parseDouble(split[0]) && score < Double.parseDouble(split[1]))) {flag = true;} else {flag = false;}
if (flag) {return bucketName;}
}
return "";
}
}4、原子性操作导致并发平安问题
redisUtil.delAndZaddExec(GameConstant.USER_SCORE_RANKING_TOPN, vals);通过 lua 脚本保障原子一致性，解决并发平安问题。
public class RedisUtil {
@Autowired
private StringRedisTemplate stringRedisTemplate;
private static final String DELANDZADDSCRIPT =
"if redis.call('zcard', KEYS[1]) > 0 then\n" +
"redis.call('del', KEYS[1])\n" +
"for i, v in pairs(ARGV) do\n" +
"if i > (table.getn(ARGV)) / 2 then\n" +
"break\n" +
"end\n" +
"redis.call('zadd', KEYS[1], ARGV[2*i - 1], ARGV[2*i])\n" +
"end\n" +
"return 1\n" +
"else\n" +
"for i, v in pairs(ARGV) do\n" +
"if i > (table.getn(ARGV)) / 2 then\n" +
"break\n" +
"end\n" +
"redis.call('zadd',KEYS[1], ARGV[2*i - 1], ARGV[2*i])\n" +
"end\n" +
"return 1\n" +
"end";
private RedisScript<Long> redisDelAndZaddScript = new DefaultRedisScript<>(DELANDZADDSCRIPT, Long.class);
/**
* 刪除及插入
* @param key 键
* @param val 批量值
*/
public void delAndZaddExec(String key, Set<ZSetOperations.TypedTuple<String>> val) {if (StringUtils.isEmpty(key)) {throw new IllegalArgumentException();
}
Object[] args = new Object[val.size()*2];
int i= 0;
for (ZSetOperations.TypedTuple<String> it : val) {args[2*i] = String.valueOf(it.getScore());
args[2*i + 1] = it.getValue();
i++;
}
stringRedisTemplate.execute(redisDelAndZaddScript, Collections.singletonList(key), args);
}
}其它非核心代码我就不贴了，至此，亿级用户游戏排行榜设计方案到此结束，心愿对你有帮忙，欢送交换意见与认识。
欢送小伙伴们关注我的公众号，Java 后端支流技术栈的原理、源码剖析、架构以及各种互联网高并发、高性能、高可用的解决方案。