分散システム読書リスト（2014）
(dancres.github.io)- 分散システムを学ぶ核心は、特定の技術よりも考え方の転換にあり、このリストはインターネット規模のシステムを設計するときに直面する問題をテーマ別にたどれるようにしている
- 資料は、設計思想、レイテンシ、AmazonとGoogleの大規模システム事例、一貫性モデル、理論、ツール、インフラ、ストレージ、合意アルゴリズム、ゴシッププロトコル、P2Pに分かれている
- CAP、2PC回避、eventual consistency、楽観的レプリケーションは、一貫性と可用性を同時に最大化するのが難しいという運用上のトレードオフを示している
- Google論文群は、MapReduce、Chubby、GFS、BigTable、Dremel、Spanner、Photon、Mesaのような大規模分散システムの実装事例を提供し、Amazonの資料はサービスベースアーキテクチャへの移行と組織文化をあわせて扱っている
- Paxos、Raft、FLP、Lamport Clock、Byzantine Generals、Chord、Kademlia、Pastryまで続けて読むと、合意・時間・レプリケーション・ルーティングの問題を一つの流れとして整理できる
考え方と設計の視点
- 分散システムで最も難しい部分は考え方を変えることであり、このリストはその転換を助ける記事や論文から始まる
- 「Thought Provokers」は、大きなサーバー、データベース、トランザクションだけですべての問題を解決できるわけではないという視点を扱っている
- Harvest, Yield and Scalable Tolerant Systems: CAPの実際の適用を扱う
- On Designing and Deploying Internet Scale Services: James Hamiltonによるインターネット規模サービスの設計とデプロイに関する資料
- The Perils of Good Abstractions: 完璧なAPIやインターフェースを作ることの難しさを扱う
- Chaotic Perspectives: 大規模システムの予測不能性、無秩序、並列性を強調する
- Pat HellandのData on the Outside versus Data on the Inside、Memories, Guesses and Apologies、Building on Quicksandも含まれる
- Jim WaldoのWhy Distributed Computing?と、Waldo、WollrathらによるA Note on Distributed Computingもあわせて読む資料である
レイテンシとインターネット規模サービス
- 「Latency」は、レイテンシは常に存在するという前提で、アーキテクチャがどのような影響を受けるかを扱う
- Latency Exists, Cope!: レイテンシへの対応方法とアーキテクチャへの影響を扱う
- Latency - the new web performance bottleneck: Web性能のボトルネックとしてのレイテンシを扱う
- The Tail At Scale: 大規模システムにおけるレイテンシ、特にtail latencyの問題を扱う
- Amazonの資料は、技術選択だけでなく、サービスベースアーキテクチャへの移行過程で形成された文化と組織まであわせて見る
- A Conversation with Werner Vogels: Amazonのサービスベースアーキテクチャへの移行を扱う
- Discipline and Focus: Amazonのサービスベースアーキテクチャへの移行をさらに扱う
- Vogels on ScalabilityとSOA creates order out of chaos @ Amazonも含まれる
Googleのシステム論文と一貫性モデル
- Googleのまとまりは、MapReduceからMesaまで、分散システムの「rocket science」と見なせる大規模システム論文を一か所に集めている
- MapReduce
- Chubby Lock Manager
- Google File System
- BigTable
- Dremel: Web規模データセットの対話的分析
- Megastore: データセンター間で低レイテンシのPaxos実装を実現するための設計
- Spanner: スケーラブルで、マルチバージョン、グローバル分散、同期レプリケーションされるGoogleのデータベース
- Photon: 連続データストリームのフォールトトレラントでスケーラブルなjoin
- Mesa: Googleのインターネット広告事業に関する中核的な測定データを保存する、地理的にレプリケーションされた準リアルタイムのスケーラブルなデータウェアハウス
- 「Consistency Models」は、システム環境に合わせて一貫性と可用性の間の妥協点を探る資料で構成されている
- CAP Conjecture: Consistency、Availability、Partition Toleranceを同時にすべて満たすことはできないという内容
- CAP Twelve Years Later: Eric Brewerが当初のトレードオフの説明を拡張している
- Werner VogelsのConsistency and AvailabilityとEventual Consistencyが含まれる
- Avoiding Two-Phase Commitと2PC or not 2PC, Wherefore Art Thou XA?は、2フェーズコミットの回避と限界を扱う
- Starbucks doesn't do two phase commit: 非同期メカニズムを扱う
- Optimistic Replication: データレプリケーションのための緩やかな一貫性アプローチを扱う
理論、言語、インフラ、ストレージ
- 「Theory」は、分散システム設計で繰り返し登場する経済性、障害仮定、時間、合意の限界を理解するために必要な資料をまとめている
- Distributed Computing Economics: Jim Gray
- Rules of Thumb in Data Engineering: Jim GrayとPrashant Shenoy
- Fallacies of Distributed Computing: Peter Deutsch
- Impossibility of distributed consensus with one faulty process: FLPとしても知られる論文で、アクセスにはアカウントや支払いが必要な場合があり、無料版のリンクもあわせて提供されている
- Unreliable Failure Detectors for Reliable Distributed Systems: FLPの難しさに対処する方法
- Lamport Clocks: 各コンピュータの時計が独立しているときに、時間のグローバルな見方を確立する問題
- The Byzantine Generals Problem
- 言語とツールの資料は、特定の技術を選ぶだけで信頼性の問題が消えるわけではないことを示している
- Programming Distributed Erlang Applications: Pitfalls and Recipes: ErlangとOTPを選ぶだけで、信頼性の高い分散アプリケーションの構築が単純になるわけではない
- インフラの資料は、時計管理がデバッグのような基本作業にも不可欠であることを扱う
- ストレージの資料は、分散キャッシングやDynamoのようなストレージ設計へとつながる
合意、ゴシップ、P2P
- Paxosのまとまりは、Paxosの理解そのものが難しいという前提から始まり、Paxos Made Simpleを先に読み、他の論文の後でもう一度読む流れを勧めている
- The Part-Time Parliament: Leslie Lamport
- Paxos Made Simple: Leslie Lamport
- Paxos Made Live - An Engineering Perspective: Chandraら
- Revisiting the Paxos Algorithm: Lynchら
- How to build a highly available system with consensus: Butler Lampson
- Reconfiguring a State Machine: クラスタメンバーシップの変更
- Implementing Fault-Tolerant Services Using the State Machine Approach: Fred Schneiderのチュートリアル
- 他の合意論文は、WAN環境とPaxosの代替をあわせて扱う
- Mencius: 広域ネットワーク向けの合意アルゴリズム
- In Search of an Understandable Consensus Algorithm: Raft論文の拡張版で、Paxosの代替
- ゴシッププロトコルの資料は、感染症的な振る舞いを持つ通信、モニタリング、メンバーシッププロトコルを集めている
- How robust are gossip-based communication protocols?
- Astrolabe: 分散システムのモニタリング、管理、データマイニングのための堅牢でスケーラブルな技術
- SWIM: スケーラブルで弱一貫性のinfection-styleプロセスグループメンバーシッププロトコル
- P2Pの資料は、分散検索、ルーティング、ストレージ、アプリケーションレベルマルチキャストをたどれるようにしている
1件のコメント
Hacker News のコメント
このリストは少し古く見えるので、Heidi Howard の分散合意リーディングリストをおすすめします
https://github.com/heidihoward/distributed-consensus-reading...
この分野の「ロケットサイエンス」として Google の MapReduce が挙げられているのを見て、何か変だと思いました
確認してみると、このリストは 2014 年の資料なので [1]、今では状況がかなり変わっている点に注意が必要です
[1] https://news.ycombinator.com/from?site=dancres.github.io
約 10 年前に作った、分散システムのリーディングリストのメタリストがあります
このリストも 10 年ほど遅れて追加しましたが、私が集めておいた項目のうち今も生きているものがどれだけあるかは、神のみぞ知るという感じです
https://gist.github.com/macintux/6227368
元記事のリストに触れている https://ferd.ca/a-distributed-systems-reading-list.html もあわせて読む価値があります
限界を押し広げたり新しいアプローチを探したりする人には役立つかもしれませんが、それ以外の人にとっては、二次方程式の解き方を尋ねたら圏論の論文を 100 本渡されるようなものです
Fred Herbert のリストは元記事より新しいものの、本人も完全ではないと言っています。彼は「Designing Data-Intensive Applications」を必読に挙げつつも、本当に理解するにはまず多くの論文を読む必要がある、というような言い方をしています
こうしたリストが理解の前提条件のように提示されると、参入障壁を上げることのように感じられます
何十年にもわたって積み重ねられてきた他人の成果のおかげで、効果的な Linux ユーザーになるためにナノカーネルの論文を 100 本読む必要はありません。優れた OS をゼロから作るのは今でも難しいですが、99% の人はそれをする必要はなく、既存のツールをうまく使いこなせばよいのです
分散システムも同じで、最前線を押し広げるのでなければ、そこまで難しくある必要はありません
研究を深掘りするより実践経験を求めるソフトウェアエンジニアなら、NATS [1] や YugaByte [2] で何かを作ってみるか、[3] のような実践チュートリアルをやってみるのがよいでしょう
「Designing Data-Intensive Applications」も読む価値があります。読み返すほど良くなる本の一つなので、論文を 100 本読んでいなくてもそのまま読んで構いません。分からない部分が出てきたら質問して助けを求めればよく、巨大なリーディングリストは飛ばしても大丈夫です
1: https://nats.io/
2: https://www.yugabyte.com/
3: https://pragprog.com/titles/tjgo/distributed-services-with-g...
それでも CRDT 技術 への言及がないのか？