（出典：Wikipedia）

1.はじめに

前回、予想以上に反響があったので、2編を作成することにしました。膨大なCassandraの内容をすべて含めることはできないので、今回も最大限に重要なもの、あるいは検索しても見つかりにくいものを中心に整理したいと思います。Cassandraについて詳しく知りたい方は、Datastaxの公式文書をお勧めします。

2. Cassandraのデータ分散

Cassandraは複数のノードで構成されたRing形態を帯び、各ノードはそれぞれのhash tokenの範囲を担当しています。そして、partition keyで指定されたcolumnのvalueでRow keyを決定して、これをhashingしたtokenに基づいてデータをノード別に分散して保存しています。Cassandraのデータ分散方式について、もう少し詳しく調べてみましょう。

まず重要な内容として、Row keyをどのようにtokenへ変換するか、みてみよう。CassandraではRow keyをtokenに変換するモジュールをPartitionerと呼びます。conf/cassandra.yamlのpartitioner項目で、当該CassandraがどのPartitionerを利用しているか確認できます。Cassandraは基本的に、RandomPartitioner、Murmur3Partitioner、ByteOrderedPartitionerという3つのPartitionerを提供しています。（もちろん、ユーザーがorg.apache.cassandra.dht.IPartitionerを継承して、必要なPartitionerを実装することもできますが、この方法はあまり推奨しません。複雑な上に性能を保証するのが難しいからです。もちろん運営上の問題もあるでしょう。）

RandomPartitionerはRow keyをMD5にhashingしてtokenを生成します。Murmur3PartitionerはMurmur5でHashingしてtokenを生成します。しかし、ByteOrderedPartitioner（以下BOP）は少し異なります。BOPはRow keyを16進数形式に変換して、この値をtokenとして使用します。つまり、BOP変換されたtokenは文字順にソートされ、各ノードに分散されます。BOPを利用すると、Row keyが常に文字順にソートされるので、大容量のデータを加工することなく、そのままrange queryにできます。いろいろと便利に使えますが、BOPは代表的なCassandraのAnti-Patternの1つでもあります。その理由は、BOPを使用するとHotspotの発生確率が非常に高いからです。

（図1：ByteOrderedPartitionerの使用でHotspotが発生する例。A〜Gで始まるRow keyが過度に多いとノード1つに肥大データが蓄積される。）

BOPを使ってRow keyの文字順に、各ノードにデータを分散するようになれば、すべてのノードにデータを均等分散するには、データの分散基準を担当するRow key自体がすべての文字列に対して均一に分布しなければなりません。しかし現実はそうではないですね。BOPを使用する場合、特定の文字に密集しているRow keyを保存するノードが自然とHotspotになってしまいます。しかも単にノードを増減することで解決する問題ではありません。ノードを増やすと、かえって全く使用しないノードが大量に生じかねないし、ノードを減らしたところで、より深刻なHotspotが生じる可能性があるからです。BOPの場合、分散の程度が完全にRow keyの分布に依存しているからです。
これらの理由から、CassandraはMurmur3Partitionerをdefault Partitionerとして使用しています。MurMur3 hash functionを利用することによって、すべてのデータを比較的、均一にすべてのノードに分散できます。もちろんこれにも欠点はあります。文字列ではなく、Hash値を基準に並べ替えて各ノードに格納するので、Row keyの文字列にソートするデータが必要な場合、ユーザーはすべてのデータを取得し、Application Layerから直接データを加工して並べ替える必要があります。例えば、膨大な量のデータが分散して保存されていますが、Row keyを基準にデータをpagingするなどの作業は不可能です。したがって、ユーザーは自分のサービスが使用するデータのスキーマを作成するとき、最初からこれを考慮して慎重に決定しなければなりません。

次はCassandraのData ConsistencyとReplicationについて簡単に調べましょう。
Cassandraは、基本的にCQLを用いてクエリ時点でReadとWriteによる様々なConsistency LevelからReplicationを通じて、どの程度のレベルのデータの整合性を確保するか選択できます。また、最初にKeyspaceを作成するとき、Replicationの配置戦略とその戦略に合ったReplicationの複製数、位置を決定できます。そして、これらの機能をサポートするために、conf/cassandra.yamlのendpoint_snitch項目にsnitchの種類をセットします。snitchは簡単に言うと、データセンターがどのように構成されているか、装置が設置されたラックがどのように分かれていているか、topologyをCassandraに教えるためのオプションです。
Cassandraで提供されるsnitchの種類は非常に多様です。snitchは単に1つのデータセンターを想定したものから、多数のデータセンターに様々なラック配置まで考慮したものまであり、さらにはCloud StackやGoogle CloudなどのCloudサービスに特化したsnitchも存在します。これらのsnitchをもとに、Cassandraはユーザーが定義したスキーマによって、どのデータセンターのどのラックに、それぞれいくつかのReplication Dataを分けて保存するかなどを決定するのです。このように構成されたCassandraのユーザーがデータをCRUDしようとした場合、ユーザーが当該クエリと一緒に指定したConsistency Levelを通じてデータを処理することになります。
Read/WriteによるConsistency Levelの種類と特徴、様々なsnitchの詳しい説明は、この記事では分量が多くなってしまうので、Datastaxの公式文書をご参照ください。（参照リンク：Snitch, Data Consistency ）

3. CassandraとRead/Write

実際にCassandraがデータを読み書きするときに起こる動作について調べてみよう。まず、CassandraにデータをWriteする状況を想定してみよう。

（図2：Cassandra Data Write）

ユーザーはCassandraのノードのいずれかにWrite要求をします。Cassandraでは要求される最初のノードをCoordinatorノードと呼びます。Coordinatorは当該データのRow keyをhashingし、どのノードにデータをWriteする必要があるか確認します。その後、クエリで指定されたConsistency Levelに応じて、いくつかのノードにWriteすべきか参照し、Writeすべきノードのstatusが正常であるか確認します。特定ノードのstatusが正常でない場合は、Consistency Levelに応じて「hint hand off」というローカルの一時記憶領域にWriteデータを保存します。後で異常状態のノードが正常に戻るとCoordinatorノードがdataをWriteしてくれます。このとき注意すべき点は、hint hand offが常にすべてのデータをConsistencyに保証しているわけではないということです。たとえデータの復元に大いに役立つ機能であっても、基本的にhint hand offはデータを一時保存する空間に過ぎません。
hint hand offにデータをバックアップした場合、CoordinatorノードはCassandraのtopologyを確認して、データセンターのどのラックのノードに先にアクセスするかを決定して、データと一緒にWriteを要求します。

（図3：Write Data Storage Layer　画像出典：Datastax）

実際にデータを保存するノードはWrite要求が届くと、万が一の障害に備えて「CommitLog」と呼ばれるローカルディスクのファイルに記録を残します。「MemTable」という名前のメモリストレージにデータをWriteした後、成功メッセージを返すことでWrite要求の動作は終了します。そして当該ノードはMemTableにデータが十分に蓄積されると、ディスクバージョンのMemTableである「SSTable」にデータをFlushします。SSTableはimmutableでsequentialであるという特徴があり、Cassandraはこれらの多数のSSTableをCompactionしてデータを管理します。
次に、Readの処理について調べてみよう。

（図4：Cassandra Data Read）

ユーザーはCassandraのノードのいずれかにRead要求をします。Coordinatorノードは、その要求のRow keyをhashingして、アクセスすべきノードの位置を把握した後、Consistency Levelをチェックして何個のReplicationを確認するか決定します。その後、Coordinatorノードは、データの最も近くにあるノードにData Requestを要求し、近くのノードにはData Digest Requestを要求します。Coordinatorノードはこのように取得したDataとData Digestを確認して、データ情報が一致しない場合、一致しないデータのノードからFull Dataを取得して、その中から最新データをユーザーに返却します。そして返却した最新データをもとに、残りのノードのデータを修復します。
実際のデータが保存されたノードの中では、どのようなプロセスで動作するか調べてみよう。

（図5：Read Data Storage Layer　画像出典：Datastax）

実際のデータが保存されているノードにデータ要求があれば、まずMemTableに保存されたデータを確認します。もし、このときデータがなければ、すでにFlushingされたデータが保存されているSSTableを確認する必要があります。とはいえ、すぐにSSTableにアクセスすることはありません。それぞれのSSTableを確認するとき、性能向上のためSSTableと組み合わせて構成されているBloom FilterとIndexをまず確認します。
Bloom Filterは肯定エラーを発生し、不正エラーは発生させない確率的なデータ構造になっています。簡単に言えば、ないものがあると嘘をつけますが、あるものがないとは嘘がつけません。I/Oが起こる前に、一時的にメモリに保存されているBloom FilterからSSTableにデータが存在するか確認したら、次に同様にメモリに保存されているSummary Indexからディスクに保存されている元のIndexを確認して、SSTable内のDataの位置に対するoffsetを把握します。この過程を経て、初めて当該SSTableから希望するデータを取得して返却することができます。このようなデータの検索過程は、最後に生成されたSSTableから順に行われます。

次はDeleteです。Cassandraは、Deleteキーをすぐには実行しません。すべてのデータにはTombstoneというmarkerが存在し、特定データのDelete要求が起きたらTombstoneにマーキングします。その後、定期的なGarbage CollectionやSSTableのCompactionなどのイベントが発生したとき、はじめてデータを削除するのです。

あとCassandraのデータ処理で残っている内容は、Updateですね。ただ多くの内容を既に説明しているので、Updateは重要な部分を何点か紹介すればクリアできそうです。なぜならCassandraのUpdateは、内部的にDelete/Writeに実装されているためです。前述の通り、データが保存されているSSTableはimmutableなので、Deleteキーを使ってTombstoneにマーキングをすることになり、Updateすべき新しいデータは他の場所に書き込まれます。

4. 2編を終えて

Cassandraが提供する機能や、よく使われる機能、使ってはいけないパターンなどについては、次の3編で紹介したいと思います。