2026-07-27

今日主题

• Count-Min Sketch 与 FrequencySketch 的本质差异
• Caffeine Node 生命周期与状态编码
• Caffeine 并发架构：热路径解耦
• 并发一致性模型层次
• W-TinyLFU 算法原理
• Caffeine 节点与维护架构
• Caffeine 与 Guava 加载模型
• JDK 8 ConcurrentHashMap
• Guava CacheLoader 批量加载与刷新机制
• Guava Graph 三种类型的本质区别
• incidentEdges 语义

新增认知

Count-Min Sketch 与 FrequencySketch 的本质差异

• Sketch 的命名来源：Sketch（素描）在概率算法领域是一类数据结构的统称，特征是用少量内存近似估计大量数据的统计信息（如访问频率），
  结果是有误差上界的近似值，而非精确值。Caffeine 用它做 TinyLFU 准入策略的频率计数。

• Flat vs Block 的本质是内存访问模式：标准 CountMinSketch（Flat）用 4 个独立哈希函数将计数器随机散布在整个数组，
  每次操作最多触发 4 次 cache miss。
  FrequencySketch（Block）将一个元素的 4 个计数器强制约束在同一个 64 字节 block 内——
  恰好等于 CPU L1 cache line 大小——第一次访问把整行加载进来，后续 3 次直接命中 L1，实质上把 4 次内存访问压缩为 1 次。

• FrequencySketch 复杂度的来源：复杂度来自两个叠加的优化——① 位压缩存储：
  把 16 个 4-bit 计数器打包进一个 long（64 bit），用位运算手动读写每个计数器，目的是让 table 更小、更容易整体驻留在 CPU 缓存；
  ② 刻意约束内存布局：通过 blockHash/counterHash 双重哈希把 4 个 slot 锁定在同一 cache line 内。
  两者结合造成大量位运算，代码难读，但换来了显著的运行时性能提升。

• 准确性与局部性的权衡：Block 布局让 4 个计数器只能从 block 内部的 8 个 long 里选，分布均匀性不如全局随机散布，
  理论上碰撞概率略高。但实测影响可忽略，性能收益远大于精度损失——这是算法实现中典型的"对硬件友好"优化思路。

Caffeine Node 生命周期与状态编码

• 脉络：多结构并存导致需要状态机：
  Node 同时挂在 CHM、access order deque、write order deque、timerWheel 等多个数据结构，删除无法原子完成，
  必然存在过渡态，因此引入 alive/retired/dead 三态状态机。

• 三态含义：alive = 同时在 CHM 和链表；retired = 已从 CHM 删除，还在链表等待摘除；dead = 两处都已清除。
  retired/dead 通过将 node.key 字段替换成哨兵对象（RETIRED_SENTINEL / DEAD_SENTINEL）来标记。

• 哨兵不会与业务 key 冲突：判断哨兵用 == 引用比较（不是 equals），哨兵是 JVM 里唯一的两个对象实例，
  任何业务 key 的内存地址都不可能与之相等。

• node.key 冗余存储的必要性：淘汰时从链表遍历拿到 node，
  需要 node.key 才能定位 CHM 的 bucket 执行 remove(key, node)。没有它就无法反查 CHM。
  这个字段同时被复用来编码状态（哨兵），一举两得，不是真正的冗余。

Caffeine 并发架构：热路径解耦

• 脉络：让 get/put 热路径尽量轻：核心目标是把链表维护、weight 计算、驱逐等重操作推给 maintenance，调用线程只做最轻量的操作。
  Read/Write Buffer 和 evictionLock 都服务于这个目标。

• Read Buffer：lock-free + 有损：get() 把访问记录扔进 striped ring buffer（CAS 写入，无锁），
  满了直接丢。丢掉只影响 LRU 顺序精度，不影响正确性。本质是延迟更新 LRU 顺序以避免读操作加锁。

• Write Buffer：无损，满了借用写线程：
  put/remove 把 AddTask/UpdateTask/RemovalTask 扔进 MPSC 队列，写线程立刻返回。
  队列满了写线程自己同步执行 maintenance，任务不能丢——丢了会导致内存泄漏或状态错误。

• evictionLock 和 CHM bin lock 职责不同：CHM bin lock 保护单个 key 的 value 读写（粒度细）；
  evictionLock 保护跨 key 的全局策略状态（access order deque、weightedSize、FrequencySketch、TimerWheel），
  两者互补，不可替代。

• CHM get 无锁可见性保证：get() 是纯 volatile 读，不加任何锁。
  put() 的 bin lock release 语义 + get() 的 volatile acquire 语义建立 happens-before，
  保证不会读到撕裂的中间状态，只可能读到旧值或新值（线性一致性）。

并发一致性模型层次

• 五种模型从弱到强：最终一致性 < 因果一致性 < 顺序一致性 < 线性一致性 < 严格一致性。严格一致性要求基于全局物理时钟，
  分布式系统中不可实现（相对论层面的约束）。

• 线性 vs 顺序一致性的区别：顺序一致性只要求全局存在一个合法的操作顺序，不要求尊重实时顺序；线性一致性额外要求操作必须尊重调用和返回之间的实时顺序。
  CHM 提供线性一致性，分布式系统通常退而求其次用因果或最终一致性。

W-TinyLFU 算法原理

• 脉络：recency + frequency 双维度：纯 LRU 只看最近访问，扫描攻击可驱逐热点；纯 LFU 新 key 频率为 0 永远进不来。
  W-TinyLFU 用三队列解决 recency（试用期），用 FrequencySketch 解决 frequency（准入门槛），
  两者结合兼顾突发热点和持续热点。

• Count-Min Sketch 是布隆过滤器的升级版：布隆过滤器每格 1 bit 回答"存在吗"；CMS 每格 4 bit 回答"出现几次"。共同点：
  多个 hash 函数映射到数组，hash 冲突只会高估不会低估，空间极小。

• CMS 的 block/slot/index 三层定位：block = 8个连续 long（64字节 = 一条L1缓存行），用 blockHash 选；
  slot = block 内具体哪个 long，用 counterHash 低位选；index = 那个 long 里16个4-bit计数器中的哪个。
  4行计数器约束在同一 cache line，一次内存加载完成，避免4次 cache miss。

• 三队列容量与流转：window（~1%）接收新 entry，满了从头部推入 probation；probation 无硬性上限，
  是 window 和 protected 降级的缓冲区，也是频率竞争的擂台；protected（~79%）保护高频热点，满了从头部降级回 probation。
  hill climber 动态调整 window/main 边界适应 workload。

• 过期策略与数据结构的对应：固定时长（expireAfterAccess/expireAfterWrite）用 LRU 队列，尾部最老，
  peek 头部即知是否过期，O(1)；可变时长（expireAfter(Expiry)）每个 key 时长不同，用时间轮精确调度。配置了 maxSize 时，
  expireAfterAccess 共用 eviction 的三条 access order 队列，减少内存开销。

Caffeine 节点与维护架构

• 节点按需生成：Caffeine 用 Node 统一缓存条目的行为契约，再按强弱键值、过期、权重等特性生成只含必要字段的子类，
  避免每个条目承担未启用功能的内存成本。基础生成类同时实现 NodeFactory，是用无参实例充当工厂、用有参实例充当真实节点，
  从而少生成一套 Factory 类型。

• 策略最终一致：BoundedLocalCache 以 ConcurrentHashMap 保障键值读写的即时正确性，
  把访问顺序、频率、权重和过期索引视为允许滞后的策略状态。读写事件先进入缓冲区，再在 evictionLock 下批量维护，以少量策略精度换取请求路径的低竞争。

• 维护集中编排：maintenance 是 BoundedLocalCache 的策略维护事务边界，
  统一排空读写缓冲、回收引用、处理过期与容量淘汰并调整 Window/Main 比例；
  但 Map 修改、逻辑过期判断、刷新和任务调度仍发生在请求路径或其他异步流程，不能把它理解成缓存所有行为的唯一入口。

• 写缓冲非写队列：writeBuffer 是承载 AddTask、UpdateTask、RemovalTask 的临时事件队列，
  排空时会同步容量、访问队列、写入过期队列、时间轮和节点生命周期；
  writeOrderDeque 才是按最后写入时间排序、服务 expireAfterWrite 的持久策略索引，并不是容量淘汰意义上的 LRU。

• 异步并非专属线程：Caffeine 默认由读写触发维护并提交 ForkJoinPool.commonPool，不会为每个缓存创建常驻线程；
  未配置 Scheduler 时，空闲缓存不会仅因 TTL 到点主动清理。
  JDK 8 的 Caffeine 2.x 中 systemScheduler 会退化为 disabledScheduler，
  需要自建 ScheduledExecutorService 才能空闲时定时唤醒。

• 过载转为背压：维护任务通过状态机合并且缓冲区有界，不会按每次读写无限提交；
  当公共线程池饱和导致 writeBuffer 填满、任务被拒绝或显式调用 cleanUp 时，maintenance 会转到调用线程同步执行。
  由此过载通常表现为策略滞后、容量暂时超限和写延迟上升，而不是内部任务无限堆积。

Caffeine 与 Guava 加载模型

• 锁域与持锁时长：Guava LocalCache 在 Segment 锁内安装 LoadingValueReference 后释放锁，
  再在锁外执行 CacheLoader；
  Caffeine 同步缓存则在 ConcurrentHashMap.compute 的 bin 原子范围内执行 mapping function。
  前者锁域较宽但持锁短，后者锁域较窄却可能被慢 Loader 长时间占用。

• 同键合并方式不同：Guava 让同 key 请求等待 LoadingValueReference 的 Future，
  Caffeine 依靠 ConcurrentHashMap.compute 保证同 key 至多执行一次同步加载。Caffeine 命中先走无锁快速路径，
  miss 或过期才进入 compute，Map 更新同步可见，淘汰与过期策略再通过 AddTask 或 UpdateTask 最终补齐。

• 慢加载选异步缓存：同步 Caffeine Loader 包含 RPC、数据库或长计算时，会阻塞同 bin 的更新，并可能妨碍扩容迁移；
  AsyncLoadingCache 先在 Map 中建立 CompletableFuture，再异步完成结果，
  更接近 Guava loading 占位符的隔离效果。

JDK 8 ConcurrentHashMap

• 从分段到分桶：JDK 7 CHM 以固定 Segment 作为写锁和容量分区，Segment 内仍有 hash bin；
  JDK 8 移除 Segment，使用单表结构，空 bin 通过 CAS 插入，非空 bin 以头节点同步。优势是写并发不再受固定 Segment 数限制，
  空间也能全表共享。

• 读取无锁写入细锁：JDK 8 CHM 通过 volatile 字段和原子数组访问实现 get 的无锁可见性；写入只在发生结构修改的 bin 上串行化。
  大量碰撞时链表可树化为红黑树，将最坏查找由 O(n) 收敛到 O(log n)，但慢 compute 仍会阻塞同 bin 更新。

• 扩容协作迁移：扩容发起线程创建两倍 nextTable，写线程通过 CAS 递减 transferIndex 领取不同区间。
  旧 bin 按 hash 与旧容量位拆成原下标和原下标加旧容量两组，迁移后以 ForwardingNode 标记；读线程可跳到新表，
  写线程遇到 MOVED 时可加入迁移，因此无需全表停顿。

• 双变量确认完成：transferIndex 归零只表示所有区间已被领取，sizeCtl 还用扩容代次 stamp 和参与者计数确认其他迁移线程均已退出。
  最后一个线程由 CAS 唯一选出，进入 finishing 全表复查所有 bin 已转发，随后发布 nextTable 并恢复新的扩容阈值。

Guava CacheLoader 批量加载与刷新机制

• loadAll 未实现时的降级路径：
  CacheLoader.loadAll() 默认实现直接抛出 UnsupportedLoadingOperationException（CacheLoader.java:126-130），
  这不是错误而是一种约定信号。LocalCache.getAll()（LocalCache.java:4055-4072）会捕获这个异常，
  逐个调用 get(key, defaultLoader) 完成加载，相当于自动降级为单点查询。只有当批量查询确实比逐次查询效率高时才需要重写 loadAll，
  否则不重写也不影响功能，只是拿不到批量优化收益。

• load/loadAll 同步，reload 接口异步但默认实现是同步的：
  CacheLoader 中 load(K) 和 loadAll(keys) 的方法签名就是直接返回值，本质是同步阻塞调用；
  只有 reload(K, V) 返回 ListenableFuture，接口设计上是异步的。但默认实现 reload() 内部只是 immediateFuture(load(key))——
  先同步执行 load 再包一层已完成的 Future，本质仍是阻塞的，只是套了个异步的壳。要让 reload 真正异步执行，需要自己重写它，
  或使用工厂方法 CacheLoader.asyncReloading(loader, executor)，
  它会把 load 提交到指定 Executor 上异步执行并返回真正未完成的 Future。

Guava Graph 三种类型的本质区别

• 脉络：从图到 Network 的递进：Graph 只记录"两节点是否连通"，ValueGraph 在边上附加一个值（如权重），
  Network 把边变成真实对象。三者的核心分水岭是"边有没有身份"——需要通过边查信息、或同两节点间存在多条平行边时，才升级到 Network。

• 边的匿名含义：Graph/ValueGraph 中边是匿名的，意味着你没有一个代表该边的对象，
  只能用 EndpointPair（两端节点的组合）来描述它。Network 中边是你自己 new 的对象，有完整身份，
  可以存储、传递、反查（network.incidentNodes(edge)）。

• 有向/无向是图级别属性：不是单条边的属性，而是整张图的配置，通过 GraphBuilder.directed() 或 .undirected() 决定。
  一张图里所有边方向一致，不能混用。有向图中 hasEdgeConnecting(A,B) 和 hasEdgeConnecting(B,A) 结果可能不同。

incidentEdges 语义

• incidentEdges 返回所有碰到该节点的边：不区分入边/出边，
  是 predecessors（入边对端节点）和 successors（出边对端节点）的边视图版本。区别在于返回值类型：
  incidentEdges 给边对象（EndpointPair 或 E），predecessors/successors 给节点。
  degree(node) 是 incidentEdges 的数量版本。