Untitled conversation
- User
pub struct RadixTree { /// This is the root of the radix/prefix tree /// This will only contain root blocks root: SharedRadixBlock, /// This is a global lookup table for all blocks which will let you jump into /// the radix tree at any point /// Lookup is best case O(1) and worst case O(N); however, even constant in-time /// could be expensive if N is large /// We should monitor the size of this table and consider using a proper radix tree. /// Transitioning to a radix tree only would require a change in the messaging structure /// as the entire prefix would need to be sent. Alternatively, we could use block_depth /// integers to indicate how many blocks to skip and use a radix/prefix tree at each level. lookup: HashMap<WorkerId, HashMap<ExternalSequenceBlockHash, SharedRadixBlock>>, /// The time buffer the radix tree should check when considering frequence of block accesses expiration_duration: Option<Duration>, } impl Default for RadixTree { fn default() -> Self { Self::new() } } impl RadixTree { /// Create a new `RadixTree`. /// /// ### Returns /// /// A new `RadixTree`. pub fn new_with_frequency(expiration_duration: Option<Duration>) -> Self { Self { root: Rc::new(RefCell::new(RadixBlock::new())), lookup: HashMap::new(), expiration_duration, } } pub fn new() -> Self { Self::new_with_frequency(None) } /// Traverse the radix tree to find the best match for a given sequence of [`LocalBlockHash`]es. /// /// ### Arguments /// /// * `sequence` - A vector of `LocalBlockHash` representing the sequence to match. /// * `early_exit` - A boolean indicating whether to exit early if a single match is found. /// /// ### Returns /// /// An `OverlapScores` representing the match scores. pub fn find_matches(&self, sequence: Vec<LocalBlockHash>, early_exit: bool) -> OverlapScores { let mut scores = OverlapScores::new(); let mut current = self.root.clone(); let now = Instant::now(); for block_hash in sequence { let next_block = { let current_borrow = current.borrow(); current_borrow.children.get(&block_hash).cloned() }; if let Some(block) = next_block { scores.update_scores(&block.borrow().workers); if let Some(expiration_duration) = self.expiration_duration { let mut block_mut = block.borrow_mut(); while let Some(access_time) = block_mut.recent_uses.front() { if now.duration_since(*access_time) > expiration_duration { block_mut.recent_uses.pop_front(); } else { break; } } scores.add_frequency(block_mut.recent_uses.len()); block_mut.recent_uses.push_back(now); } if early_exit && block.borrow().workers.len() == 1 { break; } current = block; } else { break; } } scores } /// Apply a [`RouterEvent`] to the radix tree. /// /// ### Arguments /// /// * `event` - The `RouterEvent` to apply. pub fn apply_event(&mut self, event: RouterEvent) { let (worker_id, event) = (event.worker_id, event.event); let (id, op) = (event.event_id, event.data); tracing::trace!(id, "Store operation: {:?}", op); let worker_lookup = self.lookup.entry(worker_id).or_default(); match op { KvCacheEventData::Stored(op) => { // find the parent block - if the parent exists it must be on our worker, if not, // we check the radix tree's root to find it. // this is the single most expensive lookup let current = match op.parent_hash { Some(parent) => worker_lookup.get(&parent), None => Some(&self.root), }; let mut current = match current { Some(current) => current.clone(), None => { tracing::warn!( worker_id = worker_id.to_string(), id, parent_hash = ?op.parent_hash, "Failed to find parent block; skipping store operation" ); return; } }; for block_id in op.blocks { let mut inner = current.borrow_mut(); let block = match inner.children.get(&block_id.tokens_hash) { Some(block) => block.clone(), None => { // create new block - automatically added to the lookup table let new_block = worker_lookup .get(&block_id.block_hash) .cloned() .unwrap_or_else(|| Rc::new(RefCell::new(RadixBlock::new()))); // insert into radix tree inner .children .insert(block_id.tokens_hash, new_block.clone()); new_block } }; // add our worker_id to the block block.borrow_mut().workers.insert(worker_id); // add the block to the worker_id lookup table worker_lookup.insert(block_id.block_hash, block.clone()); // drop inner so we can shift current to this block drop(inner); current = block; } } KvCacheEventData::Removed(remove) => { // tracing::trace!(id, "KV Remove Operation: {:?}", op); // let mut worker_lookup = self.lookup.get(&worker_id).expect("Worker not found"); for block in remove.block_hashes { // entry in radix tree // a small optimization would be to get the next block from the reduced set of children // in order to apply this optimization, we would need to know the list of blocks is always sorted // by parent -> child relationship let entry = match worker_lookup.get(&block) { Some(entry) => entry.clone(), None => { tracing::warn!( worker_id = worker_id.to_string(), id, "Failed to find block to remove; skipping remove operation" ); continue; } }; let mut guard = entry.borrow_mut(); guard.workers.remove(&worker_id); if guard.workers.is_empty() { // if no worker are using this block, that is true for all children guard.children.clear(); } // remove the block from the lookup table worker_lookup.remove(&block); } } KvCacheEventData::Cleared => { self.clear_all_blocks(worker_id); } } } pub fn remove_worker(&mut self, worker: WorkerId) { if let Some((_, blocks)) = self.lookup.remove_entry(&worker) { blocks.iter().for_each(|(_, block)| { block.borrow_mut().workers.remove(&worker); }); } } pub fn clear_all_blocks(&mut self, worker: WorkerId) { // Check if the worker has any blocks to clear if let Some(blocks) = self.lookup.get(&worker) { let blocks_to_clear: Vec<_> = blocks.values().collect(); // Remove the worker from each block's workers set blocks_to_clear.iter().for_each(|block| { block.borrow_mut().workers.remove(&worker); }); // Clear the worker's blocks if let Some(worker_blocks) = self.lookup.get_mut(&worker) { worker_blocks.clear(); } } } }这是一个为LLM提供kv cache查询的Radix Tree,请讲解实现的思路和细节
Assistant
这个 Radix Tree 实现是为 LLM 的 KV cache 查询优化设计的分布式前缀树结构。让我详细讲解其设计思路和实现细节:
核心设计思路
1. 数据结构设计
pub struct RadixTree { root: SharedRadixBlock, // 根节点 lookup: HashMap<WorkerId, HashMap<ExternalSequenceBlockHash, SharedRadixBlock>>, // 全局查找表 expiration_duration: Option<Duration>, // 访问频率统计的时间窗口 }这里采用了混合索引策略:
- 树形结构:用于前缀匹配查询
- 哈希表索引:实现 O(1) 的快速定位
2. 分布式缓存管理
系统支持多个 Worker 节点共享 KV cache:
- 每个
RadixBlock记录了拥有该块的所有 Worker ID lookup表按 Worker ID 分组,便于管理各 Worker 的缓存块
3. 核心功能实现
查找匹配(find_matches)
pub fn find_matches(&self, sequence: Vec<LocalBlockHash>, early_exit: bool) -> OverlapScores { let mut scores = OverlapScores::new(); let mut current = self.root.clone(); for block_hash in sequence { // 沿着前缀路径遍历 if let Some(block) = current.borrow().children.get(&block_hash) { // 更新匹配分数 scores.update_scores(&block.borrow().workers); // 访问频率统计 if let Some(expiration_duration) = self.expiration_duration { // 清理过期的访问记录 // 记录新的访问时间 // 更新频率分数 } // 早退优化:如果只有一个Worker拥有该块,可以提前结束 if early_exit && block.borrow().workers.len() == 1 { break; } } } }设计亮点:
- 前缀匹配:找出与输入序列最长公共前缀的缓存块
- 评分机制:根据匹配长度和访问频率计算得分
- 早退优化:当找到唯一匹配时可提前结束
事件处理(apply_event)
支持三种操作:
-
存储操作(Stored):
// 找到父节点 let current = match op.parent_hash { Some(parent) => worker_lookup.get(&parent), None => Some(&self.root), }; // 逐个插入新块 for block_id in op.blocks { // 创建或更新节点 // 更新 worker 集合 // 更新查找表 } -
删除操作(Removed):
- 从节点的 workers 集合中移除 worker ID
- 如果节点不再被任何 worker 使用,清理其子节点
- 更新查找表
-
清空操作(Cleared):
- 批量清理特定 worker 的所有缓存块
4. 性能优化策略
-
双重索引:
- 树形结构用于前缀查询
- HashMap 提供 O(1) 的直接访问
-
引用计数智能指针:
type SharedRadixBlock = Rc<RefCell<RadixBlock>>;- 使用
Rc<RefCell<>>实现共享可变性 - 避免数据复制,提高内存效率
- 使用
-
访问频率优化:
- 使用滑动时间窗口统计访问频率
- 优先选择频繁访问的缓存块
5. 实际应用场景
在 LLM 推理中,这个 Radix Tree 可以:
- 前缀共享:多个请求如果共享相同的前缀(如系统提示词),可以复用已缓存的 KV 值
- 分布式缓存:多个 Worker 节点可以共享缓存,提高资源利用率
- 智能路由:根据匹配度和访问频率,将请求路由到最合适的 Worker
6. 潜在改进点
代码注释中提到的一些考虑:
- 当前的 lookup 表在规模很大时可能成为瓶颈
- 可以考虑使用纯 radix tree 实现,但需要改变消息结构
- 可以使用分层的 radix tree 来优化查找性能
这个实现巧妙地平衡了查询效率和内存使用,特别适合 LLM 的 KV cache 场景,其中前缀共享是常见模式。
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.