main
py 634 lines 20.8 KB
Raw
1 # SPDX-License-Identifier: Apache-2.0
2 # SPDX-FileCopyrightText: Copyright contributors to the vLLM project
3 """Core abstractions for KV cache offloading in vLLM v1."""
4
5 from abc import ABC, abstractmethod
6 from collections.abc import Collection, Iterable, Sequence
7 from dataclasses import dataclass, field
8 from enum import Enum, auto
9 from typing import TYPE_CHECKING, Any, ClassVar, NamedTuple, NewType, TypeVar
10
11 import numpy as np
12 import torch
13
14 if TYPE_CHECKING:
15 from vllm.distributed.kv_transfer.kv_connector.v1.offloading.metrics import (
16 OffloadingConnectorStats,
17 )
18
19 from vllm.v1.kv_hints import KvHintsEnvelope
20 from vllm.v1.kv_offload.config import OffloadingConfig
21
22 # `OffloadKey` identifies an offloaded block. It combines a block hash with
23 # its KV cache group index, encoded as raw bytes to avoid tuple GC overhead.
24 # Use the helper functions below to construct / decompose keys.
25 OffloadKey = NewType("OffloadKey", bytes)
26
27
28 def make_offload_key(block_hash: bytes, group_idx: int) -> OffloadKey:
29 """Pack a block hash and group index into an `OffloadKey`."""
30 return OffloadKey(block_hash + group_idx.to_bytes(4, "big", signed=False))
31
32
33 def get_offload_block_hash(key: OffloadKey) -> bytes:
34 """Extract the block hash from an `OffloadKey`."""
35 return key[:-4]
36
37
38 def get_offload_group_idx(key: OffloadKey) -> int:
39 """Extract the group index from an `OffloadKey`."""
40 return int.from_bytes(key[-4:], "big", signed=False)
41
42
43 _T = TypeVar("_T")
44
45
46 class Medium(Enum):
47 """Storage medium of an offloading tier."""
48
49 CPU = "CPU"
50 STORAGE = "STORAGE"
51
52
53 class Locality(Enum):
54 """Locality of a tier's storage relative to the publishing instance."""
55
56 LOCAL = "LOCAL"
57 REMOTE = "REMOTE"
58
59
60 class TierMatcher(NamedTuple):
61 medium: Medium | None = None
62 locality: Locality | None = None
63
64 def matches(self, medium: Medium | None, locality: Locality | None) -> bool:
65 medium_matches = self.medium is None or medium is None or self.medium == medium
66 locality_matches = (
67 self.locality is None or locality is None or self.locality == locality
68 )
69 return medium_matches and locality_matches
70
71
72 @dataclass(frozen=True)
73 class TierFilter:
74 """Per-request filter controlling which tiers participate."""
75
76 matchers: tuple[TierMatcher, ...] = ()
77
78 ALL: ClassVar["TierFilter"]
79
80 def allows(self, medium: Medium | None, locality: Locality | None) -> bool:
81 if self is TierFilter.ALL:
82 return True
83 return any(m.matches(medium, locality) for m in self.matchers)
84
85
86 TierFilter.ALL = TierFilter(matchers=(TierMatcher(),))
87
88
89 @dataclass
90 class ReqContext:
91 req_id: str
92 kv_transfer_params: dict[str, Any] | None = None
93 kv_hints: KvHintsEnvelope | None = None
94 load_tier_filter: TierFilter = TierFilter.ALL
95 # Per-request scratch space keyed by value type, so a tier can parse
96 # kv_transfer_params and kv_hints once (in on_new_request) and read the
97 # result back on later calls for the same request.
98 _state: dict[type, Any] = field(default_factory=dict, repr=False, init=False)
99 # End-token position for each key in this request. The scheduler records
100 # these positions so managers can recover prefix order even when store
101 # calls arrive out of order (for example, SWA backfills).
102 _offload_key_positions: dict[OffloadKey, int] = field(
103 default_factory=dict, repr=False, init=False
104 )
105
106 def set_state(self, val: Any) -> None:
107 self._state[type(val)] = val
108
109 def get_state(self, cls: type[_T]) -> _T | None:
110 return self._state.get(cls)
111
112 def set_offload_key_position(self, key: OffloadKey, end_token: int) -> None:
113 self._offload_key_positions[key] = end_token
114
115 def get_offload_key_position(self, key: OffloadKey) -> int | None:
116 return self._offload_key_positions.get(key)
117
118
119 class LookupResult(Enum):
120 """Result of OffloadingManager.lookup()."""
121
122 MISS = auto()
123 HIT = auto()
124 HIT_PENDING = auto()
125 RETRY = auto()
126
127
128 class OffloadPolicy(Enum):
129 # Offload only newly-computed chunks as they arrive; prefix-hit
130 # chunks (already offloaded by a prior request) are skipped.
131 CHUNK_LEVEL = "chunk_level"
132 # Offload all chunks for the request, including prefix hits.
133 # Used by tiers that need the complete KV context for a request.
134 REQUEST_LEVEL = "request_level"
135
136
137 @dataclass
138 class RequestOffloadingContext:
139 policy: OffloadPolicy = OffloadPolicy.CHUNK_LEVEL
140
141
142 class ScheduleEndContext(NamedTuple):
143 """Per-step scheduling info passed to on_schedule_end()."""
144
145 # Request IDs scheduled for the first time this step.
146 new_req_ids: Collection[str]
147 # Request IDs preempted this step.
148 preempted_req_ids: Collection[str]
149
150
151 class LoadStoreSpec:
152 """Metadata that encapsulates information allowing a worker
153 to load, and optionally also to store, blocks of KV data.
154 """
155
156
157 @dataclass
158 class PrepareStoreOutput:
159 keys_to_store: list[OffloadKey]
160 store_spec: LoadStoreSpec
161 evicted_keys: list[OffloadKey]
162
163
164 @dataclass
165 class OffloadingEvent:
166 keys: list[OffloadKey]
167 medium: Medium
168 # True if blocks are removed, False if stored
169 removed: bool
170 locality: Locality | None = None
171 # Secondary tier identifier that generated the event, or None for primary.
172 ownership: str | None = None
173 removal_expected: bool = False
174
175
176 """
177 OffloadingManager class for managing KV data offloading in vLLM v1
178
179 This class runs in the scheduler, tracks which blocks are offloaded
180 and their address.
181
182 The class provides the following primitives:
183 lookup() - check whether a single block is offloaded and ready.
184 prepare_load() - prepare given blocks to be read.
185 The given blocks will be protected from eviction.
186 This function returns a LoadSpec which encapsulates
187 information required for performing the load.
188 touch() - marks the give blocks as recently used. Can be used
189 to track block's LRU. This function is separated from the
190 prepare_load function to allow setting block recency even
191 for blocks which do not need reading from the cache, such as
192 blocks that are cached by the GPU prefix cache.
193 complete_load() - mark blocks which were previously prepared to be
194 loaded as done loading. This is to re-allow their eviction.
195 prepare_store() - prepare the given blocks to be written.
196 Returns a StoreSpec encapsulating offloading information,
197 as well as a list of blocks that were evicted as a result.
198 complete_store() - marks a previous store as completed.
199 Following this call, the given blocks will become loadable.
200 """
201
202
203 @dataclass(frozen=True)
204 class OffloadingMetricMetadata:
205 documentation: str
206 labelnames: tuple[str, ...] = ()
207
208
209 @dataclass(frozen=True)
210 class OffloadingCounterMetadata(OffloadingMetricMetadata):
211 pass
212
213
214 @dataclass(frozen=True)
215 class OffloadingGaugeMetadata(OffloadingMetricMetadata):
216 pass
217
218
219 @dataclass(frozen=True)
220 class OffloadingHistogramMetadata(OffloadingMetricMetadata):
221 buckets: tuple[float, ...] | None = None
222
223
224 @dataclass(frozen=True)
225 class OffloadingKVEventsConfig:
226 # Global vLLM KV event publishing flag. When false, connector-specific
227 # event capture must stay inert because take_events() is not drained.
228 enable_kv_cache_events: bool
229 # OffloadingConnector opt-in for self-describing BlockStored payloads.
230 # Effective only when enable_kv_cache_events is true.
231 self_describing_kv_events: bool
232
233
234 class OffloadingManager(ABC):
235 @abstractmethod
236 def lookup(self, key: OffloadKey, req_context: ReqContext) -> LookupResult:
237 """Checks whether a single block is offloaded and ready to be read.
238
239 Args:
240 key: the key identifying the block to lookup.
241 req_context: per-request context (e.g. kv_transfer_params).
242
243 Returns:
244 HIT if the block is offloaded and ready, MISS if not found,
245 HIT_PENDING if found but not yet readable, or RETRY if the
246 lookup should be retried later.
247
248 """
249 pass
250
251 @abstractmethod
252 def prepare_load(
253 self,
254 keys: Collection[OffloadKey],
255 req_context: ReqContext,
256 ) -> LoadStoreSpec:
257 """Prepare the given blocks to be read.
258 The given blocks will be protected from eviction until
259 complete_load is called.
260 It assumes all given blocks are offloaded.
261
262 Args:
263 keys: the keys identifying the blocks.
264 req_context: per-request context (e.g. kv_transfer_params).
265
266 Returns:
267 A LoadStoreSpec that can be used by a worker to locate and load
268 the actual offloaded KV data.
269
270 """
271 pass
272
273 def touch(self, keys: Collection[OffloadKey], req_context: ReqContext):
274 """Mark the given blocks as recently used.
275 This could in practice mean moving them to the end of an LRU list.
276
277 Args:
278 keys: the keys identifying the blocks.
279 req_context: per-request context (e.g. kv_transfer_params).
280
281 """
282 return
283
284 def complete_load(self, keys: Collection[OffloadKey], req_context: ReqContext):
285 """Marks previous blocks that were prepared to load as done loading.
286
287 Args:
288 keys: the keys identifying the blocks.
289 req_context: per-request context (e.g. kv_transfer_params).
290
291 """
292 return
293
294 @abstractmethod
295 def prepare_store(
296 self,
297 keys: Collection[OffloadKey],
298 req_context: ReqContext,
299 ) -> PrepareStoreOutput | None:
300 """Prepare the given blocks to be offloaded.
301 The given blocks will be protected from eviction until
302 complete_store is called.
303
304 Args:
305 keys: the keys identifying the blocks.
306 req_context: per-request context (e.g. kv_transfer_params).
307
308 Returns:
309 A PrepareStoreOutput indicating which blocks need storing,
310 where to store them (LoadStoreSpec), and list of blocks that
311 were evicted as a result.
312 None is returned if the blocks cannot be stored.
313
314 """
315 pass
316
317 def complete_store(
318 self,
319 keys: Collection[OffloadKey],
320 req_context: ReqContext,
321 success: bool = True,
322 ):
323 """Marks blocks which were previously prepared to be stored, as stored.
324 Following this call, the blocks become loadable.
325 If success is False, blocks that were not marked as stored will be
326 removed.
327
328 Args:
329 keys: the keys identifying the blocks.
330 req_context: per-request context (e.g. kv_transfer_params).
331 success: whether the blocks were stored successfully.
332
333 """
334 return
335
336 @abstractmethod
337 def on_new_request(self, req_context: ReqContext) -> RequestOffloadingContext:
338 """Called when a new request is first seen by the scheduler.
339
340 Returns a RequestOffloadingContext indicating how this request's
341 blocks should be offloaded.
342
343 Args:
344 req_context: per-request context.
345
346 """
347 pass
348
349 def on_request_finished(self, req_context: ReqContext) -> None:
350 """Called when a request has finished.
351
352 By the time this is called, the scheduler will issue no more
353 submit-side calls for this request, such as prepare_store() and
354 prepare_load(). Completion callbacks for already-submitted transfers
355 (complete_store() and complete_load()) may still arrive afterward.
356
357 This hook does NOT imply the data has been persisted. Asynchronous
358 transfers already submitted for this request may still be in flight.
359 Managers that cascade to lower tiers should delay those tiers'
360 on_request_finished() calls until no more lower-tier submit calls can
361 be issued for this request.
362
363 Args:
364 req_context: per-request context.
365
366 """
367 return
368
369 def take_events(self) -> Iterable[OffloadingEvent]:
370 """Take the offloading events from the manager.
371
372 A tier manager emits only events for storage state it owns. A
373 composing manager may aggregate child event streams, but should not
374 synthesize events on behalf of a child tier.
375
376 Yields:
377 New OffloadingEvents collected since the last call.
378
379 """
380 return ()
381
382 def on_schedule_end(self, context: ScheduleEndContext) -> None:
383 """Called once at the end of each scheduler step.
384
385 Managers may override this to flush deferred work accumulated
386 during the step (e.g., batched promotions).
387 """
388 return
389
390 def has_pending_work(self) -> bool:
391 """Whether this manager needs the engine to keep stepping.
392
393 While True, on_schedule_end() and get_finished_jobs() continue
394 to be called even when no requests are scheduled.
395 """
396 return False
397
398 def reset_cache(self) -> None:
399 """Evict all tracked blocks and reset internal state."""
400 return
401
402 def get_stats(self) -> "OffloadingConnectorStats | None":
403 """Return collected metrics since last call, or None if disabled."""
404 return None
405
406 def shutdown(self) -> None:
407 """Shutdown the manager and release any resources."""
408 return
409
410
411 class BlockIDsLoadStoreSpec(LoadStoreSpec, ABC):
412 """Spec for loading/storing KV blocks from given block numbers.
413
414 Subclass semantics differ: GPULoadStoreSpec.block_ids are GPU block
415 indices; CPULoadStoreSpec.block_ids are CPU cache chunk indices.
416 """
417
418 def __init__(self, block_ids: list[int]):
419 self.block_ids = np.array(block_ids, dtype=np.int32)
420
421 def __repr__(self) -> str:
422 return repr(self.block_ids)
423
424
425 class GPULoadStoreSpec(BlockIDsLoadStoreSpec):
426 """Spec for loading/storing a KV block to GPU memory.
427
428 If there are multiple KV groups, the blocks are expected to be
429 ordered by the group index.
430 In that case, group_sizes[i] determines the number of blocks
431 per the i-th KV group, and thus sum(group_sizes) == len(block_ids).
432 group_sizes=None indicates a single KV group.
433
434 If block_indices is given, each group (determined by group_sizes) of block IDs
435 will correspond to logically contiguous blocks, e.g. blocks 5-10 of a some request.
436 block_indices[i] will represent the block index of the first block in group #i.
437 Thus, len(block_indices) == len(group_sizes) = number of KV cache groups.
438 This information is required in order to support off/loading from offloaded blocks
439 which are larger than GPU blocks.
440 In such cases, the first GPU block per each group may be unaligned to the offloaded
441 block size, and so knowing block_indices[i] allows the worker to correctly
442 skip part of the first matching offloaded block.
443 """
444
445 def __init__(
446 self,
447 block_ids: list[int],
448 group_sizes: Sequence[int],
449 block_indices: Sequence[int],
450 ):
451 super().__init__(block_ids)
452 assert sum(group_sizes) == len(block_ids)
453 assert len(block_indices) == len(group_sizes)
454 self.group_sizes: Sequence[int] = group_sizes
455 self.block_indices: Sequence[int] = block_indices
456
457
458 @dataclass
459 class CanonicalKVCacheTensor:
460 """A canonicalized KV cache tensor whose first dimension is num_blocks.
461
462 With standardized layouts (RFC #42082) num_blocks is always the leading
463 logical dimension.
464 """
465
466 # The KV cache tensor with shape (num_blocks, ...)
467 tensor: torch.Tensor
468 # The (possibly padded) page size per block in bytes
469 page_size_bytes: int
470
471
472 @dataclass(frozen=True)
473 class CopyRun:
474 """A strided byte correspondence between this worker's physical page and
475 a canonical page: for i in range(num_fragments), fragment i spans
476 [local_offset + i * local_stride, +fragment_size) in the worker's page and
477 [canonical_offset + i * canonical_stride, +fragment_size) canonically."""
478
479 local_offset: int
480 canonical_offset: int
481 fragment_size: int
482 num_fragments: int
483 local_stride: int
484 canonical_stride: int
485
486
487 @dataclass(frozen=True)
488 class CanonicalPageMapping:
489 """How this worker's page maps into a canonical (parallelism-free) page.
490 In-process only, never serialized. Runs cover the full local page in both
491 directions; ranks holding identical bytes take turns writing them.
492 """
493
494 # Size of the canonical page in bytes
495 canonical_page_size_bytes: int
496 # Size of this worker's (un-padded) page in bytes
497 local_page_size_bytes: int
498 # Byte correspondences between this worker's page and a canonical page
499 runs: tuple[CopyRun, ...]
500 # Number of ranks holding these exact bytes
501 num_writers: int
502 # This worker's index among those ranks
503 writer_index: int
504 # Canonical bytes identical under any parallel config with this block span
505 parallelism_agnostic: bool
506
507 def is_writer(self, block_id: int) -> bool:
508 """Whether this worker stores the canonical page of the given block.
509 Rotating by block spreads writes across ranks holding identical bytes.
510 """
511 return block_id % self.num_writers == self.writer_index
512
513
514 @dataclass
515 class CanonicalKVCacheRef:
516 """Per-layer (or group of layers) reference to a specific (by index)
517 CanonicalKVCacheTensor and records the un-padded page size used by that layer.
518 """
519
520 # Index into the list of CanonicalKVCacheTensor objects
521 tensor_idx: int
522 # The un-padded page size per block in bytes
523 page_size_bytes: int
524 # How this worker's page maps into a canonical page; None = uncertified
525 mapping: CanonicalPageMapping | None = None
526
527
528 @dataclass
529 class CanonicalKVCaches:
530 """Canonicalized block-level representation of the KV caches.
531
532 Composed of:
533 - Unique list of KV cache data tensors,
534 each with shape (num_blocks, page_size_in_bytes) and int8 dtype.
535 - Per-group data references of the tensors.
536 i.e. how each KV cache group maps to the tensors.
537 """
538
539 # Ordered list of unique block tensors, each with shape
540 # (num_blocks, ...).
541 tensors: list[CanonicalKVCacheTensor]
542 # Per-KV-cache-group list of data references that map each layer
543 # in the group to the appropriate entry in the tensors list.
544 group_data_refs: list[list[CanonicalKVCacheRef]]
545
546
547 @dataclass
548 class TransferResult:
549 job_id: int
550 success: bool
551 transfer_size: int | None = None
552 transfer_time: float | None = None
553
554
555 class OffloadingWorker(ABC):
556 """Runs in the worker process. Performs async KV transfers for ONE
557 offloaded medium (e.g. CPU). Direction is explicit via submit_store /
558 submit_load, so there is no (src_medium, dst_medium) routing."""
559
560 @abstractmethod
561 def submit_store(
562 self, job_id: int, src_spec: GPULoadStoreSpec, dst_spec: LoadStoreSpec
563 ) -> bool:
564 """Async GPU -> offloaded medium."""
565
566 @abstractmethod
567 def submit_load(
568 self, job_id: int, src_spec: LoadStoreSpec, dst_spec: GPULoadStoreSpec
569 ) -> bool:
570 """Async offloaded medium -> GPU."""
571
572 @abstractmethod
573 def get_finished(self) -> list[TransferResult]: ...
574
575 @abstractmethod
576 def wait(self, job_ids: set[int]) -> None: ...
577
578 def shutdown(self) -> None:
579 return
580
581
582 class OffloadingSpec(ABC):
583 """Spec for an offloading connector"""
584
585 @classmethod
586 def build_metric_definitions(
587 cls, extra_config: dict[str, Any]
588 ) -> dict[str, "OffloadingMetricMetadata"]:
589 """Return Prometheus metric definitions emitted by this spec."""
590 return {}
591
592 def __init__(self, config: OffloadingConfig):
593 self.config = config
594 self.extra_config = config.extra_config
595 self.replicated_layout: bool = False
596 self.kv_events_config = OffloadingKVEventsConfig(
597 enable_kv_cache_events=config.enable_kv_cache_events,
598 self_describing_kv_events=bool(
599 self.extra_config.get("self_describing_kv_events", False)
600 ),
601 )
602
603 # When True, only prompt (prefill) blocks are offloaded; decode-phase
604 # blocks (KV generated after the prompt) are skipped. Useful when prior
605 # turns' generated tokens are dropped before the next turn (e.g.
606 # reasoning models that strip thinking).
607 self.offload_prompt_only: bool = bool(
608 self.extra_config.get("offload_prompt_only", True)
609 )
610
611 self.tokens_per_block = tuple(group.tokens_per_block for group in config.groups)
612 self.tokens_per_hash = config.cache.tokens_per_hash
613 self.blocks_per_chunk = config.cache.blocks_per_chunk
614
615 @abstractmethod
616 def get_manager(self) -> OffloadingManager:
617 """Get an OffloadingManager that will be used
618 by the scheduler-side offloading connector to track
619 offloaded blocks and manage evictions.
620 """
621 pass
622
623 @abstractmethod
624 def get_worker(self, kv_caches: CanonicalKVCaches) -> OffloadingWorker:
625 """Get an OffloadingWorker that handles async KV transfers for this spec.
626
627 Args:
628 kv_caches: Canonicalized KV caches.
629
630 Returns:
631 An OffloadingWorker instance for this medium.
632
633 """
634 pass