《大规模分布式计算深入解析》12.1 内存索引与缓存:全内存索引、图缓存与热点

LRU命中率由访问顺序决定,不等于容量除热点唯一项;相同3键300次访问、容量2可得0%或99%。

内存放置与索引算法分开

HNSW的图结构不意味着所有产品都必须全内存驻留。原向量、图邻接、量化码、payload和缓存可有不同放置;容量模型详见10.1。本节只讨论一个明确对象缓存的LRU策略,不把它当整个OS页缓存算法。

真正LRU如何更新

缓存命中把对象移到最近端;未命中读取/建立对象,容量满时淘汰最久未使用者。容量为0则每次未命中。本模型用访问顺序LinkedHashMap执行这些步骤,统计hits/misses/distinct。

相同统计、不同结果

容量2,三种对象a/b/c,各访问100次,总300次。

序列命中数命中率
abc重复100轮00%
a连续100,再b100,再c10029799%

二者唯一项和访问频度完全一样,区别只有时间顺序。capacity/unique=2/3不能表示两者的真实LRU命中率,旧线性模型已经移除。

如果要采用随机独立访问的概率估计,需要明确分布及推导,也不能把估计称为逐次LRU执行。

热点、工作集与测量

观察窗口、缓存容量单位(对象或字节)、对象大小和并发会影响结果。按对象数缓存不等于按页或字节预算;生产还可能有预取、pin、分层缓存和污染控制。

Milvus小集合warmup后一次查询耗时不能证明LRU命中曲线。真实RSS、图缓存命中、缺页和设备IO需要对应指标;应用缓存与OS缓存不能合并为一个“命中率”。

架构与流程

flowchart TD
 A["一次对象访问"] --> HIT{"已在缓存?"}
 HIT -->|是| MOVE["命中;移到最近端"]
 HIT -->|否| MISS["未命中;按实际后端读取"]
 MISS --> FULL{"容量可容纳?"}
 FULL -->|容量0| SKIP["不保留对象"]
 FULL -->|需淘汰| EVICT["删除最久未使用"]
 EVICT --> INSERT["插入最近端"]
 FULL -->|有空位| INSERT

实现与验证边界

真实LRU序列、零容量、空序列与重复访问有测试;未观测产品缓存内部策略或OS页缓存淘汰。

下载卷十三实验包 。Java 8入口为 lab.RunAll;本节对应 io.IoSuite。按README分别运行模型与原生入口,失败必须返回非零。模型通过不代表完整产品实现。

一手资料

卷十三目录 · 系列导读

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析·向量数据库与 AI 检索内核》 · 目录与学习路径(45 篇)
  2. 《大规模分布式计算深入解析》15.3 自研向量引擎:可执行骨架与工程缺口
  3. 《大规模分布式计算深入解析》14.1 Milvus:组件架构、段管理与检索链路