Redis 命令及数据类型 -- CMS(Count-Min Sketch)

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

摘要

Count-Min Sketch

  • Count-Min Sketch（CMS） 用于在极低内存占用下，对高频写入的计数型数据进行近似统计，非常适合流量、事件、关键词等“只关心频次规模、不要求精确值”的场景。

  • Count-Min Sketch 是一种基于哈希的概率型计数结构，用于估算元素出现次数，具有以下核心特征：

    • 只会高估，不会低估（over-estimation）
    • 固定内存，与元素种类数无关
    • O(1) 的更新与查询复杂度
    • 不支持删除（或只能近似删除）
    • 只能返回给定元素近似统计其频次，而无法返回全部元素的统计频次

  • 基本工作原理（简化版）

1
2
3
4
5
6
1.初始化一个二维数组 counter[d][w]
2.对每个元素 x：
    a. 通过 d 个哈希函数映射到 d 行中的 w 个位置
    b. 对对应的 d 个计数器全部 +1
3.查询元素 x 的频次：
    a.取这 d 个计数器的 最小值(取最小值是为了尽量抵消哈希冲突带来的“多加”)

注意下图中的数组不是二进制的，每次映射都会+1

  • 误差与空间复杂度

维度 说明
误差上界 ≤ ε × 总插入次数
错误概率 ≤ δ
空间复杂度 O(1 / ε × log(1 / δ))
查询复杂度 O(d)
更新复杂度 O(d)

结论：数据量再大，内存不增长，代价是“精度换空间”

RedisBloom 中 CMS 的核心命令

创建 CMS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 按底层维度初始化
# CMS.INITBYDIM key width depth
# 参数说明
# width (w)：每一行的桶数（影响误差）
# depth (d)：哈希函数数量（影响冲突概率）
# 比如：
CMS.INITBYDIM page:view 1000 10
# 输出
OK

# 验证类型
type page:view
# 返回值
CMSk-TYPE

# 按误差+容量初始化
# CMS.INITBYPROB page:view error probability
# 参数说明
# error (ε)：误差上界
# probability (δ)：超过误差上界的概率，这个数字越接近零，每个项目的内存消耗就越大，每次操作的CPU使用就越多。
# RedisBloom 会自动换算 w 和 d
# 比如：
CMS.INITBYPROB key 0.001 0.01
参数 数值 说明
error 0.001 最大相对误差 ε = 0.1%
probability 0.01 只有 1% 的概率超过该误差

增加计数

1
2
3
4
5
6
# CMS.INCRBY key item1 count1 item2 count2 ...
CMS.INCRBY page:view home 1 about 1 home 1
# 输出
1) (integer) 1
2) (integer) 1
3) (integer) 2

查询计数

1
2
3
4
5
6
# CMS.QUERY key item1 item2 ...
CMS.QUERY page:view home about
# 返回的是 估算值（可能偏大）
# 输出
1) (integer) 2
2) (integer) 1

合并 CMS

1
2
3
4
5
6
7
8
9
# CMS.MERGE dest numkeys src1 src2 ... WEIGHTS w1 w2 ...
# 参数说明
# dest：目标 CMS，必须存在
# numkeys：源 CMS 数量
# src1 src2 ...：源 CMS，必须存在
# WEIGHTS w1 w2 ...：源 CMS 权重
CMS.MERGE page:view 2 page:view:1 page:view:2 WEIGHTS 1 1
# 输出
OK

获取 CMS 的信息

1
2
3
4
5
6
7
8
9
# CMS.INFO key
CMS.INFO page:view
# 输出
1) width            # 每一行桶数 w
2) (integer) 1000
3) depth            # 哈希函数数量 d
4) (integer) 10
5) count            # 当前已插入的元素数量
6) (integer) 3

CMS 的使用场景

场景1：网站PV统计

  • 需求：统计网站 PV，即页面被访问的次数，允许0.1%的误差

1
2
3
4
5
6
7
8
# 初始化 CMS
CMS.INITBYPROB page:pv 0.001 0.01
# 添加计数
CMS.INCRBY page:pv /home 1 /about 1
CMS.INCRBY page:pv /home 1

# 查询计数
CMS.QUERY page:pv /home

场景2：接口调用频次限流前置统计

  • 需求：统计接口调用次数，为限流提供已经，不需要精准计数，允许0.1%的误差

1
2
3
4
5
6
# 创建 CMS
CMS.INITBYPROB api:limit 0.001 0.01
# 添加计数
CMS.INCRBY api:limit /api/user/list 1
# 获取计数
CMS.QUERY api:limit /api/user/list