需求:从 1TB 搜索日志中高效找出搜索量最高的 10 个关键词。
核心挑战:数据量过大,无法直接加载到内存中处理。
分片数 = 1000 → 每个分片文件约 1GB(1TB ÷ 1000)
关键词 K → hash(K) % 1000 → 写入对应分片文件 输出示例:
chunk_1.sorted:
("keyword1", 10000)
("keyword2", 9800)
... 双堆协作:
堆类型 | 作用 | 容量 |
|---|---|---|
最大堆 | 提取各分片的当前最大值 | 分片数量 |
最小堆 | 维护全局 Top 10(堆顶为第10大值) | 固定10个 |
1、初始化:将每个分片文件的第一个关键词(最大值)加入最大堆。
2、循环提取:
2.1 从最大堆取出当前全局最大值(关键词 K, 次数 C)。
2.2 若最小堆未满,直接加入;否则,若 C > 堆顶值则替换。
2.3 若 C ≤ 堆顶值,且最小堆已满,提前终止(后续值更小)。
2.4 从 K 所属分片读取下一个关键词,更新最大堆。
3、输出结果:最小堆中的关键词即为全局 Top 10。
Redis的ZSET(有序集合)是实现排行榜的理想数据结构,但当分数相同时,默认会按字典序排序。要实现同分按时间排序,需要特殊设计。以下是完整方案:
# 添加/更新成员分数
ZADD leaderboard 100 user1
ZADD leaderboard 95 user2
# 获取排名(从高到低)
ZREVRANK leaderboard user1
# 获取前10名
ZREVRANGE leaderboard 0 9 WITHSCORES原理:将时间戳作为分数的小数部分
# 分数 = 原始分数 + (1 - 时间戳归一化值)
# 假设时间戳是13位(毫秒),最大时间戳设为9999999999999(可调整)
# 计算组合分数公式:
组合分数 = 原始分数 * 1e13 + (1e13 - 时间戳)
# Lua脚本示例
local score = tonumber(ARGV[1])
local timestamp = tonumber(ARGV[2])
local combined_score = score * 1e13 + (1e13 - timestamp)
redis.call('ZADD', KEYS[1], combined_score, ARGV[3])public void addToLeaderboard(String key, String member, double score) {
long timestamp = System.currentTimeMillis();
// 保证时间戳不超过12位(可根据需要调整)
long maxTimestamp = 999999999999L;
long normalizedTimestamp = Math.min(timestamp, maxTimestamp);
// 组合分数 = 原始分数 * 1e13 + (1e13 - 时间戳)
double combinedScore = score * 1e13 + (1e13 - normalizedTimestamp);
jedis.zadd(key, combinedScore, member);
}# 主ZSET存储原始分数
ZADD leaderboard:main 100 user1
# 为每个分数创建时间排序的ZSET
ZADD leaderboard:score:100 1620000000000 user1
ZADD leaderboard:score:100 1620000000001 user2
# 查询时需要两步操作:
# 1. 先获取分数段
ZSCORE leaderboard:main user1
# 2. 再按时间获取同分排名
ZREVRANGE leaderboard:score:100 0 -1 WITHSCORESLUA脚本:
-- KEYS[1]: 排行榜key
-- ARGV[1]: 原始分数
-- ARGV[2]: 用户ID
-- 返回: 1-成功
local score = tonumber(ARGV[1])
local timestamp = tonumber(ARGV[2] or redis.call('TIME')[1])
local member = ARGV[3]
-- 组合分数计算
local max_timestamp = 9999999999999
timestamp = math.min(timestamp, max_timestamp)
local combined_score = score * 1e13 + (1e13 - timestamp)
redis.call('ZADD', KEYS[1], combined_score, member)
return 1java:
@Service
public class LeaderboardService {
@Autowired
private StringRedisTemplate redisTemplate;
private static final long MAX_TIMESTAMP = 9999999999999L;
// 添加/更新排行榜
public void addToLeaderboard(String leaderboardKey, String member, double score) {
long timestamp = System.currentTimeMillis();
double combinedScore = calculateCombinedScore(score, timestamp);
redisTemplate.opsForZSet().add(
leaderboardKey,
member,
combinedScore
);
}
// 获取排行榜(分页)
public List<Ranking> getLeaderboard(String leaderboardKey, int page, int size) {
long start = (page - 1) * size;
long end = start + size - 1;
Set<ZSetOperations.TypedTuple<String>> tuples =
redisTemplate.opsForZSet().reverseRangeWithScores(leaderboardKey, start, end);
return tuples.stream()
.map(t -> {
double combinedScore = t.getScore();
double originalScore = Math.floor(combinedScore / 1e13);
long timestamp = (long)(1e13 - (combinedScore % 1e13));
return new Ranking(
t.getValue(),
originalScore,
timestamp,
redisTemplate.opsForZSet().reverseRank(leaderboardKey, t.getValue()) + 1
);
})
.collect(Collectors.toList());
}
private double calculateCombinedScore(double score, long timestamp) {
long normalizedTimestamp = Math.min(timestamp, MAX_TIMESTAMP);
return score * 1e13 + (1e13 - normalizedTimestamp);
}
@Data
@AllArgsConstructor
public static class Ranking {
private String member;
private double score;
private long timestamp;
private long rank;
}
}
方案 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|
组合分数 | 查询效率高(O(logN)),单次操作 | 分数范围受限制,需要预留位数 | 大多数场景 |
二级排序 | 精确控制,不损失原始分数精度 | 查询需要多次操作,维护复杂 | 分数精度要求高的场景 |
批量操作:使用pipeline批量更新排行榜
数据分片:对大型排行榜按分数段分片
冷热分离:将历史数据归档到其他ZSET
缓存策略:缓存前N名的结果
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。