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

[![表紙](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3967563/92aaa87d-10c3-42d8-87c3-e8aed00035c2.png)](https://leapcell.io/?lc_t=q_gobloom)

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

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

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

- 私たちのシステムにはキャッシュ層（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 種を基礎ハッシュとして利用

### ブルームフィルター構造

```go
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
}
```

### データの挿入

```go
// データをブルームフィルターに挿入
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にセット
  }
}
```

### データのクエリ

```go
// データが存在する可能性があるかクエリ
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
}
```

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

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

### テストコード

```go
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
}
```

## まとめ

ブルームフィルターはキャッシュシステムにおいて以下のような利点があります：

- 無効なデータベースクエリの削減：まずデータが存在する可能性を判定し、直接データベースにアクセスするのを回避できる。
- ストレージ節約：ハッシュテーブルよりメモリ効率が高く、大規模データに適する。
- クエリ効率の向上：O(1)の高速クエリで、全データを探索する必要がない。

今回は Go 言語によるシンプルなブルームフィルターの実装を紹介し、キャッシュ利用シーンにおけるデータベース負荷の最適化例を示しました。

---

### [私たちはLeapcell、Goプロジェクトのホスティングの最適解です。](https://leapcell.io/?lc_t=q_gobloom)

[![Leapcell](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3967563/75d3a84b-297d-45e0-bf9b-a182e7a9dc99.png)](https://leapcell.io/?lc_t=q_gobloom)

[Leapcell](https://leapcell.io/?lc_t=q_gobloom)は、Webホスティング、非同期タスク、Redis向けの次世代サーバーレスプラットフォームです：

**複数言語サポート**

- Node.js、Python、Go、Rustで開発できます。

**無制限のプロジェクトデプロイ**

- 使用量に応じて料金を支払い、リクエストがなければ料金は発生しません。

**比類のないコスト効率**

- 使用量に応じた支払い、アイドル時間は課金されません。
- 例: $25で6.94Mリクエスト、平均応答時間60ms。

**洗練された開発者体験**

- 直感的なUIで簡単に設定できます。
- 完全自動化されたCI/CDパイプラインとGitOps統合。
- 実行可能なインサイトのためのリアルタイムのメトリクスとログ。

**簡単なスケーラビリティと高パフォーマンス**

- 高い同時実行性を容易に処理するためのオートスケーリング。
- ゼロ運用オーバーヘッド — 構築に集中できます。

[ドキュメントで詳細を確認！](https://docs.leapcell.io/)

[![Try Leapcell](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3967563/86b49993-f6b8-46f8-9e6e-2a4ad385aa43.png)](https://leapcell.io/?lc_t=q_gobloom)

Xでフォローする：[@LeapcellHQ](https://x.com/LeapcellHQ)

---

[ブログでこの記事を読む](https://leapcell.io/blog/implementing-bloom-filters-in-go)