设计
访问顺序队列
双向链表对散列表中的所有条目进行排序。一个条目可以在O(1)时间内在hash map中找到,然后操作其相邻元素。
创建,更新或读取条目是顺序访问的。Least Recently Used（即LRU算法)的条目。most Recently used(即最热)的在尾部。这种结构是对于基于size(maximumSize)的驱逐和基于时间(expireAfterAccess)的驱逐的支持,这种结构所面临的挑战是每一次访问都需要这个列表的变化，而这个列表本身不能被有效地同时执行(线程不安全)。
写顺序队列
创建或更新条目是顺序写入的。 与访问顺序队列类似，写入顺序队列在O(1)时间内运行。 该队列用于生存时间到期（expireAfterWrite）。
Hierarchical TimerWheel
时间感知优先级队列使用散列和双向链表执行O(1)时间复杂度的操作。 此队列用于变量到期（expireAfter（Expiry））。
Read buffer
缓存操作的典型做法是给每次操作都加锁,以便安全的重新排列访问队列中的条目.另外一种方法是将每个重新排序操作存储在缓冲区中并批量更改.这可以被视为内存页替换策略的预写日志.当缓冲区满时,尝试获取锁并执行挂起的操作,但是如果已经挂起,则该线程可以立即返回。
读取缓冲区被实现为striped ring buffer(条带化的环形缓冲区,有关环形缓冲区的详情可以查看这里)。 stripe用于减少竞争，通过特定于线程的散列选择stripe。 环形缓冲区是一个固定大小的数组，使其高效并最小化垃圾收集开销。 stripe的数量可以根据竞争检测算法动态增长。
Write buffer
与Read buffer类似,此buffer用于replay write事件。read buffer允许有损的,因为这些事件被用来优化驱逐策略的命中率.wirte是不允许有丢失的,所以它必须作为一个有效的有界队列来实现.由于每次填充write buffer的优先级,它通常保持是空或者非常小的容量。
缓冲区被实现为一个可扩展的环形数组，可以调整到最大容量。当一个数组调整时新的数组被分配和生成。旧的数组包含消费者便利的转发连接,然后允许将旧数组解除分配.通过使用这种组块机制,缓冲区具有较小的初始size，较低的读写成本,并且产生最小的垃圾.当缓冲区已满并且不能再扩大时,生产者不断旋转重拾该数组,并试图安排维护工作,然后再短时间内完成该工作.这样做可以允许消费者线程优先,并通过重放驱逐策略上的写入来清空缓冲区。
lock amortization
虽然传统的缓存是通过锁定每一个操作来执行微量的工作,但是caffeine是通过分批工作将成本分摊到多个线程中的。这种做法将会分摊锁定状态的性能损耗而不是增加锁竞争的成本。尽管如果任务被拒绝的话或者调用者运行策略被使用,那么它可以由用户线程执行,但是这种维护低性能损耗的任务将委托给配置的Excutor。
由于锁的独占特性,缓冲区在给定的时间内只能被单个线程消耗。通过利用cpu高速缓存效率,这样就允许使用更高效的基于多生产者/消费的缓冲器实现，它也更好的符合硬件特性。
条目状态转换
高速缓存未被独占锁保护时的挑战是操作可能被记录并以错误的顺序重放.由于竞争，创建 - 读取 - 更新 - 删除序列可能不以相同顺序存储在缓冲器中。 要做到这一点将需要粗粒锁，从而降低性能。
正如在并发数据结构中一样，caffeine使用原子状态转换解决了这个困境。 一个条目可以有active，retired，或者dead状态。 active状态意味着它存在于散列表和存取/写入队列中。 从哈希表中删除条目时，将其标记为retired，需要从队列中删除。 发生这种情况时，条目被认为是dead，并有资格进行垃圾回收。
relaxed读写
Caffeine非常小心地使用每一个volatile操作.内存屏障不是从语言来实现volatile read和write的,而是由硬件来保证.通过了解哪些屏障被发射,以及它们对硬件和数据可见性的影响，存在实现更好性能的潜力。
Caffeine使用relaxed的读取时,锁可以保证独占访问,因为数据可见性可以由锁获取到的内存屏障提供.发生数据竞争也是可以接受的，例如当检查一个条目是否已经过期以模拟缓存未命中。
Caffeine以类似relaxed writes的方式来读取.如果条目使用锁来独占写,那么写入可以发生在解锁时发射的内存屏障上。 有时候也可以接受write skew，例如当读取条目时更新访问时间戳。
驱逐策略
Caffeine使用Window TinyLfu策略来提供接近最佳的命中率. 访问队列被分成两个空间：一个eden空间，如果被TinyLfu收容政策所接受，则会被驱逐到main空间。 TinyLfu估计eden区的条目和main区条目的频率，选择保留最高的历史使用条目。 频率计数存储在一个4位的CountMinSketch中，每个缓存条目需要8个字节才是准确的。 这种配置使得缓存能够在O(1)时间内以较小的占用空间基于频率和就近成度被驱逐。
Fastpath
当缓存低于其最大容量的50％时，驱逐策略尚未完全启用。 频率草图不初始化以减少内存占用，因为高速缓存可能被人为赋予较高的阈值。 除非另一个功能要求，否则不会记录访问，以避免争用读缓冲区，并在排空时重放访问。
哈希碰撞和Dos攻击保护
当key具有相同的散列码或散列到相同的位置时，可能会利用这些冲突来降低性能。 哈希表通过从链接列表降级到红黑树的来解决这个问题，并且CountMinSketch使用随机加载因子来保护其哈希函数。
对TinyLFU的攻击是利用碰撞来人为地提高驱逐政策条目的预估频率。 这导致所有新的到期条目被频率过滤器拒绝，从而使缓存无效。 一个解决方案是引入少量的抖动，这样可以使预估是不确定的。 这是通过随机接纳具有中等频率的被拒绝候选人的1％来完成的。
装饰哈希map
//TEB