非同期待機なし（Wait-Free）配列ベースの有限キュー：WFQueue

2026 年 3 月 12 日に公開された記事によると、Rust で実装された有界キューの実装とパフォーマンス分析についての詳細です。本稿では、その内容を日本語に翻訳し、整理した Markdown 形式で紹介します。

理論的背景

このキューは、チケットロックによる待機システムに基づいて動作します。以下のような仕組みを想像してください。

• 2 つの発行装置: 生産者用と消費者用のチケット発行装置があります。
• N つの箱: 並べられた N つの格納領域（箱）があり、0 から $N-1$ の番号が付いています。
• ディスプレイ: 各箱の上には現在の順番を追跡する表示があり、そこには予約番号と所有者の種類（生産側か消費側か）が表示されます。

チケットの仕組み

各チケットには以下の 2 つの数値が印刷されています。

1. 箱の番号
2. 予約番号

動作手順

生産者も消費者も、以下の単純な手順に従います。

1. 適切な発行装置からチケットを受け取る。
2. チケット上の番号に対応する箱を見つける。
3. その箱のディスプレイに、チケットに記された予約番号が表示されるまで待つ。
4. 予約番号が表示されると、許可された動作（アイテムを取出す【消費】または配置する【生産】）を実行する。

システム保証条件

予約システムは、任意の 1 つの箱に対して常に以下の条件が成り立つことを保証します。

• その箱は最初は空の状態である。
• 最初に呼ばれるチケットは必ず生産者のものである。
• 同じ種類のチケットが連なっておくことは決してない（例：生産者が続けてしまうことは防止される）。

設計意図: これにより、生産者は常にアイテムを置くための空の箱を持ち続け、消費者は常にアイテムを取り出すことができる満杯の箱を持てるように設計されています。

実装構造と設計思想

理論的な仕組みを実装に移すために、以下の構成要素を使用します。

• カウンター（2 つ）: 生産者用と消費者用にそれぞれ

  AtomicUsize

  タイプで管理。
• リングバッファ（2 つ）:
  • 「データ」バッファ: 実際にキューを通じてアイテムを送受信するために使用。
  • 「状態」バッファ: データバッファ内の各エントリの所有者を追跡するために使用。

主要構造体

/// 非同期待機なし（wait-free）の配列ベースの有界キュー
pub struct WFQueue<T, const N: usize> {
    // NonNull ポインタを使用することで、以下を防ぐことができます：
    // 1. 所有権を持たない値に対して意図せず dereference（参照解除）を行うこと。
    //    これにより未定義振動（UB）を回避します。
    // 2. Box の drop 依存をなくし、既に所有権を失った値に対して意図せず drop を呼び出さないようにします。
    // 手動でのメモリ割り当てを採用しています。
    data: NonNull<[CachePadded<T>; N]>,
    state: NonNull<[CachePadded<AtomicTicket>; N]>,
    prod_reserve: CachePadded<AtomicUsize>,
    cons_reserve: CachePadded<AtomicUsize>,
}

付録的な技術的仕様

• 前提: システム上の

  usize

  タイプが 8 バイト（64 ビット）を持つことを前提としています（アーキテクチャ依存ではなく、議論を容易にするための仮定）。
• AtomicTicket:

  AtomicUsize

  をラップする構造体です。
  • 最低位 63 ビット: 予約番号を格納。
  • 最高位ビット: チケットの種類（生産者か消費者か）を表します。
  • 排他性: 値には、対応するスロットについて誰が読み書き権限を持っているかを示す情報が含まれます。

予約番号とインデックスの計算

• 予約番号:

  fetch_add

  によって生成されます。
• インデックス取得: 状態バッファとデータバッファのインデックスは、予約番号をバッファサイズ $N$ で割った余り（modulo）で得られます。
• 最適化: 割り算・剰余演算は高価であるため、$N$ を 2 のべき乗に強制します。
  • これにより、

    (x & (N - 1)) == x % N

    という性質を利用し、ビットマスク（AND 演算）でインデックスを取得できます。
  • チケットには箱の番号（下 $N$ ビット）と予約番号が含まれており、箱の番号は bitwise AND 演算で得られます。

メモリ構成図

状態バッファのエントリとデータバッファの関係は以下の通りです。

+---+---+---+-----+-------+-------+-------+
| 0 | 1 | 2 | ... | n - 3 | n - 2 | n - 1 | <-- データバッファ (値を持つ)
+---+---+---+-----+-------+-------+-------+
  ^   ^   ^    ^      ^       ^       |
  |   |   |    |      |       |       |
+---+---+---+-----+-------+-------+-------+
| 0 | 1 | 2 | ... | n - 3 | n - 2 | n - 1 | <-- 状態バッファ (所有権を示す)
+---+---+---+-----+-------+-------+-------+
                 /         \
                /           \
               /             \
      +------------------------------+
      | 63         | 62:0            |
      +------------+-----------------+
      | status_bit | reservation_num |
      +------------+-----------------+

動作フロー

1. 生産者（Producer）の手順：アイテムをキューに投入

1. fetch_add

   で生産者カウンターを 1 増やし、増やす前の値を予約番号として保存する。
2. 状態バッファの該当スロットが以下の条件を満たすまで待つ：
   • 値が予約番号（63 ビットのみ）に対応していること。
   • スロットの状態ビットに「生産者の順番」を示す値があること。
3. 対応するデータバッファのスロットに望む値を格納する。
4. 状態バッファのエントリ内の状態ビットを切り替え、「消費者の順番」であることを示す。

2. 消費者（Consumer）の手順：アイテムを取り出す

1. fetch_add

   で消费者カウンターを 1 増やし、増やす前の値を予約番号として保存する。
2. 状態バッファの該当スロットが以下の条件を満たすまで待つ：
   • 値が予約番号（63 ビットのみ）に対応していること。
   • スロットの状態ビットに「消費者の順番」を示す値があること。
3. 対応するリングバッファのスロットから値を読み取る。
4. 状態バッファのスロットを更新：
   • 値を

     reservation_number + N

     に設定する。
   • スロットの状態ビットに「生産者の順番」を示す値とする。

メリットと特徴

1. CAS ループ不要・キャッシュ競合最小化

• CAS 不使用: Compare-And-Swap（原子比較交換）のループを使用しない設計です。
• キャッシュ効率: 状態バッファから順序待ちを行うことで、スロットのキャッシュは共有状態として維持され、MESI モデルに基づく競合が最小化されます。
• 所有権の移行: キャッシュの状態変更は、アクター（スレッド）の動作終了時だけで行われます。

2. 有界待機（Bounded Waiting）

• スレッドのサスペンドや例外発生を除けば、操作時間は上限があります。
• 饥饿（Starvation）：どの消費者も生産者も必ず進みます。
• 完了保証: すべてのエンキュー・デキュー操作は最終的に完了します。
  • 注意: OS のスレッドサスペンドや失敗による待機時間は含まれません（例：キューが満杯で消费者が動いていない場合、待ち続けても完了しない）。
• ターン制（Turn-based）: 予約番号による順序付けが機能しています。
  • 待機時間は「対立する種類のアクティブなアクターの数」と「自身の順番までの位置」によって決まります。
  • 待機時間の上限は、異なる種類のアクティブなアクターの数 $j$ に反比例します：$\frac{((\max(k - 1, 0) \cdot N) + kl)}{j}$

重要: 「駆動可能な（drivable）」操作を提供していますが、定期的に行わないとデッドロックを引き起こす可能性があります。 注: メモリアクセスによるキャッシュ競合のオーバーヘッドは考慮していません。

3. フロント・オブ・ライン・ブロッキングの最小化

• 局所性: スローダウン（遅延）が、自分自身のスロットにのみ限定されます。
• 例:
  • 2 つの生産者がいる場合、1 番目の生産者がスローダウンしても、2 番目の生産者は影響を受けず、正常に進みます。
  • 同様に、消費者側でも先行するスレッドが停止しても、後続の処理は影響を受けずに継続できます。
• 前提条件: 生産者の場合「キューが完全に空」、消费者的場合「キューが完全に満杯」を想定しています。

4. 駆動可能なエンキュー/デキュー操作（Drivable Operations）

• デフォルトではターン待ち（スピン）しますが、代替として「駆動可能」なバージョンも提供されます。
• メソッド:

  drive(num_attempts)

  メソッドを呼び出し、試行回数を指定します。
• 利点: イベントループや非同期処理において、他のキュー操作に過度に影響を与えずに使用できます。

技術的制限と目立つ挙動

極めて稀な未定義振舞い（Undefined Behavior）のリスク

このキューは整数オーバーフロー時でも動作するように意図されていますが、特定条件下で未定義振舞いが発生する可能性があります。

• 発生条件:

  usize

  のビット幅を $n$ とし、$2^{n-1} + 1$ アイテムをエンキューしようとした場合。
  • 最初のエンキュー完了前の最後の操作において、予約番号がオーバーフローして 0 になる可能性があります（最高位ビットをマスクしているため）。
  • これにより、両方の生産者が同じメモリアドレスに原子でない書き込みを試み、競合状態が発生します。
• デキュー時のリスク: コピー可能なデータ型について、同一のコピーが 2 つ以上存在すると二重解放（double-free）など引き起こされる可能性があります。

頻度と規模の目安

• 32 ビット系: 約 20 億アイテム以上の処理が必要。
• 64 ビット系（現代の殆どのシステム）: 約 $9.22 \times 10^{18}$ ($9.22$ クインタリオン) アイテムの処理が必要。
  • この規模を達成することは現実的ではありませんが、技術的な制限として理解しておく必要があります。

高コストな解放（Drop）の実装

• 構造体を解放（drop）する際、操作を完了させるまで進めなければならないため高コストです。
• 理由: 状態バッファは所有者を追跡しており、駆動可能な操作は自分の順番になるまで完了させない限りキューがロックされてしまいます。

ベンチマーク結果

方法論

• テスト内容: $2^{24}$ アイテムのエンキュー・デキュー時間を測定（合成ベンチマーク）。
• 環境:
  • CPU: Ryzen 7 7800x3D
  • メモリ: 32 GiB DDR5 (6000 MT/s オーバークロック)
  • OS: Fedora Linux 44 (Kernel 7.0.4)
  • Rust: Stable 1.95.0

データ結果

N Consumers / N Producers (バランス型)

1 Producer / N Consumers (消費集中型)

1 Consumer / N Producers (生産集中型)

分析と結論

• パフォーマンス: 他のキューと比較しても比較的良い性能を有しています。
  • 「1C/1P」のケースでは状態バッファの管理コストにより他の方が劣りますが、スレッド数増加に伴いスケールアップします。
• N Consumers/N Producers の peculiar behavior:
  • $N=4$ でピークに達し、その後低下してから緩やかに回復するパターンが見られます。
  • 当初は物理コア数が 8 つしかないことが原因かと思われましたが、論理コアをすべて使用したときに最大スループットが出るため、これは誤りでした。
• 今後の予定: 現在このプロジェクトでの改善を控えています（将来的な研究に留める）。

ソースコード

実装、テスト、ベンチマークコードは以下のリポジトリで公開されています。

• GitHub リポジトリ

免責事項・補足:

• Wait-Free の定義に関する訂正: 以前は「wait-free（待機自由）」と主張していましたが、スレッドの故障やサスペンドが他を引き起こさないという厳密な定義を満たしていないため、現在は誤りと見なされています。関連セクションは修正済みですが、他の記述部分は更新されていません。
• 参照元:

  atomic_queue

  (max0x7ba) のリポジトリ内のスクリプトを参考にベンチマーク結果を取得しています。