ドキュメント
Computer Science
データ構造
Hash Tables
Bloom Filter

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: ビット配列はいれつを作成さくせいし、全すべてのビットを0に初期化しょきか
  2. Add Element: 複数ふくすうのハッシュ関数かんすうで要素ようそのハッシュ値あたいを計算けいさんし、対応たいおうする位置いちを1に設定せってい
  3. Query Element: 同おなじハッシュ関数かんすうでハッシュ値あたいを計算けいさん
    • 全すべての対応たいおう位置いちが1なら、要素ようそは**存在そんざいする可能性かのうせいあり**
    • いずれかの対応たいおう位置いちが0なら、要素ようそは**確実かくじつに存在そんざいしない**

Applications

  • Database Query Optimization: 存在そんざいしないデータのクエリを回避かいひ
  • Web Crawler: URLが既すでにクロールされたかを判断はんだん
  • Spam Filter: メールがスパムかどうかを判断はんだん
  • CDN: コンテンツが既すでにキャッシュされているかを判断はんだん
Hash