布隆过滤器是一种概率数据结构,用于高效判断元素是否可能存在于大数据集中。本文将深入探讨布隆过滤器的工作原理、应用场景以及其实现细节。介绍如何使用PHP+Redis实现布隆过滤器,并评估其性能表现。
英文名称Bloom Filter,用于判断一个元素是否在一个大数据集合中,如果检测到存在则有可能存在,如果不存在则一定不存在。
Redis官网对于布隆过滤器的说明:https://redis.io/docs/data-types/probabilistic/bloom-filter/
布隆过滤器的查询时间复杂度是常数(很快)级别的,通常记为 O(k),其中 k 是哈希函数的个数,也是布隆过滤器中每个元素对应的位数组位置数量。
我用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
这种方式不需要考虑对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 14504 0.7 0.6 52432 6580 ? Ssl 23:17 0:00 /usr/local/redis/bin/redis-server 0.0.0.0:6379
root 14549 0.0 0.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 1000000 | 100万条数据允许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) 1 |
BF.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_percentage float 误差百分比
* @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_name string 布隆过滤器名称
* @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_name string 布隆过滤器名称
* @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_name string 布隆过滤器名称
* @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_name string 布隆过滤器名称
* @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'));
//[1, 1, 1]
var_dump($bloom_filter->mAdd('key', ['v2', 'v3', 'v4']));
//1
var_dump($bloom_filter->exists('key', 'v100'));
//[1, 1, 0]
var_dump($bloom_filter->mExists('key', ['v2', 'v3', 'v5']));
看起来这个性能很高,足以应对99%的场景了,使用MySQL测试一亿条数据中定值查找1条数据,需要278.71秒的搜索时间。
对于与布隆过滤器,在一亿条数据下进行一亿次查找:
动作 | 数量 | 配置误差值(百分比) | 实测误差数量 | 消耗时间(秒) |
---|---|---|---|---|
mAdd,批量写入操作 | 100000000 | 0.01% | / | 357.068 |
mExists,批量读取操作 | 100000000 | 0.01% | 5103 | 306.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[key] = 1
,PHP数组的底层实现是哈希表,通过数组的下标,可以直接找到对应的内存地址,所以时间复杂度是O(1),而不是O(n)。
Redis::get(get flash_sale . 用户id) > 10
的判断,如果要查数据库,redis就Redis::incr(flash_sale . 用户id)
,直到超过指定次数,然后上游直接拦截。先看预设场景,看看要不要做处理:商品被删除,MySQL无数据,布隆过滤器有数据。
此时会发现,如果redis缓存仍旧有商品信息,还会有问题,解决方案:
hIncrBy(bloom_filter_flash_sale, 取模后的数字哈希位置, 1)
,如果大于1,可以去查询数据库,做个兜底的判断策略。这个面试题老生常谈,所以在这里着重提一嘴。
会出现在搜索引擎的爬虫判断中,爬虫爬过了,就不在重复爬取了,
可以用布隆过滤器。
4G = 34359738368Bit,340亿的比特,如果设置3种哈希算法,也就意味着占用150亿个比特位,还是能存的下。
1.节省空间,2.增加查询速度。
源数据可能偏大,通过哈希函数转换后,结果成数字,这个数字就是比特数组的下标。布隆过滤器可以近似的理解为维护的是一个所有值都为数字的PHP索引数组,但是数组的占用单位是字节,而布隆过滤器可以使用更小的比特,充分利用设备存储资源。
算法:普通开发者缺少算法思维,做出来的布隆过滤器概率不可控,或者容易冲突。为了防止哈希函数的值转化为数字后位数过长(例如md5(1) 为c4ca4238a0b923820dcc509a6f75849b,转10进制是261578874264819908609102035485573088411),需要对数据长度进行取模,不取模还好,取模后极大减少了布隆过滤器的长度。例如10000条数据,设定3种哈希算法,设置3万个比特位,取模后的值大多小于3万,所以冲突的概率增加了很多。
理解深度:可能一部分开发者不知道Redis位图,或者为什么用哈希函数,还挺停留在用Redis string做判断的基础上,虽然能实现,但是占用空间有很大差距。
不同的输入数据,经过哈希计算后得到相同的输出值。
例如32位输出的md5算法,一共有1632 ≈ 3.4 ×1038种值,但是宇宙空间里的信息量却无穷的多,输入数据无穷多但输出数据有限,这就导致哈希碰撞的产生。
算法生成的信息越长,碰撞概率越低,这是个概率问题,不是一定发生或一定不发生。
本文被 PHP编程 专题收录