发帖
翼度科技»论坛 › 编程开发 › PHP › 查看内容

深入理解PHP+Redis实现布隆过滤器（亿级大数据处理和黑客攻防必备）

捷哥哥

2

主题

2

帖子

6

积分

新手上路

Rank: 1

积分
6
显示全部楼层
布隆过滤器

极简概括

英文名称Bloom Filter，用于判断一个元素是否在一个大数据集合中，如果检测到存在则有可能存在，如果不存在则一定不存在。
Redis官网对于布隆过滤器的说明：https://redis.io/docs/data-types/probabilistic/bloom-filter/
使用场景


  • 防止缓存穿透：用于快速判断某个商品数据是否存在于缓存中，如果存在，则执行下游流程，如果不存在，在此处直接拦截，避免下游流程引发的算力消耗，很适合对抗黑客刷接口的行为。
  • 网络爬虫：在爬取网页时，可以用布隆过滤器来判断一个 URL 是否已经被访问过，从而避免重复爬取相同的页面。
  • 拼写检查器：用于快速检查一个单词是否是正确拼写的，减少不必要的词典查询。
  • 用户名防重：注册或者更改某些应用的用户名时，提示用户名已存在，再超大数据量的情况下，可以用布隆过滤器替代MySQL去抗。
  • 整体来说，适用于读多写少的场景，如果是写多读少，不推荐用布隆过滤器。
优点


  • 节省空间：用比特位来存储，比用一个字节存储0和1更加节省空间。
  • 插入查询迅速：布隆过滤器内部使用位数组（bit array）来表示数据存储状态，这种结构使得在查询时只需对位数组进行一系列简单的位操作，而不需要遍历。
  • 保密性很好：Redis BitMap里存储的都是0和1，就算黑客拿到了数据，缺少代码逻辑，也根本不知道是干啥的。
缺点


  • 不支持删除：强制没问题，不支持删除是为了防止哈希碰撞引起的误删问题。一个哈希值，可能是多个源数据的转换后的结果。
  • 误判：本来一个数据不存在与这个集合当中，但是它判断数据时存在这个集合当中，这是由哈希碰撞产生的，这种无法避免，只能减少误判的概率。 所以布隆过滤器有个特点：不存在一定不存在，存在却不一定存在。
  • 避免：可以添加多个不同的的hash函数算法和bit位的长度，从而降低误判的发生，会降低性能，这需要在性能和误判之间做好权衡。
时间复杂度

布隆过滤器的查询时间复杂度是常数（很快）级别的，通常记为 O(k)，其中 k 是哈希函数的个数，也是布隆过滤器中每个元素对应的位数组位置数量。
原理


  • 存储：判断一个元素是否在一个大数据集合中，存在就是1不存在就是0，这个集合可以由一个二进制向量（向量 === 矢量，有大小有方向）表示（二进制向量，可以类比成一个数组，但是每个单位只能存储1比特的数据），用Redis的BitMap结构存储最合适。
  • 哈希转换：一般会有多个哈希算法，为了减少哈希冲突的概率。
  • 长度选择：布隆过滤器哈希位的大小，要看业务场景所使用数据的上限。
  • 判断规则：例如4条数据存储，有3个哈希算法，也就占用12个bit。判断任意一个数据是否存在，也就在bitmap上判断3个值，如果这3个值全部都在，则表示可能存在这个数据，如果小于3，则表示数据不存在。
用PHP写Redis布隆过滤器扩展

我用CRC32算法作为哈希运算写了一个，存储是用Redis的BitMap，算法数量设置到3，误差率达到了25.69%，设置到10，误差率仍有1.08%，性能降下来了，难怪网上有人评论不要手动实现布隆过滤器。受一些算法限制，写不了太好的方案。
同时在网上寻找更好的方案，发现网上的一些哈希算法报错，所以也不用。
寻找composer包，目前也没有找到太好的视线布隆过滤器的方案，不是不支持Redis，就是版本太旧，不支持PHP8。
所以需要考虑其它方向的解决方案。
  1. /**
  2. * @ 封装一个布隆过滤器类，切勿商用，否则要出事
  3. */
  4. class BloomFilter {
  5.     //redis对象
  6.     private $redis;
  7.     //布隆过滤器名称
  8.     private $bloom_filter_name;
  9.     //比特数量
  10.     private $bit_num;
  11.     //函数数量
  12.     private $func_num;
  15.     /**
  16.      * @function 初始化成员属性
  17.      * @param    $redis             object redis对象
  18.      * @param    $bloom_filter_name string 布隆过滤器名称
  19.      * @param    $bit_num           int    比特数量
  20.      * @param    $func_num          int    哈希函数数量
  21.      * @return   void
  22.      */
  23.     public function __construct($redis, $bloom_filter_name, $bit_num, $func_num) {
  24.         $this->redis             = $redis;
  25.         $this->bloom_filter_name = $bloom_filter_name;
  26.         $this->bit_num           = $bit_num;
  27.         $this->func_num          = $func_num;
  28.     }
  31.     /**
  32.      * @function 向布隆过滤器中添加数据
  33.      * @param    $val string 待添加的值
  34.      * @return   array
  35.      */
  36.     public function add($val) {
  37.         //开启管道，方便批量操作
  38.         $pipe = $this->redis->multi();
  40.         //模拟多个哈希算法
  41.         for ($i = 0; $i < $this->func_num; $i++) {
  42.             $hash = $this->hash($val . '_' . $i);
  43.             $pipe->setbit($this->bloom_filter_name, $hash, 1);
  44.         }
  46.         return $pipe->exec();
  47.     }
  50.     /**
  51.      * @function 布隆过滤器判断某个值是否存在
  52.      * @param    $val string 待添加的值
  53.      * @return   bool
  54.      */
  55.     public function exists($val) {
  56.         //开启管道，方便批量操作
  57.         $pipe = $this->redis->multi();
  59.         for ($i = 0; $i < $this->func_num; $i++) {
  60.             $hash = $this->hash($val . '_' . $i);
  61.             $pipe->getbit($this->bloom_filter_name, $hash);
  62.         }
  64.         //批处理
  65.         $results = $pipe->exec();
  66.         foreach ($results as $bit) {
  67.             if ($bit == 0) {
  68.                 return false;
  69.             }
  70.         }
  72.         return true;
  73.     }
  76.     /**
  77.      * @function 通过一些CRC32哈希算法，获取指定值的BitMap存储位置
  78.      * @param    $string string 待计算哈希的数据
  79.      * @return   int
  80.      */
  81.     private function hash($string) {
  82.         //因为crc32算法获取的是9~10位数字，方便取模
  83.         return crc32($string) % $this->bit_num;
  84.     }
  85. }
  87. //----------------------------------------------------------------------------------------------------
  88. $redis = new Redis();
  89. $redis->connect('127.0.0.1', 6379);
  91. $bloom_filter = new BloomFilter($redis, "test_key",10000, 3);
  93. $bloom_filter->add('xyz');
  95. var_dump($bloom_filter->exists('xyz')); //true
  96. var_dump($bloom_filter->exists('abc')); //false
复制代码
用C语言实现Redis布隆过滤器扩展（服务端）

这种方式不需要考虑对Redis位图的操作，而是直接调用Redis Bloom Filter的功能，所以实现思路与上文说明有所不同。
  1. Redis扩展安装官方扩展：https://redis.io/docs/data-types/probabilistic/configuration
  2. Redis Bloom Filter地址：https://github.com/RedisBloom/RedisBloom
  4. 目前的最新版本是2.6.12，但是编译报错，用2.2.18就好了
  5. wget https://github.com/RedisBloom/RedisBloom/archive/refs/tags/v2.2.18.tar.gz
  6. tar zxvf v2.2.18.tar.gz
  7. cd RedisBloom-2.2.18
  8. make
  9. 此时会生成一个redisbloom.so
  10. mkdir /usr/local/redis/ext/
  11. mv redisbloom.so /usr/local/redis/ext/redis_bloom_filter.so
  12. vim /usr/local/redis/etc/redis.conf中添加如下一行
  13. loadmodule /usr/local/redis/ext/redis_bloom_filter.so
  14. 保存
  15. 重启Redis，我这里设置了Redis服务
  16. service redis restart
  17. 查看是否启动
  18. > ps aux | grep redis
  19. root      14504  0.7  0.6  52432  6580 ?        Ssl  23:17   0:00 /usr/local/redis/bin/redis-server 0.0.0.0:6379
  20. root      14549  0.0  0.1 112828   996 pts/0    S+   23:17   0:00 grep --color=auto redis
  22. 进入redis命令行，使用命令查看扩展是否安装成功
  23. redis-cli
  24. bf.exists bloom_filter_key test_val
  25. 返回0表示安装成功
复制代码
常见指令：
指令含义示例备注BF.RESERVE配置多少数量下有多大误差，误差越小性能越差BF.RESERVE 布名 0.001 1000000100万条数据允许0.1%的误差BF.ADD向某个布隆过滤器中添加数据BF.ADD 布名 值1返回1证明插入成功BF.EXISTS判断某个布隆过滤是否存在一个值BF.EXISTS 布名 值1返回1说明存在，返回0说明不存在BF.MADD向某个布隆过滤器中插入多个值BF.MADD 布名 值2 值3 值4返回
1) (integer) 1
2) (integer) 1
3) (integer) 1BF.MEXISTS判断某个布隆过滤是否存在多个值BF.MEXISTS 布名 值2 值3 值5返回
1) (integer) 1
2) (integer) 1
3) (integer) 0注意：使用这个插件，值是MBbloom--类型的，而不是位图或者其它类型。
自己封装了一个类，如下：
  1. class BloomFilter {
  2.     //存放redis对象
  3.     private $redis;
  6.     /**
  7.      * @function 初始化Redis对象
  8.      * @param    $bloom_filter_name string 布隆过滤器名称
  9.      * @param    $num               int 要存储多少数据
  10.      * @param    $error_percentage  float 误差百分比
  11.      * @return   void
  12.      */
  13.     public function __construct($bloom_filter_name, $num, $error_percentage) {
  14.         $redis = new Redis();
  15.         $redis->connect('192.168.0.180', 6379);
  16.         $redis->rawCommand('BF.RESERVE', $bloom_filter_name, bcdiv($error_percentage, 100, 8), $num);
  17.         $this->redis = $redis;
  18.     }
  21.     /**
  22.      * @function 向布隆过滤器中添加数据
  23.      * @param    $bloom_filter_name  string 布隆过滤器名称
  24.      * @param    $val                string 要添加的数据
  25.      * @return   int
  26.      */
  27.     public function add($bloom_filter_name, $val) {
  28.         return $this->redis->rawCommand('BF.ADD', $bloom_filter_name, $val);
  29.     }
  32.     /**
  33.      * @function 布隆过滤器判断指定的值是否存在
  34.      * @param    $bloom_filter_name  string 布隆过滤器名称
  35.      * @param    $val                string 要添加的数据
  36.      * @return   int
  37.      */
  38.     public function exists($bloom_filter_name, $val) {
  39.         return $this->redis->rawCommand('BF.EXISTS', $bloom_filter_name, $val);
  40.     }
  43.     /**
  44.      * @function 向布隆过滤器中批量添加数据
  45.      * @param    $bloom_filter_name  string 布隆过滤器名称
  46.      * @param    $vals               array  要添加的数据
  47.      * @return   int
  48.      */
  49.     public function mAdd($bloom_filter_name, $vals) {
  50.         $args = array_merge(['BF.MADD'], [$bloom_filter_name], $vals);
  51.         return $this->redis->rawCommand(...$args);
  52.     }
  55.     /**
  56.      * @function 布隆过滤器批量判断指定的值是否存在
  57.      * @param    $bloom_filter_name  string 布隆过滤器名称
  58.      * @param    $vals               array  要添加的数据
  59.      * @return   array
  60.      */
  61.     public function mExists($bloom_filter_name, $vals) {
  62.         $args = array_merge(['BF.MEXISTS'], [$bloom_filter_name], $vals);
  63.         return $this->redis->rawCommand(...$args);
  64.     }
  65. }
  67. //调用-----------------------------------
  68. $bloom_filter = new BloomFilter('key',100000, 0.01);
  70. //1 重复插入返回0
  71. var_dump($bloom_filter->add('key', 'v100'));
  72. //[1, 1, 1]
  73. var_dump($bloom_filter->mAdd('key', ['v2', 'v3', 'v4']));
  74. //1
  75. var_dump($bloom_filter->exists('key', 'v100'));
  76. //[1, 1, 0]
  77. var_dump($bloom_filter->mExists('key', ['v2', 'v3', 'v5']));
复制代码
Redis布隆过滤器性能与误差实测

看起来这个性能很高，足以应对99%的场景了，使用MySQL测试一亿条数据中定值查找1条数据，需要278.71秒的搜索时间。
对于与布隆过滤器，在一亿条数据下进行一亿次查找：
动作数量配置误差值（百分比）实测误差数量消耗时间（秒）mAdd，批量写入操作1000000000.01%/357.068mExists，批量读取操作1000000000.01%5103306.646
  1. 批量写入示例代码：
  2. $bloom_filter = new BloomFilter('test_key',100000000, 0.01);
  4. $start = microtime(true);
  5. for($i = 0; $i < 100000000; $i++) {
  6.     $arr[] = $i;
  7.     if(count($arr) > 100000) {
  8.         $bloom_filter->mAdd('test_key', $arr);
  9.         $arr = [];
  10.     }
  11. }
  12. echo microtime(true) - $start;
  15. 批量读取示例代码：
  16. $bloom_filter = new BloomFilter('test_key',100000000, 0.01);
  18. $arr = [];
  19. $int = 0;
  21. $start = microtime(true);
  22. for($i = 0; $i < 100000000; $i++) {
  23.     $arr[] = uniqid();
  24.     if(count($arr) > 100000) {
  25.         $exists = $bloom_filter->mExists('test_key', $arr);
  26.         $arr = [];
  27.         foreach($exists as $v) {
  28.             if($v) {
  29.                 $int++;
  30.             }
  31.         }
  32.     }
  33. }
  34. echo microtime(true) - $start;
  36. echo "--";
  37. echo $int;
复制代码
常见问题

为什么布隆过滤器不用遍历每条数据

在海量的数据下遍历会很耗时，因此不能用遍历，寻址过程可以理解为PHP的数组利用下标方式去找到对应的值，查看是0还是1，相当于于array[key] = 1，PHP数组的底层实现是哈希表，通过数组的下标，可以直接找到对应的内存地址，所以时间复杂度是O(1)，而不是O(n)。
使用布隆过滤器防止缓存穿透


  • 缓存穿透：常见于抢购场景的黄牛，他们为了牟利，利用脚本不断拼接新参数去频繁请求接口。从服务器角度来说，如果Redis内存不存在，就会往数据库中查，大量查询任务直接穿透了Redis，压力打到了数据库，就会给数据库带来很大的压力。
  • 就有3种解决方案：

    • 通过异常行为做拦截：抢购一般会让用户登录， 让服务器知道谁在抢购，如果单位时间内Redis被穿透的次数过多，直接封禁。思路：上游添加Redis::get(get flash_sale . 用户id) > 10的判断，如果要查数据库，redis就Redis::incr(flash_sale . 用户id)，直到超过指定次数，然后上游直接拦截。
    • 如果没有查到数据，也在缓存中存储，值为1即可，但是这有2个弊端，1是缓存过后可能用不上，2是大量的缓存，也会增加存储的负担。
    • 使用布隆过滤器：上文有讲，把他放到业务逻辑的上游做判断，如果过滤器中存在，则走下游流程，如果不存在，则直接阻断其后续流程。

如何减少布隆过滤器误判的概率


  • 增加哈希函数的数量：1个哈希函数算法可能会冲突，多个与源数据进行哈希算法，就能减少冲突的发生。
  • 增加布隆过滤器的长度：例如10个比特槽位，存1000条数据，大概率有冲突的情况，但是将长度增加到2000，这就能减少冲突概率的发生。
抢购场景商品被删除了，如何同步到布隆过滤器

先看预设场景，看看要不要做处理：商品被删除，MySQL无数据，布隆过滤器有数据。

  • 如果redis缓存无商品数据：
    通过布隆过滤器->缓存无数据->查数据库->无数据->返回商品信息不存在。
  • 如果redis缓存仍旧有商品信息：
    通过布隆过滤器->缓存有->其它下单流程。
此时会发现，如果redis缓存仍旧有商品信息，还会有问题，解决方案：

  • 可以异步重建布隆过滤器：这和定期刷新缓存一个道理，防止缓存的长期不一致。
  • 维护一个计数布隆过滤器：表示该位置被几个数据进行了引用，如果是1，直接删了就行。这个可以用hash去实现hIncrBy(bloom_filter_flash_sale, 取模后的数字哈希位置, 1)，如果大于1，可以去查询数据库，做个兜底的判断策略。
50亿量级的URL集合，如何再4G的内存中判断其中一个url是否在这个集合当中

这个面试题老生常谈，所以在这里着重提一嘴。
会出现在搜索引擎的爬虫判断中，爬虫爬过了，就不在重复爬取了，
可以用布隆过滤器。
4G = 34359738368Bit，340亿的比特，如果设置3种哈希算法，也就意味着占用150亿个比特位，还是能存的下。
布隆过滤器为什么用哈希函数而不是源数据

1.节省空间，2.增加查询速度。
源数据可能偏大，通过哈希函数转换后，结果成数字，这个数字就是比特数组的下标。布隆过滤器可以近似的理解为维护的是一个所有值都为数字的PHP索引数组，但是数组的占用单位是字节，而布隆过滤器可以使用更小的比特，充分利用设备存储资源。
为什么不推荐自定义写布隆过滤器

算法：普通开发者缺少算法思维，做出来的布隆过滤器概率不可控，或者容易冲突。为了防止哈希函数的值转化为数字后位数过长（例如md5(1) 为c4ca4238a0b923820dcc509a6f75849b，转10进制是261578874264819908609102035485573088411），需要对数据长度进行取模，不取模还好，取模后极大减少了布隆过滤器的长度。例如10000条数据，设定3种哈希算法，设置3万个比特位，取模后的值大多小于3万，所以冲突的概率增加了很多。
理解深度：可能一部分开发者不知道Redis位图，或者为什么用哈希函数，还挺停留在用Redis string做判断的基础上，虽然能实现，但是占用空间有很大差距。
补充

哈希运算


  • 极简概括：哈希运算是通过一些算法，将任意长度的任意格式的二进制数据转换为固定长度数据的过程。
  • 算法举例：sha1、sha256、sha512、md5。
  • 算法特点：

    • 结果确定：给定相同的输入，哈希函数会产生相同的输出。
    • 长度确定：无论输入的大小如何，输出的长度是固定的。
    • 计算迅速：好的哈希函数可在合理的时间内对输入进行哈希计算。
    • 不可逆向：给一个哈希过后的值，由于初始数据信息丢失，无法通过这个值还原初始的信息。彩虹表并不是还原，而是对比。
    • 修改敏感：修改数据的任何一个地方，就算很小的改动，也会导致算出来的哈希值完全不同。

哈希碰撞

不同的输入数据，经过哈希计算后得到相同的输出值。
例如32位输出的md5算法，一共有1632 ≈ 3.4 ×1038种值，但是宇宙空间里的信息量却无穷的多，输入数据无穷多但输出数据有限，这就导致哈希碰撞的产生。
算法生成的信息越长，碰撞概率越低，这是个概率问题，不是一定发生或一定不发生。

来源:https://www.cnblogs.com/phpphp/p/18122907
免责声明：由于采集信息均来自互联网，如果侵犯了您的权益，请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容，谢谢合作！

上一篇: 万字详解PHP+Sphinx中文亿级数据全文检索实战（实测亿级数据0.1秒搜索耗时

下一篇: php使用swoole实现TCP服务

发表于 2024-4-9 19:36:41

举报 回复 使用道具

返回列表 发新帖

Archiver|手机版|小黑屋|翼度科技

Copyright © 2001-2020, Tencent Cloud.　Powered by Discuz! X3.4