| 1 | # SPDX-License-Identifier: Apache-2.0 |
| 2 | # SPDX-FileCopyrightText: Copyright contributors to the vLLM project |
| 3 | """Scheduler-owned lifecycle and indexes for Consumer-bound transfers.""" |
| 4 | |
| 5 | from __future__ import annotations |
| 6 | |
| 7 | from collections import OrderedDict, deque |
| 8 | from collections.abc import Iterable |
| 9 | from dataclasses import dataclass, field, replace |
| 10 | from enum import Enum, auto |
| 11 | |
| 12 | from vllm.distributed.ec_transfer.ec_connector.mooncake.metadata import ( |
| 13 | ECMooncakeLoadSpec, |
| 14 | ) |
| 15 | from vllm.logger import init_logger |
| 16 | |
| 17 | logger = init_logger(__name__) |
| 18 | |
| 19 | |
| 20 | class SchedulerTransferState(Enum): |
| 21 | """Lifecycle states visible to the Scheduler. |
| 22 | |
| 23 | The states cover waiting for a Consumer event, dispatching a Worker load, |
| 24 | retaining a locally reusable tensor, and terminal failure conditions. |
| 25 | """ |
| 26 | |
| 27 | WAITING_EVENT = auto() |
| 28 | AVAILABLE = auto() |
| 29 | LOADING = auto() |
| 30 | READY = auto() |
| 31 | RESIDENT = auto() |
| 32 | UNAVAILABLE = auto() |
| 33 | EXPIRED = auto() |
| 34 | FAILED = auto() |
| 35 | CANCELLED = auto() |
| 36 | |
| 37 | |
| 38 | @dataclass |
| 39 | class SchedulerTransfer: |
| 40 | """Track one transfer as observed by the Scheduler.""" |
| 41 | |
| 42 | transfer_id: str |
| 43 | request_id: str |
| 44 | mm_hash: str |
| 45 | state: SchedulerTransferState |
| 46 | spec: ECMooncakeLoadSpec | None |
| 47 | deadline: float | None |
| 48 | notified_requests: set[str] = field(default_factory=set, repr=False) |
| 49 | |
| 50 | |
| 51 | _TERMINAL_STATES = { |
| 52 | SchedulerTransferState.UNAVAILABLE, |
| 53 | SchedulerTransferState.EXPIRED, |
| 54 | SchedulerTransferState.FAILED, |
| 55 | SchedulerTransferState.CANCELLED, |
| 56 | } |
| 57 | |
| 58 | |
| 59 | class SchedulerTransferTable: |
| 60 | """Own Scheduler transfer state, lookup indexes, and dispatch queues. |
| 61 | |
| 62 | The Scheduler is single-threaded, so direct transitions are sufficient; |
| 63 | the Producer and Consumer managers retain stricter transition matrices |
| 64 | because callbacks and control requests can race there. |
| 65 | """ |
| 66 | |
| 67 | def __init__(self, resident_capacity: int, tombstone_ttl: float) -> None: |
| 68 | self._resident_capacity = resident_capacity |
| 69 | self._tombstone_ttl = tombstone_ttl |
| 70 | self._records: OrderedDict[str, SchedulerTransfer] = OrderedDict() |
| 71 | self._active_ids: dict[str, None] = {} |
| 72 | self._terminal_ids: OrderedDict[str, None] = OrderedDict() |
| 73 | self._resident_ids: OrderedDict[str, None] = OrderedDict() |
| 74 | self._resident_bytes = 0 |
| 75 | self._hash_index: dict[str, deque[str]] = {} |
| 76 | self._loads_to_dispatch: OrderedDict[str, None] = OrderedDict() |
| 77 | self._unavailable_requests: set[str] = set() |
| 78 | # Records expired straight out of READY/RESIDENT: the consumer worker |
| 79 | # still holds their push reservation, and nothing else tells it to let |
| 80 | # go, so the destination buffer would sit pinned until the lease TTL. |
| 81 | self._orphaned: list[str] = [] |
| 82 | |
| 83 | def get(self, transfer_id: str) -> SchedulerTransfer | None: |
| 84 | return self._records.get(transfer_id) |
| 85 | |
| 86 | def drain_orphaned(self) -> list[str]: |
| 87 | """Transfer IDs expired out of READY/RESIDENT since the last drain. |
| 88 | |
| 89 | The caller must release the consumer worker's reservation for each: |
| 90 | `cancel()` still accepts an EXPIRED record, so the usual cancel path |
| 91 | applies. |
| 92 | """ |
| 93 | orphaned = self._orphaned |
| 94 | self._orphaned = [] |
| 95 | return orphaned |
| 96 | |
| 97 | def records_for_hash( |
| 98 | self, |
| 99 | mm_hash: str, |
| 100 | states: Iterable[SchedulerTransferState], |
| 101 | ) -> list[SchedulerTransfer]: |
| 102 | wanted = set(states) |
| 103 | return [ |
| 104 | record |
| 105 | for transfer_id in self._hash_index.get(mm_hash, ()) |
| 106 | if (record := self._records.get(transfer_id)) is not None |
| 107 | and record.state in wanted |
| 108 | ] |
| 109 | |
| 110 | def first_for_hash( |
| 111 | self, |
| 112 | mm_hash: str, |
| 113 | states: Iterable[SchedulerTransferState], |
| 114 | ) -> SchedulerTransfer | None: |
| 115 | states = tuple(states) |
| 116 | if len(states) == 1: |
| 117 | wanted_state = states[0] |
| 118 | for transfer_id in self._hash_index.get(mm_hash, ()): |
| 119 | record = self._records.get(transfer_id) |
| 120 | if record is not None and record.state is wanted_state: |
| 121 | return record |
| 122 | return None |
| 123 | wanted_states = set(states) |
| 124 | for transfer_id in self._hash_index.get(mm_hash, ()): |
| 125 | record = self._records.get(transfer_id) |
| 126 | if record is not None and record.state in wanted_states: |
| 127 | return record |
| 128 | return None |
| 129 | |
| 130 | def has_state(self, mm_hash: str, states: Iterable[SchedulerTransferState]) -> bool: |
| 131 | return self.first_for_hash(mm_hash, states) is not None |
| 132 | |
| 133 | def wait_for_event( |
| 134 | self, |
| 135 | transfer_id: str, |
| 136 | request_id: str, |
| 137 | mm_hash: str, |
| 138 | deadline: float, |
| 139 | ) -> SchedulerTransfer | None: |
| 140 | """Track a request waiting for a push. |
| 141 | |
| 142 | Returns None when `transfer_id` already names a different encoding. |
| 143 | The id comes from the request, so a collision has to fail that one |
| 144 | request; re-issuing it re-runs the encode under a fresh id. |
| 145 | """ |
| 146 | record = self._records.get(transfer_id) |
| 147 | if record is None: |
| 148 | record = SchedulerTransfer( |
| 149 | transfer_id=transfer_id, |
| 150 | request_id=request_id, |
| 151 | mm_hash=mm_hash, |
| 152 | state=SchedulerTransferState.WAITING_EVENT, |
| 153 | spec=None, |
| 154 | deadline=deadline, |
| 155 | ) |
| 156 | self._insert(record) |
| 157 | elif not self._identity_matches(record, mm_hash): |
| 158 | self._refuse_colliding_id(record, mm_hash, request_id) |
| 159 | return None |
| 160 | else: |
| 161 | if not record.request_id: |
| 162 | record.request_id = request_id |
| 163 | if record.state in _TERMINAL_STATES and request_id: |
| 164 | self._notify_unavailable(record, request_id) |
| 165 | return record |
| 166 | |
| 167 | def observe_ready( |
| 168 | self, spec: ECMooncakeLoadSpec, deadline: float |
| 169 | ) -> tuple[SchedulerTransfer, bool]: |
| 170 | transfer_id = spec.transfer_id |
| 171 | record = self._records.get(transfer_id) |
| 172 | if record is None: |
| 173 | record = SchedulerTransfer( |
| 174 | transfer_id=transfer_id, |
| 175 | request_id="", |
| 176 | mm_hash=spec.mm_hash, |
| 177 | state=SchedulerTransferState.WAITING_EVENT, |
| 178 | spec=None, |
| 179 | deadline=None, |
| 180 | ) |
| 181 | self._insert(record) |
| 182 | elif not self._identity_matches(record, spec.mm_hash): |
| 183 | self._refuse_colliding_id(record, spec.mm_hash, record.request_id) |
| 184 | return record, False |
| 185 | if record.state is not SchedulerTransferState.WAITING_EVENT: |
| 186 | return record, False |
| 187 | record.spec = spec |
| 188 | record.deadline = deadline |
| 189 | self._transition(record, SchedulerTransferState.AVAILABLE) |
| 190 | return record, True |
| 191 | |
| 192 | def touch_available(self, transfer_id: str, deadline: float) -> None: |
| 193 | record = self._records.get(transfer_id) |
| 194 | if record is not None and record.state is SchedulerTransferState.AVAILABLE: |
| 195 | record.deadline = deadline |
| 196 | |
| 197 | def begin_load( |
| 198 | self, |
| 199 | mm_hash: str, |
| 200 | transfer_id: str | None = None, |
| 201 | request_id: str = "", |
| 202 | deadline: float | None = None, |
| 203 | ) -> SchedulerTransfer | None: |
| 204 | record = self._records.get(transfer_id) if transfer_id else None |
| 205 | if record is not None and ( |
| 206 | record.mm_hash != mm_hash |
| 207 | or record.state is not SchedulerTransferState.AVAILABLE |
| 208 | ): |
| 209 | record = None |
| 210 | if record is None: |
| 211 | record = self.first_for_hash( |
| 212 | mm_hash, |
| 213 | ( |
| 214 | SchedulerTransferState.AVAILABLE, |
| 215 | SchedulerTransferState.RESIDENT, |
| 216 | ), |
| 217 | ) |
| 218 | if record is None or record.spec is None: |
| 219 | return None |
| 220 | if not record.request_id: |
| 221 | record.request_id = request_id |
| 222 | # A dispatched load that never reports back would otherwise hold this |
| 223 | # hash in LOADING for good, deferring every later request for it. |
| 224 | record.deadline = deadline |
| 225 | self._transition(record, SchedulerTransferState.LOADING) |
| 226 | self._loads_to_dispatch[record.transfer_id] = None |
| 227 | return record |
| 228 | |
| 229 | def take_loads_to_dispatch(self) -> list[SchedulerTransfer]: |
| 230 | records = [ |
| 231 | record |
| 232 | for transfer_id in self._loads_to_dispatch |
| 233 | if (record := self._records.get(transfer_id)) is not None |
| 234 | and record.state is SchedulerTransferState.LOADING |
| 235 | ] |
| 236 | self._loads_to_dispatch.clear() |
| 237 | return records |
| 238 | |
| 239 | def complete_load(self, mm_hash: str) -> bool: |
| 240 | record = self.first_for_hash(mm_hash, (SchedulerTransferState.LOADING,)) |
| 241 | if record is None: |
| 242 | return self.has_state(mm_hash, (SchedulerTransferState.READY,)) |
| 243 | self._transition(record, SchedulerTransferState.READY) |
| 244 | return True |
| 245 | |
| 246 | def fail_load(self, mm_hash: str, now: float) -> bool: |
| 247 | record = self.first_for_hash(mm_hash, (SchedulerTransferState.LOADING,)) |
| 248 | if record is None: |
| 249 | return self.has_state(mm_hash, (SchedulerTransferState.FAILED,)) |
| 250 | self._transition(record, SchedulerTransferState.FAILED, now=now) |
| 251 | return True |
| 252 | |
| 253 | def release_ready(self, mm_hash: str, now: float) -> None: |
| 254 | ready = self.records_for_hash(mm_hash, (SchedulerTransferState.READY,)) |
| 255 | if ready: |
| 256 | canonical = ready[-1] |
| 257 | for record in self.records_for_hash( |
| 258 | mm_hash, |
| 259 | (SchedulerTransferState.READY, SchedulerTransferState.RESIDENT), |
| 260 | ): |
| 261 | if record is not canonical: |
| 262 | self._transition(record, SchedulerTransferState.EXPIRED, now=now) |
| 263 | if canonical.spec is None: |
| 264 | self._transition(canonical, SchedulerTransferState.EXPIRED, now=now) |
| 265 | else: |
| 266 | canonical.spec = replace(canonical.spec, local=True) |
| 267 | self._transition(canonical, SchedulerTransferState.RESIDENT) |
| 268 | self._evict_residents(now) |
| 269 | |
| 270 | def reclaim(self, mm_hash: str, now: float) -> None: |
| 271 | for record in self.records_for_hash( |
| 272 | mm_hash, |
| 273 | (SchedulerTransferState.READY, SchedulerTransferState.RESIDENT), |
| 274 | ): |
| 275 | if record.state is SchedulerTransferState.READY: |
| 276 | record.spec = None |
| 277 | else: |
| 278 | self._transition(record, SchedulerTransferState.EXPIRED, now=now) |
| 279 | |
| 280 | def mark_unavailable(self, transfer_id: str, now: float) -> None: |
| 281 | record = self._records[transfer_id] |
| 282 | self._transition(record, SchedulerTransferState.UNAVAILABLE, now=now) |
| 283 | if record.request_id: |
| 284 | self._notify_unavailable(record, record.request_id) |
| 285 | |
| 286 | def cancel( |
| 287 | self, |
| 288 | transfer_id: str, |
| 289 | now: float, |
| 290 | mm_hash: str = "", |
| 291 | request_id: str = "", |
| 292 | ) -> bool: |
| 293 | record = self._records.get(transfer_id) |
| 294 | if ( |
| 295 | record is not None |
| 296 | and mm_hash |
| 297 | and not self._identity_matches(record, mm_hash) |
| 298 | ): |
| 299 | return False |
| 300 | if record is None: |
| 301 | record = SchedulerTransfer( |
| 302 | transfer_id=transfer_id, |
| 303 | request_id=request_id, |
| 304 | mm_hash=mm_hash, |
| 305 | state=SchedulerTransferState.WAITING_EVENT, |
| 306 | spec=None, |
| 307 | deadline=None, |
| 308 | ) |
| 309 | self._insert(record) |
| 310 | if record.state in { |
| 311 | SchedulerTransferState.CANCELLED, |
| 312 | SchedulerTransferState.READY, |
| 313 | SchedulerTransferState.RESIDENT, |
| 314 | SchedulerTransferState.FAILED, |
| 315 | }: |
| 316 | return False |
| 317 | self._transition(record, SchedulerTransferState.CANCELLED, now=now) |
| 318 | self._loads_to_dispatch.pop(transfer_id, None) |
| 319 | return True |
| 320 | |
| 321 | def expire(self, now: float, terminal_limit: int) -> list[SchedulerTransfer]: |
| 322 | if terminal_limit < 0: |
| 323 | raise ValueError("terminal_limit must be non-negative") |
| 324 | expired = [] |
| 325 | for transfer_id in list(self._active_ids): |
| 326 | record = self._records[transfer_id] |
| 327 | if record.deadline is None or record.deadline > now: |
| 328 | continue |
| 329 | if record.state is SchedulerTransferState.AVAILABLE: |
| 330 | self._transition( |
| 331 | record, |
| 332 | SchedulerTransferState.EXPIRED, |
| 333 | now=now, |
| 334 | ) |
| 335 | expired.append(record) |
| 336 | elif record.state is SchedulerTransferState.LOADING: |
| 337 | self._transition( |
| 338 | record, |
| 339 | SchedulerTransferState.UNAVAILABLE, |
| 340 | now=now, |
| 341 | ) |
| 342 | if record.request_id: |
| 343 | self._notify_unavailable(record, record.request_id) |
| 344 | expired.append(record) |
| 345 | while self._terminal_ids: |
| 346 | transfer_id = next(iter(self._terminal_ids)) |
| 347 | record = self._records[transfer_id] |
| 348 | if ( |
| 349 | record.deadline is not None |
| 350 | and record.deadline > now |
| 351 | and len(self._terminal_ids) <= terminal_limit |
| 352 | ): |
| 353 | break |
| 354 | self._remove(transfer_id) |
| 355 | return expired |
| 356 | |
| 357 | def take_unavailable_requests(self) -> set[str]: |
| 358 | unavailable = self._unavailable_requests |
| 359 | self._unavailable_requests = set() |
| 360 | return unavailable |
| 361 | |
| 362 | def _notify_unavailable(self, record: SchedulerTransfer, request_id: str) -> None: |
| 363 | if request_id not in record.notified_requests: |
| 364 | record.notified_requests.add(request_id) |
| 365 | self._unavailable_requests.add(request_id) |
| 366 | |
| 367 | def _insert(self, record: SchedulerTransfer) -> None: |
| 368 | self._records[record.transfer_id] = record |
| 369 | self._active_ids[record.transfer_id] = None |
| 370 | if record.mm_hash: |
| 371 | self._hash_index.setdefault(record.mm_hash, deque()).append( |
| 372 | record.transfer_id |
| 373 | ) |
| 374 | |
| 375 | @staticmethod |
| 376 | def _identity_matches(record: SchedulerTransfer, mm_hash: str) -> bool: |
| 377 | return not record.mm_hash or record.mm_hash == mm_hash |
| 378 | |
| 379 | def _refuse_colliding_id( |
| 380 | self, record: SchedulerTransfer, mm_hash: str, request_id: str |
| 381 | ) -> None: |
| 382 | """Report a transfer id that already names another encoding. |
| 383 | |
| 384 | Transfer ids arrive on the request, so a collision is reachable from |
| 385 | outside and must not reach the engine as an exception. |
| 386 | """ |
| 387 | logger.warning( |
| 388 | "EC Mooncake transfer_id=%s already names mm_hash=%s; refusing " |
| 389 | "mm_hash=%s for request %s", |
| 390 | record.transfer_id, |
| 391 | record.mm_hash[:16], |
| 392 | mm_hash[:16], |
| 393 | request_id or "<unknown>", |
| 394 | ) |
| 395 | if request_id: |
| 396 | self._unavailable_requests.add(request_id) |
| 397 | |
| 398 | def _transition( |
| 399 | self, |
| 400 | record: SchedulerTransfer, |
| 401 | state: SchedulerTransferState, |
| 402 | now: float | None = None, |
| 403 | ) -> None: |
| 404 | if record.state is SchedulerTransferState.RESIDENT: |
| 405 | self._resident_ids.pop(record.transfer_id, None) |
| 406 | if record.spec is not None: |
| 407 | self._resident_bytes -= record.spec.nbytes |
| 408 | if state is SchedulerTransferState.RESIDENT: |
| 409 | self._resident_ids[record.transfer_id] = None |
| 410 | if record.spec is not None: |
| 411 | self._resident_bytes += record.spec.nbytes |
| 412 | if state in _TERMINAL_STATES: |
| 413 | if now is None: |
| 414 | raise ValueError("Terminal transition requires a timestamp") |
| 415 | # Keep a bounded tombstone so late events and repeat request IDs |
| 416 | # remain idempotent instead of reviving a finished transfer. |
| 417 | record.deadline = now + self._tombstone_ttl |
| 418 | self._active_ids.pop(record.transfer_id, None) |
| 419 | self._terminal_ids[record.transfer_id] = None |
| 420 | self._terminal_ids.move_to_end(record.transfer_id) |
| 421 | if state is SchedulerTransferState.EXPIRED and record.state in ( |
| 422 | SchedulerTransferState.READY, |
| 423 | SchedulerTransferState.RESIDENT, |
| 424 | ): |
| 425 | self._orphaned.append(record.transfer_id) |
| 426 | record.state = state |
| 427 | self._records.move_to_end(record.transfer_id) |
| 428 | |
| 429 | def _evict_residents(self, now: float) -> None: |
| 430 | while self._resident_bytes > self._resident_capacity and self._resident_ids: |
| 431 | record = self._records[next(iter(self._resident_ids))] |
| 432 | self._transition(record, SchedulerTransferState.EXPIRED, now=now) |
| 433 | |
| 434 | def _remove(self, transfer_id: str) -> None: |
| 435 | record = self._records.pop(transfer_id, None) |
| 436 | self._active_ids.pop(transfer_id, None) |
| 437 | self._terminal_ids.pop(transfer_id, None) |
| 438 | if transfer_id in self._resident_ids: |
| 439 | self._resident_ids.pop(transfer_id) |
| 440 | if record is not None and record.spec is not None: |
| 441 | self._resident_bytes -= record.spec.nbytes |
| 442 | self._loads_to_dispatch.pop(transfer_id, None) |
| 443 | if record is None or not record.mm_hash: |
| 444 | return |
| 445 | transfer_ids = self._hash_index[record.mm_hash] |
| 446 | transfer_ids.remove(transfer_id) |
| 447 | if not transfer_ids: |
| 448 | self._hash_index.pop(record.mm_hash) |