0. Motivation

SSTable（Sorted String Table）は、大規模なデータベースシステムにおいて、高速な書き込み性能を実現するためのデータ構造として広く利用されています[g]。しかし、その設計上、読み込み操作に特化していないません。一方、SSTableを採用しているにも関われらず、Cassandraは高速な読み込み性能で知られており、その背後にあるデータ構造に興味を持ちました。

そちらの要因の一つにBloom filterと呼ばれるデータ構造があります。そのため、本記事ではBloom filterの数学的背景とCassandraでどう利用されているかについて解説し、その効果を理解することを目的とします。

1. Bloom filterとは？

Bloom filterは、集合の要素が存在するかを効率的にチェックするためのデータ構造です。具体的には、ある要素が集合に「存在する可能性がある」か「確実に存在しない」かを返します。誤って存在すると判定される「偽陽性」は発生する可能性がありますが、「偽陰性」（実際には存在する要素を存在しないと判定すること）は発生しません。

2. Bloom filterの数式的背景

2.1. ビット配列とハッシュ関数

Bloom filterは次の2つの基本要素を持ちます：

ビット配列：長さmのビット列B。初期状態ではすべて0で初期化されています。
ハッシュ関数：独立なハッシュ関数の集合H = {h_1, h_2, ..., h_k}。各関数は、要素をビット配列のインデックスにマッピングします。

2.2. 要素の追加

集合に要素xを追加する際、次のステップを踏みます：

k個のハッシュ関数h_i(x)を使って、xをk個のビット配列のインデックスにマッピングする。
それらのインデックスに対応するビットを1にセットする。

ビット配列Bの更新は次のように表せます：

\begin{aligned}
B[h_i(x)] = 1 \quad (i = 1, 2, ..., k)
\end{aligned}

2.3. 要素の存在判定

要素yが集合に含まれているかを確認するには、次の手順を実行します：

k個のハッシュ関数h_i(y)を使って、ビット配列のk個の位置を確認。
すべてのビットが1であれば、yが集合に存在する可能性があると判定し、1つでも0があれば、yは確実に集合に存在しないと判定します。

この手順は次の数式で表せます：

\begin{aligned}
\forall i \in \{1, 2, ..., k\}, B[h_i(y)] = 1 \quad \text{ならば、} \quad y \text{は存在する可能性がある}
\end{aligned}

2.4. 誤判定率（偽陽性）

Bloom filterには、要素が存在しない場合でも「存在する可能性がある」と誤って判定する偽陽性が発生することがあります。その確率を数学的に導出します。

まず、ビット配列の各ビットが1になる確率を考えます。要素n個を filterに追加したとき、任意のビットが1になる確率は次の式で近似されます：

\begin{aligned}
p_1 = 1 - \left(1 - \frac{1}{m}\right)^{kn}
\end{aligned}

ここで、mはビット配列の長さ、kはハッシュ関数の数、nは集合の要素数です。

次に、yが存在しない要素だと仮定して、その要素がすべてのk個のハッシュ関数で1を指す確率、すなわち偽陽性率は次のように求められます：

\begin{aligned}
P(\text{偽陽性}) = \left( p_1 \right)^k = \left(1 - \left(1 - \frac{1}{m}\right)^{kn}\right)^k
\end{aligned}

2.5. 最適なハッシュ関数の数

偽陽性率を最小化するためには、最適なハッシュ関数の数kを選ぶ必要があります。この値は、近似計算を行うと次の式で最適化されます[3]：

\begin{aligned}
k = \frac{m}{n} \ln 2
\end{aligned}

2.6. まとめると

偽陽性率はビット配列のサイズm、ハッシュ関数の数k、および要素数nに依存します。
最適なハッシュ関数の数は、与えられたビット配列のサイズと要素数の値から計算できます。

3. 数式を使った具体的な例

次に、具体例を使って、上記の数式がどのように適用されるかを示します。

例

ビット配列のサイズm = 1000、ハッシュ関数の数k = 5、要素数n = 100の場合を考えます。

存在しない要素についてのビットが1になる確率は：

\begin{aligned}
p_1 = 1 - \left(1 - \frac{1}{1000}\right)^{5 \times 100}　\approx 0.393
\end{aligned}

次に、偽陽性率は：

\begin{aligned}
P(\text{偽陽性}) = (0.393)^5 \approx 0.009
\end{aligned}

したがって、この filterの偽陽性率は約0.9%であることがわかります。

4. Bloom filterに関連する参考資料

Bloom filterの初期の発明は、Bloomさんによる「Space/Time Trade-offs in Hash Coding with Allowable Errors」という論文[1]で説明されました。
さらに、偽陽性率やパフォーマンスを改善するためのバリエーション（Counting Bloom Filterなど）も研究されているそうです[2]。

Bloom, Burton H. "Space/time trade-offs in hash coding with allowable errors." Communications of the ACM 13.7 (1970): 422-426.
Broder, Andrei, and Michael Mitzenmacher. "Network applications of bloom filters: A survey." Internet mathematics 1.4 (2004): 485-509.
Yuichi Kiri, Bloom Filterの数理 #algorithm - Qiita

（上記リンクは2024/10/18アクセスしました）

5. CassandraにおけるBloom filterの具体的な利用

Bloom filterがCassandraに使われていると冒頭で説明しましたが、それはシステム全体の一部に過ぎません。具体的にBloom filterはCassandraの複数ノード一つ一つに複数存在するSSTableから不要なディスクアクセスを避けるために利用されています。以下では、Bloom filterがCassandraでどのように活用されているかを詳しく説明します。

5.1. Cassandraでのデータ検索の流れ

5.1.1. キーのハッシュ化とノードの特定[a],[b]

クライアントは、検索対象のパーティションキーを持ってリクエストを送信します。
キーにハッシュ関数を適用し、トークンリング上で担当ノードを計算します。
- 具体的には、キーにMurmurhashなどのハッシュ関数を適用して得られたトークン値をトークンリング上に配置します。各ノードはこのリング上で特定のトークン範囲を担当しており、キーのトークン値が属する範囲のノードがデータの保管先となります。
このことで、特定のNodeだけ確認をすれば良い状態になります。

5.1.2. ノード内でのMemtableとSSTableの検索[c][e]

次に実際にどこにデータがあるかを確認します。
Memtableの検索：まず、メモリ上の最新データであるMemtableをチェックします。
Bloom filterによるSSTableのフィルタリング：
- Memtableにデータがない場合、ディスク上のSSTableを検索する必要があります。
- 各SSTableのBloom filterをチェックし、キーが存在する可能性があるSSTableのみを対象とし検索をするようにします。
つまり、Bloom filterを使用することで必要なSSTableのみを確認することができます。

（ここではBloom filterに関連するところだけ説明をしていますが、他にも様々な工夫があります）

5.2. データ検索におけるBloom filterの役割[f]

5.2.1. ノード内の複数のSSTable

SSTableは、データの書き込み時の効率が非常に良いデータ構造を持つファイルで複数存在します。[h]
一方で読み込み時に、これら全てのSSTableを順番にチェックすると、ディスクI/Oが増加し、パフォーマンスが低下します。

5.2.2. Bloom filterの活用

各SSTableには、そのSSTableに含まれる全てのキーに対するBloom filterが作成されます。
データ検索時、まず各SSTableのBloom filterをメモリ上でチェックします。
- 検索対象のキーがそのSSTableに存在する可能性があるかを高速に判定します。
キーが存在しないSSTableをスキップすることで、不要なディスクアクセスを削減できます。

5.3. Bloom filterの数式とCassandraの関連

3章で説明したBloom filterの数式をCassandraにおける各SSTableのBloom filterに適用してみます。

つまり、ビット配列のサイズ（m）、ハッシュ関数の数（k）、SSTable内のキー数（n）が、各Bloom filterの偽陽性率に影響します。

5.3.1. 偽陽性率の影響

偽陽性率（P(偽陽性})）は、各SSTableのBloom filterで計算されます。
あるNode内のSSTableの数（S）が増えると、そのNodeに関して偽陽性によるディスクアクセスの確率も増加します。

5.3.2. あるNode内の全体の偽陽性率の計算

取得しようとするキーが存在しない場合において、Bloom filterの偽陽性によりディスクアクセスが発生する確率は以下のようになります：

\begin{aligned}
P_{\text{全体の偽陽性}} = 1 - \left(1 - P(\text{偽陽性・SSTable})\right)^{S}
\end{aligned}

(P(偽陽性・SSTable))：1つのSSTableのBloom filterの偽陽性率
(S)：ノード内のSSTableの総数

この式は、各SSTableのBloom filterが独立であると仮定しています。

5.4. SSTableの数とBloom filterの関係

SSTableの数（S）が増えると、Bloom filterのチェック回数も増加します。
各Bloom filterの偽陽性率が一定でも、全体の偽陽性率はSSTableの数に比例して上昇します。
したがって、一つ一つのSSTableに関係のあるBloom filterの最適化だけではなく、あるNodeにあるSSTableの数を管理することもCassandraのパフォーマンスにおいて重要です。

5.4.1. 具体例

例えば、各SSTableの偽陽性率が1%で、ノード内に50個のSSTableがある場合：

\begin{aligned}
P_{\text{全体の偽陽性}} = 1 - \left(1 - 0.01\right)^{50} \approx 39.4\%
\end{aligned}

存在しないキーでも、約39.4%の確率でディスクアクセスが発生します。
これはパフォーマンスに影響を与えるため、コンパクションによりSSTableの数を減らすなどの対策が必要です。[d]

実際にSSTableの数が10個まで減らせた場合は以下のようになります：

\begin{aligned}
P_{\text{全体の偽陽性}} = 1 - \left(1 - 0.01\right)^{10} \approx 9.5\%
\end{aligned}

5.5. まとめ

Bloom filterはCassandraにおいて、不要なディスクアクセスを避けるために重要な役割を果たしています。
ただし、SSTableに関する最適化としてBloom filterを調整しても、Node内にあるSSTableの数を減らさない場合はCassandraの読み込みのパフォーマンスは悪化してしまいます。

6. Cassandra 参考資料

以下の資料は2024/10/18にアクセスをしています。

a. How data is distributed across a cluster (using virtual nodes) | Apache Cassandra 3.0
b. Partitioners | Apache Cassandra 3.x
c. データはどのようにして読み取られるか | DSE 6.7アーキテクチャー・ガイド
d. Compaction | Apache Cassandra Documentation
e. Storage Engine | Apache Cassandra Documentation
f. Bloom Filters | Apache Cassandra Documentation
g. データはどのように書き込まれるか | DSE 5.1アーキテクチャー・ガイド
h. What is a SSTable? Definition & FAQs | ScyllaDB

7. 最後に

自分自身、CassandraやBloom filter, SSTableに対しては雰囲気でしか理解できていなかったのですが、ブログを書いたことで頭の整理になり良かったです。

また、ここで取り扱った内容はCassandraのアーキテクチャのごく一部であり他にも自分が雰囲気でしか理解できていないことがたくさんあります（Gossip Protocolの話、Consistencyの話やVector Search(ANN)の話、Compactionについてもっと深い話など）。また興味が出たタイミングで深ぼってみたいと思います。

なにか誤りや質問があればコメントくださればと思います！
ここまでありがとうございました :)