深入理解PHP+Redis實現布隆過濾器(億級大數據處理和黑客攻防必備)

来源:https://www.cnblogs.com/phpphp/p/18122907
-Advertisement-
Play Games

布隆過濾器 極簡概括 英文名稱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種解決方案:
    1. 通過異常行為做攔截:搶購一般會讓用戶登錄, 讓伺服器知道誰在搶購,如果單位時間內Redis被穿透的次數過多,直接封禁。思路:上游添加Redis::get(get flash_sale . 用戶id) > 10的判斷,如果要查資料庫,redis就Redis::incr(flash_sale . 用戶id),直到超過指定次數,然後上游直接攔截。
    2. 如果沒有查到數據,也在緩存中存儲,值為1即可,但是這有2個弊端,1是緩存過後可能用不上,2是大量的緩存,也會增加存儲的負擔。
    3. 使用布隆過濾器:上文有講,把他放到業務邏輯的上游做判斷,如果過濾器中存在,則走下游流程,如果不存在,則直接阻斷其後續流程。

如何減少布隆過濾器誤判的概率

  • 增加哈希函數的數量:1個哈希函數演算法可能會衝突,多個與源數據進行哈希演算法,就能減少衝突的發生。
  • 增加布隆過濾器的長度:例如10個比特槽位,存1000條數據,大概率有衝突的情況,但是將長度增加到2000,這就能減少衝突概率的發生。

搶購場景商品被刪除了,如何同步到布隆過濾器

先看預設場景,看看要不要做處理:商品被刪除,MySQL無數據,布隆過濾器有數據。

  • 如果redis緩存無商品數據:
    通過布隆過濾器->緩存無數據->查資料庫->無數據->返回商品信息不存在。
  • 如果redis緩存仍舊有商品信息:
    通過布隆過濾器->緩存有->其它下單流程。

此時會發現,如果redis緩存仍舊有商品信息,還會有問題,解決方案:

  1. 可以非同步重建布隆過濾器:這和定期刷新緩存一個道理,防止緩存的長期不一致。
  2. 維護一個計數布隆過濾器:表示該位置被幾個數據進行了引用,如果是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種值,但是宇宙空間里的信息量卻無窮的多,輸入數據無窮多但輸出數據有限,這就導致哈希碰撞的產生。
演算法生成的信息越長,碰撞概率越低,這是個概率問題,不是一定發生或一定不發生。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 使用defineModel時,為什麼子組件內沒有任何關於props的定義和emit事件觸發的代碼?修改defineModel返回值會修改父組件上綁定的變數,這是否破壞了vue的單向數據流呢? ...
  • React 學習之 createElement React 元素 在 React 中,元素是 React 應用的最小構建塊。 一個 React 元素是 React 對象的一個輕量級、靜態的表示。 它們被 React 用於知道屏幕上什麼應該被渲染,併在數據改變時保持 UI 的更新。 React 元素是 ...
  • 一、三次握手 三次握手(Three-way Handshake)其實就是指建立一個TCP連接時,需要客戶端和伺服器總共發送3個包 主要作用就是為了確認雙方的接收能力和發送能力是否正常、指定自己的初始化序列號為後面的可靠性傳送做準備 過程如下: 第一次握手:客戶端給服務端發一個 SYN 報文,並指明客 ...
  • 首先寫一個bind的簡單示例: 'use strict' function fn() { console.log('this::', this) console.log('arguments::', arguments) } // fn() // 這裡調用時this 在嚴格模式下是undefined ...
  • React 學習之 Hello World React 簡介 React是一個用於構建用戶界面的JavaScript庫,由Facebook開發並維護。React通過聲明式的方式來構建UI,使得代碼更易於理解和測試。React的核心概念包括組件(Component)和虛擬DOM(Virtual DOM ...
  • nvm nvm(Node Version Manager)是一個Node.js的版本管理器。 安裝nvm windows安裝nvm 1. 下載nvm 下載地址:nvm-windows,下載 nvm-noinstall 或者 nvm-setup.exe 如果使用 nvm-noinstall 可以運行 ...
  • 多租戶的概念是我在畢業後不久進第一家公司接觸到的,當時所在部門的業務是計劃建設一套基於自研的、基於開放 API 的、基於 PaaS 的、面向企業(ToB)的多租戶架構平臺,將我們的服務可以成規模地、穩定高效地交付給客戶使用。 ...
  • 什麼是客戶管理系統? 客戶管理系統,也稱為CRM(Customer Relationship Management),主要目標是建立、發展和維護好客戶關係。 CRM系統圍繞客戶全生命周期的管理,吸引和留存客戶,實現縮短銷售周期、降低銷售成本、增加銷售收入的目的,從而提高企業的盈利能力和競爭力。 CR ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...