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(也称为前缀树或 Patricia Tree)的设计思路和细节。这个数据结构被用于优化 LLM(Large Language Model,大型语言模型)的 KV(Key-Value)缓存查询。
背景:LLM 的 KV 缓存
大型语言模型在生成文本时,需要存储中间计算结果,通常以 Key-Value(KV)对的形式缓存下来。这些 KV 对通常具有以下特点:
- 序列依赖:KV 对是按照输入序列(例如,句子或段落)的顺序生成的。每个 KV 对依赖于前面的 KV 对。
- 局部性:在生成过程中,模型倾向于频繁访问最近生成的 KV 对。
- 高维键:Key 通常是高维哈希值(例如,
LocalBlockHash),Value 是模型内部表示(这里不关注 Value,仅关注 Key 的组织)。
为什么选择 Radix Tree?
普通的哈希表(如
HashMap)可以快速查找 KV 对,但无法利用 序列依赖 和 局部性。而 Radix Tree 是一种压缩的前缀树,非常适合存储具有共同前缀的键集(这里的“前缀”是指序列中的前导元素)。它能:- 压缩存储:共享相同前缀的键不会重复存储节点,减少内存占用。
- 快速前缀匹配:沿着树遍历,可以高效匹配序列的前缀部分,符合 LLM 访问模式。
- 动态维护:支持插入、删除,同时保持结构高效。
数据结构设计
我们逐一解析代码中的核心组件。
1.
RadixTree结构体pub struct RadixTree { root: SharedRadixBlock, // 根节点(仅包含子节点) lookup: HashMap<WorkerId, HashMap<ExternalSequenceBlockHash, SharedRadixBlock>>, // 全局快速查找表 expiration_duration: Option<Duration>, // 访问时间窗口(用于频率统计) }root:树的根节点,是一个SharedRadixBlock(即Rc<RefCell<RadixBlock>>,下文解释)。根节点 只存储子节点,不存储实际的 Worker 信息。lookup:这是一个 二级哈希表:- 第一层:
WorkerId → HashMap,区分不同 Worker(可能是分布式系统中的节点)的 KV 对。 - 第二层:
ExternalSequenceBlockHash → SharedRadixBlock,快速索引 任意一个块 在 Radix Tree 中的位置。
- 第一层:
expiration_duration:可选的时间窗口,用于统计 块的访问频率(最近一段时间内被访问的次数)。这对缓存淘汰策略(LFU,Least Frequently Used)有帮助。
2.
RadixBlock(未直接展示,但可推断)每个
RadixBlock节点大概长这样:struct RadixBlock { children: HashMap<LocalBlockHash, SharedRadixBlock>, // 子节点(键是下一层哈希) workers: HashSet<WorkerId>, // 当前块被哪些 Worker 使用 recent_uses: VecDeque<Instant>, // 访问时间戳(如果启用 expiration_duration) }children:子节点的哈希表。键是LocalBlockHash(序列中的下一个哈希值),值是下一层的RadixBlock(包装在SharedRadixBlock中)。workers:记录哪些 Worker 引用了这个块。如果workers.is_empty(),说明没人用它了,可清理。recent_uses:如果配置了expiration_duration,则记录最近访问时间,用于频率统计。
SharedRadixBlock = Rc<RefCell<RadixBlock>>的作用:Rc(Reference Counting):共享所有权,多个地方可以持有同一个块,不用担心生命周期。RefCell:提供 运行时借用检查,允许.borrow()、.borrow_mut()动态访问/修改节点,避免 Rust 编译期借用规则的限制。
核心操作详解
1.
find_matches:沿着树查找匹配序列pub fn find_matches(&self, sequence: Vec<LocalBlockHash>, early_exit: bool) -> OverlapScores { let mut current = self.root.clone(); let now = Instant::now(); for block_hash in sequence { let next_block = current.borrow().children.get(&block_hash).cloned(); if let Some(block) = next_block { // 1. 更新匹配分数(该块有哪些 Worker) scores.update_scores(&block.borrow().workers); // 2. 更新访问频率(如果启用) if let Some(expiration_duration) = self.expiration_duration { // 移除过期的访问记录,并添加当前时间 block.borrow_mut().recent_uses.push_back(now); // 计算频率(窗口内访问次数) scores.add_frequency(block.borrow().recent_uses.len()); } // 3. 是否提前退出(比如已找到唯一匹配) if early_exit && block.borrow().workers.len() == 1 { break; } // 进入下一层 current = block; } else { // 没找到匹配的块,直接退出 break; } } scores }逻辑:
- 从
root开始。 - 按
sequence顺序逐个哈希匹配current.children。 - 若匹配到:
- 累加 匹配分(记录哪些 Worker 包含此序列)。
- 若开启频率统计,则 更新访问时间队列,并计算队列长度(代表频率)。
- 如果设置
early_exit且已经 唯一匹配(某个 Worker 独占此块),则终止遍历。
- 若某一步没匹配到,直接
break(序列前缀不匹配)。
举例:
假设
sequence = [H1, H2, H3],树结构如下:root ├── H1 → BlockA (Worker1, Worker2) │ └── H2 → BlockB (Worker1) │ └── H3 → BlockC (Worker1) └── H4 → ...遍历过程:
root.children[H1]→BlockA(匹配,累计 Worker1+Worker2)。BlockA.children[H2]→BlockB(匹配,累计 Worker1)。BlockB.children[H3]→BlockC(匹配,累计 Worker1)。
若
early_exit=true,在第 2 步发现只剩 Worker1,立即返回。2.
apply_event:处理插入/删除事件这是动态更新树的核心逻辑,处理三种事件:
Stored(插入)、Removed(删除)、Cleared(清空某 Worker 全量数据)。(1)
Stored操作(插入新块)KvCacheEventData::Stored(op) => { let current = match op.parent_hash { Some(parent) => worker_lookup.get(&parent).cloned(), // 从 lookup 快速找父块 None => Some(self.root.clone()), // 无父块,从 root 开始 }; // 遍历 op.blocks,按顺序插入树中 for block_id in op.blocks { let mut inner = current.borrow_mut(); let block = inner.children.entry(block_id.tokens_hash).or_insert_with(|| { // 若块不存在,则新建并加入 lookup 表 let new_block = Rc::new(RefCell::new(RadixBlock::new())); worker_lookup.insert(block_id.block_hash, new_block.clone()); new_block }); // 块存在或新建后,添加当前 WorkerId block.borrow_mut().workers.insert(worker_id); current = block; // 进入下一层 } }关键点:
- 先通过
parent_hash查找 父块(要么在worker_lookup里,要么是root)。 - 遍历
op.blocks(假设[B1, B2, B3]):current.children[B1]:不存在则新建Block1,加入worker_lookup,插入worker_id。Block1.children[B2]:同上,新建/复用Block2,插入worker_id。- 依次类推,链式深入。
- 同时更新
worker_lookup,保证全局可快速索引任意块。
(2)
Removed操作(删除块)KvCacheEventData::Removed(remove) => { for block_hash in remove.block_hashes { if let Some(entry) = worker_lookup.get(&block_hash).cloned() { let mut guard = entry.borrow_mut(); guard.workers.remove(&worker_id); // Worker 引用计数 -1 if guard.workers.is_empty() { guard.children.clear(); // 级联删除子节点(没人用了) } worker_lookup.remove(&block_hash); // 从快速表移除 } } }逻辑:
- 对每个要删除的
block_hash: - 从
worker_lookup找到对应的RadixBlock。 block.workers.remove(worker_id),相当于引用计数减一。- 若
workers.is_empty()(没人引用了),则:children.clear()(递归释放内存,假设没有其他引用)。
- 从
worker_lookup移除此block_hash。
(3)
Cleared操作(清空某 Worker 的全量数据)直接调用
clear_all_blocks(worker_id):pub fn clear_all_blocks(&mut self, worker: WorkerId) { if let Some(blocks) = self.lookup.get(&worker) { for block in blocks.values() { block.borrow_mut().workers.remove(&worker); // 移除引用 } self.lookup.get_mut(&worker).unwrap().clear(); // 清空 worker 的索引表 } }等价于:遍历此 Worker 的所有块,执行
workers.remove(worker_id),然后删掉worker_lookup里的记录。频率统计与过期逻辑
expiration_duration机制用于实现 近似 LFU(Least Frequently Used):- 每个
RadixBlock维护recent_uses: VecDeque<Instant>。 - 访问时(
find_matches),push_back(now)当前时间戳。 - 同时,清理过期记录:从队首开始,移除
now - expiration_duration之前的旧时间戳。 scores.add_frequency(block.borrow().recent_uses.len()):把 窗口内访问次数 作为频率分数。
这样,避免了全局维护频率计数器的开销,只有 活跃遍历的路径 才更新时间戳。
总结:设计亮点
- Radix Tree 压缩序列存储:共享前缀,避免冗余节点。
- 双重索引:
root → children树状遍历匹配序列。worker_lookup哈希表 随机访问任意块,弥补树查找慢的问题。
- 动态维护:插入、删除、清空操作保证树和索引表一致性。
- 频率窗口统计:用
VecDeque<Instant>实现轻量 LFU,适应 LLM 访问局部性。 - 线程安全:通过
Rc<RefCell<>>共享块所有权,运行时借用检查避免锁开销。
这个实现非常适合 序列依赖强、局部访问频繁、动态更新 的场景(如 LLM 的 KV 缓存管理)。如果数据规模继续扩大,可以考虑:
- 更高效的频率统计(如
HyperLogLog近似计数)。 - 分层 Radix Tree(目前是两层:
WorkerId → block_hash,可变为WorkerId → shard_id → block_hash)。 - 内存池优化,减少
Rc引用计数开销。
总之,这是一个 理论与工程实践结合得非常好的数据结构实现!
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.