布隆過濾器 極簡概括 英文名稱Bloom Filter,用於判斷一個元素是否在一個大數據集合中,如果檢測到存在則有可能存在,如果不存在則一定不存在。 Redis官網對於布隆過濾器的說明:https://redis.io/docs/data-types/probabilistic/bloom-filt ...
布隆過濾器
極簡概括
英文名稱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 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']));
Redis布隆過濾器性能與誤差實測
看起來這個性能很高,足以應對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記憶體不存在,就會往資料庫中查,大量查詢任務直接穿透了Redis,壓力打到了資料庫,就會給資料庫帶來很大的壓力。
- 就有3種解決方案:
- 通過異常行為做攔截:搶購一般會讓用戶登錄, 讓伺服器知道誰在搶購,如果單位時間內Redis被穿透的次數過多,直接封禁。思路:上游添加
Redis::get(get flash_sale . 用戶id) > 10
的判斷,如果要查資料庫,redis就Redis::incr(flash_sale . 用戶id)
,直到超過指定次數,然後上游直接攔截。 - 如果沒有查到數據,也在緩存中存儲,值為1即可,但是這有2個弊端,1是緩存過後可能用不上,2是大量的緩存,也會增加存儲的負擔。
- 使用布隆過濾器:上文有講,把他放到業務邏輯的上游做判斷,如果過濾器中存在,則走下游流程,如果不存在,則直接阻斷其後續流程。
- 通過異常行為做攔截:搶購一般會讓用戶登錄, 讓伺服器知道誰在搶購,如果單位時間內Redis被穿透的次數過多,直接封禁。思路:上游添加
如何減少布隆過濾器誤判的概率
- 增加哈希函數的數量: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種值,但是宇宙空間里的信息量卻無窮的多,輸入數據無窮多但輸出數據有限,這就導致哈希碰撞的產生。
演算法生成的信息越長,碰撞概率越低,這是個概率問題,不是一定發生或一定不發生。