ブロックI/O層とマルチキュー（blk-mq）の構造

ブロックI/O層を「データ構造」で捉える

read/write はシステムコールでカーネルに入り、ページキャッシュを抜けると最終的にブロックデバイスへの要求になります。この変換を担うのがブロックI/O層ですが、本記事はスケジューラの並べ替えアルゴリズムではなく、層を流れるデータ構造とキューの構造に焦点を当てます。並べ替え方式の系譜（エレベータ・Deadline・CFQ）はI/OスケジューラとブロックI/O層で扱っているので、ここでは「bioがどうrequestになり、どのキューを通ってデバイスへ届くか」を構造図として言葉で描きます。

要点を先に置くと、層の中心には2つの構造体があります。

• bio：I/Oの入力単位。1回の論理I/Oを表し、「どのセクタ範囲へ／どのメモリページ群（bio_vec配列）の内容を／読むか書くか」を持つ。ファイルシステムが論理オフセットを物理ブロック（LBA）へ翻訳した結果がここに詰まる。
• request：デバイスへの発行単位。隣接・連続する複数の bio をマージして束ねたもの。実際にドライバがコマンド化して投げる粒度。

read/write ─→ bio ─→ (マージ) ─→ request ─→ ディスパッチ ─→ ドライバ ─→ デバイス
          入力単位            発行単位

つまり層の仕事は「多数の小さな bio を、できるだけ大きく連続した request に束ね、適切なキューを経由してデバイスへ流す」ことです。

bio から request へ：マージという束ね

新しい bio が届くと、層はまず既存の request に合体できないかを探します。これがマージで、コマンド発行回数とデバイス側のオーバーヘッドを直接減らす最も効く最適化です。

• バックマージ：新 bio のセクタが、既存 request の末尾の直後に連続する場合。最も頻度が高い。
• フロントマージ：新 bio が既存 request の先頭の直前に連続する場合。
• マージ不可：連続しない、あるいはサイズ上限（max_sectors）や境界制約に触れる場合は、新たな request を起こす。

既存request: セクタ[100..107]
新bio:       セクタ[108..111]  → バックマージ → [100..111] へ拡張
新bio:       セクタ[ 96.. 99]  → フロントマージ → [ 96..107] へ拡張
新bio:       セクタ[500..503]  → 連続しない    → 新しいrequestを生成

隣接候補を高速に探すため、層は最近のリクエストをハッシュやコア局所のキャッシュ（plug、後述）で管理します。マージは要求数そのものを減らすため、並べ替えで移動距離を縮める以上に効く場面が多いのが実務上のポイントです。

なぜ単一キューが頭打ちになったのか

blk-mq以前のレガシーブロック層は、デバイスごとに1本の request キューを1つのスピンロック（queue_lock）で保護する設計でした。HDD時代はこれで十分でした。デバイス自体が直列（ヘッドは1つ）なので、要求を直列に並べること自体が仕事だったからです。

ところがSSD、とりわけNVMeが前提を壊します。SSDにはシークも回転待ちもなく、性能の源は内部の多数チャネルを同時に叩く並列性へ移りました。NVMe規格は最大65535本のサブミッションキュー、各深さ最大65536を許します。この並列デバイスに対し、単一キュー＋単一ロックは構造的な欠陥になります。

• 全CPUコアが1本のロックを奪い合う。コア数が増えるほど競合が悪化し、ロック取得待ちがCPUを飽和させる。
• せっかく並列に受けられるデバイスへ、要求を直列にしか注げない。デバイスの実力の前にソフト側が律速する。
• 完了割り込みを処理するコアが、要求を発行したコアと異なると、request 構造へのアクセスがキャッシュライン越しに飛び回る（キャッシュ局所性が崩れる）。

数十万〜数百万IOPSの世界では、この単一直列点が決定的なボトルネックでした。「デバイスは速いのにカーネルが追いつかない」を解くには、キューの構造そのものを変える必要があったのです。

blk-mq：二段キューという答え

blk-mq（マルチキューブロック層）は、1本だったキューを2段に分離します。役割が明確に分かれている点が設計の核です。

• ソフトウェアキュー（ctx）：CPU（コア）ごとに1本。要求はまず自コアのキューに入る。コア局所なのでロック競合が原理的に消える。マージや並べ替えはここで完結する。
• ハードウェアディスパッチキュー（hctx）：デバイスが持つ実キューに1対1で対応。ソフトウェアキューの要求をここへ流し込み、ドライバがデバイスへ発行する。

 CPU0   CPU1   CPU2   CPU3       ← ソフトウェアキュー ctx（コア毎・競合なし）
   \     |      |     /
     [  hctx 0  ]  [  hctx 1  ]  ← ハードウェアディスパッチキュー（実キューに対応）
          |             |
      NVMe SQ/CQ0    NVMe SQ/CQ1 ← デバイスの実キュー（並列に発行）

ctx から hctx への対応づけ（マッピング）が肝です。コアとハードウェアキューを揃えれば、そのコアで発行した要求の完了割り込みを、同じコアで受けられる。request 構造が同じCPUのキャッシュに留まり、コア間のキャッシュライン移動が消えます（割り込みの上半分・下半分の完了処理がここに乗ります）。NVMeドライバは典型的にコア数ぶんのハードウェアキューを作り、ctx と hctx をほぼ1対1に張ることで、発行から完了までを1コアで閉じます。

構造の対比：レガシー vs blk-mq

両者の差は「並べ替えアルゴリズム」ではなくキューとロックの構造にあります。

Linuxは段階的に移行し、最終的にレガシー層を撤廃してblk-mqへ一本化しました。現在のスケジューラ（none／mq-deadline／kyber／bfq）はすべてblk-mqの上に載る実装であり、この二段キュー構造が共通の土台です。

NVMe時代のスケーラビリティが生まれる仕組み

なぜこの構造が「スケールする」と言えるのか。スケーラビリティはコアを増やしたとき性能が頭打ちにならず伸びることを指し、その条件はコア間で共有する書き込みポイントを無くすことです。blk-mqはそれを構造で満たします。

1. ロック競合の消滅：要求は自コアのソフトウェアキューに入るため、ホットパスにコア共有ロックが無い。コアを足しても競合が増えない。
2. キャッシュ局所性の維持：発行と完了が同コアに閉じ、request 構造のキャッシュライン移動が起きない。コアごとに独立して回る（NUMA局所性とも同じ発想）。
3. デバイス並列性の解放：ハードウェアキューが実キューに1対1で張られ、複数コアが互いに干渉せず同時にコマンドを発行できる。NVMeの数万キューに対し、ソフト側がボトルネックにならない。

理想：性能 ∝ コア数（各コアが独立に発行・完了）
  Core0 → ctx0 → hctx0 → SQ0   ┐
  Core1 → ctx1 → hctx1 → SQ1   ├ 共有点なし＝線形に近くスケール
  Core2 → ctx2 → hctx2 → SQ2   ┘

完全な線形ではありません。タグ空間やデバイス側キュー数が有限なので、コア数がハードウェアキュー数を超えると複数 ctx が1つの hctx を共有し、そこに軽い同期が戻ります。それでも「全コアが1ロックを奪い合う」旧来の構造に比べれば、競合点は桁違いに小さく抑えられます。

まとめ