接到一个优化场景：

小程序用户的openid作为最主要的业务查询字段，在做了缓存设计之后仍有非常高频的查询，通过埋点简单统计约在每日1000w次。

其中，由于新增用户、新增矩阵小程序等原因，请求的openid根本不存在MySQL数据库中，这部分统计约占30%左右，也就是约300w次查询是浪费的。

优化的思路也非常简单：布隆过滤（bloom filter）。

它作为非常成熟的方案很适合类似场景，所以使用bloom在查MySQL之前优先判断openid是否存在就可以解决这个问题。

虽然平时对bloom的原理有所了解，但是本次主要的挑战是需要过滤的openid数据集有8亿，具体实施的过程中遇到了很多没有考虑过的细节，因此整理分享一下。

先简单描述一下bloom filter的原理。

布隆过滤器（Bloom Filter）：

具体来说：

当要加入一个元素时，使用多个不同的哈希函数对该元素进行哈希，得到多个哈希值，然后将这些哈希值对应的位数组上的位置值为1。

当查找一个元素时，同样使用多个哈希函数进行哈希，然后查看对应位置上的位：

由于布隆过滤器的判重操作只需对位数组进行一次查找，无需遍历整个集合，因此它的查找效率非常高，并且它所占用的空间相对于集合本身也非常少。

但是，布隆过滤器存在一定的误判率。

对于一个元素，如果多个哈希函数将其映射到的位都已被标记为1，则它可能被误判为存在于集合中，即有一定的假阳性率 。

误判率取决于哈希函数的数量和位向量的长度。

8亿数据集做布隆过滤主要需要规划的问题是：

1）内存占用

说bloom的内存占用前，要来说明一下bloom在redis中的实现：Bitmap。

在Redis中，Bitmap通过字符串来实现，一个字符串可以存储超过2^32个元素，所以一个bloom能存储的最大上限就是2^32个，约42.9亿。

那么在redis底层bitmap 和string 其实是同一个结构，只是提供了不同的命令来进行操作，想要看一个redis 对象占用多少内存可以使用 MEMORY USAGE Key，返回的是字节数：

2）Bitmap内存分配

如上图bitmap操作命令：

setbit  key  index  1 

这里有个需要注意的问题是，如果index比较大，比如在10亿位上写1，那么redis在内存分配时其实是分配了一个完整的10亿长度的数组（10亿位是1，前面的全部补0）。

可以理解为是一个非常长的字符串，而不是下意识我们想象很简单的1个bit那么小，它瞬间分配的内存大概在128M

3）Bitmap读取

既然一个10亿位的bitmap需要128M内存，那么很直接的想法就是，这么大的内存，bitmap读起来会慢吗？

结论当然是不会的。

因为bitmap是一个位数组，它在内存中是连续的，CPU并不需要去读取完整的128M内存，它只要获取到这个数组起始位置，+ index 就可以计算出对应的位置然后进行读取，也就是说，它的时间复杂度是 O(1)

虽然读操作是O(1)的，但是很显然创建一个大的bitmap时是非常重量级的一个操作，布隆过滤的Hash函数计算基本都是32位，64位长度的Hash值

我们无法控制bitmap的增长是一个顺序过程，所以最直接的办法就是控制最大长度

4）分片 -- Roaring Bitmap

目前openid数据总量已经有8亿+，肯定不能都放入一个Bitmap中，这样就会有个非常大的key，最简单的优化方向就是分片。

Roaring Bitmap (RBM)就是类似的算法，RBM 的主要思想并不复杂，简单来讲，有如下三条：

用计算器按一下，就可以直观地理解这个例子了：

821697800 对应的 16 进制数为 30FA1D08， 其中高 16 位为 30FA， 低16位为 1D08。

找到数值为 30FA 的容器（如果该容器不存在，则新建一个）。

这里用 Bitmap 做存储，找到了相应的容器后，看一下低 16 位的数值 1D08，它相当于是 7432，因此在 Bitmap 中找到相应的位置，将其置为 1 即可。 

5）实现取高位和低位代码

$container = $hash >> 16;

$index     = $hash & 0xFFFF;

做一个git演示，可以看到821697800转换为二进制后，通过位移取值，可以一次一次移，也可以一次移16位。

总结一下，Roaring Bitmap 先取高16位做桶，是为了做分片，取低16位做index，主要是为了压缩Bitmap长度，达到节省内存的作用。

6）Hash函数规划

已知openid 8亿，按照预留一倍空间规划，这个布隆过滤器总量为20亿，通过RBM分片分散到2^16 = 65525 个container中，也就是每个container承担3w个元素，这样取低16位长度就不太够了。

我们可以取低17位，这样一个container可以存储13w个，我们期望的误差率为千分之一，那么可以通过布隆计算公式得出需要的Hash函数个数，这里我们直接利用ChatGPT计算就好了：

得出需要15个哈希函数，其实按照公式算出来这个值还是有待论证，我对它的存疑是这样的：

15个哈希函数，3w个元素，如果不考虑哈希冲突，也就是有15*3w = 45w，而一个container的总长度才13w，真的能满足千分之一的误差率吗？

我去验证了，答案是不能。

45w次hash结果存入一个container中，大多数的位都存满了1，导致误差率高达50%以上。

那么问题出在哪里？没有深究这个公式是如何推导出来的，就用最朴素的方法去尝试了多种条件下的测试。

得出的结论是：元素n *哈希个数k ，不能超过位图长度m（或者超过太多）， 在这个基础上，公式推导的结论是可靠的。

7）继续思考 

既然65535个container不能满足需要，那可选的方案就只有继续扩大bitmap长度或者是扩大container数量。

最终用的方案是扩大一倍container数量，也就是取高17位作为container，公式推导需要10个hash，最终也验证了这个结果是对的。

得出了hash个数之后，就需要找一些具体的hash函数，这里贴一些搜集到的hash算法和具体实现的代码：

8）Redis key数量对性能是否有影响

既然选择了扩大container数量，紧接着需要思考的问题是：

选择增大key数量会对redis性能有影响吗？

Redis把所有的key都放在了一个字典当中，它的查询时间复杂度是O(1)，所以基本上key的数量对于读写操作是不影响的，可以看下Redis 键空间示意图：

但是也不是说 Redis 中key过多完全没有影响，它更主要的会影响到备份的效率，特别是启动一个RDB 备份 Process时，key的数量过多会影响RDB的执行效率，而负责数据读取和备份是两个线程，并不影响。

总结：只是多了6w的key而已，对Redis来说还是很小case的，相对于可能形成的大key造成的影响，还是简单的多加点key吧。

在整个实战的过程中，非常大的一个难点是数据集很大，想要验证一遍非常耗时，那么提升redis写入性能就非常重要，所以一开始就想到了使用批处理的方式。

    $redis->multi()    ->set('key1', 'val1')    ->get('key1')    ->set('key2', 'val2')    ->get('key2')    ->exec();

但是这里有一个细节， $redis->multi() 支持两种模式，

默认是使用Redis::MULTI，但它们的作用和使用方式略有不同：

总结：

虽然Multi 功能更强，但是相对的执行效率也慢（当然还是要比单个命令执行要快的，节省了很多网络io时间），而pipeline模式的性能要比Multi快50倍 （ 这个基准测试是以100w次 setbit操作测试的）。

按照pipeline模式下8亿openid * 10 hash  = 20个小时来算，如果用multi，我可能要跑一个月。

选对批处理模式，对于大批量数据导入相当重要。