これは何？

分散システム初学者が、MITの院生向け講義 6.824: Distributed Systems を一通りやってみたので、その内容をまとめる。

分散システムなる分野に入門したいと思った際の一つの選択肢として個人的にオススメできるコンテンツだったので、この場で広く推すために書いている。

Lab3で扱うRaftのアーキテクチャ図より引用¹

きっかけ

元々のモチベーションとしては、お仕事周りでAurora²やDynamo³、EBS⁴といった文献に目を通す中で、そもそも根底にある分散システムという分野を全然知らない。俺たちは雰囲気でクラウドをやっている(画像略)⁵…という気分になったのがきっかけだった。

ちょうど年末の空き時間に分散システムのオススメコンテンツを探している中で、推されていたこのコンテンツに出会ったのが12月末。その後は仕事の後など空き時間にちまちまやって、結局Lab3まで終えたのが5月頭なので、計4ヶ月強取り組んでいたことになる。

6.824: Distributed Systems とは

現在MITの教員である [Robert Morris]
(https://ja.wikipedia.org/wiki/%E3%83%AD%E3%83%90%E3%83%BC%E3%83%88%E3%83%BBT%E3%83%BB%E3%83%A2%E3%83%AA%E3%82%B9) がLecturerを務める分散システム全般に関する講義であり、計21Lectureの中で様々なCase Studyが取り上げられ、perfomance、fault tolerance、consistencyといったトピックを学ぶことができる。

講義の中では、分散データベースや分散ファイルサーバー、分散計算処理基盤の有名所（最近は加えてBlockchain周りも）がピックアップされており、実績があって身近なシステムがテーマとして取り上げられるため、最後まで興味深く取り組めた。

良かった点

新旧の重要なトピックを網羅的に(ざっくりストーリーを作りつつ)カバーしてくれているので、自分のような初学者にはピッタリ
論文reading、講義でのインプットと実装課題でのアウトプットのバランスが良い
基本的に講義で扱うコンテンツや講義動画がpublicに公開されており、日本からでも空き時間に勉強できる ⁶

具体的な内容

こちらのスケジュール表に全てのコンテンツがまとまっているので、興味のある方はまずこのページをブクマしておいて欲しい。ここに全てのコンテンツへのリンクがまとまっている。

自分が取り組んだコンポーネントとしては、1)事前課題の論文reading、2)講義での解説、3)実装課題の3つ。他に中間・期末試験やoptionalで好きなテーマでの実装projectがあるがここでは省略する。⁷

事前課題の論文Reading

Lectureごとに論文や記事がアサインされており、合わせて用意されている簡単なQuestionに答えられる程には読み込むことが推奨されている。

このQuestionが優秀で、論文に目を通したけど何も頭に残らなかったという自体を回避できるスグレモノ。更に、それぞれの論文についてよくあるFAQまで用意されているので、至り着くせりである。

ちなみにQuestionにはたまに変則的なものも混ざっており、Bitcoin回は**「Bitcoinで何かものを買う体験をしてみろ」**だった。今後一生買わないかと思っていたBitcoinをここで買う羽目になるとは思わなかった⁸。

以下に実際に講義ごとに取り上げている論文/記事と、概要を示す。個人の感想も多分に含むので、一部正確さに欠ける表現もあるが、あくまで雰囲気を掴んでもらう目的で載せている。ぜんぜん違うよ！という箇所があればコメントで教えて頂きたい。

LEC1: MapReduce (2004)

大規模なデータ処理をMap、Reduceという形で記述することで、廉価なサーバーで構築したクラスタ上での分散処理を容易に実現できるプログラミングモデル、MapReduceの話。講義のゴールとしても掲げている"abstractions that hide the complexity of distribution"をまさに実現しているトップバッター。

LEC2, 5: Online Go tutorial, The Go Memory Model

後述のLabでGolangを扱うのでその予習

LEC3: GFS (2003)

従来の分散ファイルシステムとは違い、定期的に一部のコンポーネントが止まることは織り込み済みで、GB以上の大容量ファイルを主に扱い、シーケンシャルな読み書きが多い、そんな環境に最適化された分散ファイルシステムを構築した話。

LEC4: Fault-Tolerant Virtual Machines (2010)

Primary-backup replicationの一例として、VMWareのvSphere Fault Toleranceを扱っている。VMをstate machineとして捉え、primary VMの全てのinputを決定的なoperationとして順次backup VMに適用していけば両者を同じ状態で同期できるという話

LEC6,7: Raft (extended) (2014)

耐障害性を実現するためにreplicated state machineの仕組みがよく利用されるが、その基盤技術として複製されたログの一貫性を担保するコンセンサスアルゴリズムというものがあり、その一つであるRaftの話。 (multi-)Paxosと比較して、同程度に効率的だが、より理解しやすい仕組みを目指して開発された。理解しやすいのかとは思うが、バグのない実装が簡単にできるかというとそういうわけでもない。

LEC8: ZooKeeper (2010)

分散システムのコーディネーション用サービスであるZooKeeperの話。講義では、汎用的なコーディネーションサービスとしてのAPIの仕様と、サーバー台数を増やした際のパフォーマンスの向上に注目していた。特に読み込みは一貫性を緩めた分、diskや他サーバーへのアクセスを必要としないので、読み込みが支配的なアプリケーションで数10万rpsを出すことも可能だとか。

LEC9: Object Storage on CRAQ (Chain Replication with Apportioned Queries) (2009)

Primary-backup replicationの特殊系として、strong consistencyを実現しつつも高スループットで耐障害性のあるChain Replicationという仕組みがある。CRAQはそこからstrong consistencyは維持しつつ、読み込みのスループットをスケールアウト可能にした話。

LEC10: Aurora (2017)

みんな大好きAmazon Auroraの話。単なるRDBサーバーの同期レプリケーション時にスループットのボトルネックになっていたネットワークIOを削減するために、redo logのみをネットワーク越しでストレージサービスに送り、pageの生成などは全てストレージサービス側でバックグラウンド処理させる構成に変更。AZ障害や一部のサーバーの遅延の影響を最小化するために、Quoram modelを導入したりもしている。

LEC11: Frangipani:A Scalable Distributed File System (1997)

クライアント側のローカルキャッシュとストレージサーバーの組み合わせからなる分散ファイルシステムの話。ローカルキャッシュを持ちつつも、外部のロックサーバーを利用することで、strong consistencyを実現している。あるマシンで変更したファイルやディレクトリは即座に別のマシンで閲覧可能になるということ。

LEC12: 教科書 distributed transaction周り

AtomicityやTwo phase commitについて。と言いつつ自分は@kumagiさんの素晴らしい資料を読んでいたのだけど https://qiita.com/advent-calendar/2016/transaction

LEC13: Spanner (2012)

NoSQLのようなスケーラビリティとSQLデータベースの便利さを兼ね備えたNewSQLというカテゴリでも語られるSpannerの話。詳細は@kumagiさんの素晴らしい記事をどうぞ。

LEC14: FaRM (2015)

HWも含めてプロトコルを再考することで、爆速transactionを狙うdistributed KVSのプロトタイプ。Kernel bypassやRDMAを採用してserver間の通信が5μsと爆速。不揮発性DRAMを利用するのでdisk accessも発生しない。複数データセンターレベルの冗長性も求めない分spannerより二桁ほど爆速。

LEC15: Spark (2012)

大規模計算クラスタ上で、インメモリでの計算を容易に行うための抽象化を導入した話。MapReduceに比べると、メモリにデータを残したまま次の処理に繋げるのでdisk IOも少なくパフォーマンスが優れていてる。

LEC16: Memcached at Facebook (2013)

大規模にmemcachedを利用した際のCase Study。次第に規模が大きくなるにつれどのような課題が発生して、いかに対処したかを詳細に解説している。

LEC17: COPS (2011)

causal+ consistencyという一貫性モデルを定義し、それを満たすスケーラブルなKVSを実装した話。causal+ consistencyは、完全なeventual consistencyと比較すると、クライアント単位で一部の処理の因果関係が保たれている分挙動が直感的。strong consistencyと比較すると、サーバーをまたがった同期処理をする必要がないのでwriteのパフォーマンスも稼ぎやすくnetwork partition時にも可用性を高めやすいという位置付けなのだろう。

LEC18: Certificate Transparencyについての記事

Certificate Transparency(CT)という、PKIの証明書発行プロセスの透明性を担保する仕組みの話。従来は、CAが一部のクライアントにだけ悪意のある証明書を発行していてもサイトオーナーや利用者は検知しずらかった。CTでは、全員が同じappend-only log(証明書情報群)を見ていることを保証できる仕組みを作ろうとしていて、仮に上記の改ざんが生じた場合も比較的早期に検知できる。ちなみにこれは後段のBlockchainへの布石。

LEC19: Bitcoin (2008)

言わずと知れたビットコイン、ブロックチェーンの話。ただ分散システムの観点で興味深いのは、信頼できないノードの混ざった不特定多数のノードの中で、時間の経過に伴い合意した値が覆される確率が0に収束するようなプロトコルを提案したところなのかと思う。例えばノード数でのmajority voteではなく、計算リソース量に応じて確率的に合意が取れるProof of Workの仕組みを採用した点などは面白い。

LEC20: BlockStack (2017)

Blockchain上で非中央集権なDNSやPKIの仕組みを再構築するぞという話。ブロックチェーン
を非中央集権的で、順序保証や一貫性のあるlog replication基盤とみなし、その上でreplicated state machineを構築する発想は面白い。

LEC21: おまけこの講義のTAによって昔に書かれた論文を皆で読む

講義 (YouTubeに動画あり)

こちらのYouTubeのchannel に約1時間の講義videoがほぼ全てアップロードされている。内容は上記の事前課題で扱った内容について、特に分散システムの文脈で重要なエッセンスにフォーカスして説明するというもの。論文だけだと捉えづらかった分散システムという分野、歴史におけるその論文の位置づけを解説してくれる。

2020年度の前半はRobert Morrisが黒板の前で楽しそうに話している姿が眺められるのだが、後半はコロナの影響でホワイトボードでの説明に切り替わっているのは残念（内容的には問題ない）

また、たまにゲストが登場する回もあるのだが、例えば2021年度はGoのコアチームの一人のRuss Coxが直々にGoでconcurrencyを扱う際の実装のヒントについて話している。Robert MorrisとRuss Cox、なんて豪華な、、

実装課題

このパートが無ければ本講義の魅力は半減していただろう実装課題。課題(Lab)は計4つ。最近はGolangを使って以下のトピックを実装してみようというものになっている。

Lab1: MapReduce
Lab2: Raft
Lab3: Fault-tolerant Key/Value Service on Raft
Lab4: Sharded Key/Value Service on Raft (これはoptionalだったので自分は断念)

テストコードと、テストコードが利用する最低限実装する必要のあるインターフェースだけが用意されており、後は論文やヒントを読みながら好きに実装してねという形。ただ、テストコードは充実していて、ネットワークパーティションやサーバークラッシュ/リカバリが複合的にシミュレートされる環境下で、複数のクライアントからのアクセスにされされながらも要件を満たした挙動が取れているかしっかりチェックされる。ちなみに、書こうとすると論文が半分もまともに読めていないことに気づく。

正常系が動いて満足して動作してからが本当のスタートで、いかにLinearizableなKVSというものを実装することが難しいのかを痛感させられた。ちなみに自分は発狂した。Golangに慣れている人であれば発狂することなく書ける気はする。是非感想をコメントで教えて欲しい。

やってみた感想

全体を一通りこなしてみた感想としては、まだまだ研究室配属されてその分野の論文を読み始めた段階のような経験値ではあるが、この分野の解像度が少し上がった実感はある。

例えば最近ではWerner Vogels⁹が、Amazon S3のconsistency modelがstrong consistencyに変更された件に言及するブログを出していたが、その中でリリース当時の判断として、ごく低頻度で起こりうるeventual consistencyな挙動を許容して、高可用性に最適化したキャッシュの仕組みをメタデータ管理部分に採用するという判断を下した経緯が書かれていた。これは2006年当時は、画像のホスティングやバックアップがS3の主な利用用途であり、eventual consistencyでも特に問題はなかったからだということだ。

講義の中でも、パフォーマンスや可用性、一貫性等のトレードオフがある程度ある中で、その時代時代の各システムに求められる要件に合わせていい塩梅のバランスを取って設計がなされてきた歴史が書かれていたが、上記のS3の話についてもそんな試行錯誤の一つなのだと捉えることができる。

DynamoDBの裏側の仕組みを解説している動画を視聴した際にも、PaxosとRaftの違いこそあれ、実装課題Lab3,4の延長として実プロダクトには他にどのようなコンポーネントが必要なのかという観点で妄想しながら2倍楽しむことができる。

初めは講義の多さに3日坊主を覚悟しながら取り組み始めた 6.824: Distributed Systems だったが、完全な初学者からはじまって、分散システムという分野の概念、面白さ、辛さを垣間見ることができたのは良い経験になった。

これを読んで、一人でも6.824: Distributed Systemsに取り組む仲間が増えれば幸いです。

Have Fun!

In Search of an Understandable Consensus Algorithm(Extended Version) ↩
Amazon Aurora: Design Considerations for High Throughput Cloud-native Relational Databases ↩
Dynamo: Amazon’s Highly Available Key-value Store ↩
Millions of tiny databases ↩
本業は真面目にやっている。念の為。 ↩
4つ目を挙げていいのであれば、Robert Morrisが楽しそうに話しているのは見ていて楽しい。 ↩
具体的な内容については自分が扱った2020年度のものを対象として説明する。2021年度のものも現状ほぼ同じ認識。 ↩
ちなみに結局イーサリアムを買ったのだが、講義が終わって売るタイミングに3割伸びていた。なんだこれ。 ↩
CTO, AMAZON.COM ↩