принцип реализации кофеина (анализ исходного кода)

Java

предисловие

В последней статье были представлены часто используемые фреймворки кэширования, и мы узнали, что лучший фреймворк кэширования памяти — это Caffeine.

В этой статье подробно объясняется принцип внутренней реализации Caffeine на исходном уровне, включая следующее содержание.

  • Стратегия ликвидации tinyLFU
  • Отношения внутреннего интерфейса кофеина
  • Атомарность нагрузки ставит недействительные операции
  • Анализ политики истечения срока действия кэша

Алгоритм удаления кеша

Роль алгоритма устранения кеша заключается в том, чтобы определить, какие данные будут повторно использоваться в течение короткого периода времени в рамках ограниченных ресурсов, тем самым повышая частоту попаданий в кеш.

LRU (Least Recently Used)

Алгоритм считает, что данные, к которым недавно обращались, будут иметь более высокую вероятность доступа в будущем, обычноРеализовано с использованием связанного списка

Если данные добавляются или к ним осуществляется доступ, переместите данные в начало связанного списка,Голова связанного списка — это горячие данные, а хвост — холодные данные., когда данные заполнены, хвостовые данные удаляются

Его реализация относительно проста, но и доставляет некоторые проблемы.Обход данных приведет к резкому падению частоты попаданий LRU., загрязнение кеша более серьезно

Алгоритм LRU не бесполезен, онХорошо работает при резком трафике

LFU (Least FrequentlyUsed)

Алгоритм основан на данныхИсторическая частота доступа для отсеивания данных, основная идея такова: если к данным обращались много раз в прошлом, в будущем к ним будут обращаться чаще.

По задумке LFU, если вы хотите реализовать этот алгоритм,Необходимо поддерживать дополнительный набор логики для подсчета количества посещений каждого элемента, приведет к пустой трате ресурсов памяти

FIFO (First In First Out)

Обдумывание в порядке поступления, определение времени хранения,Данные, которые наиболее далеки от настоящего, будут удалены в первую очередь., относительно прост в реализации

TinyLFU

Caffeine использует алгоритм, сочетающий в себе преимущества LRU и LFU:Особенности W-TinyLFU: высокая частота попаданий, низкое использование памяти

Прежде чем разбираться в алгоритме W-TinyLFU, сначала разберитесь с алгоритмом TinyLFU.

Цель TinyLFU — решить проблему большого объема памяти в традиционном алгоритме LFU., который также основан на алгоритме LFU

это может быть вЗамена части статистики данных LFU в сценарии большого объема трафика, принцип чем-то похож на BloomFilter (фильтр Блума)

Теперь, когда мы говорим о фильтре Блума, давайте поговорим о его принципе.

БлумФильтрБольшой битовый массив используется для хранения тегов всех ключей, и каждый ключ сопоставляется с соответствующими битами битового массива с помощью нескольких вычислений хэш-модуля.

Если ключ существует, установите соответствующий бит в 1, чтобы его можно было передать черезНебольшой объем памяти для фильтрации большого количества данных

Фильтр Блума не может точно определить, должен ли ключ существовать, но он не должен существовать, если он не существует.

Партнеры, которые поняли принцип hashmap, отреагировали, то есть два разных ключа могут получить один и тот же хэш-слот по модулю путем хеширования.

В кэширующих приложениях большеИспользуйте его для решения проблемы проникновения в кеш

TinyLFUОн обрабатывает несколько битов как единое целое, которое используется для подсчета частоты использования ключа.

Ключ сопоставляется с несколькими разными битами посредством нескольких различных хеш-вычислений, а минимальное значение сопоставления берется как частота использования ключа при чтении.

В Caffeine поддерживается 4-битный CountMinSketch для записи частоты использования ключа.

4-битный означает, что максимальная частота использования статистического ключа равна 15. Конкретную логику реализации см. в классе FrequencySketch в исходном коде.

Как показано на рисунке выше, информация описания класса FrequencySketch четко объяснена.

Максимальная частота ограничена 15 (4 бита), а периодический процесс старения вдвое снижает популярность всех элементов.

Когда TinyLFU имеет дело с пакетным трафиком, он может не собрать достаточно данных о частоте вовремя, чтобы убедиться, что они находятся в кеше, что приведет к снижению частоты попаданий кеша.Чтобы решить эту проблему, алгоритм W-TinyLFU был развит.

W-TinyLFU

W-TinyLFU отОконный кеш и основной кеш состоят из двух частей., а также стратегию кэширования, принятую Caffeine

В основном кэше используются стратегии утилизации SLRU и TinyLFU., занимающий 99% всего кеша

Кэш окна использует алгоритм LRU без какой-либо стратегии повторного использования., доля общего кеша составляет 1%, а оконный кеш используется для решения проблемы всплеска трафика

Caffeine может динамически изменять размер окон и основного пространства в зависимости от характеристик рабочей нагрузки.

кеш окна

Кэш окна состоит из двух частей: большого окна и маленького окна.

Если новое окно с высокой частотой данных более популярно, то кеш малого окна с новой частотой данных более популярен.

основной кеш

Основной кеш состоит из двух частей: Probation и Protected.

Пробация используется для хранения относительно холодных данных, занимающих 20% пространства основного кеша.

Защищенный используется для хранения горячих данных, он занимает 80% пространства основного кэша

Данные могут передаваться друг другу в этих двух частях пространства

Процесс удаления кеша:

Недавно добавленные данные сначала помещаются в кеш окна, и если кеш окна заполнен, данные (кандидаты) удаляются из кеша окна.

Перенести в основной тайник Зону пробации, если Зона пробации тоже заполнена, удалить данные (жертву) из Зоны пробации

Затем кандидаты и жертвы решают остаться или остаться в зависимости от частоты посещений, зарегистрированных TinyFLU.

В частности, вы можете просмотреть метод accept класса BoundedLocalCache в среде Caffeine, как показано на рисунке.

ступенчатая логика

1. Сначала получите частоту доступа кандидатов и жертв.

2. Судя по тому, что кандидат больше жертвы, жертва будет устранена, иначе она пойдет вниз

3. Судя по тому, что частота посещения кандидата меньше или равна 5, кандидат отсеивается, в противном случае опускаемся

4. Если ни один из них не будет установлен, они будут удалены случайным образом.

Отношения внутреннего интерфейса кофеина

Диаграмма классов UML кофеина

При просмотре исходного кода можно сначала найти зависимости фреймворка, а затем просмотреть диаграмму классов UML через идею, что позволяет наглядно увидеть взаимосвязь между интерфейсами и классами

Можно обнаружить, что в исходном коде Caffeine есть два пакета и два класса. Конкретная логика реализации находится под пакетом кеша. Откройте диаграмму классов UML этого пакета через идею.

Выберите способ 1:1, чтобы видеть более четко

На класс со всеми именами классов, набранными сплошной синей линией в верхнем регистре, можно не обращать внимания. На самом деле это динамически сгенерированный класс. Основное внимание уделяется конкретной реализации трех интерфейсов верхнего уровня: Cache, LocalCache и AsyncLoadingCache.

Исходный код сборки Caffeine

При сборке кэша Caffeine он строится через метод сборки, и какой метод загрузки используется, также различается по методу сборки

Итак, нам нужно посмотреть, как реализован метод сборки.

Первый шаг: откройте класс Caffeine, чтобы просмотреть метод сборки.

Из класса Caffeine мы можем обнаружить, что эта сборка представляет собой перегруженный метод, и есть две реализации, которые могут передавать параметры и не передавать параметры.

Давайте сначала посмотрим на содержимое метода сборки без параметров, который сопровождается тернарным оператором и, наконец, возвращает конкретно созданный экземпляр класса реализации.

Для чего используются эти классы реализации?Давайте сначала посмотрим на диаграмму основных классов Caffeine, чтобы получить общее представление о взаимосвязях внутреннего интерфейса Caffeine.

Вы можете видеть, что сначала есть класс с именем Cache, а затем мы находим Cache через диаграмму классов UML, которую мы только что открыли, и нажимаем F4, чтобы войти в класс Cache.

Cache

Кэш — это интерфейс, который в основном предоставляет определения некоторых методов.

LoadingCache

Затем снова взглянем на интерфейс LoadingCache.

LoadingCache наследуется от интерфейса Cache и расширяет три метода: get, getAll, refresh.

Можно проанализировать, что интерфейс Cache больше похож на карту, используемую для хранения значения k.

LoadingCache определяет механизм загрузки и обновления, а определенные записи в нем обрабатываются с помощью CacheLoader, передаваемого методом сборки.

LocalManualCache

Потом смотрим LocalManualCache, он же наследует интерфейс Cache

Интерфейс LocalManualCache в основном имеет два класса реализации UnboundedLocalManualCache и BoundedLocalManualCache.

UnboundedLocalManualCache

Если стратегия повторного использования не настроена, будет использоваться UnboundedLocalManualCache, который также обеспечивает минимальную функцию кэширования.

Как видно из конструктора, он инициализирует ConcurrentHashMap с емкостью 16, а также предоставляет базовые счетчики состояний, удаляет прослушиватели и писатели.

Поскольку у него нет какой-либо активной стратегии утилизации, он по существу работает с ConcurrentHashMap.

BoundedLocalManualCache

Это реализация кеша со стратегией рециркуляции, для Caffeine с набором стратегии рециркуляции она будет соответствовать определенному классу реализации, который реализован LocalCacheFactory.

Вы можете видеть, что в нем есть только один метод newBoundedLocalCache.

Этот метод объединяет строку для каждого варианта нашей конфигурации и, наконец, получает соответствующийРеализовать полное имя класса и загрузить его через загрузчик классов

Поднятие тяжестей также написано, потому чтоКофеин оптимизирован для любой ситуации, и именно так диаграммы классов UML, созданные в соответствии с упомянутой выше идеей, получаются из всех имен классов, написанных с заглавной буквы.

В конечном итоге он вернет BoundedLocalCache, который является классом реализации, который мы в конечном итоге будем использовать.

Классификация кэша кофеина

отсинхронный к асинхронному,ручная загрузка в автоматическую загрузку,От ограниченного до неограниченногоЭти три измерения можно условно разделить на восемь типов кеша.

Атомарность кофеиновых операций

Операции загрузки, установки и аннулирования Caffeine являются атомарными, что означает, чтоЭти три операции взаимоисключающие

Загрузка и установка не могут выполняться одновременно, а загрузка и недействительность не могут выполняться одновременно.Преимущество этого заключается в том, что результат может быть точно таким, как ожидалось.

Этот способ отличается от Гуавы,Гуава не блокирует

Предположим, что сначала вызывается загрузка, а затем вызывается невалидация. Вскоре выполняется инвалидация. В это время загрузка еще не загружена, и результат выполнения не такой, как ожидалось.

Концепция может быть более абстрактной, продемонстрируем это на примере.

Пример гуавы

@SneakyThrows
public static void main(String[] args) {
    LoadingCache<String, String> cache = CacheBuilder.newBuilder()
        .maximumSize(5)
        .expireAfterWrite(10, TimeUnit.MINUTES)
        .build(new CacheLoader<String, String>() {
            @SneakyThrows
            @Override
            public String load(String id) {
                // 加载时,睡眠一秒
                Thread.sleep(1000);
                return id + System.currentTimeMillis();
            }
        });

    // 异步线程加载
    new Thread(() -> {
        try {
            System.out.println("执行get");
            cache.get("key");
        } catch (ExecutionException e) {
            e.printStackTrace();
        }
    }).start();

    // 异步线程移除
    new Thread(() -> {
        // 睡眠,让这个线程后执行
        try {
            Thread.sleep(200);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("执行invalidate");
        cache.invalidate("key");
    }).start();

    // 按程序逻辑来说,我们应该拿到的结果是空map
    Thread.sleep(1200);
    System.out.println(cache.asMap());
}

Видно, что в случае многопоточности, даже если после вызова get вызывается метод invalidate, ключ не удаляется, и результат выполнения не соответствует ожидаемому.

Пример кофеина

@SneakyThrows
public static void main(String[] args) {
    LoadingCache<String, String> cache = Caffeine.newBuilder()
        .maximumSize(5)
        .expireAfterWrite(10, TimeUnit.MINUTES)
        .build(key -> {
            // 加载时,睡眠一秒
            Thread.sleep(1000);
            return key + System.currentTimeMillis();
        });

    // 异步线程加载
    new Thread(() -> {
        System.out.println("执行get");
        cache.get("key");
    }).start();

    // 异步线程移除
    new Thread(() -> {
        // 睡眠,让这个线程后执行
        try {
            Thread.sleep(200);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("执行invalidate");
        cache.invalidate("key");
    }).start();

    // 按程序逻辑来说,我们应该拿到的结果是空map
    Thread.sleep(1200);
    System.out.println(cache.asMap());
}

Видно, что при использовании Caffeine даже в случае многопоточного выполнения результаты выполнения могут гарантированно соответствовать ожиданиям.

Принцип реализации Caffeine для обеспечения атомарности на самом деле очень прост, а его хранилище использует ConcurrentHashMap.

Используя блокировку узла ConcurrentHashMap, операция аннулирования соответствует методу удаления.

Анализ политики истечения срока действия кэша кофеина

Caffeine имеет три стратегии истечения срока действия.Далее давайте проанализируем, как Caffeine активно выполняет переработку кеша.

Откройте класс BoundedLocalCache, чтобы увидеть методы afterRead и afterWrite.

Вы можете видеть, что оба метода afterRead и afterWrite вызывают метод scheduleDrainBuffers.

Давайте еще раз взглянем на метод scheduleDrainBuffers.

Специфическая функция этого метода фактически используется для планирования задач с истекшим сроком действия Мы видим, что его реализация имеет операцию блокировки.

После успешной блокировки через пул потоков будет вызвана задача стокбуферстаск, а класс, к которому принадлежит дренбафферстаск, — PerformCleanupTask

Мы можем еще раз взглянуть на метод запуска, реализованный в PerformCleanupTask.

Вы можете видеть, что метод PerformCleanUp вызывается через кеш в методе run, нажмите и посмотрите конкретную реализацию метода PerformCleanUp.

Вы можете видеть, что метод PerformCleanUp блокируется и разблокируется при вызове метода обслуживания, а затем щелкните, чтобы просмотреть конкретную реализацию метода обслуживания.

В этом методе есть много методов, и эти методы используются для конкретной переработки.

void maintenance(@Nullable Runnable task) {
    lazySetDrainStatus(PROCESSING_TO_IDLE);

    try {
      // 读缓存用尽了
      drainReadBuffer();

      // 写缓存用尽了
      drainWriteBuffer();
      if (task != null) {
        task.run();
      }
        
      // key的引用用尽了
      drainKeyReferences();
      // value的引用用尽了
      drainValueReferences();

      // 达到过期时间了
      expireEntries();
      // 达到大小的限制了
      evictEntries();

      climb();
    } finally {
      if ((drainStatus() != PROCESSING_TO_IDLE) || !casDrainStatus(PROCESSING_TO_IDLE, IDLE)) {
        lazySetDrainStatus(REQUIRED);
      }
    }
  }
Категории