リーダ選出: ring アルゴリズム
Raft Consensus Algorithm をみつけてリーダ選出とは、となったので調べてちょっと書いてみたメモ。なお、この記事では raft のことは書いてない。
リーダ選出とは
リーダ選出アルゴリズムとは、分散システム内で特別な役割を持ったノード(プロセス)を選出するためのアルゴリズムのこと。 リーダを決め、中央集権的にシステムを動かすことで、権限が分散している場合にくらべシステム内の一貫性を容易に保てる1。 たとえば、分散メモリがあるとすると、あるプロセスが分散メモリに値を書き込む際には、そのプロセスはロックを取ってから書き込みをしないとレースコンディションが発生する可能性がある。この時、一つのプロセスをリーダにし、そのプロセスが他のプロセスにロックを提供し、書き/読み込みをしたいプロセスがロックを取ってクリティカルコンディションに入ることで安全に分散メモリを操作できる。
ring アルゴリズム
ring 型のネットワークを考える。
ring型ネットワークとは、それぞれのプロセスが自分以外の２つのプロセスと結びついてる様なネットワーク。
要は以下の形をしたネットワーク。
CS 551: Synchronization, Token Ring Election Algorithm Exampleより
この記事での ring アルゴリズムは以下の話。wikipediaの分散システムのページを見てると、これは ring アルゴリズムの中でも Rings with unique IDs というやつっぽいのだけど、いまいち全体の世界観をつかめていないのでよくわかってない。
- アイデア : CS 551: Synchronization, A Token Ring Election Algorithm
- 図 : CS 551: Synchronization, Token Ring Election Algorithm Example
このアルゴリズムは election message を送るステップと coordinator message を送るステップの２つのステップに分かれる。
まず、現在のリーダが何かしらの理由 (通信不能になったり、プロセスが死んだり) で fail したところからリーダ選出が始まる。
リーダが fail したのを他のプロセスが検知して election message というメッセージを次のプロセスに送る。もし、次のプロセスが fail したリーダのプロセスだった場合はその次のプロセスに送る。
election message とは自分の id を追加した配列を含んでいるメッセージのこと。例えば、下の図の場合は P3 が自分の id である 3 というメッセージを、それを受け取った P5 は、受け取ったメッセージに自分の id である 5 を追加した 3,5 というメッセージを次のプロセス P0 に送る。
この 3 であったり、3,5 であったりを election message といっている。そして、election message が ring を一周して元のプロセス(図ではP3)に戻ってきたところで election message を送るステップは終了する。
CS 551: Synchronization, Token Ring Election Algorithm Exampleより
ここからが、次の coordinator message を送るプロセスになる。
election message が ring を一周して、最初にリーダの fail を検知したプロセスに戻ってきたとき、election message の中身は ringに所属しているプロセスのidが全て含まれている。この id の中から一番大きな値を選びだし、その id が次のリーダだということを他のプロセスに周知するメッセージが coordinator message になる。coordinator message が ring を一周して元のプロセスに戻ってきたところで coordinator message を送るステップも終了しリーダが決定する。
例えば下の図では、P3が最初にリーダの fail を検知したプロセスだとして、そこに返ってきた election message が 3,5,0,1,4 だとすると、この中から一番大きな数である 5 を次のリーダ(つまりプロセス P5 )とする。そこで P3 は 「次のリーダは P5 だ」というメッセージまた他のプロセスに送信する。このメッセージを coordinator message という。他のプロセスも自分の次のプロセスに「次のリーダは P5 だ」というメッセージをおくる。そして、P3 に戻ってきたところリーダ選出を終えて P5 がこのシステムのリーダとなる。
CS 551: Synchronization, Token Ring Election Algorithm Exampleより
作った
ring アルゴリズムを実装してみた。
ring アルゴリズム自体の実装は https://github.com/ganmacs/eve/blob/master/lib/eve/agent/ring.rb この辺にある。仕様的なものを見つけることができなかったので、上の図を見て気持ちを感じて実装した。
