Caffeine 核心架构与底层原理

一、 底层存储与数据结构：数据与元数据的解耦

Caffeine 在内存布局上做到了严格的职责分离，它的底层并非单一结构，而是由“数据的存储”与“淘汰元数据的存储”共同组成：

1. ConcurrentHashMap（数据载体）：
   • 作用： 负责存储真实的 Key-Value 数据节点（Node），承担所有业务线程的高并发读写请求。
   • 特点： 保证了 O(1) 的定位速度和多线程下数据本身的安全。它是所有缓存操作的入口。
2. FrequencySketch（频率记录器）：
   • 底层实现： 采用 Count-Min Sketch 算法（一种概率型计数数据结构）。它本质上是一个一维的 long 数组，通过多个不同的 Hash 算法映射位图来记录访问频率。
   • 优势： 传统的 LFU 需要使用 HashMap 记录每个 Key 的频率，极其消耗内存。Count-Min Sketch 通过微小的 Hash 冲突代价，将频率计数压缩到了只需要 4-bit 即可表示一个 Key 的访问热度，极大降低了内存开销。
3. 三个双端队列（状态链表）：
   • 数据节点在 ConcurrentHashMap 中存在的同时，其引用会被串联在逻辑队列中，用于维护淘汰顺序。这三个队列分别是：
     • Window 区（Eden）：占比极小（默认 1%），采用严格 LRU，用于抵御突发性的稀疏流量（Burst Traffic）。
     • Main-Probation（试用区）：占比约 20%，采用 LRU。
     • Main-Protected（保护区）：占比约 79%，采用 LRU，存放真正的高频热点数据。

二、 W-TinyLFU 淘汰与晋升算法：精准的优胜劣汰

传统的 LRU 无法应对周期性扫描（会导致热点数据被洗掉），而传统的 LFU 无法应对突发流量（旧的热点数据占据缓存不放）。Caffeine 提出的 W-TinyLFU (Window-TinyLFU) 完美融合了两者的优点。

数据的生命周期与流转机制如下：

1. 新数据写入（进入 Window 区）： 所有新加入的数据首先放入 Window 区。这保证了哪怕是突发流量，也能在缓存中存活一小段时间（Recency），弥补了纯 LFU 算法对新数据不友好的缺陷。
2. Window 区满与准入竞争（Admission Policy）：
   • 当 Window 区空间耗尽，队尾的最久未访问节点（候选者 Candidate）将被驱逐。
   • 频率 PK（核心）： 候选者不会直接进入 Main 区，而是必须与 Main-Probation 区队尾的节点（受害者 Victim）进行比较。Caffeine 会去 FrequencySketch 中查询两者的历史访问频率。
   • 胜者为王： 只有当新数据的频率 大于 试用区待淘汰数据的频率时，新数据才会被允许进入 Main-Probation 区；否则，新数据直接被丢弃（拒绝准入）。
3. 主区的晋升与降级（Promotion & Demotion）：
   • 晋升： 当 Main-Probation（试用区）中的数据再次被业务访问时，它会被晋升到 Main-Protected（保护区），成为受保护的核心热点。
   • 降级： 随着保护区数据增多并达到上限，保护区队尾的数据会被降级，重新跌落回试用区，参与后续的淘汰 PK。
   • 衰减机制（Reset）： 为了防止曾经的热点数据永远占据空间（缓存污染），FrequencySketch 内部有一个计数器。当系统的总访问次数达到一定阈值时，所有 Key 的频率记录都会减半（衰减），从而给新数据让出竞争空间。

三、 读写分离与多生产单消费：极致的无锁并发设计

这是 Caffeine 碾压 Guava Cache 的核心所在。传统缓存（如 Guava）在每次读写数据后，都需要同步更新 LRU 双向链表。因为链表操作非线程安全，必须加锁。在高并发下，这把锁成为了吞吐量的绝对瓶颈。

Caffeine 彻底解耦了“操作数据”和“维护策略”的执行逻辑：

1. 多生产者（业务线程）：只记日志，绝不等待
   • 读操作（Read）： 业务线程从 ConcurrentHashMap 拿到数据后，只负责将这次访问事件（Event）记录到一个类似于 Striped64（类似 LongAdder）的 RingBuffer 中。利用多段细粒度的环形数组，极大地避免了 CPU 缓存行的伪共享（False Sharing）问题，实现了完全无锁的记录。
   • 写操作（Write）： 业务线程执行增删改后，将事件写入一个 MPSC（多生产者单消费者）队列 中。
   • 有损记录（Lossy）： 极其精妙的一点是，对于读操作，如果 RingBuffer 瞬间被打满，业务线程会直接丢弃这次访问记录，而不是阻塞等待。因为在庞大的基数下，丢弃少量的访问记录完全不影响 TinyLFU 对“热点数据”的宏观统计，这是一种用微小的统计精度换取绝对吞吐量的妥协策略。
2. 单消费者（维护线程）：异步批处理，独享锁
   • Caffeine 内部调度着一个后台线程（单消费者）。
   • 它会定期（或者当 Buffer 达到一定阈值时）异步地将 RingBuffer 和 MPSC 队列中的事件批量排出（Drain）。
   • 无锁化维护： 因为全世界只有这一个线程在消费这些事件，所以由它去更新 FrequencySketch 频率、移动 Window/Main 区的双向链表指针时，完全不需要加任何全局锁。