etcd総選挙を眺めてみる

##はじめに
(2015/09/20追記)
初出時はv0.3.0くらいだったetcdも今の最新は2.2.0。起動時のオプションやAPIも非互換な形で変わってしまっているので、最新に合わせてお試し部分を少し修正。(@takiuchiさん、ご指摘ありがとうございます)

##etcdとRaft

etcdはCoreOSで使われている軽量KVSで、Configurationなどの情報を複数のマシン間で共有できるようにする仕組みみたい。/etcに置かれた設定ファイルの置き換え的な意味合いで "etc" daemonなのかなと思ったが、語源を発見できず、もしかしたらぜんぜん違うかもしれない。

ともかく、etcdはKVSでありながら複数マシン間でのreplicationを実現している。まぁ、そんなKVSは沢山あるが、etcdで取っているアプローチがやや面白かったのでちょっと調べてみた。

まず、基本になる考え方が、Raft Distributed Consensus Alrogithm/Protocolという技術。分散環境において「合意」を取り付けるためのアルゴリズムおよびそのプロトコルだが、民主的かつ合理的な考えをベースにしている。作ったのはDiego OngaroというスタンフォードのPhD学生と、その指導教官であるJohn Ousterhout。

ちなみにOusterhout先生はTcl/Tkを作った人だった。軽量なスクリプト言語がほとんど無い時期に簡単なGUIも含めて作れる環境は画期的だった。ボクもだいぶお世話になった。そして最悪な言語仕様(と言うか、言語処理系の実装)に悩まされた。その後Pythonが出てきて即そちらに鞍替えしたが、ExpectというInteraction自動化のためのツール(Hubotのはしりの様なもの)とかもあって周りでは暫く使っている人はいたなぁ。イカン、脱線した。

Raft概要

Raftに関しては一から理解されたい方は上記二人共著の論文のドラフトが以下にあるのでそちらをどうぞ。ちなみに私は全然読めてません。

Raftを理解する上でもう少し楽なのが、このビデオで、Ousterhout先生自らが説明してくれている。

この冒頭で説明してくれているのだが、Raftでは非対称な(つまり各ノード間で役割の差がある)、リーダーの居るモデルを採用している。対案としては、各ノードが平等で常にコンセンサスを取りながら進めるモデルがあるが、リーダーがいた方が効率的というのがRaft側の主張。通常時の動作を簡略化できるし、「合意形成」というプロセスをリーダー選出時だけに集約できる。まぁ、納得のいく主張だ。

各ノードの役割は基本的に3つ。命令を出す側の Leader とそれに従順に従う Follower、そしてLeaderがいなくなった時に一時的に現れる Candidate。当たり前だが一つのクラスタにリーダーは一人。

そして Term (期間・任期)という考え方が取り入れられていて選ばれたリーダーはそのTermの間だけリーダーであり続ける。実はリーダーが決まらない期間も一つのTermとするのだがそれは後ほど。

我々が普通に行っている選挙とちょっと違っているのは、この任期はリーダーが健在の間はずっと続く。リーダーが長期間に渡って常に正しく振る舞うことを前提にした、まぁ通常世界ではあまり考えにくい前提だが、効率の側面からもそれは理解できる。逆にリーダーがいなくなった時に選挙が行われ新たなリーダーが選ばれる。

リーダーを選出するプロセスは次の章で説明するが、一度決めたリーダーは何らかの理由(例えばシステムクラッシュやネットワーク断など)でいなくなるかもしれない。そのために、リーダーは存在感を示さなければならない。存在感というか存在そのものか。そのために、何もなくても一定時間ごとに各ノードに対して空のコマンドを発行し続ける。俗にHeartbeatsと呼ばれるが「オレ、居るからねー」と言い続ける感じ。

リーダー選出プロセス

あまり正確ではないかもしれないけど、私の理解した範囲でリーダー選出までの流れを書いてみる。

1. ノードは立ち上がるとFollowerになる。そして、既に居るはずのLeaderからのheartbeatsを待つ。
2. 一定時間(100ms-500msのランダム値)経ってLeaderからのお知らせが来ない場合はLeader不在と判断し、自らLeader候補として立候補する(Candidateになる)。その時に内部に保持しているTermの値を一つ増加させる。
3. Candidateはグループ内の他のノードに対して「第n期のリーダーとしてオレに投票して」ってお願いする。
4. 投票依頼に対して過半数のOKを貰えれば正式にリーダーになり、heartbeatsを送り始める。もし他のノードから「オレがリーダーになったから」と言われればスゴスゴとそれに従いFollowerに戻る。もう一つの可能性としては誰も過半数を取れないということが考えられるがその場合は再度Termの値を更新して再選挙。この最後の例が前に出てきた「リーダー不在のTerm」になる。

基本的にはこれだけ。

なお、この選出プロセスに関してはこのプレゼンが理解の手助けになった。Raftの概要説明としてもとても良いプレゼンです。

リーダーの離脱と復帰

5つのノードからなるクラスタを考える。ノード#1がLeaderでノード#2から#5がFollowerとする。ここで例えばノード#1がネットワークから切り離されたとする。例えばスイッチの故障とかで。しばらくするとリーダーからのお知らせが来ていないことに皆気がつく。

そうなると再選挙になるのだが、Candidateになって手を挙げるまでの時間は各ノードで異なる(タイムアウトはランダムに決められるため)。基本的には最初に手を上げた人が他の人からの承認を貰って新リーダーになる。時間的に近いタイミングで複数が手を挙げてしまうことはあるが、上記のプロセスでいずれ#2から#5の中から一人が選ばれる。

では、ノード#1が復帰してきた時にどうなるか。この人は自分が切り離されている間に選挙が行われて新リーダーが選ばれた事を知らない。切り離された間はコマンドを送ってもFollowerから返事が無いことはわかるが、わかるのはそれだけ。

で、リーダー気分で「オレ、居るからな―」とheartbeatsを送る。というか送り続けている。Followerから「判っとります」と返事が来ることを期待しているが、代わりに受け取るのは「オレ、リーダーだからなー」という新リーダーからのお知らせ。

「えっ」となるわけだが、ここで威力を発揮するのがTermの概念。新リーダーが主張しているのは第n代のリーダー。一方、オレは第(n-1)代のリーダーだ。「そうか、オレの時代は終わったのか…」とつぶやきはしないと思うが、素直にFollowerの立場になり、新リーダーの命令を忠実に実行する役割に回る。

実例

文章だけでは判りにくいので試してみる方法を考えてみた。せっかくなのでetcdを使おう。

etcdはgo言語で実装されていて、goのRaft実装であるgoraftを基板に使っている。CoreOSで使うのが筋かと思うが、実験のためにOSXの上で5つのインスタンスを同時実行してみる。

GithubからCloneしてきてビルドしても良いが、homebrewにあるのでそれをインストール。2015/09/20現在、v2.2.0は未だ来ていなくてv2.1.2が最新の模様

$ brew update
$ brew install etcd
$ /usr/local/bin/etcd --version
etcd Version: 2.1.2
Git SHA: GitNotFound
Go Version: go1.5
Go OS/Arch: darwin/amd64

実行には幾つかパラメータの指定が必要。ノードの指定は昔のバージョンではIP:PORT形式だったが、最近はURL形式、しかも複数指定できるようだ。冗長かもしれないが、以下を行う

• -listen-peer-urlsと-initial-advertise-peer-urlでピア間通信の為のURLを指定
• -listen-client-urlsと-advertise-client-urls でAPIアクセスの為のURLを指定
• -initial-cluster でクラスタを構成するノードのURL一覧
• -initial-cluster-state クラスタの初期状態の指定

そして以下は以前と同じだ

• -data-dir 各ノードの状態をファイル保持するためのディレクトリ
• -name 各ノードの名前

一々指定するのが面倒だったのでシェルスクリプトにしてみた。

#!/bin/bash
index=$1
HOST=127.0.0.1
PR_PORT=$(expr 2380 + $index)
MY_PORT=$(expr 4000 + $index)
CLUSTERS="machine0=http://127.0.0.1:2380,machine1=http://127.0.0.1:2381,machine2=http://127.0.0.1:2382,machine3=http://127.0.0.1:2383,machine4=http://127.0.0.1:2384"
MACHINE_NAME=machine$index
ETCD=/usr/local/bin/etcd
$ETCD \
　-initial-advertise-peer-urls http://$HOST:$PR_PORT \
  -listen-peer-urls  http://$HOST:$PR_PORT \
  -listen-client-urls http://$HOST:$MY_PORT \
  -advertise-client-urls http://$HOST:$MY_PORT \
  -data-dir machines/$MACHINE_NAME\
  -name $MACHINE_NAME \
  -initial-cluster $CLUSTERS \
  -initial-cluster-state new

これをetcdのディレクトリに置いた上で、terminalを5枚開く。そしてそれぞれで以下の引数の0の部分を1, 2, 3, 4と変えながら実行。

$ cd etcd
$ ./run_etcd.sh 0

リーダーは、吐かれているログを見ると判る。ただし、名前でなくidで書かれているのでマシン名を知るにはメンバのリストを出して確認。昔はリーダのIP:PORTが一発でわかるAPIが提供されていたのだが、いつの間になくなってしまった。なので、少し面倒だが、

$ url http://127.0.0.1:4000/v2/members

でノードのidとMachine名とクライアントURLを確認し、例えば、リーダーがmachine1であれば、

$ url http://127.0.0.1:4001/v2/stats/leader

とすると、確認できる。上記のAPIはLeader以外では{"message":"not current leader"}が返ってくる。

で、ここでおもむろにmachine1のterminalでCtrl-Cして殺してみる。すると他のノードのwindowがワタワタし始める。しばらくしてもログの更新が止まらないのが新リーダー。machine1のterminalで再度先ほどと同じ ./run_etcd.sh 1をすればwarningは止まる。念のため、各ノードのログを見ると、どれがリーダーになったかが判る。そして、それが例えばmachine0であれば、

$ curl http://127.0.0.1:4000/v2/stats/leader

とすると確認できる。

ここでさらに新たにリーダーになったノードを殺してみると今度は別のノードがリーダーになる。2つ一度にダウンさせてみるとか色々試してみると面白い。

書き始めた時の想定よりも相当長くなってしまったが、備忘録的な意味合いも含めてあげておこう。本当はetcdがどうやって設定データをお互いに更新し合っているのかを調べたかったのだが、そこまで辿り着かなかった。それはまた次回(はあるのか？)

関連記事

• 分散合意アルゴリズム Raft を理解する
  • この記事とは違って真面目にRaftを解説されています。