読者です 読者をやめる 読者になる 読者になる

俺の報告

RoomClipを運営するエンジニアの日報(多分)です。

日報 #97 - phi_thresholdとheartbeatとfluentd

胃腸弱者故に年末はシンドイでござる。
油そば食ったら2時間以上もたれる程度には内蔵弱しです。

本日はfluentdのお話。
素晴らしいソフトfluentdなのですが、まれに激しい勢いでwarningを吐き出します。
常駐アプリのこわいところですね。
今回喰らったのは

[warn]: detached forwarding server

みたいな警告。
fluentdの受信サーバは正常で、今までもずっとつながっていたのに、
突如としてこうなりました。
端的に、hertbeatした結果サーバ応答が得られなかったということでしょう。
ではこのhertbeat、一体どういう仕組なんですかね。
http://bynatures.net/wordpress/3104/
http://blog.livedoor.jp/sonots/archives/36895001.html
この辺の素晴らしいサイトを参考にすれば解決はできるのですが、
イマイチこのphiとやらが意味不明なので、改めてそれについて調べてみましょう。
https://code.google.com/p/cassandra-shawn/downloads/detail?name=The+Phi+Accrual+Failure+Detector.pdf
ここに論文がございましたので、ちょっと読んでみます。

難しそうですが、むちゃくちゃ複雑というわけでもないので、簡単に説明します。 重要なのは序盤の説明部分と、phiの実装部分なのでそこの部分を抜粋します。

死活監視システムを、真偽値、いわゆる「死んでるか、生きてるか」の二択問題と捉えると、
現在の複雑なアプリケーションとしては不十分だと序盤で主張されています。
「同時処理的なアプリケーションの場合は、死活監視の結果を連続値で取得できる」事ができてしかるべきだと。

具体的な例をとって考えてみます。
論文のこの所。

Consider a distributed application in which one of the processes is designated as a master while all other processes play the role of workers. The master holds a list of jobs that needs to be computed and maintains a list of available worker processes. As long as jobs remain in its list, the master sends jobs to idle workers and collects the results after they have been computed. Assume now that some of the workers might crash (for simplicity, we assume that the master never crashes). Let some worker process pw crash during the execution; the master must be able to detect that pw has crashed and take appropriate actions, otherwise the system might block forever.

要はワーカーを複数抱えたマスタープロセスがあった時の話。
一部のワーカープロセスが死んじゃったよ!っていう死活監視が出来たとして、
適切な対応しないとシステム全体が死んじゃうよね?って話。

With accrual failure detectors, this could be realized as follows. When the confidence level reaches some low threshold, the master simply flags the worker process pw and temporarily stops sending new jobs to pw. Then, when reaching a moderate threshold, the master cancels all unfinished computations that were running on pw and resubmit them to some other worker processes.

だから、プロセスの死亡にも「連続値」を使うと便利だと主張されているわけです。
例えば、「あぁあのワーカー、疲れてきてるな、、、」と判断できれば、次々に仕事を投げるのを止めてみるって判断ができますね。さらに「あぁ、あのワーカー全然回復しない、アカンかもしらんぞ、、、」ってなったら、そいつに投げてた仕事で、終わってない奴は全部キャンセルして、他のワーカーに再度振り直すわけです。
最終的に「あいつ、ガチで逝きやがった」ってなったら初めて、ワーカーリストから外す。
こういう対応ができてしかるべきだという話です。

んで、問題はどうやって「死活監視を連続値で判定」するのかと。
簡単に云うとこんな感じらしいです。

Briefly speaking, the φ failure detector works as follows. The protocol samples the arrival time of heartbeats and maintains a sliding window of the most recent samples. This window is used to estimate the arrival time of the next heartbeat, similarly to conven- tional adaptive failure detectors [9], [10]. The distribution of past samples is used as an approximation for the probabilistic distribution of future heartbeat messages. With this information, it is possible to compute a value φ with a scale that changes dynamically to match recent network conditions.

ハートビートが到達するまでの時間をサンプリングして、スライディングウィンドウ(いわゆるバッファ。ただし逐次的に処理される)に保持する。そのサンプルデータを使って次のハートビートが来るのを予測する。(多分だけどポアソン分布みたいなものかな)過去のサンプル値は、将来のハートビートの近似値として使われる。こうすることで、「死活値」を連続値として、直近のデータを元に計算できるんですって。
なんか抽象的なので、一気に飛ばして、

IV. IMPLEMENTATION OF THE φ ACCRUAL FAILURE DETECTOR

この辺に飛びましょう。
そこに計算式が載ってます。

  1. Meaning of the value φ As mentioned, φ failure detector implements the abstraction of an accrual failure detector. The suspicion level of accrual failure detector is given by a value called φ. The basic idea of the φ failure detector is to express the value of φ on a scale that is dynamically adjusted to reflect current network conditions. Let Tlast , tnow , and Plater (t) denote respectively: the time when the most recent heartbeat was received (Tlast ), the current time (tnow ), and the probability that a heartbeat will arrive more than t time units after the previous one (Plater (t)). Then, the value of φ is calculated as follows.

φ(t[now] ) = − log10(P[later] (t[now] − T[last] ))

あらまぁ、案外と簡単です。
何となく図を見れば分りますが、
要は「次のハートビートが来るまでの時間とその確率の関係」でおちてるかどうかを捉えるという感じみたいです。
ハートビートってのが分かりづらいという場合は、本当に「心臓の鼓動」と捉えてみるだけでわかると思います。
死にそうな人がいたとして、あなたはその人の心拍をずっと計測しているとします。
あるとき「トクン」と聞こえました。
しばらく待っているとまた「トクン」と聞こえました。
あなたはそれをずーっと計測していて、 「まぁだいたい2秒に1回くらいトクンってする。その間はこの人は生きてるはず。」
っていう予想を立てたとします。

あるときまた「トクン」と聞こえました。(=T[last])
その前提で、この人が「次にトクンと返してくれる確率」を追い続けてみます。

最後の「トクン」から一秒も立っていない間に「トクン」と聞こえる可能性は低いです。
ですが、まだ二秒たってないわけですから、「次にトクンと返してくれる確率」はまだまだ高いままです。
で、二秒経ちました。
そろそろ「トクン」と聞こえて欲しい頃です。
ですが聞こえなかったとします。
あなたは不安に思います。
「このままこの人は死んでしまって、次にトクンと返してくれないんじゃないか…」と思うはずです。
つまり、「次にトクンと返してくれる確率」はグッと低くなった感じがします。
これは時間が立てば立つほど低くなり続けますね。
これを逆数にすれば、「次にトクンと返さない確率=死んでる確率」はどんどん大きくなっていくと解釈できます。
(この辺の説明は正確には正しくないですが)
この性質を数値化したのがphiみたいです。
つまり、コレが高ければ高いほど「っは!こいつ、死んでる!!」って思うわけですね。

で、問題はこのPの分布、いわゆる「大体二秒に1回トクンってするけど、三秒のときは確率いくつくらいで、一秒の時も確率いくつくらいで、、、」っていうのを連続関数にした式ものっています。
意外と正規分布を使っているようです。
ポアソン分布でもいい気はするのですが。
とにかく結構シンプルですね。

あぁ長くなりました。
面倒なのでこのへんで終わりにして、
fluentdの話。
fluentdも受信サーバの死活監視をこのシステムを使って判定しています。
なので、phiのしきい値が低いと「こいつ死んでるわ―」って判定してくるんですね。
受信サーバの応答が芳しくないとすぐ切っちゃったりするみたいです。
この辺はちゃんとfluentdのプログラムをよんで、実際どういう風にphiを計算しているのかを見るべきですが、
恐らくAWSとかの場合死活監視はCloudWatchなどで行っているはずなので別段気にせずphiのしきい値を大きくして構わないと判断しました。
まぁ最終的にはheartbeatの間隔と合わせて決めるべきですけど、、、
てなことで結論はシンプルでしたが、勉強になりました。
現場からは以上でした。