Bloom Filter

Bloom Filter（布隆過濾器）是一種空間效率極高的機率型資料結構，用於測試一個元素是否為集合的成員。

Characteristics

• Space Efficient: 使用極少的記憶體空間
• False Positive Possible: 可能會有誤判（判斷存在但實際不存在）
• No False Negative: 不會漏判（判斷不存在時一定不存在）
• Cannot Delete: 標準 Bloom Filter 不支援刪除操作

Use Case: User Registration Check

以下是使用 Bloom Filter 優化用戶註冊流程的架構圖：

  sequenceDiagram
    participant C as Client
    participant LB as Load Balancer /<br/>API Gateway
    participant BE as Backend Server
    participant RC1 as Redis Node 1<br/>(0-5460)
    participant RC2 as Redis Node 2<br/>(5461-10922)
    participant RC3 as Redis Node 3<br/>(10923-16383)
    participant DBP as DB Primary<br/>(Write)
    participant DBS as DB Secondary<br/>(Read)

    C->>LB: POST /api/register
    LB->>BE: 路由請求

    BE->>BE: 1. Bloom Filter 檢查<br/>2. CRC16(key) = hash<br/>3. slot = hash % 16384

    alt Bloom Filter 回傳 True
        alt slot in 0-5460
            BE->>RC1: 查找節點 1
        else slot in 5461-10922
            BE->>RC2: 查找節點 2
        else slot in 10923-16383
            BE->>RC3: 查找節點 3
        end

        alt 快取命中
            RC1-->>BE: Cache Hit
            BE-->>C: 返回用戶已存在
        else 快取未命中
            RC1-->>BE: Cache Miss
            BE->>DBS: 查詢用戶是否存在
            DBS-->>BE: 返回查詢結果

            alt 用戶不存在 (執行註冊)
                BE->>DBP: 寫入新用戶資料
                DBP-->>BE: 寫入完成
                DBP->>DBS: 資料同步
                BE->>RC1: 更新對應節點快取
                BE-->>C: 註冊成功
            else 用戶已存在
                BE->>RC1: 更新對應節點快取
                BE-->>C: 返回用戶已存在
            end
        end
    else Bloom Filter 回傳 False
        BE-->>C: 返回可以註冊
    end

How It Works

1. Initialization: 建立一個 bit array，所有位元初始化為 0
2. Add Element: 使用多個 hash function 計算元素的 hash 值，將對應位置設為 1
3. Query Element: 使用相同的 hash function 計算 hash 值
   • 如果所有對應位置都是 1，則元素可能存在
   • 如果任一對應位置是 0，則元素一定不存在

Applications

• Database Query Optimization: 避免查詢不存在的資料
• Web Crawler: 判斷 URL 是否已爬取
• Spam Filter: 判斷郵件是否為垃圾郵件
• CDN: 判斷內容是否已快取