布隆过滤器简介
布隆过滤器：一种数据结构，是由一串很长的二进制向量组成，可以将其看成一个二进制数组，也称 位数组 初始默认值都是 0
添加数据
当要向布隆过滤器中添加一个元素 key 时，我们通过多个 hash 函数，算出多个值，然后将这些值所在的方格置为 1
判断数据是否存在
同理，通过多个 hash 函数计算出多个值，判断对应值是否为1
-
如果有一个不为 1 那么可以确定该数据一定不存在于这个布隆过滤器中
-
如果全为 1 那么这个数据
不一定存在于这个布隆过滤器中，因为 hash 计算出来的结果又重复的
优缺点
-
优点，占用内存少，插入和查询速度都贼快
-
缺点，随着数据的增加，误判率会增加；无法判断数据一定存在；无法删除数据
如何选择哈希个数和过滤器长度
很显然，过小的布隆过滤器很快所有的 bit 位均为 1，那么查询任何值都会返回“可能存在”，起不到过滤的目的了。布隆过滤器的长度会直接影响误报率，布隆过滤器越长其误报率越小。
另外，哈希函数的个数也需要权衡，个数越多则布隆过滤器 bit 位置位 1 的速度越快，且布隆过滤器的效率越低；但是如果太少的话，那我们的误报率会变高。
k 为哈希函数个数，m 为布隆过滤器长度，n 为插入的元素个数，p 为误报率
如何选择适合业务的 k 和 m 值呢，这里直接贴一个公式：
注意
Redis 因其支持 setbit 和 getbit 操作，且纯内存性能高等特点，因此天然就可以作为布隆过滤器来使用。但是布隆过滤器的不当使用极易产生大 Value，增加 Redis 阻塞风险，因此生成环境中建议对体积庞大的布隆过滤器进行拆分。
拆分的形式方法多种多样，但是本质是不要将 Hash(Key) 之后的请求分散在多个节点的多个小 bitmap 上，而是应该拆分成多个小 bitmap 之后，对一个 Key 的所有哈希函数都落在这一个小 bitmap 上。
附录
- 参考链接：https://zhuanlan.zhihu.com/p/43263751
<?php
/**
* 布隆过滤器:说存在，不一定存在；说不存在，那一定不存在
*
* User: 舒孝元
* Date: 2020/8/19 14:43
* Mail: sxy@shuxiaoyuan.com
* Website: https://www.shuxiaoyuan.com
*/
/**
* 布隆过滤器简介
* 介绍下Bloom Filter的基本处理思路：
* 申请一批空间用于保存0 1信息，再根据一批哈希函数确定元素对应的位置，如果每个哈希函数对应位置的值为全部1，说明此元素存在。
* 相反，如果为0，则要把对应位置的值设置为1。由于不同的元素可能会有相同的哈希值，即同一个位置有可能保存了多个元素的信息，从而导致存在一定的误判率。
* 如果申请空间太小，随着元素的增多，1会越来越多，各个元素冲突的机会越来越来大，导致误判率会越来越大。
* 另外哈希函数的选择及个数上也要平衡好，多个哈希函数虽然可以提供判断的准确性，但是会降低程序的处理速度，而哈希函数的增加又要求有更多的空间来存储位置信息。
*
* Bloom-Filter的应用。
* Bloom-Filter一般用于在大数据量的集合中判定某元素是否存在。
* 例如邮件服务器中的垃圾邮件过滤器。
* 在搜索引擎领域，Bloom-Filter最常用于网络蜘蛛(Spider)的URL过滤，网络蜘蛛通常有一个 URL列表，保存着将要下载和已经下载的网页的URL，
* 网络蜘蛛下载了一个网页，从网页中提取到新的URL后，需要判断该URL是否已经存在于列表中。此时，Bloom-Filter算法是最好的选择。
* 比如说，一个象 Yahoo,Hotmail 和 Gmai 那样的公众电子邮件（email）提供商，总是需要过滤来自发送垃圾邮件的人（spamer）的垃圾邮件。
* 一个办法就是记录下那些发垃圾邮件的 email 地址。由于那些发送者不停地在注册新的地址，全世界少说也有几十亿个发垃圾邮件的地址，将他们都存起来则需要大量的网络服务器。
* 布隆过滤器是由巴顿.布隆于一九七零年提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。我们通过上面的例子来说明起工作原理。
* 假定我们存储一亿个电子邮件地址，我们先建立一个十六亿二进制（比特），即两亿字节的向量，
* 然后将这十六亿个二进制位全部设置为零。对于每一个电子邮件地址 X，我们用八个不同的随机数产生器（F1,F2, ...,F8） 产生八个信息指纹（f1, f2, ..., f8）。
* 再用一个随机数产生器 G 把这八个信息指纹映射到 1 到十六亿中的八个自然数 g1, g2, ...,g8。现在我们把这八个位置的二进制位全部设置为一。
* 当我们对这一亿个 email 地址都进行这样的处理后。一个针对这些 email 地址的布隆过滤器就建成了。（见下图）
* 现在，让我们看看如何用布隆过滤器来检测一个可疑的电子邮件地址 Y 是否在黑名单中。
* 我们用相同的八个随机数产生器（F1, F2, ..., F8）对这个地址产生八个信息指纹 s1,s2,...,s8，
* 然后将这八个指纹对应到布隆过滤器的八个二进制位，分别是 t1,t2,...,t8。如果 Y 在黑名单中，显然，t1,t2,..,t8 对应的八个二进制一定是一。
* 这样在遇到任何在黑名单中的电子邮件地址，我们都能准确地发现。
* 布隆过滤器决不会漏掉任何一个在黑名单中的可疑地址。
* 但是，它有一条不足之处。也就是它有极小的可能将一个不在黑名单中的电子邮件地址判定为在黑名单中，
* 因为有可能某个好的邮件地址正巧对应八个都被设置成一的二进制位。
* 好在这种可能性很小。我们把它称为误识概率。在上面的例子中，误识概率在万分之一以下。
* 布隆过滤器的好处在于快速，省空间。但是有一定的误识别率。常见的补救办法是在建立一个小的白名单，存储那些可能别误判的邮件地址。
*/
namespace App\Http\Controllers\Redis;
use App\Common\BloomFilterHash;
use App\Common\Tools;
use App\Constants\RedisDemo\RedisDemo;
use Illuminate\Http\Request;
use Illuminate\Support\Facades\Redis;
/**
* Redis::setBit 偏移量为 0-2^32-1，所以生成的哈希不能大于 2^32 -1
* Redis::setBit 参考链接 https://redis.io/commands/setbit
* 注意，一旦完成了第一次分配，后续对相同键的SETBIT调用将不会有分配开销。
*
* 该布隆过滤器总位数为2^32位, 判断条数为2^30条. hash函数最优为3个.(能够容忍最多的hash函数个数)
*
* 注意, 在存储的数据量到2^30条时候, 误判率会急剧增加, 因此需要定时判断过滤器中的位为1的的数量是否超过50%, 超过则需要清空.
*/
class RedisBloomFilterController
{
public string $key = RedisDemo::REDIS_BLOOM_FILTER;
/**
* 位图思想，需要用到的哈希算法，一般1~3个就行
*/
private array $hashFunction = ['FNVHash', 'SDBMHash'];
public function __destruct()
{
// 设置 Redis 的过期时间
Redis::EXPIRE($this->key, 24 * 3600);
}
/**
* Description: 简单测试-位图思想
* Author: Shuxiaoyuan
* Email: sxy@shuxiaoyuan.com
* DateTime: 2022/1/11 11:26
*
* @param Request $request
*
* @return array
*/
public function bloomIndex(Request $request): array
{
$key = $this->key;
// 偏移量
$offset = (int)$request->input('offset', 1);
/**
* Redis 最大只支持 0xFFFFFFFF == 4294967295 ≈ 512MB
* 注意：本地上测试的时候，会发现，经常 flash ，原因有以下几点
* 一：Redis配置文件里面设置了最大内存
* 二：本机没那么多空余内存分配
* 三：偏移量太大
*/
$old_status = Redis::setbit($key, $offset, 1);
$new_status = Redis::getbit($key, $offset);
$data = [
'redis_key' => $key,
'offset' => $offset,
'old_status' => $old_status,
'new_status' => $new_status,
];
return Tools::outSuccessInfo($data);
}
/**
* Description: 获取字符串经过哈希算法后的值
* Author: Shuxiaoyuan
* Email: sxy@shuxiaoyuan.com
* DateTime: 2022/1/10 16:12
*
* @param Request $request
*
* @return array
*/
public function getHash(Request $request): array
{
$string = $request->input('string', 'shuxiaoyuan');
// 获取该类所有方法
$rc = new \ReflectionClass(BloomFilterHash::class);
// 默认获取所有，这里只拿静态方法
// 只获取 public 和 static 方法(\ReflectionMethod::IS_STATIC | \ReflectionMethod::IS_PUBLIC)
$reflection_methods = $rc->getMethods(\ReflectionMethod::IS_STATIC);
// dd($reflection_methods); // 返回包含每个方法 ReflectionMethod 对象的数组。
$data['string'] = $string;
foreach ($reflection_methods as $method) {
$name = $method->name;
$data['hash_value'][$method->name] = BloomFilterHash::$name($string);
}
return Tools::outSuccessInfo($data);
}
/**
* Description: 添加一个元素到布隆过滤器
* Author: Shuxiaoyuan
* Email: sxy@shuxiaoyuan.com
* DateTime: 2022/1/10 18:04
*
* @param Request $request
*
* @return array
*/
public function bloomAddOne(Request $request): array
{
$key = $this->key;
$string = $request->input('string', 'shuxiaoyuan');
/**
* Redis 官方提供的布隆过滤器到了 Redis 4.0 提供了插件功能之后才正式登场。
* 布隆过滤器作为一个插件加载到 Redis Server 中，给 Redis 提供了强大的布隆去重功能。
*
* docker pull redislabs/rebloom
* bf.add 只能一次添加一个元素
* bf.madd 可以添加多个 bf.madd test user1 user2 user3 ……
*/
$script = <<<SCRIPT
return redis.call('bf.add', KEYS[1], ARGV[1])
SCRIPT;
$value = Redis::eval($script, 1, $key, $string);
// 采用位图思想
// $value = $this->addOne($key, $string);
$data = [
'redis_key' => $key,
'string' => $string,
'value' => $value,
];
return Tools::outSuccessInfo($data);
}
/**
* Description: 判断一个元素是否存在
* Author: Shuxiaoyuan
* Email: sxy@shuxiaoyuan.com
* Website: https://www.shuxiaoyuan.com
* DateTime: 2023/4/19 16:30
*
* @param Request $request
*
* @return array
*/
public function bloomGetOne(Request $request): array
{
$key = $this->key;
$string = $request->input('string', 'shuxiaoyuan');
/**
* bf.exists 一次只能查询一个
* bf.mexists 一次可以查询多个 bf.mexists test user1 user2 user3 ……
*/
$script = <<<SCRIPT
return redis.call('bf.exists', KEYS[1], ARGV[1])
SCRIPT;
$value = Redis::eval($script, 1, $key, $string);
// 采用位图思想
// $value = $this->exists($key, $string);
$data = [
'redis_key' => $key,
'string' => $string,
'status' => $value,
];
return Tools::outSuccessInfo($data);
}
/**
* Description: 测试误判率1:查找存在的数据
* Author: Shuxiaoyuan
* Email: sxy@shuxiaoyuan.com
* Website: https://www.shuxiaoyuan.com
* DateTime: 2023/4/20 11:07
*
*/
public function test1(Request $request): array
{
set_time_limit(0);
ini_set('memory_limit', '-1M');
$key = $this->key . 'tmp';
$number = (int)$request->input('number', 1000);
$insert = 0;
$exists = 0;
for ($i = 0; $i < $number; $i++) {
$script = <<<SCRIPT
return redis.call('bf.add', KEYS[1], ARGV[1])
SCRIPT;
$insert += Redis::eval($script, 1, $key, 'user' . $i);
$script = <<<SCRIPT
return redis.call('bf.exists', KEYS[1], ARGV[1])
SCRIPT;
// 经过测试，发现百分百无误判
$exists += Redis::eval($script, 1, $key, 'user' . $i);
}
Redis::del($key);
$data = [
'insert' => $insert,
'exists' => $exists,
];
return Tools::outSuccessInfo($data);
}
/**
* Description: 测试误判率2:查找不存在的数据
* Author: Shuxiaoyuan
* Email: sxy@shuxiaoyuan.com
* Website: https://www.shuxiaoyuan.com
* DateTime: 2023/4/20 11:29
*
* @param Request $request
*
* @return array
*/
public function test2(Request $request): array
{
set_time_limit(0);
ini_set('memory_limit', '-1M');
$key = $this->key . 'tmp';
$number = (int)$request->input('number', 1000);
$insert = 0;
$exists = [];
for ($i = 0; $i < $number; $i++) {
$script = <<<SCRIPT
return redis.call('bf.add', KEYS[1], ARGV[1])
SCRIPT;
$insert += Redis::eval($script, 1, $key, 'user' . $i);
$script = <<<SCRIPT
return redis.call('bf.exists', KEYS[1], ARGV[1])
SCRIPT;
// 每次塞入时，肯定是没有 i+1 这个的
$tmp = Redis::eval($script, 1, $key, 'user' . ($i + 1));
if ($tmp) {
// 当数量为 1000 时，误判为:306,310,442,611,741,902
$exists[] = $i;
}
}
Redis::del($key);
$data = [
'insert' => $insert,
'exists' => $exists,
];
return Tools::outSuccessInfo($data);
}
/**
* Description: 测量误判率
* Author: Shuxiaoyuan
* Email: sxy@shuxiaoyuan.com
* Website: https://www.shuxiaoyuan.com
* DateTime: 2023/4/20 11:34
*
* 测量方法：
* 我们先随机出一堆字符串，然后切分为 2 组，
* 将其中一组塞入布隆过滤器，然后再判断另外一组的字符串存在与否，
* 取误判的个数和字符串总量一半的百分比作为误判率。
*/
public function test3(Request $request): array
{
set_time_limit(0);
ini_set('memory_limit', '-1M');
$key = $this->key . 'tmp';
$number = (int)$request->input('number', 1000);
if ($number % 2) {
$number += 1;
}
$half = (int)bcdiv($number, 2);
for ($i = 0; $i < $half; $i++) {
$script = <<<SCRIPT
return redis.call('bf.add', KEYS[1], ARGV[1])
SCRIPT;
Redis::eval($script, 1, $key, 'user' . $i);
}
$count = 0;
for ($i = $half + 1; $i < $number; $i++) {
$script = <<<SCRIPT
return redis.call('bf.exists', KEYS[1], ARGV[1])
SCRIPT;
if (Redis::eval($script, 1, $key, 'user' . $i)) {
$count += 1;
}
}
Redis::del($key);
$data = [
'insert' => $number,
'count' => $count,
'proportion' => bcdiv($count, $half, 8)
];
return Tools::outSuccessInfo($data);
}
/**
* Description: 添加一个元素到布隆过滤器，采用位图实现
* Author: Shuxiaoyuan
* Email: sxy@shuxiaoyuan.com
* DateTime: 2022/1/10 17:27
*
* 这里采用的思想是用的位图实现，将 string 按照一定的 hash 函数计算后，将相应位置1
*
* @param string $string
* @param string $key
*
* @return mixed
*/
private function addOne(string $key, string $string): mixed
{
// 位图最大为 2^32 = 4294967296
$bit = [];
foreach ($this->hashFunction as $function) {
$bit[] = (int)BloomFilterHash::$function($string);
}
$redis_response = Redis::pipeline(function ($pipeline) use ($string, $key) {
foreach ($this->hashFunction as $function) {
$hash = (int)BloomFilterHash::$function($string);
$pipeline->setbit($key, $hash, 1);
}
});
return [
'bit' => $bit,
'redis_response' => $redis_response,
];
}
/**
* Description: 判断元素是否存在，采用位图实现
* Author: Shuxiaoyuan
* Email: sxy@shuxiaoyuan.com
* DateTime: 2022/1/10 17:27
*
* 采用的思想是位图的思想，将 string 按照相同的 hash 函数计算后，取出相应的所有位，依次判断每一位是否为1
*
* @param $string
* @param $key
*
* @return bool
*/
private function exists(string $key, string $string): bool
{
// 采用管道
$dataResponse = Redis::pipeline(function ($pipeline) use ($string, $key) {
$len = strlen($string);
foreach ($this->hashFunction as $function) {
$hash = BloomFilterHash::$function($string, $len);
$pipeline->getBit($key, $hash);
}
});
foreach ($dataResponse as $bit) {
if ($bit == 0) {
return false;
}
}
return true;
}
}