| 1 | # SPDX-License-Identifier: Apache-2.0 |
| 2 | # SPDX-FileCopyrightText: Copyright contributors to the vLLM project |
| 3 | """AsyncLookupManager: per-tier async lookup manager for secondary tier |
| 4 | existence checks. |
| 5 | |
| 6 | Each secondary tier that wants non-blocking lookups composes its own |
| 7 | AsyncLookupManager instance internally. The manager maintains lookup |
| 8 | state and uses a background thread to execute batch_lookup() calls. |
| 9 | |
| 10 | Locking design |
| 11 | -------------- |
| 12 | There is no explicit lock. Thread safety is achieved by ownership: |
| 13 | |
| 14 | * _lookup_state and _lookup_batch are owned exclusively by the scheduler |
| 15 | thread. lookup(), flush(), and cleanup() read and write them directly. |
| 16 | |
| 17 | * _lookup_queue is written by the scheduler (flush → put_nowait, one item |
| 18 | per step) and read by the background thread (get). queue.Queue is |
| 19 | thread-safe. |
| 20 | |
| 21 | * _pending_results is written by the background thread (put) and read by |
| 22 | the scheduler (get_nowait inside drain_results). queue.SimpleQueue is |
| 23 | thread-safe by design. |
| 24 | |
| 25 | lookup() accumulates new keys in _lookup_batch without touching the queue. |
| 26 | flush() is called once per step from the tier's on_schedule_end(), posting |
| 27 | the entire batch as a single queue item so the background thread sees one |
| 28 | batch per step. |
| 29 | Results are drained on the first lookup after each flush, at flush(), and |
| 30 | after worker shutdown. In-flight lookups with no remaining request references |
| 31 | are retained until their results are drained, allowing new requests to share |
| 32 | the same probe. |
| 33 | """ |
| 34 | |
| 35 | import queue |
| 36 | import threading |
| 37 | from abc import ABC, abstractmethod |
| 38 | from collections.abc import Collection, Iterable |
| 39 | from dataclasses import dataclass, field |
| 40 | from enum import Enum, auto |
| 41 | |
| 42 | from vllm.logger import init_logger |
| 43 | from vllm.v1.kv_offload.base import OffloadKey, ReqContext |
| 44 | |
| 45 | logger = init_logger(__name__) |
| 46 | |
| 47 | |
| 48 | class LookupPhase(Enum): |
| 49 | """Lifecycle phase of a lookup probe.""" |
| 50 | |
| 51 | PENDING = auto() # Accumulated in _lookup_batch, but not yet submitted. |
| 52 | IN_FLIGHT = auto() # Submitted to the worker, but not yet resolved. |
| 53 | RESOLVED = auto() # A final verdict has been applied to the state. |
| 54 | |
| 55 | |
| 56 | @dataclass(slots=True) |
| 57 | class LookupState: |
| 58 | generation: int |
| 59 | phase: LookupPhase = LookupPhase.PENDING |
| 60 | # None while pending/in flight; True if the key exists; False if absent or |
| 61 | # explicitly marked missing after a failed load. |
| 62 | result: bool | None = None |
| 63 | request_ids: set[str] = field(default_factory=set) # requests asking for the lookup |
| 64 | |
| 65 | |
| 66 | class AsyncLookupManager(ABC): |
| 67 | """Per-tier async lookup manager for secondary tier existence checks. |
| 68 | |
| 69 | Each secondary tier that wants non-blocking lookups composes its own |
| 70 | AsyncLookupManager instance internally. The manager maintains lookup |
| 71 | state (cache, queue) and uses a background thread to execute the actual |
| 72 | batch_lookup() calls. |
| 73 | |
| 74 | Subclasses implement only batch_lookup() — all queue management, |
| 75 | state tracking, and result delivery is provided by this base class. |
| 76 | |
| 77 | The owning tier delegates its lookup(), on_schedule_end(), and |
| 78 | on_request_finished() to this manager: |
| 79 | - lookup() → drain_results() + lookup state check |
| 80 | - on_schedule_end() → flush() |
| 81 | - on_request_finished() → cleanup() |
| 82 | """ |
| 83 | |
| 84 | def __init__( |
| 85 | self, |
| 86 | tier_type: str, |
| 87 | ) -> None: |
| 88 | self._tier_type = tier_type |
| 89 | |
| 90 | # key → LookupState; scheduler-owned, no lock needed. |
| 91 | self._lookup_state: dict[OffloadKey, LookupState] = {} |
| 92 | # req_id → keys looked up by that request (reverse index for cleanup). |
| 93 | self._req_keys: dict[str, set[OffloadKey]] = {} |
| 94 | # Results from an older state must not be applied after cleanup removes |
| 95 | # and recreates a key. |
| 96 | self._next_generation = 0 |
| 97 | |
| 98 | # Accumulates (key, req_context, generation) triples during lookup(). |
| 99 | # Flushed as one queue item per step by flush(). |
| 100 | self._lookup_batch: list[tuple[OffloadKey, ReqContext, int]] = [] |
| 101 | |
| 102 | # Scheduler → worker: one full step's batch per item. |
| 103 | # None is used as a shutdown sentinel. |
| 104 | self._lookup_queue: queue.SimpleQueue[ |
| 105 | list[tuple[OffloadKey, ReqContext, int]] | None |
| 106 | ] = queue.SimpleQueue() |
| 107 | |
| 108 | # Worker → scheduler: completed result batches. |
| 109 | # Each item is a list of (key, generation, found) triples. |
| 110 | # SimpleQueue is explicitly thread-safe for one writer / one reader. |
| 111 | self._pending_results: queue.SimpleQueue[list[tuple[OffloadKey, int, bool]]] = ( |
| 112 | queue.SimpleQueue() |
| 113 | ) |
| 114 | self._need_to_drain: bool = False |
| 115 | |
| 116 | self._thread = threading.Thread( |
| 117 | target=self._worker, |
| 118 | name=f"vllm_offloading_lookup_{tier_type}", |
| 119 | daemon=True, |
| 120 | ) |
| 121 | self._thread.start() |
| 122 | |
| 123 | @abstractmethod |
| 124 | def batch_lookup( |
| 125 | self, keys: list[OffloadKey], req_context: ReqContext |
| 126 | ) -> Iterable[bool]: |
| 127 | """Check whether a batch of blocks exist in this tier. |
| 128 | |
| 129 | Called from the worker thread — must be synchronous and must not |
| 130 | touch the primary tier or scheduler state. |
| 131 | |
| 132 | Returns a list parallel to keys: True if present, False if not. |
| 133 | """ |
| 134 | ... |
| 135 | |
| 136 | # ------------------------------------------------------------------ |
| 137 | # Scheduler-thread API |
| 138 | # ------------------------------------------------------------------ |
| 139 | |
| 140 | def lookup(self, key: OffloadKey, req_context: ReqContext) -> bool | None: |
| 141 | """Non-blocking lookup called from the scheduler thread. |
| 142 | |
| 143 | Returns: |
| 144 | True — block is present in this tier. |
| 145 | False — block is not present in this tier. |
| 146 | None — result not yet available; retry next step. |
| 147 | |
| 148 | """ |
| 149 | if self._need_to_drain: |
| 150 | self.drain_results() |
| 151 | self._need_to_drain = False |
| 152 | req_id = req_context.req_id |
| 153 | state = self._lookup_state.get(key) |
| 154 | if state is None: |
| 155 | state = LookupState(generation=self._next_generation) |
| 156 | self._next_generation += 1 |
| 157 | self._lookup_state[key] = state |
| 158 | self._lookup_batch.append((key, req_context, state.generation)) |
| 159 | state.request_ids.add(req_id) |
| 160 | self._req_keys.setdefault(req_id, set()).add(key) |
| 161 | return state.result |
| 162 | |
| 163 | def flush(self) -> None: |
| 164 | """Post this step's accumulated keys to the worker thread. |
| 165 | |
| 166 | Called once per step from on_schedule_end() after all lookup() calls |
| 167 | are done. The worker receives the full batch and processes it during |
| 168 | the model-execution window, maximising time available before the next |
| 169 | step's drain_results(). Also drains completed lookups when there |
| 170 | are no new keys to submit. |
| 171 | """ |
| 172 | self.drain_results() |
| 173 | self._need_to_drain = True |
| 174 | batch = self._lookup_batch |
| 175 | self._lookup_batch = [] |
| 176 | in_flight_batch = [] |
| 177 | for key, req_context, generation in batch: |
| 178 | state = self._lookup_state.get(key) |
| 179 | if state is None or state.generation != generation: |
| 180 | continue |
| 181 | assert state.phase is LookupPhase.PENDING |
| 182 | state.phase = LookupPhase.IN_FLIGHT |
| 183 | in_flight_batch.append((key, req_context, generation)) |
| 184 | if in_flight_batch: |
| 185 | self._lookup_queue.put(in_flight_batch) |
| 186 | |
| 187 | def drain_results(self) -> None: |
| 188 | """Apply pending worker results to _lookup_state. |
| 189 | |
| 190 | Called from lookup(), flush(), and shutdown() on the scheduler thread. |
| 191 | """ |
| 192 | while True: |
| 193 | try: |
| 194 | batch = self._pending_results.get_nowait() |
| 195 | except queue.Empty: |
| 196 | break |
| 197 | for key, generation, result in batch: |
| 198 | state = self._lookup_state.get(key) |
| 199 | if state is None or state.generation != generation: |
| 200 | continue |
| 201 | if not state.request_ids: |
| 202 | del self._lookup_state[key] |
| 203 | continue |
| 204 | assert state.phase is LookupPhase.IN_FLIGHT |
| 205 | # Each lookup generation is enqueued exactly once. A matching |
| 206 | # generation must not receive a second result; stale |
| 207 | # generations were discarded above. |
| 208 | assert state.result is None, ( |
| 209 | "cached key received a second lookup result; the " |
| 210 | "enqueue-once invariant is broken and could reopen the " |
| 211 | "failed-load livelock" |
| 212 | ) |
| 213 | state.result = result |
| 214 | state.phase = LookupPhase.RESOLVED |
| 215 | |
| 216 | def mark_miss(self, keys: Collection[OffloadKey]) -> None: |
| 217 | """Force the cached verdict for ``keys`` to False after a failed load, so |
| 218 | the scheduler stops re-issuing the doomed promotion (livelock, #49176). |
| 219 | Keys with no cached entry are skipped.""" |
| 220 | for key in keys: |
| 221 | state = self._lookup_state.get(key) |
| 222 | if state is not None: |
| 223 | state.result = False |
| 224 | state.phase = LookupPhase.RESOLVED |
| 225 | |
| 226 | def cleanup(self, req_id: str) -> None: |
| 227 | """Release request references, retaining in-flight lookups. |
| 228 | |
| 229 | Called from the tier's on_request_finished(). Uses the reverse |
| 230 | index to visit only keys associated with this request. |
| 231 | """ |
| 232 | for key in self._req_keys.pop(req_id, ()): |
| 233 | state = self._lookup_state[key] |
| 234 | state.request_ids.discard(req_id) |
| 235 | if not state.request_ids and state.phase is not LookupPhase.IN_FLIGHT: |
| 236 | del self._lookup_state[key] |
| 237 | |
| 238 | def shutdown(self) -> None: |
| 239 | """Stop the worker thread and drain completed lookups.""" |
| 240 | self._lookup_queue.put(None) # unblock _worker from _lookup_queue.get() |
| 241 | self._thread.join() |
| 242 | self.drain_results() |
| 243 | |
| 244 | # ------------------------------------------------------------------ |
| 245 | # Internal helpers |
| 246 | # ------------------------------------------------------------------ |
| 247 | |
| 248 | def _worker(self) -> None: |
| 249 | while True: |
| 250 | pending = self._lookup_queue.get() |
| 251 | if pending is None: |
| 252 | break |
| 253 | |
| 254 | # Group by req_id. |
| 255 | batches: dict[str, tuple[ReqContext, list[tuple[OffloadKey, int]]]] = {} |
| 256 | for key, req_context, generation in pending: |
| 257 | req_id = req_context.req_id |
| 258 | if req_id not in batches: |
| 259 | batches[req_id] = (req_context, []) |
| 260 | batches[req_id][1].append((key, generation)) |
| 261 | |
| 262 | if not batches: |
| 263 | continue |
| 264 | |
| 265 | results: list[tuple[OffloadKey, int, bool]] = [] |
| 266 | for req_context, entries in batches.values(): |
| 267 | keys = [key for key, _ in entries] |
| 268 | try: |
| 269 | hits = self.batch_lookup(keys, req_context) |
| 270 | except Exception as exc: |
| 271 | logger.warning( |
| 272 | "batch_lookup failed on tier %s for %d keys: %s", |
| 273 | self._tier_type, |
| 274 | len(keys), |
| 275 | exc, |
| 276 | ) |
| 277 | hits = (False for _ in keys) |
| 278 | |
| 279 | for (key, generation), hit in zip(entries, hits): |
| 280 | results.append((key, generation, hit)) |
| 281 | |
| 282 | # Post the entire batch as one item — no lock needed. |
| 283 | if results: |
| 284 | self._pending_results.put(results) |