GO CountMinSketch计数器(布隆过滤器思想的近似计数器)

简介

CountMinSketch

与布隆过滤器类似，由于它是基于概率的，因此它所统计的计数是有一定概率存在误差的，也就是可能会比真实的计数大。比如一个元素实际的计数是10，但是计算器的计算结果可能比10大。因此适合能够容忍计数存在一定误差的场景，比如社交网络中推文的访问次数。

它一秒能够进行上百万次操作（主要取决于哈希函数的速度），并且如果我们每天有一个长度为100亿的数据流需要进行计数，计数值允许的误差范围是100，允许的错误率是0.1%，计数器大小是32位，只需要7.2GB内存，这完全可以单机进行计数。

二维数组无符号int

每个元素会通过不同的哈希函数映射到每一行的某个位置，并增加对应位置上的计数：

估算计数也是如上图流程，根据哈希映射到每一行的对应位置，然后读取所有行的计数，返回其中最小的一个。

返回最小的一个是因为其他其他元素也可能会映射到自身所映射位置上面，导致计数比真实计数大，因此最小的一个计数最可能是真实计数：

123abc

当然，如果一个元素的每一行的对应位置都被其他元素所映射，那么这个估算的计数就会比真实计数大。

CountMinSketch计数器里面的哈希函数需要是彼此独立且均匀分布（类似于哈希表的哈希函数），而且需要尽可能的快，比如murmur3就是一个很好的选择。

CountMinSketch计数器的性能严重依赖于哈希函数的性能，而一般哈希函数的性能则依赖于输入串（一般为字节数组）的长度，因此为了提高CountMinSketch计数器的性能建议减少输入串的长度。

下面是一个简单的性能测试，单位是字节，可以看到时间的消耗随着元素的增大基本是线性增长的：

数组大小、哈希函数数量、错误范围和错误率之间是互相影响的，如果我们想减少错误率和错误范围，则需要更大的数组和更多的哈希函数。但是我们很难直观的计算出这些参数，还好有两个公式可以帮助我们计算出准确的数值：

数据流大小错误范围错误率数组大小哈希函数数量

map

CountMinSketch

TinyLFU是一个缓存淘汰策略，它里面有LFU策略的思想，LFU是一个基于访问频率的淘汰策略，因此需要统计每个元素被访问的次数。如果对每个元素使用一个独立的计数器，那么这个成本会很大，而且对于一个缓存淘汰策略来说，我们并不需要这个计数器非常大且非常准确。

CountMinSketch

uint8uint16uint32uint642bit4bit6bit

k*m的二维数组counters

我们首先使用上面提到的两个公式计算数组每一行长度和哈希函数的数量，然后初始化哈希函数列表和二维数组。

对于一个元素，我们需要把它根据每个哈希函数计算出它在每一行数组的位置，然后增加对应位置计数器的计数值。

这里需要注意的是，计数值可能会溢出，因此我们首先判断是否溢出，如果溢出则设置为最大值。

同增加计数原理，把元素根据哈希函数映射到每一行数组的对应位置，然后选择所有行中最小的那个计数值。