億級排行榜設計
問題
假如有 10 億的用戶，每個用戶有自己的分數 (score)，請你設計一個排行榜，可以根據用戶的分數進行排名，每個用戶可以知道自己在排行榜中的排名情況。
分析
一說到排行榜，我們的第一反應肯定是使用 Redis 的 ZSET 結構實現，那麼使用 ZSET 如何實現對 10 億用戶進行排序？
ZSET 單 key
第一種思路，使用 ZSET 單 key，也就是將 10 億用戶都放入一個 ZSET key 中，簡單明瞭，這樣設計是最簡單的，但查詢的性能是否可以接受？我們來計算一下：
ZSET 結構使用 SkipList 實現，查詢的時間複雜度：ZREVRANK：O(log(N))
查詢單個排名的理論時間複雜度：O(log(10^9)) ≈ 30 次比較
內存佔用分析：
public class PerformanceAnalysis {
// 1. 內存佔用(假設每個成員)
private static final long MEMORY_PER_MEMBER =
+ 8 // score (double)
+ 20 // member (假設userId字符串)
+ 8 // 指針
+ 32; // 跳錶節點開銷
// 10億用戶預估內存
private static final long TOTAL_MEMORY =
MEMORY_PER_MEMBER * 1_000_000_000L; // 約68GB
// 2. 跳錶層數
private static final int SKIP_LIST_LEVELS =
(int) Math.log(1_000_000_000L) / Math.log(2); // 約30層
}假定每個成員對象約 68 字節，那麼 10 億用戶約需要 68GB 內存，當然實際場景下，可以考慮對單個成員對象再進行壓縮，內存佔用可以再小一點。
如果僅從查詢的效率考慮，如果僅查詢單個成員的排名，Redis 的查詢耗時是不用擔心的，但如果要進行範圍查詢，那麼性能則非常不樂觀了。
在實際的生產環境中，如此大的單 Key 我們一般稱爲 GodKey 或者 BigKey，是需要極力避免的，我們都知道 Redis 是純內存的數據庫，執行命令是單線程執行的，對於內存操作是非常的快的，但是如果單個 Key 值特別大時，容易阻塞線程，影響其他命令的執行，同時對於 Redis 服務器的網卡也是一個巨大的挑戰，試想如果對於 68G 的 ZSET Key 進行範圍查詢的話，如果 1W QPS，Redis 怕是直接會被打爆。
如此看來，這個使用單 Key 存儲全部的用戶數據，應該行不通的。
ZSET 多 Key
“一個籬笆三個樁，一個好漢三個幫”，那麼既然一個 key 搞不定，那我們就分多個 key 就好了吧？那麼我們該如何將 10 億用戶存儲到多個 key 中呢？
正常第一反應，我們就搞 10000 個 key，然後使用 userId 取模，路由到對應的子 key 就好了吧？但是我們的需求是，需要可以知道每個用戶在排行榜中的排名，顯然這種路由的方式，是無法滿足需求的。
拆分多個子 key，根據某種規則路由的思路是完全沒問題的，不能根據 userId 路由，那我們可否換一種思路，以其他維度進行路由？
換一個思路，如果以分數作爲分桶邏輯，初始化 N 個分桶，每個分桶的劃定範圍以分數區間劃定，當新用戶獲得分數後，根據其分數路由到所在的分桶中。
那麼，用戶的排名該如何計算？
計算用戶的排名，我們肯定已經知道用戶所在的分桶，可以直接獲得在當前分桶中的排名，同時比當前分桶分數大的分桶名稱我們肯定也可以知道，那麼將所有的前面的分桶中的總數量累加，再加上當前分桶的排名，就是該用戶的總排名。
問題
綜上，多個子 key 也就是數據分桶的邏輯，基本上是可以滿足我們的需求的，但是還有一個問題，就是數據分佈不均勻的問題，我們設定的多個分桶，但是每個分桶中的數據量一定不是均勻的，可能會出現數據傾斜的問題，如何解決？
對此，較爲簡單的處理方式，當某個數據桶的數據量超過一定的閾值後，可以進行拆分，縮小分桶的數值範圍，分割成兩個子桶，如此循環往復，直到無法再切分爲止。
實現 demo
下面是 Claude 給出的代碼實現 Demo，邏輯可能不嚴謹，僅作參考：
import lombok.Data;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.data.redis.core.ZSetOperations;
import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
public class ScoreBucketRankingSystem {
@Data
public class UserScore {
private long userId;
private double score;
private long timestamp;
}
@Data
public class RankInfo {
private long userId;
private double score;
private long rank;
private String bucketKey;
}
@Data
public class ScoreBucket {
private String bucketKey;
private double minScore;
private double maxScore;
private long userCount;
}
private final RedisTemplate<String, String> redisTemplate;
private final String BUCKET_PREFIX = "rank:bucket:";
private final String BUCKET_META_KEY = "rank:bucket:meta";
// 緩存分桶信息
private final ConcurrentHashMap<String, ScoreBucket> bucketCache = new ConcurrentHashMap<>();
// 初始化分桶配置
private final List<ScoreBucket> initBuckets = new ArrayList<>() ;
public ScoreBucketRankingSystem(RedisTemplate<String, String> redisTemplate) {
this.redisTemplate = redisTemplate;
initBuckets();
}
// 初始化分桶
private void initBuckets() {
for (ScoreBucket bucket : initBuckets) {
String bucketKey = BUCKET_PREFIX + bucket.getBucketKey();
bucketCache.put(bucketKey, bucket);
// 存儲分桶元信息
redisTemplate.opsForHash().put(
BUCKET_META_KEY,
bucketKey,
JSON.toJSONString(bucket)
);
}
}
// 更新用戶分數
public void updateScore(long userId, double newScore) {
// 1. 找到用戶當前所在的分桶
String oldBucketKey = findUserCurrentBucket(userId);
// 2. 計算用戶應該在的分桶
String newBucketKey = calculateBucketKey(newScore);
// 3. 如果分桶發生變化，需要遷移
if (oldBucketKey != null && !oldBucketKey.equals(newBucketKey)) {
moveUserToBucket(userId, oldBucketKey, newBucketKey, newScore);
} else {
// 4. 直接更新分數
updateUserScore(userId, newBucketKey, newScore);
}
}
// 查找用戶當前所在的分桶
private String findUserCurrentBucket(long userId) {
for (String bucketKey : bucketCache.keySet()) {
Double score = redisTemplate.opsForZSet().score(bucketKey, String.valueOf(userId));
if (score != null) {
return bucketKey;
}
}
return null;
}
// 根據分數計算應該所在的分桶
private String calculateBucketKey(double score) {
for (ScoreBucket bucket : bucketCache.values()) {
if (score >= bucket.getMinScore() && score <= bucket.getMaxScore()) {
return BUCKET_PREFIX + bucket.getBucketKey();
}
}
throw new IllegalArgumentException("Score out of range: " + score);
}
// 將用戶從舊分桶移動到新分桶
private void moveUserToBucket(long userId, String oldBucketKey, String newBucketKey, double newScore) {
redisTemplate.execute(new SessionCallback<List<Object>>() {
@Override
public List<Object> execute(RedisOperations operations) {
operations.multi();
// 從舊分桶刪除
operations.opsForZSet().remove(oldBucketKey, String.valueOf(userId));
// 更新分桶計數
operations.opsForHash().increment(BUCKET_META_KEY, oldBucketKey + ":count", -1);
operations.opsForHash().increment(BUCKET_META_KEY, newBucketKey + ":count", 1);
// 添加到新分桶
operations.opsForZSet().add(newBucketKey, String.valueOf(userId), newScore);
return operations.exec();
}
});
}
// 更新用戶分數
private void updateUserScore(long userId, String bucketKey, double newScore) {
redisTemplate.opsForZSet().add(bucketKey, String.valueOf(userId), newScore);
}
// 獲取用戶排名信息
public RankInfo getUserRankInfo(long userId) {
String bucketKey = findUserCurrentBucket(userId);
if (bucketKey == null) {
return null;
}
Double score = redisTemplate.opsForZSet().score(bucketKey, String.valueOf(userId));
Long rank = redisTemplate.opsForZSet().reverseRank(bucketKey, String.valueOf(userId));
if (score == null || rank == null) {
return null;
}
// 計算全局排名
long globalRank = calculateGlobalRank(bucketKey, rank);
RankInfo rankInfo = new RankInfo();
rankInfo.setUserId(userId);
rankInfo.setScore(score);
rankInfo.setRank(globalRank);
rankInfo.setBucketKey(bucketKey);
return rankInfo;
}
// 計算全局排名
private long calculateGlobalRank(String currentBucketKey, long rankInBucket) {
long globalRank = rankInBucket;
// 加上更高分數段的用戶數
for (ScoreBucket bucket : bucketCache.values()) {
String bucketKey = BUCKET_PREFIX + bucket.getBucketKey();
if (bucket.getMaxScore() > bucketCache.get(currentBucketKey).getMaxScore()) {
globalRank += bucket.getUserCount();
}
}
return globalRank;
}
// 獲取排行榜區間
public List<RankInfo> getRankRange(int start, int end) {
List<RankInfo> result = new ArrayList<>();
int currentPosition = 0;
// 從高分到低分遍歷分桶
for (ScoreBucket bucket : bucketCache.values()) {
String bucketKey = BUCKET_PREFIX + bucket.getBucketKey();
// 獲取分桶內的排名區間
Set<ZSetOperations.TypedTuple<String>> ranksInBucket =
redisTemplate.opsForZSet().reverseRangeWithScores(
bucketKey,
Math.max(0, start - currentPosition),
end - currentPosition
);
if (ranksInBucket != null) {
for (ZSetOperations.TypedTuple<String> rank : ranksInBucket) {
if (currentPosition >= start && currentPosition <= end) {
RankInfo rankInfo = new RankInfo();
rankInfo.setUserId(Long.parseLong(rank.getValue()));
rankInfo.setScore(rank.getScore());
rankInfo.setRank(currentPosition + 1);
rankInfo.setBucketKey(bucketKey);
result.add(rankInfo);
}
currentPosition++;
}
}
if (currentPosition > end) {
break;
}
}
return result;
}
// 獲取分桶統計信息
public List<ScoreBucket> getBucketStats() {
List<ScoreBucket> stats = new ArrayList<>();
for (ScoreBucket bucket : bucketCache.values()) {
String bucketKey = BUCKET_PREFIX + bucket.getBucketKey();
Long count = redisTemplate.opsForZSet().zCard(bucketKey);
ScoreBucket stat = new ScoreBucket();
stat.setBucketKey(bucket.getBucketKey());
stat.setMinScore(bucket.getMinScore());
stat.setMaxScore(bucket.getMaxScore());
stat.setUserCount(count != null ? count : 0);
stats.add(stat);
}
return stats;
}
// 定期優化分桶
public void optimizeBuckets() {
List<ScoreBucket> stats = getBucketStats();
// 檢查是否需要分裂或合併分桶
for (ScoreBucket bucket : stats) {
if (bucket.getUserCount() > 100_000_000) { // 1億用戶
// 分裂分桶
splitBucket(bucket);
} else if (bucket.getUserCount() < 1_000_000) { // 100萬用戶
// 考慮合併分桶
mergeBucket(bucket);
}
}
}
// 分裂分桶
private void splitBucket(ScoreBucket bucket) {
double mid = (bucket.getMinScore() + bucket.getMaxScore()) / 2;
ScoreBucket lowerBucket = new ScoreBucket();
lowerBucket.setBucketKey(bucket.getBucketKey() + "_lower");
lowerBucket.setMinScore(bucket.getMinScore());
lowerBucket.setMaxScore(mid);
ScoreBucket upperBucket = new ScoreBucket();
upperBucket.setBucketKey(bucket.getBucketKey() + "_upper");
upperBucket.setMinScore(mid + 1);
upperBucket.setMaxScore(bucket.getMaxScore());
// 重新分配用戶到新分桶
redistributeUsers(bucket, lowerBucket, upperBucket);
}
// 合併分桶
private void mergeBucket(ScoreBucket bucket) {
// 實現合併邏輯
}
// 重新分配用戶
private void redistributeUsers(ScoreBucket oldBucket, ScoreBucket lowerBucket, ScoreBucket upperBucket) {
String oldBucketKey = BUCKET_PREFIX + oldBucket.getBucketKey();
String lowerBucketKey = BUCKET_PREFIX + lowerBucket.getBucketKey();
String upperBucketKey = BUCKET_PREFIX + upperBucket.getBucketKey();
long cursor = 0;
ScanOptions options = ScanOptions.scanOptions().count(1000).build();
do {
ScanResult<ZSetOperations.TypedTuple<String>> scanResult =
redisTemplate.opsForZSet().scan(oldBucketKey, options);
for (ZSetOperations.TypedTuple<String> tuple : scanResult.getContent()) {
String userId = tuple.getValue();
double score = tuple.getScore();
if (score <= lowerBucket.getMaxScore()) {
redisTemplate.opsForZSet().add(lowerBucketKey, userId, score);
} else {
redisTemplate.opsForZSet().add(upperBucketKey, userId, score);
}
}
cursor = scanResult.getCursor();
} while (cursor != 0);
// 更新分桶緩存
bucketCache.put(lowerBucketKey, lowerBucket);
bucketCache.put(upperBucketKey, upperBucket);
bucketCache.remove(oldBucketKey);
// 刪除舊分桶
redisTemplate.delete(oldBucketKey);
}
}本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/RpSHmksqjCQbLgDUN-7eFQ