このエントリーについて
このエントリーを書き始めた経緯は下記にあります。
今回は前回の続きでセクション3からです！前回のエントリーはこちらです。
3. Borgアーキテクチャ(Borg architecture)
Borgセルは、マシンのセット、Borgmasterと呼ばれる論理的に集中化されたコントローラ、およびセル内の各マシン上で実行されるBorgletと呼ばれるエージェントプロセスで構成されます(図1参照)。
BorgのすべてのコンポーネントはC++で書かれています。
3.1 Borgmaster
各セルのBorgmasterは、メインBorgmasterプロセスと個別のスケジューラ（§3.2）の2つのプロセスで構成されています。
メインのBorgmasterプロセスは、ステートを変更（ジョブの作成など）するか、データへの読み取り専用アクセスを提供（ルックアップジョブなど）するクライアントのRPCを処理します。
また、システム内のすべてのオブジェクト（マシン、タスク、アロケートなど）のステートマシンを管理し、Borgletsと通信し、SigmaのバックアップとしてWeb UIを提供します。
Borgmasterは論理的には単一のプロセスですが、実際には5回複製されます。
各レプリカは、セルのほとんどのステートのインメモリコピーを保持し、このステートは、レプリカのローカルディスク上の高可用性の分散Paxosベースのストア[55]にも記録されます。
セルごとに選出された単一のマスターは、Paxosリーダーとステートミューテーターの両方として機能し、ジョブの送信やマシン上のタスクの終了など、セルのステートを変更するすべての操作を処理します。
セルが起動したときや選択されたマスターに障害が発生したときには、マスターが（Paxosを使用して）一つ選出されます。このとき、他のシステムが見つけられるように、Chubby-lockを仕掛けます。
マスターの選出と新しいマスターへのフェイルオーバーには通常約10秒かかりますが、一部のインメモリステートを再構築する必要があるため、大きなセルでは最大1分かかります。
レプリカが停止から復旧すると、最新のステートを持つ他のPaxosレプリカからステートを動的に再同期します。
ある時点におけるBorgmasterのステートはチェックポイントと呼ばれ、定期的なスナップショットとPaxosストアに保持されている変更ログを取ります。
チェックポイントには、Borgmasterのステートを過去の任意のポイントにリストアする（たとえば、Borgでソフトウェアの欠陥を引き起こしてデバッグできるようにするリクエストを受け入れる直前）、極端な状況での手作業による修正、将来のクエリのためのイベントの永続的なログの構築、およびオフラインシミュレーションなど、多くの用途があります。
Fauxmasterと呼ばれる忠実度の高いBorgmasterシミュレーターを使用してチェックポイントファイルを読み取ることができ、これにはBorgletsへのスタブ化が施されたインターフェースを備えた本番Borgmasterコードの完全なコピーが含まれています。 Fauxmasterではステートマシンを変更して「すべての保留中のタスクをスケジュールする」などのような操作を行うRPCを受け付けます。まるで実際のBorgmasterであるかのように、 ユーザーは、過去に実際に発生したシステムステートへの変更をステップスルーして確認できます。 Fauxmasterは、キャパシティプランニング（「このタイプの新しいジョブがいくつあるか」）や、セルの構成を変更する前の健全性チェック（「この変更により重要なジョブが発生するか」など）にも役立ちます。
3.2 スケジューリング(Scheduling)
ジョブが送信されると、BorgmasterはそのジョブをPaxosストアに永続的に記録し、ジョブのタスクを保留キューに追加します。
これはスケジューラによって非同期にスキャンされ、スケジューラは、ジョブの制約を満たす十分な使用可能なリソースがある場合にタスクをマシンに割り当てます（スケジューラは主にタスクに対して動作し、ジョブに対しては動作しません）。
スキャンは優先度の高いものから低いものに向かって進み、優先度内のラウンドロビン方式によって変調され、ユーザー間の公平性を保証し、大規模なジョブの背後でのHoL(Head-of-Line)ブロッキングを回避します。
スケジューリングアルゴリズムには、タスクを実行できるマシンを検出する実行可能性チェックと、実行可能なマシンの1つを選択するスコアリングの2つの部分があります。
実行可能性チェックでは、スケジューラはタスクの制約を満たし、十分な「使用可能」リソースを持つマシンのセットを見つけます。これには、削除可能な優先度の低いタスクに割り当てられたリソースも含まれます。
スコアリングでは、スケジューラは各実行可能なマシンの「良さ」を判断します。
スコアはユーザー指定の設定を考慮しますが、ほとんどの場合、プリエンプトされたタスクの数と優先度の最小化、タスクのパッケージのコピーがすでにあるマシンの選択、電源および障害ドメインへのタスクの分散、優先度の高いタスクと低いタスクを1台のマシンに混在させて負荷の急増時に優先度の高いタスクを拡張できるようにするなどのパッキング品質などの組込み基準によって決定されます。
Borgはもともと、スコアリングにE-PVM [4] の変形版を使用していました。これは、異なる種類のリソース間で単一のコスト値を生成し、タスクを配置する際のコストの変化を最小限に抑えます。
実際には、E-PVMはすべてのマシンに負荷を分散し、負荷の急増に備えて余裕を残しますが、特に単一マシンの大部分を必要とする大規模なタスクの場合は断片化が増加します。これを「worst fit（最悪の適合）」と呼ぶことがあります。
その対極にあるのが「ベストフィット」で、これは可能な限りマシンをいっぱいにしようとします。
これにより、一部のマシンでユーザージョブが空のままになる（依然としてストレージサーバーが実行されます）ため、大きなタスクを配置するのは簡単ですが、密に詰め込むことで、ユーザやBorgがリソース要件を誤って見積もることがなくなります。
これは、負荷が集中するアプリケーションに悪影響を及ぼします。特に、CPUの必要性が低いバッチジョブでは、スケジュールを簡単に設定し、使用されていないリソースで日和見的に実行しようとすることがあります。prodでないタスクの20%は、0.1未満のCPUコアしか要求しないためです。
現在のスコアリング・モデルは、孤立したリソース (マシン上の別のリソースが完全に割り当てられているために使用できないリソース) の量を削減しようとするハイブリッド・モデルです。
これにより、ワークロードに最適な状態よりも、パッケージングの効率（[78]で定義）が約3~5%向上します。
スコアリングフェーズで選択されたマシンに、新しいタスクに適合するだけの十分なリソースがない場合、Borgは優先度の低いタスクから優先度の高いタスクへと優先順位を下げます（kill）。
移行または休止状態にするのではなく、プリエンプトされたタスクをスケジューラの保留キューに追加します。3
タスクのスタートアップレイテンシ（ジョブの送信からタスク実行中に遷移するまでの時間）は、大きな注目を受け続けている分野です。
中央値は通常約25秒で、大きく変動します。
パッケージのインストールには全体の約80%の時間がかかります。既知のボトルネックの1つは、パッケージが書き込まれるローカルディスクの競合です。
タスクの起動時間を短縮するために、スケジューラは、必要なパッケージ（プログラムとデータ）が既にインストールされているマシンにタスクを割り当てようとします。ほとんどのパッケージはイミュータブルであるため、共有およびキャッシュが可能です。（これは、Borgスケジューラーによってサポートされるデータの局所性の唯一の形式です。）
さらに、Borgはtreeおよびtorrentのようなプロトコルを使用して、パッケージをマシンに並行して配布します。
さらに、スケジューラーはいくつかの技術を使用して、何万台ものマシンでセルをスケールアップできるようにしています(§3.4)。
3.3 Borglet
Borgletは、セル内のすべてのマシンに存在するローカルBorgエージェントです。
タスクを開始および停止し、失敗した場合は再起動します。OSカーネル設定を操作してローカルリソースを管理したり、デバッグログをロールオーバーしたりします。また、マシンのステートをBorgmasterおよびその他の監視システムに報告します。
Borgmasterは数秒ごとに各Borgletをポーリングして、マシンの現在のステートを取得し、未処理のリクエストを送信します。
これにより、Borgmasterは通信速度を制御し、明示的なフロー制御メカニズムの必要性を回避し、リカバリストームを防止します[9]。
選出されたマスターは、Borgletに送信するメッセージを準備し、セルのステートをそのレスポンスで更新する責務があります。
パフォーマンスのスケーラビリティのために、各Borgmasterレプリカはステートレスなリンクシャードを実行して、一部のBorgletとの通信を処理します。Borgmasterの選出が行われるたびに、パーティションは再計算されます。
復元性のために、Borgletは常に完全なステートを報告しますが、選択されたマスターでの更新負荷を減らすために、ステートマシンに差分だけを報告することによって、この情報を集約し、圧縮します。
Borgletが複数のポーリングメッセージに応答しない場合、そのマシンはダウンとしてマークされ、実行中のタスクは他のマシンで再スケジュールされます。
通信が回復すると、Borgmasterは、重複を避けるために、スケジュール変更されたタスクを強制終了するようBorgletに指示します。
Borgletは、Borgmasterとの通信が失われた場合でも通常の動作を継続するため、すべてのBorgmasterレプリカが失敗しても、現在実行中のタスクとサービスは稼働し続けます。
3.4 スケーラビリティ(Scalability)
Borgの集中型アーキテクチャのスケーラビリティの限界がどこから来るのかはわかりません。これまでのところ、制限に近づくたびに、それを排除することに成功してきました。
単一のBorgmasterはセル内の何千ものマシンを管理することができ、いくつかのセルは毎分10000タスク以上の到着率を持っています。
ビジー状態のBorgmasterは、10~14個のCPUコアと最大50GBのRAMを使用します。
このスケールを達成するためにいくつかの手法を使用しています。
Borgmasterの初期のバージョンには、リクエストやスケジュールされたタスクを受け付け、Borgletと通信するシンプルな同期ループがありました。
より大きなセルを処理するために、スケジューラを独立したプロセスに分割し、耐障害性のために複製される他のBorgmaster機能と並行して動作できるようにしました。
スケジューラのレプリカは、セルのステートがキャッシュされたコピーで動作します。
選択されたマスター（割り当てられた作業と保留中の作業の両方を含む）からステートの変更を繰り返し取得し、ローカルコピーを更新し、タスクを割り当てるスケジューリングパスを実行し、選出されたマスターにそれらの割り当てを通知します。
マスターは、不適切な場合（たとえば、期限切れの状態に基づいている場合）を除き、これらの割り当てを受け入れて適用します。。不適切な場合は、スケジューラの次のパスで再検討されます。
これは、Omegaで使用される楽観的同時実行制御[69]と本質的にはよく似ていますが、実際、最近、異なるワークロードタイプに対して異なるスケジューラーを使用する機能をBorgに追加しました。
レスポンスタイムを改善するために、Borgletと通信し、読み取り専用のRPCに応答するための個別のスレッドを追加しました。 パフォーマンスを向上させるために、これらの機能を5つのBorgmasterレプリカ§3.3に共有（パーティション化）しました。
これらを合わせると、UIの99パーセンタイルのレスポンスタイムは1秒未満に、Borgletポーリング間隔の95パーセンタイルは10秒未満に保たれます。
Borgスケジューラのスケーラビリティをさらに向上するためのポイントがあります。
スコアのキャッシュ: 実現可能性の評価とマシンのスコアリングにはコストがかかるため、Borgはマシンのプロパティやタスクの変更 （マシン上のタスクが終了する、プロパティやタスクの要件が変更されるなど）が発生するまでスコアをキャッシュします。リソース量の小さな変更を無視すると、キャッシュを無効化する頻度が減ります。
等価クラス: Borgジョブのタスクは、通常、同一の要件と制約を持っているので、すべてのマシン上のすべての保留中のタスクの実行可能性を決定し、すべての実行可能なマシンをスコアリングするのではなく、Borgは、同一の要件を持つタスクのグループである等価クラスごとに1つのタスクの実行可能性とスコアリングのみを行います。
ランダム化の緩和: 大きなセル内のすべてのマシンの実行可能性とスコアを計算するのは無駄です。そのため、スケジューラーは、スコアリングに「十分な」実行可能なマシンが見つかるまでランダムな順序でマシンを検査し、そのセット内で最適なマシンを選択します。これにより、タスクがシステムに出入りするときに必要なスコアリングとキャッシュの無効化の量が削減され、マシンへのタスクの割り当てが高速化されます。ランダム化の緩和は、Sparrowのバッチサンプリング[65]に似ていますが、優先度、プリエンプション、不均一性、およびパッケージインストールのコストも処理します。
私たちの実験（§5）では、セルのワークロード全体をゼロからスケジュールするのに通常数百秒かかりましたが、上記の手法を無効にした場合は3日以上経っても完了しませんでした。 ただし、通常、保留中のキューを介したオンラインスケジューリングパスは0.5秒未満で完了します。
4. 可用性(Availability)
大規模システム[10、11、22]では、障害が発生するのが一般的です。
図3は、15のサンプルセルにおけるタスクの削除原因の内訳を示しています。 Borg上で動作するアプリケーションは、レプリケーションや分散ファイルシステムへの永続的な状態の保存、（必要に応じて）随時チェックポイントを取るといった技術を使って、こうした出来事に対応することが期待されます。 それでもなお、私たちはこうした出来事の影響を緩和しようと努力しています。
例えば、Borgは
- 必要に応じて、削除されたタスクを新しいマシンで自動的に再スケジュールします。
- マシン、ラック、電源などの障害ドメインにジョブのタスクを分散することで、相関障害を減らします。
- 許容されるタスク中断率と、OSやマシンのアップグレードなどのメンテナンス作業中に同時にダウンする可能性のあるジョブのタスク数を制限します。
- 宣言型の望ましい状態の表現と冪等な変更操作を使うので、失敗したクライアントは、忘れられたリクエストを無害に再送信することができます。
- 到達不能になったマシンからタスクの新しい場所を見つける速度を制限します。なぜなら、大規模なマシン障害とネットワークの分割を区別できないからです。
- タスクやマシンのクラッシュを引き起こすタスクとマシンの組み合わせを繰り返すことを回避しています。
- ログ保存タスク(§2.4)を繰り返し再実行することで、ローカルディスクに書き込まれた重要な中間データを回復します。これは、そのタスクが割り当てられていたallocが終了したり、別のマシンに移動された場合でも同様です。ユーザーは、システムが試行を続ける時間を設定できます。通常は数日です。
Borgの主要な機能設計は、BorgmasterまたはタスクのBorgletがダウンしても、すでに実行中のタスクが引き続き実行されることです。
ただし、マスターがダウンしていると、新しいジョブをサブミットしたり、既存のジョブを更新したり、障害が発生したマシンのタスクを再スケジュールしたりできないため、マスターを維持することは依然として重要です。
Borgmasterは、マシン障害時のレプリケーション、過負荷を回避するためのアドミッション制御、外部依存性を最小化するためのシンプルで低レベルなツールを使用したインスタンスのデプロイなど、実際に99.99%の可用性を達成できる技術を組み合わせて使用しています。
各セルは他のセルとは独立しており、相関するオペレーターのエラーと障害の伝播の可能性を最小限に抑えます。
これらの目標は、スケーラビリティの制限ではなく、より大きなセルに対する主要な論拠です。
さて、今回はBorgのコンポーネントであるBorgmaster及びBorgletのアーキテクチャに関するセクションです。
めちゃくちゃ面白いなという感想しか出てこないのですが、さらっと振り返ると、やはりBorgによって生まれた基本的な考えは、Kubernetesに確実に引き継がれているんだろうなというところに帰結しました。
一点知らなかったのは、Borgでは分散システムのための合意形成にPaxosというアルゴリズムを用いているんですね。Kubernetes（というよりはむしろ、Kubernetes上でステートを管理するetcd）ではRaftが用いられており、分散システム初心者の自分はPaxosを知りませんでした。
Paxosは@kumagiさんの資料などにも言及がありますが、2019年において、一般的にはRaftを使うほうが筋がよさそうです。当時は今ほど選択肢がなかったのだと思います。
ここまで来た論文読解もいよいよ本番という感じがしてきました（死亡フラグ）
次はセクション5、Utilizationからです。かなり長いのでこれだけで一本のエントリーになるかもしれません（もしかしたら6のIsolationも巻き込めるかもしれませんが）。
