京東面試：億級黑名單 如何設計？億級查重呢？（答案含：布隆過濾器、布穀鳥過濾器）

首先回顧一下：四大統計（基數統計，二值統計，排序統計、聚合統計）的原理 和應用場景

尼恩這邊的文章都有一個 基本的規則，從最爲基礎的講起。

先看看 常見的四大統計。

億級海量數據查重，如何實現 ？涉及的是四大統計其中的 二值統計

億級海量數據黑名單 ，如何存儲？涉及的也是四大統計其中的 二值統計

第 1 大統計：基數統計

基數（Cardinality）是指一個集合中不同元素的數量， 或者說統計一個集合中不重複元素的個數。

簡單來說： 基數（Cardinality）就是去除重複後的數的個數

例如，對於一個包含重複元素的集合 {1, 2, 2, 3, 4, 4, 4}，其基數爲 4，即不同元素的個數。

在 Redis 中，HashSet / HyperLogLog 數據結構都能提供 高效的基數統計，而 HyperLogLog 算法可以在不保存原始數據的情況下快速計算出一個集合的基數。

基數統計的 2 大類型

類型 1：精確計算：

對於較小規模的數據集，可使用數據結構如哈希集合（HashSet）來實現基數統計。

哈希集合利用哈希函數將元素映射到存儲位置，其內部會自動處理元素的插入和衝突問題。

當插入一個元素時，哈希集合會根據元素的哈希值確定存儲位置，若該位置沒有元素，則直接插入；若已存在元素（哈希衝突），則通過一定的衝突解決策略（如鏈表法或開放尋址法）來處理。

通過計算哈希集合中的元素數量，即可得到集合的基數。

類型 2：近似計算原理（以 HyperLogLog 爲例）：

HyperLogLog 是一種基於概率的數據結構，用於估算大數據集的基數。

它的基本原理是將元素哈希爲二進制串，然後通過統計哈希值的前導零的最大長度來估算基數。

每個不同的元素經過哈希後，其哈希值的前導零長度呈現一定的概率分佈。

HyperLogLog 通過維護多個寄存器來記錄這些最大長度，然後根據這些寄存器的值和一定的數學公式來估算集合中的不同元素數量。

這種方法以犧牲一定的準確性爲代價，換取了對內存的高效利用，能夠在有限的內存空間內處理大規模數據集。

HyperLogLog 不存儲數據，只記錄不重複數的個數，HyperLogLog 有誤差，在 0.8125%。

基數統計的應用場景和案例

基數統計場景 1：網站流量分析：

互聯網公司中，用於統計網站的獨立訪客數量，爲市場部門評估網站的用戶覆蓋範圍和廣告效果提供重要數據

例如，像百度這樣的大型搜索引擎網站，每天有海量的訪問請求。

通過基數統計，可以瞭解有多少不同的用戶訪問了網站，而不需要記錄每個用戶的詳細訪問信息。

使用 HyperLogLog 算法，在內存佔用較小的情況下，就能快速估算出 UV/PV/ 註冊 IP 數 / 每日訪問 IP 數 / 統計在線人數:

  1. 統計網站註冊 IP 數：使用 HyperLogLog 可以高效地統計網站註冊用戶的獨立 IP 數量，爲網站運營者提供有價值的數據支持。

  2. 統計每日訪問 IP 數：通過對用戶訪問日誌進行處理，使用 HyperLogLog 可以快速統計出每日的獨立訪問 IP 數，有助於分析網站流量和用戶行爲。

  3. 統計頁面實時 UV PV 數：在實時監控系統中，使用 HyperLogLog 可以估算出頁面的實時訪問用戶數（UV）和頁面訪問量（PV），爲網站運營者提供實時反饋。

  4. 統計在線人數：在實時在線人數統計系統中，HyperLogLog 可以用於估算當前在線用戶的數量，爲系統性能優化和用戶體驗改進提供數據支持。

  5. APP 活躍用戶數：統計一個 APP 的日活 (日活躍用戶數量)、月活數 (月活躍用戶數量)，即每天或每月有多少不同的用戶活躍

上面的基數統計，其實對應到一些常見名詞：UV、PV、DAU、MAU

  1. UV(Unique Visitor)：獨立訪客，一般爲客戶端 IP，要去重

  2. PV(Page View)：頁面瀏覽量，不用去重

  3. DAU(Daily Active User)：日活躍用戶量，當天登錄或者使用某個產品的用戶數，要去掉重複登錄的用戶，多次登錄只記錄一次

  4. MAU(Monthly Active User)：月活躍用戶

基數統計場景 2：數據庫去重：

在數據庫管理中，用於統計一個表中某列的不同值的數量。

比如，在電商數據庫中，統計產品表中不同品牌的數量，有助於瞭解產品的品牌多樣性和市場分佈。

第 2 大統計：二值統計

二值統計通常涉及到將數據分爲兩個類別或狀態，比如成功與失敗、是與非等，並對這些類別進行計數和分析。

這種統計方法在處理二分類問題時非常常見，比如在質量控制、用戶行爲分析等領域。

二值統計的 4 大類型

類型 1：計數器數組：

使用一個數組作爲計數器，數組的每個元素用於記錄兩種狀態中的一種狀態的數量。

例如，有一個數組counts，counts[0]用於記錄狀態爲 0 的元素數量，counts[1]用於記錄狀態爲 1 的元素數量。

當一個元素狀態發生變化時，相應的計數器就會增加或減少。

這種方法在簡單的編程場景中比較直觀，適用於小規模的二值統計。

類型 2：位圖（Bitmap）：

位圖是一種簡單直觀的二值統計數據結構。它將每個元素對應到位圖中的一個位，位的值只能是 0 或 1，分別代表兩種狀態。

例如，在統計用戶是否登錄的場景中，將用戶 ID 與位圖中的位進行一一對應，若用戶已登錄，對應的位設爲 1；若未登錄，則設爲 0。

通過對所有位進行掃描和計數，可以快速統計出處於兩種狀態的元素數量。

類型 3：布隆過濾器 BloomFilter

布隆過濾器底層使用一個初值全爲 0 的 bit 數組和多個 hash 函數，

每次查找時，先將 key 根據 hash 函數映射到某個位置，判斷是否爲 0，爲 0 說明該數據不存在，直接返回，可以添加和快速查找元素是否存在，

添加時先對 key 經過所有的 hash 並對長度取模，得到多個位置並對每個位置設置爲 1，

查詢時仍是得到多個位置，只要有一個爲 0，則該 key 不存在，當然，BloomFilter 判存在的時候，有誤判，即使是全爲 1 時也不一定存在，因爲存在哈希衝突

類型 4：布穀鳥過濾器 CuckooFilter

布隆過濾器最大的缺陷就是不能刪除數據。

因此誕生了需要布隆過濾器的增強版本，布穀鳥過濾器就是其中一種。

布穀鳥過濾器可以被認爲是一個增強版的布隆過濾器，它支持元素的動態添加和刪除，同時提供了比傳統布隆過濾器更高的查詢效率和空間利用率。

布穀鳥過濾器的核心在於使用 “指紋信息” 代替簡單的位數組來存儲數據。

每個元素通過哈希函數生成一個或多個 “指紋”，這些指紋被存儲在過濾器中。

查詢時，只需檢查對應位置上是否存在相應的指紋信息即可。

相比於布隆過濾器，布穀鳥過濾器可以刪除數據。

而且基於相同的集合和誤報率，布穀鳥過濾器通常佔用的空間更少。相對的，算法實現也就更復雜。

不過，布穀鳥過濾器 同樣存有誤判率。即有可能將⼀個不在集合中的元素錯誤的判斷成在集合中。

注：布隆過濾器的誤報率通過調整位數組的大小和哈希函數來控制，而布穀鳥過濾器的誤報率受指紋大小和桶大小控制。桶大小：數組大小；指紋大小：每個位置存在數據個數

二值統計的應用場景和案例

二值統計的場景 1：設備狀態監測：

在網絡設備管理中，用於統計設備的在線（1）和離線（0）狀態。

例如，在一個數據中心，有大量的服務器，通過二值統計監控服務器的運行狀態。可以使用計數器數組，每次服務器狀態變化時更新相應的計數器。

當需要了解在線和離線服務器的數量時，直接讀取計數器的值即可，以便及時發現設備故障和網絡問題。

二值統計的場景 2：用戶行爲分析：

在互聯網產品中，統計用戶對某個功能的使用情況。

以一款移動社交應用爲例，統計用戶開啓或關閉推送通知功能的比例，可以使用位圖來記錄每個用戶的推送通知狀態。

通過統計位爲 1（開啓）和位爲 0（關閉）的數量，就能得到開啓和關閉推送通知的用戶比例，幫助產品團隊評估推送功能的受歡迎程度和對用戶的干擾程度。

再以網站的簽到功能爲例: 電商用戶簽到記錄，就是二值統計，可以基於 bitmap 二進制數組實現簽到日曆，用 bit 統計一位用戶，用一個二進制 bit 位代表一天的簽到狀態

第 3 大統計：排序統計

排序統計涉及將數據按照一定的順序（如升序或降序）進行排列，以便於分析和比較。

排序統計的例子，比如，可以使用 ZSET 對排序統計

  1. 可以 使用 ZSET 對文章的點贊數排序並分頁展示

  2. 對評論根據時間進行排序

排序算法如快速排序、歸併排序、堆排序等，都是排序統計中常用的方法。

排序統計的 2 大類型

第 1 類：基於比較的排序算法原理（如快速排序、歸併排序）：

這些算法的基本思想是通過比較元素之間的大小關係來確定它們的順序。

以快速排序爲例，它首先選擇一個基準元素，將數組分爲兩部分，小於基準元素的放在左邊，大於基準元素的放在右邊。然後對這兩部分分別進行快速排序，直到整個數組有序。

排序過程中，通過不斷地比較和交換元素的位置，實現元素的排序。

第 2 類：基於索引的數據結構原理（如有序集合）：

有序集合（Sorted Set）是一種同時具備集合和排序功能的數據結構。當插入一個新元素時，根據其排序值將元素插入到合適的位置，以保持集合的有序性。

它通過爲每個元素關聯一個分數（score）來實現排序。

元素按照分數的大小進行排序，分數可以是任意的數值，用於表示元素的某種屬性。

例如，在一個電商系統中，將商品的價格作爲分數，商品名稱作爲元素，就可以構建一個按照價格排序的有序集合。當插入一個新元素時，根據其分數將元素插入到合適的位置，以保持集合的有序性。

排序統計的應用場景和案例

排序統計的場景 1：排行榜系統：

在遊戲、音樂、電商等衆多領域都有廣泛應用。

例如，在遊戲排行榜中，根據玩家的得分對玩家進行排名。

使用（Sorted Set）有序集合，將玩家的得分作爲分數，玩家 ID 作爲元素，通過有序集合的操作，可以快速插入新玩家的分數，更新排行榜，並且可以方便地獲取前幾名玩家的信息，用於展示排行榜頁面。

排序統計的場景 2：數據篩選和統計：

在數據分析中，根據一定的數值範圍對數據進行篩選和統計。

例如，在電商系統中，統計價格在某個區間的商品數量。

通過有序集合，按照商品價格進行排序後，可以使用範圍查詢操作，快速獲取價格在指定區間的商品數量，幫助商家進行價格策略分析和庫存管理。

第 4 大統計：聚合統計

聚合統計是一種數據處理技術，它將多個數據記錄組合成一個集合，並計算該集合的統計信息，如總和、平均值、最大值和最小值等。

聚合操作通常用於數據倉庫和數據分析中，以簡化數據並提取有用的信息。

聚合統計的核心在於對數據進行分組（grouping），然後對每個組應用聚合函數（如 sum, avg, max, min 等）來計算統計值。

Redis 聚合統計的數據結構

Redis 提供了多種數據結構用於聚合統計，如集合（Set）、有序集合（Sorted Set）、哈希（Hash）等。

集合可以存儲不重複的元素，通過操作命令（如SCARD統計集合元素個數、SINTER計算集合交集等）實現簡單的聚合。

Redis 有序集合（ Sorted Set） 爲每個元素關聯一個分數，可根據分數進行排序和範圍統計。

Redis 哈希（Hash） 結構以鍵 - 值對的形式存儲數據，方便對不同屬性進行統計。

Redis 聚合統計的命令執行機制

對於聚合統計命令，Redis 在內部會遍歷相關的數據結構進行計算。在處理有序集合的範圍統計時，會根據元素的分數，通過二分查找等算法快速定位符合範圍的元素。

例如，在計算集合交集時，Redis 會逐個比較參與交集運算的集合中的元素，找出共同的元素。

聚合統計的應用場景

場景 1：網站流量分析
場景 2：電商數據分析
場景 3：社交平臺用戶行爲分析
場景 4：遊戲數據分析

回到前面的相關面試題，都屬於二值統計的類型

億級海量數據查重，如何實現 ？

億級海量數據黑名單 ，如何存儲？

50 億個電話號碼，如何判斷是否 10 萬個電話號碼是否存在？

安全連接網址，全球數 10 億的網址判斷？

大概的方案有三個：

使用 BitMap 位圖進行二值統計

BitMap 可以用作簽到、統計、用戶狀態等的處理

除了最後一個功能，Set無法完全支持，其他都是可以支持的。

那麼，爲什麼還需要BitSet了？

原因是空間佔用。

BitSet 不是 Redis 中的數據結構，其本質是 String 的內部數據結構 Bit。

我們可以理解爲：一連串 Bit 構成了 String，每一個 Bit 只能存儲 0 和 1，同時有自己的偏移量，而 Redis 可以根據偏移量對任何一個 Bit 進行 位操作 。

Redis 中 String 最大可以達到 512M ，根據這個公式：($offset/8/1024/1024)MB可以算出，offset 最大爲4,294,967,296，也就是 2 的 32 次方 ，所以 offset 也不能大於這個值。

使用 BitMap 位圖進行用戶黑名單管理

key爲user_blacklist，offset 是用戶的 id(用戶 不能大於 2^32 次方, 不能大於 10 個億)

以下是一個使用 Redis 的位圖（BitMap）實現用戶黑名單管理的示例代碼：

引入 Redis 的 Java 客戶端依賴，如果使用 Maven，可以在pom.xml文件中添加以下依賴：

<dependency>
    <groupId>redis.clients</groupId>
    <artifactId>jedis</artifactId>
    <version>3.3.0</version>
</dependency>

Java 實現代碼如下

import redis.clients.jedis.Jedis;

public class RedisUserBlacklist {
    public static void main(String[] args) {
        // 連接到 Redis 服務器
        Jedis jedis = new Jedis("localhost", 6379);

        // 假設用戶 ID 範圍爲 1 到 1000
        int userId = 123;

        // 將用戶加入黑名單，將對應位置的位設置爲 1
        jedis.setbit("user_blacklist", userId - 1, true);

        // 檢查用戶是否在黑名單中
        boolean isInBlacklist = jedis.getbit("user_blacklist", userId - 1);

        System.out.println("User " + userId + " is in blacklist: " + isInBlacklist);

        // 關閉連接
        jedis.close();
    }
}

在這個示例中，首先連接到本地的 Redis 服務器，然後使用setbit方法將位圖中對應參與者編號的位設置爲 1 表示加入黑名單，再使用getbit方法檢查某個參與者是否黑名單。

問題：上面講到，Redis 中 String 最大可以達到 512M ，根據這個公式：($offset/8/1024/1024)MB可以算出，offset 最大爲4,294,967,296，也就是 2 的 32 次方 ，所以 offset 也不能大於這個值。

問題 1：假設 40 億賬號， 有 1 千萬的黑名單， 假設使用 32 位無符號整數來表示用戶 ID，那麼可能需要一個非常長的位圖來涵蓋所有可能的用戶 ID，這可能會導致內存空間的浪費， 512M 內存，可能很多都是 空閒位。

問題 2：假設 100 億賬號， 有 1 千萬的黑名單，Redis 中 String 最大可以達到 512M，最多也就 40 多億，可能編號不夠用。

假設 100 億賬號， 有 1 千萬的黑名單，使用布隆過濾器進行二值統計， 需要的內存大概只要 600kb， 內存的估算大致如下：

那麼是吧 錯誤率提升到 0.01 ，也只要 2.5M 內存， 是 bitmap 的百分之一。

使用 布隆過濾器（Bloom Filter） 進行二值統計

布隆過濾器（英語：Bloom Filter）是 1970 年由布隆提出的。主要用於判斷一個元素是否在一個集合中。

它實際上是一個很長的二進制向量和一系列隨機映射函數。BloomFilter 在 NoSql、大數據的去重、判斷數據是否存在等領域有着廣泛的應用。

BloomFilter 常見應用場景：

經典場景：解決緩存穿透的問題

一般情況下，先查詢緩存是否有該條數據，緩存中沒有時，再查詢數據庫。

當數據庫也不存在該條數據時，每次查詢都要訪問數據庫，這就是緩存穿透。

緩存穿透帶來的問題是，當有大量請求查詢數據庫不存在的數據時，就會給數據庫帶來壓力，甚至會拖垮數據庫。

可以使用布隆過濾器解決緩存穿透的問題，把已存在數據的 key 存在布隆過濾器中。

當有新的請求時，先到布隆過濾器中查詢是否存在，如果不存在該條數據直接返回；如果存在該條數據再查詢緩存查詢數據庫。

經典場景：黑名單校驗

發現存在黑名單中的，就執行特定操作。

比如：識別垃圾郵件，只要是郵箱在黑名單中的郵件，就識別爲垃圾郵件。

假設黑名單的數量是數以億計的，存放起來就是非常耗費存儲空間的，布隆過濾器則是一個較好的解決方案。

把所有黑名單都放在布隆過濾器中，再收到郵件時，判斷郵件地址是否在布隆過濾器中即可。

布隆過濾器（Bloom Filter）原理

瞭解布隆過濾器原理之前，先回顧下 Hash 函數原理。

哈希函數

哈希函數的概念是：將任意大小的輸入數據轉換成特定大小的輸出數據的函數，轉換後的數據稱爲哈希值或哈希編碼，也叫散列值。

下面是一幅示意圖：

所有散列函數都有如下基本特性：

但是用 hash 表存儲大數據量時，空間效率還是很低，當只有一個 hash 函數時，還很容易發生哈希碰撞。

布隆過濾器數據結構

BloomFilter 是由一個固定大小的二進制向量或者位圖（bitmap）和一系列映射函數組成的。

在初始狀態時，對於長度爲 m 的位數組，它的所有位都被置爲 0，如下圖所示：

當有變量被加入集合時，通過 K 個映射函數將這個變量映射成位圖中的 K 個點，把它們置爲 1（假定有兩個變量都通過 3 個映射函數）。

查詢某個變量的時候我們只要看看這些點是不是都是 1 就可以大概率知道集合中有沒有它了

爲什麼說是可能存在，而不是一定存在呢？那是因爲映射函數本身就是散列函數，散列函數是會有碰撞的。

誤判率

布隆過濾器的誤判是指多個輸入經過哈希之後在相同的 bit 位置 1 了，這樣就無法判斷究竟是哪個輸入產生的，因此誤判的根源在於相同的 bit 位被多次映射且置 1。

這種情況也造成了布隆過濾器的刪除問題，因爲布隆過濾器的每一個 bit 並不是獨佔的，很有可能多個元素共享了某一位。如果我們直接刪除這一位的話，會影響其他的元素。(比如上圖中的第 3 位)

特性

單體服務 本地布隆過濾器 Guava

首先引入 Guava 的依賴：

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>31.0.1-jre</version>
</dependency>

接下來，使用了 Google Guava 庫中的布隆過濾器實現。

首先創建了一個可以容納 1000 個整數元素且誤判率爲 0.01 的布隆過濾器，然後插入了一些元素，並測試了一個存在的元素和一個不存在的元素在布隆過濾器中的判斷結果。

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

public class BloomFilterExample {
    public static void main(String[] args) {
        // 創建一個可以容納 1000 個元素，誤判率爲 0.01 的布隆過濾器
        BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), 1000, 0.01);

        // 插入元素
        for (int i = 1; i <= 500; i++) {
            bloomFilter.put(i);
        }

        // 查詢元素
        int testValue = 450;
        boolean mightContain = bloomFilter.mightContain(testValue);
        System.out.println("布隆過濾器判斷 " + testValue + " 是否存在：" + mightContain);

        // 測試誤判
        int nonExistentValue = 10000;
        boolean falsePositive = bloomFilter.mightContain(nonExistentValue);
        System.out.println("布隆過濾器對不存在的值 " + nonExistentValue + " 的誤判：" + falsePositive);
    }
}

注意，對於不存在的元素，布隆過濾器可能會產生誤判，認爲它存在於集合中。

Guava 提供的布隆過濾器的實現還是很不錯的，但是它有一個重大的缺陷就是隻能單機使用（另外，容量擴展也不容易），而現在互聯網一般都是分佈式的場景。

爲了解決這個問題就需要用到 Redis 中的布隆過濾器了。

Redis 的 BloomFilter (布隆過濾器)

Redis4.0 版本 之前的布隆過濾器可以使用 Redis 中的位圖操作實現，

直到 Redis4.0 版本提供了插件功能，Redis 官方提供的布隆過濾器才正式登場。

Redis4.0 版本 開始，布隆過濾器作爲一個插件加載到 Redis Server 中，就會給 Redis 提供了強大的布隆去重功能。

Redis 的 BloomFilter (布隆過濾器), 通過 一個可擴展的模塊 RedisBloom 這個 Module 實現。

RedisBloom 是一款集成了衆多功能的 RedisModule 模塊。

RedisBloom 這個 Module 內集成了很多的小功能，其中主要包括：可擴展的布隆過濾器（BloomFilter），可擴展的布穀鳥過濾器（CuckooFilter），最小計數草圖（Count-Min Sketch），近似百分位（T-Digest），頭部 K 元素（TopK）等。

可擴展的模塊 RedisBloom 這個 Module 的官方地址如下：

可擴展的布隆過濾器（BloomFilter），可擴展的布穀鳥過濾器（CuckooFilter），最小計數草圖（Count-Min Sketch），近似百分位（T-Digest），頭部 K 元素（TopK）等。其中很多功能都是依據 BloomFilter 類 的相關功能來進行實現的。

安裝 REDIS 和 REDISBLOOM 插件

編譯安裝 redis

#下載
[root@localhost redis]# /root/redis
[root@localhost redis]# wget https://download.redis.io/releases/redis-5.0.5.tar.gz
 
#解壓安裝
[root@localhost redis]# tar -zxvf redis-5.0.5.tar.gz
[root@localhost redis]# ls
redis-5.0.5  redis-5.0.5.tar.gz
[root@localhost redis]# cd redis-5.0.5
[root@localhost redis-5.0.5]# make

下載 REDISBLOOM 插件

https://github.com/RedisLabsModules/redisbloom/

tag:https://github.com/RedisBloom/RedisBloom/tags

下載壓縮包

[root@localhost redis]# wget https://github.com/RedisBloom/RedisBloom/archive/v2.2.1.tar.gz

解壓並安裝，生成. so 文件

[root@localhost redis]# tar -zxf v2.2.1.tar.gz 
[root@localhost redis]# ls
redis-5.0.5  redis-5.0.5.tar.gz  RedisBloom-2.2.1  v2.2.1.tar.gz
[root@localhost redis]# cd RedisBloom-2.2.1/
[root@localhost RedisBloom-2.2.1]# make
[root@localhost RedisBloom-2.2.1]# ls
changelog  contrib  Dockerfile  docs  LICENSE  Makefile  mkdocs.yml  ramp.yml  README.md  redisbloom.so  rmutil  src  tests

在 redis 配置文件 (redis.conf) 中加入該模塊即可

[root@localhost redis-5.0.5]# pwd
/root/redis/redis-5.0.5
[root@localhost redis-5.0.5]# ls
00-RELEASENOTES  CONTRIBUTING  deps     Makefile   README.md   runtest          runtest-moduleapi  sentinel.conf  tests
BUGS             COPYING       INSTALL  MANIFESTO  redis.conf  runtest-cluster  runtest-sentinel   src            utils
[root@localhost redis-5.0.5]# ls |grep redis.conf
redis.conf

　配置文件添加. so 文件

[root@localhost redis-5.0.5]# vim redis.conf

　

啓動 REDIS

[root@localhost redis-5.0.5]# ./src/redis-server ./redis.conf &

#查看是否啓動成功
[root@localhost redis-5.0.5]# ps -ef|grep 6379
root       4234   4176  0 22:12 pts/0    00:00:07 ./redis-server *:6379
root       8744   4176  0 23:06 pts/0    00:00:00 grep --color=auto 6379

#連接客戶端

[root@localhost redis-5.0.5]# ./src/redis-cli 
127.0.0.1:6379> keys *
(empty list or set)
127.0.0.1:6379>

Redis 的 BloomFilter 相關命令

REDISBLOOM 基本操作命令：

6ss6Id

以下命令僅參考當時的最新的代碼，詳細的準確命令請參考 社區命令文檔地址 。

Redis 的 BloomFilter 的 c++ 編碼結構

一個可擴展的布隆過濾器所依賴的主要數據結構如下所示：

typedef struct SBChain {
    SBLink *filters;  // 記錄所有的布隆過濾器
    size_t size;      // 記錄當前所有布隆過濾器可存儲元素的數量
    size_t nfilters;  // 記錄當前布隆過濾器數據的個數
    unsigned options; // 創建布隆過濾器表所依賴的參數
    unsigned growth;  // 創建新的布隆過濾器時其容量是上一個布隆過濾器的容量倍數
} SBChain;

typedef struct SBLink {
    struct bloom inner; // 對應的布隆過濾器
    size_t size;        // 已插入布隆過濾器表中的元素的個數
} SBLink;

struct bloom {
    uint32_t hashes;   // 記錄當前的hash數量
    uint8_t force64;
    uint8_t n2;
    uint64_t entries;  // 記錄當前布隆過濾器的容量

    double error;      // 記錄當前布隆過濾器的誤判率
    double bpe;

    unsigned char *bf; // 指向布隆過濾器存儲內容的內存塊
    uint64_t bytes;    // 記錄布隆過濾器存儲內容的內存塊的大小（字節）
    uint64_t bits;     // 記錄布隆過濾器存儲內容的內存塊的大小（比特）
};

BloomFilter 存儲結構

Redis 的 BloomFilter 的哈希規則（插入 / 判斷規則）

按照布隆過濾器的計算規則，在不同的誤判率的情況下我們需要使用多個不同的哈希函數計算對應的比特位，我們接下來看一下布隆過濾器的判斷 / 插入規則：

哈希算法： MurmurHash64A

判斷方式：

// 計算傳入元素的哈希特徵
bloom_hashval bloom_calc_hash64(const void *buffer, int len) {
    bloom_hashval rv;
    rv.a = MurmurHash64A_Bloom(buffer, len, 0xc6a4a7935bd1e995ULL);
    rv.b = MurmurHash64A_Bloom(buffer, len, rv.a);
    return rv;
}

// 判斷多個布隆過濾器中的對應比特位
for (int ii = sb->nfilters - 1; ii >= 0; --ii) {
    if (bloom_check_h(&sb->filters[ii].inner, h)) {
        return 0;
    }
}

Redis Client 客戶端中布隆過濾器的基本使用

在 Redis 中，布隆過濾器有兩個基本命令，分別是：

比如：

> bf.add one-more-filter fans1
(integer) 1
> bf.add one-more-filter fans2
(integer) 1
> bf.add one-more-filter fans3
(integer) 1
> bf.exists one-more-filter fans1
(integer) 1
> bf.exists one-more-filter fans2
(integer) 1
> bf.exists one-more-filter fans3
(integer) 1
> bf.exists one-more-filter fans4
(integer) 0
> bf.madd one-more-filter fans4 fans5 fans6
1) (integer) 1
2) (integer) 1
3) (integer) 1
> bf.mexists one-more-filter fans4 fans5 fans6 fans7
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 0

上面的例子中，沒有發現誤判的情況，是因爲元素數量比較少。

當元素比較多時，可能就會發生誤判，怎麼才能減少誤判呢？

Redis Client 創建一個自定義參數的布隆過濾器

上面的例子中使用的布隆過濾器，只是默認參數的布隆過濾器，它在我們第一次使用bf.add命令時自動創建的。

Redis 還提供了自定義參數的布隆過濾器，想要儘量減少布隆過濾器的誤判，就要設置合理的參數。

在使用bf.add命令添加元素之前，使用bf.reserve命令創建一個自定義的布隆過濾器。

bf.reserve命令有三個參數，分別是：

比如：

>  bf.reserve one-more-filter 0.0001 1000000
OK

如果對應的 key 已經存在時，在執行bf.reserve命令就會報錯。

如果不使用bf.reserve命令創建，而是使用 Redis 自動創建的布隆過濾器，默認的error_rate是 0.01，capacity是 100。

布隆過濾器的error_rate越小，需要的存儲空間就越大，對於不需要過於精確的場景，error_rate設置稍大一點也可以。

布隆過濾器的capacity設置的過大，會浪費存儲空間，設置的過小，就會影響準確率，所以在使用之前一定要儘可能地精確估計好元素數量，還需要加上一定的冗餘空間以避免實際元素可能會意外高出設置值很多。

總之，error_rate和 capacity都需要設置一個合適的數值。

實戰：使用 redisson 布隆過濾器實現用戶黑名單

pom 中引入 redisson 依賴:
<dependency>
    <groupId>org.redisson</groupId>
    <artifactId>redisson</artifactId>
    <version>3.16.0</version>
</dependency>
編寫代碼測試
import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;

public class RedissonBloomFilterBlacklist {
    public static void main(String[] args) {
        // 創建 Redisson 配置
        Config config = new Config();
        config.useSingleServer().setAddress("redis://127.0.0.1:6379");

        // 創建 Redisson 客戶端
        RedissonClient redisson = Redisson.create(config);

        // 創建布隆過濾器，用於存儲用戶黑名單
        RBloomFilter<String> blacklistFilter = redisson.getBloomFilter("userBlacklist");
        // 初始化布隆過濾器，預計存儲 10000 個元素，誤報率爲 0.01
        blacklistFilter.tryInit(10000, 0.01);

        // 將用戶 ID 添加到黑名單
        blacklistFilter.add("user123");
        blacklistFilter.add("user456");

        // 檢查用戶是否在黑名單中
        boolean isInBlacklist = blacklistFilter.contains("user123");
        System.out.println("User123 is in blacklist: " + isInBlacklist);

        boolean isNotInBlacklist = blacklistFilter.contains("user789");
        System.out.println("User789 is in blacklist: " + isNotInBlacklist);

        // 關閉 Redisson 客戶端
        redisson.shutdown();
    }
}

在這個示例中，首先創建了 Redisson 客戶端連接到 Redis 服務器。

然後創建了一個布隆過濾器，用於存儲用戶黑名單。

可以將用戶 ID 添加到布隆過濾器中，並檢查某個用戶 ID 是否在黑名單中。

注意，布隆過濾器存在一定的誤報率，即可能會將不在黑名單中的用戶誤判爲在黑名單中，但不會出現漏報（即真正在黑名單中的用戶一定能被檢測到）。

實戰：BloomFilter 實現億級海量數據查重 / 億級海量數據黑名單

package com.crazymaker.cloud.redis.redission.demo.business;

import io.rebloom.client.Client;
import lombok.extern.slf4j.Slf4j;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Service;
import redis.clients.jedis.Jedis;
import redis.clients.jedis.JedisPool;

/**
 * redis BloomFilter 布隆過濾器module 基於位圖算法
 * 功能：海量數據（億級）查重
 * 優點：佔用內存極少，並且插入和查詢速度都足夠快
 * 缺點：隨着數據的增加，誤判率會增加；還有無法判斷數據一定存在；另外還有一個重要缺點，無法刪除數據。
 */
@Slf4j
@Service
public class RedisModuleBloomFilter {

    @Autowired
    private JedisPool jedisPool;

    /**
     * 手機號是否存在檢測
     *
     * @param filterName 過濾器名稱
     * @param phone      手機號
     * @return true 表示存在
     */
    public boolean isExist(String filterName, String phone) {

        boolean booleans = false;
        try {
            //log.info("[名單過濾]數據：應用過濾器：{}，開始：{}", filterName, System.currentTimeMillis());
            booleans = getClient().exists(filterName, phone);
            //log.info("[名單過濾]數據：應用過濾器：{}，結束：{}", filterName, System.currentTimeMillis());

        } catch (Exception e) {
            e.printStackTrace();
        }

        return booleans;
    }

    /**
     * 多手機號 是否存在檢測
     *
     * @param filterName
     * @param phones     手機號數組
     * @return 返回對應的數組，true 表示存在
     */
    public boolean[] isExist(String filterName, String[] phones) {

        if (null == phones || phones.length < 1) {
            return null;
        }

        if (phones.length > 1000000) {
            return null;
        }

        boolean[] booleans = null;
        try {

            //log.info("[名單過濾]數據：應用過濾器：{}，開始：{}", filterName, System.currentTimeMillis());
            booleans = getClient().existsMulti(filterName, phones);
            //log.info("[名單過濾]數據：應用過濾器：{}，結束：{}", filterName, System.currentTimeMillis());

        } catch (Exception e) {
            e.printStackTrace();
        }

        return booleans;
    }


    /**
     * 數據添加到過濾器
     *
     * @param filterName 過濾器名稱
     * @param phones     要添加的手機號
     * @return
     */
    public boolean[] addFilter(String filterName, String[] phones) {

        if (null == phones || phones.length < 1) {
            return null;
        }

        boolean[] booleans = null;
        try {
            log.info("[過濾器添加數據]數據：應用過濾器：{}，開始：{}", filterName, System.currentTimeMillis());
            booleans = this.getClient().addMulti(filterName, phones);
            log.info("[過濾器添加數據]數據：應用過濾器：{}，結束：{}", filterName, System.currentTimeMillis());
        } catch (Exception e) {
            e.printStackTrace();
        }

        return booleans;
    }

    /**
     * 初始化過濾器
     */
    public void initFilter() {

        try {
            Client client = this.getClient();

            log.info("[初始化過濾器]數據：應用過濾器開始：{}", System.currentTimeMillis());
            //初始化過濾器 投訴
            client.createFilter("REDIS_BLOOM_FILTERS_SYSTEM_BLACK_COMPLAINT", 500000, 0.0001);
            //初始化過濾器 回T
            client.createFilter("REDIS_BLOOM_FILTERS_SYSTEM_BLACK_T", 200000, 0.0001);
            log.info("[初始化過濾器]數據：應用過濾器結束：{}", System.currentTimeMillis());

        } catch (Exception e) {
            e.printStackTrace();
        }

    }

    public Client getClient() {

        Client client = new Client(jedisPool);
        return client;
    }

    public Client getClient(JedisPool pool) {

        Client client = new Client(pool);

        return client;
    }
}

布隆過濾器的大小預估

如下地址是一個免費的在線布隆過濾器在線計算的網址： 點擊這裏

經過哈希計算次數設置爲 3 次，這個 3% 的誤判率和 3 次哈希運算需要多大空間位數組呢？

計算得到的結果是 984.14KiB，100W 的 key 才佔用了 0.98M，而如果是 10 億呢，計算的結果是 960M，這個內存空間是完全可以接受的。

布隆過濾器的優點和缺點

和 BitMap 相比，BloomFilter 有個巨大的性能優點：內存僅佔用其 1/10 甚至不到

相比於其它的數據結構，布隆過濾器在空間和時間方面都有巨大的優勢。

布隆過濾器存儲空間和插入 / 查詢時間都是常數 ，另外，散列函數相互之間沒有關係，方便由硬件並行實現。

該模塊主要用於判斷某個元素是否存在，利用 BitMap 這樣的數據結構，在犧牲可接受範圍的精度下極大提高了內存使用率和性能，查詢複雜度約爲 O(hash fun number)，和 redis 原有的 set 結構（非 zip set int）相比，內存僅佔用其 1/10 甚至不到。

以下爲 redis 中和 set 的測試內存結果對比：測試元素 100w ，元素大小 32 個字節

# 布隆過濾器
# Memory
used_memory:4714576
used_memory_human:4.50M

# set
# Memory
used_memory:73434368
used_memory_human:70.03M
123456789

根據以上結果，似乎布隆過濾器十分優秀，但由於原理的限制，布隆過濾器無法進行元素刪除。

BloomFilter 同 BitSet 對比

布隆過濾器的優點：

布隆過濾器的 問題

3 的缺點：

布隆過濾器的 問題 具體的介紹如下:

  1. 只能添加不能刪除，

    因爲多個 key 映射的位置可能相同，如果刪除一個，可能導致本來存在的也會被認爲不存在，因爲存在哈希衝突，可能添加的兩個元素佔一個坑位，此時如果刪除其中一個則另一個的該坑位也爲 0，也會被認爲刪除，就會導致誤判率增加，故不要輕易刪除 key

  2. 假陽性問題：判斷結果爲存在的場景，有誤判

    布隆過濾器中一個元素如果判斷結果爲存在的時候元素不一定存在，但是判斷結果爲不存在的時候則一定不存在。因此，布隆過濾器不適合那些對結果必須精準的應用場景。

    全爲 1 不一定存在，有一個 0 則一定不存在，誤判就是把認爲存在的，可能不存在的

  3. 儘可能使得初始 bit 數組足夠大，不要後續擴容

    當容量快滿時，hash 碰撞的概率變大，插入、查詢的錯誤率也就隨之增加了

    當實際元素過大時，遠遠大於初始數組，則必須對布隆過濾器重建，否則誤判率會非常大，此時重新分配一個更大的 bit 數組，然後將原來的元素重新添加進入，再繼續判斷

    使用時要儘可能使得初始 bit 數組足夠大，不要後續擴容，後續要進行重建

    當 bitmap 過小時，要進行重建，重新創建一個更大的 bitmap，然後將數據重新加入

其他問題

Cuckoo Filter 布穀鳥過濾器

爲了解決布隆過濾器不能刪除元素的問題, 論文《Cuckoo Filter：Better Than Bloom》作者提出了布穀鳥過濾器。

布穀鳥過濾器就是布隆過濾器的升級版，全面優化了布隆過濾器的痛點。

布穀鳥哈希（Cuckoo Hashing）是一種哈希表的實現方式，它允許多個元素映射到同一個哈希桶（或稱爲槽位）。

這種哈希方法得名於布穀鳥的寄生繁殖行爲，即布穀鳥將蛋產在其他鳥的巢中，迫使其他鳥撫養其後代。

爲啥要取名布穀鳥呢? 有個成語，「鳩佔鵲巢」, 布穀鳥也是。

布穀鳥從來不自己築巢, 它將自己的蛋產在別人的巢裏，讓別人來幫忙孵化。

待小布谷鳥破殼而出之後，因爲布穀鳥的體型相對較大，它又將養母的其它孩子（還是蛋）從巢裏擠走 —— 從高空摔下夭折了。

布穀鳥哈希結構的原理

布穀鳥哈希結構是一種哈希表實現方式，它通過使用多個哈希函數和 “踢出” 機制來解決哈希衝突問題。

布穀鳥哈希（Cuckoo Hashing）是一種用於高效實現哈希表的數據結構和算法。它的主要目的是在處理哈希衝突時，通過特定的策略來保證數據的快速插入、查詢和刪除操作，同時儘量減少哈希衝突對性能的影響。

其核心思想是使用多個哈希函數（通常爲兩個或更多）來確定元素在哈希表中的存儲位置。例如，假設有兩個哈希函數和，當插入一個元素時，會先嚐試將其插入到所對應的位置。如果該位置已經被其他元素佔用（發生哈希衝突），則會根據一定的規則 “驅逐” 當前佔用該位置的元素，並將被驅逐的元素重新插入到所對應的位置。

這個過程可能會持續進行，直到所有元素都找到合適的位置或者達到一定的重試次數限制。

在布穀鳥哈希中，當發生哈希衝突時，元素不是被簡單地放在同一個桶中，而是會 “踢出” 已有的元素，並將這個被踢出的元素重新哈希到另一個位置。

是一種鳩佔鵲巢的策略，最原始的布穀鳥哈希方法是使用兩個哈希函數對一個key進行哈希，得到桶中的兩個位置，此時

當然假如存在絕對的空間不足，那老是踢出也不是辦法，所以一般會設置一個踢出閾值，如果在某次插入行爲過程中連續踢出超過閾值，則進行擴容。

Cuckoo Filter 插入

Cuckoo Filter 布穀鳥過濾器的插入是重點，與樸素的布穀鳥哈希不同，布穀鳥過濾器採取了兩個並不獨立的哈希函數，

布穀鳥過濾器也是由兩個或者多個哈希函數構成，布穀鳥過濾器的布穀鳥哈希表的基本單位稱爲條目（entry）。

每個條目存儲一個指紋（fingerprint），指紋指的是使用一個哈希函數生成的 n 位比特位，n 的具體大小由所能接受的誤判率來設置，論文中的例子使用的是 8bits 的指紋大小。

具體的指紋是通過哈希函數取一定量的比特位

fp = fingerprint(x)

假設要計算條目（entry） x 的 兩個桶的索引 p1 、P2 ， 具體的 函數如下

fp = fingerprint(x)
p1 = hash(x)
p2 = p1 ^ hash(fp)  // 異或

p1 、P2 即計算出來兩個桶的索引，其中

進行異或操作的好處是，因爲異或操作的特性：同爲 0 不同爲 1，且 0 和任何數異或是這個數的本身。

那麼反過來，p1 也可以通過 p2 和指紋異或來計算。

 p1= p2 ^ hash(fp)  // 異或

換句話說，在桶中遷走一個鍵，我們直接用當前桶的索引 ii 和存儲在桶中的指紋計算它的備用桶。

上圖（a）(b) 展示了一個基本的布穀鳥哈希表的插入操作，是由一個桶數組組成，每個插入項都有由散列函數 h1(x) 和 h2(x) 確定的兩個候選桶。

哈希表由一個桶數組組成，其中一個桶可以有多個條目（比如上述圖 c 中有四個條目）。

而每個桶中有四個指紋位置，意味着一次哈希計算後布穀鳥有四個 “巢 “可用，而且四個巢是連續位置，可以更好的利用 cpu 高速緩存。

也就是說每個桶的大小是 4*8bits。

Cuckoo Filter 插入時的踢出

最簡單的布穀鳥哈希結構是一維數組結構，會有兩個 hash 算法將新來的元素映射到數組的兩個位置。

如果兩個位置中有一個位置爲空，那麼就可以將元素直接放進去。

但是如果這兩個位置都滿了，它就不得不「鳩佔鵲巢」，隨機踢走一個，然後自己霸佔了這個位置。

p1 = hash1(x) % l
p2 = hash2(x) % l

不同於布穀鳥的是，布穀鳥哈希算法會幫這些受害者（被擠走的蛋）尋找其它的窩。

因爲每一個元素都可以放在兩個位置，只要任意一個有空位置，就可以塞進去。

所以這個傷心的被擠走的蛋會看看自己的另一個位置有沒有空，如果空了，自己挪過去也就皆大歡喜了。但是如果這個位置也被別人佔了呢？

好，那麼它會再來一次「鳩佔鵲巢」，將受害者的角色轉嫁給別人。然後這個新的受害者還會重複這個過程直到所有的蛋都找到了自己的巢爲止。

布穀鳥過濾器本質上是一個 桶數組，每個桶中保存若干數量的 指紋（指紋由元素的部分 Hash 值計算出來）。

定義一個布穀鳥過濾器，每個桶記錄 2 個指紋，5 號桶和 11 號桶分別記錄保存 a, b 和 c, d 元素的指紋，如下所示：

此時，向其中插入新的元素 e，發現它被哈希到的兩個候選桶分別爲 5 號 和 11 號，但是這兩個桶中的元素已經添加滿了：

按照布穀鳥過濾器的特性，它會將其中的一個元素重哈希到其他的桶中（具體選擇哪個元素，由具體的算法指定），新元素佔據該元素的位置，如下：

以上便是向布穀鳥過濾器中添加元素併發生衝突時的操作流程，在我們的例子中，重新放置元素 e 觸發了另一個重置，將現有的項 a 從桶 5 踢到桶 15。

這個過程可能會重複，直到找到一個能容納元素的桶，這就使得布穀鳥哈希表更加緊湊，因此可以更加節省空間。如果沒有找到空桶則認爲此哈希表太滿，無法插入。

Cuckoo Filter 查找

布穀鳥過濾器的查找過程很簡單，給定一個項 x ，算法首先根據上述插入公式，計算 x 的指紋和兩個候選桶。

然後讀取這兩個桶：如果兩個桶中的任何 Item 與現有指紋匹配，則布穀鳥過濾器返回 true，否則過濾器返回 false。

此時，只要不發生桶溢出，就可以確保沒有假陰性。

Cuckoo Filter 刪除

標準 BloomFilter 布隆過濾器不能刪除，因此刪除單個項需要重建整個 BloomFilter 過濾器，而計數 BloomFilter 布隆過濾器需要更多的空間。

布穀鳥過濾器就像計數布隆過濾器，可以通過從哈希表刪除相應的指紋刪除插入的項。

具體刪除的過程也很簡單，檢查給定項的兩個候選桶；如果任何桶中的指紋匹配，則從該桶中刪除匹配指紋的一份副本。

Cuckoo Filter 的問題和優化

但是會遇到一個問題，那就是如果數組太擁擠了，連續踢來踢去幾百次還沒有停下來，這時候會嚴重影響插入效率。

這時候布穀鳥哈希會設置一個閾值，當連續佔巢行爲超出了某個閾值，就認爲這個數組已經幾乎滿了。這時候就需要對它進行擴容，重新放置所有元素。

還會有另一個問題，那就是可能會存在擠兌循環。比如兩個不同的元素，hash 之後的兩個位置正好相同，這時候它們一人一個位置沒有問題。但是這時候來了第三個元素，它 hash 之後的位置也和它們一樣，很明顯，這時候會出現擠兌的循環。不過讓三個不同的元素經過兩次 hash 後位置還一樣，這樣的概率並不是很高，除非你的 hash 算法太挫了。

布穀鳥哈希算法對待這種擠兌循環的態度就是認爲數組太擁擠了，需要擴容（實際上並不是這樣）。

上面的布穀鳥哈希算法的平均空間利用率並不高，大概只有 50%。到了這個百分比，就會很快出現連續擠兌次數超出閾值。這樣的哈希算法價值並不明顯，所以需要對它進行改良。

優化的兩個方案

方案之一是增加 hash 函數

讓每個元素不止有兩個巢，而是三個巢、四個巢。這樣可以大大降低碰撞的概率，將空間利用率提高到 95% 左右。

方案之二是在數組的每個位置上掛上多個座位

是在數組的每個位置上掛上多個座位

這樣即使兩個元素被 hash 在了同一個位置，也不必立即「鳩佔鵲巢」，因爲這裏有多個座位，你可以隨意坐一個。

除非這多個座位都被佔了，才需要進行擠兌。很明顯這也會顯著降低擠兌次數。這種方案的空間利用率只有 85% 左右，但是查詢效率會很高，同一個位置上的多個座位在內存空間上是連續的，可以有效利用 CPU 高速緩存。

所以更加高效的方案是將上面的兩個改良方案融合起來，比如使用 4 個 hash 函數，每個位置上放 2 個座位。這樣既可以得到時間效率，又可以得到空間效率。這樣的組合甚至可以將空間利用率提到高 99%，這是非常了不起的空間效率。

和 Cuckoo Filter 相比，BloomFilter 的不足

相比布穀鳥過濾器，布隆過濾器有以下不足：查詢性能弱、空間利用效率低、不支持反向操作（刪除）以及不支持計數。

布隆過濾器 BloomFilter 查詢性能弱

因爲布隆過濾器需要使用多個 hash 函數探測位圖中多個不同的位點，這些位點在內存上跨度很大，會導致 CPU 緩存行命中率低。

布隆過濾器 BloomFilter 空間效率低

因爲在相同的誤判率下，布穀鳥過濾器的空間利用率要明顯高於布隆，空間上大概能節省 40% 多。

不過布隆過濾器並沒有要求位圖的長度必須是 2 的指數，而布穀鳥過濾器必須有這個要求。從這一點出發，似乎布隆過濾器的空間伸縮性更強一些。

布隆過濾器 BloomFilter 不支持反向刪除操作

這個問題着實是擊中了布隆過濾器的軟肋。

在一個動態的系統裏面元素總是不斷的來也是不斷的走。布隆過濾器就好比是印跡，來過來就會有痕跡，就算走了也無法清理乾淨。

比如，本來只留下 1kw 個元素，但是整體上來過了上億的流失元素，布隆過濾器很無奈，它會將這些流失的元素的印跡也會永遠存放在那裏。

隨着時間的流失，這個過濾器會越來越擁擠，直到有一天你發現它的誤判率太高了，不得不進行重建。

布穀鳥過濾器在論文裏聲稱自己解決了這個問題，它可以有效支持反向刪除操作。

而且將它作爲一個重要的賣點，誘惑你們放棄布隆過濾器改用布穀鳥過濾器。

Redis 的 CuckooFilter (布穀鳥過濾器)

布穀鳥過濾器在某些場景下能夠比布隆過濾器提供更好的填充率，並且支持了刪除元素，在某些場景下也爲很多業務提供了更好的支持。

Redis 的 CuckooFilter (布穀鳥過濾器) 相關命令

以下命令僅參考當時的最新的代碼，詳細的準確命令請參考 社區命令文檔地址 。

Redis 的 布穀鳥過濾器 的主要 c++ 數據結構

Redis 的 布穀鳥過濾器 的主要 c++ 數據結構如下所示：

typedef struct {
    uint64_t numBuckets;     // bucket 的數量，大小爲2次冪的值
    uint64_t numItems;       // 插入元素的數量
    uint64_t numDeletes;     // 刪除元素的數量
    uint16_t numFilters;     // 所有子布穀鳥過濾器的數量
    uint16_t bucketSize;     // 每個 bucket 中可以存儲指紋的數量，默認爲2
    uint16_t maxIterations;  // 尋找指紋的存儲空間時的最大迭代次數，默認爲20次
    uint16_t expansion;      // 擴展倍數，大小爲2次冪的值，默認爲2
    SubCF *filters;          // 所有子布穀鳥過濾器信息的數組
} CuckooFilter;

typedef struct {
    uint32_t numBuckets;     // bucket 的數量，大小爲2次冪的值
    uint8_t bucketSize;      // 每個 bucket 中可以存儲指紋的數量
    uint8_t *data;           // 實際存儲數據的內存塊指針
} SubCF;

typedef struct {
    uint64_t i1;             // 記錄元素的一個哈希值
    uint64_t i2;             // 記錄元素的另一個哈希值
    uint8_t fp;              // 指紋的大小是1到255
} CuckooKey;

Redis 的 布穀鳥過濾器 哈希規則（插入 / 判斷規則）

按照布穀鳥過濾器的計算規則，當我們需要判斷一個元素是否存在的時候, 需要判斷兩個位置上的空間中是否存在特定的指紋信息；

當需要進行插入操作的時候需要從兩個索引的位置上隨機找到一個空餘的空間進行插入操作，因此針對於每一個傳入的元素，我們都會生成兩個對應的特徵值。

哈希算法： MurmurHash64A

判斷方式：

Redis 的 布穀鳥過濾器 踢除規則

由於不同傳入值的指紋可能相同，同一個 bucket 的空間可能會被其他相同指紋的傳入值佔滿，導致新的值無法插入，這時就需要對已有空間中的值進行踢除操作。

相關函數：Filter_KOInsert

具體流程：

  1. 將從最新的布穀鳥過濾器中執行踢除操作；

  2. 依據傳入值的其中一個哈希值，找到對應的 bucket 的位置，獲取其中特定位置中的指紋信息，然後將新的指紋存儲到特定位置上；

  3. 尋找上次獲取到的 bucket 中的老的指紋的下一個位置點，判斷對應的 bucket 中是否有空閒位置：

Redis Client 客戶端 布穀鳥過濾器的命令

創建布穀鳥過濾器

CF.RESERVE {key} {capacity} [BUCKETSIZE {bucketsize}] [MAXITERATIONS {maxiterations}]
[EXPANSION {expansion}]

命令用於創建布穀鳥過濾器，時間複雜度：O(1)，

其中參數介紹如下：

布穀鳥過濾器中添加元素

CF.ADD {key} {item}

命令用於布穀鳥過濾器中添加元素。

時間複雜度：O(sub filter number + maxiterations)。

其中參數介紹如下：

布穀鳥過濾器中添加元素（不存在時則插入）

CF.ADDNX {key} {item}

命令用於布穀鳥過濾器中添加元素，當元素不存在時則插入，

之所以需要提供這樣的命令，源於布穀鳥的佔位踢出算法，如果連續的插入相同的元素，則會導致內存使用率降低，同時會導致刪除後數據依然存在，故寫入前應當判斷元素是否存在。

時間複雜度：O(sub filter number + maxiterations)。

其中參數介紹如下：

CF.RESERVE 和 CF.ADD，CF.ADDNX 的複合體

創建的同時，添加元素

CF.INSERT {key} [CAPACITY {capacity}] [NOCREATE] ITEMS {item ...}
CF.INSERTNX {key} [CAPACITY {capacity}] [NOCREATE] ITEMS {item ...}

這兩個命令爲 CF.RESERVE 和 CF.ADD，CF.ADDNX 的複合體，這裏不在重複介紹。

布穀鳥過濾器中判斷元素是否存在

CF.EXISTS {key} {item}

命令用於布穀鳥過濾器中判斷元素是否存在，時間複雜度：O(sub filter number)。

其中參數介紹如下：

布穀鳥過濾器中刪除元素

CF.DEL {key} {item}

命令用於布穀鳥過濾器中刪除元素，這裏需要注意的是，如果同一個元素添加多次，則同樣需要刪除多次，時間複雜度：O(sub filter number)。

其中參數介紹如下：

布穀鳥過濾器中查詢元素存在的數量

CF.COUNT {key} {item}

命令用於布穀鳥過濾器中查詢元素存在的數量，這裏需要注意的是返回的不是一個準確值，時間複雜度：O(sub filter number)。

其中參數介紹如下：

將一個布穀鳥過濾器以分片的方式讀出

CF.SCANDUMP {key} {iter}

命令用於將一個布穀鳥過濾器以分片的方式讀出，返回兩個子段分別爲分片總數和分片字節，當返回分配總數爲 0，且字節爲空時代表讀取結束，時間複雜度：O(n)，

其中參數介紹如下：

將一個布穀鳥過濾器以分片的方式寫入

CF.LOADCHUNK {key} {iter} {data}

命令用於將一個布穀鳥過濾器以分片的方式寫入，存在則覆蓋。時間複雜度：O(n)，其中參數介紹如下：

查看布穀鳥過濾器詳情

CF.INFO {key}

命令用於查看布穀鳥過濾器詳情，時間複雜度：O(1)，

其中參數介紹如下：

實戰：CuckooFilter 實現億級海量數據查重 / 億級海量數據黑名單

package com.crazymaker.cloud.redis.redission.demo.business;

import io.rebloom.client.Client;
import lombok.extern.slf4j.Slf4j;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Service;
import redis.clients.jedis.Jedis;
import redis.clients.jedis.JedisPool;

import java.util.ArrayList;
import java.util.List;

/**
 * redis CuckooFilter 布穀鳥過濾器module 基於位圖算法
 * 功能：億級海量數據查重/或者億級海量數據黑名單 
 * 優點：佔用內存極少，並且插入和查詢速度都足夠快
 * 缺點：隨着數據的增加，誤判率會增加；還有無法判斷數據一定存在；另外還有一個重要缺點，無法刪除數據。
 */
@Slf4j
@Service
public class RedisModuleCuckooFilter {

    @Autowired
    private JedisPool jedisPool;


    /**
     * 手機號是否存在過濾器中
     *
     * @param filterName 過濾器名稱
     * @param phone      手機號
     * @return true 表示存在
     */
    public boolean isExist(String filterName, String phone) {

        boolean booleans = false;
        try {
            //log.info("[名單過濾]數據：應用過濾器：{}，開始：{}", filterName, System.currentTimeMillis());
            booleans = getClient().cfExists(filterName, phone);
            //log.info("[名單過濾]數據：應用過濾器：{}，結束：{}", filterName, System.currentTimeMillis());

        } catch (Exception e) {
            e.printStackTrace();
        }
        return booleans;
    }

    /**
     * 數據添加到過濾器
     *
     * @param filterName 過濾器名稱
     * @param phone      要添加的手機號
     * @return
     */
    public Boolean addFilter(String filterName, String phone) {
        Boolean booleans = false;
        try {
            log.info("[過濾器添加數據]數據：應用過濾器：{}，開始：{}", filterName, System.currentTimeMillis());
            booleans = this.getClient().cfAddNx(filterName, phone);
            log.info("[過濾器添加數據]數據：應用過濾器：{}，結束：{}", filterName, System.currentTimeMillis());
        } catch (Exception e) {
            e.printStackTrace();
        }
        return booleans;
    }

    /**
     * 數據添加到過濾器
     *
     * @param filterName 過濾器名稱
     * @param phones     要添加的手機號
     * @return
     */
    public List<Boolean> addFilter(String filterName, String[] phones) {

        if (null == phones || phones.length > 0) {
            return new ArrayList<>();
        }
        List<Boolean> booleans = new ArrayList<>();
        try {
            log.info("[過濾器添加數據]數據：應用過濾器：{}，開始：{}", filterName, System.currentTimeMillis());
            booleans = this.getClient().cfInsertNx(filterName, phones);
            log.info("[過濾器添加數據]數據：應用過濾器：{}，結束：{}", filterName, System.currentTimeMillis());
        } catch (Exception e) {
            e.printStackTrace();
        }
        return booleans;
    }

    /**
     * 數據從過濾器刪除
     *
     * @param filterName 過濾器名稱
     * @param phone      要刪除的手機號
     * @return
     */
    public boolean deleteFilter(String filterName, String phone) {

        if (null == phone) {
            return false;
        }

        boolean booleans = false;
        try {
            log.info("[過濾器刪除數據]數據：應用過濾器：{}，開始：{}", filterName, System.currentTimeMillis());
            booleans = this.getClient().cfDel(filterName, phone);
            log.info("[過濾器刪除數據]數據：應用過濾器：{}，結束：{}", filterName, System.currentTimeMillis());
        } catch (Exception e) {
            e.printStackTrace();
        }

        return booleans;
    }

    /**
     * 初始化過濾器
     */
    public void initFilter() {

        try {
            Client client = this.getClient();
            log.info("[初始化過濾器]數據：應用過濾器開始：{}", System.currentTimeMillis());
            //初始化過濾器 系統白名單
            client.createFilter("REDIS_BLOOM_FILTERS_SYSTEM_WHITE", 100000, 0.0001);
        } catch (Exception e) {
            e.printStackTrace();
        }

    }

    public Client getClient() {
        Client client = new Client(jedisPool);
        return client;
    }

    public Client getClient(JedisPool pool) {

        Client client = new Client(pool);
        return client;
    }
}

布穀鳥過濾器和布隆過濾器的對比

該模塊主要用於判斷某個元素是否存在，相比於布隆過濾器，布穀鳥過濾器支持數據刪除，同時由於布穀鳥算法，其佔用內存在理論情況下比布隆過濾器更小，查詢複雜度約爲 O(2)，

以下爲 redis 中和 set 的測試內存結果對比：測試元素 100w ，元素大小 32 個字節

# 布穀鳥過濾器
# Memory
used_memory:2114792
used_memory_human:2.02M

# set
# Memory
used_memory:73434368
used_memory_human:70.03M

根據以上結果，看上去似乎布穀鳥過濾器在查詢和內存的使用效率上會高於布隆過濾器，但在實際情況中爲了減少互踢問題，需要擴容，實際使用內存甚至會高於布隆過濾器，同樣，由於互踢問題的存在，在實際的寫入效率上也比布隆過濾器要差一些。

但在實際使用場景中，常常存在需要進行數據擦除的情況，相比於布隆過濾器，布穀鳥過濾器在不是極端的使用場景則更爲靈活。

布穀鳥過濾器優點和缺點

優點

缺點

使用的過程中，還是並且要充分考慮布穀鳥過濾器存在誤判率的特點，合理應用於合適的場景。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/G4Y1u85eJL2gDEedi8_RZg

猜你喜歡