发表于 分类于

背景

之前其实已经看过了非常多种的热key算法，自己也用space-saving实现过一套proxy上的热key收集和缓存。但是最近看到的CMS算法，我觉得也非常好，时间复杂度低，原理清晰简单，空间消耗也是常数。

CMS算法的全称叫Count-Min Sketch，redis的开源module布隆过滤器RedisBloom就是基于它实现的统计元素的使用计数。

Count-Min Sketch

核心原理

基于哈希函数和二维数组（矩阵），通过多个哈希函数将元素映射到二维数组的不同位置，并对对应位置的计数器进行累加，以此来估算元素的频率。

具体逻辑

  1. 数据结构：假设有 d 个哈希函数h1, h2 … hd ，以及一个大小为w*d的二维数组（计数器矩阵） C 。这里 w 表示每个哈希函数映射的桶（bucket）的数量， d 表示哈希函数的个数。
  2. 元素计数：当一个元素 x 出现时，分别通过 d 个哈希函数计算其在二维数组中的位置。即对于第 i 个哈希函数hi，计算hi(x) ，得到一个在 0 到 w 之间的索引值，然后将矩阵 C 中第 i 列、索引值对应的位置的计数器加 1 ，也就是 (C[i][hi(x)]++) 。
  3. 频率估算：当需要估算元素 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.

具体实现方式

  1. 对于某个统计时间窗口，当发现热key时，可以直接用字典来保存当前热key的【key->次数】的映射
  2. 对于历史数据统计，可以采用lru，比如使用双向链表+字典来实现，比如每个统计时间窗口到达时，倾倒当前的热key字典到lru结构中。
  3. 历史数据记录保持多久有一个时间窗口，可以定期遍历lru双向链表来清理过期的热key历史数据。