理系学生日記

おまえはいつまで学生気分なのか

Serfの基盤 SWIM プロトコル概要

protocol middleware

Serf

今週、暇なときわりかし Serf を調べてました。 Serf はみんな大好き HashiCorp 社が出しているソフトウェアなわけですが、Serf by HashiCorp に書いてあるとおり、大きく分けて 3 つの機能を持っています。

  1. クラスタのメンバ管理機能
  2. メンバの障害検出機能
  3. イベント伝搬

中心となるのはクラスタのメンバ管理です。メンバがあるところにはグループがあるので、グループの構成・維持機能と言い代えても良い。 世の中には数多、グループを必要とする機能というのはあり、一例を挙げても冗長性を提供する HA クラスタや、LB 配下に並ぶことになるであろう Web サーバのグループといったものなどがあり、こういった「特定の機能を持つサーバ/ノードの集合」という概念はシステム上の至るところに表れます。 これまで、このあたりのグループ管理機能というのはそれに付随する役割とともに提供される (たとえば、HA クラスタのクラスタ維持機能は HA ソフトウェアにバインドされていることが通常です)ことが多かったのですが、このグループ構成・維持機能を単一のソフトウェアに切り出したのが Serf です。

Serf は、中央集権のノードなしに、個々のノードが P2P でクラスタを構成するというアーキテクチャを取っており、このアーキテクチャで上述の機能を実現するための根幹となっているのが SWIM (Scalable Weakly-consistent Infection-style process group Membership protocol) と呼ばれるプロトコルです。公式ドキュメントにも記載があるとおり、このあたりの詳細は 論文 にまとめられているので、それをまとめてみました。 論文では、オリジナルの SWIM に対し、主にメンバシップ情報の伝搬に修正を加えているんですが、Serf 自身はノード間の伝搬スピードを上げるためにさらにプロトコル細部の修正を入れた実装になっているようです。

Gossip Protocol

SWIM 自身は、いわゆる Gossip Protocol、あるいは epidemic protocol と呼ばれるタイプのプロトコルです。 gossip protocol は Gossip Protocol にも書いてありますが

  • 個々のノードは、隣接ノードからランダムにいくつかのノードを選択し、情報を伝える

という動作を繰り返すことで、信頼性のない通信路上で、多数のノードが耐障害性の高い情報共有を行うことができるというプロトコルになります。

SWIM

メンバシップを管理するプロトコルで重要なのは以下の指標です。

  1. 故障したノードが検出されること、および、その故障から検出までに要する時間の短さ
  2. ノードが死んでいないにも関わらず「死んでいる」と判断してしまう偽陽性(false positive) の発生確率低減
  3. グループが大きくなる毎に[tex:O(n2)]で増えていくネットワーク負荷の解消

SWIM はこれらを実現するために、2 つのコンポーネントを持っています。

  1. 故障検出コンポーネント
  2. 情報伝搬(dissemination)コンポーネント

故障検出コンポーネント

SWIM の故障検出の仕組みを理解するのは簡単で、これを表現するのは以下のシーケンス図になります。 f:id:kiririmode:20150419181513p:plain 前提として、SWIM の各ノード (論文では Process と呼んでいます) は個々に、自分の属しているグループのメンバリストを保持しています。ここで任意のノード M_i は、プロトコルで定められた時間 T' に 1 回、メンバリストからランダムにノード(M_j) を選択し、そのノード M_j が生きているかどうかを確認する動作をします。 この動作は以下の通り。

  1. M_i は M_j に直接 Ping を送る。そのあと、M_i は M_j から Ack が応答されるのを待つ。もちろん、応答されれば、M_i は M_j が正常と判断する
  2. Ack が返ってこないままタイムアウトした場合、M_i はメンバリストから k 個のノードを選択し、「M_j に Ping を送っておくれ (ping-req(M_j)) という要求を k 個のノードに送る。このうちの 1 つのノードに M_j から ACK が返却されると、そのノードは M_i に ACK を転送する。
  3. 上記の流れにおいて、ACK が返ってこない場合に、M_i は M_j を故障していると判断する

このような動作は数学的に解析済であり、故障検出の時間はノード数 n が増加してもサチること、メッセージ負荷や false-positive の発生確率が n に依らないことなどが分かっています。

また、論文では、「故障した」と思われるノードをメンバリストから即消去せず、一定期間はそのままメンバとして扱う手法で false-positive の発生確率を小さくしようとしていますが、Serf はここにさらなる修正を加えているので、この詳細には触れません。

情報伝搬コンポーネント

「ノードが壊れてた」あるいは「このノードが新しく参加した」という情報は、グループ内の全ノードに伝搬させる必要があります。オリジナルの SWIM は、これをマルチキャストに頼っていましたが、論文の SWIM は、この部分も infection-style の情報伝搬にすることで、さらなる耐障害性の向上を図っています。Serf はこれを、ping や ack に、これらのメンバシップの情報を「一緒に載せる」ことで実現しています。

まとめ

SWIM 自身は、もちろん Serf 専用のプロトコルというわけではなく、かなり広範な分散システムに適用できるメンバシップ管理のプロトコルです。グループのサイズが大きくなっても耐えられるスケーラビリティ、激しいパケットロスの中でもグループを構成できる頑健性、そして何より、数学的な解析により各ノード間でメンバシップ情報を同期できる時間の上限がきちんと押さえられていることが大きいと思います。