Yuchen You

这篇作品和十多年前的 Spark 的设计非常类似，都是 frontend (DSL) – runtime codesign 来实现全局的加速; Frontend with DSL Runtime (Radix Attention) 解决的问题 还是针对 KV cache 的计算角度，sglang 希望能解决不同 request 之间的 prefix 共享问题，尤其是在 system prompt 存在的情况下，很多时候的 system prompt 是大多数请求共享的，并不需要每次都计算，这样可以节省很多计算量; 不止如此，还有更多的 shared-prefix 的情况，在这些情况下应该能共享 KV cache, 这就是最核心的 motivation; 方法 因为要面向最大 prefix 建模，这里就需要一个 radix tree 的数据结构，要求在一个 prompt 的任意 token 位置都可以裂开分成多个 child 对应不同的 后续 prompt 内容; 这里由于要支持任意 token 位置断开，所以在 pagedattention 的框架下，必须要把每个 page 大小设置成 ...

背景故事 书接上回，在 orca 这篇论文的笔记最后我们发现了 Orca 的 batching 调度的一个局限性; 如果把 prefill 和 decode 阶段的操作 batch 到一起可能会存在比较大的性能差异, 往往 decode 阶段是更快的，而 prefill 阶段会把同批次的 decode 请求拉慢; 根据分类，使用诸如 Orca/vLLM 的 iteration level batching (也叫 continuous batching), 其实可以理解为优先处理所有请求的 prefill 部分 (只要 GPU 资源有空就拿来处理新请求的 prefill 部分)，所以在这篇论文中称之为 prefill-prioritize. 两个核心卡顿 generation-stalls: decode 请求在受到来自 prefill 的 batching 的时候会出现一定时间的 latency 等待 pipeline-stalls: 在使用 pipeline-parallel 算法的时候，会将一个完整的 model 按照层 (block) 进行按组分割放到不同的几个 gpu 上 ...

KV Cache 优化的讨论 对于一个 Transformer Block, 我们应该有 token tensor -> projection -> attention -> FFN 这几个核心步骤; 那么使用 kv cache 的话在 decode 阶段可以把 attention 计算的复杂度降低到 O(N)O(N)O(N)，并且这个可以同时利好 projection 和后续的 ffn 让其不再需要处理完整的 prompt 而是只有最后一个新的 token; 因此 kv cache 的 存在 可以极大地优化一个 decode 推理流程; 但是我们主要好奇的是 kv cache 的优化究竟占到了多少的性能提升，假设我们有一个弱化版的 kv cache, 对比 vllm 版本究竟弱化化了多少; 然后 FFN 在有 kvcache 的前提下，又能怎么优化; 这是两个不同角度的问题; 而且 KV Cache 的特性是 append only, 这样相当于对于写满的 block 这里的操作是 read-only, 但是经常会涉及 dead -> 回收所有权; KV ca ...

Prefill 阶段的计算复杂度 工业常见 dense LLM 的 hidden dimension 大概是 4K 到 16K 量级 无法 batch 的几种情况 其实卡住 batch 的原因都是在 attention 模块的计算部分 两个进程都在 prefill 阶段但是二者张量的形状不同; prefill 阶段二者都要计算完整的 softmax(QKtdk)Vsoftmax(\frac{QK^t}{\sqrt{d_k}})Vsoftmax(dk​​QKt​)V, 如果要一起计算就需要 X.shape(−1)X.shape(-1)X.shape(−1) 和 X.shape(−2)X.shape(-2)X.shape(−2) 分别相等，也就是张量形状一致; 两个进程都在 decode 阶段但是二者的 token id 不同; decode 阶段计算是最后一个 token 对应的 query 去和前面所有的 K 和 V 做匹配，如果二者的 index 不同，说明其前面的 K 和 V 的行数 (sequence id/维度) 不同，从而导致形状不同 两个进程处在不同的 p/d ...

[!Mem0 记忆管线的黑话] extraction phase: 从新一轮对话里提炼候选事实, 写入路径的第一步 update phase: 候选事实和已有记忆对账, 决定 ADD / UPDATE / DELETE / NOOP Ω\OmegaΩ: extraction 吐出的候选记忆集合 SSS: 异步刷新的全局对话摘要, 提供"远景" tool call: LLM 自己选操作并执行的 function-calling 接口 Mem0g^gg: 把记忆表示从自然语言换成知识图谱的变体 Mem0 在 memory 光谱里的位置 agent memory 这一堆框架, 区分它们最有用的是两个轴: 记忆的表示 (自然语言 / 向量 / 图 / 时序图) 和记忆的生命周期 (写入 →\rightarrow→ 检索 →\rightarrow→ 更新 →\rightarrow→ 遗忘); Mem0 base 在表示这一轴上是最朴素的一档: 记忆就是一条条自然语言 fact, 存在一个普通向量库里, 检索走 RAG 式的 ANN; 论文原话是向量库 “employs ...

📝 术语别名 handle: Chubby 里 client open 一个 path 后拿到的, 绑定 session 的远程对象引用; 不是 session 本身, 是 session 内部的一个对象级句柄; znode: ZooKeeper 状态树上的一个节点, 既能当目录又能存一小坨 data, 带 version; ephemeral / sequential: 临时节点 (session 一断自动删) / 顺序节点 (创建时由 ZK 追加一个全局单调的编号), 选主 recipe 的两块积木; Zab: ZooKeeper Atomic Broadcast, ZK 内部的 leader-based 原子广播协议, 跟 Paxos / Raft 同级但不是同一个; A-linearizability: ZooKeeper 自己定义的一致性, 写线性 + 同一 client 的请求按发送序进入全局顺序 (per-client FIFO); wait-free: 一个 client 可以同时挂多个 in-flight 请求, 不用等上一个回包就发下一 ...

[!术语速查 / 黑称] context: 从 LLM 采样时塞进窗口的那一整坨 token —— system prompt, tools, MCP, 外部数据, message history 全算在内; attention budget: 模型的 “注意力预算”, 每多塞一个 token 就从里面扣一点, 不是免费的; context rot: context 越长, 模型越记不住前面说过啥 —— “上下文腐烂”, 每个模型都有这毛病; just-in-time: 不在 inference 前把数据全嚼碎喂进去, 而是让 agent 攥着轻量标识 (文件路径, query, 链接), 运行时按需 拉回 数据; progressive disclosure: agent 靠探索一点点把相关 context 挖出来 —— 文件大小暗示复杂度, 命名暗示用途, 时间戳暗示新鲜度; compaction: context 快满时, 把对话 压 成摘要, 拿摘要开一个新窗口接着跑; 前置直觉: 为什么 context 越长反而越笨 先讲个最朴素的画面: 人塞太多东西进脑子也会断片; ...

这二十年其实是同一个故事在反复上演: 数据先撑爆了存储和计算, 然后撑爆了数据库, 接着业务拆成微服务又撑爆了运维; 每一次"撑爆"都把某家公司摁在地上摩擦, 而它们挣扎着爬起来时顺手造的那个轮子, 转头就成了全行业的地基; 这篇严格按时间从上往下串成一个故事, 每个轮子只记三件事: 哪年、谁家、被啥需求逼的; 它同时也是 ds/ 这一摞笔记的索引页, 相关的都挂了内链; 一张总图先压个轴, 后面分幕细讲 (主线是后台基建, 另有"可靠性"和"前台 Web"两条副线, 放在最后单讲): 12345678910111213141516171998 ─ VMware 虚拟化: 一台物理机切成多台 VM, 是多租户云的前提2003 ─ GFS / Xen Google 在会坏的廉价磁盘上存 PB / 开源虚拟化2004 ─ MapReduce / nginx 普通工程师也能并行算 PB / nginx 解决 C10K 高并发2006 ─ Bigtable·Chubby·AWS·Hadoop 结构化存储·协 ...

📝 术语别名 cell: 一个故障隔离单元, 通常 1 master + 5 replica; coarse-grained lock: 粗粒度锁, 持有时间小时/天级 (典型如"我是这个集群的 master"), 跟毫秒级临界区互斥的 fine-grained lock 相对; advisory lock: 建议锁, 系统不强制, 靠"守规矩的应用"自觉遵守; safety / liveness: 安全性(“坏事永不发生”, 比如绝不脑裂) / 活性(“好事最终发生”, 比如最终能达成决定); 论文定位 Mike Burrows, “The Chubby lock service for loosely-coupled distributed systems”, OSDI 2006, Google; 这不是一篇推公式的理论论文, 而是一篇工程经验总结: Chubby 在 Google 内部已经给 GFS、Bigtable 这些大家伙撑了好几年选主了, 所以全文都是踩坑之后的反思, 读它的正确姿势是" ...