分散システム

2021年春

概要

15-440は分散システムの入門コースである。 機能的で、使い勝手がよく、スケーラブルな分散システムを作るための技術に重点を置く予定です。 問題をより具体的にするために、クラスには、重要な設計と実装を必要とするいくつかの複数週のプロジェクトが含まれています

このコースの目標は2つあります。 まず、ロック、並行処理、キャッシュ、プリフェッチ、スケジューリング、ネットワーク上の通信など、分散システム設計の背後にある原理と技術を理解することである。 第二に、実際の分散システムの設計、実装、およびデバッグの実践的な経験を積むことである。

このコースが教える主なテーマは以下の通りである。

• リソースの希少性、スケジューリング。 通信の遅延と帯域幅
• ネーミング
• 抽象化とモジュール化
• 不完全通信と他のタイプの障害
• 偶発的および悪意のある害からの保護
• 楽天主義
• 合意
• 計測法の使用(Use of instrumentation, 問題解決におけるモニタリング、デバッグツール。
• 上記のテーマに沿った実質的なプログラミングプロジェクトの設計、実装、デバッグ

成績評価

すべてのコースワークは個人で行われます。 チームやプロジェクトパートナーは存在しません。 このコースの対面式提供（COVID前と、できればCOVID後）の場合、評価はプロジェクト（45％）、問題集（20％）、中間試験（15％）、期末試験（20％）に基づいて行われました。 2021年春に提供されるコースでは、COVIDの制約により、試験は累積問題集に置き換わります。 これは公開試験のようなものですが、時間的なプレッシャーはありません。 その名の通り、その時点までに授業で扱ったすべての内容が含まれます。 その他の問題集は、トピックに焦点を当てた問題集なので、トピック問題集と呼んでいます。 つまり、2021年春の評価は以下のようになります（重みはすべて概算、5％の範囲内）：

• 4つのプロジェクトで45％、
• 4つのトピカル問題集で20％、
• 15％の学期中累積問題集
• 20％の最終累積問題集で均等に重み付けされます。

学習成果

学生が、分散システムにおける以下のコアシステム概念について、深い理解、流暢な推論、および実践的な実装スキルを獲得することを期待しています。

1. • 通信とリモートプロシージャコール
   • 制御セマンティクスと言語制限
   • Exactly-once, At-Most-Oce, 1161>
   • シリアライズとデシリアライズ
   • End-to-end argument and its application to real systems
   • Integration with threading
   • Concurrency of operations
2. • Data Caching and one->
   • Dental Caching and One->
   • Data Caching and one->

   Data Caching and One->

Data Caching and One->

3. Dental Caching and One->

Data Caching and One->

4. Cache consistency protocol and implementation tradeoffs
5. Origin of temporal and spatial locality
6. Cache quality metrics
7. Application-specific consistency protocols
8. Prefetching.Cache Quality指標
9. Application-specific consistency protocols
10. Prefetch: 1161>
11. Extraction of hints
12. Buffer bloat
13. • Failures in distributed systems: origins and empirical studies
    • Fail fast and Byzantine failures
    • Fail resilienceの基本的限界
14. • 障害耐性.Fault Tolerances: atomic transactions; ACID property
    • Implementation challenges
    • Shadowing, intentions lists and write-ahead logging
    • Tradeoffs in physical logging and operation logging
    • Nested transactions
    • Distributed transactions
15. • Consensus and blockchain.The Factor of Fault tolerance: Factor tolerance: Factor toleranceの基本的限界。 unanimity (two-phase commit)
    • Majority (leader election, Paxos)
    • Byzantine (single-shot and Dolev-Strong)
    • State machine replication and Streamlet
    • Bitcoin

16. Map-Reduce, MPI and GraphLab

17. など一般的なプログラミングパラダイム（時間が許す場合のみ）。
    • Achieving high availability: Voting-based preservation of one-copy semantics
    • Taxonomy of replication strategies.高可用性を実現するためのレプリケーション戦略
    • Taxonomy of replication strategies: 悲観的アプローチと楽観的アプローチ
    • 読み書き競合
    • サーバー・クライアントとピアツーピア戦略
    • キャッシュと切断操作。 競合の解決
    • 可用性を高めるための低帯域幅の利用

Course Logistics

Professors

ティーチングアシスタント

Yiwen Song (Victor)00 pm

講義

• 火・木 10:40 am – 12:00 noon
• ズームリンクとビデオ録画です。 キャンバスのこのコースのページで
• 授業はありません。 2月23日（火）、4月15日（木）（スプリング・カーニバル）
• 最終授業。 5月6日（木）

Recitations

• 時間：水曜日 19:00～19:50 (Section A), 20:00～20:50 (Section B)
• ズームリンクとビデオ録画があります。 このコースのキャンバスページ

Course Notes

でコースのAFSエリアに配置されます。

教科書とオプションの読書

必須の教科書はありません。

• “Distributed Systems: Principles and Paradigms” by Andrew S. Tanenbaum and Maarten Van Steen, Third (2017) Edition, Prentice Hall
• “Guide to Reliable Distributed Systems” by Kenneth P. Birman, Springer
• Foundations of Distributed Consensus and Blockchains by Elaine Shi (2020, Book manuscript)

また、このWebページの上部にある「Readings」リンクには、講義の各所で言及する特定のオプションリーダがいくつか用意されています。

Course Policies

Prerequisites

このコースは大きなプロジェクト要素があるため、UNIXシステム上でのCとJavaプログラミングに熟練している必要があります。 このコースで必要となるプログラミングスキルの多くは、15-213を受講し、「C」以上の評価を得ていることが必要です。 15-213でCを取得した場合、15-440を受講する前にアカデミックアドバイザーと面談し、自分のバックグラウンドについて話し合う必要があります。

Policy on Academic Integrity

The Carnegie Mellon University Policy on Academic Integrityがこのコースに適用されます。

Guidance on Collaboration:

• Student are encouraged to talk to each other, to the TA, to the instructors, or anyone to any other about of the assignments. しかし、どのような援助も、問題の議論と解決への一般的なアプローチのスケッチに限定されなければなりません。
• 各学生は問題セットに対して自分自身の解決策を書き出さなければなりません。 すべてのプロジェクトは個人で行わなければならない。
• 他の学生の解決策を参照することは禁止されており、提出された解決策はいかなるソースからもコピーしてはならない。 これらの行為は不正行為となります。
• ある行為が不正行為にあたるかどうか疑問がある場合は、遠慮なく講師に質問してください。

共有に関するガイダンス。 15-440で完成させた作品を、今後このコースを受講する他の学生に提供したり、今後このコースで使用することはできません（以前このコースを受講した学生が完成させた作品を使用してはいけないのと同様）。

録画

2021年春は、CMU Computing Servicesによって各講義と暗唱のZoomセッションを録画し、このコース用のキャンバスページに掲載します。

TA利用時間の制限

特にTAの注意を待つ学生の長い列がある場合、全員に公平になるように、すべての相談に10分という制限を設ける予定です。 10分を過ぎても終わらない学生は、TAとの時間を増やす前に列の最後尾に戻ります。 TAと会う前に準備をしておくこと。

Piazza Policy

このコースではピアッツァのウェブサイトを使って質問に答えています: このコースのピアッツァページはこちらです。

ピアッツァは授業中に手を上げて質問することだと思ってください。 どんな質問もバカバカしいものではありませんから、怖がらないでください。 質問をする人ひとりに対して、同じ質問がすでに出ている人、あるいはもうすぐ出てくる人がたくさんいるはずです。 あなたの質問に対する答えは、その人たちのためにもなるかもしれません。 また、あなたの疑問が生じなかった人もいるかもしれません。 質問をすることで、その人たちが今まで見えなかった微妙な部分を見ることができるようになるのです。 講師への直接のメールには回答しません。

常に、ピアッツァへの投稿（質問だけでなく、仲間の質問に対する回答も）には、適切な判断を期待します。 学習プロセスの一部は、自分が理解するための正しい洞察に到達するまで、教材と格闘することです。 支援要請に対してあまりに詳細に投稿すると、学習効果が損なわれることがあります。 逆に、マンネリから抜け出せないときに正しい方向へ導いてくれるのは嬉しいこともあります。 そしてもちろん、課題や利用可能なツールについての誤解は、迅速に解決されるべきです。 ピアッツァのサイトに投稿する際は、直接友人と共同作業をするような感覚で、最善の判断で行ってください。 大まかなガイドライン:

投稿・回答して良い例:

• 課題の誤解
• 要件の明確化
• 課題仕様や参照実装、テストでのバグ
• システムコールや関数などの動作に関する小規模で詳細な質問など。
• 課題の FAQ に入りそうなもの

投稿や回答がまずいもの例。

• 数行以上のコード
• システムがどのように動作するかの深い説明
• システムを高いレベルでアーキテクチャするための最善の方法に関する質問
• 成績に関する質問

ピアッツァ質問を投稿する前に自分自身で考える相応の努力をしていることを期待しております。 これは特にコードのデバッグに関して言えることです。 manページを試しましたか? 関連しそうなリソースをGoogleで検索してみましたか？ 過去の質問とその回答を見てみましたか？ printf を挿入して、あなたのコードで何が起こっているのか理解しようとしましたか。

デバッグツールとして autolab を使用しないでください。 私たちは、あなたが autolab に提出する前に、あなたのコードをデバッグする妥当な努力をしたことを期待しています。 テストケースを作成し、コードをストレステストすることは、プロジェクトがすべてであることの一部です。 そのような努力をしなければ、このコースにおける学習の重要な部分を失うことになります。 オートラボへの提出は、あなたのコードをテストし、デバッグし、あなたの能力の及ぶ限り改善したプロセスの最後のステップであるべきです。 piazzaの投稿でautolabのダンプを送信して「助けてください」と言うのは、piazzaのエチケットに対する重大な違反です。

piazzaのプライベートな投稿はサポートされていません。 これはこのクラスの方針として決定されたものです。 ピアッツァへの投稿は、手を挙げて質問するのと同じだということを忘れないでください。 あなたが質問をし、講師の回答を見ることで、他の受講生も恩恵を受けます。 もしあなたが望むなら、私たちはあなたの投稿を他の学生に匿名で行うことを許可します。 これは、授業中に質問する場合とは異なり、すでにプライバシーが保たれていることになります。 本当に稀なことですが、コースの内容とは関係なくプライベートな要求をする必要がある場合、特別なプライベートメーリングリストが作られます。

本当にプライベートな要求をする場合[email protected]にメールを送ると、講師の誰かが返信をします。 このメーリングリストへのメールには、授業内容に関するもの（例：授業で使用した教材の説明など）は無視されますので、そのような質問はピアッツァに投稿してください。

Policy on Late Submissions

プロジェクトについて:

• 各学生は学期を通して5日間の遅刻をすることができます。 休日、旅行、面接、風邪、その他同様の状況を考慮した上で、これらの遅刻日を設定してください。 どのような理由であれ、講師の許可を得ることなく、自由に使用することができます。 1つの期限に使用できる遅延日は最大2つです（つまり、複数のチェックポイントがあるプロジェクトでは、各チェックポイントで最大2つの遅延日を使用することができます）。

• 遅延日1日 = 期日から (0,24) 時間経過、遅延日2日 = 期日から (24, 48) 時間経過、など

• 遅延日をすべて使った場合、2日間までは1日あたり15%のペナルティで遅延提出が可能です。 言い換えれば、遅延日をすべて使い切っても、次の2日間は提出することができ、それぞれの日（猶予日）に15％のペナルティを受けます。

• 遅延日と猶予日を組み合わせて2日以上遅れて提出することはできません。

問題集についてです。 ペナルティの有無にかかわらず、遅刻の提出は認められません。 必ず期限内に提出してください。

プロジェクトのスタイルガイド

コードの機能性をテストするだけでなく、各プロジェクトのポイントの一部をスタイルと読みやすさに留保します。 最も重要なことは、一貫性のある読みやすいスタイルです。 常識的に考えて、500文字のコード行は避け、変数名をfooとしない（文脈上意味がある場合を除く）、大文字小文字をランダムに混在させないようにしましょう。

私たちは次のことを求めています:

ドキュメント 良いドキュメントは重要です: 将来自分自身のため、コードの他のメンテナのため、そしてこのコンテキストでは、あなたのコードを見る採点者のためです。 すべての行を文書化する必要はありませんが（良いコードはある意味で自己文書化されるべきです）、通常、各関数の一般的な使用法と目的、および大規模または複雑なコードブロックを強調することは良いことです。 また、各ファイルにファイルヘッダを付け、そのファイルがプロジェクト全体の構造の中でどのように位置づけられるかを詳しく説明するのもよい方法です。 ホワイトスペース 一貫してください。 ある場所ではタブ2つ、別の場所ではタブ4つといった使い方はしないでください。 コードが読みやすくなるように、合理的にホワイトスペースを使用してください。 行の長さ 行の長さについては、一貫性があり、行の制限が妥当である限り、妥当とします（500字はNGですが、80字や120字は一般的に使われており、認められています）。 変数名 変数名は、何を表すか、どのような用途に使われるかを明確に示すものでなければなりません。 デッド/テストコード デバッグ用のプリント文やコメント付きの大きなコードの塊が散乱しているようなコードは提出しないようにしてください。 可読性が低下し、本番で実際に動作するコードから遠ざかってしまいます。 設計 コードやプロジェクトが適度にモジュール化されるように設計してください。 5000行の関数は、一般に設計が悪いことの表れで、後で頭痛の種になります。

Google のスタイルガイドが参考になるでしょう。

健康

健康のためのヒントをいくつか挙げておきます。