缓存之美：万字长文详解 Caffeine 实现原理

abstract class BoundedLocalCache<K, V> extends BLCHeader.DrainStatusRef implements LocalCache<K, V> {
    // 默认入参 onlyIfAbsent 为 false，表示向缓存中添加相同的 key 会对 value 进行替换     @Override    public @Nullable V put(K key, V value) {        return put(key, value, expiry(), /* onlyIfAbsent */ false);    }}

abstract class BoundedLocalCache<K, V> extends BLCHeader.DrainStatusRef implements LocalCache<K, V> {
    static final int WRITE_BUFFER_RETRIES = 100;
    final MpscGrowableArrayQueue<Runnable> writeBuffer;
    final ConcurrentHashMap<Object, Node<K, V>> data;
    final ReentrantLock evictionLock;
    final NodeFactory<K, V> nodeFactory;
    @Nullable    V put(K key, V value, Expiry<K, V> expiry, boolean onlyIfAbsent) {        // 不允许添加 null        requireNonNull(key);        requireNonNull(value);
        Node<K, V> node = null;        // 获取当前时间戳        long now = expirationTicker().read();        // 计算缓存权重，如果没有指定 weigher 的话，默认权重为 1        int newWeight = weigher.weigh(key, value);        // 创建用于查找的键对象        Object lookupKey = nodeFactory.newLookupKey(key);
        for (int attempts = 1; ; attempts++) {            // 尝试获取节点；prior 译为先前的；较早的            Node<K, V> prior = data.get(lookupKey);            // 处理不存在的节点            if (prior == null) {                // 如果 node 在循环执行中还未被创建                if (node == null) {                    // NodeFactory 创建对应类型节点                    node = nodeFactory.newNode(key, keyReferenceQueue(), value, valueReferenceQueue(), newWeight, now);                    // 设置节点的过期时间                    setVariableTime(node, expireAfterCreate(key, value, expiry, now));                }                // 尝试添加新节点到缓存中，如果键已存在则返回现有节点                prior = data.putIfAbsent(node.getKeyReference(), node);                // 返回 null 表示插入成功                if (prior == null) {                    // 写后操作：添加 AddTask 并调度执行任务                    afterWrite(new AddTask(node, newWeight));                    return null;                }                // onlyIfAbsent 形参在默认的 put 方法中为 false，以下逻辑简单介绍                // 如果此时有其他线程添加了相同 key 的元素                else if (onlyIfAbsent) {                    // 获取到当前值，尝试判断读后失效策略，更新访问时间，并执行读后操作 afterRead 方法                    V currentValue = prior.getValue();                    if ((currentValue != null) && !hasExpired(prior, now)) {                        if (!isComputingAsync(prior)) {                            tryExpireAfterRead(prior, key, currentValue, expiry(), now);                            setAccessTime(prior, now);                        }                        // 读后操作，该方法在 getIfPresent 中进行讲解                        afterRead(prior, now, /* recordHit */ false);                        return currentValue;                    }                }            } else if (onlyIfAbsent) {                // 同样的逻辑                V currentValue = prior.getValue();                if ((currentValue != null) && !hasExpired(prior, now)) {                    if (!isComputingAsync(prior)) {                        tryExpireAfterRead(prior, key, currentValue, expiry(), now);                        setAccessTime(prior, now);                    }                    afterRead(prior, now, /* recordHit */ false);                    return currentValue;                }            }        }        // ...    }}

abstract class BoundedLocalCache<K, V> extends BLCHeader.DrainStatusRef implements LocalCache<K, V> {
    // 写重试最多 100 次    static final int WRITE_BUFFER_RETRIES = 100;
    static final int WRITE_BUFFER_MIN = 4;    static final int WRITE_BUFFER_MAX = 128 * ceilingPowerOfTwo(NCPU);
    final MpscGrowableArrayQueue<Runnable> writeBuffer = new MpscGrowableArrayQueue<>(WRITE_BUFFER_MIN, WRITE_BUFFER_MAX);
    // 添加写后 Task 到 writeBuffer 中并在合适的时机调度执行任务    void afterWrite(Runnable task) {        // 最多重试添加 100 次        for (int i = 0; i < WRITE_BUFFER_RETRIES; i++) {            if (writeBuffer.offer(task)) {                // 写后调度                scheduleAfterWrite();                return;            }            // 向 writeBuffer 中添加任务失败会调度任务执行            scheduleDrainBuffers();            // 自旋等待，让出 CPU 控制权            Thread.onSpinWait();        }        // ...    }}

abstract class BaseMpscLinkedArrayQueuePad1<E> extends AbstractQueue<E> {    byte p000, p001, p002, p003, p004, p005, p006, p007;    byte p008, p009, p010, p011, p012, p013, p014, p015;    byte p016, p017, p018, p019, p020, p021, p022, p023;    byte p024, p025, p026, p027, p028, p029, p030, p031;    byte p032, p033, p034, p035, p036, p037, p038, p039;    byte p040, p041, p042, p043, p044, p045, p046, p047;    byte p048, p049, p050, p051, p052, p053, p054, p055;    byte p056, p057, p058, p059, p060, p061, p062, p063;    byte p064, p065, p066, p067, p068, p069, p070, p071;    byte p072, p073, p074, p075, p076, p077, p078, p079;    byte p080, p081, p082, p083, p084, p085, p086, p087;    byte p088, p089, p090, p091, p092, p093, p094, p095;    byte p096, p097, p098, p099, p100, p101, p102, p103;    byte p104, p105, p106, p107, p108, p109, p110, p111;    byte p112, p113, p114, p115, p116, p117, p118, p119;}

abstract class BaseMpscLinkedArrayQueueProducerFields<E> extends BaseMpscLinkedArrayQueuePad1<E> {    // 生产者操作索引（并不对应缓冲区 producerBuffer 中索引位置）    protected long producerIndex;}

abstract class BaseMpscLinkedArrayQueueConsumerFields<E> extends BaseMpscLinkedArrayQueuePad2<E> {    // 掩码值，用于计算消费者实际的索引位置    protected long consumerMask;    // 消费者访问这个缓冲区来获取元素消费    protected E[] consumerBuffer;    // 消费者操作索引（并不对应缓冲区 consumerBuffer 中索引位置）    protected long consumerIndex;}

abstract class BaseMpscLinkedArrayQueueColdProducerFields<E> extends BaseMpscLinkedArrayQueuePad3<E> {    // 生产者可以操作的最大索引上限    protected volatile long producerLimit;    // 掩码值，用于计算生产者在数组中实际的索引    protected long producerMask;    // 存储生产者生产的元素    protected E[] producerBuffer;}

class MpscGrowableArrayQueue<E> extends MpscChunkedArrayQueue<E> {
    MpscGrowableArrayQueue(int initialCapacity, int maxCapacity) {        // 调用父类的构造方法        super(initialCapacity, maxCapacity);    }}
abstract class MpscChunkedArrayQueue<E> extends MpscChunkedArrayQueueColdProducerFields<E> {    // 省略字节占位字段...    byte p119;
    MpscChunkedArrayQueue(int initialCapacity, int maxCapacity) {        // 调用父类的构造方法        super(initialCapacity, maxCapacity);    }
}
abstract class MpscChunkedArrayQueueColdProducerFields<E> extends BaseMpscLinkedArrayQueue<E> {    protected final long maxQueueCapacity;
    MpscChunkedArrayQueueColdProducerFields(int initialCapacity, int maxCapacity) {        // 调用父类的构造方法        super(initialCapacity);        if (maxCapacity < 4) {            throw new IllegalArgumentException("Max capacity must be 4 or more");        }        // 保证了最大值最少比初始值大 2 倍        if (ceilingPowerOfTwo(initialCapacity) >= ceilingPowerOfTwo(maxCapacity)) {            throw new IllegalArgumentException(                    "Initial capacity cannot exceed maximum capacity(both rounded up to a power of 2)");        }        // 最大容量也为 2的n次幂        maxQueueCapacity = ((long) ceilingPowerOfTwo(maxCapacity)) << 1;    }}
abstract class BaseMpscLinkedArrayQueue<E> extends BaseMpscLinkedArrayQueueColdProducerFields<E> {
    BaseMpscLinkedArrayQueue(final int initialCapacity) {        if (initialCapacity < 2) {            throw new IllegalArgumentException("Initial capacity must be 2 or more");        }
        // 初始化缓冲区大小为数值最接近的 2 的 n 次幂        int p2capacity = ceilingPowerOfTwo(initialCapacity);        // 掩码值，-1L 使其低位均为 1，左移 1 位则最低位为 0，eg: 00000110，注意该值会被生产者和消费者掩码值共同赋值        long mask = (p2capacity - 1L) << 1;        // 创建一个大小为 2的n次幂 +1 大小的缓冲区，注意这个 buffer 分别被 producerBuffer 和 consumerBuffer 共同引用        E[] buffer = allocate(p2capacity + 1);        // BaseMpscLinkedArrayQueueColdProducerFields 类中相关字段赋值        producerBuffer = buffer;        producerMask = mask;        // 将 producerLimit 值赋为 掩码值        soProducerLimit(this, mask);        // BaseMpscLinkedArrayQueueConsumerFields 类中相关字段赋值        consumerBuffer = buffer;        consumerMask = mask;    }}

abstract class BaseMpscLinkedArrayQueue<E> extends BaseMpscLinkedArrayQueueColdProducerFields<E> {
    private static final Object JUMP = new Object();
    @Override    @SuppressWarnings("MissingDefault")    public boolean offer(final E e) {        if (e == null) {            throw new NullPointerException();        }
        long mask;        E[] buffer;        long pIndex;
        while (true) {            // 生产者最大索引（生产者掩码值），获取 BaseMpscLinkedArrayQueueColdProducerFields 中定义的该字段            long producerLimit = lvProducerLimit();            // 生产者当前索引，初始值为 0，BaseMpscLinkedArrayQueueProducerFields 中字段             pIndex = lvProducerIndex(this);            // producerIndex 最低位用来表示扩容（索引生产者索引 producerIndex 并不对应缓冲区中实际的索引）            // 低位为 1 表示正在扩容，自旋等待直到扩容完成（表示只有一个线程操作扩容）            if ((pIndex & 1) == 1) {                continue;            }
            // 掩码值和buffer可能在扩容中被改变，每次循环使用最新值            mask = this.producerMask;            buffer = this.producerBuffer;
            // 检查是否需要扩容            if (producerLimit <= pIndex) {                int result = offerSlowPath(mask, pIndex, producerLimit);                switch (result) {                    case 0:                        break;                    case 1:                        continue;                    case 2:                        return false;                    case 3:                        resize(mask, buffer, pIndex, e);                        return true;                }            }
            // CAS 操作更新生产者索引，注意这里是 +2，更新成功结束循环            if (casProducerIndex(this, pIndex, pIndex + 2)) {                break;            }        }        // 计算该元素在 buffer 中的实际偏移量，并将其添加到缓冲区中        final long offset = modifiedCalcElementOffset(pIndex, mask);        soElement(buffer, offset, e);        return true;    }
    // 没有将 resize 逻辑封装在该方法中，而是由该方法判断是否需要扩容    private int offerSlowPath(long mask, long pIndex, long producerLimit) {        int result;        // 获取消费者索引 BaseMpscLinkedArrayQueueConsumerFields 类中        final long cIndex = lvConsumerIndex(this);        // 通过掩码值计算当前缓冲区容量        long bufferCapacity = getCurrentBufferCapacity(mask);        result = 0;        // 如果队列还有空间        if (cIndex + bufferCapacity > pIndex) {            // 尝试更新生产者最大限制，更新失败则返回 1 重试            if (!casProducerLimit(this, producerLimit, cIndex + bufferCapacity)) {                result = 1;            }        }        // 如果队列已满且无法扩展        else if (availableInQueue(pIndex, cIndex) <= 0) {            result = 2;        }        // 更新 producerIndex 最低位为 1，成功则进行扩容，否则重试        else if (casProducerIndex(this, pIndex, pIndex + 1)) {            result = 3;        } else {            result = 1;        }        return result;    }
    private void resize(long oldMask, E[] oldBuffer, long pIndex, final E e) {        // 计算新缓冲区大小并创建，2 * (buffer.length - 1) + 1        int newBufferLength = getNextBufferSize(oldBuffer);        final E[] newBuffer = allocate(newBufferLength);
        // 更新缓冲区引用为新的缓冲区        producerBuffer = newBuffer;        // 更新新的掩码        final int newMask = (newBufferLength - 2) << 1;        producerMask = newMask;
        // 计算元素在新旧缓冲区中的偏移量        final long offsetInOld = modifiedCalcElementOffset(pIndex, oldMask);        final long offsetInNew = modifiedCalcElementOffset(pIndex, newMask);
        // 将元素放到新缓冲区中        soElement(newBuffer, offsetInNew, e);        // 将新缓冲区连接到旧缓冲区中        soElement(oldBuffer, nextArrayOffset(oldMask), newBuffer);
        // 校验可用空间        final long cIndex = lvConsumerIndex(this);        final long availableInQueue = availableInQueue(pIndex, cIndex);        if (availableInQueue <= 0) {            throw new IllegalStateException();        }
        // 更新生产者限制大小和生产者索引        soProducerLimit(this, pIndex + Math.min(newMask, availableInQueue));        soProducerIndex(this, pIndex + 2);
        // 将旧缓冲区中该位置的元素更新为 JUMP 标志位，这样在被消费时就知道去新的缓冲区获取了        soElement(oldBuffer, offsetInOld, JUMP);    }
    private long nextArrayOffset(final long mask) {        return modifiedCalcElementOffset(mask + 2, Long.MAX_VALUE);    }
    // 因为最低位用来表示是否在扩容，所以 producerIndex 和 consumerIndex 并不表示实际的索引    // 注意生产者（消费者）操作索引值会随着元素的增加不断变大，因为有它们和掩码值的位与运算才保证了索引值一直在索引值的有效范围内    static long modifiedCalcElementOffset(long index, long mask) {        return (index & mask) >> 1;    }}

abstract class BaseMpscLinkedArrayQueue<E> extends BaseMpscLinkedArrayQueueColdProducerFields<E> {
    static final VarHandle P_INDEX = pIndexLookup.findVarHandle(            BaseMpscLinkedArrayQueueProducerFields.class, "producerIndex", long.class);
    // volatile 可见性保证    static long lvProducerIndex(BaseMpscLinkedArrayQueue<?> self) {        return (long) P_INDEX.getVolatile(self);    }
    // CAS 操作    static boolean casProducerIndex(BaseMpscLinkedArrayQueue<?> self, long expect, long newValue) {        return P_INDEX.compareAndSet(self, expect, newValue);    }}

abstract class BaseMpscLinkedArrayQueue<E> extends BaseMpscLinkedArrayQueueColdProducerFields<E> {
    private static final Object JUMP = new Object();
    public E poll() {        // 读取消费者相关字段 BaseMpscLinkedArrayQueueConsumerFields 类        final E[] buffer = consumerBuffer;        final long index = consumerIndex;        final long mask = consumerMask;
        // 根据消费索引，计算出元素在消费者缓冲区中实际的位置        final long offset = modifiedCalcElementOffset(index, mask);        // 读取该元素（volatile 可见性读取）        Object e = lvElement(buffer, offset);
        // 如果为空        if (e == null) {            // 比较生产者索引，如果两个索引不相等，那么证明两索引间存在距离表示还有元素能够被消费            if (index != lvProducerIndex(this)) {                // 自旋读取元素，直到读到元素                do {                    e = lvElement(buffer, offset);                } while (e == null);            } else {                // 索引相等证明确实是空队列                return null;            }        }        if (e == JUMP) {            // 获取到新缓冲区            final E[] nextBuffer = getNextBuffer(buffer, mask);            // 在新缓冲区中获取到对应元素            return newBufferPoll(nextBuffer, index);        }        // 清除当前索引的元素，表示该元素已经被消费        soElement(buffer, offset, null);        // 更新消费者索引，这里也是 +2，它并不表示实际的在缓冲区的索引        soConsumerIndex(this, index + 2);        return (E) e;    }
    private E[] getNextBuffer(final E[] buffer, final long mask) {        // 如果已经发生扩容，此时 consumerMask 仍然对应的是扩容前的 mask        // 此处与生产者操作扩容时拼接新旧缓冲区调用的是一样的方法，这样便能够获取到新缓冲区的偏移量        final long nextArrayOffset = nextArrayOffset(mask);        // 获取到新缓冲区，因为在扩容操作时已经将新缓冲区链接到旧缓冲区上了        final E[] nextBuffer = (E[]) lvElement(buffer, nextArrayOffset);        // 将旧缓冲区中新缓冲区位置设置为 null 表示旧缓冲区中已经没有任何元素需要被消费了，也不再需要被引用了（能被垃圾回收了）        soElement(buffer, nextArrayOffset, null);        return nextBuffer;    }
    private long nextArrayOffset(final long mask) {        return modifiedCalcElementOffset(mask + 2, Long.MAX_VALUE);    }
    private E newBufferPoll(E[] nextBuffer, final long index) {        // 计算出消费者操作索引在新缓冲区中对应的实际位置        final long offsetInNew = newBufferAndOffset(nextBuffer, index);        // 在新缓冲区中获取到对应元素        final E n = lvElement(nextBuffer, offsetInNew);        if (n == null) {            throw new IllegalStateException("new buffer must have at least one element");        }        // 清除当前索引的元素，表示该元素已经被消费        soElement(nextBuffer, offsetInNew, null);        // 更新消费者索引        soConsumerIndex(this, index + 2);        return n;    }
    private long newBufferAndOffset(E[] nextBuffer, final long index) {        // 将消费者缓冲区引用和掩码值更新        consumerBuffer = nextBuffer;        consumerMask = (nextBuffer.length - 2L) << 1;        return modifiedCalcElementOffset(index, consumerMask);    }
    static long modifiedCalcElementOffset(long index, long mask) {        return (index & mask) >> 1;    }
    static <E> E lvElement(E[] buffer, long offset) {        return (E) REF_ARRAY.getVolatile(buffer, (int) offset);    }}

abstract class BoundedLocalCache<K, V> extends BLCHeader.DrainStatusRef implements LocalCache<K, V> {
    final ReentrantLock evictionLock = new ReentrantLock();    // 默认为 ForkJoinPool.commonPool()    final Executor executor;    // 该任务在创建缓存时已经完成初始化    final PerformCleanupTask drainBuffersTask;
    // 根据状态的变化来调度执行任务    void scheduleAfterWrite() {        // 获取当前 drainStatus，drain 译为排空，耗尽        int drainStatus = drainStatusOpaque();        for (; ; ) {            // 这里的状态机变更需要关注下            switch (drainStatus) {                // IDLE 表示当前无任务可做                case IDLE:                    // CAS 更新状态为 REQUIRED                    casDrainStatus(IDLE, REQUIRED);                    // 调度任务执行                    scheduleDrainBuffers();                    return;                // REQUIRED 表示当前有任务需要执行                case REQUIRED:                    // 调度任务执行                    scheduleDrainBuffers();                    return;                // PROCESSING_TO_IDLE 表示当前任务处理完成后会变成 IDLE 状态                case PROCESSING_TO_IDLE:                    // 又来了新的任务，则 CAS 操作将它更新为 PROCESSING_TO_REQUIRED 状态                    if (casDrainStatus(PROCESSING_TO_IDLE, PROCESSING_TO_REQUIRED)) {                        return;                    }                    drainStatus = drainStatusAcquire();                    continue;                    // PROCESSING_TO_REQUIRED 表示正在处理任务，处理完任务后还有任务需要处理                case PROCESSING_TO_REQUIRED:                    return;                default:                    throw new IllegalStateException("Invalid drain status: " + drainStatus);            }        }    }
    // 调度执行缓冲区中的任务    void scheduleDrainBuffers() {        // 如果状态表示正在有任务处理则返回        if (drainStatusOpaque() >= PROCESSING_TO_IDLE) {            return;        }        // 注意这里要获取同步锁 evictionLock        if (evictionLock.tryLock()) {            try {                // 获取锁后再次校验当前处理状态                int drainStatus = drainStatusOpaque();                if (drainStatus >= PROCESSING_TO_IDLE) {                    return;                }                // 更新状态为 PROCESSING_TO_IDLE                setDrainStatusRelease(PROCESSING_TO_IDLE);                // 同步机制保证任何时刻只能有一个线程能够提交任务                executor.execute(drainBuffersTask);            } catch (Throwable t) {                logger.log(Level.WARNING, "Exception thrown when submitting maintenance task", t);                maintenance(/* ignored */ null);            } finally {                evictionLock.unlock();            }        }    }
}

abstract class BoundedLocalCache<K, V> extends BLCHeader.DrainStatusRef implements LocalCache<K, V> {
    // 可重用的任务，用于执行 maintenance 方法，避免了使用 ForkJoinPool 来包装    static final class PerformCleanupTask extends ForkJoinTask<Void> implements Runnable {        private static final long serialVersionUID = 1L;
        final WeakReference<BoundedLocalCache<?, ?>> reference;
        PerformCleanupTask(BoundedLocalCache<?, ?> cache) {            reference = new WeakReference<BoundedLocalCache<?, ?>>(cache);        }
        @Override        public boolean exec() {            try {                run();            } catch (Throwable t) {                logger.log(Level.ERROR, "Exception thrown when performing the maintenance task", t);            }
            // Indicates that the task has not completed to allow subsequent submissions to execute            return false;        }
        @Override        public void run() {            // 获取到缓存对象            BoundedLocalCache<?, ?> cache = reference.get();            if (cache != null) {                cache.performCleanUp(null);            }        }        // ...    }}

abstract class BoundedLocalCache<K, V> extends BLCHeader.DrainStatusRef implements LocalCache<K, V> {
    final ReentrantLock evictionLock = new ReentrantLock();
    // 执行该任务时，也要获取同步锁，表示任务只能由一个线程来执行    void performCleanUp(@Nullable Runnable task) {        evictionLock.lock();        try {            // 执行维护任务            maintenance(task);        } finally {            evictionLock.unlock();        }        rescheduleCleanUpIfIncomplete();    }
    @GuardedBy("evictionLock")    void maintenance(@Nullable Runnable task) {        // 更新状态为执行中        setDrainStatusRelease(PROCESSING_TO_IDLE);
        try {            // 处理读缓冲区中的任务            drainReadBuffer();
            // 处理写缓冲区中的任务            drainWriteBuffer();            if (task != null) {                task.run();            }
            // 处理 key 和 value 的引用            drainKeyReferences();            drainValueReferences();
            // 过期和驱逐策略            expireEntries();            evictEntries();
            // “增值” 操作，后续重点讲            climb();        } finally {            // 状态不是 PROCESSING_TO_IDLE 或者无法 CAS 更新为 IDLE 状态的话，需要更新状态为 REQUIRED，该状态会再次执行维护任务            if ((drainStatusOpaque() != PROCESSING_TO_IDLE) || !casDrainStatus(PROCESSING_TO_IDLE, IDLE)) {                setDrainStatusOpaque(REQUIRED);            }        }    }}

abstract class BoundedLocalCache<K, V> extends BLCHeader.DrainStatusRef implements LocalCache<K, V> {
    static final int NCPU = Runtime.getRuntime().availableProcessors();
    static final int WRITE_BUFFER_MAX = 128 * ceilingPowerOfTwo(NCPU);
    final MpscGrowableArrayQueue<Runnable> writeBuffer;
    @GuardedBy("evictionLock")    void drainWriteBuffer() {        // 最大循环次数为 writeBuffer 最大容量，直至弹出元素为 null        for (int i = 0; i <= WRITE_BUFFER_MAX; i++) {            Runnable task = writeBuffer.poll();            if (task == null) {                return;            }            task.run();        }        // 更新状态为 PROCESSING_TO_REQUIRED        setDrainStatusOpaque(PROCESSING_TO_REQUIRED);    }}

abstract class BoundedLocalCache<K, V> extends BLCHeader.DrainStatusRef implements LocalCache<K, V> {
    static final long MAXIMUM_CAPACITY = Long.MAX_VALUE - Integer.MAX_VALUE;
    final class AddTask implements Runnable {        final Node<K, V> node;        // 节点权重        final int weight;
        AddTask(Node<K, V> node, int weight) {            this.weight = weight;            this.node = node;        }
        @Override        @GuardedBy("evictionLock")        @SuppressWarnings("FutureReturnValueIgnored")        public void run() {            // 是否指定了驱逐策略            if (evicts()) {                // 更新缓存权重和窗口区权重                setWeightedSize(weightedSize() + weight);                setWindowWeightedSize(windowWeightedSize() + weight);                // 更新节点的 policyWeight，该字段只有在自定了权重计算规则时才有效                // 否则像只定义了固定容量的驱逐策略，使用默认元素权重为 1 是不需要关注该字段的                node.setPolicyWeight(node.getPolicyWeight() + weight);
                // 检测当前总权重是否超过一半的最大容量                long maximum = maximum();                if (weightedSize() >= (maximum >>> 1)) {                    // 如果超过最大容量                    if (weightedSize() > MAXIMUM_CAPACITY) {                        // 执行驱逐操作                        evictEntries();                    } else {                        // 延迟加载频率草图 frequencySketch 数据结构，用于统计元素访问频率                        long capacity = isWeighted() ? data.mappingCount() : maximum;                        frequencySketch().ensureCapacity(capacity);                    }                }
                // 更新频率统计信息                K key = node.getKey();                if (key != null) {                    // 因为频率草图数据结构具有延迟加载机制（权重超过半数）                    // 所以实际上在元素权重还未过半未完成初始化时，调用 increment 是没有作用的                    frequencySketch().increment(key);                }
                // 增加未命中样本数                setMissesInSample(missesInSample() + 1);            }
            // 同步检测节点是否还有效            boolean isAlive;            synchronized (node) {                isAlive = node.isAlive();            }            if (isAlive) {                // 写后过期策略                if (expiresAfterWrite()) {                    writeOrderDeque().offerLast(node);                }                // 过期策略                if (expiresVariable()) {                    timerWheel().schedule(node);                }                // 驱逐策略                if (evicts()) {                    // 如果权重比配置的最大权重大                    if (weight > maximum()) {                        // 执行固定权重（RemovalCause.SIZE）的驱逐策略                        evictEntry(node, RemovalCause.SIZE, expirationTicker().read());                    }                    // 如果权重超过窗口区最大权重，则将其放在窗口区头节点                    else if (weight > windowMaximum()) {                        accessOrderWindowDeque().offerFirst(node);                    }                    // 否则放在窗口区尾节点                    else {                        accessOrderWindowDeque().offerLast(node);                    }                }                // 访问后过期策略                else if (expiresAfterAccess()) {                    accessOrderWindowDeque().offerLast(node);                }            }
            // 处理异步计算            if (isComputingAsync(node)) {                synchronized (node) {                    if (!Async.isReady((CompletableFuture<?>) node.getValue())) {                        long expirationTime = expirationTicker().read() + ASYNC_EXPIRY;                        setVariableTime(node, expirationTime);                        setAccessTime(node, expirationTime);                        setWriteTime(node, expirationTime);                    }                }            }        }    }}

abstract class BoundedLocalCache<K, V> extends BLCHeader.DrainStatusRef implements LocalCache<K, V> {
    final ConcurrentHashMap<Object, Node<K, V>> data;
    @GuardedBy("evictionLock")    @SuppressWarnings({"GuardedByChecker", "NullAway", "PMD.CollapsibleIfStatements"})    boolean evictEntry(Node<K, V> node, RemovalCause cause, long now) {        K key = node.getKey();        @SuppressWarnings("unchecked")        V[] value = (V[]) new Object[1];        boolean[] removed = new boolean[1];        boolean[] resurrect = new boolean[1];        Object keyReference = node.getKeyReference();        RemovalCause[] actualCause = new RemovalCause[1];
        data.computeIfPresent(keyReference, (k, n) -> {            if (n != node) {                return n;            }            synchronized (n) {                value[0] = n.getValue();
                // key 或 value 为 null，这种情况下可能使用了 Caffeine.weakKeys, Caffeine.weakValues, or Caffeine.softValues                // 导致被垃圾回收了                if ((key == null) || (value[0] == null)) {                    // 标记实际失效原因为垃圾回收                     actualCause[0] = RemovalCause.COLLECTED;                }                // 如果原因为垃圾回收，记录 resurrect 复活标记为 true                else if (cause == RemovalCause.COLLECTED) {                    resurrect[0] = true;                    return n;                }                // 否则记录入参中的原因                else {                    actualCause[0] = cause;                }
                // 过期驱逐策略判断                if (actualCause[0] == RemovalCause.EXPIRED) {                    boolean expired = false;                    if (expiresAfterAccess()) {                        expired |= ((now - n.getAccessTime()) >= expiresAfterAccessNanos());                    }                    if (expiresAfterWrite()) {                        expired |= ((now - n.getWriteTime()) >= expiresAfterWriteNanos());                    }                    if (expiresVariable()) {                        expired |= (n.getVariableTime() <= now);                    }                    if (!expired) {                        resurrect[0] = true;                        return n;                    }                }                // 固定容量驱逐策略                else if (actualCause[0] == RemovalCause.SIZE) {                    int weight = node.getWeight();                    if (weight == 0) {                        resurrect[0] = true;                        return n;                    }                }
                // 通知驱逐策略监听器，调用它的方法                notifyEviction(key, value[0], actualCause[0]);                // 将该 key 对应的刷新策略失效                discardRefresh(keyReference);                // 标记该节点被驱逐                removed[0] = true;                // 退休准备被垃圾回收                node.retire();            }            return null;        });
        // 如果复活标记为 true 那么不被移除        if (resurrect[0]) {            return false;        }
        // 节点已经要被驱逐        // 如果在窗口区，那么直接从窗口区移除        if (node.inWindow() && (evicts() || expiresAfterAccess())) {            accessOrderWindowDeque().remove(node);        }        // 如果没在窗口区        else if (evicts()) {            // 在试用区直接在试用区移除            if (node.inMainProbation()) {                accessOrderProbationDeque().remove(node);            }            // 在保护区则直接从保护区移除            else {                accessOrderProtectedDeque().remove(node);            }        }        // 将写后失效和时间轮中关于该节点的元素移除        if (expiresAfterWrite()) {            writeOrderDeque().remove(node);        } else if (expiresVariable()) {            timerWheel().deschedule(node);        }
        // 同步机制将 node 置为 dead        synchronized (node) {            logIfAlive(node);            makeDead(node);        }
        if (removed[0]) {            // 节点被移除监控计数和节点移除通知回调            statsCounter().recordEviction(node.getWeight(), actualCause[0]);            notifyRemoval(key, value[0], actualCause[0]);        }
        return true;    }}

abstract class BoundedLocalCache<K, V> extends BLCHeader.DrainStatusRef implements LocalCache<K, V> {
    static final int MAX_PUT_SPIN_WAIT_ATTEMPTS = 1024 - 1;
    static final long EXPIRE_WRITE_TOLERANCE = TimeUnit.SECONDS.toNanos(1);
    final ConcurrentHashMap<Object, Node<K, V>> data;
    @Nullable    V put(K key, V value, Expiry<K, V> expiry, boolean onlyIfAbsent) {        requireNonNull(key);        requireNonNull(value);
        Node<K, V> node = null;        long now = expirationTicker().read();        int newWeight = weigher.weigh(key, value);        Object lookupKey = nodeFactory.newLookupKey(key);        for (int attempts = 1; ; attempts++) {            Node<K, V> prior = data.get(lookupKey);            if (prior == null) {                // ...             }
            // 元素被读到之后可能已经被驱逐了            if (!prior.isAlive()) {                // 自旋尝试重新从 ConcurrentHashMap 中获取，再获取时如果为 null 则执行新增逻辑                if ((attempts & MAX_PUT_SPIN_WAIT_ATTEMPTS) != 0) {                    Thread.onSpinWait();                    continue;                }                // 如果自旋尝试后元素仍未被删除，校验元素是否处于存活状态                // 如果处于非存活状态，那么可能这个元素已经被破坏，无法被移除，抛出异常                data.computeIfPresent(lookupKey, (k, n) -> {                    requireIsAlive(key, n);                    return n;                });                continue;            }
            V oldValue;            // 新的过期时间            long varTime;            int oldWeight;            boolean expired = false;            boolean mayUpdate = true;            boolean exceedsTolerance = false;            // 为元素加同步锁            synchronized (prior) {                // 如果此时元素已经失效了，那么需要重新循环                if (!prior.isAlive()) {                    continue;                }                oldValue = prior.getValue();                oldWeight = prior.getWeight();                // oldValue 为 null 证明它被垃圾回收器回收了                if (oldValue == null) {                    // 记录元素创建后的过期时间                    varTime = expireAfterCreate(key, value, expiry, now);                    // 驱逐监听器回调                    notifyEviction(key, null, RemovalCause.COLLECTED);                }                // 如果元素已经过期了                else if (hasExpired(prior, now)) {                    // 标记过期标志为 true                    expired = true;                    // 记录元素创建后的过期时间并回调驱逐监听器                    varTime = expireAftexpireAfterCreateerCreate(key, value, expiry, now);                    notifyEviction(key, oldValue, RemovalCause.EXPIRED);                }                // onlyInAbsent 为 true 时不会对已存在 key 的值进行修改                else if (onlyIfAbsent) {                    mayUpdate = false;                    // 记录元素读后过期时间                    varTime = expireAfterRead(prior, key, value, expiry, now);                } else {                    // 记录元素修改后过期时间                    varTime = expireAfterUpdate(prior, key, value, expiry, now);                }
                // 需要修改原有 key 的 value 值                if (mayUpdate) {                    exceedsTolerance =                            // 配置了写后过期策略且已经超过写后时间的容忍范围                            (expiresAfterWrite() && (now - prior.getWriteTime()) > EXPIRE_WRITE_TOLERANCE)                                    // 或者配置了可变时间过期策略同样判断是否超过时间的容忍范围                                    || (expiresVariable() && Math.abs(varTime - prior.getVariableTime()) > EXPIRE_WRITE_TOLERANCE);
                    // 更新值，更新权重，更新写时间                    prior.setValue(value, valueReferenceQueue());                    prior.setWeight(newWeight);                    setWriteTime(prior, now);
                    // 写后刷新策略失效                    discardRefresh(prior.getKeyReference());                }
                // 更新过期时间                setVariableTime(prior, varTime);                // 更新访问时间                setAccessTime(prior, now);            }
            // 根据不同的情况回调不同的监听器            if (expired) {                notifyRemoval(key, oldValue, RemovalCause.EXPIRED);            } else if (oldValue == null) {                notifyRemoval(key, /* oldValue */ null, RemovalCause.COLLECTED);            } else if (mayUpdate) {                notifyOnReplace(key, oldValue, value);            }
            // 计算写后权重变化            int weightedDifference = mayUpdate ? (newWeight - oldWeight) : 0;            // 如果 oldValue 已经被回收 或 权重修改前后发生变更 或 已经过期，添加更新任务            if ((oldValue == null) || (weightedDifference != 0) || expired) {                afterWrite(new UpdateTask(prior, weightedDifference));            }            // 如果超过了时间容忍范围，添加更新任务            else if (!onlyIfAbsent && exceedsTolerance) {                afterWrite(new UpdateTask(prior, weightedDifference));            } else {                // 没有超过时间容忍范围，更新写时间                if (mayUpdate) {                    setWriteTime(prior, now);                }                // 处理读后操作                afterRead(prior, now, /* recordHit */ false);            }
            return expired ? null : oldValue;        }    }}

abstract class BoundedLocalCache<K, V> extends BLCHeader.DrainStatusRef implements LocalCache<K, V> {
    final ReentrantLock evictionLock;
    void afterWrite(Runnable task) {        // 这段逻辑我们在看 AddTask 的逻辑时已经看过了，所以略过        for (int i = 0; i < WRITE_BUFFER_RETRIES; i++) {            if (writeBuffer.offer(task)) {                scheduleAfterWrite();                return;            }            scheduleDrainBuffers();            Thread.onSpinWait();        }
        // 以下逻辑用于解决在重试了 100 次后仍然写入失败的问题，它会尝试获取 evictionLock 同步锁        // 直接同步执行“维护”方法并执行当前任务，但是它并无法解决某个写入操作执行时间很长的问题        // 发生这种情况的原因可能是由于执行器的所有线程都很忙（可能是写入此缓存），写入速率大大超过了消耗速率，优先级反转，或者执行器默默地丢弃了维护任务        lock();        try {            maintenance(task);        } catch (RuntimeException e) {            logger.log(Level.ERROR, "Exception thrown when performing the maintenance task", e);        } finally {            evictionLock.unlock();        }        // 重新调度异步维护任务，确保维护操作能及时执行        rescheduleCleanUpIfIncomplete();    }
    void lock() {        long remainingNanos = WARN_AFTER_LOCK_WAIT_NANOS;        long end = System.nanoTime() + remainingNanos;        boolean interrupted = false;        try {            for (;;) {                try {                    if (evictionLock.tryLock(remainingNanos, TimeUnit.NANOSECONDS)) {                        return;                    }                    logger.log(Level.WARNING, "The cache is experiencing excessive wait times for acquiring "                            + "the eviction lock. This may indicate that a long-running computation has halted "                            + "eviction when trying to remove the victim entry. Consider using AsyncCache to "                            + "decouple the computation from the map operation.", new TimeoutException());                    evictionLock.lock();                    return;                } catch (InterruptedException e) {                    remainingNanos = end - System.nanoTime();                    interrupted = true;                }            }        } finally {            if (interrupted) {                Thread.currentThread().interrupt();            }        }    }
    // 调用同步的维护方法时，可能发生获取锁超时，那么再重新开启一个异步维护调度    void rescheduleCleanUpIfIncomplete() {        // 校验是否有任务需要被执行        if (drainStatusOpaque() != REQUIRED) {            return;        }
        // 默认线程池调度任务执行，这个方法我们在上文中已经详细介绍过        if (executor == ForkJoinPool.commonPool()) {            scheduleDrainBuffers();            return;        }
        // 如果自定义了线程池，那么会使用自定义的线程池进行处理        var pacer = pacer();        if ((pacer != null) && !pacer.isScheduled() && evictionLock.tryLock()) {            try {                if ((drainStatusOpaque() == REQUIRED) && !pacer.isScheduled()) {                    pacer.schedule(executor, drainBuffersTask, expirationTicker().read(), Pacer.TOLERANCE);                }            } finally {                evictionLock.unlock();            }        }    }}

abstract class BoundedLocalCache<K, V> extends BLCHeader.DrainStatusRef implements LocalCache<K, V> {
    final class UpdateTask implements Runnable {        final int weightDifference;        final Node<K, V> node;
        public UpdateTask(Node<K, V> node, int weightDifference) {            this.weightDifference = weightDifference;            this.node = node;        }
        @Override        @GuardedBy("evictionLock")        public void run() {            // 写后过期和自定义过期逻辑            if (expiresAfterWrite()) {                reorder(writeOrderDeque(), node);            } else if (expiresVariable()) {                timerWheel().reschedule(node);            }            // 指定了驱逐策略            if (evicts()) {                // 变更节点权重                int oldWeightedSize = node.getPolicyWeight();                node.setPolicyWeight(oldWeightedSize + weightDifference);                // 如果是窗口区节点                if (node.inWindow()) {                    // 更新窗口区权重                    setWindowWeightedSize(windowWeightedSize() + weightDifference);                    // 节点权重超过最大权重限制，直接驱逐                    if (node.getPolicyWeight() > maximum()) {                        evictEntry(node, RemovalCause.SIZE, expirationTicker().read());                    }                    // 节点权重比窗口区最大值小                    else if (node.getPolicyWeight() <= windowMaximum()) {                        onAccess(node);                    }                    // 窗口区包含该节点且该节点的权重大于窗口最大权重，则放到头节点                    else if (accessOrderWindowDeque().contains(node)) {                        accessOrderWindowDeque().moveToFront(node);                    }                }                // 如果是试用区节点                else if (node.inMainProbation()) {                    // 节点权重比最大权重限制小                    if (node.getPolicyWeight() <= maximum()) {                        onAccess(node);                    }                    // 否则将该节点驱逐                    else {                        evictEntry(node, RemovalCause.SIZE, expirationTicker().read());                    }                }                // 如果是保护区节点                else if (node.inMainProtected()) {                    // 更新保护区权重                    setMainProtectedWeightedSize(mainProtectedWeightedSize() + weightDifference);                    // 同样的逻辑                    if (node.getPolicyWeight() <= maximum()) {                        onAccess(node);                    } else {                        evictEntry(node, RemovalCause.SIZE, expirationTicker().read());                    }                }
                // 更新缓存权重大小                setWeightedSize(weightedSize() + weightDifference);                // 更新完成后超过最大权重限制执行驱逐操作                if (weightedSize() > MAXIMUM_CAPACITY) {                    evictEntries();                }            }            // 配置了访问后过期            else if (expiresAfterAccess()) {                onAccess(node);            }        }    }
    @GuardedBy("evictionLock")    void onAccess(Node<K, V> node) {        if (evicts()) {            K key = node.getKey();            if (key == null) {                return;            }            // 更新访问频率            frequencySketch().increment(key);            // 如果节点在窗口区，则将其移动到尾节点            if (node.inWindow()) {                reorder(accessOrderWindowDeque(), node);            }            // 在试用区的节点执行 reorderProbation 方法，可能会将该节点从试用区晋升到保护区            else if (node.inMainProbation()) {                reorderProbation(node);            }            // 否则移动到保护区的尾结点            else {                reorder(accessOrderProtectedDeque(), node);            }            // 更新命中量            setHitsInSample(hitsInSample() + 1);        }        // 配置了访问过期策略        else if (expiresAfterAccess()) {            reorder(accessOrderWindowDeque(), node);        }        // 配置了自定义时间过期策略        if (expiresVariable()) {            timerWheel().reschedule(node);        }    }
    static <K, V> void reorder(LinkedDeque<Node<K, V>> deque, Node<K, V> node) {        // 如果节点存在，将其移动到尾结点        if (deque.contains(node)) {            deque.moveToBack(node);        }    }
    @GuardedBy("evictionLock")    void reorderProbation(Node<K, V> node) {        // 检查试用区是否包含该节点，不包含则证明已经被移除，则不处理        if (!accessOrderProbationDeque().contains(node)) {            return;        }        // 检查节点的权重是否超过保护区最大值        else if (node.getPolicyWeight() > mainProtectedMaximum()) {            // 如果超过，将该节点移动到 试用区 尾巴节点，保证超重的节点不会被移动到保护区            reorder(accessOrderProbationDeque(), node);            return;        }
        // 更新保护区权重大小        setMainProtectedWeightedSize(mainProtectedWeightedSize() + node.getPolicyWeight());        // 在试用区中移除该节点        accessOrderProbationDeque().remove(node);        // 在保护区尾节点中添加        accessOrderProtectedDeque().offerLast(node);        // 将该节点标记为保护区节点        node.makeMainProtected();    }}