MySQLのインデックスとCassandraのスピードが異なる理由 ～アルゴリズムと計算量、アーキテクチャから読み解く～

# TL;DR

「NoSQLは速いんです！」とよく言われていますが、実際になんで速いか理解している人は少ないのではないでしょうか。本記事では、MySQLとCassandraのデータアクセスの仕組みと計算量を比較し、その違いを解説します。

# 1. データベースの基本概要

## MySQL
MySQLは、リレーショナルデータベース管理システム（RDBMS）の代表格であり、ACID特性を強くサポートしています。トランザクション処理や複雑なクエリ、ジョイン操作に優れており、従来のウェブアプリケーションやビジネスアプリケーションで広く利用されています。

- [MySQL](https://www.mysql.com/jp/)

## Cassandra
一方、Cassandraは分散型のNoSQLデータベースで、高いスケーラビリティと可用性を誇ります。大規模なデータセットやリアルタイム分析、書き込みが多いシナリオに適しており、マスター・スレーブ構造を持たず、全ノードが対等に動作する点が特徴です。Cassandraはデータを自動的にシャーディング（分割）し、トークンリングを用いてデータを均等に分散配置します。

- [Welcome to Apache Cassandra’s documentation! | Apache Cassandra Documentation](https://cassandra.apache.org/doc/latest/)

# 2. 計算量の定義：Nとは何か

計算量を議論する際に重要なのは、**$N$の定義**です。ここでの$N$は「データベース内の対象となるデータの総数」を指します。具体的には、検索や挿入、削除などの操作対象となるレコード数を表します。この定義に基づいて、各アルゴリズムやデータ構造の性能を評価します。

# 3. MySQLのインデックス構造：B-tree

MySQLで最も一般的に使用されるインデックス構造はB-tree（バランスドツリー）です。B-treeインデックスは、以下のような特徴を持ちます。

- **階層的構造**: B-treeはノードが階層的に配置されており、検索時にはルートノードからリーフノードまで順次辿っていきます。
- **バランスの取れた高さ**: 全てのリーフノードが同じ深さにあるため、検索にかかる時間が一定です。
- **範囲クエリに強い**: B-treeは連続した範囲のデータを効率的に検索できるため、`BETWEEN`や`LIKE`などのクエリに適しています。

:::note warn
B-tree以外にも、MySQLではハッシュインデックスもありますが、ハッシュインデックスは等値検索に特化しており、範囲クエリには向いていません。よくまとめられている記事はこちらです：
1. [mysql - B-Tree vs Hash Table - Stack Overflow](https://stackoverflow.com/questions/7306316/b-tree-vs-hash-table)
2. [MySQL :: MySQL 5.7 Reference Manual :: 8.3.8 Comparison of B-Tree and Hash Indexes](https://dev.mysql.com/doc/refman/5.7/en/index-btree-hash.html)
:::

## 計算量
B-treeの主な操作における計算量は以下の通りです：

- **検索**: **$O(\log N)$**
- **挿入**: **$O(\log N)$**

B-treeは対数時間で操作を完了するため、大規模データでも比較的効率的に動作します。しかし、データ量が増加すると、操作回数も対数的に増加し、特にディスクI/Oが多く発生する場合はパフォーマンスに影響を及ぼす可能性があります。

- 詳細：[B-tree - Wikipedia](https://en.wikipedia.org/wiki/B-tree)

**補足**:
- **キャッシュの影響**: MySQLではキャッシュメカニズムを活用することで、ディスクI/Oを回避し、検索速度を向上させることができます。キャッシュヒット率が高いほど、実際の検索時間は短縮されます。（詳細：[MySQL :: MySQL 8.0 リファレンスマニュアル :: 8.10.1 InnoDB バッファプールの最適化](https://dev.mysql.com/doc/refman/8.0/ja/innodb-buffer-pool-optimization.html)）

# 4. Cassandraのデータアクセスとアルゴリズムと計算量

Cassandraは独自のアーキテクチャとアルゴリズムを採用しており、高いパフォーマンスを実現しています。主な要素として、Bloom filter、\log-Structured Merge Trees (LSM Trees)、シャーディング（トークンリング）、キャッシュメカニズムなどがあります。

- [データはどのようにして読み取られるか | DSE 6.7アーキテクチャー・ガイド](https://docs.datastax.com/ja/dse/6.7/dse-arch/datastax_enterprise/dbInternals/dbIntAboutReads.html)
- [データはどのように書き込まれるか | DSE 5.1アーキテクチャー・ガイド](https://docs.datastax.com/ja/dse/5.1/dse-arch/datastax_enterprise/dbInternals/dbIntHowDataWritten.html)

結論から伝えると、以下のような特徴があります：

1. **検索**: **$O(1)$**
2. **挿入**: **$O(1)$**

## 検索の計算量
Cassandraの検索パフォーマンスは物理Nodeの数を$n_p$、仮想Nodeの数を$n_v$とすると、データの分散度は以下のように表されます：

1. 物理Nodeへのルーティング: **$O(\log n_p)$**
    - 理由：ハッシュの計算に関連する箇所の計算量は1だが、どの物理ノードの範囲に所属するか探索する必要があるため（詳細分からなかったため二分探索の計算量と同じとした）
    - 詳細：[Consistent hashing | Apache Cassandra 3.0](https://docs.datastax.com/en/cassandra-oss/3.0/cassandra/architecture/archDataDistributeHashing.html), [How data is distributed across a cluster (using virtual nodes) | Apache Cassandra 3.0](https://docs.datastax.com/en/cassandra-oss/3.0/cassandra/architecture/archDataDistributeDistribute.html)
1. Memtableの検索: **$O(m)$** ($m$はMemtableのサイズ)
    - 理由：Memtableはskip listを使用しており、検索がこちらの計算量に依存します（ただし、Version5.0でTrie memtableが実装されたため、その場合はキーの長さに依存するため大幅に改善される可能性があります）。
    - 詳細：[CEP-19: Trie memtable implementation - CASSANDRA - Apache Software Foundation](https://cwiki.apache.org/confluence/display/CASSANDRA/CEP-19%3A%2BTrie%2Bmemtable%2Bimplementation), [Skip list - Wikipedia](https://en.wikipedia.org/wiki/Skip_list), [Trie - Wikipedia](https://en.wikipedia.org/wiki/Trie)
1. 行キャッシュの検索: **$O(1)$**
    - 理由：行キャッシュはOHCProviderまたはSerializingCacheProviderを利用しており、この記事ではハッシュマップとして仮定をしています（また、このキャッシュは書き込みが多い場合は効果が薄いため通常は無効になっています）。
    - 詳細：[cassandra.yaml構成ファイル | DSE 5.1開発者ガイド](https://docs.datastax.com/ja/dse/5.1/dse-dev/datastax_enterprise/config/configCassandra_yaml.html?utm_source=chatgpt.com#configCassandra_yaml__row_cache_class_name), [行キャッシュ | 用語集](https://docs.datastax.com/ja/glossary/doc/glossary/gloss_row_cache.html)
1. Bloom filterの存在確認: **$O(1)$**
    - 理由：Bloom filterの数はSSTableの数と一致し、SSTableの数はコンパクションの結果などで増減しますが、一般的には一定です。
    - 詳細：[Bloom Filters | Apache Cassandra Documentation](https://cassandra.apache.org/doc/stable/cassandra/operating/bloom_filters.html)
1. チャンク・キャッシュ/メモリー内のパーティション・インデックス内のパーティション・オフセットを検索: **$O(\log n_s)$** ($n_s$はSSTable内で管理するインデックスエントリの数)
    - メモリ内のインデックスサマリーを用いて、ターゲットキーの正確な位置（オフセット）を二分探索的に特定します。
    - 詳細：[SSTables 3.0 Index File Format | ScyllaDB Docs](https://opensource.docs.scylladb.com/stable/architecture/sstable/sstable3/sstables-3-index.html)
1. 必要なインデックス・データがキャッシュに存在しない場合には、ディスクI/Oが発生: **$O(IO)$**
    - 計算量的にはチャンク単位のI/OはO(1)とみなせますが、実際の遅延はディスクレイテンシに依存します。
6. 圧縮されていないチャンク・キャッシュからのデータの展開: **$O(1)$**
    - 既にデータがチャンク・キャッシュ内に存在する場合、ハッシュ参照等で定数時間アクセスが可能です。  
7. 必要なデータ・チャンクがキャッシュに存在しない場合のディスクアクセス: **$O(IO)$**
    - 圧縮オフセット・マップを使用して、ディスク上のデータを見つけます  
        - 圧縮後のデータを格納するSSTableでは、圧縮オフセット・マップにより目的のチャンクを特定します。
    - ディスク上のSSTableからデータをチャンク・キャッシュにフェッチします  
        - 実際に圧縮されたデータを読み込み、展開後、チャンク・キャッシュへ格納します。 
        - 計算量: **$O(1)$**（ただしI/O発生時は$O(IO)$）

そのため、RowCacheがない場合は、
- すべてMemtableにデータがある場合: **$O(\log n_p + m)$**
- Memtableにデータがないが、キャッシュにデータがある場合: **$O(\log n_p + m + \log n_s)$**
- インデックス・データｍデータがディスクにある場合: **$O( \log n_p + m + \log n_s + IO)$**

上記のようにありますが、$n_p$や$n_s$は物理NodeやSSTableの数に依存するため$N$と比較すると実質的に定数とみなせるため、$O(1)$としても問題ありません。

## 挿入の計算量
Cassandraの挿入操作は、主に以下のステップで構成されます（nodeへのルーティングは読み取り時と同じのため省略します）

1. commit logへの書き込み: **$O(1)$**
    - 理由：commit logは追記専用であり、書き込みが常に末尾に行われるため、定数時間で書き込みが完了します。
    - 詳細：[Apache Cassandra | Apache Cassandra Documentation](https://cassandra.apache.org/_/blog/Learn-How-CommitLog-Works-in-Apache-Cassandra.html)
1. memtableへの書き込み: **$O(m)$** ($m$はMemtableのサイズ)
    - 理由：Memtableはskip listを使用しており、挿入がこちらの計算量に依存します(先述したとおり、Trie memtableが導入された場合は改善されます。ただ、そちらは最新のCassandraのバージョンにのみ適用されるため、ここではskip listを前提としています)。
    - 詳細：[CEP-19: Trie memtable implementation - CASSANDRA - Apache Software Foundation](https://cwiki.apache.org/confluence/display/CASSANDRA/CEP-19%3A%2BTrie%2Bmemtable%2Bimplementation), [Skip list - Wikipedia](https://en.wikipedia.org/wiki/Skip_list), [Trie - Wikipedia](https://en.wikipedia.org/wiki/Trie)
1. memtableのflush: **$O(m)$**
    - 理由：Memtableが一定のサイズに達するなどすると、ディスクに書き込まれます。この際、データの書き込みが行われるため、メモリ上のデータをディスクにフラッシュする操作はメモリサイズに依存します。
    - 詳細：[データはどのように書き込まれるか | DSE 5.1アーキテクチャー・ガイド](https://docs.datastax.com/ja/dse/5.1/dse-arch/datastax_enterprise/dbInternals/dbIntHowDataWritten.html#memtable%E3%81%8B%E3%82%89%E3%81%AE%E3%83%87%E3%83%BC%E3%82%BF%E3%81%AE%E3%83%95%E3%83%A9%E3%83%83%E3%82%B7%E3%83%A5)

よって、挿入操作全体の計算量は、$O(m)$となります。
ただ、これもデータサイズの$N$と比較すると定数とみなせるため、$O(1)$としても問題ありません。

# 5. まとめ

MySQLとCassandraは、それぞれ異なるデータアクセスの仕組みを持ち、計算量も異なります。MySQLはB-treeを用いたインデックス構造により、対数時間での検索や挿入を実現しています。一方、Cassandraは独自のアーキテクチャとアルゴリズムにより、検索や挿入を定数時間で行うことができます。

ただ、データベースの選定においては、データの特性やアクセスパターン、整合性、可用性など、さまざまな要素を考慮する必要があります。適切なデータベースを選択するためには、それぞれの特性を理解し、適切なユースケースに適したデータベースを選択することが重要です。