PHP实现Bitmap的探索 - GMP扩展使用

一、背景

公司当前有一个用户群的系统，核心功能是根据不同的条件组去不同的业务线中get符合条件的uid列表，然后存到redis中的bitmap中。

举个🌰，如果一个用户群中有两个用户: 3和7，即[3,7]，用bitmap表示那就是：00010001

最后利用redis提供的bitOp命令: bitOp AND \ bitOp XOR \ bitOp OR对各个条件组对应的uid列表bitmap做交并差集计算，得出最终的用户群并存储到redis bitmap中。

二、问题

对于上面描述的系统，如果用户群人数较多的那我们就需要执行较多次的setBit {uid} 1命令，而且如果用户群中的第一个uid是一个特别大的值比如10亿的话，就可能会一次malloc 1000000000/1024/1024/8 ~= 120M的内存，这可能会导致redis卡住一段时间，在高并发的redis实例上执行这个操作是相当危险的。而且可以预想到对于两个较大的bitmap key执行bitOp也是非常消耗CPU的，应该尽量避免在存储型的redis实例中做这种十分消耗CPU的计算操作。

实际上内存最少只能申请一个字节，即8位，所以上面的计算方式稍有出入，但相差并不大。

三、解决方案

针对上述的问题，可以将bitmap的计算挪到应用程序中来，只将最终统计出来的bitmap存储到redis中即可。 如果最终结果用户群中的第一个uid是一个特别大的值的话，可以先set 1K再设置2K..3K…这样缓存的增加bitmap的大小避免redis卡住。

四、PHP实现Bitmap

由于该系统目前是使用的PHP，所以下面记录下PHP实现Bitmap的”心路历程“。

由于要操作PHP变量的某一位，所以就要借助位运算来实现，但是又由于PHP的位运算只能作用在整型数上，所以我们无法使用字符串或者浮点数来实现，所以最先考虑的就是使用整型数组来实现。

为什么是数组呢？因为在64位机器上一个整型变量最多只能使用64位，又由于PHP的整型是有符号的，所以最高位无法供我们使用，所以一个整型变量能存储的最大的uid就是63，这真是太鸡肋了-_-||，所以只能搞个用多个整型变量了实现了。

OK，到此为止貌似找到一个看起来不错的解决方案。但是我们再思考这样一个问题：假设我们系统中最大的uid是63x100万=3.6千万（*对主流互联网公司来说这很正常吧😸*），那为了存储所有uid，我们需要1百万个整数才行，即我们需要一个拥有1百万个元素的数组，那么如果我在进程中制造了一个这样的数组会占用多少内存呢？会是64 * 1百万 / 1024 / 1024 / 8 ~= 7.6M吗？答案是否定的，因为php数组是由HashTable实现的，这是一个复杂的结构体，除了数组元素占用的内存外，还有其他的占用。（这里先不做展开，有兴趣可以自行查看下php数组的实现） 眼见为实：

<?php
ini_set('memory_limit','4G');
$arr = [];
for ($i = 0; $i < 64 * 1000000; $i++)
{
    $arr[] = PHP_INT_MAX;
}

echo "done\n";
while(1){
}

查看内存占用

可以看到大概是1.5G，比我们上面预计的大的多,这太可怕了，必须优化下我们的内存占用，才能真正在生产环境中使用。

这里需要提一句，我的机器只有8G，所以程序可能会用到swap分区，而ps命令结果中的RSS不统计swap分区的占用，在我实际实现中发现ps结果中RSS一列显示占用的内存会随着时间慢慢减少，但是我的程序中arr变量占用的内存是不可能被回收的，所以推测是物理内存中占用的部分内存被置换到了swap分区中。如果你要进行这个实验的话建议关闭swap分区，这样你能得到一个更准确的结果。

五、继续优化

基于上面的经验，如果我们要占用尽可能小的内存，那我们必须能够操作一段近乎无限长的内存且不能产生其他额外占用才可以。幸运的是PHP给我们提供了这样一个扩展：GMP，这个扩展可以让我们使用一个任意长度的整数。OK现在我们拥有了获得一块连续的内存而不会产生其他额外占用的手段，再写一段代码使用下并验证下内存占用情况：

<?php

$gmp = gmp_init(0);
gmp_setbit($gmp, 64 * 1000000, true);
echo "done\n";
while(1){}

Awesome，这次只使用了15M的内存。更加兴奋的是这个扩展提供了诸如：gmp_and、gmp_or、gmp_xor这样进行位运算的函数，极大的方便了我们的使用。

到此为止我们似乎找到了一个完美的解决方案，但是真的完美吗？No！其实还可以再优化一下，想象下如果我们有一个用户群，里面只有一个uid：64000000（表示为数组的话就是：[64000000]），为了存储这个用户我们需要占用7.6M内存，而这个用户群中仅仅只有一个元素，这真是极大的浪费啊！

为了优化这个问题可以拥抱上面被我们唾弃的数组😸，一个大的bitmap拆分为一个个小bitmap的数组，这一个个小的bitmap我们限制大小为1Kw位。

回到上面的问题，如果我们要存储[64000000]这个用户群的话只需要在数组的第6个元素中设置一个little bitmap: 1即可。这样我们就由一开始的占用7.6M内存优化为了占用1位内存。

OK，到此为止我们找到一个还不错的解决方案😸。

后言

为了在Mac中安装GMP扩展又耗费了很多时间，当然，这又是另外一个故事了。有时间我会分享Mac中安装GMP扩展的过程中我遇到的问题。

参考资料

1. GNU Multiple Precision
2. Process Memory Management in Linux
3. 从源码看 PHP 7 数组的实现