文章目录
一、写在前面
官方中文文档：https://redis.ac.cn/docs/latest/develop/data-types/probabilistic/top-k/
Top-K 是一种概率数据结构，允许您查找数据流中最常见的项目。
Top K 是 Redis 开源版中的一种概率数据结构，用于估计数据流中排名最高的 K 个元素。
在此语境中，“排名最高”是指“附加有最高数字或分数的元素”，其中分数可以是该元素在流中出现的次数计数，因此该数据结构非常适合查找流中出现频率最高的元素。一个非常常见的应用是检测网络异常和 DDoS 攻击，Top K 可以回答以下问题：来自同一地址或同一 IP 的请求流量是否突然增加？
确实，它与 Count-Min Sketch 的功能存在一些重叠，但这两种数据结构有其差异，应应用于不同的用例。
Redis 开源版对 Top-K 的实现基于 Gong Junzhi 等人提出的 HeavyKeepers 算法。它摒弃了一些旧方法，如“全部计数”和“全部接受部分计数”，转而采用“指数衰减计数”策略，该策略对小流量（mouse flow）有偏向性，而对大流量（elephant flow）影响有限。此实现结合使用两种数据结构：一个哈希表，用于存储概率计数（很像 Count-Min Sketch）；一个最小堆，用于存储计数最高的 K 个项目。这确保了比以往的概率算法更高的准确性和更短的执行时间，同时将内存使用量保持在 Sorted Set 通常所需的一小部分。它还有一个额外的好处，即当元素添加到或从 Top K 列表中移除时，能够获得实时通知。
1、使用场景
热门话题标签（社交媒体平台、新闻分发网络）
在过去 X 小时内，人们提及最多的 K 个话题标签是什么？
今天阅读/查看次数最高的 K 条新闻是什么？
数据流是指传入的社交媒体帖子，您可以从中解析出不同的话题标签。
TOPK.LIST 命令的时间复杂度为 O(K*log(k))，因此如果 K 很小，则无需保留所有话题标签的单独集合或有序集合。您可以直接从 Top K 本身查询。
二、使用
1、TOPK.RESERVE 初始化
# 语法
#topk: 要保留的出现频率最高项目的数量。
#width: 每个数组中保留的计数器数量。（默认值 8）
#depth: 数组数量。（默认值 7）
#decay: 已占用桶中计数器减少的概率。它会对其计数器进行幂运算 (decay ^ bucket[i].counter)。因此，随着计数器值的升高，减少的几率会降低。（默认值 0.9）
TOPK.RESERVE key topk [width depth decay]
# 示例
redis> TOPK.RESERVE topk 50 2000 7 0.925
OK
2、TOPK.ADD 添加一次
向数据结构添加一个项。可以一次添加多个项。如果一个项进入 Top-K 列表，则返回被逐出的项。这允许动态检测进入或逐出 Top-K 列表的热门项。
# 语法
TOPK.ADD key items [items ...]
redis> TOPK.ADD topk foo bar 42
1) (nil)
2) baz
3) (nil)
3、TOPK.COUNT (已弃用) 返回计数
返回项的计数。可以同时请求多个项。请注意，此数字永远不会高于实际计数，并且很可能低于实际计数。
此命令已被弃用。计数并非项出现次数的代表性值。
# 语法
TOPK.COUNT key item [item ...]
# 示例
redis> TOPK.COUNT topk foo 42 nonexist
1) (integer) 3
2) (integer) 1
3) (integer) 0
4、TOPK.INCRBY 带增量分数添加
按增量增加数据结构中项目的分数。可以一次增加多个项目的分数。如果某个项目进入 Top-K 列表，则返回被逐出的项目。
# 语法
# increment：当前项目分数的增量。增量必须大于或等于 1。增量限制为 100,000，以避免服务器冻结。
# 返回值：如果元素被从 TopK 列表中移除，则返回 简单字符串回复 (Simple string reply)，否则返回 空回复 (Nil reply)。
TOPK.INCRBY key item increment [item increment ...]
redis> TOPK.INCRBY topk foo 3 bar 2 42 30
1) (nil)
2) (nil)
3) foo
5、TOPK.INFO 查看信息
返回所需项目数 (k)、宽度、深度和衰减值。
# 语法
TOPK.INFO key
# 示例
TOPK.INFO topk
1) k
2) (integer) 50
3) width
4) (integer) 2000
5) depth
6) (integer) 7
7) decay
8) "0.92500000000000004"
6、TOPK.LIST 查询Top K 列表
注意，这个列表只返回topk列表
# 语法
# WITHCOUNT: 返回每个元素 (或更少) 的计数。
TOPK.LIST key [WITHCOUNT]
# 所有元素
TOPK.LIST topk
1) foo
2) 42
3) bar
# 带有计数的所有元素
TOPK.LIST topk WITHCOUNT
1) foo
2) (integer) 12
3) 42
4) (integer) 7
5) bar
6) (integer) 2
7、TOPK.QUERY 检查元素
检查元素是否属于 Top-K 元素之一。可以同时检查多个元素。
# 语法
TOPK.QUERY key item [item ...]
# 示例
redis> TOPK.QUERY topk 42 nonexist
1) (integer) 1
2) (integer) 0
三、实战
1、示例
# 1、创建一个保留5个TopK数量的集合
127.0.0.1:6379> TOPK.RESERVE top 5 2000 7 0.925
OK
# 2、存放六个元素，我们发现，存第六个的时候，会将原来数量最少的元素从TopK踢出（如果数量一样可能随机踢出）
127.0.0.1:6379> TOPK.ADD top A B C D E F
1) (nil)
2) (nil)
3) (nil)
4) (nil)
5) (nil)
6) "C"
# 3、此时查看TopK，只能查出5个，并且按照数量倒序排序
127.0.0.1:6379> TOPK.LIST top
1) "E"
2) "F"
3) "D"
4) "A"
5) "B"
# 4、将之前踢出的C加上，发现C的排序上来了，因为C是2了
127.0.0.1:6379> TOPK.ADD top A C
1) (nil)
2) "E"
127.0.0.1:6379> TOPK.LIST top
1) "A"
2) "C"
3) "F"
4) "B"
5) "D"
# 5、将E添加两次，E又上来了
127.0.0.1:6379> TOPK.ADD top E E
1) "F"
2) (nil)
127.0.0.1:6379> TOPK.LIST top
1) "E"
2) "A"
3) "C"
4) "B"
5) "D"