Caffeine 并发设计深度解析（面试向）

Caffeine 并发设计深度解析面试向一、为什么摒弃分段锁Segment LockConcurrentHashMap (JDK7) 分段锁的问题锁粒度仍然较粗一个 Segment 锁住一批桶每个 Segment 是独立 HashTable内存开销大写竞争集中在 Segment 上扩展性受限缓存场景下读远多于写且每次读都可能触发统计/LRU 更新分段锁会成为瓶颈Caffeine 借鉴了 JDK8 ConcurrentHashMap 的思路实际底层就是基于 CHM并在缓存语义层做了进一步优化。二、Caffeine 的核心并发设计1. 数据存储层CAS synchronized细粒度锁底层BoundedLocalCache继承自类 ConcurrentHashMap 的结构CAS 操作节点的状态字段如writeTime、accessTime、weight使用VarHandle/Unsafe进行 CAS 更新无锁synchronized 锁单个桶头节点仅在哈希冲突链表/红黑树修改时才加锁锁粒度 单个 bin读操作完全无锁依赖 volatile 可见性2. 读写缓冲区核心创新ReadBuffer多个 RingBuffer类似 Striped 设计每次get()后需要更新 LRU/LFU 频率若直接改链表会引发竞争解决方案线程哈希到不同的 RingBuffer默认 4 × NCPU 向上取2幂使用 CAS 写入 ring buffer有损满了就丢弃不影响正确性异步批量 drain 到 LRU 队列WriteBufferMpscGrowableArrayQueue多生产者单消费者无锁队列写操作必须保证不丢失所以是无损的同样异步 drain3. 异步维护drainStatus 状态机通过 CAS 维护drainStatusIDLE/REQUIRED/PROCESSING_TO_IDLE/PROCESSING_TO_REQUIRED只有一个线程能成为 drainertryLock语义其他线程提交完任务直接返回不阻塞读写主路径4. 频率统计FrequencySketchW-TinyLFUCount-Min Sketch 的 4-bit 计数器通过位运算 CAS 更新计数无锁三、面试高频问答Q1Caffeine 比 Guava Cache 快在哪里Guava 用分段锁 同步执行 LRU 维护 → 读路径上有锁竞争Caffeine 把维护操作异步化RingBuffer 缓冲 后台 drain→ 读路径几乎无锁Q2为什么 ReadBuffer 可以有损它只用于更新访问频率/LRU 顺序丢一两个事件不影响正确性仅影响淘汰精度换来极致性能Q3synchronized 在哪里用仅在修改 bin 头节点链表/树时使用且是 JDK8 优化后的偏向→轻量→重量级锁路径竞争少时几乎零开销Q4CAS 用在哪些地方节点状态字段更新、ringBuffer 写入索引、drainStatus 切换、FrequencySketch 计数Q5与 ConcurrentHashMap 的关系Caffeine 的 BoundedLocalCache 借鉴 CHM 的 bin 结构和锁策略但额外叠加了缓存语义层的异步维护机制四、总结一句话Caffeine CHM 的细粒度桶锁CAS synchronized bin有损 ReadBuffer / 无损 WriteBuffer 异步化维护W-TinyLFU 淘汰让读写主路径几乎无锁竞争把维护开销摊销到后台单线程。FrequencySketch 与 W-TinyLFU 详解一、为什么需要频率统计传统 LRU 的致命缺陷只看最近不看频次经典反例缓存污染一次性扫描大量冷数据如全表扫描会把热点数据全挤出缓存例如热点 key A 被访问 1000 次但突然来一批只访问 1 次的冷 keyA 就被淘汰了解决思路淘汰时同时考虑访问频率 (LFU)和最近访问 (LRU)→TinyLFU / W-TinyLFU二、FrequencySketch 是什么它是 Caffeine 实现的Count-Min Sketch (CM-Sketch)变种用极小内存近似统计每个 key 的访问频率。朴素 LFU 的问题给每个 key 维护一个计数器 → 1 万个 key 就要 1 万个 long内存开销大、且 key 已经被淘汰后计数器还占空间Count-Min Sketch 的核心思想用一个固定大小的二维计数矩阵 多个哈希函数key 经过 4 个不同哈希函数映射到 4 个槽位每次访问4 个槽位都 1查询频率时取这 4 个槽位的最小值Min作为估计值因为哈希冲突只会让计数偏大取 min 能逼近真实值hash1 → [槽位a] 1 key → hash2 → [槽位b] 1 hash3 → [槽位c] 1 hash4 → [槽位d] 1 频率估计 min(a, b, c, d)三、Caffeine 的工程优化精髓所在1.4-bit 计数器而不是 int/long每个计数器只用 4 bit最大值 151 个 long (64 bit) 可以装16 个计数器内存占用极低1 万 entry 缓存 ≈ 几十 KB为什么 15 够用→ 配合下面的老化机制2.饱和计数 (Saturation)计数到 15 就不再增加避免热点 key 计数无限膨胀且让新热点有机会翻身3.Aging / Reset老化机制—— 关键每当总访问次数达到阈值默认 容量的 10 倍所有计数器右移 1 位除以 2作用让历史频率衰减适应访问模式变化避免老热点永远霸占缓存对应论文里的Freshness Mechanism4.CAS 无锁更新// 伪代码 long old table[index]; long updated old (1L offset); // 对应 4-bit 段 1 UNSAFE.compareAndSwapLong(table, index, old, updated);多线程并发更新计数器全程无锁失败重试竞争极小哈希分散5.块级哈希 (Block Hash)4 个哈希值落在同一个 64-byte cache line 内4 个 long 32 byte一个 block 8 个 longCPU 缓存友好一次内存加载完成 4 次查询这是 Caffeine 比传统 CM-Sketch 快很多的原因之一四、W-TinyLFU 整体淘汰流程W-TinyLFU Window LRU Main (SLRU) TinyLFU 准入过滤器新数据 → [Window LRU (1%)] ──淘汰候选→ ┐ ├─ TinyLFU 比较频率 → 胜者进 Main Main SLRU (99%) ──淘汰候选→ ──┘ ├─ Probation (20%) └─ Protected (80%)三个区域| 区域 | 占比 | 算法 | 作用 | |------|-----|------|-----| |Window| 1% | LRU | 缓冲新入 key应对突发流量 | |Probation| 80%×20% | LRU | 试用区低频区 | |Protected| 80%×80% | LRU | 保护区高频区 |准入决策核心当 Window 满了要把Window 候选放进 Main从 Main 的 Probation 取出 LRU 端的受害者 victim用FrequencySketch 比较两者频率candidate 频率 victim → 替换candidate 频率 ≤ victim → 拒绝保留老的这就是 TinyLFU 的准入过滤思想五、面试高频问答Q1FrequencySketch 内存开销4-bit × (容量 × 10) 大约几十 KB 级别几乎可忽略Q2为什么取 minCM-Sketch 因哈希冲突计数只会偏大不会偏小取 min 是无偏下界估计Q3为什么要老化适应热点漂移防止僵尸热点配合 4-bit 饱和避免溢出Q4W-TinyLFU 解决了什么解决纯 LFU 对突发流量不友好新 key 频率为 0 进不来→ 用 Window 兜底解决纯 LRU 的缓存污染一次性扫描挤掉热点→ 用 TinyLFU 准入过滤Q5为什么 Caffeine 命中率高W-TinyLFU 论文证明在多种工作负载下命中率接近最优 (Belady)显著优于 LRU/LFU/ARC一句话总结FrequencySketch 4-bit Count-Min Sketch 老化 CAS 无锁 cache-line 友好以极小内存代价提供准确的频率估计W-TinyLFU Window LRU SLRU 频率准入兼顾突发流量与长期热点是 Caffeine 高命中率的核心。已详细讲解 FrequencySketch 与 W-TinyLFUFrequencySketch频率草图基于 Count-Min Sketch用 4 个哈希函数映射到 4 个槽位取 min 作为频率估计4-bit 计数器1 long 装 16 个内存极小饱和到 15 不再累加总计数达阈值时全部右移 1 位老化CAS 无锁更新4 个哈希落同一 cache line块哈希CPU 友好W-TinyLFU 淘汰Window(1%) LRU Main SLRU(99% Probation 20% Protected 80%)准入过滤Window 候选 vs Main victim频率高者胜出解决 LRU 缓存污染 LFU 对突发流量不友好的问题核心面试点4-bit 饱和、老化机制、CAS 无锁、块哈希、准入过滤思想、为什么命中率接近 Belady 最优。