Goによるブルームフィルター

Posted at 2025-05-15

キャッシュ設計において、私たちはしばしば頭を悩ませる問題に直面します。それは、「無効なクエリ」が大量に発生し、データベースへの負荷が急増することです。例えば、ユーザーが存在しないデータをリクエストした場合、通常はデータベースにクエリを投げますが、データベースからは「見つからない」という応答が返ってきます。このようなリクエストが多数あると、データベースは意味のないクエリ処理に忙殺され、システムパフォーマンスに悪影響を及ぼします。それでは、クエリの前に「データが存在する可能性があるかどうか」を知る方法はないのでしょうか？ここで役立つのがブルームフィルターです。

従来のキャッシュシナリオでの問題点

次のようなシナリオを想定してください：

私たちのシステムにはキャッシュ層（Redis）とデータベース層（MySQL）がある。
ユーザーが特定のデータをリクエストすると、まずキャッシュを検索し、ヒットすればそのまま返す。
キャッシュに存在しない場合はデータベースを検索し、データベースにもなければ「見つからない」と返す。

一見すると、この設計は合理的に見えます。しかし実際の運用では、大量の無効なクエリが発生する可能性があります：

ユーザーが ID=99999999 のデータをリクエスト
    -> キャッシュに存在しない
    -> データベースで ID=99999999 を検索
    -> データベースから「見つからない」と返される

ユーザーが存在しないデータを何度もリクエストすると、以下の問題が生じます：

キャッシュが役立たない：毎回データベースを検索するため、キャッシュ層が意味を成さない。
データベースの負荷が増大：大量の無効なリクエストがデータベースの応答を遅くする。

一般的な最適化案としては、無効なクエリを事前にフィルタリングし、既に「存在しない」と確定しているデータについては直接エラーを返し、データベースに問い合わせないことです。これこそがブルームフィルターが活躍する場面です。

ブルームフィルターとは？

ブルームフィルター（Bloom Filter）は、高効率な集合クエリアルゴリズムであり、ある値が「存在する可能性があるか」あるいは「絶対に存在しないか」を素早く判定できます。簡単に言えば：

ブルームフィルターが「存在しない」と言えば、本当に存在しません。そのままエラーを返し、データベースに問い合わせる必要はありません。
ブルームフィルターが「存在する可能性あり」と言えば、念のためデータベースで確認します。

ブルームフィルターの基本的なロジックはとてもシンプルです：

複数のハッシュ関数を用いて、データを固定長のビット配列にマッピングする。
クエリ時には、同じハッシュ関数で対象データを計算し、該当するビットがすべて 1 かどうかを確認する。
もし一部のビットが 0 なら、そのデータは絶対に存在しません。
すべてのビットが 1 なら、データが存在する可能性があります（ただし誤判定の可能性もある）。

メリット：

メモリ効率が高い。従来のハッシュテーブルより少ない空間で済む。
クエリが高速で、計算量はほぼ O(1)。
効率的なフィルタリングで、データベースへの負荷を減らせる。

デメリット：

誤判定の可能性がある（ただしハッシュ関数の数を調整すれば誤判定率を下げられる）。
データの削除ができない（一般的には大量データやキャッシュ用途に使う）。

ブルームフィルターのデータ構造

ブルームフィルターのコアとなるデータ構造は、以下の 2 つです：

ビット配列（bit array）：ある値が存在するかどうかを記録する。初期状態は全て 0。
複数のハッシュ関数：データに対してビット位置を計算するために使う。

例：

"Leap"を挿入すると、ハッシュ計算後、ビット配列の2、5、8、9番目にマッピングされる：
インデックス：  0  1  2  3  4  5  6  7  8  9
値：            0  0  1  0  0  1  0  0  1  1

"Leap"を検索する場合：

"Leap"のハッシュ値を計算し、2、5、8、9 の位置がすべて 1 なら「存在する可能性あり」と判断する。
"cell"を計算し、どこかのビットが 0 なら「存在しない」と即座に判定できる。

Go 言語によるブルームフィルターの実装

以下は Go 言語によるブルームフィルターの実装例です：

BloomFilter 構造体
コンストラクタ NewBloomFilter。期待する要素数と許容誤判率から、最適なビット配列サイズ(m)とハッシュ関数数(k)を自動算出
コンストラクタ NewBloomFilterWithMK。m と k を直接指定できる
Add メソッド：要素の追加
MightContain メソッド：要素が存在する可能性があるかチェック（誤判定の可能性はあるが、漏れはしない）
getHashes 内部メソッド：ダブルハッシュで k 個のハッシュ値を生成。ここでは FNV-1a ハッシュの 2 種を基礎ハッシュとして利用

ブルームフィルター構造

package main

import (
  "fmt"
  "hash/fnv"
)

// ブルームフィルター構造体
type BloomFilter struct {
  m    uint64 // ビット配列サイズ（bit数）
  k    uint64 // ハッシュ関数数
  bits []byte // ビット配列
}

// ブルームフィルターの生成
func NewBloomFilter(expectedN uint64, falsePositiveRate float64) *BloomFilter {
  m, k := estimateParameters(expectedN, falsePositiveRate)
  if m == 0 || k == 0 {
    panic("Invalid parameters for Bloom filter: m or k is zero")
  }
  return NewBloomFilterWithMK(m, k)
}

// estimateParameters：期待要素数nと誤判率pから最適なm, kを算出
// m = - (n * ln(p)) / (ln(2))^2
// k = (m / n) * ln(2)
func estimateParameters(n uint64, p float64) (m uint64, k uint64) {
  if n == 0 || p <= 0 || p >= 1 {
    return 1000, 10
  }
  mFloat := -(float64(n) * math.Log(p)) / (math.Ln2 * math.Ln2)
  kFloat := (mFloat / float64(n)) * math.Ln2

  m = uint64(math.Ceil(mFloat))
  k = uint64(math.Ceil(kFloat))

  if k < 1 {
    k = 1
  }
  return
}

// NewBloomFilterWithMK：指定のm, kでブルームフィルターを生成
func NewBloomFilterWithMK(m, k uint64) *BloomFilter {
  if m == 0 || k == 0 {
    panic("Invalid parameters for Bloom filter: m or k is zero")
  }
  numBytes := (m + 7) / 8
  return &BloomFilter{
    m:    m,
    k:    k,
    bits: make([]byte, numBytes),
  }
}

// getHashes：ダブルハッシュ法でデータからk個のハッシュ値を生成
func (bf *BloomFilter) getHashes(data []byte) []uint64 {
  hashes := make([]uint64, bf.k)

  // FNV-1aの2種（またはseed）を基礎ハッシュ関数とする
  h1 := fnv.New64()
  h1.Write(data)
  hash1Val := h1.Sum64()

  h2 := fnv.New64a()
  h2.Write(data)
  hash2Val := h2.Sum64()

  for i := uint64(0); i < bf.k; i++ {
    if hash2Val == 0 && i > 0 {
      hash2Val = 1
    }
    hashes[i] = (hash1Val + i*hash2Val) % bf.m
  }
  return hashes
}

データの挿入

// データをブルームフィルターに挿入
func (bf *BloomFilter) Add(data []byte) {
  hashes := bf.getHashes(data)
  for _, h := range hashes {
    byteIndex := h / 8                     // バイトインデックス取得
    bitOffset := h % 8                     // バイト内ビット位置
    bf.bits[byteIndex] |= (1 << bitOffset) // 対応ビットを1にセット
  }
}

データのクエリ

// データが存在する可能性があるかクエリ
func (bf *BloomFilter) MightContain(data []byte) bool {
  hashes := bf.getHashes(data)
  for _, h := range hashes {
    byteIndex := h / 8
    bitOffset := h % 8
    if (bf.bits[byteIndex] & (1 << bitOffset)) == 0 {
      // どれか1つのハッシュビットが0なら、要素は確実に存在しない
      return false
    }
  }
  // 全てのビットが1なら、存在する可能性あり
  return true
}

ブルームフィルターのリセット

// Reset：ブルームフィルターを初期化（全ビットを0にする）
func (bf *BloomFilter) Reset() {
  for i := range bf.bits {
    bf.bits[i] = 0
  }
}

テストコード

func main() {
  // 例：期待要素数1000、誤判率1%
  expectedN := uint64(1000)
  falsePositiveRate := 0.01

  m, k := estimateParameters(expectedN, falsePositiveRate)
  fmt.Printf("Estimated parameters: m = %d, k = %d\n", m, k)

  bf := NewBloomFilter(expectedN, falsePositiveRate)
  // または bf := NewBloomFilterWithMK(m,k)

  // 要素を追加
  item1 := []byte("apple")
  item2 := []byte("banana")
  item3 := []byte("cherry")

  bf.Add(item1)
  bf.Add(item2)

  fmt.Printf("MightContain 'apple': %t\n", bf.MightContain(item1))           // true
  fmt.Printf("MightContain 'banana': %t\n", bf.MightContain(item2))          // true
  fmt.Printf("MightContain 'cherry': %t\n", bf.MightContain(item3))          // false（未追加のためfalse）
  fmt.Printf("MightContain 'grape': %t\n", bf.MightContain([]byte("grape"))) // false（これもfalse）

  bf.Reset()
  fmt.Println("After Reset:")
  fmt.Printf("MightContain 'apple': %t\n", bf.MightContain(item1)) // false
}