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

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

布隆过滤器

极简概括

英文名称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。
所以需要考虑其它方向的解决方案。
/**
* @ 封装一个布隆过滤器类,切勿商用,否则要出事
*/
class BloomFilter {
    //redis对象
    private $redis;
    //布隆过滤器名称
    private $bloom_filter_name;
    //比特数量
    private $bit_num;
    //函数数量
    private $func_num;


    /**
   * @function 初始化成员属性
   * @param    $redis             object redis对象
   * @param    $bloom_filter_name string 布隆过滤器名称
   * @param    $bit_num         int    比特数量
   * @param    $func_num          int    哈希函数数量
   * @return   void
   */
    public function __construct($redis, $bloom_filter_name, $bit_num, $func_num) {
      $this->redis             = $redis;
      $this->bloom_filter_name = $bloom_filter_name;
      $this->bit_num         = $bit_num;
      $this->func_num          = $func_num;
    }


    /**
   * @function 向布隆过滤器中添加数据
   * @param    $val string 待添加的值
   * @return   array
   */
    public function add($val) {
      //开启管道,方便批量操作
      $pipe = $this->redis->multi();

      //模拟多个哈希算法
      for ($i = 0; $i < $this->func_num; $i++) {
            $hash = $this->hash($val . '_' . $i);
            $pipe->setbit($this->bloom_filter_name, $hash, 1);
      }

      return $pipe->exec();
    }


    /**
   * @function 布隆过滤器判断某个值是否存在
   * @param    $val string 待添加的值
   * @return   bool
   */
    public function exists($val) {
      //开启管道,方便批量操作
      $pipe = $this->redis->multi();

      for ($i = 0; $i < $this->func_num; $i++) {
            $hash = $this->hash($val . '_' . $i);
            $pipe->getbit($this->bloom_filter_name, $hash);
      }

      //批处理
      $results = $pipe->exec();
      foreach ($results as $bit) {
            if ($bit == 0) {
                return false;
            }
      }

      return true;
    }


    /**
   * @function 通过一些CRC32哈希算法,获取指定值的BitMap存储位置
   * @param    $string string 待计算哈希的数据
   * @return   int
   */
    private function hash($string) {
      //因为crc32算法获取的是9~10位数字,方便取模
      return crc32($string) % $this->bit_num;
    }
}

//----------------------------------------------------------------------------------------------------
$redis = new Redis();
$redis->connect('127.0.0.1', 6379);

$bloom_filter = new BloomFilter($redis, "test_key",10000, 3);

$bloom_filter->add('xyz');

var_dump($bloom_filter->exists('xyz')); //true
var_dump($bloom_filter->exists('abc')); //false用C语言实现Redis布隆过滤器扩展(服务端)

这种方式不需要考虑对Redis位图的操作,而是直接调用Redis Bloom Filter的功能,所以实现思路与上文说明有所不同。
Redis扩展安装官方扩展:https://redis.io/docs/data-types/probabilistic/configuration
Redis Bloom Filter地址:https://github.com/RedisBloom/RedisBloom

目前的最新版本是2.6.12,但是编译报错,用2.2.18就好了
wget https://github.com/RedisBloom/RedisBloom/archive/refs/tags/v2.2.18.tar.gz
tar zxvf v2.2.18.tar.gz
cd RedisBloom-2.2.18
make
此时会生成一个redisbloom.so
mkdir /usr/local/redis/ext/
mv redisbloom.so /usr/local/redis/ext/redis_bloom_filter.so
vim /usr/local/redis/etc/redis.conf中添加如下一行
loadmodule /usr/local/redis/ext/redis_bloom_filter.so
保存
重启Redis,我这里设置了Redis服务
service redis restart
查看是否启动
> ps aux | grep redis
root      145040.70.6524326580 ?      Ssl23:17   0:00 /usr/local/redis/bin/redis-server 0.0.0.0:6379
root      145490.00.1 112828   996 pts/0    S+   23:17   0:00 grep --color=auto redis

进入redis命令行,使用命令查看扩展是否安装成功
redis-cli
bf.exists bloom_filter_key test_val
返回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--类型的,而不是位图或者其它类型。
自己封装了一个类,如下:
class BloomFilter {
    //存放redis对象
    private $redis;


    /**
   * @function 初始化Redis对象
   * @param    $bloom_filter_name string 布隆过滤器名称
   * @param    $num               int 要存储多少数据
   * @param    $error_percentagefloat 误差百分比
   * @return   void
   */
    public function __construct($bloom_filter_name, $num, $error_percentage) {
      $redis = new Redis();
      $redis->connect('192.168.0.180', 6379);
      $redis->rawCommand('BF.RESERVE', $bloom_filter_name, bcdiv($error_percentage, 100, 8), $num);
      $this->redis = $redis;
    }


    /**
   * @function 向布隆过滤器中添加数据
   * @param    $bloom_filter_namestring 布隆过滤器名称
   * @param    $val                string 要添加的数据
   * @return   int
   */
    public function add($bloom_filter_name, $val) {
      return $this->redis->rawCommand('BF.ADD', $bloom_filter_name, $val);
    }


    /**
   * @function 布隆过滤器判断指定的值是否存在
   * @param    $bloom_filter_namestring 布隆过滤器名称
   * @param    $val                string 要添加的数据
   * @return   int
   */
    public function exists($bloom_filter_name, $val) {
      return $this->redis->rawCommand('BF.EXISTS', $bloom_filter_name, $val);
    }


    /**
   * @function 向布隆过滤器中批量添加数据
   * @param    $bloom_filter_namestring 布隆过滤器名称
   * @param    $vals               array要添加的数据
   * @return   int
   */
    public function mAdd($bloom_filter_name, $vals) {
      $args = array_merge(['BF.MADD'], [$bloom_filter_name], $vals);
      return $this->redis->rawCommand(...$args);
    }


    /**
   * @function 布隆过滤器批量判断指定的值是否存在
   * @param    $bloom_filter_namestring 布隆过滤器名称
   * @param    $vals               array要添加的数据
   * @return   array
   */
    public function mExists($bloom_filter_name, $vals) {
      $args = array_merge(['BF.MEXISTS'], [$bloom_filter_name], $vals);
      return $this->redis->rawCommand(...$args);
    }
}

//调用-----------------------------------
$bloom_filter = new BloomFilter('key',100000, 0.01);

//1 重复插入返回0
var_dump($bloom_filter->add('key', 'v100'));
//
var_dump($bloom_filter->mAdd('key', ['v2', 'v3', 'v4']));
//1
var_dump($bloom_filter->exists('key', 'v100'));
//
var_dump($bloom_filter->mExists('key', ['v2', 'v3', 'v5']));Redis布隆过滤器性能与误差实测

看起来这个性能很高,足以应对99%的场景了,使用MySQL测试一亿条数据中定值查找1条数据,需要278.71秒的搜索时间。
对于与布隆过滤器,在一亿条数据下进行一亿次查找:
动作数量配置误差值(百分比)实测误差数量消耗时间(秒)mAdd,批量写入操作1000000000.01%/357.068mExists,批量读取操作1000000000.01%5103306.646批量写入示例代码:
$bloom_filter = new BloomFilter('test_key',100000000, 0.01);

$start = microtime(true);
for($i = 0; $i < 100000000; $i++) {
    $arr[] = $i;
    if(count($arr) > 100000) {
      $bloom_filter->mAdd('test_key', $arr);
      $arr = [];
    }
}
echo microtime(true) - $start;


批量读取示例代码:
$bloom_filter = new BloomFilter('test_key',100000000, 0.01);

$arr = [];
$int = 0;

$start = microtime(true);
for($i = 0; $i < 100000000; $i++) {
    $arr[] = uniqid();
    if(count($arr) > 100000) {
      $exists = $bloom_filter->mExists('test_key', $arr);
      $arr = [];
      foreach($exists as $v) {
            if($v) {
                $int++;
            }
      }
    }
}
echo microtime(true) - $start;

echo "--";
echo $int;常见问题

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

在海量的数据下遍历会很耗时,因此不能用遍历,寻址过程可以理解为PHP的数组利用下标方式去找到对应的值,查看是0还是1,相当于于array = 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】 我们会及时删除侵权内容,谢谢合作!
页: [1]
查看完整版本: 深入理解PHP+Redis实现布隆过滤器(亿级大数据处理和黑客攻防必备)