One Hash Bloom Filters

注: いつものように、私の公開しているすべての文章は私が手書きしたものです。

概要

ブルームフィルターは、確率的データ構造であり、「キーXはこの集合に存在するか？」という問いに、「間違いなく存在しない」または「おそらく存在する」という形で、迅速かつ低コストで回答することを可能にします。

ワークロードとハードウェアで許容できる偽陽性率を選択し、キーを集合に追加し、後でそれらの存在を確認します。

ブルームフィルターは、集合のカーディナリティ（要素数）と比較してメモリ使用量が少なく、計算コストも非常に低いです。これらの理由から、高性能データシステムで頻繁に使用されています。

例えば、データベースはインメモリのブルームフィルターを保持し、行を検索する際にディスクにアクセスする前にそれをチェックすることができます。これにより、非常に遅いディスクI/Oを大幅に節約できます。

私たちはBlueskyのバックエンドでも、あらゆる場所でそれらを使用しています。ブロック、ミュート、ラベルなどの検索において、データベースへのクエリを毎秒数百万件節約することが可能になります。例えば、「ユーザーXはユーザーYをブロックしているか？」という質問に、データベースにアクセスすることなく回答できることがよくあります。

以下は、本番環境で使用しているブルームフィルターの陽性ヒット率のここ数日間のデータです。

［画像: 本番環境のブルームフィルター陽性ヒット率の画像］

上記の黄色い線は約1%の陽性率を示しており、これは99%の時間でデータベースクエリを完全にスキップできることを意味します。これは、サイトのスケーリングと低コストでのサイト運用において極めて重要でした。

従来のブルームフィルター

ブルームフィルターはビット配列とk個のハッシュ関数で構成されます。配列のサイズとkは事前に選択し、特定の偽陽性率を達成するためにワークロードに合わせて適切にサイズ設定したいと考えます。

キーを集合に追加するには、k個のハッシュ関数でそれを処理し、各位置のビットをセットします。

キーが集合に存在するかどうかを確認するには、k回ハッシュし、ビット配列の各結果位置をチェックします。いずれかのビットがゼロであれば、そのキーは追加されていません。すべてのビットが1にセットされていれば、それは集合に含まれている可能性があります。

以下は、偽陽性の可能性のある例です。

［画像: すべてのハッシュ関数項目が1の場合、その項目は集合に含まれている可能性があることを示す画像］

そして、確実に存在しない例です。

［画像: いずれかのハッシュ関数項目がゼロの場合、その項目は集合に確実に存在しないことを示す画像］

非常にシンプルです！

ダブルハッシュ

ディスクへのアクセスよりはるかに低コストですが、高パフォーマンスシステムにとって、キーごとにk個の独立したハッシュを計算することは依然としてやや高コストです。

2008年に、KirschとMitzenmacherは、2つのハッシュで同じ出力を得られることを示す論文を発表しました。その数学は私には難解すぎますが、i
番目の位置を (hash_1 + i*hash_2) % n として導出すると、偽陽性率は実質的にk個の独立したハッシュを使用した場合と同じになります。助かりました！

Daniel Lemire（私の大きなインスピレーション源であり、彼の本を買うべきです）がメンテナンスしているbits-and-blooms/bloomは、Goで書かれた素晴らしいダブルハッシュブルームフィルターの実装です。これは128ビットのmurmur3を2回実行して4つの64ビット値を取得し、それらを組み合わせてk個のビット位置を生成します。私たちはこれをBlueskyで長期間本番環境で使用していました。

Blueskyのバックエンドでは、プロセスが起動するたびに、ブロック、ミュート、リストアイテムなどのSELECT * FROM ...を実行し、すべてのアイテムをブルームフィルターに追加します。また、リアルタイムのatprotoファイアホースコンシューマーが（プロセス起動中であっても）ブルームフィルターにアイテムを挿入しているため、注意しないと競合状態が発生する可能性があります。

bits-and-bloomsライブラリの問題点は、内部的にスレッドセーフではないため、データ競合を避けるためにすべてのブルームフィルターアクセスをmutexでラップする必要があったことです。pprofによると、mutexの競合が実際にプロセス起動時のボトルネックになっていました。単一のデプロイが、これのために90分もかかっていたのです！

そこで、私の同僚であるJasmineはライブラリをフォークし、同じロジックをmutexなしで安全に実行するatomic-bloomを作成しました。これにより、競合が大幅に減少し、mutexベースのアプローチよりもはるかに高速になりました。デプロイ時間は90分から約15分に短縮され、より迅速かつ自信を持って出荷できるようになりました。素晴らしいです！

One Hash

さらに進むことはできるでしょうか？

Blueskyにとって、答えはいいえです。私たちの当初の問題は競合であり、ハッシュ関数の数やその他の要因ではなかったため、アムダールの法則により、顕著な影響をもたらすさらなる速度向上は得られませんでした。しかし、さらに深く掘り下げて新しいことを学ぶのは楽しいことです！

ブルームフィルター技術に関する研究の一環として、Luらによる、単一のハッシュのみを使用してブルームフィルターを行う方法を示す、さらに多くの数学を使用したこの論文に出会いました。

その仕組みの概要は以下の通りです。

• 1つの大きなビット配列の代わりに、それを固定サイズのk個の配列パーティションに分割します。
• 各パーティションは異なるサイズを持ち、すべてのサイズは互いに素です。つまり、2つのサイズは1以外の共通因数を持ちません。
• 与えられたキーを1回ハッシュしてhashを取得します。
• パーティションpのビット位置は hash%size_p（パーティションのサイズ）です。
• k個のパーティションがあるため、その単一のハッシュからチェックするk個のビット位置が得られます。
• これらのk個のビット位置は、他のブルームフィルタータイプと同様に使用できます！

この技術を手に、私はjcalabro/gloomを作成しました。これはGoで書かれたワンハッシュブルームフィルター（OHBF）の実装です。これは過去9ヶ月間Blueskyのバックエンドで稼働しており、非常に良好な状態を保っています。また、私たちの高性能同期サービスであるjetstreamでも使用されています。

使用例を以下に示します。

package main

import (
	"fmt"
	"sync"

	"github.com/jcalabro/gloom"
)

func main() {
	// スレッドセーフなアトミックブルームフィルターを作成します。
	// - 期待容量: 100万要素
	// - 概算偽陽性率: 1%
	f := gloom.NewAtomic(1_000_000, 0.01)

	var wg sync.WaitGroup
	defer wg.Wait()

	for i := range 8 {
		wg.Go(func() {
			for j := range 100000 {
				str := fmt.Sprintf("key-%d-%d", i, j)

				if f.TestString(str) {
					// キーはセットに含まれていないため、常に偽陽性です
					fmt.Printf("found a false positive: %s\n", str)
				}

			f.AddString(str)
			}
		})
	}
}

さて、内部でどのように機能するかを詳細に見ていきましょう。キーをチェックする際にブロックインデックスとhを選択する方法を示すサンプルGoコードを以下に示します。

hash := xxh3.Hash128(key) // 128ビットハッシュを計算

block := hash.Hi % numBlocks // 上位64ビットでブロックを選択
h := hash.Lo                 // 下位64ビットがチェックするハッシュ

次に、ブルームフィルターを次のようにチェックします。

［画像: ワンハッシュブルームフィルターの仕組みを示す画像］

単一ハッシュであることに加えて、いくつかの楽しいパフォーマンス最適化手法も採用しています。

まず、一般的なCPUキャッシュラインサイズに合わせるために、ブルームフィルターを多数の64バイトブロックに分割します。次に、Goのアロケータはそれらのブロック割り当てがキャッシュアラインメントを保証しないため、わずかに過剰に割り当て、アラインメントを保証するためにunsafeを使用します。実装はこちらを参照してください。

これらの2つの技術を組み合わせることで、最悪の場合でも、ブルームフィルターのルックアップは1回のキャッシュミスで済むことが保証されます。素晴らしいです！

Daniel Lemireによる別の興味深い最適化は、高価な除算命令を必要とするモジュロ演算の代わりに、単一のMUL命令でチェックするブロックを選択できるようにします。

私が話す最後の興味深い最適化は、ShardedAtomicFilterです。Blueskyでは、高性能なベアメタルサーバーの大規模なフリートを管理していました。それらのシステムから最大限のパフォーマンスを引き出すには、複数のコアが同じデータで競合するのを避けることが重要です。ShardedAtomicFilterは、書き込みを多くのバックエンドフィルターシャードに分散させることで、競合の可能性を減らします。

結論

ブルームフィルター（およびroaring bitmaps）は世界を動かしています。

これがブルームフィルターの仕組みについての興味深い探求であったことを願っています。面白い低レベルのエンジニアリングの詳細に興味がある場合は、Blueskyで私をフォローするか、atproto、RSSなどでこのブログを購読することを検討してください。

余談ですが、私は最先端を押し上げる新しいオブザーバビリティスイートに取り組んでいます。GitHubでスターを付けてください。近いうちにさらに詳しい議論にご期待ください！