Start-time Fair Queueing: 後払い型公平スケジューリング

本記事では、LLM 向けロードバランサーに使えるスケジューリングアルゴリズムとして採用した、Start-time Fair Queueing（SFQ）[1] を紹介します。

各ユーザーは「これまでどれだけ先に通してもらったか」を示すメーター \(S_i\) を持ちます。次はメーターが最小のユーザーから通し、推定コスト \(c(r)\) をその場で加算します。いわば「先に通して、使った分を後から記録する」方式です。

等重みなら、中核は次の 1 行です（重み付きは §4.4）。

\[ \boxed{\;i^{*} = \mathop{\mathrm{arg\,min}}_{i \in A}\, S_i,\qquad v \leftarrow S_{i^{*}},\qquad S_{i^{*}} \leftarrow S_{i^{*}} + c(r_{i^{*}})\;} \]

\(A\) は待機中のユーザーの集合、\(v\) は競争の基準線となる仮想時刻です。参加・復帰時は \(S_i \leftarrow \max(S_i, v)\) とし、アイドル中の優先権の貯金と、出入りによる課金のすり抜けを防ぎます（§2.4）。この方式には DRR の割当量がなく、公平性の粒度は自動的にリクエスト 1 件分になります。ただし、保証されるのは単一スケジューラで課金した推定コストの配分であり、投入後の GPU 時間などの公平性ではありません（§8）。

対象とする問題

複数のユーザー（組織や API キーなど）が GPU サーバー群を共有する状況を考えます。全体 FIFO では大量に送るユーザーがキューを埋め、ラウンドロビンでは件数しか揃わないため、重いリクエストを送るユーザーが処理能力を多く取れます。必要なのは、混雑時には件数ではなく処理コストをおおむね等分し、空いているときには余計な待ちを作らない順序付けです。

これはパケットスケジューリングの fair queueing（フロー = ユーザー、パケット = リクエスト、パケット長 = コスト）と同型ですが、LLM 推論には次の難しさがあります。

不可分・非中断：一度投入したリクエストを分割したり、途中で止めて他を先に進めたりすることはできません。
コストの分散が大きい：短い補完から長大な生成まで数桁の開きがあり、形式上の上限もモデルやワークロードとともに動きます。
ユーザーの出入りが激しい：バッチ処理のように一時的に大量のリクエストをバーストさせた後、長い沈黙に入るユーザーが普通に存在します。

最大パケット長が MTU として固定されたネットワークでは、それに合わせて割当量を配る DRR[2] が使えます。一方、上限が大きく動く LLM 推論には、割当量を持たない SFQ の後払いが適しています。本記事が扱うのは推論エンジン内部ではなく、既存のサーバー群へ投入する順序の層です（§6.2）。

1. 記法と前提

1.1. ユーザーとリクエスト

同じモデルを提供するサーバー群ごとにスケジューラを 1 つ置きます。各ユーザー \(i\) は未処理リクエストを FIFO で持ち、先頭をサーバーへ送り出すことを投入と呼びます。スケジューラは、待機キューが空でないユーザーのうち、次に誰から投入するかだけを決めます。

1.2. コストと逐次モデル

リクエスト \(r\) は、投入時に確定するコスト \(c(r) > 0\) を持ちます。LLM 推論では入力長と推定出力長から見積もり、後から補正しません（§5.1・§7.4）。アルゴリズムは最大値を入力に取りませんが、解析では対象区間に現れた最大コストを \(c_{\max}\) と書きます。

投入できるたびに 1 件を選び直す逐次モデルを用います。実装が複数件をまとめて進めても、1 件ごとに選択すれば解析は変わりません（§7.1）。同値はユーザー ID 順で解決します。

1.3. パケットの言葉との対応

SFQ の原論文はパケット交換網の言葉で書かれています。本記事の言葉との対応は次の通りで、以降は断りなく読み替えます。

原論文の言葉	本記事の言葉	LLM 配信での実体
フロー	ユーザー	組織・API キーなどの公平性の主体
パケット	リクエスト	1 回の推論呼び出し
パケット長 \(l\)	コスト \(c(r)\)	入力長と推定出力長から見積もる処理量（§7.4）
重み \(r_f\)	重み \(w_i\)	契約や優先度（本記事の解析は等重み、§4.4）
リンクでの送信	サーバー群への投入	ロードバランサーがリクエストを送り出すこと
busy period	待機リクエストが存在する期間	混雑のひとまとまり（§2.5）

2. アルゴリズム

2.1. 原論文の定義：タグと仮想時刻

原論文では、フロー \(i\) の \(j\) 番目のパケット \(p_i^j\) に次のタグを付けます（\(A(p)\) は到着時刻、\(l_i^j\) は長さ、\(w_i\) は重みです）。

\[ S(p_i^j) = \max\bigl(v(A(p_i^j)),\ F(p_i^{j-1})\bigr),\qquad F(p_i^j) = S(p_i^j) + \frac{l_i^j}{w_i} \]

start tag \(S\) は仮想的な開始時刻、finish tag \(F\) は終了時刻です。SFQ は \(S\) が最小のパケットを送り、仮想時刻 \(v\) をその \(S\) にします。busy period が終わると、\(v\) を送信済みパケットの \(F\) の最大値へ進めます。\(v\) は理想モデルのシミュレーションではなく、SFQ 自身から得られる観測値です（§6.1）。

2.2. ユーザーごとの 1 変数への畳み込み

ユーザー内は FIFO なので、必要なのは各ユーザーの先頭リクエストの start tag だけです。キューが空でない間は、次の start tag が直前の finish tag に一致するため、ユーザーごとに「次の start tag」\(S_i\) を 1 つ持てば十分です。

SFQ は start tag が最小のリクエストから投入するため、仮想時刻 \(v\)（直近に投入したリクエストの start tag）が、待機中のリクエストの start tag を上回ることはありません。キューが空でないユーザーに新しいリクエストが到着したとき、直前のリクエストの finish tag は「その start tag + コスト」であり、start tag は \(v\) 以上、コストは正なので、finish tag は必ず \(v\) より大きくなります。したがって \(\max(v, F_{\text{直前}}) = F_{\text{直前}}\) となり、到着時のタグ付けに \(v\) が実際に関与するのは、キューが空から非空に戻る瞬間だけです。この瞬間の扱いが合流規則（§2.4）になります。

本記事では \(S_i\) をメーター、投入時に \(c(r)\) だけ進める操作を課金と呼びます。待機中のユーザー間では、\(S_i\) は累積コストを現在の基準線 \(v\) に揃えた値として振る舞います（§3.1）。

2.3. 選択と課金

1 件の投入は以下の手順で行います（等重み。重み付きは §4.4）。

メーターが最小のユーザー \(i^{*} = \mathop{\mathrm{arg\,min}}_{i \in A} S_i\) を選びます（同値はユーザー ID 順）。
仮想時刻を進めます：\(v \leftarrow S_{i^{*}}\)。選ばれたメーターは待機中の最小値なので、これは原論文の「送信中のパケットの start tag」の読み替えです（§5.3）。
\(i^{*}\) の待機キューの先頭リクエスト \(r\) を投入します。
課金します：\(S_{i^{*}} \leftarrow S_{i^{*}} + c(r)\)。課金後の値は、いま投入したリクエストの finish tag、すなわち次のリクエストの start tag です。

課金直前は必ず \(S_{i^{*}} = v\)、直後は \(S_{i^{*}} = v + c(r)\) です。メーターは投入時に 1 回だけ課金し、補正も返金もしません（§5.1）。

2.4. 参加と復帰

ユーザーの待機キューが空になると、そのユーザーは選択の対象から外れますが、メーターの値はそのまま残します。リクエストが到着して待機キューが空から非空に戻るとき、および初めて見るユーザーが参加するとき、メーターを次の式で合流させます。

\[ S_i \leftarrow \max\bigl(S_i,\ v\bigr) \]

新規ユーザーは \(S_i = v\) から始めます。\(v\) 側はアイドル中の優先権の貯金を防ぎ、\(S_i\) 側は出入りを挟んでも直近に取り過ぎた分を残します。

\(\max\) の \(S_i\) 側は、単純な代案である「復帰時は常に \(S_i \leftarrow v\) とするリセット合流」に存在する抜け道を塞ぐための規則です。

リセット合流には抜け道があります。1 件送っては投入されるのを待ち、キューが空になってから次の 1 件を送る、という出し方をするユーザーは、復帰のたびに基準線へ戻るため、累積でどれだけコストを消費していても毎回ほぼ最優先で投入され続けます。混雑中にこの出し方をされると、深いバックログを持つユーザーを差し置いて処理能力を際限なく持っていけてしまいます（§3.3）。DRR では復帰したフローが環状リストの末尾に並び直すため、この種のすり抜けはもともと起きません。

メーターの残り \(S_i-v\) は高々 \(c_{\max}\) で、基準線が追いつけば消えます（§3.1）。記憶するのは直近の高々 1 件分だけです。

2.5. 全体アイドル：競争のリセット

待機中のユーザーが 1 人もいなくなったとき（順序の層の busy period の終わり）、仮想時刻を次の式で進めます。

\[ v \leftarrow \max\Bigl(v,\ \max_i S_i\Bigr) \]

\(\max_i S_i\) は割り当て済み finish tag の最大値です。これで前の競争を閉じ、次の混雑は全員が同じ基準線から始まります。最後に重い 1 件を通したユーザーだけが、無関係な次の混雑まで不利を持ち越すことはありません。

一見すると §2.4 で塞いだはずのリセットを再導入しているようですが、両者は発動条件が決定的に異なります。リセット合流は「他のユーザーが待っている最中に」自分だけが基準線へ戻れてしまうのに対し、全体アイドルのリセットは待機中のユーザーが 1 人も存在しない瞬間、つまり守るべき相手がいない瞬間にしか発動しません。混雑が続いている限り絶対に起きないため、公平性の保証には影響しないのです（§3.4）。

2.6. アルゴリズム全体

リクエストが到着したら、そのユーザーの待機キュー（FIFO）に追加します。待機キューがそれまで空だった場合は、追加する前に \(S_i \leftarrow \max(S_i, v)\) で合流させます（新規ユーザーは \(S_i = v\)）。
処理能力に空きがある間、§2.3 の選択・投入・課金を 1 件ずつ繰り返します。
待機中のユーザーがいなくなったら、\(v \leftarrow \max(v, \max_i S_i)\) で競争をリセットします（§2.5）。
完了・失敗・キャンセルではメーターを変更しません。

2.7. 小さな数値例

ユーザー A のリクエストがすべて \(c = 3\)、ユーザー B のリクエストがすべて \(c = 1\) で、両者とも十分なバックログを持つとします。初期状態は \(S_A = S_B = v = 0\)、同値のときはユーザー ID 順（A が先）です。各行の \(v\) は、その投入の手順 2 で更新された直後の値を示します。

投入	\(v\)	選択	課金	\(S_A\)	\(S_B\)
初期	0	—	—	0	0
1	0	A（同値）	+3	3	0
2	0	B	+1	3	1
3	1	B	+1	3	2
4	2	B	+1	3	3
5	3	A（同値）	+3	6	3
6	3	B	+1	6	4
7	4	B	+1	6	5
8	5	B	+1	6	6

A は 2 件、B は 6 件ですが、コスト合計はともに 6 です。各メーターも常に帯 \([v,v+3]\) に収まり、§3.1 の上界を確認できます。

3. 公平性の性質

3.1. メーターのバンド不変量

逐次モデル（§1.2）のもとで、任意の時点で次の 3 つが成り立ちます。

仮想時刻 \(v\) は単調非減少です。後戻りすることはありません。
すべてのユーザーについて \(S_i \le v + c_{\max}\) です。
待機中のユーザーについて \(S_i \ge v\) です。

特に 2 と 3 から、待機中のユーザーのメーターは常に幅 \(c_{\max}\) の帯 \([v,\ v + c_{\max}]\) に収まり、どのペアのメーター差も \(c_{\max}\) を超えません。証明は、状態が変化するイベントについての帰納法です。

選択と課金：新しい \(v\) は待機中のメーターの最小値なので、性質 3 より元の \(v\) 以上です（性質 1）。選ばれたユーザーの課金直後のメーターは \(v + c(r) \le v + c_{\max}\) です（性質 2）。他の待機中のユーザーのメーターは最小値以上、すなわち新しい \(v\) 以上です（性質 3）。
参加・復帰：合流後のメーターは \(\max(S_i, v)\) で、帰納法の仮定より \(S_i \le v + c_{\max}\) なので合流後も \(v + c_{\max}\) 以下（性質 2）、かつ \(v\) 以上（性質 3）です。
全体アイドル：新しい \(v\) は \(\max(v, \max_i S_i)\) で元の \(v\) 以上（性質 1）、性質 2 より元の \(v + c_{\max}\) 以下です。\(v\) が増える方向なので性質 2 は保たれ、待機中のユーザーがいないため性質 3 は空虚に成り立ちます。
離脱：何も変えません。

ユーザーがいない初期状態では自明に成り立つため、この不変量は常に維持されます。

3.2. 混雑ユーザー間のコスト差

区間 \([t_1,t_2]\) に課金されたコストの合計を \(W_i\) とします。ユーザー \(i,j\) が区間を通して待機中なら合流はなく、\(W_i=S_i(t_2)-S_i(t_1)\) なので、次式が成り立ちます。

\[ W_i - W_j = \bigl(S_i(t_2) - S_j(t_2)\bigr) - \bigl(S_i(t_1) - S_j(t_1)\bigr) \]

右辺の各項は §3.1 のバンド不変量より絶対値が \(c_{\max}\) 以下なので、以下を得ます。

\[ \boxed{\;\bigl|W_i - W_j\bigr| \;\le\; 2\,c_{\max}\;} \]

したがって、混雑がどれだけ続いてもコスト差は最大リクエスト 2 件分を超えません。これは原論文の公平性定理の等重みの場合です。

3.3. 出入りを繰り返しても得はできない

任意のユーザー \(i\) が区間内で何度出入りしても、次が成り立ちます。

\[ W_i \;\le\; v(t_2) - v(t_1) + c_{\max} \]

一方、区間を通して待機中のユーザー \(j\) には、次の下界があります。

前者は次の通りです。メーターを変える操作は課金と合流の 2 つで、どちらもメーターを増やすため、区間内に受け取るコスト \(W_i\) はメーターの増加量を超えません。区間内で最初に選択の対象になった時点のメーターは \(v(t_1)\) 以上（区間開始時に待機中なら性質 3、途中で合流したなら合流先が \(v \ge v(t_1)\)）、区間終了時のメーターは \(v(t_2) + c_{\max}\) 以下（性質 2）です。後者は、\(S_j(t_2) \ge v(t_2)\) と \(S_j(t_1) \le v(t_1) + c_{\max}\) の差を取れば従います。

\[ W_j \;\ge\; v(t_2) - v(t_1) - c_{\max} \]

両式より \(W_i-W_j\le 2c_{\max}\) です。出入りを繰り返しても、混雑し続けるユーザーより 2 件分を超えて多く受け取れません。逆向きには、頼まなかった分まで保証されません。

復帰のたびに \(S_i\leftarrow v\) とリセットすると、この上界は成り立ちません。\(\max(S_i,v)\) が出入りをまたいで課金を保存します。

3.4. 全体アイドルのリセットが安全な理由

§2.5 のリセットは、待機中のユーザーがいないときだけ発動します。区間を通して待機中のユーザーがいるという §3.2・§3.3 の条件下では発動しないため、保証は影響を受けません。

逆に、全員の待機キューが空になったなら、その瞬間に処理能力を取り合っている相手はいません。前の混雑で誰がどれだけ取ったかを次の混雑まで持ち越しても、それによって守られるユーザーはおらず、たまたま直前に重い 1 件を通したユーザーが次の混雑の先頭で待たされるという不自然さだけが残ります。busy period ごとに競争を閉じるという原論文の設計は、後払い方式の「直近に取り過ぎた分だけ覚える」という減衰（§2.4）を、混雑の切れ目で完結させたものと読めます。また、このリセットを意図的に起こすことはできません。自分のキューを空にしても、他に待機中のユーザーが 1 人でもいればリセットは起きないからです。

3.5. 粒度の下限

不可分・非中断のリクエストでは、コスト \(c_{\max}\) の 1 件を投入した直後に、そのユーザーが同じ量だけ先行します。したがって瞬時のずれを \(c_{\max}\) 未満にはできず、SFQ の粒度は原理的な下限と同じオーダーです。DRR の粒度には割当量 \(Q\) も加わります（§4.2）。

4. DRR との比較

4.1. DRR の仕組みと SFQ の後払い

DRR[2] は、各フローのデフィシットカウンタ \(DC_i\) に、訪問ごとに割当量 \(Q_i\) を加えます。先頭パケットが残高に収まる間は送信して長さを差し引き、キューが空ならカウンタを 0 に戻します。\(Q_i \ge L_{\max}\) なら毎回 1 パケット以上送れるため、処理は償却 \(O(1)\) です。

DRR は割当量を与信として先に配り、残高に収まるリクエストだけを通します。SFQ は先に通して全額をメーターへ課金し、他のユーザーが追いつくまで休ませます。大きなリクエストもクレジットの貯まり待ちをせず、割当量も不要です。

1 本のリンクでは重い仕事を先に流すことが他フローの遅延へ直結します。一方、LLM 配信では複数サーバーが並列に実行し、投入量は別の層で制御できるため、後払いを採りやすくなります（§5.2）。

4.2. 割当量というパラメータがない

DRR の割当量 \(Q\) は、公平性の粒度・巡回の計算量・復帰時の待ちを同時に決めます。固定 MTU があれば \(Q=L_{\max}\) 程度にできますが、LLM の最大コストはモデルやワークロードとともに動きます。大きく取れば粒度と待ちが粗く、小さく取れば重いリクエストに複数巡回が必要です。

SFQ の粒度は自動的に \(c_{\max}\) になります。代わりに選択には \(O(T)\) の走査か \(O(\log T)\) の順序付き構造が必要です。DRR の償却 \(O(1)\) は数万フローを扱うルータで重要ですが、数百ユーザー程度のロードバランサーでは SFQ の計算量も問題になりにくいです（§7.1）。

4.3. アイドルからの復帰

どちらもアイドル中の権利を貯金できません。DRR はキューが空になるとカウンタを 0 に戻し、復帰時は環状リストの末尾から最悪 1 巡回待ちます。SFQ は \(\max(S_i,v)\) で合流し、メーターの残りがなければ次の投入から候補になります。残りがあっても高々 1 件分で、全体アイドルでは消えます（§2.5・§3.1）。

4.4. 重み付け

重み \(w_i\) を使う場合、DRR は \(Q_i\propto w_i\)、SFQ は課金を \(c/w_i\) とします。後者は §2.1 の定義そのものです。本記事の解析と例は等重みです。

4.5. 比較のまとめ

観点	DRR	SFQ
ユーザーごとの状態	デフィシットカウンタ（与信残高）	メーター \(S_i\)（次のリクエストの start tag）
全体の状態	環状リストの現在位置	仮想時刻 \(v\)
選択	環状リストを巡回	待機中のユーザーの argmin
コストの扱い	割当量を先に配布し、送信で消費（先払い）	投入時に課金（後払い）
必要なコスト情報	正確なコスト（原論文ではパケット長）	投入時に定まる値（見積もりで可）
パラメータ	割当量 \(Q_i\)	なし
公平性の粒度	\(Q + L_{\max}\) のオーダー	\(c_{\max}\)（区間のコスト差 \(\le 2c_{\max}\)）
1 決定の計算量	償却 \(O(1)\)（\(Q \ge L_{\max}\) のとき）	\(O(T)\) 走査（順序付き構造で \(O(\log T)\)）
想定規模	ルータの数千〜数万フロー	1 スケジューラあたり数十〜数百ユーザー
アイドル復帰	カウンタを 0 に戻しリスト末尾へ（最悪 1 巡回待ち）	\(\max(S_i, v)\) で合流（残りがなければ即候補）
全体アイドル	状態なし（各フローは離脱時にリセット済み）	\(v\) を finish tag の最大値へ進めて競争をリセット
重み付け	\(Q_i \propto w_i\)	\(c / w_i\) を課金

5. LLM 配信に合わせた設計判断

5.1. コストは見積もりで確定させ、後から動かさない

パケットの世界では長さは送信前に正確に分かりますが、LLM 推論では処理量を支配する出力長が完了まで分かりません。幸い、SFQ の規則がコストに要求するのは「投入時に定まっている正の値であること」だけで、§3 の性質はその値が実測とずれていても（課金した値の上での公平性として）成り立ちます。そこで本記事の使い方では、投入時の見積もりをそのまま課金して確定させます。処理が完了して実際の出力長が分かった後で、課金済みのメーターを差分補正する（追徴・還付する）案も自然に思えますが、採用しません。

不変量の単純さ：「メーターは投入でちょうど 1 回課金される」という 1 行が、補正を認めた途端、二重補正の防止や途中失敗時の扱いなど、状態に依存する分岐の集合に化けてしまいます。
順序の安定性：出力長の分散は大きく、事後補正は選択順序を過去の観測ノイズで揺らします。順序の決定に使う量を投入時点で確定する値に限ることで、シミュレーションでの再現とデバッグが素直になります。
調整の置き場所：実測との系統的なずれは、個々のリクエストにさかのぼって精算しなくても、見積もり式そのものを長期の実測で校正すれば吸収できます（§7.4）。校正と公平性の機構は独立に進められます。

同じ理由で、失敗やキャンセルでも返金しません。課金済みのリクエストが失敗した場合、そのユーザーは「使っていない分」を一時的に背負いますが、その量は高々数件分で、基準線の前進とともに自然に消えます（§2.4）。過負荷時にリクエストを間引く場合も、間引く対象を課金前の待機段階から選ぶ設計にすれば、「課金済みを取り消して返金する」という状況自体が生まれません。

なお、見積もりコストとの相性という点で、SFQ が start tag 側を基準にしていることには実利があります。選択は「過去に課金した累積」であるメーターだけで決まり、いま選ぼうとしているリクエスト自身のコストは選択に影響しません。コストが効くのは課金の瞬間、つまり次回以降の順位だけです。見積もりが多少ずれても「次にどのユーザーを通すか」の判断は歪まず、ずれの影響は事後の休み時間の長さに限定されます。finish tag を基準にする WFQ では、選択の時点でそのパケットの長さが必要になるため、この分離は成り立ちません（§6.1）。

5.2. 決めるのは順序だけ

本記事の使い方で SFQ が決めるのは「次にどのユーザーのリクエストを進めるか」という順序だけです。どのサーバーに置くか（配置）、そもそも受けるか捨てるか（受付制御）は別の層が受け持ちます。原論文の SFQ が 1 本の出力リンクの帯域を分けるのに対し、ここでは「サーバー群への投入順序」を分けており、サーバーが複数あることは公平性の層からは見えません。公平性・配置・流量制御を直交させておくことで、それぞれの層を独立に検証できます。

順序の層だけを見れば、この構成は work-conserving です。クレジットが貯まるまで処理を保留する仕組みがないため、投入できるリクエストがあるのに公平性の都合で寝かせることはありません。なお、選ばれた先頭リクエストがどのサーバーにも置けないときに、メーターのより大きいユーザーを先に通すか（追い越し）、その場で止まるかは配置との接続部の設計に依存します。追い越しは稼働率を上げますが、「なぜこのユーザーが先に通ったのか」をメーターだけで説明できなくなるため、公平性の説明可能性を優先するなら止まる方が単純です。

5.3. 単一リンクからサーバー群への読み替え

原論文は「1 本のリンクで 1 パケットずつ送信する」前提で書かれており、仮想時刻も「送信中のパケットの start tag」で定義されます。ロードバランサーでは投入は一瞬で完了し、投入済みのリクエストは複数のサーバーで並行に実行されるため、「送信中の 1 件」に当たるものがありません。本記事の読み替えは次の 2 つです。\(v\) は「最後に投入したリクエストの start tag」とし（§2.3 の手順 2）、busy period は「待機リクエストが存在する期間」とします（§2.5）。どちらも、原論文の定義を投入という離散イベントの列の上で読み直しただけのものです。

この読み替えで運ばれるのは、順序の公平性、すなわち課金したコストの配分に関する §3 の性質だけです。原論文はこのほかに、リンク容量を前提としたスループット・遅延の保証や、サーバーの処理速度が変動しても公平性が保たれるという頑健性も示していますが、これらは単一リンク・正確なパケット長という前提に依存するため、そのままは持ち込めません（§8）。もっとも、投入後の実行を複数のサーバーが並列に担い、サーバーごとの流量は別の層が制御する構成（§5.2）で順序の層に求めたいのは、まさに持ち込める側の性質だけです。処理速度を参照せずに公平性が定義されているからこそ、実行時間が出力長や負荷で大きく揺れる LLM 配信にも記号の読み替えだけで適用できる、とも言えます。

6. 関連手法の中での位置づけ

6.1. fair queueing・stride scheduling の系譜

「累積量が最小の主体を選ぶ」という骨格は、fair queueing の古典に繰り返し現れます。出発点は、仕事を無限に分割できると仮定した理想的な流体モデルである GPS[4] です。これを不可分なパケットの世界で近似する系譜として、WFQ[3] は GPS をシミュレートした仮想時刻の上で finish tag が最小のパケットを選びます。SFQ[1] はこの系譜の中で、2 つの単純化を同時に行った方式と位置づけられます。第一に、基準を finish tag から start tag へ移したことです。これにより、選択の時点でパケット長（コスト）を参照する必要がなくなります（§5.1）。第二に、仮想時刻を GPS のシミュレーションではなく「いま送信しているパケットの start tag」という観測値で定義したことです。これにより、タグの計算が算術 1 回で済みます。本記事が LLM 配信に採用したのは、まさにこの 2 つの単純化がそのまま効くためです。

CPU スケジューリングにも同じ骨格があります。stride scheduling[5] は、チケット数に反比例した固定の stride を pass 値へ積み増しながら pass 最小のクライアントを選ぶ方式で、SFQ のユーザーごとの 1 変数（§2.2）は「stride を毎回のリクエストのコストにした stride scheduling」と見ることもできます。Linux の CFS[6] では、実行した CPU 時間を重みで正規化して積む vruntime が最小のタスクが選ばれ、min_vruntime が新しく実行可能になったタスクを過去にさかのぼって有利にしすぎないための基準点として、SFQ の仮想時刻と似た役割を持ちます（スリープから復帰したタスクの扱いには実装上の細部があるため、ここでは役割の類似に留めます）。系譜の中で見ると、DRR はタグ計算すら避けて償却 \(O(1)\) に振り切った枝であり、SFQ は対象規模が小さければタグ系の最も素朴な形で十分であることを示した枝です。

6.2. LLM サービングの公平化研究との関係

LLM に固有の公平スケジューリングとしては、VTC（Virtual Token Counter）[7] が代表的です。VTC は continuous batching を行う推論エンジンの内部に組み込まれ、クライアントごとに処理した入力・出力トークン数の重み付き累積カウンタを持ち、バックログのあるクライアントのうちカウンタ最小のものを優先します。アイドル明けのクライアントのカウンタを持ち上げて貯金を防ぐ点まで含めて、「累積量最小を選ぶ」という骨格は SFQ と共通です。

異なるのは挿入位置と責務です。VTC がエンジンのスケジューラを置き換えて「実際に処理されたトークン量」の公平を作るのに対し、前段の SFQ は無改造のサーバー群の手前に立ち、「リクエストをどの順で投入するか」だけを公平化します。個々のサーバーのエンジンには自分に届いたリクエストしか見えないため、サーバー群を束ねるロードバランサーには、エンジン内部の公平化とは別に、ユーザー横断の投入順序を公平にする層が必要になります。逆に、責務を投入順序に絞っているおかげで、エンジンに手を入れられない環境でもそのまま使え、配置・受付制御・エンジン内部のスケジューリングとも衝突しません（§5.2）。両者は競合ではなく、分業の中の別の層を受け持つ補完関係にあります。投入後の実行の公平性を扱わないという限界（§8）は、この分業の裏返しです。

なお、VTC 以降の研究では、トークン単位の公平性に加えてプレフィックスキャッシュの局所性を同時に扱うもの[8]や、利用者間の公平性と運用者側の効率まで含めて総合的に扱うもの[9]も現れています。本記事の対象は、それらより前段の投入順序に限定されます。

6.3. 比較のまとめ

本章で挙げた手法は、いずれも「累積量が最小の主体を選ぶ」という骨格を共有しており、違いは「重い 1 件が来たときにどう扱うか」と「アイドルから復帰したときにどう扱うか」の2 つの観点に現れます。

SFQ（本記事で紹介した手法）[1]
- 重いリクエストの挙動：メーターが最小でありさえすれば \(c_{\max}\) 級の 1 件も直ちに投入し、その瞬間にコストの全額を 1 回だけ課金します。以後そのユーザーは、他のユーザーのメーターが追いつくまで選ばれません。「先に通して、後からそのユーザーを休ませる」後払いであり、混雑ユーザー間のコスト差はどの区間で測っても \(2c_{\max}\) 以下に収まります（§3.2）。
- 復帰時の挙動：合流規則 \(\max(S_i, v)\) により、アイドル中の貯金はできず、基準線より上に残ったメーターは引き継ぎます。残りがなければ合流した瞬間からメーターが最小のグループの一員となり、次の投入から直ちに候補になります（§2.4）。待機中のユーザーが全員いなくなった時点でだけ、競争がリセットされます（§2.5）。
Deficit Round Robin[2]
- 重いリクエストの挙動：訪問のたびに割当量 \(Q_i\) が与信残高として貯まり、重い 1 件は残高が長さに達するまで送信されません。「大きい仕事を送る前に待たせる」先払いで、支払いは送信時の残高消費として完結し、送った後のペナルティはありません。
- 復帰時の挙動：キューが空になるとデフィシットカウンタを 0 に戻し、復帰時は環状リストの末尾に並び直します。使い残しの与信は没収され、自分の番まで最悪 1 巡回分を待ちます。
- SFQ との違い：支払いの向きが逆です。DRR は「送る前に貯めて待つ」、SFQ は「先に送って後で休む」形を取ります。これに伴い、割当量というパラメータの有無、償却 \(O(1)\) の巡回か argmin かという計算の形、重い 1 件の待たされ方が変わります（§4）。
GPS[4]
- 重いリクエストの挙動：仕事を無限に分割できると仮定した流体モデルで、重い 1 件もバックログのある全フローと同時に、重み比例のレートで少しずつ処理されます。1 件を丸ごといつ通すかという「順序」の概念自体がありません。
- 復帰時の挙動：復帰した瞬間から容量の重み比例シェアを受け取ります。アイドル中のシェアはその場で消えるため、貯金は原理的に生じません。
- SFQ との違い：分割可能という前提が、不可分・非中断のリクエストを丸ごと投入する SFQ と正反対です。GPS は実装対象ではなく、WFQ や SFQ などの離散方式が近似の目標とする理想的な基準として機能します。
WFQ[3]
- 重いリクエストの挙動：GPS 上での仮想完了時刻（finish tag）が最小のリクエストを通します。重いリクエストは finish tag が遠くなるため、通る前に軽いリクエストへ順番を譲り、選ばれた時点で丸ごと通されます。支払いは「完了が遅いはずのものを後回しにする」という順序付けの側に織り込まれています。
- 復帰時の挙動：到着したリクエストのタグは、そのユーザーの前回の finish tag と現在の仮想時刻の大きい方を起点に計算されるため、アイドル中の貯金は生じません。
- SFQ との違い：完了時点（finish 側）を基準に並べるか、開始時点（start 側）を基準に並べるかが異なります。WFQ は選択の時点でリクエストのコスト（原論文ではパケット長）が必要で、仮想時刻の計算に GPS のシミュレーションも必要です。SFQ はどちらも不要で、この 2 つの単純化がコストが見積もりでしかない LLM 配信への適用を可能にしています（§5.1・§6.1）。
Stride scheduling[5]
- 重いリクエストの挙動：pass 値が最小のクライアントを選び、選ぶたびにチケット数に反比例した固定の stride を積み増します。1 回の割り当ては固定のクォンタムで、「重い仕事」はプリエンプション可能な CPU 時間として細切れに刻まれるため、1 回の支払いが大きく跳ねることはありません。
- 復帰時の挙動：参加・復帰するクライアントの pass を全体の基準値に揃えて開始し、休止中の貯金を防ぎます。
- SFQ との違い：1 回に積む量が固定（チケット由来）か、毎回の仕事のコストかが違いです。SFQ のユーザーごとの 1 変数は「stride を毎回のリクエストのコストにした stride scheduling」と見なせます（§6.1）。可分な CPU 時間と不可分なリクエストという対象の違いが、そのまま stride の可変化に対応しています。
Linux CFS[6]
- 重いリクエストの挙動：vruntime が最小のタスクを実行します。実行は中断可能で、実際に使った CPU 時間（重みで正規化）が連続的に vruntime へ課金される、実測ベースの後払いです。重い仕事はタイマーで刻まれ、実行と課金を少しずつ繰り返しながら他のタスクと交互に進みます。
- 復帰時の挙動：min_vruntime を基準点として、起床したタスクが過去にさかのぼって有利になりすぎないよう vruntime を調整します（スリープ復帰の扱いには実装上の細部があります）。
- SFQ との違い：課金が実測かつ連続なのに対し、本記事の使い方の SFQ は投入時の推定コストを一括で課金し、以後いっさい補正しません（§5.1）。プリエンプションできる CPU と、投入したら止められないリクエストという対象の違いが、課金のタイミングの違いにそのまま現れています。
VTC（Virtual Token Counter）[7]
- 重いリクエストの挙動：推論エンジン内部で、クライアントごとの処理済み入力・出力トークン数の重み付き累積カウンタが最小のものを、continuous batching の各ステップで優先します。重いリクエストは処理が進むにつれてカウンタが増え、トークン粒度で徐々に他のクライアントへ譲っていく形になります。
- 復帰時の挙動：アイドル明けのクライアントのカウンタを現在の水準まで持ち上げ、休止中の貯金を防ぎます。SFQ の合流規則と同じ役割です。
- SFQ との違い：挿入位置と責務が異なります。VTC はエンジンのスケジューラを置き換えて「実際に処理されたトークン量」を公平化するのに対し、前段の SFQ は無改造のサーバー群の手前で「投入順序」だけを公平化します（§6.2）。課金も、実測トークンの逐次加算に対して、投入時の推定コストの一括課金という違いがあります。

7. 実装メモ

7.1. データ構造と計算量

選択は「待機中のユーザーの中でメーター最小のものを探す」作業なので、（メーター, ユーザー ID）をキーにした順序付き集合や優先度付きキューを維持すれば、1 決定あたり \(O(\log T)\) で済みます。課金や合流のたびに削除と再挿入が 1 回ずつ入るだけで、更新の形は単純です。ユーザー数が数百程度までなら、構造を持たずに毎回線形走査（\(O(T)\)）しても実用上は十分速く、実装の単純さを優先できます。

スケジューラはイベント駆動で構いません。リクエストの到着と完了を契機に「置ける限り 1 件ずつ投入する」ループを回せば、§1.2 の逐次モデルとそのまま一致します。1 回の契機で処理する件数に上限を設けても、選択を 1 件ごとにやり直している限り、解析は変わりません。

7.2. 数値の維持

メーターと仮想時刻は単調に増え続けますが、アルゴリズム上意味を持つのは差 \(S_i - v\) だけです。値が大きくなってきたら、すべてのユーザーのメーターから \(v\) を引いて \(v = 0\) に戻せば、選択順をいっさい変えずに、値域を帯の幅（高々 \(c_{\max}\)、§3.1）に畳めます。浮動小数点で運用する場合の桁落ち対策としては、これで十分です。長期間投入のないユーザーのメーターは、全体アイドルのリセット（§2.5）以降は \(v\) 以下に揃うため、状態ごと破棄しても挙動は変わりません。

7.3. 決定性

メーターが同値のときはユーザー ID の辞書順で選び、選択の経路に乱数を置かないことで、同じイベント列に対する投入列は完全に再現可能になります。§3 の性質をシミュレーションでテストする際、この決定性が前提になります。浮動小数点の比較には全順序の比較（Rust なら total_cmp）を使うと安全です。

7.4. コストの見積もり

LLM 推論のコストは、投入の時点では確定していません。処理量を支配する出力長が、完了するまで分からないためです。実用上は、入力長と推定出力長にそれぞれ重みを掛けて足すような単純な式で十分です。推定出力長には、リクエストに付く出力最大長（max_tokens など）をそのまま使うのではなく、過去のリクエストにおける「実際の出力長の合計 ÷ 出力最大長の合計」の比を掛けて縮めると、実態に近づきます。この比は長期の集計からゆっくり更新すれば良く、モデルごとやユーザーごとに持つこともできます。

重要なのは、こうした校正がすべてアルゴリズムの外側で行われることです。見積もり式をどれだけ改善しても、個々のリクエストのコストは投入の時点で確定し、以後動きません（§5.1）。§3 の性質はコストがどんな正の値でも成り立つため、見積もりの改善と公平性の機構は独立に進められます。だからこそ本記事では、コストを最初から与えられた値として扱ってきました（§1.2）。

7.5. 検証したい性質

実装時は、次の 5 つの性質を回帰テストとして固定しておくと安心です。(1) 等コストの 2 ユーザー間で投入件数の差が常に 1 以内に収まる（等分配）。(2) コストが 10 倍のリクエストを送るユーザーは、件数がおよそ 10 分の 1 になる（コストの公平）。(3) 長いアイドル明けのユーザーが基準線から再開し、待ち時間分の優先権を持たない（貯金なし）。(4) 1 件ずつ送ってキューを空にし続けるユーザーの取り分が、混雑し続けるユーザーと同水準に収まる（リセット悪用の防止）。(5) 待機中のユーザーが全員いなくなった後の新しい混雑では、全ユーザーが同じ基準線から始まる（全体アイドルのリセット）。

8. 設計上の限界

SFQ をこの形で使うことには、トレードオフや限界もあります。具体的な注意点を明記しておきます。

公平性は課金したコストの上で成立する点：実際の資源消費が課金したコストから系統的にずれるユーザーがいれば、そのずれの分だけ実測ベースの公平性は歪みます。是正は個々の課金の補正ではなく、見積もり式の校正で行う方針です（§5.1・§7.4）。
順序の公平であって実行の公平ではない点：制御しているのは投入の順序だけで、投入後の GPU 時間や KV キャッシュの占有、推論エンジン内部のプリエンプションには関与しません。
原論文の遅延・スループット保証は持ち込めない点：それらの保証は単一リンクと正確なパケット長を前提とするため、本記事の読み替え（§5.3）で運ばれるのはコスト配分の公平性（§3）だけです。個々のリクエストの締切や最大待ち時間は保証しません。
ユーザー内が FIFO 固定である点：ユーザー内部の優先度付けやリクエスト種別ごとの制御は持ちません。
単一スケジューラ前提である点：メーターと仮想時刻は 1 プロセス内の状態であり、ロードバランサーを複数レプリカに分けた場合の、レプリカ横断の公平性はスコープ外です。
選択が \(O(T)\)〜\(O(\log T)\) である点：数万フローを線速で処理する用途には向きません。その規模は DRR 系の \(O(1)\) 設計の土俵です（§4.2）。

9. まとめ

規則は「メーターが最小のユーザーを選び、投入した瞬間にコストを 1 回だけ課金する」「参加・復帰時は \(\max(S_i, v)\) で合流する」「待機中のユーザーが全員いなくなったら仮想時刻を finish tag の最大値へ進める」の 3 つだけです。これは 1996 年の SFQ そのものであり、一度確定した課金は後から補正も返金もしません。
保証は課金した推定コストの上での公平性で、単一スケジューラの投入順序に限定されます。混雑が続くユーザー間の区間のコスト差は常に \(2c_{\max}\) 以下で、リクエストが不可分である以上、この粒度は原理的な下限と同じオーダーです。
DRR との決定的な違いは、送信許可の割当量を先に配るのではなく、先に通してからメーターに記録する後払い方式である点です。これにより、パラメータ調整の不要化、リクエスト 1 件分の粒度、アイドルからの速い復帰が得られます。代償は選択の \(O(T)\)（順序付き構造で \(O(\log T)\)）で、ルータ規模のフロー数を捌く用途は切り捨てています。
選択がメーターだけで決まりリクエスト自身のコストを参照しないこと、仮想時刻が観測値であること、処理速度を参照せずに公平性が定義されていること。この 3 つの性質のおかげで、SFQ はコストが見積もりでしかなく実行が並列な LLM 配信のロードバランサーに、記号の読み替えだけでそのまま使えます。

本記事の範囲は方式の定義と理論的な性質の整理に留まります。実トラフィックでの挙動の検証、見積もり式の校正の精度、重み付き運用の評価は、今後の課題です。

10. 参考文献

本記事の主題および比較と位置づけに用いたパケットスケジューリング・CPU スケジューリング・LLM サービングの文献情報は以下の通りです。

[1] Pawan Goyal, Harrick M. Vin, Haichen Cheng, "Start-time Fair Queueing: A Scheduling Algorithm for Integrated Services Packet Switching Networks," SIGCOMM, 157―168, 1996. （Start-time Fair Queueing。本記事の主題）
[2] M. Shreedhar, George Varghese, "Efficient Fair Queuing Using Deficit Round-Robin," IEEE/ACM Transactions on Networking 4(3), 375―385, 1996. （Deficit Round Robin）
[3] Alan Demers, Srinivasan Keshav, Scott Shenker, "Analysis and Simulation of a Fair Queueing Algorithm," SIGCOMM, 1―12, 1989. （Fair Queueing / WFQ）
[4] Abhay K. Parekh, Robert G. Gallager, "A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Case," IEEE/ACM Transactions on Networking 1(3), 344―357, 1993. （Generalized Processor Sharing）
[5] Carl A. Waldspurger, William E. Weihl, "Stride Scheduling: Deterministic Proportional-Share Resource Management," Technical Memorandum MIT/LCS/TM-528, MIT Laboratory for Computer Science, 1995. （Stride scheduling）
[6] Ingo Molnar, "CFS Scheduler," The Linux Kernel documentation, 2007. （Linux CFS の設計文書）
[7] Ying Sheng, Shiyi Cao, Dacheng Li, Banghua Zhu, Zhuohan Li, Danyang Zhuo, Joseph E. Gonzalez, Ion Stoica, "Fairness in Serving Large Language Models," OSDI, 2024. （VTC: 推論エンジン内部でのトークン単位の公平化）
[8] Shiyi Cao, Yichuan Wang, Ziming Mao, Pin-Lun Hsu, Liangsheng Yin, Tian Xia, Dacheng Li, Shu Liu, Yineng Zhang, Yang Zhou, Ying Sheng, Joseph Gonzalez, Ion Stoica, "Locality-aware Fair Scheduling in LLM Serving," arXiv preprint arXiv:2501.14312, 2025. （DLPM: プレフィックス局所性と公平性の両立）
[9] Zhixiang Wei, James Yen, Jingyi Chen, Ziyang Zhang, Zhibai Huang, Chen Chen, Xingzi Yu, Yicheng Gu, Chenggang Wu, Yun Wang, Mingyuan Xia, Jie Wu, Hao Wang, Zhengwei Qi, "Equinox: Holistic Fair Scheduling in Serving Large Language Models," arXiv preprint arXiv:2508.16646, 2025. （Equinox: 公平性と運用効率の総合的な扱い）

最終更新日: 2026年7月12日