[MySQLのインデックスとCassandraのスピードが異なる理由 ～アルゴリズムと計算量、アーキテクチャから読み解く～ #B-Tree - Qiita](https://qiita.com/making111/items/9dd42386f5542990ce5d#4-cassandra%E3%81%AE%E3%83%87%E3%83%BC%E3%82%BF%E3%82%A2%E3%82%AF%E3%82%BB%E3%82%B9%E3%81%A8%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%A8%E8%A8%88%E7%AE%97%E9%87%8F) [[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) ## 検索の計算量 Cassandraの検索パフォーマンスは物理Nodeの数を、仮想Nodeの数をとすると、データの分散度は以下のように表されます： 1. 物理Nodeへのルーティング: $O(log {n_p})$ - 理由：仮想Nodeが物理Nodeにマッピングされ、その際にConsistent Hashingが使用されるため、物理Nodeへのルーティングは二分探索に近い計算量となります。 - 詳細：[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) 2. Memtableの検索: $O(log(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) 2. Bloom filterの存在確認: - 理由：Bloom filterの数はSSTableの数と一致し、SSTableの数はコンパクションの結果などで増減しますが、一般的には一定です。 - 詳細：[Bloom Filters | Apache Cassandra Documentation](https://cassandra.apache.org/doc/stable/cassandra/operating/bloom_filters.html) 3. チャンク・キャッシュ/メモリー内のパーティション・インデックス内のパーティション・オフセットを検索: (はSSTable内で管理するインデックスエントリの数) - メモリ内のインデックスサマリーを用いて、ターゲットキーの正確な位置（オフセット）を二分探索的に特定します。 - 詳細：[SSTables 3.0 Index File Format | ScyllaDB Docs](https://opensource.docs.scylladb.com/stable/architecture/sstable/sstable3/sstables-3-index.html) 4. 必要なインデックス・データがキャッシュに存在しない場合には、ディスクI/Oが発生: - 計算量的にはチャンク単位のI/OはO(1)とみなせますが、実際の遅延はディスクレイテンシに依存します。 5. 圧縮されていないチャンク・キャッシュからのデータの展開: - 既にデータがチャンク・キャッシュ内に存在する場合、ハッシュ参照等で定数時間アクセスが可能です。 6. 必要なデータ・チャンクがキャッシュに存在しない場合のディスクアクセス: - 圧縮オフセット・マップを使用して、ディスク上のデータを見つけます - 圧縮後のデータを格納するSSTableでは、圧縮オフセット・マップにより目的のチャンクを特定します。 - ディスク上のSSTableからデータをチャンク・キャッシュにフェッチします - 実際に圧縮されたデータを読み込み、展開後、チャンク・キャッシュへ格納します。 - 計算量: （ただしI/O発生時は） そのため、RowCacheがない場合は、 - すべてMemtableにデータがある場合: - Memtableにデータがないが、チャンクキャッシュにデータがある場合: - データがディスクにある場合: 上記のようにありますが、やは物理NodeやSSTableの数に依存するためと比較すると実質的に定数とみなせるため、としても問題ありません。 ## 挿入の計算量 Cassandraの挿入操作は、主に以下のステップで構成されます（nodeへのルーティングは読み取り時と同じのため省略します） 7. commit logへの書き込み: - 理由：commit logは追記専用であり、書き込みが常に末尾に行われるため、定数時間で書き込みが完了します。 - 詳細：[Apache Cassandra | Apache Cassandra Documentation](https://cassandra.apache.org/_/blog/Learn-How-CommitLog-Works-in-Apache-Cassandra.html) 8. memtableへの書き込み: (は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) 9. memtableのflush: - 理由：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) よって、挿入操作全体の計算量は、となります。 ただ、これもデータサイズのと比較すると定数とみなせるため、としても問題ありません。