はじめに

Raft Consensus Algorithm の論文 “In Search of an Understandable Consensus Algorithm” http://ramcloud.stanford.edu/raft.pdf について簡単に紹介する。 また、論文のついでに読んでおくと理解が捗ると思われる文献（スライド、ウェブサイト）も紹介する。

というのも先日、ふと システム系論文紹介 Advent Calendar 2014 という物を私が立ち上げてしまったので、言い出しっぺの自分が先陣を切らせてもらう。 とはいえ今回の論文紹介にじっくり時間をかけて取り組めなかったため、雑な紹介になってしまう点はご了承いただきたい。

12月6日（土）に開催される 第3回 システム系論文輪読会 - connpass もあるため、輪読の発表会に興味のある方は是非参加いただきたい。

Raftとは何か。論文を読まずに雰囲気を理解する

Raftはコンセンサスアルゴリズムという、分散システム向けアルゴリズムのひとつである。 コンセンサス（合意）の簡単な例を出すと、リーダー（マスター）とスレーブ関係のあるクラスタを構築したとき、リーダーであるマシンが障害によりクラッシュ／通信途絶したようなときどうやって次のリーダーを選出するかという問題があり、それを解決するアルゴリズムがコンセンサスアルゴリズムである（リーダー選出, Wikipedia: Leader election 。もちろんリーダー選出以外にも合意する事柄は存在し、他にもいくつかの使い道がある）。

同じくコンセンサスアルゴリズムの有名なものにPaxos(wikipedia)があげられるが、実装の難易度が高いことでも知られている。 Raftについては、しばらく前から、 CoreOS プロジェクトで使われている・開発されたKVSである etcdにRaftが使われているということで最近は注目を浴びている様子である。

いきなりAdvent Calendar／本エントリの意義が問われそうであるが、アルゴリズム紹介という意味では無理して紹介文や論文を読まずに理解できるのならそれに越したことはない。 というわけでまずは参考資料を先に紹介する。 全体の概要をつかむためにも、先にこれらをぱらぱら読んでおきたい。

Raft from Preferred Infrastructure & Preferred Networks

論文を読む

上の資料を読んでいると、わざわざ論文は読まなくてもいいんじゃないかと思えてくる（すみません）。 自分でRaftを実装してみたい、となるとやはり読んだ方が良いと思う。

RAMCloudとは何なのか

論文や関連文献を見ていると、RAMCloudというキーワードが何度か出現する。 RAMCloudとは一体なんなのか。 ざっと読んだ限りでは、オンメモリ（DRAM）上に全てのデータを乗せるストレージシステムらしい。 RAMCloudのシステムを構成するクラスタ間では、Infinibandや10GbEなどの高速なインターコネクトで接続する。 また、 http://raftconsensus.github.io にも載っているRaftを使ったLogCabinという分散ストレージがRAMCloudプロジェクト内で開発されていたらしい。

  • https://ramcloud.atlassian.net/wiki/display/RAM/RAMCloud
  • RAMCloudsの根拠
    • 2011年ではあるが、InfoQ の記事のツッコミは結構痛い

そして、Raftの論文の著者である Diego Ongaro氏とJohn Ousterhout 氏の二人ともRAMCloudプロジェクト関係者（詳しく確かめてないが、もしかしてFounder？）である。 ここは今後論文を漁るときに注意しておきたいと思った点である。

検索してみた限りでは、RAMCloud自体はそう流行っているわけでもなさそうだ。 同じくStanford発であるSparkとは少し対称的かなと思ってしまった。

まとめ

本当は論文を読むつもりだったが、読み終わらなかったので紹介ということで参考文献を紹介して体裁を整えることにした。 Paxosと比べて理解が容易・実装しやすいらしいので、Paxosに挫折した人は論文も読んで、実装も是非挑戦してみてはいかがだろうか。 Raftが開発された経緯やRAMCloudプロジェクトはもっと深追いするのに興味深いトピックかもしれない。