スケジューリング：神話と現実。 Yandexの経験

ここ数年、私はさまざまなプランナーを構築してきましたが、困難な経験を同僚と共有することになりました。 同僚の2つのカテゴリについて話しています。 最初の人は、21日間でスケジューラを開発する方法を学びたい人です。 2番目のものは、単に動作するために、SMSと登録なしで新しいスケジューラを必要とする人です。 特に、2番目のカテゴリの人々を支援したいと思います。







まず、いつものように、いくつかの一般的な言葉を言う価値があります。 スケジューラーとは何ですか（スケジューラー、または簡単にするために、「スケジューラー」）？ これは、リソースを消費者に分配するシステムのコンポーネントです。 リソース共有は、空間と時間の2つの次元で発生します。 ほとんどの場合、プランナーは2番目の次元に焦点を合わせます。 通常、リソースとは、プロセッサ、ディスク、メモリ、およびネットワークを指します。 しかし、非表示にするのは罪です。仮想のナンセンスを流すことができます。 一般的な言葉の終わり。



「プランナー」という言葉に加えて、他の言葉は多くの場合、多くの公共の関心を呼び起こします。隔離、誠実さ、保証、遅延、期限。 また、いくつかのフレーズがあります：サービスの品質（QoS）、リアルタイム、一時的な保護。 実践が示すように、計画立案者は、シェラーダーの有無にかかわらず、同時に達成できない特性の魔法の組み合わせをしばしば期待します。 目的の特性が達成された場合、通常、プランナーはそれ自体で予測不可能なもののままであり、操作中に質問のリストは増加するだけです。 私は彼らの行動の秘密のベールを開けようとします。 しかし、まず最初に。

神話番号1。 何がそんなに複雑なの？

棚が存在するシステムの動作を説明および予測するために、人々は多くの本を執筆し、1つではなく理論全体を開発しました。 少なくとも、スケジューリング理論（スケジューリング理論）とキューイング理論（予想外に：ロシア語版ではキューイング理論）に言及する価値があります。 そのような理論はすべて非常に複雑であり、率直に言って、単純に無限です。 計画タスクの言葉遣いのうち、特別な分類を持つ動物園全体があります。 問題のほとんどがNP完全またはNPハードであることが知られているという事実によって、ポイントは促進されません。 成功した場合でも、最適な解またはその近似を見つけるための多項式アルゴリズムがある場合、それはしばしば判明します：問題のオンラインバージョン（事前にどのクエリを冗談する必要があるか、または表示されるかが不明な場合）には、最適なアルゴリズムはまったく存在せず、 「必要に応じて」すべてをバックオフします。 しかし、物事は見た目ほど悪くはありません。 人類はすでにシェドラーについて多くのことを知っており、その一部は機能します。

神話番号2。 Shedulersはすべての問題を解決します

シェダラーを備えたシステムの予測不可能な動作の優れた例は、今日のインターネットです。 これは、多くのシェダラーと帯域幅と遅延の保証の絶対的な欠如、分離の欠如、TCPプロトコルの形式の正義の類似性を備えたシステムです。偶然にも、数十年後には現在も研究および改善されており、そのような改善は重要な結果をもたらす可能性があります。







GoogleのTCP BBRを思い出してください。 著者は予想外に、TCP BBRの作成は制御理論の最新の進歩なしでは不可能であると言います。制御理論の基礎は非標準のmax-plus-algebraです。 ここで判明したのは、30年以上かかったことです。



しかし、これはシェダーに関するものではなく、フロー制御に関するものです。 そして、あなたは絶対に正しいでしょう。 事実は、それらが非常に強く結びついているということです。 従来のシステムでは、シェドラーはいくつかのボトルネック、つまり限られたリソースに直面しています。 論理的です。リソースは不足しており、公平に分割する必要があるようです。 このようなリソース（都市道路網）があり、平均移動時間を短縮するために（条件付きで、ガレージの出口で）シェダーを作成するとします。 したがって、平均移動時間は、 リトルの定理を適用することで簡単に計算できることがわかります。これは、システム内の車の数とシステムへの進入速度の比に等しいことです。 配当を減らすと、同じ帯域幅で移動時間が短くなります。 渋滞はなく、道路上の車を少なくすればよいことがわかりました（キャプテン）。 このタスクを実行するShedulerは、フロー制御がない場合は役に立ちません。 インターネットでは、説明されている問題はbufferbloatと呼ばれます 。



「シェダラーエンジニアリング」のルールセットを記述した場合、最初のルールは次のようになります。シェドラーの後に発生するキューを制御します。 キューサイズを制御する最も一般的な方法はMaxInFlightです（その高度なバージョンはMaxInFlightBytesと呼ばれます）。 彼には問題があります。実際、正しい番号を選択することは不可能です。 任意の固定数を選択すると、バンドの不完全な使用（1）、または過度のバッファリング（2）のいずれかが保証され、その結果、平均レイテンシが増加するか、幸運な場合はタイムアウトとバンドの損失が発生します。







適切なフロー制御は、システムをモード（1）と（2）の間のKleinrockポイントに維持し、スループット/レイテンシー比を最大化する必要があります（TCP BBRを参照）。

神話番号3。 分離には正義が必要

フェアプランニングには、ネットワークとプロセッサという2つの古典的な用途があります。 GPSは測位システムではありませんが、無限に小さな部分ですべてのユーザーに同時にサービスを提供する理想的なシェダーです。 このようなシェダーは、最大最小の公平性を提供します。 実際のシェデラー（WFQ、DRR、SFQ、SCFQ、WF2Q）は、有限サイズの部分で消費者にサービスを提供します。ネットワークについてはパケット、プロセッサについては時間単位です。 これらのシェダラーは、動作が可能な限り理想に近く、遅延を最小限に抑えるように設計されています。つまり、異なるユーザーが受け取るサービスの量の違いです。 次に、割り当てられた帯域を管理するために、開発者はユーザーの重みを入力し、帯域幅の少ない分離されたシステムにいると言い始めます。 ここに欺deがあります。 実際、分離はありません。



潜在的に100人のユーザー間で共有したいプロセッサがあるとします。 Vityaが良いユーザーだとしましょう。 彼は10ミリ秒で完了したタスクをサービスに送信し、さらに99人のユーザーがいることを理解しているため、1秒間待機する準備ができています。 ただし、場合によっては最大1秒かかるタスクを送信する人もいます。 プリエンプションが不可能であると想定します。 最悪の場合、Vitaは99秒待たなければなりません。 ビクターは、おそらく、そのようなシステムから脱出したいと思っています。



面白くない、とあなたは言います。 これはどのようなシステムですか？プリエンプションなしですか？ システムは気分を害することができなければならず、幸せになります。 クエリの実行時間が10ミリ秒を超えている場合でも、プリエンプションを有効にし、次の要求に制御を移し、一般に科学的に知られている最高の公平なシェダーを使用します。 ヴィティヤは、まるで彼が孤立しているように、1秒で答えを見るでしょうか？ 10 ms（現在のサービス要求）+ 99 * 10 ms（他のユーザーからの要求）+ 10 ms（Vitin要求）= 1010 ms。 これが最大待機時間です。つまり、このようなシステムの方が優れています。



ビクターは言う-素晴らしいシステム！ -そして、1 msのリクエストを送信します。 そして、再び1秒間実行されます（最悪の場合）。 完全に分離されたシステムでは、このような要求は100ミリ秒で完了しますが、ここでは10倍悪化しています。 それだけでなく、この秒からはどこにも行くことができませんが、実際のシステムでは他の問題も確実に解決します

• 予測不可能な可変ユーザー数-100人ではなく1000人の場合、10秒待つ必要があります。
• コンテキスト切り替えのコストが高い。 たとえば、HDDへのクエリを計画している場合、ユーザーを切り替えると、8ミリ秒のレベルでシーク時間が発生する可能性があり、その結果、最大待機時間が800ミリ秒になり、ディスク帯域幅が減少し、すべてのユーザーのキューが増加します。
• 多くの場合、このようなVitiは複数の要求を行いたいが、大量に送信します。 要求は、スケジューラーの前のキューに蓄積され、お互いを待ちます。
• その他の優先トラフィック。
• 科学で知られている最良のシェダーでは、追加の遅延が発生することはありません（特定の数値と式については、 遅延率サーバーキーワードを探してください）。

神話番号4。 重量に応じてストリップを分割するには正義が必要です

正義は本当の隔離を提供しないが、ストリップをうまく分割することがわかります。 しかし、そこにありました。 このような古典的なシェダーの正義は瞬時に行われます。 これは、あなたの番が到着したときにリクエストを送信しないと、リソースを受け取らず、残りのリソースに分割されることを意味します。 長期間（たとえば24時間）後に、消費者に重みが与えられた割合でリソースがまったく食べられなかったことが判明する場合があります。 最悪の場合、他の消費者がいない場合にのみ、消費者が任意の割合で入ることができます。 その結果、重量と消費されるリソースはまったく関連しない場合があります。 これは冗談です、あなたは言う、決して起こらない。 しかし、各マシンにシェダーを備えた分散システムを用意しましょう。 実際には2つのリソースがあるため、2人のユーザーの要求は2つの異なるマシンに来て、リソースを奪い合うことはありません。



集約されたフローのグラフに直線を表示する場合は、履歴（長期）正義または割り当てを使用する必要があります。 しかし、最初にそれが必要な理由を自問してください。

神話番号5。 優先トラフィックの狭いチャネルを教えてください

ウェイト付きの公正なシェダーを使用しており、一部の公式トラフィックに帯域の0.1％を割り当て、残りに残りの99.9％を割り当てたいとします。 その結果、最大遅延x1000が得られます。 この現象は帯域幅遅延結合と呼ばれます。 これは前の議論の直接的な結果です。 最大遅延時間は、選択した帯域の幅に反比例します。 つまり、優先トラフィックには他のメカニズムが必要です。

神話番号6。 システムをフルにロードし、遅延の測定を開始しました

定理 100％を超える負荷のシステムでは、応答の遅延は上からの任意の数に制限されません。 その証拠は明らかだと思います。 キューは、何かがバーストするまで積み上げられます。 システムの時間的特性（シェダーを含む）を誤って測定および比較する方法は、Gil Tene氏（ 表示または読み取り可能 ）が述べています。 ここにイラストだけを残します。

神話番号7。 リアルタイムスケジューラで期限を保証できます

フェアシェダーが不要になった場合は、リアルタイムシステムで使用されるシェダーが必要になる場合があります。 おそらくすべてが良いと高速です。 とりわけ、リアルタイムシステムの正確さは、タスクが時間通りに完了するかどうかに依存します。 ただし、これはすべてが迅速に行われるという意味ではありません。 たとえば、期限とタスクは「春のレビューの開始前に新しいシェダラーを作成して導入する」ことができます。 さらに、このようなシステムの平均応答時間は最悪の場合に非常に近い場合があります。



RTシステムの特徴的な機能：実行可能性についてスケジュールを事前にチェックします。 ここでの「実現可能性」とは、すべてのタスクの期限に従う能力を意味し、「事前」とは、たとえば、組み立て中、システムの構成時、または新しいタスクの開始時です。 さらに、システム内のすべての期限を遵守する簡単な方法がありますが、それは基本的に可能です。 リアルタイムシェダーについてです。 たとえば、EDF（ Earliest Deadline First ）アルゴリズムが単一のプロセッサに最適であることが証明されています。 最適性とは、特定のタスクセットに対して少なくとも実行可能なスケジュールがある場合、EDFは期限前にタスクを完了することを意味します。



しかし、世界の調和のとれた絵が崩壊し、システムが期限に間に合わなくなる状況があります。

• オーバーラン。 ハードRTシステムでは、最悪の場合にタスクがどれだけ実行されるかを知っていると想定されます。 ただし、理想的でない世界ではそうではなく、タスクの完了に時間がかかる場合があります。 タスクを本来よりも長く実行できるようにすると、他のタスクの実行可能性が危険にさらされます。 EDFの場合、ドミノ効果が発生します。
  
  
  
  

• 過負荷 新しく到着したタスクが希望の時間枠に合わない可能性があります。 それを受け入れると、再びドミノ効果が得られます。 通常、このような場合、システムの過負荷が検出され、それを除去するための対策が取られます。 たとえば、新しいタスクまたは現在のタスクの実行を拒否します。 別のオプションは、保証の改訂と一部のタスクの期限を遅らせるスキームです。

したがって、EDFは、可能であれば期限を実行し、不可能な場合はプロセスに最大の損害を与えます。 別の言い方をすれば、最大遅延を最小限に抑えることで、EDFは可能な限り多くのタスクの期限に間に合わなくなります。 EDFは、過負荷状態で直接適用しないでください-結局のところ、予測および/または防止することがしばしば問題になります。 しかし、戦う方法はまだあります。

神話番号8。 システムは100％を超えてロードできません

RTシステムの負荷係数（負荷係数）を決定するには、次の形式の単純な周期モデルを使用します。 T _i msごとに1回到着し、最悪の場合にはC _i msのリソースの排他的所有権を必要とするタスクがあります。 次に、負荷係数は、リアルタイムの1秒間の要求されたリソース時間、つまりU = C ₁ / T ₁ + ... + C _n / T _nとして定義されます。 このような単純なモデルでは、すべてが明確ですが、期間がなく、現在のタスクとその期限のみがある場合の負荷係数の計算方法は？



次に、負荷係数の定義が異なります。 現在のタスクは期限順にソートされます。 次に、セットMの中で最も短い期限を持つ1つのクエリから始めて、すべてのクエリを調べ、このセットに追加します。 各ステップのMには、特定の時点tまでに完全に完了する必要がある要求が含まれます。 それらの合計残余価値を（突然それらの一部を既に部分的に満たした場合）残りの時間t-今で割る。 取得された値は、セットMの負荷係数Uです。現在の負荷係数を取得するには、受信したすべてのUの最大値を見つける必要があります。検出された値は、ご想像のとおり、時間によって大きく異なり、1を超えることが容易に判明します。負荷係数> 1の場合







期限を守ることが重要な場合は、監視する価値のある指標として、従来の処理（システムがビジー状態であった時間の一部）ではなく、説明した負荷係数を使用する必要があります。

神話番号9。 公正なリアルタイムプランナー

リアルタイムシステムには、一時的な保護という用語があります。 ユーザーの行動が他のユーザーの操作の期限の実現可能性を危険にさらすことができない状況を記述するために使用されます。 実際、これらの単語の背後には単純な事実が隠されています。タスクが予想よりも長くかかった場合、完了を禁止する必要があります。 このアイデアを実装するために、非リアルタイムシェダーによって無視されるすべての松葉杖をバイパスするメカニズムのセットがあります。 その結果、タスクは、1組の数字（Q、P）でストリップを予約することになります。Qは消費者予算（ms）、Pは予算補充期間（ms）です。 簡単な結論：消費者はQ / Pリソースを受け取ります。 さらに、理論は、サイズがQ ms以下のタスクの実行を保証し、過負荷（オーバーサブスクリプション）がなければ、P msの期限内にP msごとに1回だけ到着します。 つまり、Q ₁ / P ₁ + ... + Q _n / P _n <1。優れた理論。 未使用のリソースを分配するためのさまざまな方法があります（再利用）。



しかし、Vityaを止めることはできません。 彼はそのようなシステムにさえ入り、要求に応じて10ミリ秒を取得したいという同じ欲求を持っています。 Vitiに加えて、システムにはさらに99人のユーザーがいます。 したがって、Vitiの帯域の1％、つまりQ / P = 1/100を予約する必要があります。 Q値が少なくとも10ミリ秒であることを要求することにより、リクエストが1つの期間で完了することを保証します。 Q = 10 msと仮定します。 次に、P = Q /（1/100）= 100Q = 1秒。 これは、シェダーの保証です。



もちろん、1010ミリ秒よりも1000ミリ秒の方が良い結果ですが、それほどではありません。 しかし、Vityaが1ミリ秒を取得したいという願望を抱いている場合、100ミリ秒で回答を提供できることが保証されています。 このようなシェダーには最小クォンタムがなく、必要最小限の回数だけコンテキストを切り替えます。これは、ディスクにとって非常に重要です。 誰も非常に短期間回答を必要としない場合、ディスクは自動的に最大のデータの一部を無効にし始め、スループットが増加します。



冗長スキームと通常のフェアシェダースキームには、別の重要な違いがあります。 それは、システムに入ったクエリの実行がいつ終了するかをより正確に予測し、システムの他の部分でこの知識を使用できるという事実にあります。



したがって、通常の公平なスケジューラと比較して、公平なリアルタイムスケジューラにはいくつかの有用な特性（予測可能性、最小限のオーバーヘッド、柔軟性の向上など）がありますが、これには最悪の応答時間の劇的な改善は含まれません。