如何在億萬級數據中查找數據是否存在

我們在註冊應用程序的時候，經常會碰見提示用戶名 / 郵箱 / 手機號已存在，需要更換。要實現這種功能的方案有很多種，本文我們就來看看不同設計方案的優缺點。

數據庫方案

這種方法是實現起來最簡單的方案，但是會帶來以下的問題：

存在延遲較高的性能問題。如果數據庫數據量很大，查詢速度就會比較慢。此外，數據庫查詢設計應用服務器和數據庫服務器之間的網絡通信。建立連接、發送查詢請求和接收響應需要的時間也會導致延遲。
數據庫負載過大。頻繁執行SELECT查詢來檢查用戶名的唯一性，每個查詢都會消耗數據庫資源，包括 CPU 和 I/O 資源。
可擴展性差。數據庫對併發連接和資源有限制。如果註冊率繼續上升，數據庫服務器可能難以處理不斷增加的傳入請求。數據庫的垂直擴展（向單個服務器配置更多資源）可能成本高昂並且總是會有上限。

緩存方案

import org.redisson.Redisson;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;
import org.redisson.api.RMap;

publicclass UserExistenceChecker {

    // 用於存儲用戶信息的 Redis 哈希映射名稱
    privatestaticfinal String USER_HASH_NAME = "users";

    public static void main(String[] args) {
        // 創建 Redisson 客戶端
        RedissonClient redisson = createRedissonClient();

        // 讀取用於存儲用戶信息的哈希表
        RMap<String, String> users = redisson.getMap(USER_HASH_NAME);

        // 在哈希映射中添加用戶
        users.put("user123", "someUserInfo"); // Here "someUserInfo" could be a JSON string, UUID, etc.

        // 檢查用戶是否存在
        boolean exists = users.containsKey("user123");
        System.out.println("User 'user123' exists? " + exists);

        // 檢查不存在的用戶
        exists = users.containsKey("user456");
        System.out.println("User 'user456' exists? " + exists);

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

    // 創建 Redisson 客戶端的輔助方法
    private static RedissonClient createRedissonClient() {
        Config config = new Config();
        config.useSingleServer()
                .setAddress("redis://127.0.0.1:6379") // 調整爲 Redis 地址
                .setPassword("yourpassword"); // 提供 Redis 密碼（如有）

        return Redisson.create(config);
    }
}

該解決方案最大的問題是內存使用過多。假設每個用戶名需要大約 15 個字節的內存。如果要存儲 10 億個用戶名，則需要 15GB 的內存。

總內存 = 每條記錄的內存使用量 _ 記錄數 = 15 字節 / 記錄 _ 1,000,000,000 條記錄 = 15,000,000,000 字節 ≈ 15,000,000 KB ≈ 15,000 MB ≈ 15 GB

布隆過濾器方案

如果緩存的方案導致內存佔用過多，那有沒有更好的辦法？布隆過濾器是一個非常好的選擇方案。

什麼是布隆過濾器

布隆過濾器是一種高度節省空間的隨機數據接哦古。它使用位數組來簡介地表示一個集合，並可以判斷一個元素是否屬於這個集合。

布隆過濾器的這種效率也是有一定代價的：在判斷一個元素是否屬於某個集合時，有可能錯誤地將不屬於該集合的元素認爲屬於該集合（誤報）。

因此，布隆過濾器不適合需要 “零錯誤” 的應用場景。但是，在可以容忍低錯誤率的應用場景下，布隆過濾器通過極少的錯誤實現了存儲空間的顯著節省。

結構

從上面的介紹可以知道，布隆過濾器的核心思想是使用一個位數組（bit array）和一組哈希函數。

爲數組，每個初始位都爲 0：

插入構建階段

插入值 x 時，使用 k 個哈希函數（下圖中 k 爲 3）分別對 x 的值進行哈希，並將哈希值與布隆過濾器的容量（位數組長度）取餘，並將結果所代表的相應位數組的位置設爲 1。

查詢階段

搜索過程與插入過程類似。類似地，使用 k 個哈希函數對要搜索的值進行哈希。只有當哈希得到的每一位的值爲 1 時，才表明該值 “可能” 真實存在；反之，如果任意一位的值爲 0，則表明該值一定不存在。例如，y1 一定不存在，而 y2 可能存在。

Redis 本身支持布隆過濾器的數據結構。我們可以簡單的使用 Redisson 客戶端實現一下代碼：

import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;

publicclass UserExistenceChecker {

    // Redis 中 Bloom 過濾器的名稱
    privatestaticfinal String BLOOM_FILTER_NAME = "user_existence_filter";

    public static void main(String[] args) {
        // 創建 Redisson 客戶端
        RedissonClient redisson = createRedissonClient();

        // 檢索或創建 Bloom 過濾器實例
        // 預期元素數和誤報概率是參數
        RBloomFilter<String> bloomFilter = redisson.getBloomFilter(BLOOM_FILTER_NAME);
        bloomFilter.tryInit(100000L, 0.001); // 用預期元素和誤報率初始化 Bloom 過濾器

        // 添加一個用戶到布隆過濾器
        bloomFilter.add("user123");

        // 檢驗用戶是否存在
        boolean exists = bloomFilter.contains("user123"); // Should return true
        System.out.println("User 'user123' exists? " + exists);

        // 檢查是否有不存在的用戶（由於 Bloom Filter 的特性，可能會誤報爲真實用戶）
        exists = bloomFilter.contains("user456"); // 假定未添加，理想情況下應返回 false，但也可能是誤報
        System.out.println("User 'user456' exists? " + exists);

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

    // 創建 Redisson 客戶端方法
    private static RedissonClient createRedissonClient() {
        Config config = new Config();
        config.useSingleServer()
                .setAddress("redis://127.0.0.1:6379") // 調整爲 Redis 地址
                .setPassword("yourpassword"); // 提供 Redis 密碼（如有）

        return Redisson.create(config);
    }
}

優點：

節省內存空間：與使用哈希表等數據結構相比，布隆過濾器通常需要更少的內存空間，因爲它不存儲實際元素，只存儲元素的哈希值。如果存儲 10 億條記錄，錯誤率probability爲 0.001，則僅需要 1.67GB內存。相比原來的 15GB，已經大大減少了。
高效查找：布隆過濾器可以在常數時間（O(1)）內快速判斷集合中是否存在某個元素，而無需遍歷整個集合。

缺點：

存在誤報率：布隆過濾器在判斷某個元素是否存在時，存在一定的誤報率。這意味着在某些情況下，它可能會錯誤地報告某個元素存在，但不會錯誤地報告某個元素不存在。但是，這問題通常影響不大。
無法刪除元素：布隆過濾器通常不支持從集合中刪除元素，因爲刪除一個元素會影響其他元素的哈希值，增加誤報率。

如何保證布隆過濾器不會誤報？

可以考慮使用布隆過濾器與數據庫結合的方案。

使用布隆過濾器判斷某個元素是否存在時，是有一定概率可能會誤報該元素存在，但不會誤報該元素不存在。

所以，當使用布隆過濾器判斷某個元素不存在時，可以直接信任這個結果並返回。如果確定某個元素存在，此時不能完全相信它的判斷，反之，可以去查詢數據庫中的真實結果。

因爲判斷某個元素存在的概率已經很低了，所以實際訪問數據庫的量級也會很小，整體壓力並不大。

可以刪除布隆過濾器中的元素嗎？

爲什麼不能從布隆過濾器中刪除元素呢？我們可以用一個例子說明。

例如，如果我們想從集合中刪除成員 “Tommy”，那麼我們首先會使用 k（下圖 k 爲 2）個哈希函數來計算“Tommy” 在布隆過濾器中的各個位置。由於 “Tommy” 已經是集合中的成員，因此位數組中對應的位置必須爲 1。如果我們要刪除這個成員“Tommy”，則需要將計算出來位置爲 1 的全置爲 0。如下圖所示，只需將索引位置 2 和 5 處的值設置爲 0 即可。

那麼問題就來了。我們假設 “Bob” 也已經是該集合中的一個成員了。如果我們需要查詢 “Bob” 是否在集合中，通過 2 次哈希函數計算後，我們判斷第 3 和第 5 的位置是否爲 1。此時，我們得到的結果是第 5 個位置爲 0，即 “Bob” 不屬於該集合。顯然，這是一個誤報。

所以，用存在就置 1 的布隆過濾器不支持刪除元素，但是計數的布隆過濾器是可以支持刪除的。

計數布隆過濾器的出現解決了上述問題。它將標準布隆過濾器的位數組的每一位擴展位一個小計數器。當插入元素時，對應的 k（k 是哈希函數的次數）計數器的值分別加 1。當刪除一個元素時，對應的 k 個計數器的值分別減 1。

由此我們可以看出，計數布隆過濾器以佔用數倍的存儲空間位代價，爲布隆過濾器增加了刪除操作。基本原理是不是挺簡單的？看看下圖就可以明白它和布隆過濾器的區別在哪裏了。

計數器的大小選擇

計數布隆過濾器和布隆過濾器的一個主要區別是計數布隆過濾器用計數器替代了布隆過濾器中的位。

那麼，計算器應該設置多大呢？這裏需要考慮空間的利用問題。從使用角度來說，當然越大越好，因爲更大的計數器可以代表更多的信息。但較大的計數器意味着佔用較多的資源，往往會造成很大的空間資源浪費。

因此，在選擇計數器時，應儘量滿足要求。計數器的具體計算比較複雜，涉及一系列數據公式，這裏就點到爲止，詳細可以去網上找找資料瞭解一下。

總結

Redis 布隆過濾器方案爲大數據量下的唯一性驗證提供了一種高效的基於內存的解決方案。它需要在內存消耗和錯誤率之間取得平衡。當然，布隆過濾器還有更多的應用場景，比如防止緩存穿透、防止惡意訪問等，留待以後文章在做介紹。

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