局所トレーサビリティビュー グループ: HERD

同一キャッシュキーに対する並行リクエストを直列化し、1つのリクエストのみが関数を実行し、他のリクエストはその結果を共有することで重複実行を防止できること。

コンポーネント構成

graph TD
  A[core.Spot] -->|管理要求| B[CacheManager]
  B -->|In-flight追跡| C[_inflight Dict]
  C -->|同期待機| D[threading.Event]
  C -->|非同期待機| E[asyncio.Future]

コンポーネント責務

コンポーネント責務インターフェースCacheManagerキャッシュキーごとの実行状態管理と実行のシリアライズget_or_create_inflight()_inflight実行中のタスクを保持し、後続リクエストをイベントで待機させるExecutionStatecore.Spot待機結果の受け取りとエラーの伝播cached_run()

データフロー

sequenceDiagram
  participant T1 as Thread 1 (First)
  participant T2 as Thread 2 (Second)
  participant CM as CacheManager
  participant Fn as Target Function

  T1->>CM: get_or_create(key)
  Note over CM: 新規作成 (Executor)
  T2->>CM: get_or_create(key)
  Note over CM: 既存あり (Waiter)

  T1->>Fn: execute()
  Fn-->>T1: result
  T1->>CM: set_result(key, result)
  Note over CM: Eventをセット
  CM-->>T2: notify result
  T1-->>T1: return result
  T2-->>T2: return result

技術選定

技術領域選定理由待機機構Event / FutureOS/ランタイムレベルの待機を使用し、CPU負荷（ビジーループ）を回避スコープキャッシュキー単位異なる関数の実行は妨げず、同一入力のみを直列化安全策タイムアウト & リトライ実行者がハングした場合に、待機側がデッドロックしないよう保護

非機能要件方針

• 一貫性: 実行者が成功すれば全員に結果を、失敗すれば全員に同じ例外を伝播

• 効率性: メモリリークを防ぐため、結果配布後に _inflight エントリを即座に削除

• 信頼性: 強参照 (StrongReference) で実行中のタスクを保持し、GCによる消失を防止

インターフェース

class CacheManager:
    def get_or_create_inflight(
        self, key: str, is_async: bool
    ) -> ExecutionState: ...

振る舞い

同時実行制御

1. キャッシュキーをキーとした _inflight 辞書をチェックする
2. 存在しない場合: ExecutionState を新規作成し、自分が「実行者 (Executor)」となる
3. 存在する場合: 既存の ExecutionState を返し、自分は「待機者 (Waiter)」となる
4. 完了通知: 実行者が処理を終えたら、ExecutionState の Event (または Future) をセットし、結果を共有する

強参照によるインフライト状態の保持

目的

実行中のタスク状態（イベント・結果・Future）が GC によって消失しないよう、 _inflight 辞書を通じて強参照で保持する。WeakRef は使用しない。

データ構造

_inflight 辞書はキャッシュキーをキーとし、以下の3要素タプルを値として保持する:

_inflight: dict[str, tuple[threading.Event, list[asyncio.Future], list]]

ライフサイクル

1. 作成: wait_herd_sync / wait_herd_async で _inflight にキーが存在しない場合、 _inflight_lock を保持した状態で新規タプルを挿入する
2. 保持: 実行者が処理を完了するまで、_inflight 辞書がタプルへの唯一の管理参照を保持する。 待機者はロック取得時にタプル要素への参照を取得するが、_inflight エントリが正規の所有者である
3. 解放: notify_and_cleanup_inflight で以下の順序で解放する: a. _inflight_lock を取得し、エントリの同一性を event の identity (is) で確認する b. 辞書からエントリを削除する（del _inflight[cache_key]） c. ロックを解放した後、event.set() で同期待機者に通知する d. futures リスト内の各 asyncio.Future に結果またはエラーを伝播する

不変条件

• _inflight 辞書への挿入・削除は常に _inflight_lock の保護下で行う
• 1つのキャッシュキーに対して _inflight 内には高々1つのエントリしか存在しない
• エントリの削除は、挿入時の event と同一オブジェクト（is 比較）を持つスレッドのみが行える
• result_box への書き込みは実行者スレッドのみが行い、待機者は読み取り専用とする
• futures リストへの追加は _inflight_lock の保護下でのみ行う

GC安全性

_inflight 辞書は CacheManager インスタンスの属性であり、CacheManager が 生存している限り、全てのインフライトエントリは GC の対象にならない。 CacheManager 自体は Spot インスタンスが所有するため、with spot: ブロック内での 安全性が保証される。

パラメータ詳細

エラーハンドリング

• 実行者失敗: 実行者が例外を投げた場合、待機者全員にも同じ例外が伝播される。
• タイムアウト: タイムアウト時は待機を解除し、自らが実行者となって再試行（またはエラー）を試みる。

エッジケース

• 非同期混在: 同一キーに対して同期実行と非同期実行が混在する場合も、スレッドセーフなロックにより一つの実行に絞り込まれる。

目的

Thundering Herd Protection は、同一キーへの並行リクエストが一斉に関数を実行する「Thundering Herd」問題を防ぐ。この保護が不完全だと、重い計算やAPI呼び出しが不要に多重実行され、リソース浪費やレートリミット超過を招く。並行性バグはテスト困難であるため、複数の観点から網羅的に検証する。

検証観点

• 同期並行: 複数スレッドが同一キーで同時にキャッシュミスした場合、関数が1回のみ実行され、全スレッドが同じ結果を受け取ること
• 非同期並行: 複数の asyncio.Task が同一キーで同時にキャッシュミスした場合も、関数が1回のみ実行されること
• 例外伝播: 実行者（executor）の関数が例外を送出した場合、全待機スレッド/タスクに同じ例外が伝播すること。例外後に _inflight エントリがクリーンアップされること
• タイムアウト: 待機が HERD_TIMEOUT（300秒）を超過した場合にタイムアウト処理が発動し、無限待機にならないこと
• リトライ: HERD_MAX_RETRIES（3回）の範囲でリトライが行われ、上限超過で最終エラーが返ること
• CacheManager モック: _inflight 辞書の状態遷移（エントリ追加→結果セット→エントリ削除）が正しい順序で行われること

実装概要

CacheManager クラス内で、Thundering Herd（キャッシュミス時に同一キーへの 大量アクセスが同時に発生する問題）を防止する直列化機構を実装。 _inflight 辞書で実行中のキーを管理し、最初の1スレッド/タスクだけが関数を実行し、 後続の呼び出しは wait_herd_sync / wait_herd_async でその完了を待機する。

設計判断

同期・非同期の統合的保護

_inflight 辞書の値として (threading.Event, list[asyncio.Future], list[result]) の タプルを保持し、スレッドベースの待機 (Event.wait) と asyncio ベースの待機 (Future) の 両方を単一の管理下で混在できるようにしている。

タイムアウトと再試行（自己回復）

関数の実行がハングアップした場合に待機側が永遠にブロックされるのを防ぐため、 HERD_TIMEOUT（300秒）と HERD_MAX_RETRIES（3回）を設定。 タイムアウト時には警告ログを出しつつ再試行し、上限を超えれば TimeoutError で フェイルファストする堅牢な設計とした。

実装メモ

• notify_and_cleanup_inflight() で待機タスクへの結果伝播と _inflight からの削除を _inflight_lock によりアトミックに行う
• result_box（要素数1のリスト）をリファレンス渡しで共有することで、 Event が set された際に安全に結果を取得できるようにしている
• _notify_future() は call_soon_threadsafe を使い、非同期Futureに対して 別スレッドから安全に結果（または例外）をセットする