| 1 | # SPDX-License-Identifier: Apache-2.0 |
| 2 | # SPDX-FileCopyrightText: Copyright contributors to the vLLM project |
| 3 | """In-process auxiliary-output storage.""" |
| 4 | |
| 5 | from __future__ import annotations |
| 6 | |
| 7 | import mmap |
| 8 | import queue |
| 9 | import threading |
| 10 | from collections import OrderedDict |
| 11 | from collections.abc import Iterable |
| 12 | from dataclasses import dataclass |
| 13 | |
| 14 | |
| 15 | @dataclass(frozen=True) |
| 16 | class BlockObject: |
| 17 | """One immutable auxiliary output object.""" |
| 18 | |
| 19 | key: str |
| 20 | payload: bytes |
| 21 | |
| 22 | |
| 23 | class BlockObjectStoreError(RuntimeError): |
| 24 | """AuxOutput storage or retrieval failed.""" |
| 25 | |
| 26 | |
| 27 | class BackgroundBlockObjectStore: |
| 28 | """Serialize store mutations on a background thread.""" |
| 29 | |
| 30 | def __init__(self, store: BlockObjectStore, *, max_pending_batches: int) -> None: |
| 31 | self._store = store |
| 32 | self._queue: queue.Queue[ |
| 33 | tuple[list[BlockObject], tuple[str, ...], tuple[str, ...]] | None |
| 34 | ] = queue.Queue(maxsize=max_pending_batches) |
| 35 | self._error: BaseException | None = None |
| 36 | self._closed = False |
| 37 | self._thread = threading.Thread( |
| 38 | target=self._run, |
| 39 | daemon=True, |
| 40 | name="vllm-aux-output-writer", |
| 41 | ) |
| 42 | self._thread.start() |
| 43 | |
| 44 | def _run(self) -> None: |
| 45 | while True: |
| 46 | update = self._queue.get() |
| 47 | try: |
| 48 | if update is None: |
| 49 | return |
| 50 | if self._error is None: |
| 51 | objects, retain_keys, release_keys = update |
| 52 | self._store.put( |
| 53 | objects, |
| 54 | retain_keys=retain_keys, |
| 55 | release_keys=release_keys, |
| 56 | ) |
| 57 | except BaseException as error: |
| 58 | self._error = error |
| 59 | finally: |
| 60 | self._queue.task_done() |
| 61 | |
| 62 | def _raise_if_failed(self) -> None: |
| 63 | if self._error is not None: |
| 64 | raise BlockObjectStoreError( |
| 65 | "auxiliary output publication failed" |
| 66 | ) from self._error |
| 67 | |
| 68 | def put( |
| 69 | self, |
| 70 | objects: list[BlockObject], |
| 71 | *, |
| 72 | retain_keys: Iterable[str] = (), |
| 73 | release_keys: Iterable[str] = (), |
| 74 | ) -> None: |
| 75 | retains = tuple(retain_keys) |
| 76 | releases = tuple(release_keys) |
| 77 | if not objects and not retains and not releases: |
| 78 | return |
| 79 | if self._closed: |
| 80 | raise RuntimeError("auxiliary output store is closed") |
| 81 | self._queue.put((objects, retains, releases)) |
| 82 | self._raise_if_failed() |
| 83 | |
| 84 | def get_concatenated(self, keys: list[str]) -> bytes: |
| 85 | self._queue.join() |
| 86 | self._raise_if_failed() |
| 87 | return self._store.get_concatenated(keys) |
| 88 | |
| 89 | def close(self) -> None: |
| 90 | if self._closed: |
| 91 | return |
| 92 | self._closed = True |
| 93 | self._queue.join() |
| 94 | self._queue.put(None) |
| 95 | self._thread.join() |
| 96 | self._store.close() |
| 97 | self._raise_if_failed() |
| 98 | |
| 99 | |
| 100 | class BlockObjectStore: |
| 101 | """Single-owner bounded store that fails closed after an eviction.""" |
| 102 | |
| 103 | _UNALLOCATED_SLOT = -1 |
| 104 | |
| 105 | def __init__( |
| 106 | self, |
| 107 | *, |
| 108 | max_bytes: int, |
| 109 | object_nbytes: int, |
| 110 | ) -> None: |
| 111 | if object_nbytes <= 0: |
| 112 | raise ValueError("auxiliary output object size must be positive") |
| 113 | if max_bytes < object_nbytes: |
| 114 | raise ValueError("auxiliary output store must fit at least one object") |
| 115 | self.object_nbytes = object_nbytes |
| 116 | self.num_slots = max_bytes // object_nbytes |
| 117 | self._lru: OrderedDict[str, int] = OrderedDict() |
| 118 | self._references: dict[str, int] = {} |
| 119 | self._free_slots: list[int] = [] |
| 120 | self._next_slot = 0 |
| 121 | self._arena: mmap.mmap | None = mmap.mmap( |
| 122 | -1, self.num_slots * self.object_nbytes |
| 123 | ) |
| 124 | |
| 125 | def _evict_to_fit(self, protected: set[str]) -> None: |
| 126 | excess = len(self._lru) - self.num_slots |
| 127 | if excess <= 0: |
| 128 | return |
| 129 | victims = [] |
| 130 | for key in self._lru: |
| 131 | if key not in self._references and key not in protected: |
| 132 | victims.append(key) |
| 133 | if len(victims) == excess: |
| 134 | break |
| 135 | if len(victims) != excess: |
| 136 | raise BlockObjectStoreError( |
| 137 | "auxiliary output store cannot retain the requested batch: " |
| 138 | f"limit={self.num_slots} objects" |
| 139 | ) |
| 140 | for victim in victims: |
| 141 | slot = self._lru.pop(victim) |
| 142 | if slot != self._UNALLOCATED_SLOT: |
| 143 | self._free_slots.append(slot) |
| 144 | |
| 145 | def _allocate_slot(self) -> int: |
| 146 | if self._free_slots: |
| 147 | return self._free_slots.pop() |
| 148 | slot = self._next_slot |
| 149 | self._next_slot += 1 |
| 150 | return slot |
| 151 | |
| 152 | def put( |
| 153 | self, |
| 154 | objects: list[BlockObject], |
| 155 | *, |
| 156 | retain_keys: Iterable[str] = (), |
| 157 | release_keys: Iterable[str] = (), |
| 158 | ) -> None: |
| 159 | arena = self._arena |
| 160 | if arena is None: |
| 161 | raise RuntimeError("auxiliary output store is closed") |
| 162 | unique = {obj.key: obj for obj in objects} |
| 163 | self._retain(retain_keys) |
| 164 | terminal_order = self._release(release_keys) |
| 165 | for key in unique: |
| 166 | self._lru.setdefault(key, self._UNALLOCATED_SLOT) |
| 167 | self._lru.move_to_end(key) |
| 168 | for key in terminal_order: |
| 169 | if key in self._lru: |
| 170 | self._lru.move_to_end(key) |
| 171 | try: |
| 172 | self._evict_to_fit(set(unique) - set(terminal_order)) |
| 173 | except BlockObjectStoreError: |
| 174 | for key in unique: |
| 175 | if self._lru.get(key) == self._UNALLOCATED_SLOT: |
| 176 | del self._lru[key] |
| 177 | raise |
| 178 | for object_id, obj in unique.items(): |
| 179 | slot = self._lru.get(object_id) |
| 180 | if slot is None: |
| 181 | continue |
| 182 | if slot != self._UNALLOCATED_SLOT: |
| 183 | continue |
| 184 | slot = self._allocate_slot() |
| 185 | offset = slot * self.object_nbytes |
| 186 | arena[offset : offset + self.object_nbytes] = obj.payload |
| 187 | self._lru[object_id] = slot |
| 188 | |
| 189 | def _retain(self, keys: Iterable[str]) -> None: |
| 190 | for key in keys: |
| 191 | references = self._references.get(key, 0) |
| 192 | self._references[key] = references + 1 |
| 193 | |
| 194 | def _release(self, keys: Iterable[str]) -> list[str]: |
| 195 | terminal_order = [] |
| 196 | for key in keys: |
| 197 | references = self._references[key] - 1 |
| 198 | if references: |
| 199 | self._references[key] = references |
| 200 | continue |
| 201 | del self._references[key] |
| 202 | terminal_order.append(key) |
| 203 | return terminal_order |
| 204 | |
| 205 | def get_concatenated(self, keys: list[str]) -> bytes: |
| 206 | arena_obj = self._arena |
| 207 | if arena_obj is None: |
| 208 | raise RuntimeError("auxiliary output store is closed") |
| 209 | try: |
| 210 | entries = [self._lru[key] for key in keys] |
| 211 | except KeyError as error: |
| 212 | raise BlockObjectStoreError( |
| 213 | "auxiliary output object does not exist; the object may have been " |
| 214 | f"evicted (used={len(self._lru)}, " |
| 215 | f"limit={self.num_slots} objects). Increase " |
| 216 | "aux_output_config.max_bytes when a KV cache hit requires it." |
| 217 | ) from error |
| 218 | arena = memoryview(arena_obj) |
| 219 | try: |
| 220 | payload = b"".join( |
| 221 | arena[slot * self.object_nbytes : (slot + 1) * self.object_nbytes] |
| 222 | for slot in entries |
| 223 | ) |
| 224 | finally: |
| 225 | arena.release() |
| 226 | for key in keys: |
| 227 | self._lru.move_to_end(key) |
| 228 | return payload |
| 229 | |
| 230 | def close(self) -> None: |
| 231 | arena = self._arena |
| 232 | if arena is not None: |
| 233 | self._arena = None |
| 234 | arena.close() |