Skip to content
TheChatArchiveThe Chat Archive
Metallama-4-maverick-03-26-experimental· MetaHugging Face LMArena Human Preference 140K

Untitled conversation

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with Claudeclaude-opus-4-20250514-thinking-16k’s answer.
  1. 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,请讲解实现的思路和细节

  2. Meta Assistant

    这是一个非常有趣的实现!我会详细讲解这个 Radix Tree(也称为前缀树或 Patricia Tree)的设计思路和细节。这个数据结构被用于优化 LLM(Large Language Model,大型语言模型)的 KV(Key-Value)缓存查询。

    背景:LLM 的 KV 缓存

    大型语言模型在生成文本时,需要存储中间计算结果,通常以 Key-Value(KV)对的形式缓存下来。这些 KV 对通常具有以下特点:

    1. 序列依赖:KV 对是按照输入序列(例如,句子或段落)的顺序生成的。每个 KV 对依赖于前面的 KV 对。
    2. 局部性:在生成过程中,模型倾向于频繁访问最近生成的 KV 对。
    3. 高维键:Key 通常是高维哈希值(例如,LocalBlockHash),Value 是模型内部表示(这里不关注 Value,仅关注 Key 的组织)。

    为什么选择 Radix Tree?

    普通的哈希表(如 HashMap)可以快速查找 KV 对,但无法利用 序列依赖 和 局部性。而 Radix Tree 是一种压缩的前缀树,非常适合存储具有共同前缀的键集(这里的“前缀”是指序列中的前导元素)。它能:

    1. 压缩存储:共享相同前缀的键不会重复存储节点,减少内存占用。
    2. 快速前缀匹配:沿着树遍历,可以高效匹配序列的前缀部分,符合 LLM 访问模式。
    3. 动态维护:支持插入、删除,同时保持结构高效。

    数据结构设计

    我们逐一解析代码中的核心组件。

    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
    }
    

    逻辑:

    1. 从 root 开始。
    2. 按 sequence 顺序逐个哈希匹配 current.children。
    3. 若匹配到:
      • 累加 匹配分(记录哪些 Worker 包含此序列)。
      • 若开启频率统计,则 更新访问时间队列,并计算队列长度(代表频率)。
      • 如果设置 early_exit 且已经 唯一匹配(某个 Worker 独占此块),则终止遍历。
    4. 若某一步没匹配到,直接 break(序列前缀不匹配)。

    举例:

    假设 sequence = [H1, H2, H3],树结构如下:

    root
     ├── H1 → BlockA (Worker1, Worker2)
     │     └── H2 → BlockB (Worker1)
     │           └── H3 → BlockC (Worker1)
     └── H4 → ...
    

    遍历过程:

    1. root.children[H1] → BlockA (匹配,累计 Worker1+Worker2)。
    2. BlockA.children[H2] → BlockB (匹配,累计 Worker1)。
    3. 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; // 进入下一层
        }
    }
    

    关键点:

    1. 先通过 parent_hash 查找 父块(要么在 worker_lookup 里,要么是 root)。
    2. 遍历 op.blocks(假设 [B1, B2, B3]):
      • current.children[B1]:不存在则新建 Block1,加入 worker_lookup,插入 worker_id。
      • Block1.children[B2]:同上,新建/复用 Block2,插入 worker_id。
      • 依次类推,链式深入。
    3. 同时更新 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); // 从快速表移除
            }
        }
    }
    

    逻辑:

    1. 对每个要删除的 block_hash:
    2. 从 worker_lookup 找到对应的 RadixBlock。
    3. block.workers.remove(worker_id),相当于引用计数减一。
    4. 若 workers.is_empty()(没人引用了),则:
      • children.clear()(递归释放内存,假设没有其他引用)。
    5. 从 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):

    1. 每个 RadixBlock 维护 recent_uses: VecDeque<Instant>。
    2. 访问时(find_matches),push_back(now) 当前时间戳。
    3. 同时,清理过期记录:从队首开始,移除 now - expiration_duration 之前的旧时间戳。
    4. scores.add_frequency(block.borrow().recent_uses.len()):把 窗口内访问次数 作为频率分数。

    这样,避免了全局维护频率计数器的开销,只有 活跃遍历的路径 才更新时间戳。

    总结:设计亮点

    1. Radix Tree 压缩序列存储:共享前缀,避免冗余节点。
    2. 双重索引:
      • root → children 树状遍历匹配序列。
      • worker_lookup 哈希表 随机访问任意块,弥补树查找慢的问题。
    3. 动态维护:插入、删除、清空操作保证树和索引表一致性。
    4. 频率窗口统计:用 VecDeque<Instant> 实现轻量 LFU,适应 LLM 访问局部性。
    5. 线程安全:通过 Rc<RefCell<>> 共享块所有权,运行时借用检查避免锁开销。

    这个实现非常适合 序列依赖强、局部访问频繁、动态更新 的场景(如 LLM 的 KV 缓存管理)。如果数据规模继续扩大,可以考虑:

    • 更高效的频率统计(如 HyperLogLog 近似计数)。
    • 分层 Radix Tree(目前是两层:WorkerId → block_hash,可变为 WorkerId → shard_id → block_hash)。
    • 内存池优化,减少 Rc 引用计数开销。

    总之,这是一个 理论与工程实践结合得非常好的数据结构实现!

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.