CassandraでのCluster membersipとFailure detection

Cassandraでは、ノードのメンバシップをgossip-basedなprotocalでEventually consistentに管理しています。また、ノードの状態についても、gossip-basedなprotocolをベースに管理しています。

この、Gossipアルゴリズムというのは何かというと、噂の伝播をモデル化したもので、大雑把に書くと、

  • メッセージに通し番号を付け、 初めて受け取ったメッセージは受信者が処理して、ノードリストに記載された宛先リストに転送
  • 二回目以降に受け取った同一のメッセージは、処理せずに破棄（破棄などのパターンは、色々ありうる）
  • 上記のようにGossipを伝播しあう

といったことをします。

データがどこにあるかを一極集中でなく分散してCassandraではもってるわけですが、完全に分散しているとノードを幾つかホップして、データのありかを探さなければいけなくなるので、latency的には問題がでると。そこで、gossipアルゴリズムを使って、メンバシップを伝播しあうことで、データのありかをeventual consistentに管理することで、latencyを上げようというのが、このアルゴリズムを使う目的のようです。

では、以下CassandraのGossipの方法です。

CassandraでのGossipの方法

パッケージとしては、org.apache.cassandra.gmsです。

Cassandraでは、gossip exchangeを以下のルールにしたがってGossipします。

  • 生きているendpointにGossip
  • 到達不能なノードと生きているノードの数に応じて、到達不能なendpoindにランダムにGossip
  • Gossipされたノードがシードじゃない、または生きているノードの数がシードの数より小さければ、ランダムにシードにgossipする

実装としては、GossipTimerTaskのrunメソッド内。GossiperのGossipTimerTaskがgossipの肝。ここからたどって読めば、Gossip周りの流れが全てわかります。

Failure Detection

以下のようなクラス構成。

IEndpointStateChangePublisher <- Gossiper
IFailureDetecterEventListener <-
IEndpointStateChangeSubscriber <- StorageService
                               <- StorageLoadBalancer

StorageService, StorageLoadBalancerの初期化時に、Gossiper.instance.registerでEndpoint登録をしている。GossiperがSubscriberとしてのStorageServiceインスタンスを全て管理していて、IEndpointStateChangePuli

GossiperがTimerTaskで定期的にEndpointの状態チェック（doCheckStatusメソッド）をして、IFailureDetectionListenerを実装しているGossiperが、convictメソッドでendpoint群の状態をチェックして、その状態にしたがって、IEndpontStateChangeSubscriberであるStorageService(or StorageLoadBalancer)のonXXXメソッドを呼ぶ。状態は、Gossipメッセージで伝播している。IEndPointStateChangeSubscriberのinterfaceは、以下のようになってます。

public void onJoin(InetAddress endpoint, EndPointState epState);

public void onChange(InetAddress endpoint, String stateName, ApplicationState state);

public void onAlive(InetAddress endpoint, EndPointState state);

public void onDead(InetAddress endpoint, EndPointState state);

次は、データ構造。

EndpointStateのデータ構造

EndpointStateは、以下のようにApplicationStateとHeartBeatStateを保持しています。

 EndpointState -- ApplicationState
                     -- HeartBeatState
  • Gossipper
    • endPointStateMap
      • 全てのノードのステートを保持

GossipMessageについて

Syn, Ackについては後で追記。