大きな要求の隣の小さな要求：準備キューと公平性

一言でいうと

準備ができた接続を見つけることと、その接続にCPUをどれだけ与えるかは、別の問題です。有限な作業バジェットと、重複のない準備キューで、小さなリクエストが長いリクエストの後ろで飢えないようにします。

なぜ必要なのか

前では、1回recvして別の接続に戻りました。今回は、データがあるあいだ読み続けるという最適化を想像してみましょう。お客さんAは8KiBの原稿を渡し、お客さんBは1文字だけを渡します。Aを完全に空にしてからBを見ると、総スループットはよく見えても、Bの最初の応答は遅れます。Aが読む速度より速く送り続ければ、ループはBや終了リクエストまで戻ってこられないかもしれません。非ブロッキングは、各呼び出しが待たないという意味であって、呼び出しを無限に繰り返すコードが公平だという意味ではありません。

この問題は、acceptにもあります。新しい接続をEAGAINまで受け取るループは、普段はすぐ終わりますが、接続が入り続ける条件では、既存の接続の仕事を後回しにします。読み取るバイト数、接続の開始数、準備完了の作業の処理数に、それぞれバジェットを置く理由です。バジェットは、接続の総許容量とは違います。今回のターンで1KiBだけ読むことと、リクエストを最大1KiBまでしか受けないことは、別々の契約です。

どう動くのか

epoll(7)は、準備リストとラウンドロビンでスターベーションを避ける設計を説明しています。レベルトリガーは、条件が残っていれば次の待機でも準備完了の状態が見えます。エッジトリガーは、すでに受け取った通知だけを信じて、一部のデータのあとで眠ってしまうと、残りのデータを見逃すことがあります。ETでバジェットを使い切って止まった作業は、アプリケーションが覚えておく必要があります。EAGAINを観察したときはじめて、いまできることを使い切ったと判断します。

今回の比較実験は、Pythonの低水準epollにEPOLLETを直接指定します。後続の接続診断器はDefaultSelectorを使い、ETの読み取りサーバーを実装するものではありません。2つのコードを区別してください。実験は準備完了の状態を忘れるエラーを見せ、診断器は、複数の完了イベントをバジェットの分だけ分けて処理するのに、同じキューの原則を適用します。

python3 /opt/fixtures/reactor/fairness_probe.py

実験は、外部通信なしでsocketpairを2組作り、Aに8192バイト、Bに1バイトを先に入れます。カーネルの返却順序を仮定しないように、プログラムが意図的にAから処理します。各ターンでは、最大1024バイトを読みます。追加の送信やEOFなしで、次の結果を比べます。

戦略	Aでの消費	Bの順番	次のカーネルイベント
各接続を1回だけ処理し、準備完了の事実を捨てます	1024バイト	2番目	0個
やることが残った接続を、キューの後ろに回します	8192バイト	2番目	0個

最初の戦略は、Bに順番を与えましたが、Aの残り7168バイトを残しました。次のイベント0個を、入力0バイトと解釈してはいけません。2つ目は、Bを早く処理しながら、Aの仕事を続けます。これは2つの接続での制御された結果であり、すべてのトラフィックのレイテンシの上限や、性能向上率を証明するものではありません。

キューが新しいメモリリークにならないように

同じ接続がselectのたびに繰り返し現れても、キューには1回だけ入れます。dequeは順序を、setは含まれているかどうかを担当します。取り出すときにsetからも取り除かないと、あとでもう一度入れられません。接続の終了時には、キューからも消す必要があります。ファイル記述子の数字だけをキーに使うと、閉じたFDの数字が新しい接続に再利用されたときに、以前の作業と混同することがあります。ラボは、Dialオブジェクトをキーに使い、概念テストは、同じFDに異なる世代番号を付けて区別します。

小さなバジェットが常によいとは限らない

バジェットを1に減らすと、接続間の切り替えは頻繁になりますが、キュー管理とシステムコールのコストも増えます。逆に、バジェットを大きくすると、1ターンの作業量が大きくなり、制御リクエストが後ろに押しやられることがあります。同じ総バイト数のリクエストだけを回さず、長いリクエストと短いリクエストの比率を変えてみてください。スループット、短いリクエストの待ち、制御リクエストを観察するまでにかかったターン数を、別々に記録すれば、何を得て何を失ったのかを説明できます。今回の実験の「2番目のターン」という値は、この入力の組み合わせの証拠であり、任意のリクエスト数でも2番目になるという保証ではありません。

キューが残っているのに、selectで1秒ずつ眠ると、すでに見つけた仕事を自分で後回しにしてしまいます。次の待機は0にしつつ、今回のターンの処理バジェットは維持します。逆に、キューも新しい作業もないのに、ずっと0で呼び出し続けると、ビジーウェイトになります。待機時間は「常に短く」ではなく、まだできる仕事と、最も近い締め切りから計算します。

現場での姿

ダウンロードサーバーの総転送量だけを見ていると、短い制御リクエストが押しやられる現象が隠れることがあります。長い接続と短い接続を混ぜて、短い接続が何ターン目に処理されるかと、最長の待ちをあわせて観察してください。1つの作業が長く計算する構造なら、I/Oのバジェットだけでは足りません。CPU作業の分離や計算量の制限は、別に設計する必要があります。

次の確認ですること

次のクイズでは、準備キューの反例を先に確認します。そのあとの総合ラボのReadyQueueで、重複排除・FIFO・終了した作業の削除を実装します。接続の開始バジェットと、完了処理のバジェットを、別々に検証します。キューだけを作っておいて、一度にすべてを消費するループを書くと、このモジュールの目的は達成できません。