from __future__ import annotations import heapq import time from dataclasses import dataclass from typing import Any, Callable, Dict, List, Tuple, TypeAlias import torch from freetoken.core import get_global_ctx from freetoken.utils import align_down from .base import BaseCacheHandle, BasePrefixCache, InsertResult, MatchResult, SizeInfo KEY_FN: TypeAlias = Callable[[torch.Tensor], Any] class RadixTreeNode: counter: int = 0 def __init__(self, key_fn: KEY_FN, tic: int | None = None) -> None: self.key_fn = key_fn self.children: Dict[Any, RadixTreeNode] = {} self._parent: RadixTreeNode | None = None self.ref_count: int = 0 self.uuid = RadixTreeNode.counter RadixTreeNode.counter += 1 self.timestamp = tic or time.monotonic_ns() # Secondary "currency" for hybrid models (HybridRadixCache): an optional GDN state # snapshot slot attached at this node's END boundary, with its own ref count. None # for plain KV radix. ``split_at`` leaves the new prefix node's ``mamba_value`` None # ("a snapshot cannot be split") -- the snapshot stays on the original (suffix) node, # whose end boundary is unchanged. Forward-compat seam for SWA. self.mamba_value: int | None = None self.mamba_ref_count: int = 0 # SWA second currency (SWARadixCache). Unlike the GDN snapshot above, SWA stores NO # separate slot: ``value`` (full-pool page indices) is canonical and the swa KV is # reached via the pool's full->swa mapping. ``swa_tombstone`` marks that the swa KV for # these tokens was freed (slid out of window) while the full KV survives; ``swa_ref_count`` # is the trailing-window lock; ``swa_uuid`` is the window-boundary handle (lock release). # All default off -> the plain KV radix and the GDN hybrid radix are unaffected. self.swa_tombstone: bool = False self.swa_ref_count: int = 0 self.swa_uuid: int | None = None # these fields should be updated later self._key: torch.Tensor self._value: torch.Tensor self._length: int def set_key_value(self, key: torch.Tensor, value: torch.Tensor) -> None: assert len(key) == len(value) self._key = key self._value = value self._length = len(key) def set_parent(self, parent: RadixTreeNode) -> None: self._parent = parent parent.children[self.key_fn(self._key)] = self @property def length(self) -> int: return self._length @property def parent(self) -> RadixTreeNode: assert self._parent is not None return self._parent @property def value(self) -> torch.Tensor: return self._value def is_root(self) -> bool: return self._parent is None def is_leaf(self) -> bool: return len(self.children) == 0 def get_match_len(self, input_ids: torch.Tensor) -> int: from freetoken.kernel import fast_compare_key # compare key and input_ids, find the first diff return fast_compare_key(self._key, input_ids) def split_at(self, pos: int) -> RadixTreeNode: assert 0 < pos < self.length parent = self.parent new_node = RadixTreeNode(self.key_fn, self.timestamp) new_node.set_key_value(self._key[:pos], self._value[:pos]) new_node.set_parent(parent) new_node.ref_count = self.ref_count # SWA: a tombstone covers all the node's tokens, so both halves inherit it; both halves # stay within a locked window, so the swa lock copies; the window-boundary uuid migrates # to the root-side (prefix) node and is cleared on the suffix (matches sglang _split_node). new_node.swa_ref_count = self.swa_ref_count new_node.swa_tombstone = self.swa_tombstone new_node.swa_uuid = self.swa_uuid self.swa_uuid = None self.set_key_value(self._key[pos:], self._value[pos:]) self.set_parent(new_node) return new_node def __lt__(self, other: RadixTreeNode) -> bool: return self.timestamp < other.timestamp @dataclass(frozen=True) class RadixCacheHandle(BaseCacheHandle): node: RadixTreeNode def get_matched_indices(self) -> torch.Tensor: node = self.node value_list: List[torch.Tensor] = [] while not node.is_root(): value_list.append(node.value) node = node.parent value_list.reverse() return torch.cat(value_list) class RadixPrefixCache(BasePrefixCache): def __init__(self, device: torch.device, page_size: int | None = None): super().__init__() self.device = device # Explicit page_size beats the global ctx: a manager constructed with page_size!=ctx # (tests, future multi-granularity) must not silently split the two (the tree would # align by one granularity while the manager frees by the other -> orphaned pages). self.page_size = get_global_ctx().page_size if page_size is None else int(page_size) self.key_fn = _get_key_fn(self.page_size) self.empty_tensor = torch.empty(0, dtype=torch.int32, device=device) self.evictable_size = 0 self.protected_size = 0 self.root_node = RadixTreeNode(self.key_fn) self.root_node.ref_count = 1 # root is always protected def lock_handle(self, handle: BaseCacheHandle, unlock: bool = False) -> None: assert isinstance(handle, RadixCacheHandle) node = handle.node if unlock: while not node.is_root(): node.ref_count -= 1 assert node.ref_count >= 0 if node.ref_count == 0: self.evictable_size += node.length self.protected_size -= node.length node = node.parent else: while not node.is_root(): if node.ref_count == 0: self.evictable_size -= node.length self.protected_size += node.length node.ref_count += 1 node = node.parent def match_prefix(self, input_ids: torch.Tensor) -> MatchResult: node, prefix_len = self._tree_walk(input_ids) return MatchResult(RadixCacheHandle(prefix_len, node)) def insert_prefix(self, input_ids: torch.Tensor, indices: torch.Tensor) -> InsertResult: insert_len = align_down(len(input_ids), self.page_size) input_ids, indices = input_ids[:insert_len], indices[:insert_len] node, prefix_len = self._tree_walk(input_ids) if prefix_len != insert_len: # NOTE: prefix_len < insert_len new_node = RadixTreeNode(self.key_fn) # A view would keep the request's full output-budget token buffer alive. new_node.set_key_value( input_ids[prefix_len:].clone(), indices[prefix_len:].clone() ) new_node.set_parent(node) self.evictable_size += new_node.length node = new_node return InsertResult(prefix_len, RadixCacheHandle(insert_len, node)) def evict(self, size: int) -> torch.Tensor: if size == 0: return self.empty_tensor assert ( size <= self.evictable_size ), f"Cannot evict {size}, only {self.evictable_size} is evictable" leave_nodes = self._collect_leave_nodes_for_evict() heapq.heapify(leave_nodes) evicted_indices: List[torch.Tensor] = [] evicted_size = 0 while evicted_size < size: assert ( leave_nodes ), f"Cannot evict enough cache, need {size}, only {evicted_size} evicted" node = heapq.heappop(leave_nodes) assert node.ref_count == 0 and node.is_leaf() and not node.is_root() evicted_size += node.length evicted_indices.append(node.value) self.evictable_size -= node.length parent = node.parent del parent.children[self.key_fn(node._key)] # NOTE: root is always protected, so won't be evicted if parent.is_leaf() and parent.ref_count == 0: heapq.heappush(leave_nodes, parent) return torch.cat(evicted_indices) def reset(self) -> None: raise NotImplementedError("RadixManager.reset is not implemented") @property def size_info(self) -> SizeInfo: return SizeInfo( evictable_size=self.evictable_size, protected_size=self.protected_size, ) def check_integrity(self) -> None: pass def _collect_leave_nodes_for_evict(self) -> List[RadixTreeNode]: nodes: List[RadixTreeNode] = [self.root_node] leave_nodes: List[RadixTreeNode] = [] while len(nodes) > 0: node = nodes.pop() if node.is_leaf(): if node.ref_count == 0: leave_nodes.append(node) else: for child in node.children.values(): nodes.append(child) return leave_nodes def _tree_walk(self, input_ids: torch.Tensor) -> Tuple[RadixTreeNode, int]: prefix_len = 0 indice_len = len(input_ids) node = self.root_node tic = time.monotonic_ns() while prefix_len < indice_len: child_node = node.children.get(self.key_fn(input_ids[prefix_len:])) if child_node is None: return node, prefix_len node = child_node # walk to child node # NOTE: at least 1 page is matched, so match_len >= page_size match_len = node.get_match_len(input_ids[prefix_len:]) match_len = align_down(match_len, self.page_size) prefix_len += match_len # need to split the node if not fully matched if match_len != node.length: node = node.split_at(match_len) node.timestamp = tic return node, prefix_len # update timestamp for accessed node node.timestamp = tic return node, prefix_len def _get_key_fn(page_size: int) -> KEY_FN: if page_size == 1: return lambda x: x[0].item() return lambda x: tuple(x[:page_size].tolist())