ジョブキューは見た目よりずっと複雑だ
Job queues are deceptively tricky (typesanitizer.com)
要約
この記事では、一見単純に見えるジョブキューシステムが持つ隠れた複雑性について解説します。特に、リファレンスリポジトリのバックグラウンドパッキングという具体的な問題を通して、スケジューリング間隔、同時実行制限、そしてそれらが予期せぬ挙動を引き起こす可能性を探ります。システム設計における「キューへの警戒」「制限」「フォールトモデル」といった視点が、この複雑性を理解する上で役立つことを示唆しています。
全文翻訳
Job queues are deceptively tricky
プログラマーとして楽しいことの一つは、よく知らないシステムについて深く調べていくと、表面的には単純に見えるシステムが、実際には興味深い複雑さの側面を明らかにすることです。言い換えれば、現実は驚くほど詳細を持っているのです。
この記事では、ここ数日間(そしてこの記事を頭の中で下書きしている間に、以前の職場でそれについてもっと長く考えていたことに気づきましたが、それほど明確ではありませんでした)考えていたジョブキューについて話したいと思います。
「ジョブキュー」とは何を意味するのでしょうか?それは、バッチジョブを投入し、スケジューリングし、実行するという概念を持つシステムを意味します。一般的に、システムはFIFOまたはFIFOライクであることが期待されますが、それは必須ではありません。通常、キューは定期的にジョブをスケジューリングするためのネイティブな方法をバンドルしています。これにより、設定ファイル(例: JSONやYAMLを使用)を使ってサブミッションを指定できます。
ジョブキューは、レイテンシ要件はそれほど高くないがスループット要件が高いあらゆる状況で自然に発生します。継続的インテグレーション(CI)は一般的な例です。別の例は、データ分析目的のサマリーです。
過去1〜2年間で、システム設計について考える際に役立ついくつかのレンズがあります。
-
キューへの警戒: キューは通常、ほぼ満杯かほぼ空になりがちで、適切なサイジングについていくつかの考察が必要です。また、Marc Brookerのブログから、レイテンシに関してキューの直感に反する動作についても多く学びました。私が読んだキューに関するブログ記事では、一般的にレイテンシに焦点が当てられており、スループットには焦点が当てられていません。これが、私が「キュー」と「ジョブキュー」を以前に結びつけなかった理由の一部だと思います。
-
制限: これは、Tiger Styleガイドに基づいています。これはTigerBeetleのチームが書いたもので、様々なものに対する明示的な制限について述べています。一般化すると、これは許容範囲(tolerances)とモジュール化された推論のための予算(budgets)という概念につながります。面白いことに、Appleでのキャリアの初期の頃、特に低レベルコードのために、チームがどれだけのメモリ予算を交渉しなければならないかといった議論に、私は少し困惑していたのを覚えています。私は時間の経過とともにそのアプローチへの尊敬を深めました。
-
フォールトモデル: 大まかに言うと、フォールトモデルは、依存関係におけるエラーと信頼性に関する仮定を記述します。
私は、TigerBeetleのCEOであるJoran Dirk Greefの講演やツイート、そしてAlex Millerの著作から、このトピックについて多くを学びました。
これらのレンズがシステム設計にどのように適用できるかを、この記事の後半で示そうと思います。
問題
私の職場では、「リファレンスリポジトリ」をパッキングするためのバックグラウンドジョブがあります。リファレンスリポジトリとは、アグレッシブにリパックされたgitリポジトリのことです。リパッキングに馴染みがない場合、より「アグレッシブに圧縮された」と考えてください。
これらはオブジェクトストレージに保存され、新しいリポジトリは、リファレンスリポジトリをダウンロードし、デフォルトブランチの先端のデルタ(変更差分)を取得することで、マシン上にセットアップできます。非常に大きなリポジトリの場合、ダウンローダーにとって、このアプローチは、より一般的なgit clone操作を行うよりもレイテンシを削減するのに役立ちます。
gitがアグレッシブなリパッキングをどのように行うかの実際の詳細は、この記事ではあまり重要ではありません。重要なのは、大まかに言って、2つの形式のリパッキングが利用可能であるということです。
- 一括リパッキング(Wholesale repacking): これは、gitがパッキングの実行方法に関するいかなるベースライン情報も無視し、すべてをゼロから再計算します。テスト対象のリポジトリの場合、これは7時間かかります。git操作に数時間かかることに驚いているなら、(1)この問題がないことを嬉しく思い、(2)ここでのサブ操作の一部は、リポジトリのサイズに関係なく、単一スレッドで行われるように見えます。
- インクリメンタルリパッキング(Incremental repacking): これは、gitがリポジトリ内に既に保存されているパッキングに関するベースライン情報を再利用するため、変更されたものだけをリパックします。したがって、
cloneを実行してからfetchを実行した場合、fetchからの新しい変更のみがリパックされ、clone操作から受信した履歴に対していくつかの表層的なチェックが実行されるだけです。これは2時間かかります。
OK。これがセットアップです。
より高コストな、7時間かかる処理を行うオプションがあります。これは、より小さなリファレンスリポジトリを生成し、ダウンロードが速くなり、展開(un-tarring)が速くなり、ディスク使用量が削減されます。サイズ感の目安として、一括リパックされたリポジトリは、インクリメンタルにパックされたリポジトリよりも50〜60%小さくなることがあります。
より低コストな、2時間かかる処理を行うオプションがあります。これは、より最新のリファレンスリポジトリを生成します。つまり、ダウンローダーが最新の変更を取得することをまだ気にかけている場合、次に取得するデルタは小さくなり、より高速になり、サーバーへの負荷が軽減されます。しかし、追加のディスク使用量が数百メガバイトまたはギガバイトになる場合、それは良くありません。
もう一つ注意すべき点は、これがコードリポジトリであるため、下流のコンシューマーは週末よりも平日にずっとアクティブであるということです。
両方の長所を活かす?
上記の二分法を見たときの自然な次のステップは、次のことを提案することです。「なぜ週末に一括リパッキングを行い、平日にインクリメンタルリパッキングを行わないのか?」これは、平日に最新性を確保し(より多くのコンシューマーがアクティブな場所)、週末の一括リパッキングはリファレンスリポジトリのサイズ増加をより遅くすることを保証するように思えます。
簡単にするために、リファレンスリポジトリを<myrepo>-<timestamp>.tarのようなキーでバケットに書き込んでいるとしましょう。
インクリメンタルにパックされたリポジトリのサイズを小さく保つために、次のいずれかを行うことができます。
- 一括リパックされたリポジトリを同じキー形式で書き込み、インクリメンタルリパッキングジョブが
clone操作からではなく、最後に成功したリパック(一括またはインクリメンタル)からブートストラップするようにします。 - 一括リパックされたリポジトリを、
<myrepo>-<timestamp>-packed.tarのような変更されたキー形式で書き込み、インクリメンタルリパックをそのキー場所からブートストラップします。ただし、これは、週末にインクリメンタルリパッキングが実行されていないと仮定した場合、他のコンシューマーが遅れすぎないように更新する必要が生じる可能性があります。
よりシンプルに見えるため、最初の方法を選択するとしましょう。
では、これをどのようにスケジューリングするかという問題になります。
典型的なジョブキューは、正当な理由から、クライアントに提供するスケジューリング制御を限定しています。多数のノブを提供すると、予期しないスケジューリング決定のリスクが増大します。
私が上記の「自然な次のステップ」を書いたとき、私は本質的にコントロールループを書くという観点から考えていました。しかし、ジョブキューを使用している場合、私は(定義上)コントロールループにアクセスできません。誰かがそのループを書いており、動作をカスタマイズするために利用可能な設定ノブを確認する必要があります。
ここでは、キューが2つの設定ノブを提供すると仮定しましょう。
- スケジューリング間隔: ジョブは、この間隔で設定されたタイマーで開始されます。
- 同時実行数制限: 特定の設定に対する実行中のジョブの最大数。
この最適化の旅を始める前に、これらの設定ノブは次のように設定されていたとしましょう。
- スケジューリング間隔: 9時間。ジョブの7時間の実行時間からいくらかの余裕を持たせるため。
- 同時実行数制限: 1。ここでは複数のジョブが同じことをしてもあまり意味がないため。
ここでの自然な次のステップは、「7時間実行されるジョブに対して9時間の間隔は十分でした。平日のインクリメンタルリパックジョブは2時間かかるので、間隔を3時間に設定しましょう。週末に一括リパッキングジョブが実行されている場合、3時間では完了しないため、タイマーが再びトリガーされても、同時実行数制限により他のジョブは実行できなくなり、すべてうまくいくはずです。」と考えることかもしれません。
残念ながら、読者の皆さん、この単純な推論はうまくいきません。
可能なセマンティクスのセット
しばらくの間、ジョブキューをどのように使用するかを考えるのをやめ、ジョブキューを実装することについて考えてみましょう。
あるジョブ J の設定に基づいて実行中のジョブ J1 があるとします。スケジューリング間隔が経過し、新しいジョブ J2 を作成したいが、J1 が完了していない場合。J2 をどうすべきでしょうか?基本的に、4つの選択肢しかありません。
- 並列起動(Parallel Spawn): 同時実行数制限が2より大きい場合、
J2を開始して実行できます。 - 同時実行数制限が1の場合、3つの選択肢があります。
- 新規優先(Prefer New):
J1を停止し、J2を開始します。 - 待機(Wait):
J1が完了するのを待ち、その後J2を開始します。 - 旧優先(Prefer Old):
J2を自動キャンセルし、J1の実行を続行させます。
- 新規優先(Prefer New):
ここで少し立ち止まって、これらの可能なセマンティクスの中で、実装する価値がある、または合理的と呼べるものはどれか、直感的な答えを考えてみてください。
もしあなたが私と似ているなら、おそらく並列起動、新規優先、待機は擁護可能であり、旧優先は奇妙/逆行的だと感じるでしょう。「この状況が発生した場合、ジョブの所有者は古い結果よりも新しい結果を重視する可能性が高いので、新規優先をサポートするのは理にかなっていますが、旧優先をサポートするのは奇妙に思えます。誰がそれを望むでしょうか?」といった理由で正当化するかもしれません。
前述のレンズを思い出してください:キューへの警戒、制限、フォールトモデル。
まず注意すべきは、待機オプションは(論理的な)ジョブごとの設定キューを必要とすることです。キューはおそらく(制限に従って)バウンドされるべきです。OK、では制限はどう決定すべきでしょうか?制限に達した場合どうすべきでしょうか?どの利用率レベルでアラートを開始すべきでしょうか(つまり、キューサイズのソフト制限は何ですか)?キューは厳密にFIFOであるべきですか?これらは良い質問です!万能の答えはありませんが、重要なのは、待機セマンティクスがサポートされている場合、これらの質問をすべきであるということです。
制限について考えると、新規優先セマンティクスは、スケジューリング間隔もハードリミットであることを意味します。概念的には、これらは異なるものです。後者が個別の設定ノブとして提供されていれば、これらを独立に変えることを想像できます。
最後に、これらのセマンティクスが意味をなすフォールトモデルは何でしょうか?
- 新規優先:
J1の実行時間が、非決定的な理由(例: レート制限にヒットした)によりスケジューリング間隔を超過しました。私たちは楽観的なので、J2が同じ問題にヒットしない可能性があります。
言い換えれば、ジョブが遅かれ早かれ成功すると期待しています。
-
待機: 上記と同じです。さらに、ジョブのドロップが望ましくないという非機能要件(または仮定!)があります。
-
旧優先:
J1がハングしていないと仮定すると、おそらく時間を与えれば完了するでしょう。それでも、暴走するリソース使用を防ぐために、スケジューリング間隔とは別にハードリミットを設定したいはずです。私たちは悲観的なので、J2の実行時間もスケジューリング間隔を超過すると仮定します。したがって、J2をキャンセルするのが最も賢明です。そうすれば、少なくともJ1は完了する機会を得られます。
単純なことをしたかっただけなのに
記憶を呼び戻しましょう。私たちがやろうとしていたことは次のとおりです。
- 平日は高速パス(2時間)で、週末は低速パス(7時間)で同じジョブを実行したかった。
- スケジューリング間隔用の設定ノブが1つあった。平日に最新の結果を得るために、それを3時間に設定することを考えていた。
- 同時実行数制限は1で、複数のジョブが同時に実行されるのを避けた。
週末の異なるセマンティクスで、このような設定がどのように機能するか見てみましょう。スケジューリング操作は瞬時であると仮定します。
- 新規優先: 7時間かかるジョブが3時間マークに達すると、キャンセルされます。新しい7時間ジョブがトリガーされ、再び3時間後にキャンセルされます。本質的に、これらのジョブはどれも完了しないため、16個のジョブで48時間のコンピューティングリソースを無駄にすることになります。
- 待機: 週末の48時間で、16個のジョブをトリガーでき、合計コンピューティング需要は16×7 = 112時間になります。キューの制限が(112-48)/7 = 64/7 = 9.15 より大きい場合、週末が終わる頃には約64時間の保留中の作業が残ります。しかし、平日は(24×5×(3-2)/3)= 40時間の余裕しかないため、次の週末が始まる前にキューを drain することはできません。
- 旧優先: 48時間で、約7個の7時間ジョブをほぼ完了でき、約1時間の保留中の作業が残ります。9/16個のジョブがキャンセルされます。月曜日には、週末からの追加作業が1時間しか残っていないため、すぐにスケジュールに戻ることができます。
したがって、旧優先がここに最も適しているようです。はい、それはまだ直感に反するように見えるかもしれませんが、それについては後ほど説明します。
もう一つ面白い点は、待機戦略を使用している場合、実際には助けずに問題をマスクしてしまう可能性があることです。週末にキューが長時間空でないためにページングされたかもしれません。そこで、同時実行数を増やすことにしました。良いキリの良い数字である4を選びました。新しいランナーがジョブを処理し始め、素晴らしい!しかし、これらの高コストなジョブは7時間実行されますが、その結果のほとんどは、週末に3時間しか有用でなく、その後置き換えられてしまいます。😬
旧優先の適切さに戻り、フォールトモデルについて書いたことをもう一度見てみましょう。
- 新規優先: [..] ジョブが遅かれ早かれ成功すると期待しています。
- 待機: 上記と同じです。さらに、ジョブのドロップが望ましくないという非機能要件(または仮定!)があります。
- 旧優先: [..]
J2自体もスケジューリング間隔を超過すると仮定します。[..]
週末に持とうとしていたスケジュール(7時間ジョブ、3時間間隔)では、旧優先の仮定に非常によく合いますが、新規優先と待機の仮定とは直接矛盾します。
さらに、私たちの週末のワークロードは、何かが実行されている場合にジョブをドロップすることに全く問題がありません。しかし、待機セマンティクスは、私たちが気にかけなかったことに対して高い代償を払わせることになり、おそらくそれに対処するためにさらに高価なソリューションが必要になるでしょう。
もし旧優先セマンティクスが提供されていない場合、通常のスケジューリングと同時実行数の制限という2つのプリミティブだけでは、それをエミュレートすることはできません。上記のワークロードの場合、cronライクなスケジューリングのような、よりリッチなプリミティブがあれば、作業を2つの別々のジョブに分割できます。1つは平日にのみ実行され、もう1つは週末にのみ実行されます。
もっと悪くなり得たこと
以前、フォールトモデルについて考えていました。可愛かったですよね?
私たちが話してきたシステムとは別のシステムを想像してみてください。コストを管理するためのグローバルな同時実行数制限があります。バックグラウンドで起動される様々なジョブがたくさん入ってきます。すべてFIFOキューに入ります。誰もグローバルサイズ制限を設定しませんでした。
数ヶ月に一度、顧客がジョブキュー関連の機能を試します。彼らは手動で新しいジョブをいくつか起動し、キューの位置が100K以上(あるいは1M以上)になっているのを見ます。「うーん、この機能は機能していないようです?」と彼らは思います。サポートエンジニアにエスカレートします。それはあなたのカンバンボード上のチケットになります。エンジニアが入ってきて、不満を感じながら手動でDELETEを実行してキューをクリアします。
新しいマネージャーが「この問題を体系的に解決するために何ができるか?」と尋ねます。あなたは数日間かけて問題を分析します。実行時間を見ます。キューの成長チャートを見ます。ああ、これらのジョブがどれくらいの時間がかかるか、あるいはどれくらいの数が来るかを予測するのは難しいです。ジョブの作成を減らすべきでしょうか?データベースの列を見ると、同じ設定から来たジョブを正確にチェックするための十分な情報がないことに気づきます。ジョブ作成の柔軟性により、ジョブの重複排除の概念を後付けするのは非常に難しいようです。
マネージャーが戻ってきて、「80-20ソリューションはありますか?」と言います。あなたは、キューに入れられたジョブのうち、似ているように見える既存のジョブを選び、エンキュー操作時にインプレースで上書きしようとするハックを追加します。キューは、新しいジョブが既存のジョブを上書きするため、サイズがほぼバウンドされるようになりますが、顧客が調整してシステムを均衡から崩すことができる設定ノブがまだいくつかあります。あなたは、それらの設定ノブを調整することは「ユーザーエラー」だと宣言し、次のチケットに進みます。
これを書いている間、apenwarrの持てないログ/イベント処理パイプラインの言葉を思い出しました。
(その段落を読んで、私は突然自分自身に深い同情を感じます。私は今や、人よりも傷跡の方が多いと思います。)
ただランダムに、全く理由もなく。
とにかく
希望(そうでなければ人生はあまりにも憂鬱すぎるので)
キュー、制限、フォールトモデルを明示的に考慮してシステムを設計することは可能であるように思われます。そして、これらを考慮することは、より優雅に劣化し、予期しない状況をより良く処理する設計につながるように思われます。特に、悲観的な仮定の下で設計が行われた場合です。
特に、これらを明示的に書き出すことは、システムデザイナーとして価値があります。なぜなら、潜在的なコンシューマーが、頭の中で様々な状況で何が起こるかを詳細なステップバイステップのシミュレーションを経る前に、自分のワークロードに対してシステムを迅速に評価できるからです。
逆に、以前使用したことのない新しいシステムを使用している場合、ドキュメント化されている(またはコードにアクセスできる)場合は、この情報を見つけることが役立ちます。そうすれば、デザイナーの仮定が、意図したワークロードにどれだけうまく適用されるか(または違反されるか)を確認できます。
特に、設定ファイルが関与する場合、特にデータだけでなく制御フローを調整するものは、対応する制御ループに関わる様々なエラーケースを掘り下げるために少し立ち止まる価値があります。なぜなら、設定ファイルはこれらの情報を隠してしまう傾向があるからです。
単純なモデルに適したシステムの場合、上記のように、シミュレーションを必要とせずに、ペンと紙だけで異なるケースをモデル化できるかもしれません。そうすることで、期待通りに物事が進まない場合に何が起こるかを簡単に無視してしまう、私たち自身の思考のギャップを明らかにすることができます。