用CMS实现redis热key采集
背景
之前其实已经看过了非常多种的热key算法，自己也用space-saving实现过一套proxy上的热key收集和缓存。但是最近看到的CMS算法，我觉得也非常好，时间复杂度低，原理清晰简单，空间消耗也是常数。
CMS算法的全称叫Count-Min Sketch，redis的开源module布隆过滤器RedisBloom就是基于它实现的统计元素的使用计数。
Count-Min Sketch
核心原理
基于哈希函数和二维数组（矩阵），通过多个哈希函数将元素映射到二维数组的不同位置，并对对应位置的计数器进行累加，以此来估算元素的频率。
具体逻辑
- 数据结构：假设有 d 个哈希函数h1, h2 … hd ，以及一个大小为w*d的二维数组（计数器矩阵） C 。这里 w 表示每个哈希函数映射的桶（bucket）的数量， d 表示哈希函数的个数。
- 元素计数：当一个元素 x 出现时，分别通过 d 个哈希函数计算其在二维数组中的位置。即对于第 i 个哈希函数hi，计算hi(x) ，得到一个在 0 到 w 之间的索引值，然后将矩阵 C 中第 i 列、索引值对应的位置的计数器加 1 ，也就是 (C[i][hi(x)]++) 。
- 频率估算：当需要估算元素 x 的出现频率时，分别计算 d 个哈希函数映射位置的计数器值，取其中的最小值作为元素 x 出现频率的近似值。
时间窗口优化
- 划分时间窗口(1s、5s)，每个新窗口开始时，重置 Count - Min Sketch 矩阵，并重新开始计数。假设窗口长度为 T 秒，某个键在上一个窗口中的计数为 count，则其 QPS 为 count / T。
讨论
优势
- 内存高效：只需要存储一个大小固定的二维数组和少量的哈希函数，占用的内存空间小。
- 快速计算：对元素的计数和频率估算操作的时间复杂度低，均为 O(d) ，可以实时处理大量的元素
局限
- 个人感觉就是哈希桶的数量不太好确定。且计算哈希函数不能太慢，但一般密码算法都不算快。
- 估算误差：由于哈希冲突的存在，对元素频率的估算结果可能会高估实际频率。
内存占用
- O (d×w)，其中 d 是哈希函数的数量，w 是每个哈希函数对应的桶数量。
- 例如：d 个哈希函数 × 4 字节 int 计数器 × w 个桶 ：4 × 4 × 10000 = 160,000B ≈ 156.25KB.
具体实现方式
- 对于某个统计时间窗口，当发现热key时，可以直接用字典来保存当前热key的【key->次数】的映射
- 对于历史数据统计，可以采用lru，比如使用双向链表+字典来实现，比如每个统计时间窗口到达时，倾倒当前的热key字典到lru结构中。
- 历史数据记录保持多久有一个时间窗口，可以定期遍历lru双向链表来清理过期的热key历史数据。