# Cassandra — A Decentralized Structured Storage System > [!abstract] > Cassandra は、Facebook が開発した分散構造化ストレージシステムであり、大量の構造化データをコモディティサーバ群に分散配置しつつ、単一障害点のない高可用サービスを提供する。データモデルは [[Bigtable|[[@2006__OSDI__Bigtable - A Distributed Storage System for Structured Data]]]] のカラムファミリモデルに由来し、パーティショニングとレプリケーションの設計は [[Dynamo|[[@2007__SOSP__Dynamo - Amazon's Highly Available Key-value Store]]]] の手法を踏襲する。書き込みスループットの最大化と読み取り効率の両立を主目標とし、Facebook Inbox Search（1 億ユーザ超）を本番稼働させた実績を持つ。 ## 論文情報 | 項目 | 内容 | |---|---| | タイトル | Cassandra - A Decentralized Structured Storage System | | 著者 | [[Avinash Lakshman]]、[[Prashant Malik]] | | 所属 | [[Facebook]] | | 発表 | LADIS 2009（Workshop on Large Scale Distributed Systems and Middleware）、ACM SIGOPS Operating Systems Review 44(2), 2010 | | URL | https://dl.acm.org/doi/10.1145/1773912.1773922 | ## 概要 Cassandra は、数百〜数千台のコモディティサーバ上で大規模な構造化データを管理する分散ストレージシステムである。完全なリレーショナルデータモデルを提供せず、動的なデータレイアウトとフォーマット制御を備えた単純なデータモデルを採用する。設計上の主要な影響源は 2 つあり、Dynamo からはコンシステントハッシュによるパーティショニング、クォーラムベースのレプリケーション、ゴシップベースのメンバーシップ管理を継承し、Bigtable からはカラムファミリ・スーパーカラムファミリのデータモデルと、コミットログ + メモリ上テーブル + SSTable による永続化パイプラインを継承している。 ## 問題設定 Facebook は数億のユーザに対してピーク時に数万台のサーバでサービスを提供しており、常に一定数のサーバやネットワークコンポーネントが障害状態にある。この環境で Inbox Search 機能を実現するためには、以下を満たすストレージ基盤が必要であった。 - 1 日あたり数十億件の書き込みを処理する高い書き込みスループット - 地理的に分散したデータセンタ間でのレプリケーション - ユーザ数の増加に対するリニアなスケーラビリティ - 構成要素の障害を常態として扱う耐障害設計 既存の選択肢のうち、リレーショナルデータベースは強一貫性の保証がネットワーク分断時の可用性を犠牲にし、Dynamo はベクトルクロックの書き込み前読み取りが高書き込みスループット環境では制約となり、Bigtable は分散ファイルシステム（GFS）に依存するため独立したデプロイが困難であった。 ## 提案手法 ### データモデル Cassandra のテーブルは、キーによって索引付けされた分散多次元マップである。行キーに対する操作はレプリカ単位で原子的に実行される。カラムはカラムファミリとしてグループ化され、[[@2006__OSDI__Bigtable - A Distributed Storage System for Structured Data]] のカラムファミリと類似した構造を持つ。さらにスーパーカラムファミリ（カラムファミリの入れ子）を導入し、カラムの時刻順・名前順ソートを提供する。 ### パーティショニング [[一貫性ハッシュ法]]（consistent hashing）によりデータをクラスタ全体に分散する。各ノードにはリング上のランダムな位置が割り当てられ、キーのハッシュ値から時計回りに最初に見つかるノードがコーディネータとなる。Dynamo の仮想ノード方式ではなく、負荷情報に基づきノードがリング上を移動する方式を採用し、負荷分散の決定論性を確保した。 ### レプリケーション 各データ項目はレプリケーションファクタ N に従い N 個のノードに複製される。レプリケーションポリシーとして「ラック非対応」「ラック対応」「データセンタ対応」の 3 種を提供し、Zookeeper を用いたリーダ選出でレプリカの範囲割り当てを管理する。データセンタ間レプリケーションにより、データセンタ全体の障害にも耐える。書き込みはクォーラム数のレプリカから応答を得て完了とし、読み取りは要求される[[結果整合性]]レベルに応じて最も近いレプリカまたは全レプリカにルーティングされる。 ### メンバーシップと障害検知 クラスタメンバーシップは Scuttlebutt に基づく[[ゴシッププロトコル]]で管理される。障害検知には Φ 累積障害検知器（Φ Accrual Failure Detector）の改良版を採用した。従来のブーリアン判定ではなく、疑念レベル Φ を連続値で出力し、Φ = 1 で誤検知確率約 10%、Φ = 2 で約 1% となる。ゴシップメッセージの到着間隔を指数分布で近似し（原論文のガウス分布ではなく）、ネットワーク・負荷条件に動的に適応する。100 ノードクラスタにおいて、従来の障害検知器が 2 分要した検知を Φ = 5 の保守的設定で平均 15 秒に短縮した。 ### ローカル永続化（[[LSMツリー]]型パイプライン） 書き込みは以下のパスを経る。 1. **コミットログ**への逐次書き込み（専用ディスク）— 耐久性と復旧を保証 2. **メモリ上データ構造**（メムテーブル）への更新 3. 閾値超過時にメムテーブルを**SSTable** としてディスクにフラッシュ（逐次書き込み、インデックス付き） 4. バックグラウンドの**コンパクション**により複数 SSTable をマージ（Bigtable のコンパクションと同様） 読み取りではまずメモリ上構造を参照し、ヒットしなければ新しい順にディスクファイルを走査する。各ファイルにはブルームフィルタが付随し、不要なディスクアクセスを回避する。256 KB 境界ごとのカラムインデックスにより、目的のカラムへの高速ジャンプを実現する。すべてのディスク書き込みは逐次的であり、ファイルは不変（ミューテーションなし）であるため、読み取り時にロックが不要であり、事実上ロックフリーの読み書き操作が可能である。 ### 実装 Java で実装され、SEDA アーキテクチャに基づくイベント駆動パイプラインを持つ。制御メッセージは UDP、レプリケーションとルーティングは TCP を使用する。ノード追加時のデータ転送は単一ノードから 40 MB/秒の転送レートを実測した。 ## 新規性 - Dynamo のパーティショニング・レプリケーション設計と Bigtable のカラムファミリデータモデルを**明示的に統合**した最初のシステムの一つであり、両者の弱点（Dynamo のベクトルクロック書き込み前読み取り、Bigtable の GFS 依存）を回避した - Φ 累積障害検知器を[[ゴシッププロトコル]]環境に初めて適用し、到着間隔を指数分布で近似することで精度と速度を改善した - データセンタ対応レプリケーションにより、地理分散環境での完全非中央集権ストレージを実現した ## 実験設定 - Facebook Inbox Search：1 億ユーザ超（論文時点で 2.5 億ユーザに拡大） - 150 ノードクラスタ、米国東西海岸のデータセンタに分散配置 - 50 TB 以上のデータを格納 - 障害検知実験：100 ノードクラスタ ## 実験結果 ### Inbox Search の本番レイテンシ | 統計量 | Search Interactions | Term Search | |---|---|---| | 最小 | 7.69 ms | 7.78 ms | | 中央値 | 15.69 ms | 18.27 ms | | 最大 | 26.13 ms | 44.41 ms | ### 障害検知 - 従来の障害検知器：100 ノードで障害検知に約 2 分 - Φ 累積障害検知器（Φ = 5）：同条件で平均 15 秒 ### データ移行 - MySQL から 7 TB のインデックスデータを MapReduce で変換し Cassandra に投入 - 単一ノードからのデータ転送レート：40 MB/秒 ## 考察 Cassandra の設計は、当時の分散ストレージにおける 2 つの主要アプローチ —— Dynamo 型の完全非中央集権キーバリューストアと Bigtable 型の構造化ストレージ —— のハイブリッドであり、両者の長所を取り込みつつ短所を回避している。特に、ベクトルクロックを排除しタイムスタンプベースの衝突解決を採用したことで書き込みパスが単純化され、高書き込みスループットが実現された。一方、この選択はタイムスタンプの精度に依存するため、クロック同期の精度が書き込みの正確性に直結する。 Zookeeper をリーダ選出に使用している点は「完全非中央集権」という主張とやや矛盾するが、著者自身も「一定の協調機構は分散機能の実装を容易にする」と述べており、実用上の妥協として位置づけている。 ## 強み - 書き込みパスの単純さ（コミットログ → メムテーブル → SSTable）による高スループット - データセンタ対応レプリケーションによる地理分散高可用性 - Φ 累積障害検知器による適応的で高速な障害検知 - 1 億ユーザ超の本番環境での実証 ## 弱点・課題 - キー間のトランザクションやセカンダリインデックスが未サポート（論文時点）。著者は将来の課題として言及 - タイムスタンプベースの衝突解決はクロック同期の精度に依存し、同時書き込みの意味論が不明確 - 定量的なベンチマーク評価（スループット、スケーラビリティの体系的測定）が不足しており、Inbox Search の運用数値のみ - スーパーカラムファミリの設計は後に廃止される（Apache Cassandra 3.x 以降） - 論文で述べられた圧縮機能の追加は未実装であった（後のバージョンで実現）