Go to Qiita Advent Calendar 2024 Top
LoginSignup
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

Distributed computing (Apache Spark, Hadoop, Kafka, ...)Advent Calendar 2024

Day 15
@making111(N Maki)

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

Last updated at Posted at 2024-12-14

TL;DR

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

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

MySQL

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

Cassandra

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

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

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

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

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

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

B-tree以外にも、MySQLではハッシュインデックスもありますが、ハッシュインデックスは等値検索に特化しており、範囲クエリには向いていません。よくまとめられている記事はこちらです：

  1. mysql - B-Tree vs Hash Table - Stack Overflow
  2. MySQL :: MySQL 5.7 Reference Manual :: 8.3.8 Comparison of B-Tree and Hash Indexes

計算量

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

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

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

補足:

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

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

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

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

検索の計算量

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

  1. 物理Nodeへのルーティング: $O(\log n_p)$
  2. Memtableの検索: $O(m)$ ($m$はMemtableのサイズ)
  3. 行キャッシュの検索: $O(1)$
  4. Bloom filterの存在確認: $O(1)$
  5. チャンク・キャッシュ/メモリー内のパーティション・インデックス内のパーティション・オフセットを検索: $O(\log n_s)$ ($n_s$はSSTable内で管理するインデックスエントリの数)
  6. 必要なインデックス・データがキャッシュに存在しない場合には、ディスクI/Oが発生: $O(IO)$
    • 計算量的にはチャンク単位のI/OはO(1)とみなせますが、実際の遅延はディスクレイテンシに依存します。
  7. 圧縮されていないチャンク・キャッシュからのデータの展開: $O(1)$
    • 既にデータがチャンク・キャッシュ内に存在する場合、ハッシュ参照等で定数時間アクセスが可能です。
  8. 必要なデータ・チャンクがキャッシュに存在しない場合のディスクアクセス: $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)$
  2. memtableへの書き込み: $O(m)$ ($m$はMemtableのサイズ)
  3. memtableのflush: $O(m)$

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

5. まとめ

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

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

2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?