#まえふり
LITALICOの管理栄養士 @Sadalsuud です。好きな食べ物はピザです。
以前からインスタレーションなどを作成してTwitterに投稿していたことがあり、入社数日目にはCTOの @takish さんがフォロワーだったことが判明。
それからなんやかんやあって、社内ハッカソンに参加させていただいたり、このAdvent Calendarにも参加させていただいたりしています。
というわけで、『LITALICO Engineers Advent Calendar 2017』12日目の記事です。
読むのが面倒になった方は最後にあるgifだけ見て帰っていただければ幸甚です。
#分散データベースのうわべの話
分散データベースでは、データベースがクラスタ化され、各ノードに処理が分散されます。
AWSのNoSQLである、AmazonDynamoDBは次のように説明されています。
DynamoDB は十分な数のサーバー間でデータとトラフィックを自動的に分散し、一貫した高速なパフォーマンスを維持したまま、スループットとストレージの要件に対応します。すべてのデータは SSD (Solid State Disk) に保存され、1 つの AWS リージョン内の複数のアベイラビリティーゾーン間で自動的にレプリケートすることによって、高い可用性とデータ堅牢性を実現します。
http://docs.aws.amazon.com/ja_jp/amazondynamodb/latest/developerguide/Introduction.html
こうした分散システムでは、あるノードで起こった処理をシステム全体に周知させ、破綻なく稼働を続けさせる必要があるそうです。
なぜなら、分散されているとはいえデータベースであるので、複製したあるノードでは x=a だけど、別の複製では x=b だったということでは、一貫性が低下するばかりです。そこで、あるノードで起こったイベントは、全ノードに周知（マルチキャスト）されるようになっています。
しかし、マルチキャストが起こるとしても、受け取った各ノードでは x=a と x=b のどちらが最新の値なのか、前後関係を判断して更新するか否かを決める必要があります。
非分散システムではタイムスタンプがあれば、そのイベントが「いつ」起こったのか判断することができますが、分散システムではそうはいきません。なぜなら、分散したノード間で共通して使える「時計」がないからです。
それなら、共通の時刻を配信するようなサーバー作って･･･って思うのですが、異なるクロックの異なるノード間で、イベント発生の前後関係を比較できるほどの絶対時間を持つことは簡単ではないそうです。
そこで用いられるのが「論理クロック」という概念。論理クロックは、絶対時間としてそのイベントが「いつ」起こったのかを示すのではなく、どういった「順番」で起こったのかを示してくれます。
この順番を示すために使われるしくみのひとつがベクトルタイムスタンプ(Vector Clock)です。
#ベクトルタイムスタンプ(Vector Clock)のしくみ
ベクトルタイムスタンプ自体には次のようなルールがあります。（注:実際にDBの中で動いている因果一貫性確保のためのベクトルタイムスタンプのしくみは、ここで説明したものを発展させたしくみのようです。詳しくは後述します。）
-
前提
-
全ノード数を n としたとき、各ノードではそれぞれ n次元のベクトルを持つようにします。
-
このn次元ベクトル各成分には、そのノードが知っている、各ノードで起こったイベントの数が割り当てられています。そこには自分自身のイベント数を割り当てるベクトル成分もあります。
-
更新のルール
-
自ノードでイベントが発生したときには、n次元ベクトルの自身が該当する成分をインクリメントします。
-
自ノードから周知メッセージを他のプロセスへ送信する場合は、自身のn次元ベクトルを添えて送り、そのあとにn次元ベクトルの自身が該当する成分をインクリメントします。
-
メッセージを受信したときは、まず自身が該当する成分をインクリメントしたあと、メッセージに含まれるn次元ベクトルと、自身の保持するn次元ベクトルを比較し、それぞれの成分に対して大きいほうの値をベクトルタイムスタンプとして保持します。
次の例を見てください。
この例では2つのノード、P1とP2が、お互いにメッセージを送り合う様子を示しています。時間は左側から右側に向かって進行していきます。
全ノード数は2なので、各ノードは2次元のベクトルを持つことになります。
そして、P1のベクトルでは要素の1番目に自身のイベント回数を保持しており、2番目の要素にはそのとき知っているP2のイベント回数を保持していることになります。
最初、P1でAというイベントが起こります。イベントが発生したのでルール乗っ取って、自身を示す成分をインクリメントします。[0,0]→[1,0]
次にP1にはP2からメッセージが送られてきます。このメッセージに添付されているのは[0,1]です。これはP2で1回イベントが起こったことを知らせるものなので、まずP1の自身の成分をインクリメントした後、受信のしたP2のイベント回数を、該当成分に取り込みます。[1,0]→[2,1]
そして、Cでもイベントがあり、自身のベクトルをインクリメントした後、[2,1]→[3,1]
DでP2にメッセージを送ります。[3,1]→[4,1]
P2もメッセージを受け取るときは同様に、自身の成分をインクリメントした後、P1の成分をメッセージから受け取ります。[0,2]→[3,3]
こうして、ベクトルタイムスタンプが作成されていきます。
ベクトルタイムスタンプで前後関係の比較するときは、各成分ごとに比較を行います。
・ある時点βのベクトルタイムスタンプのすべての成分が、比較対象αと比べて大きい時
βはαの後に起こったと判断できる。（値が等しい成分があってもよい）
・ある時点βのベクトルタイムスタンプのすべての成分が、比較対象αと比べて小さい時
βはαの前に起こったと判断できる。（値が等しい成分があってもよい）
・ある時点βと比較対象αのベクトルタイムスタンプが、どれかひとつの成分でもでも共通の大小関係が成立しないときは、αとβの前後関係は判断できない。
（例）
このように判断します。
例えば先ほどの例で、F[0,1]とC[3,1]では、すべての成分でCのほうが値が大きくなっています。
この時、CはFより後に起こったと判断できます。
[再掲]
では、AとEの関係はどうでしょうか。
A[1,0]とE[0.1]では、1つ目の成分はAのほうが大きいですが、2つ目の成分ではEが大きくなっています。
このとき、AとBの関係は、どちらが先に起こったか判断することができません。
ベクトルタイムスタンプでは、メッセージを送る際に必ず、送信ノードと受信ノードの間に前後を比較できる関係が成立します。
各ノードが持つイベントの初期値を変更して、かつノード数を一つ増やしたのが次の図です。
このときでも、それぞれのノード間の比較は同様のルールで行うことができます。
例えばF[5,16,0]とC[9,16,0]では、前2つのベクトルはCのほうが値が大きく、最後のベクトルは同じ値なので、Cのほうが後に起こったと判断できます。
しかし、C[9,16,0]とH[5,16,4]では、すべてのベクトルで共通した大小関係が成立しないので、どちらが早く起こったかは判定できません。
ベクトルタイムスタンプでは、すべてのケースで順序関係を明らかにすることはできないものの、メッセージの送信が適切なタイミングで行われれば、処理の因果関係を示す証拠になります。
#ビジュアライズしてみた！
この仕組みをビジュアライズしたのがこちら。
3つのノード間でメッセージを送りあっており、イベントの発生や、メッセージの送受信のタイミングでベクトルタイムスタンプが更新されていきます。
メッセージが届くまでの時間はそれぞれで違います。これは現実でもネットワークの状況によって発生しうることを意図しています。
#ビジュアライズの実装
ビジュアライズする以上、スケーラビリティも再現して、動的にノード数が増えたり減ったりするところも作りたかったのですが、v4では値を保持することが苦手なため、よい実装が思いつきませんでした。
結果的に、処理が煩雑怪奇の奇々怪々になったパッチの全体像がこちらです。
オブジェクト指向がいかに偉大なのか、その鱗片を味わいました。
#因果一貫性を担保する際のDBでの使用
上記まで紹介したのはベクトルタイムスタンプの考え方なのですが、実際にDBの因果一貫性を保つ目的では、データ書き込み時のメッセージの送信時にのみ値をインクリメントするということが行われているようです。
そして、送信と受信の間を比較して、そのタイムスタンプに連続性が無い場合、更新を一時保留します。
例えば[7,3]を持つP1に、P2から[6,5］が届いたとします。もしP1側で保持しているP2のイベントを3→5へそのまま更新してしまっては、P1はP2で起こった、4のイベントを知らないまま、5へ更新を行ってしまいます。
これを防止するために、実際の処理では連続性のないタイムスタンプを受け取るとその更新を一旦保留にして、まだ到着していないであろうメッセージの到着を待ちます。
#おわりに
もちろん、一貫性の維持はこのベクトルタイムスタンプだけでなく、ほかにもさまざまなアルゴリズムが働いているものだと思います。
ともあれ、アルゴリズムって映像にするとエモいですよね…。
これを書きながらTwo-Phase Commitのビジュアライズも作ってみたくなったので、いずれチャレンジしてみようと思います。
→作りました！
Two-Phase Commit
(普段つくっている作品などはこちら)
内容については、さまざまな記事や文献を参考にさせていただき、間違いのないように留意しておりますが、いうて私はまだ栄養士にしいたけが生えたくらいの存在なので、誤りなどありましたら、ぜひご指摘いただければ幸いです。
さて、明日は @kazuis さんの「新しいシステムのアーキテクチャを決めるときに考えている事」です！お楽しみに！
参考にさせていただいたサイトさま・資料
enPiT（東大・東工大）クラウドシステム基礎（順序づけ）
分散システムの一貫性に関する動向について
分散システム第7章（前半）
ベクタークロック : kei@sodan
Causal Ordering : kei@sodan
分散システム読書会 06章-同期（前編）
同期(2)排他制御