Blueskyのデプロイを90分から15分に短縮した、ハッシュ1回のBloomフィルタ

One Hash Bloom Filters

Bloomフィルタは「このキーは集合にない」を高速に判定できる確率的データ構造で、Blueskyのバックエンドでもブロックやミュートの照会に多用され、毎秒数百万のScyllaクエリを削減している。従来は複数ハッシュが必要だったが、Luらの論文の手法を用い、サイズが互いに素な複数のパーティションに1回のハッシュだけでビット位置を決める実装gloomを公開。キャッシュライン単位のブロック化やアトミックなシャーディングで競合を抑え、9か月間本番で稼働している。