Gossiper

gossiper は、システムの全てのノードが他のノード (なにか状態が変更されたときに到達不可能なノードやまだクラスタに参加していないノードを含む) の状態に関する重要な情報を、徐々にしかし確実に知るようにするための責任を負っています。

API

ゴシップの情報は、ApplicationState オブジェクト (本質的には key/value のペア) にくるまれています (より詳しくは下のデータ構造の節に書かれています)。gossiper は、!IEndPointStateChangeSubscriber インタフェースを介して変更点を受け取るように登録した他のノードにそれを伝達します。そのインタフェースは、onJoin, onAlive, onDead メソッド (どういうときによばれるかはわかりますね) と、ApplicationState が変更されたときに呼ばれる onChange メソッドを提供します。これには2つの自明でないプロパティーがあります。

  1. もしノードが複数の変更をある ApplicationState キーに対して行った場合、他のノードは途中の状態でなく、最も新しい状態だけを見ることが出来るという保証があります。

  2. ApplicationState を全て消去する場合の規定はありません。

Gossiper の実装

ゴシップタイマータスクは、1秒ごとに走ります。各タスクが走る間、ノードは次のルールに従ってゴシップの交換を行ないます。

  1. (もしあれば) ランダムなエンドポイントにゴシップを伝えます。
  2. 到達できないノードと生きているノードの数に応じたある確率で、到達できないノードにゴシップを伝えます。
  3. もし、(1) でゴシップが送られたノードが seed でないか、生きているノード数が seed の数を下回った場合、到達できないノードと生きているノードの数に応じたある確率で、ランダムな seed のゴシップを伝えます。

これらのルールは、もしネットワークが up した場合に全てのノードがそのうち他の全てのノードの状態を知ることができるように開発されました。(もちろん、もし各ノードが1つの seed としかコンタクトせず、知っているノードにランダムにゴシップを伝えるような場合は、複数のシードがあると分割 -- すなわち、各 seed がクラスタ中のノードのサブセットのみを知っている -- されることがあります。Step 3 はこのような状態や他の些細な問題を避けます。

このようにして、ノードはゴシップの交換を各ラウンドで1~3ノードとおこないます。(もしくは、クラスタ中に自分しかいなければゴシップの交換は行われません)

データ構造

HeartBeatState

HeartBeatState は、世代とバージョン番号からなっています。世代はサーバーが走っている間は同じ値を取り、ノードがスタートすると増えていきます。ノードがリスタートする前と跡を区別するために使われます。バージョン番号は、application state とシェアされ、順序が保証されます。各ノードは1つの HeartBeatState と関連付けられています。

ApplicationState

ApplicationState は、状態とバージョン番号からなっており、Cassandra 中の1つの "component" もしくは "element" の状態を表します。例えば、"load information" という application state は、(5.2, 45) という値になります。これは、node load が 5.2 で、version が 45 であることを顕います。同様に、bootstrap 中のノードは、"bootstrapping" という application state をもち、例えば (bxLpassF3XD8Kyks, 56) という値になります。初めの値は bootstrap トークンで、2つめの値は version です。バージョン番号は、application state と HeartBeatState で共有されており、順序が保証されています。値は増えることのみが許されます。

EndPointState

EndPointState は、ある エンドポイント(ノード) の ApplicationStatesHeartBeatState をふくんでいます。EndPointState は各タイプの ApplicationState ごとに1つのみを持ちます。すなわち、もし EndPointState がすでに load information を含んでいれば、新しい load information で古い値は上書きされます。ApplicationState バージョン番号は、古い値で新しい値を上書きしないことを保証します。

endPointStateMap

endPointStateMap は、Gossiper の内部の構造で、(そのノードが知っている) 全てのノード (自分自身を含む) に関する EndPointState を含みます。

ゴシップの交換

GossipDigestSynMessage

ゴシップの交換を開始するノードは、GossipDigestSynMessage というゴシップのダイジェストを含んだものを送ります。1つのゴシップダイジェストは、エンドポイントのアドレス、世代番号、そしてエンドポイントに現れる最大のバージョン番号からなっています。ここで、最大のバージョン番号とは、このエンドポイントの EndPointState の中の最大のバージョン番号を指します。

例をあげましょう。

ノード 10.0.0.1 が次の情報を endPointStateMap 中にもっているとします。(endPointStateMap は自分自身をふくんでいることに注意。)

EndPointState 10.0.0.1
  HeartBeatState: generation 1259909635, version 325
  ApplicationState "load-information": 5.2, generation 1259909635, version 45
  ApplicationState "bootstrapping": bxLpassF3XD8Kyks, generation 1259909635, version 56
  ApplicationState "normal": bxLpassF3XD8Kyks, generation 1259909635, version 87
EndPointState 10.0.0.2
  HeartBeatState: generation 1259911052, version 61
  ApplicationState "load-information": 2.7, generation 1259911052, version 2
  ApplicationState "bootstrapping": AujDMftpyUvebtnn, generation 1259911052, version 31
EndPointState 10.0.0.3
  HeartBeatState: generation 1259912238, version 5
  ApplicationState "load-information": 12.0, generation 1259912238, version 3
EndPointState 10.0.0.4
  HeartBeatState: generation 1259912942, version 18
  ApplicationState "load-information": 6.7, generation 1259912942, version 3
  ApplicationState "normal": bj05IVc0lvRXw2xH, generation 1259912942, version 7

この場合、これらのエンドポイントの最大のバージョン番号はそれぞれ 325, 61, 5, 18 です。エンドポイント 10.0.0.2 のゴシップダイジェストは "10.0.0.2:1259911052:61" で本質的には "AFAIK endpoint 10.0.0.2 は世代 1259911052 で動いており、最大のバージョン番号 61 を持つ"という意味です。 ノードが GossipDigestSynMessage を送る場合、エンドポイントごとに必ず1つのゴシップダイジェストがあります。すなわち、この場合、 GossipDigestSynMessage は "10.0.0.1:1259909635:325 10.0.0.2:1259911052:61 10.0.0.3:1259912238:5 10.0.0.4:1259912942:18" となるでしょう。 HeartBeatState は必ずしも最大のバージョン番号でなくても構いませんが、普通はそうです。

Main code pointers:

Gossiper.GossipTimerTask.run: Main gossiper loop
Gossiper.makeRandomGossipDigest: Constructs gossip digest list to be used in GossipDigestSynMessage
Gossiper.makeGossipDigestSynMessage: Constructs GossipDigestSynMessage from a list of gossip digests

GossipDigestAckMessage

GossipDigestSynMessage を受け取るノードは、それを検査し、GossipDigestAckMessage を返します。GossipDigestAckMessage は2つのパート、ゴシップダイジェストリストとエンドポイントの状態リストを持っています。GossipDigestSynMessage 中のゴシップダイジェストリストから、各エンドポイントが自分が知っているよりも新しいもしくは古いバージョンを持っているかどうかがわかります。

また例を上げましょう。

今ノード 10.0.0.2 におり、endPointState が次のようになっているとします。

EndPointState 10.0.0.1
  HeartBeatState: generation 1259909635, version 324
  ApplicationState "load-information": 5.2, generation 1259909635, version 45
  ApplicationState "bootstrapping": bxLpassF3XD8Kyks, generation 1259909635, version 56
  ApplicationState "normal": bxLpassF3XD8Kyks, generation 1259909635, version 87
EndPointState 10.0.0.2
  HeartBeatState: generation 1259911052, version 63
  ApplicationState "load-information": 2.7, generation 1259911052, version 2
  ApplicationState "bootstrapping": AujDMftpyUvebtnn, generation 1259911052, version 31
  ApplicationState "normal": AujDMftpyUvebtnn, generation 1259911052, version 62
EndPointState 10.0.0.3
  HeartBeatState: generation 1259812143, version 2142
  ApplicationState "load-information": 16.0, generation 1259812143, version 1803
  ApplicationState "normal": W2U1XYUC3wMppcY7, generation 1259812143, version 6

受け取るゴシップダイジェストリストは "10.0.0.1:1259909635:325 10.0.0.2:1259911052:61 10.0.0.3:1259912238:5 10.0.0.4:1259912942:18" であることに注意します。受け取り側のエンドポイントがこれを扱う場合、次のステップが行われます。

ゴシップダイジェストをソート

ゴシップダイジェストリストを、送り手側のダイジェストと我々が持っている情報でそれぞれの最大バージョンの差分を取り、降順にソートします。 すなわち、もっともバージョン番号が異なるものを最初に扱うようにします。1つのゴシップメッセージにはいるエンドポイントの情報の数は限られています。このステップでは、最も差が大きいものから処理することを保証します。

ゴシップダイジェストリストを検査

このステージでは、到着するゴシップダイジェストリストを調べて、上で触れた GossipDigestAckMessage の2つのパートを構築します。すなわち、 ゴシップダイジェストリストとエンドポイント状態リストです。例を1つ1つ追ってみましょう。

10.0.0.1:1259909635:325 我々が持っている endPointStateMap では、世代は等しくなっています。そのため、10.0.0.1 は我々がゴシップを受け取ってから再起動はされていません。バージョン番号は我々の最大バージョン番号より大きくなっています (325 > 324)。そのため、送り手に対して、バージョン番号 324 から何が起こっているのかを聞かなければなりません。このために、我々はゴシップにダイジェスト 10.0.0.1:1259909635:324 を含めておきます。これは、私は 10.0.0.1 に対して世代 1259909635 バージョン 324 のことまで知っています。これよりも新しいものがあったら教えてください、という意味です。

10.0.0.2:1259911052:61 これを検査すると、我々は送り手よりも 10.0.0.2 のことをよく知っていることが分かります。世代は一致していますが、我々のバージョン番号の方が、63 > 61 なので大きいためです。送り手の最大バージョンは 61 なので、我々はこれよりも新しい状態を探します。endPointStateMap を見ると2つあることがわかります。application state "normal" (version 62) と HeartBeatState (version 63) です。我々はこの ApplicationState を送り手に送ります。この場合、ダイジェストをおくっているのではないことに注意してください。ダイジェストは単に最大のバージョン番号を教えてくれるだけです。我々は差異はすでに知っているので、ApplicationStates 全てを送信します。

10.0.0.3:1259912238:5 この場合、世代がまず一致していません。我々の世代は、受け取ったものより小さくなっています。すなわち、10.0.0.3 はリブートされたということがわかります。我々は送り手に、世代 1259912238 のバージョン 0 から全てのデータを送ってもらうことを要求します。すなわち、我々はゴシップに 10.0.0.3:1259912238:0 を入れるようにします。

10.0.0.4:1259912942:18 我々はこのエンドポイントについて何も知りません。そのため、我々は、10.0.0.3 と同様に、全ての情報を送ってもらうことを要求します。返答メッセージに 10.0.0.4:1259912942:0 を含めます。

この時点で、次のようなメッセージを含む GossipDigestAckMessage が構築されました。

10.0.0.1:1259909635:324
10.0.0.3:1259912238:0
10.0.0.4:1259912942:0
10.0.0.2:[ApplicationState "normal": AujDMftpyUvebtnn, generation 1259911052, version 62], [HeartBeatState, generation 1259911052, version 63]

GossipSynMessage の送り手にこの GossipAckMessage を送ります。

Main Code Pointers:

GossipDigestSynVerbHandler.doVerb: Main function for handling GossipDigestSynMessage
GossipDigestSynVerbHandler.doSort: Sorts gossip digest list
Gossiper.examineGossiper: Examine gossip digest list
Gossiper.makeGossipDigestAckMessage: Constructs GossipDigestAckMessage from a list of gossip digests

GossipDigestSynVerbHandler

GossipDigestAck2Message

あとでちゃんと書く

stats