Redis 命令及数据类型 -- TopK

发表于 分类于 ， 置顶 精品
阅读次数： 本文字数： 1.3k 阅读时长 ≈ 5 分钟

摘要

TopK

  • TopK，专门用于解决 “在海量数据流中，实时找出最热门的 N 个元素” 这一类问题

  • Top-K 属于流式重频（Heavy Hitters）算法家族，其目标不是记录所有元素，而是：

    • 在受限内存下，持续维护出现频率最高的 K 个元素

  • TopK 的核心特性

1
2
3
4
5
固定容量：只维护 K 个元素
近似统计：计数可能略有误差
自动淘汰：低频元素会被踢出
写入极快：适合高 QPS
内存稳定：与数据规模无关

  • RedisBloom 的 TopK 内部使用 CMS 作为频次估算基础，并结合堆+淘汰策略来维护热点集合。

    • CMS: 参考 Redis 命令及数据类型 -- CMS(Count-Min Sketch)
    • 堆+淘汰策略: TopK 在内部如何决定谁能进入 TopK、谁必须被踢出 TopK 的一整套机制。
      • 堆：TopK 使用一个最小堆来维护 TopK 元素，TopK 维护 K 个候选元素，堆顶永远是 当前 TopK 中频次最低的那个
      • 淘汰策略：TopK 使用一个 LRU 缓存来记录最近访问的元素，当 TopK 元素数量达到上限时，将 LRU 缓存中的元素逐个加入 TopK，并更新 TopK 元素的频率。
      • 一句话：当新元素的估算频次超过当前最弱的那个时，就把弱者淘汰掉，让新元素进榜。

当一个新元素到来时，我该不该让它进入 TopK？

  • 下面是 TopK 在 TOPK.ADD 时的真实逻辑抽象

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Step 1：更新 CMS（不存 item，只更新计数器）
CMS.increment(item)

# Step 2：item 是否在 TopK 显式集合中？
if item in TopK:
    # 重新平衡堆位置
    update_heap(item)
    return

# Step 3：TopK 是否未满？
if TopK.size < K:
    TopK.insert(item)
    return

# Step 4：比较 CMS 估算值
freq_new = CMS.query(item)
freq_min = CMS.query(TopK.min_item)

if freq_new > freq_min:
    TopK.evict_min()
    TopK.insert(item)
else:
    # 什么都不做
    pass

TopK 的应用场景

问题 TopK 是否适合
当前访问量最高的 URL ✅
搜索热词 Top 10 ✅
商品点击榜 ✅
所有商品的点击次数 ❌
精确计数 ❌

RedisBloom TopK 的核心命令

创建 TopK

  • 使用 TopK 前必须先创建 TopK

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# TOPK.RESERVE key topk [width depth decay]
# 参数说明
# key: 键名
# topk: 存储的元素数量，即统计的前 K 个元素
# width: 内部CMS 的宽度，默认 8
# depth: 内部CMS 的深度，默认 7
# decay: 衰减因子（0 ~ 1），默认 0.9

# 示例
# 含义：维护访问量最高的 100 个 URL，允许历史热度逐渐衰减。
TOPK.RESERVE topk:urls 100 2000 7 0.9
# 返回值
OK

# 验证类型
type topk:urls
# 返回值
TopK-TYPE

添加元素

1
2
3
4
5
6
7
# TOPK.ADD key items [items ...]
# 示例
# 含义：添加元素 "a" 和 "b" 到 TopK 中
TOPK.ADD topk:urls a b
# 返回值，被挤出 TopK 的元素（如果有）
1) (nil)
2) (nil)

增加元素的频率

1
2
3
4
5
6
# TOPK.INCRBY key item increment [item increment ...]
# 示例
# 含义：将元素 "a" 的频率增加 1
TOPK.INCRBY topk:urls a 1
# 输出结果
1) (nil)

查询元素是否在 TopK 中

1
2
3
4
5
6
# TOPK.QUERY key item [item ...]
# 示例
# 含义：查询元素 "a" 是否在 TopK 中
TOPK.QUERY topk:urls a
# 返回值
1) (integer) 1 # 1 表示元素 "a" 在 TopK 中，0 表示元素 "a" 不在 TopK 中

获取 TopK 中的元素

1
2
3
4
5
6
7
8
9
10
11
# TOPK.LIST key [WITHCOUNT]
# 参数说明
# WITHCOUNT: 是否返回每个元素出现的次数，默认不返回
# 示例
# 含义：获取 TopK 中的元素，并返回每个元素出现的次数
TOPK.LIST topk:urls WITHCOUNT
# 输出结果
1) "a"
2) (integer) 2
3) "b"
4) (integer) 1

获取近似计数

1
2
3
4
5
6
# TOPK.COUNT key item [item ...]
# 示例
# 含义：获取元素 "a" 的近似计数
TOPK.COUNT topk:urls a
# 输出结果
1) (integer) 2

查看TopK 的状态

1
2
3
4
5
6
7
8
9
10
11
12
13
# TOPK.INFO key
# 示例
# 含义：查看 TopK 的状态
TOPK.INFO topk:urls
# 输出结果
1) k                    # topk 的大小
2) (integer) 100
3) width                # 内部 CMS 的宽度
4) (integer) 2000
5) depth                # 内部 CMS 的深度
6) (integer) 7
7) decay                # 衰减因子
8) "0.9"

TopK 的衰减（decay）参数怎么理解

  • decay 用于解决一个问题：“老热点永远霸榜，新热点上不来”

decay 行为
1.0 永不衰减（全历史统计）
0.9 越老的数据权重越低
0.5 热点更新非常快

  • 经验值：

    • 实时热点：0.8 ~ 0.9
    • 长周期榜单：0.95 ~ 1.0

CMS 和 TopK 组合使用场景

📌场景1： 实时热搜榜（最经典组合）

  • 需求：统计所有搜索词频次（CMS），同时实时出TOP10热搜（TOPK），既知热度又能排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 1. 初始化CMS（统计全量搜索词计数，误差0.001）
cms.initbyprob search_count 0.001 0.01

# 2. 初始化TOPK（取TOP10热搜）
topk.reserve search_top10 10

# 3. 用户搜索核心操作（2命令必一起执行）
# 搜索"周杰伦"，CMS计数+1，同时录入TOPK（自动累加热度）
cms.incrby search_count 周杰伦 1
topk.incrby search_top10 周杰伦 1

cms.incrby search_count 原神 1
topk.incrby search_top10 原神 1
cms.incrby search_count 周杰伦 1  # 重复搜索，双端同步+1
topk.incrby search_top10 周杰伦 1

# 4. 核心查询：先取TOP10，再查精准计数（组合核心）
# 第一步：取TOP10热搜列表
topk.list search_top10  # 返回：周杰伦、原神...

# 第二步：查热搜词精准近似计数（CMS比TOPK.count更准）
cms.query search_count 周杰伦  # 返回2（精准）
topk.count search_top10 周杰伦  # 参考值，优先用CMS结果

# 5. 辅助查询：判断词是否在热搜榜
topk.query search_top10 周杰伦  # 1=在，0=不在