アーキテクチャーオーバービューは、Cassandra（カサンドラ）ユーザー向けのCassandraアーキテクチャーの概略です。
開発者の方は、Wikiのフロントページから開発者向けのリンクをご覧ください。
このページの情報は、オライリー主催のOSCON 2009Cassandra: Open Source Bigtable + Dynamo、Jonathan Ellis (Rackspace Hosting) (PDF)のプレゼンテーション資料に基づいています。
なぜCassandraなのでしょうか？
- MySQLでは、あまりにも多くのランダムI/Oが発生する
- ファイルベースのソリューションでは、あまりにも多くのロックが必要とされる
新たなデータの出現
- スケールアップではなく、スケールアウト
- オンライン状態でのロードバランシングとクラスタの増加の実現
- 柔軟なスキーマ
- キー指向のクエリー
- CAP定理（経験則）を認識すること
CAP定理（経験則）
Eric Brewer（エリック・ブルーワー）の*CAP定理 (PDF)に支配された状況では、*Consistency（一貫性、コンシステンシー）、Availability（可用性、アベイラビリティー）、*Partition-tolerance（分断耐性、パーティショントレランス）*のうち2つを選択する必要があります。同時に3つの性質を満たすことはできないため、それらを得るにはレイテンシー（遅延）を許容する必要があります。
Cassandraは、可用性と分断耐性（AP）を重視しています。一貫性と遅延はトレードオフの関係にあり、Cassandraでは整合性レベルが調整可能（tunable）です。遅延を許容すればCassandraでは強い一貫性（Strong Consistency）を得ることができます。しかし、行ロックを取得することはできません。その点は、HBaseの方が優れています。
メモ: HBaseは、一貫性と分断耐性（CP）を重視しています
歴史とアプローチ
2つの有名な論文
- Bigtable: A Distributed Storage System for Structured Data, 2006 (PDF)
- Dynamo: amazon's highly available keyvalue store, 2007 (PDF)
2つのアプローチ
- BigTable：”どのようにしてGFS上に分散データベースを構築できるか？”
- Dynamo：”どのようにして、分散ハッシュテーブルをデータセンターに相応しいように構築できるか？”
10,000フィートからのCassandra要約
- Dynamoのパーティショナーおよびレプリケーション
- BigTableに類似したログ構造のColumnFamilyデータモデル
Cassandraハイライト
- 高可用性
- 可用性の増分
- イベンチュアルコンシステント（Eventually Consistent）
- 一貫性と遅延というトレードオフの関係が調整可能
- 最小限の管理
- SPOF（Single Point of Failure、単一障害点）がない
P2P流通モデル：SPOF（単一障害点）のないことを意味する整合性モデルで動作します。
キーの流通と分割
Dynamoアーキテクチャー＆ルックアップ
ノードA、B、C、D、E、F、そしてGのリングでは、ノードB、C、とDは、キーを重要な_k_を含む(a,b)の範囲の中でキーを格納します。
{{パーティショナー}}のために{{IntitialToken}}パラメーターを使用して、Cassandraのどこにキーがあるのか、その方向性を決定することができます。ストレージの構成を参照してください。
アーキテクチャーの詳細
- O（1）ノードのルックアップ
- 明示的なレプリケーション
- イベンチュアルコンシステント（Eventually Consistent）
アーキテクチャーレイヤー
コアレイヤー |
ミドルレイヤー |
トップレイヤー |
メッセージサービス（Messaging service） |
||
コミットログ（Commit log） |
||
廃棄（Tombstones）の有効期間 |
書き込み
任意のノードにおけるパーティショナー、コミットログ（Commit log）、Memtable、SSTable、コンパクションは、Wの応答を待ちます。
書き込みモデル：
2つの書き込みモード：
- クォーラム書き込み（Quorum write）: ブロッククォーラムに達するまで
- 非同期書き込み（Async write）: 任意のノードに要求を送信します。そのノードから適切なノードにデータを送信し、ただちにクライアントへ返信します。
仮にノードがダウンした場合、別のノードへヒント（訳注：ダウンしたノードの情報）と共に書き込みます。このヒントは2つ書き込まれる必要があります。ハーベスターが、15分毎に通過し、ヒントを見つけ、データを適切なノードへ移動します。
Write path
At write time,
- you first write to a disk commit log (sequential)
- After write to log it is sent to the appropriate nodes
- Each node receiving write first records it in a local log, then makes update to appropriate memtables (one for each column family). A Memtable is Cassandra's in-memory representation of key/value pairs before the data gets flushed to disk as an SSTable.
- Memtables are flushed to disk when:
- Out of space
- Too many keys (128 is default)
- Time duration (client provided – no cluster clock)
- When memtables written out two files go out:
- Data File (SSTable). A SSTable (terminology borrowed from Google) stands for Sorted Strings Table and is a file of key/value string pairs, sorted by keys.
- Index File (SSTable Index). (Similar to Hadoop MapFile / Tfile)
- (Key, offset) pairs (points into data file)
- Bloom filter (all keys in data file). A Bloom filter, is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set. False positives are possible, but false negatives are not. Cassandra uses bloom filters to save IO when performing a key lookup: each SSTable has a bloom filter associated with it that Cassandra checks before doing any disk seeks, making queries for keys that don't exist almost free. Bloom filters are surprisingly simple: divide a memory area into buckets (one bit per bucket for a standard bloom filter; more -typically four - for a counting bloom filter). To insert a key, generate several hashes per key, and mark the buckets for each hash. To check if a key is present, check each bucket; if any bucket is empty, the key was never inserted in the filter. If all buckets are non-empty, though, the key is only probably inserted - other keys' hashes could have covered the same buckets. See All you ever wanted to know about writing bloom filters for details and in particular why getting a really good output distribution is important.
- When a commit log has had all its column families pushed to disk, it is deleted
- Compaction: Data files accumulate over time. Periodically data files are merged sorted into a new file (and creates new index)
- Merge keys
- Combine columns
- Discard tombstones
書き込みのプロパティ
- 読み込みをしない
- シークを行わない
- 高速
- ColumnFamilyの範囲内がアトミックである
- 常に書き込み可能
削除
Deletion marker (tombstone) necessary to suppress data in older SSTables, until compaction Read repair complicates things a little Eventually consistent complicates things more Solution: configurable delay before tombstone GC, after which tombstones are not repaired
読み込み
パスの読み込み
- 任意のノード
- パーティショナー
- Rの応答を待つ
- Nの待機 - Rの応答をバッググラウンドで処理中に、読み込みの修復を実行
Cassandraはプロパティを読み込む
- 複数のSSTableを読み込む
- （まだ高速ですが）遅延書き込み
- シークはより多くのメモリー消費を軽減することが可能
- 数十億の行にわたりスケール
一貫性
Thrift APIドキュメントも参照してください。
Consistency describes how and whether a system is left in a consistent state after an operation. In distributed data systems like Cassandra, this usually means that once a writer has written, all readers will see that write.
On the contrary to the strong consistency used in most relational databases (ACID for Atomicity Consistency Isolation Durability) Cassandra is at the other end of the spectrum (BASE for Basically Available Soft-state Eventual consistency). Cassandra weak consistency comes in the form of eventual consistency which means the database eventually reaches a consistent state. As the data is replicated, the latest version of something is sitting on some node in the cluster, but older versions are still out there on other nodes, but eventually all nodes will see the latest version.
More specifically:
R=read replica count W=write replica count N=replication factor Q=QUORUM (Q = N / 2 + 1)
- If W + R > N, you will have consistency
- W=1, R=N
- W=N, R=1
- W=Q, R=Q where Q = N / 2 + 1
Cassandra provides consistency when R + W > N (read replica count +
write replica count > replication factor).
You get consistency if R + W > N, where R is the number of records to read, W is the number of records to write, and N is the replication factor. A ConsistencyLevel of ONE means R or W is 1. A ConsistencyLevel of QUORUM means R or W is ceiling((N+1)/2). A ConsistencyLevel of ALL means R or W is N. So if you want to write with a ConsistencyLevel of ONE and then get the same data when you read, you need to read with ConsistencyLevel ALL.