mirror of
https://github.com/FlashML-org/FreeToken.git
synced 2026-11-21 01:52:30 +08:00
456 lines
23 KiB
Python
456 lines
23 KiB
Python
"""SWA (sliding-window-attention) radix cache.
|
|
|
|
A SEPARATE class from ``RadixPrefixCache`` (like ``HybridRadixCache`` for GDN) that REUSES the
|
|
shared ``RadixTreeNode`` + walk/split. Strictly mirrors sglang ``SWARadixCache``.
|
|
|
|
The second "currency" is NOT a stored slot: ``node.value`` (full-pool page indices) is canonical
|
|
and radix-shared; the swa KV for those tokens lives in the smaller swa pool reached via the pool's
|
|
``full_to_swa`` mapping and is freed independently as tokens slide out of the window -> the node is
|
|
marked ``swa_tombstone`` (full KV survives). A matched prefix is reusable for SWA layers only up to
|
|
the deepest node with ``>= sliding_window`` contiguous live (non-tombstone) tokens back to the last
|
|
tombstone, or tombstone-free to root (sglang ``_match_prefix_helper``).
|
|
|
|
Two-tier lock (``full_ref >= swa_ref``): full pins node..root; swa pins only the trailing window,
|
|
bounded by ``swa_uuid``. Two-tier eviction: full pass = unlocked leaf LRU (frees both pools); swa
|
|
pass = unlocked node LRU incl. internal -> tombstone in place (free swa only).
|
|
|
|
LRU: FreeToken heapq + timestamp, but ``match_prefix`` stamps the matched path with strictly
|
|
DECREASING timestamps toward root (sglang ``_match_post_processor``) so the heap evicts near-root
|
|
SWA nodes first -- the same victim order as sglang's maintained LRUList.
|
|
"""
|
|
from __future__ import annotations
|
|
|
|
import heapq
|
|
from dataclasses import dataclass
|
|
from typing import List, NamedTuple, Optional, Tuple
|
|
|
|
import torch
|
|
|
|
from freetoken.utils import align_down
|
|
|
|
from .base import BaseCacheHandle
|
|
from .radix_cache import RadixTreeNode, _get_key_fn
|
|
|
|
|
|
@dataclass(frozen=True)
|
|
class SWACacheHandle(BaseCacheHandle):
|
|
"""Lock handle for a matched SWA prefix: the windowed-safe matched node (lock target) + the
|
|
reusable full-pool KV page indices. ``swa_uuid`` is the window-boundary returned by
|
|
``inc_lock``; ``CacheManager.lock`` records it on the handle (via object.__setattr__ -- the
|
|
base handle is a frozen dataclass) and ``unlock``/``dec_lock`` consume it."""
|
|
|
|
node: RadixTreeNode
|
|
kv_indices: torch.Tensor
|
|
swa_uuid: Optional[int] = None
|
|
|
|
def get_matched_indices(self) -> torch.Tensor:
|
|
return self.kv_indices
|
|
|
|
# A logical-clock event id is multiplied by this so a single match/insert event leaves room to
|
|
# encode per-node depth offsets below it (decreasing toward root) without colliding with the next
|
|
# event. Bounds the max radix path depth -- 2^24 nodes is far beyond any real prefix.
|
|
_EVENT_STRIDE = 1 << 24
|
|
|
|
|
|
class SWAMatch(NamedTuple):
|
|
kv_indices: torch.Tensor # reused full-pool KV page indices for [0:cached_len) (windowed-safe)
|
|
cached_len: int # truncated to the windowed-reuse boundary
|
|
node: RadixTreeNode # the matched windowed-safe node (lock target)
|
|
|
|
|
|
class SWAEvictResult(NamedTuple):
|
|
kv_indices: torch.Tensor # full-pool page indices removed from the tree (-> free_slots)
|
|
swa_indices: torch.Tensor # full-pool indices whose swa slots to free_swa (tombstoned + removed)
|
|
|
|
|
|
class SWARadixCache:
|
|
def __init__(self, device: torch.device, page_size: int, sliding_window_size: int) -> None:
|
|
assert sliding_window_size > 0, "SWARadixCache requires a positive sliding window"
|
|
self.device = device
|
|
self.page_size = page_size
|
|
self.sliding_window_size = sliding_window_size
|
|
self.key_fn = _get_key_fn(page_size)
|
|
# Page-index dtype: matches the engine's int32 page_table / free_slots so an empty result
|
|
# (returned by insert/evict/match) never promotes them to int64 when concatenated.
|
|
self.empty = torch.empty(0, dtype=torch.int32, device=device)
|
|
self.root = RadixTreeNode(self.key_fn)
|
|
self.root.set_key_value(self.empty, self.empty)
|
|
self.root.ref_count = 1 # root is always protected
|
|
self.full_evictable = 0
|
|
self.full_protected = 0
|
|
self.swa_evictable = 0 # tokens of live (non-tombstone), unlocked swa
|
|
self.swa_protected = 0
|
|
self._clk = 0 # logical access clock (tie-free, for near-root-first order)
|
|
self._uuid = 0 # monotonic swa window-boundary handle counter
|
|
self._revives = 0 # observability: # of insert-side tombstone revives (Branches 1/2)
|
|
|
|
# ---------------------------------------------------------------- match / insert
|
|
def match_prefix(self, input_ids: torch.Tensor) -> SWAMatch:
|
|
"""Match the token prefix for the full layers, then truncate the reusable length to the
|
|
windowed-reuse boundary for the swa layers: the deepest node whose run of contiguous live
|
|
(non-tombstone) tokens back to the last tombstone is ``>= sliding_window_size`` (or the
|
|
path is tombstone-free to root). Mirrors sglang ``_match_prefix_helper``."""
|
|
node = self.root
|
|
value: List[torch.Tensor] = []
|
|
# path connected to root without a tombstone is always reusable -> start at +inf.
|
|
match_since_tomb = float("inf")
|
|
best_value_len = 0 # number of leading entries of ``value`` that are windowed-safe
|
|
best_node = self.root
|
|
prefix_pos, total = 0, len(input_ids)
|
|
|
|
while prefix_pos < total:
|
|
child = node.children.get(self.key_fn(input_ids[prefix_pos:]))
|
|
if child is None:
|
|
break
|
|
if child.swa_tombstone:
|
|
# commit the windowed-safe boundary at the PARENT (before this tombstone) if the
|
|
# live run leading up to it already covers the window; then reset the run.
|
|
if match_since_tomb >= self.sliding_window_size:
|
|
best_value_len = len(value)
|
|
best_node = node
|
|
match_since_tomb = 0
|
|
match_len = align_down(child.get_match_len(input_ids[prefix_pos:]), self.page_size)
|
|
if match_len == 0:
|
|
break
|
|
if match_len < child.length:
|
|
child = child.split_at(match_len) # child := the matched prefix segment
|
|
value.append(child.value)
|
|
if not child.swa_tombstone:
|
|
match_since_tomb += child.length
|
|
node = child
|
|
prefix_pos += match_len
|
|
break
|
|
value.append(child.value)
|
|
if not child.swa_tombstone:
|
|
match_since_tomb += child.length
|
|
node = child
|
|
prefix_pos += match_len
|
|
|
|
if match_since_tomb >= self.sliding_window_size:
|
|
best_value_len = len(value)
|
|
best_node = node
|
|
|
|
self._stamp_path(best_node)
|
|
kv = torch.cat(value[:best_value_len]) if best_value_len else self.empty
|
|
return SWAMatch(kv, int(kv.numel()), best_node)
|
|
|
|
def insert(self, input_ids: torch.Tensor, kv_indices: torch.Tensor,
|
|
swa_evicted_seqlen: int = 0, update_kv_after_len: int = 0
|
|
) -> Tuple[int, torch.Tensor]:
|
|
"""Insert the committed full KV prefix. ``kv_indices`` are the request's full-pool page
|
|
indices (the swa rides along via the full->swa mapping, live where the request allocated
|
|
it). Two frontiers drive the sglang ``_insert_helper`` reconcile:
|
|
|
|
- ``update_kv_after_len`` (= the request's old reused-prefix length): only nodes extending
|
|
PAST it carry the request's freshly-(re)computed live-swa indices. Nodes entirely within
|
|
it are tree-shared slots and are left untouched.
|
|
- ``swa_evicted_seqlen`` (= positions whose swa the request itself freed during decode):
|
|
below it the request's swa is the sentinel; at/above it it is live.
|
|
|
|
A matched node that is ``swa_tombstone`` (swa freed by an earlier ``evict_swa``) and extends
|
|
into the fresh region is REVIVED -- not by rewriting the mapping but by adopting the
|
|
request's live-swa indices into ``node.value`` and clearing the tombstone (sglang Branches
|
|
1/2/3). Tokens of the new suffix before ``swa_evicted_seqlen`` are inserted as a tombstone;
|
|
a live (non-tombstone) leaf is always added (the free_swa ``-page_size`` margin guarantees a
|
|
live tail). Returns ``(matched_prefix_len, freed_full_indices)``: the full-pool slots the
|
|
caller must return to BOTH pools (displaced old tree slots + non-adopted request dups;
|
|
``free_swa`` is idempotent on the already-sentinel ones)."""
|
|
insert_len = align_down(len(input_ids), self.page_size)
|
|
input_ids, kv_indices = input_ids[:insert_len], kv_indices[:insert_len]
|
|
freed: List[torch.Tensor] = []
|
|
node = self.root
|
|
total = 0
|
|
while total < insert_len:
|
|
child = node.children.get(self.key_fn(input_ids[total:]))
|
|
if child is None:
|
|
break
|
|
match_len = align_down(child.get_match_len(input_ids[total:]), self.page_size)
|
|
if match_len == 0:
|
|
break
|
|
partial = match_len < child.length
|
|
if partial:
|
|
child = child.split_at(match_len)
|
|
seg_kv = kv_indices[total:total + match_len] # request's fresh slots for this span
|
|
if update_kv_after_len < total + match_len:
|
|
if child.swa_tombstone:
|
|
assert child.swa_ref_count == 0, "a tombstoned node cannot hold a swa lock"
|
|
if child.ref_count > 0:
|
|
# A full-locked reader still gathers the node's CURRENT slots through its
|
|
# own row; freeing them on revive would hand live KV to the next alloc.
|
|
# Keep the tombstone + the tree's value, drop the request's dup (Branch 3
|
|
# shape) -- the window simply stays unrevived until the lock clears.
|
|
freed.append(seg_kv.clone())
|
|
elif swa_evicted_seqlen <= total:
|
|
# Branch 1: the node's swa is live in the request -> revive it whole. Free
|
|
# the old (sentinel-mapped) tree slots; adopt the request's live-swa slots.
|
|
freed.append(child.value)
|
|
child.set_key_value(child._key, seg_kv.clone())
|
|
child.swa_tombstone = False
|
|
child.timestamp = self._tick()
|
|
self.swa_evictable += child.length
|
|
self._revives += 1
|
|
elif swa_evicted_seqlen < total + match_len:
|
|
# Branch 2: the request's freed-swa frontier falls inside the node. Split;
|
|
# the head [:start] stays tombstone (full KV kept), revive the live tail.
|
|
start = swa_evicted_seqlen - total
|
|
child.split_at(start) # head=[:start] tombstone; child=tail[start:]
|
|
freed.append(child.value) # tail's old (sentinel) tree slots
|
|
freed.append(seg_kv[:start].clone()) # dup for the still-tombstone head
|
|
child.set_key_value(child._key, seg_kv[start:].clone())
|
|
child.swa_tombstone = False
|
|
child.timestamp = self._tick()
|
|
self.swa_evictable += child.length
|
|
self._revives += 1
|
|
else:
|
|
# Branch 3: node still wholly out-of-window -> keep tombstone, drop the dup.
|
|
freed.append(seg_kv.clone())
|
|
else:
|
|
# Matched a live node -> tree slots are canonical; drop the request's dup.
|
|
freed.append(seg_kv.clone())
|
|
total += match_len
|
|
node = child
|
|
if partial:
|
|
break
|
|
# Suffix: tokens [total:insert_len) not yet in the tree. Tombstone [total, swa_evicted_seqlen),
|
|
# then a live (non-tombstone) leaf for the in-window remainder (never a tombstone leaf --
|
|
# the clamp + the free_swa -page_size margin guarantee a live tail).
|
|
if total < insert_len:
|
|
# Both suffix nodes can share this copy without retaining the request buffer.
|
|
suffix_ids = input_ids[total:].clone()
|
|
suffix_kv = kv_indices[total:].clone()
|
|
boundary = max(0, min(swa_evicted_seqlen, insert_len) - total)
|
|
boundary = min(boundary, max(0, len(suffix_ids) - self.page_size))
|
|
if boundary > 0:
|
|
node = self._add_child(node, suffix_ids[:boundary], suffix_kv[:boundary],
|
|
tombstone=True)
|
|
suffix_ids, suffix_kv = suffix_ids[boundary:], suffix_kv[boundary:]
|
|
if len(suffix_ids):
|
|
self._add_child(node, suffix_ids, suffix_kv, tombstone=False)
|
|
return total, (torch.cat(freed) if freed else self.empty)
|
|
|
|
def _add_child(self, parent: RadixTreeNode, ids: torch.Tensor, kv: torch.Tensor,
|
|
*, tombstone: bool) -> RadixTreeNode:
|
|
child = RadixTreeNode(self.key_fn, self._tick())
|
|
child.set_key_value(ids, kv)
|
|
child.set_parent(parent)
|
|
child.swa_tombstone = tombstone
|
|
self.full_evictable += child.length
|
|
if not tombstone:
|
|
self.swa_evictable += child.length
|
|
return child
|
|
|
|
# ---------------------------------------------------------------- locking (dual)
|
|
def inc_lock(self, node: RadixTreeNode) -> Optional[int]:
|
|
"""Pin the matched node's KV path (full ref node..root) and the trailing window of live
|
|
swa tokens (swa ref). Stamps and returns ``swa_uuid_for_lock`` at the node where the
|
|
cumulative swa lock first covers the window (None if the path is shorter than a window).
|
|
Enforces full_ref >= swa_ref. Mirrors sglang ``inc_lock_ref``."""
|
|
swa_uuid_for_lock: Optional[int] = None
|
|
swa_locked = 0
|
|
cur = node
|
|
while not cur.is_root():
|
|
if cur.ref_count == 0:
|
|
self.full_evictable -= cur.length
|
|
self.full_protected += cur.length
|
|
cur.ref_count += 1
|
|
if swa_locked < self.sliding_window_size and not cur.swa_tombstone:
|
|
if cur.swa_ref_count == 0:
|
|
self.swa_evictable -= cur.length
|
|
self.swa_protected += cur.length
|
|
cur.swa_ref_count += 1
|
|
swa_locked += cur.length
|
|
if swa_locked >= self.sliding_window_size:
|
|
if cur.swa_uuid is None:
|
|
self._uuid += 1
|
|
cur.swa_uuid = self._uuid
|
|
swa_uuid_for_lock = cur.swa_uuid
|
|
cur = cur.parent
|
|
return swa_uuid_for_lock
|
|
|
|
def dec_lock(self, node: RadixTreeNode, swa_uuid_for_lock: Optional[int] = None,
|
|
skip_swa: bool = False) -> None:
|
|
dec_swa = not skip_swa
|
|
cur = node
|
|
while not cur.is_root():
|
|
cur.ref_count -= 1
|
|
assert cur.ref_count >= 0
|
|
if cur.ref_count == 0:
|
|
self.full_evictable += cur.length
|
|
self.full_protected -= cur.length
|
|
if dec_swa and not cur.swa_tombstone and cur.swa_ref_count > 0:
|
|
cur.swa_ref_count -= 1
|
|
if cur.swa_ref_count == 0:
|
|
self.swa_evictable += cur.length
|
|
self.swa_protected -= cur.length
|
|
if swa_uuid_for_lock is not None and cur.swa_uuid == swa_uuid_for_lock:
|
|
dec_swa = False # window boundary reached (inclusive); stop swa decrement
|
|
cur = cur.parent
|
|
|
|
# ---------------------------------------------------------------- eviction (dual)
|
|
def evict_full(self, num_tokens: int) -> SWAEvictResult:
|
|
"""Evict full KV by LRU over UNLOCKED LEAF nodes (an internal node's KV is a prefix
|
|
dependency). Frees both pools for each evicted leaf; cascade-reclaims exposed swa-tombstone
|
|
leaves' full KV. Mirrors sglang ``evict`` full pass."""
|
|
leaves = [n for n in self._leaves() if n.ref_count == 0]
|
|
heapq.heapify(leaves)
|
|
kv, swa, freed = [], [], 0
|
|
while freed < num_tokens and leaves:
|
|
node = heapq.heappop(leaves)
|
|
if node.ref_count != 0 or not node.is_leaf() or node.is_root():
|
|
continue
|
|
freed += node.length
|
|
kv.append(node.value)
|
|
self.full_evictable -= node.length
|
|
if not node.swa_tombstone:
|
|
swa.append(node.value) # its swa is still live -> free it too
|
|
self.swa_evictable -= node.length
|
|
parent, casc = self._cascade_swa_tombstone_leaves(self._unlink(node), kv)
|
|
freed += casc
|
|
# Re-push the SURVIVING ancestor the cascade returned (the original parent may have
|
|
# been unlinked/freed by the cascade -- re-pushing it would double-free / KeyError).
|
|
if parent.is_leaf() and parent.ref_count == 0 and not parent.is_root():
|
|
heapq.heappush(leaves, parent)
|
|
return SWAEvictResult(torch.cat(kv) if kv else self.empty,
|
|
torch.cat(swa) if swa else self.empty)
|
|
|
|
def evict_swa(self, num_tokens: int) -> SWAEvictResult:
|
|
"""Evict swa KV by LRU over UNLOCKED, non-tombstone swa-bearing nodes -- internal nodes
|
|
too. Internal (or full-locked) node -> TOMBSTONE in place (free swa, keep full KV +
|
|
children). Free leaf -> free both pools, unlink, cascade. Mirrors sglang ``evict`` swa
|
|
pass + the leaf-with-full-lock edge."""
|
|
cands = [n for n in self._swa_nodes() if n.swa_ref_count == 0]
|
|
heapq.heapify(cands)
|
|
kv, swa, freed = [], [], 0
|
|
while freed < num_tokens and cands:
|
|
node = heapq.heappop(cands)
|
|
if node.swa_tombstone or node.swa_ref_count != 0 or node.is_root():
|
|
continue
|
|
if node.is_leaf() and node.ref_count == 0:
|
|
kv.append(node.value)
|
|
swa.append(node.value)
|
|
self.full_evictable -= node.length
|
|
self.swa_evictable -= node.length
|
|
freed += node.length
|
|
node.swa_tombstone = True
|
|
self._cascade_swa_tombstone_leaves(self._unlink(node), kv)
|
|
else:
|
|
swa.append(node.value) # tombstone internal / full-locked leaf in place
|
|
self.swa_evictable -= node.length
|
|
freed += node.length
|
|
node.swa_tombstone = True
|
|
return SWAEvictResult(torch.cat(kv) if kv else self.empty,
|
|
torch.cat(swa) if swa else self.empty)
|
|
|
|
def trim_head_swa(self, input_ids: torch.Tensor, keep_from: int) -> torch.Tensor:
|
|
"""Tombstone the swa currency of the path strictly below ``keep_from`` (full KV stays),
|
|
returning the freed swa-bearing full indices for the caller to release. Retention
|
|
companion of the finish-time soft pin: only the trailing window ``[keep_from, P)``
|
|
needs to stay swa-live for a next-turn cut near P, so the head is reclaimed eagerly
|
|
instead of lingering as LRU litter. Locked (swa_ref>0), tombstoned and leaf nodes are
|
|
left untouched; ``keep_from`` must be page-aligned."""
|
|
if keep_from <= 0:
|
|
return self.empty
|
|
self.match_prefix(input_ids[:keep_from]) # ensure a node boundary at keep_from (splits)
|
|
freed: List[torch.Tensor] = []
|
|
node, pos = self.root, 0
|
|
while pos < keep_from:
|
|
child = node.children.get(self.key_fn(input_ids[pos:]))
|
|
if child is None or pos + child.length > keep_from:
|
|
break
|
|
if not child.swa_tombstone and child.swa_ref_count == 0 and not child.is_leaf():
|
|
freed.append(child.value)
|
|
self.swa_evictable -= child.length
|
|
child.swa_tombstone = True
|
|
node, pos = child, pos + child.length
|
|
return torch.cat(freed) if freed else self.empty
|
|
|
|
@property
|
|
def full_evictable_size(self) -> int:
|
|
return self.full_evictable
|
|
|
|
@property
|
|
def swa_evictable_size(self) -> int:
|
|
return self.swa_evictable
|
|
|
|
@property
|
|
def size_info(self):
|
|
from .base import SizeInfo
|
|
return SizeInfo(evictable_size=self.full_evictable, protected_size=self.full_protected)
|
|
|
|
def check_integrity(self) -> None:
|
|
for n in self._all_nodes():
|
|
assert n.ref_count >= 0 and n.swa_ref_count >= 0
|
|
assert n.ref_count >= n.swa_ref_count, "full_ref must be >= swa_ref"
|
|
if n.swa_tombstone:
|
|
assert n.swa_ref_count == 0, "a tombstoned node cannot hold a swa lock"
|
|
|
|
# ---------------------------------------------------------------- helpers
|
|
def _unlink(self, node: RadixTreeNode) -> RadixTreeNode:
|
|
parent = node.parent
|
|
del parent.children[self.key_fn(node._key)]
|
|
return parent
|
|
|
|
def _cascade_swa_tombstone_leaves(
|
|
self, parent: RadixTreeNode, kv_out: List[torch.Tensor]
|
|
) -> Tuple[RadixTreeNode, int]:
|
|
"""After a leaf is unlinked, eagerly reclaim the swa-tombstone leaves it exposes upward
|
|
(full KV still present, no children, unlocked): free their full KV and unlink. Keeps the
|
|
'a live leaf always carries live swa' invariant (sglang _iteratively_delete_tombstone_leaf).
|
|
Returns ``(surviving_ancestor, freed_full_tokens)`` -- the caller MUST use the returned
|
|
ancestor (the passed-in ``parent`` may itself have been unlinked/freed by the cascade)."""
|
|
freed = 0
|
|
while (parent.swa_tombstone and parent.is_leaf()
|
|
and parent.ref_count == 0 and not parent.is_root()):
|
|
kv_out.append(parent.value)
|
|
self.full_evictable -= parent.length
|
|
freed += parent.length
|
|
parent = self._unlink(parent)
|
|
return parent, freed
|
|
|
|
def _stamp_path(self, node: RadixTreeNode) -> None:
|
|
"""Stamp the matched path with strictly DECREASING timestamps toward root (deepest newest)
|
|
so the eviction heap (min on timestamp) reclaims near-root swa nodes first -- the same
|
|
victim order as sglang's reset_node_and_parents_mru."""
|
|
self._clk += 1
|
|
base = self._clk * _EVENT_STRIDE
|
|
off, cur = 0, node
|
|
while not cur.is_root():
|
|
cur.timestamp = base - off
|
|
off += 1
|
|
cur = cur.parent
|
|
|
|
def _tick(self) -> int:
|
|
self._clk += 1
|
|
return self._clk * _EVENT_STRIDE
|
|
|
|
def _leaves(self) -> List[RadixTreeNode]:
|
|
out, stack = [], [self.root]
|
|
while stack:
|
|
n = stack.pop()
|
|
if n.is_leaf():
|
|
if not n.is_root():
|
|
out.append(n)
|
|
else:
|
|
stack.extend(n.children.values())
|
|
return out
|
|
|
|
def _swa_nodes(self) -> List[RadixTreeNode]:
|
|
out, stack = [], [self.root]
|
|
while stack:
|
|
n = stack.pop()
|
|
if not n.is_root() and not n.swa_tombstone:
|
|
out.append(n)
|
|
stack.extend(n.children.values())
|
|
return out
|
|
|
|
def _all_nodes(self) -> List[RadixTreeNode]:
|
|
out, stack = [], [self.root]
|
|
while stack:
|
|
n = stack.pop()
|
|
if not n.is_root():
|
|
out.append(n)
|
|
stack.extend(n.children.values())
|
|
return out
|
|
|
|
__all__ = ["SWARadixCache", "SWAMatch", "SWAEvictResult", "SWACacheHandle"]
|