最近、Raftを実装しています。

Raftは、各タームごとにリーダーが一人だけ存在し、 そのリーダーはフォロアに対してハートビートを投げ続けることによって そいつらが選挙タイムアウトすることを防ぐという仕組みが論文には記述されています。

これらのハートビートの間隔や、選挙タイムアウトは、「単一の値をあらかじめ決めておく」 ということになっていて、まず第一にこれがめんどくさいから自動化したいという要求があり得ます。

もしそんな要求がないとしても、サーバが世界中に地理分散していて、各ノード間の レイテンシが異なる場合には、単一のハートビートを決めることが出来なくなります。 敢えていうと、もっとも遅いノード間に合わせれば良いということになって、 それでも運用は出来るとは思うのですが、実際にはリーダーの障害をより早く検知することが出来るのだから この点では最善とはいえません。

もし、ハートビートの間隔や、選挙タイムアウトを適応的に決めることが出来れば、 運用が楽になりますし、サーバが地理分散していても問題がなくなるはずです。 つまり、リーダーから常時50msでハートビートが来てるノードは100msくらい待ってこなかったらリーダーの障害を 疑えるし、500msかかってるノードは、100msではまた疑ってはならず、1000msくらいは待ちましょうという「感じ」 のことが出来ればいいわけです。しかしこれには理論的な裏付けが全くありません。適当すぎます。 ファッキン適当エンジニアリングです。

自然と、次のようなアルゴリズムを考えるに至ります。

前N個のハートビート間隔を保存しておいて、その外れ値を落としたあと平均をとって、それをもとにして 選挙タイムアウトを決めればよいのではないか。

しかし、これもやはり、理論的な裏付けがないのです。 ハートビートと選挙タイムアウトはRaftのクラスタを安定させるための極めて重要な要素であり、 ここでヒューリスティックはまずいのです。

でも、このアイデアをベースにして理論的な裏付けを足したアルゴリズムがあるのです。 それがPhi Accrual Failure Detectorです。（以下Phi-FD） Accrualは、「アクルーアル」と読むのですがAccumulationみたいな意味の英語です。

Phi-FDのアルゴリズムを超ざっくりと肝だけ説明します。

一応、おもむろに実装してみました。 https://github.com/akiradeveloper/phi-detector

Phi-FDでは、ハートビートのインターバルは正規分布すると仮定します。

この正規分布が与えられた上で、前回のハートビートからの時間tを与えると、 これから無限時間待ったとしてどのくらいの確率でハートビートが得られるかが計算出来ます。 （確率密度関数の積分です） これをP(t)としましょう。

明らかに、tが大きくなればなるほど、次にハートビートが来ることがどんどん望めなくなります。 まるで、年齢が上がれば上がるほど結婚出来る確率が低くなっていくおれの現実のように（泣） うあああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああ

これがアルゴリズムの肝です。

では、いかにも仰々しいPhiとは何なんでしょうか？ PhiというのはP(t)の逆数のようなものです。 実際には対数ですが、意味は同じです。

このPhiはスレッショルドとして使います。 つまり、Phiをものすごく高くとるということは、 ものすごくP(t)が低くなるまで死亡判定はしません ということを言っています。

次は、Phi-FDをRaftライブラリに組み込もうと思っていますが、 なんとなく、同時立候補を避けることが難しくて、 「選挙タイムアウトは固定でないといけない」という結論に至りそうな予感がします。 とはいえ、馬鹿は考えても意味はないのでやってみます。

あなたの「いいね」、待ってます。 https://github.com/akiradeveloper/lol