tantan的博客

Notes, ideas, and observations

和 Bw-Tree 一样出自微软研究院,但思路几乎相反:Bw-Tree 用 delta chain 攒写入,读的时候要沿链表追指针;Bf-Tree 把攒写入的地方换成一个按 key 有序、长度可变的 mini-page,读写都只需一次二分查找。论文的实验里专门实现了一个"类 Bw-Tree"的 Bδ-Tree 作为对照。

一句话概括:加一层间接,把一切修改都变成"新建一个对象 + 一次 CAS"。页之间不再用物理指针相连,而用逻辑页号(PID);PID 到物理地址的翻译放在一张映射表里。于是改一个页只需要把新状态挂上去、再 CAS 一下映射表的槽位,页的物理位置在内存里、在闪存上都可以随意搬动。

ptmalloc 是 glibc 的默认内存分配器,也是最流行的内存分配器之一,起源于 Doug Lea 的 dlmalloc。由 Wolfram Gloger 改进得到可以支持多线程。

在仓库级计算机(warehouse-scale computer,WSC)中,内存分配是一项显著的计算开销,对它的优化可以节省可观的成本。一种经典方法是提高分配器本身的效率,减少花在分配器代码中的周期。然而,内存分配决策还会通过数据放置影响应用的整体性能,这提供了用更少硬件资源完成更多应用工作的机会。本文聚焦于大页覆盖率(hugepage coverage)。

现代内存分配器需要同时兼顾性能、安全、并发以及具体使用场景的特殊需求。一个越来越常见的场景是作为 Swift、Python 这类使用引用计数自动释放对象的语言的后端。本文提出 mimalloc,它很好地平衡了这些需求,性能显著优于现有分配器,并且专门支持依赖分配器实现引用计数的语言。

SGLang 程序可以通过 “fork” 原语串联多个生成调用并创建并行副本。此外,不同的程序实例通常共享某些公共部分(例如,系统 Prompt)。这些场景在执行过程中会生成许多共享的 Prompt 前缀,从而为重用 KVCache 提供了大量机会。在 LLM 推理过程中,KVCache 存储前向传递的中间 Tensor,用于解码未来的 Token。它们以自注意力机制中的键值对命名 [51]。 KVCache 的计算仅取决于前缀 Token。因此,具有相同 Prompt 前缀的请求可以重用 KVCache,从而减少冗余计算和内存使用。更多背景和一些示例在附录 A 中提供。

Google 从事大规模 Linux 容器的管理工作已有十余年,期间开发了三种不同的容器管理系统。

0%