Reading “Raft” – consensus algorithm

Raftという、合意アルゴリズムが存在する。これは、多数決を元にした多数派の意見を決定するためのアルゴリズムで、分散環境下における合意形成でも使える。最近、分散系の幾つかのWebサイトを眺めていると見つけた。

私は、こういう系統の技術分野は大学院の頃にByzantine General Problemを扱ってから比較的興味を持っている。

実際のツールだと、CoreOSのetcdやhashicopeのconsulなんかで使われているみたい。

Raft自体に関係するところは以下。

• https://raft.github.io/
• http://thesecretlivesofdata.com/raft/

幾つかの言語で実装されているみたい。etcdではgolangぽい。

• Erlang実装の1つ
  • https://github.com/dreyk/zraft_lib
• Elixir実装の1つ。
  • https://github.com/mururu/rafute

幾つかRaftの論文のreferencesを見てみましたが、Byzantine faultなんかはやぱり参考にされていました。2014年が論文としては初出？

LESLIE LAMPORT氏によるByzantine General Problemの問題は、懐かしさがある(大学院の頃によく読んでいた)。最近はご無沙汰だけれど、技術だけの話でいうとこれ系が関わる仕事はしてみたいな。

参考

• http://blog.obfuscatism.net/2014/12/01/raft.html
• http://kumagi.hatenablog.com/entry/distributed_system_taxonomy_part4