Goでの効率的なキャッシュのためのBloomフィルタの実装

キャッシュ設計において、私たちはしばしば厄介な問題に遭遇します。それは、大量の「無効なクエリ」がデータベースに莫大な圧力をかけることです。例えば、ユーザーが存在しないデータを要求すると、通常はデータベースにクエリを送り、「見つかりません」という結果が返されます。このようなリクエストが多いと、データベースはこれらの無意味なクエリの処理に追われ、システムパフォーマンスに影響を与えます。では、クエリを行う前に、データが「存在する可能性があるか」を事前に知る方法はないのでしょうか？ここでBloomフィルタが登場します。

従来のキャッシュシナリオにおける問題点

次のようなシナリオを想像してみてください。

• システムには**キャッシュ層（Redis）とデータベース層（MySQL）**があります。
• ユーザーが何らかのデータを要求すると、まずキャッシュを確認します。キャッシュヒットした場合、結果を直接返します。
• データがキャッシュにない場合、データベースにクエリを送信します。データベースにもデータがない場合、「見つかりません」という結果をユーザーに返します。

一見すると、この設計は合理的であるように思えます。しかし実際には、大量の無効なクエリに遭遇する可能性があります。

User requests data with ID=99999999
    -> Not found in cache
    -> Query database for ID=99999999
    -> Database returns: not found

存在しないデータをユーザーが繰り返し要求すると、最終的には次のようになります。

• キャッシュが機能しない：すべてのリクエストがデータベースにクエリを送信し、キャッシュ層が無意味になる。
• 過剰なデータベース負荷：多数の無効なリクエストがデータベースの応答を遅らせる。

一般的な最適化は、無効なクエリを事前に除外することです。つまり、存在しないことがすでにわかっているデータをすぐに返し、データベースにクエリを送信しないようにします。これはまさにBloomフィルタが活躍する場面です。

Bloomフィルタとは？

Bloomフィルタは、効率的な集合メンバーシップクエリアルゴリズムです。値が存在する可能性があるか、または確実に存在しないかを迅速に判断できます。簡単に言うと：

• Bloomフィルタが「存在しない」と判断した場合、それは本当に存在しないため、すぐにエラーを返すことができます。データベースにクエリを送信する必要はありません。
• Bloomフィルタが「存在する可能性がある」と判断した場合、データベースにクエリを送信して確認します。

Bloomフィルタの基本的なロジックは単純です。

• 複数のハッシュ関数を使用して、データを固定サイズのビット配列にマッピングします。
• クエリを実行するときは、ターゲットデータに対して同じハッシュを計算し、対応するすべてのビットが1に設定されているかどうかを確認します。
• それらのビットのいずれかが0の場合、データは確実に存在しません。
• すべてのビットが1の場合、データは存在する可能性があります（特定の間違い陽性率で）。

利点：

• メモリを節約—従来のハッシュテーブルよりも占有スペースが少ない。
• 高速なクエリ—時間計算量はO(1)に近い。
• 効率的なフィルタリング—データベースの負荷を軽減。

短所：

• 間違い陽性の可能性（ただし、ハッシュ関数の数を調整することで間違い陽性率を下げることができます）。
• データを削除できない（通常、ビッグデータストリームまたはキャッシュシナリオで使用されます）。

Bloomフィルタのデータ構造

Bloomフィルタの中核となるデータ構造は、2つのコンポーネントです。

• ビット配列： 特定の値が存在するかどうかを記録するために使用されます。すべてのビットは0に初期化されます。
• 複数のハッシュ関数： データに対応するビット位置を計算するために使用されます。

例：

「Leap」を挿入します。ハッシュ計算後、ビット配列の2、5、8、および9の位置にマッピングされます。
Index:   0  1  2  3  4  5  6  7  8  9
Value:   0  0  1  0  0  1  0  0  1  1

「Leap」をクエリする場合：

• 「Leap」のハッシュを計算し、2、5、8、および9の位置がすべて1であることを見つけます。これは存在する可能性があることを示します。
• 「cell」のハッシュを計算し、一部のビットが0であることを見つけたため、すぐに「存在しません」として返されます。

GoでのBloomフィルタの実装

以下は、Goを使用したBloomフィルタの実装です。

• BloomFilter構造体。
• コンストラクターNewBloomFilter。これは、予想される要素数と許容される間違い陽性率に基づいて、最適なビット配列サイズ（m）とハッシュ関数の数（k）を自動的に計算します。
• コンストラクターNewBloomFilterWithMK。これにより、mとkを直接指定できます。
• 要素を追加するためのAddメソッド。
• 要素が存在する可能性があるかどうかを確認するためのMightContainメソッド（間違い陽性が発生する可能性がありますが、間違い陰性は決して発生しません）。
• 内部getHashesメソッド。これは、ダブルハッシュを使用してk個のハッシュ値を生成します。ここでは、FNV-1aハッシュアルゴリズムの2つのバリアントを基本ハッシュとして使用します。

Bloomフィルタの構造

package main

import (
  "fmt"
  "hash/fnv"
)

// Bloom filter struct
type BloomFilter struct {
  m    uint64 // Size of bit array (number of bits)
  k    uint64 // Number of hash functions
  bits []byte // Bit array
}

// Create a Bloom filter
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 calculates the optimal m and k based on the expected number of elements n and the false positive rate p
// 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 creates a Bloom filter using the specified m and 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 uses double hashing to generate k hash values for the data
func (bf *BloomFilter) getHashes(data []byte) []uint64 {
  hashes := make([]uint64, bf.k)

  // Use two different versions (or seeds) of FNV-1a as base hash functions
  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
}

データの挿入

// Insert data into the Bloom filter
func (bf *BloomFilter) Add(data []byte) {
  hashes := bf.getHashes(data)
  for _, h := range hashes {
    byteIndex := h / 8                     // Find the byte index
    bitOffset := h % 8                     // Find the bit offset within the byte
    bf.bits[byteIndex] |= (1 << bitOffset) // Set the corresponding position to 1
  }
}

データのクエリ

// Check whether data might exist
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 {
      // If any bit corresponding to a hash is 0, the element definitely does not exist
      return false
    }
  }
  // If all bits corresponding to hashes are 1, the element might exist
  return true
}

Bloomフィルタのリセット

// Reset clears the Bloom filter (sets all bits to 0)
func (bf *BloomFilter) Reset() {
  for i := range bf.bits {
    bf.bits[i] = 0
  }
}

テストコード

func main() {
  // Example: expect 1000 elements, false positive rate 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)
  // Or bf := NewBloomFilterWithMK(m, k)

  // Add some elements
  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 (should be false, as it wasn't added)
  fmt.Printf("MightContain 'grape': %t\n", bf.MightContain([]byte("grape"))) // false (should also be false)

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

まとめ

Bloomフィルタは、キャッシュシステムにおいて次の点で役立ちます。

• 無効なデータベースクエリの削減：データが存在する可能性があるかどうかを最初に判断し、データベースに直接アクセスすることを回避します。
• ストレージスペースの節約：ハッシュテーブルよりもメモリ使用量が少なく、大規模データに適しています。
• クエリ効率の向上：クエリの時間計算量はO(1)であり、データセット全体を走査する必要はありません。

Goを使用して単純なBloomフィルタを実装し、それをキャッシュシナリオに適用して、データベースの負荷を最適化しました。

---

Leapcellは、Goプロジェクトをホストするための最適な選択肢です。

Leapcellは、Webホスティング、非同期タスク、およびRedis向けの次世代サーバーレスプラットフォームです。

多言語サポート

• Node.js、Python、Go、またはRustで開発できます。

無制限のプロジェクトを無料でデプロイ

• 使用量に応じてのみ料金が発生します — リクエストも料金もかかりません。

比類のないコスト効率

• アイドル料金なしの従量課金。
• 例：25ドルで平均応答時間60msで694万リクエストをサポートします。

合理化された開発者エクスペリエンス

• 簡単なセットアップのための直感的なUI。
• 完全に自動化されたCI/CDパイプラインとGitOps統合。
• 実用的な洞察のためのリアルタイムメトリックとロギング。

容易なスケーラビリティとハイパフォーマンス

• 高い同時実行性を容易に処理するための自動スケーリング。
• 運用上のオーバーヘッドはゼロ—構築に集中するだけです。

詳細については、ドキュメントをご覧ください。

Xでフォローしてください：@LeapcellHQ