Углубленная расшифровка кеша из будущего - Caffeine

Java задняя часть алгоритм

1. Введение

Прежде чем читать эту статью, я надеюсь, вы хорошо ее прочитали:История эволюции кеша, которую вы должны знатьиКак спроектировать и использовать кеш изящно?. Эти две статьи в основном знакомят вас с тем, как использовать кеш из реального боя. В обеих статьях я рекомендую Caffeine, локальный кеш, вместо вашего Guava Cache. В этой статье я расскажу о конкретных функциях кэша Caffeine, а также о внутреннем принципе реализации, чтобы все знали, что это такое и зачем это нужно. Некоторые люди спросят: Я не использую Caffeine Эта статья не должна быть мне полезна, не волнуйтесь, знание Caffeine определенно поможет вам в разработке другого кода. Конечно, перед введением я все же должен опубликовать несколько сравнительных фотографий его и других тайников:

Видно, что Caffeine в принципе выше других кэшей по всем параметрам.Не много чепухи, давайте сначала посмотрим, как его использовать.

1.1 Как использовать

Caffeine относительно прост в использовании, а API соответствует Guava Cache:

public static void main(String[] args) {
        Cache<String, String> cache = Caffeine.newBuilder()
                .expireAfterWrite(1, TimeUnit.SECONDS)
                .expireAfterAccess(1,TimeUnit.SECONDS)
                .maximumSize(10)
                .build();
        cache.put("hello","hello");
    }

2. Введение в принцип кофеина

2.1W-TinyLFU

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

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

Возвращаясь к LRU, наш LRU не так уж и бесполезен, LRU отлично справляется с ситуацией всплеска трафика, потому что ему не нужно накапливать частоту данных.

Итак, W-TinyLFU сочетает в себе LRU и LFU, а также некоторые особенности других алгоритмов.

2.1.1 Запись частоты

Первое, о чем нужно поговорить, это проблема записи частоты, цель, которую мы хотим достичь, это использовать ограниченное пространство для записи частоты доступа, которая меняется во времени. Мы используем Count-Min Sketch в W-TinyLFU для записи частоты посещений, что также является вариантом фильтра Блума. Как показано ниже:

Если нам нужно записать значение, то нам нужно хэшировать его с помощью нескольких алгоритмов хеширования, а затем добавить к записи соответствующего алгоритма хеширования 1. Зачем нам нужно несколько алгоритмов хеширования? Так как это алгоритм сжатия, конфликты обязательно возникнут.Например, мы создаем массив Long и вычисляем хэш-позицию каждого данных. Например, Чжан Сан и Ли Си могут иметь одинаковое хеш-значение. Например, если они оба равны 1, позиция Long[1] увеличит соответствующую частоту. Чжан Сан посещает 10 000 раз, а Ли Си посещает один раз. Long[1] 1] Эта позиция равна 10 001. Если вы возьмете показатель посещаемости Ли Си, это будет 10 001. Однако имя Ли Си было посещено только один раз. Чтобы решить эту проблему, можно использовать множественный алгоритм хеширования. следует понимать как понятие длинного [][] двумерного массива.Например, в первом алгоритме Чжан Сан и Ли Си конфликтуют, а во втором и третьем велика вероятность того, что конфликта нет, такие как Алгоритм имеет вероятность конфликта около 1%, а вероятность конфликта между четырьмя алгоритмами составляет 1% в четвертой степени. В этом режиме, когда мы берем частоту посещений Li Si, мы берем количество посещений Li Si с самой низкой частотой среди всех алгоритмов. Значит, его зовут Граф-Мин Скетч.

Вот сравнение с предыдущим, вот простой пример: если хэш-карта записывает эту частоту, если у меня есть 100 данных, то этот хэш-карта должен хранить 100 частот доступа к этим данным. Даже если емкость моего кеша равна 1, из-за правил Lfu я все равно должен записывать частоту доступа этих 100 штук данных. Если есть больше данных, у меня больше записей.

В Count-Min Sketch позвольте мне прямо рассказать о реализации в caffeine (в классе FrequencySketch), если размер вашего кеша равен 100, он сгенерирует длинный массив, размер которого является ближайшей степенью от 2 до 100. , то есть 128 . И этот массив будет записывать нашу частоту обращения. Максимальная частота, указанная в кофеине, равна 15, двоичные биты 15 равны 1111, всего 4 бита, а тип Long — 64 бита. Таким образом, каждый тип Long может поставить 16 алгоритмов, но кофеин этого не делает, используются только четыре алгоритма хеширования, каждый тип Long делится на четыре сегмента, и каждый сегмент хранит частоты четырех алгоритмов. Преимущество этого заключается в том, что конфликт хэшей может быть дополнительно уменьшен, и исходный хеш размером 128 становится 128X4.

Структура лонга выглядит следующим образом:

Наши 4 сегмента разделены на A, B, C, D, которые я буду называть позже. А четыре алгоритма в каждом сегменте я ему называю s1, s2, s3, s4. Вот пример: что мне делать, если я хочу добавить цифровую частоту с доступом к 50? Здесь мы используем size=100 в качестве примера.

  1. Сначала определите, в каком сегменте находится хеш 50. С помощью хеш & 3 (двоичное число 3 равно 11) должно быть получено число меньше 4. Предполагая, что хэш & 3 = 0, он находится в сегменте A.
  2. Используйте другие алгоритмы хеширования, чтобы снова хешировать хэш 50, чтобы получить позицию длинного массива, которая является позицией в массиве длиной 128. Предположим, что алгоритм s1 получает 1, алгоритм s2 получает 3, алгоритм s3 получает 4 и алгоритм s4 получает 0.
  3. Поскольку алгоритм S1 получает 1, позиция s1 в сегменте A длинного [1] равна +1, что обозначается как 1As1 плюс 1, затем 3As2 плюс 1, 4As3 плюс 1 и 0As4 плюс 1.

В это время некоторые люди зададутся вопросом, не слишком ли мала максимальная частота 15? В этом алгоритме не имеет значения, например, размер равен 100. Если он увеличит размер *10 глобально, то есть в 1000 раз, он будет глобально делиться на 2 до распада.После распада он может продолжают расти.Этот алгоритм доказан в документе W-TinyLFU.Он может лучше адаптироваться к частоте доступа периода времени.

2.2 Производительность чтения и записи

В кэше гуавы мы сказали, что его операции чтения и записи смешаны с обработкой времени истечения срока действия, то есть вы также можете выполнять операцию исключения в операции размещения, поэтому его производительность чтения и записи будет в определенной степени затронута. Вы можете видеть изображение выше. Кофеин разрывает кеш гуавы при операциях чтения и записи. В основном потому, что в кофеине работа с этими событиями осуществляется через асинхронную операцию, и он отправляет события в очередь.Структура данных очереди здесь RingBuffer.Если вам непонятно, вы можете прочитать эту статью.Высокопроизводительный деструктор очередей без блокировки, о котором вы должны знать. Затем он будет использовать ForkJoinPool.commonPool() по умолчанию или самостоятельно настроить пул потоков, выполнить операцию извлечения из очереди, а затем выполнить последующие операции исключения и истечения срока действия.

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

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

2.3 Стратегия устранения данных

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

  • Очередь Эдема: В кофеине оговорено, что она может составлять только %1 от емкости кеша, если size=100, то эффективный размер этой очереди равен 1. Вновь поступившие данные записываются в эту очередь, чтобы предотвратить устранение всплесков трафика из-за отсутствия частоты доступа ранее. Например, когда запускается новая драма, в начале фактически нет частоты доступа, чтобы предотвратить ее удаление другими кэшами после того, как она выйдет в сеть и присоединится к этой области. Иденский район, самый благоустроенный и благоустроенный район, здесь трудно исключить другими данными.

  • Очередь на пробацию: она называется очередью на пробацию.В этой очереди это означает, что ваши данные относительно холодные и скоро будут удалены. Эффективный размер равен размеру минус eden минус защищенный.

  • Защищенная очередь: в этой очереди вы можете быть уверены, что вы не будете временно исключены, но не волнуйтесь, если в очереди пробации нет данных или защищенные данные заполнены, вы также столкнетесь с неловкой ситуацией исключения. Конечно, если вы хотите стать этой очередью, вам нужно один раз получить доступ к испытательному сроку, и она будет повышена до защищенной очереди. Этот эффективный размер равен (размер минус eden) X 80%. Если размер = 100, будет 79.

Три очереди связаны следующим образом:

  1. Все новые данные попадают в Eden.
  2. Иден заполнен и исключен на испытательный срок.
  3. Если к одному из данных обращаются в испытательном сроке, данные обновляются до защищенных.
  4. Если Protected заполнен, он будет по-прежнему понижен до Probation.

Когда произойдет удаление данных, они будут исключены из испытательного срока. Голова очереди данных в этой очереди будет называться жертвой.Этот глава очереди должен войти первым.По алгоритму LRU очереди он должен быть фактически устранен,но здесь его можно назвать только Жертва Эта очередь Это очередь на условный срок, и представитель собирается казнить его. Здесь хвост очереди называется кандидатом, также называемым злоумышленником. Здесь жертва будет ПК с нападающим, чтобы решить, кого нам следует устранить.

С помощью частотных данных, записанных в нашем эскизе Count-Min, делаются следующие выводы:

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

3. Функциональный анализ кофеина

В Caffeine много функций, давайте разберем, как работают эти API?

3.1 Расцветает сто цветов - Cache Factory

В Caffeine есть класс LocalCacheFactory, который создаст определенный кэш в соответствии с вашей конфигурацией.

Видно, что он соберет строку в зависимости от того, настроили ли вы время истечения, уберете listener и другие параметры и, наконец, сгенерирует конкретный Кэш в соответствии со строкой.Кэшей здесь слишком много, а авторский исходник напрямую не написано.Эта часть кода,а генерация кода через Java Poet:

3.2 Политика краткосрочного истечения срока действия

В Caffeine есть два типа кешей: ограниченный кеш и неограниченный кеш.Неограниченный кеш не имеет срока действия и не имеет границ. Три API истечения срока действия предоставляются в ограниченных кешах:

  • expireAfterWrite: представляет, как долго он истечет после записи.
  • expireAfterAccess: представляет, как долго он истечет после последнего доступа.
  • expireAfter: в expireAfter вам нужно реализовать интерфейс Expiry самостоятельно.Этот интерфейс поддерживает создание, обновление и время истечения срока действия после доступа. Обратите внимание, что этот API является взаимоисключающим с двумя предыдущими API. Разница между этим и двумя предыдущими API заключается в том, что вам нужно сообщить фреймворку кэширования, что он должен истечь в определенное время, то есть получить конкретное время истечения с помощью предыдущих методов перезаписи создания, обновления и доступа.

В Caffeine есть метод scheduleDrainBuffers, который используется для планирования наших задач с истекшим сроком действия, которые будут вызываться после того, как мы прочитаем и напишем:

Во-первых, он заблокируется.Если блокировка не удалась, значит, кто-то уже выполняет планирование. Он будет использовать пул потоков по умолчанию ForkJoinPool или пользовательский пул потоков.DrainBuffersTask здесь на самом деле является PerformCleanupTask в Caffeine.

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

Вы можете видеть, что в нем много методов. Другие методы будут обсуждаться позже. Здесь мы сосредоточимся на expireEntries(), который является методом, используемым для истечения срока действия:

  • Сначала получите текущее время.
  • Второй шаг — истечение срока expireAfterAccess:

Здесь, в соответствии с нашей конфигурацией, метод evicts() является истинным, поэтому все три очереди будут просрочены и удалены.Как упоминалось выше, все эти три очереди являются очередями LRU, поэтому нашему методу expireAfterAccessEntries нужно только поместить заголовок каждой очереди Узел оценивает, истек ли срок действия доступа, а затем удаляет его.

  • Третий шаг — expireAfterWrite:

Видно, что здесь используется очередь writeQrderDeque, когда заполняются данные этой очереди? Конечно, он тоже асинхронный.Конкретный метод находится в нашем draninWriteBuffer выше.Он достанет Task, который мы положили в RingBuffer до этого, и выполнит его, в том числе добавив writeQrderDeque. Стратегия истечения срока действия очень проста: просто выполните цикл и откройте первый, чтобы определить, истекает ли он.

  • Четвертый шаг, expireVariableEntries expire:

В приведенном выше методе мы видим, что колесо времени используется для обработки истечения срока действия Что такое колесо времени? Он должен быть знаком с некоторыми системами задач на время, и он не является для него незнакомым.Это эффективная структура для обработки задач на время, которую можно просто рассматривать как многомерный массив. В Caffeine это двухслойное колесо времени, то есть двумерный массив.Его одномерные данные представляют большее временное измерение, такое как секунды, минуты, часы, дни и т. д., а его двумерные данные представляют меньшее измерение времени, например, интервал в секундах. Когда TimeWhile[i][j] находится, его структура данных фактически представляет собой связанный список, который записывает наш Node. В Caffeine мы используем колесо времени для записи наших данных, срок действия которых истекает в определенное время, а затем обрабатываем их.

Колесо времени в Caffeine показано выше. Когда мы вставляем данные, мы вычисляем время, когда он должен истечь в соответствии с методом, который мы переписали.Например, он должен истечь в 1536046571142. Время истечения последней обработки 1536046571100, вычтите его, чтобы получить 42 мс, а затем поместите его в Время колесо, поскольку оно меньше 1,07 с, помещается непосредственно в позицию 1,07 с, а определенная позиция во втором слое (которую нужно вычислить по определенному алгоритму) и вставляется в связанный список с помощью хвостовой вставки метод.

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

3.3. Удаление старой и развертывание новой стратегии обновления

Caffeine предоставляет метод refreshAfterWrite(), позволяющий нам обновлять стратегию после написания:

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

Обратите внимание, что обновление здесь обновляется не по истечении срока его действия, а только после повторного доступа к данным. Например: есть данные с ключом: «кофе», значение: «латте», мы устанавливаем 1 с для обновления, мы ждем 1 минуту после добавления данных, само собой разумеется, что он обновит в следующий раз, чтобы получить новое значение , к сожалению, нет, и по-прежнему возвращают «латте» при посещении. Но если вы продолжите посещение, то обнаружите, что он уже освежился.

Давайте посмотрим, как работает автоматическое обновление? Автоматическое обновление существует только после операции чтения, то есть нашего метода afterRead(), один из которых называется refreshIfNeeded, который будет обновляться в зависимости от того, синхронны вы или асинхронны.

3.4 Ложные и реальные - мягкие и слабые ссылки

В Java существует четыре типа ссылок: сильная ссылка (StrongReference), мягкая ссылка (SoftReference), слабая ссылка (WeakReference), виртуальная ссылка (PhantomReference).

  • Сильная ссылка: Объявление объекта непосредственно в нашем коде является строгой ссылкой.
  • Мягкая ссылка: если объект имеет только мягкую ссылку, если места в памяти достаточно, сборщик мусора не восстановит его; если места в памяти недостаточно, память этих объектов будет восстановлена. Пока сборщик мусора не переработан, программа может использовать объект. Мягкая ссылка может использоваться в сочетании с очередью ссылок.Если объект, на который ссылается мягкая ссылка, утилизируется сборщиком мусора, виртуальная машина Java добавляет эту мягкую ссылку в связанную с ней очередь ссылок.
  • Слабые ссылки: в процессе сканирования области памяти, находящейся под юрисдикцией потока сборщика мусора, когда он находит объект только со слабыми ссылками, его память будет освобождена независимо от того, достаточно ли текущего места в памяти или нет. Слабые ссылки можно использовать в сочетании с очередью ссылок (ReferenceQueue).Если объект, на который ссылается слабая ссылка, является сборщиком мусора, виртуальная машина Java добавит слабую ссылку в соответствующую очередь ссылок.
  • Фантомные ссылки: если объект содержит только фантомные ссылки, он может быть утилизирован сборщиком мусора в любое время, как если бы у него вообще не было ссылок. Виртуальная ссылка должна использоваться вместе с очередью ссылок (ReferenceQueue). Когда сборщик мусора готов освободить объект, если он обнаруживает, что у него все еще есть виртуальная ссылка, он добавит виртуальную ссылку в связанную с ним очередь ссылок перед освобождением памяти объекта.

3.4.1 Стратегия устранения слабых ссылок

Стратегия устранения слабых ссылок поддерживается в Caffeine, который имеет два API: weakKeys() и weakValues() используются для установки того, является ли ключ слабой ссылкой или значение является слабой ссылкой. Конкретный принцип заключается в том, чтобы обернуть ключ и значение виртуальными ссылками и привязать их к очереди ссылок при размещении:

.

Когда дело доходит до утилизации, в методе обслуживания, который мы представили ранее, есть два метода:

//处理key引用的
drainKeyReferences();
//处理value引用
drainValueReferences();

Конкретные коды обработки:

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

Примечание: многие студенты думают, что кеш хранится в виде Key-Value, но на самом деле он хранится в виде KeyReference — Node (узел содержит значение).

3.4.2 Стратегия исключения мягких ссылок

Стратегия устранения мягких ссылок также поддерживается в Caffeine.Его API — softValues(), а мягкие ссылки поддерживают только значение, но не ключ. Мы видим, что есть:

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

3.5 Познай себя и врага — больше контролируй

Некоторые стратегии мониторинга управления предоставляются в Caffeine, которые включаются через API RecordStats().По умолчанию используется тот, который поставляется с Caffeine, или вы можете реализовать его самостоятельно. В интерфейсе StatsCounter определены методы, которые необходимо расставить точками, на данный момент это следующие:

  • RecordHits: запись попаданий в кеш
  • RecordMisses: промахи кеша записи
  • recordLoadSuccess: запись успешно загружена (имеется в виду успешная загрузка CacheLoader)
  • RecordLoadFailure: ошибка загрузки записи
  • recordEviction: запись данных об исключении

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

3.6 Начало и окончание – исключить мониторинг

Много раз нам нужно знать, почему кеш в Caffeine был удален, чтобы сделать некоторые оптимизации? На данный момент нам нужен слушатель, код такой:

Cache<String, String> cache = Caffeine.newBuilder()
                .removalListener(((key, value, cause) -> {
                    System.out.println(cause);
                }))
                .build();

Есть много причин для устранения кофеина:

  • EXPLICIT: эта причина вызвана пользователем, который удаляется путем вызова метода удаления.
  • REPLACED: при обновлении это фактически эквивалентно удалению старого значения.
  • COLLECTED: Для нашего сборщика мусора, который является мягкой ссылкой, которую мы сократили выше, это слабая ссылка.
  • EXPIRED: истек срок действия и исключен.
  • SIZE: Размер удаляется. При превышении максимального размера он будет удален.

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

4. Наконец

В этой статье представлены все функциональные принципы Caffeine, а точки знаний включают: LFU, LRU, колесо времени, четыре ссылки на Java и так далее. Не имеет значения, если вы не заинтересованы в кофеине, я считаю, что вы многому научились благодаря внедрению этих знаний. Наконец, серия кешей в основном подошла к концу.Если вы хотите узнать больше, вы можете подписаться на мой официальный аккаунт, добавить меня в друзья или присоединиться к группе технического обмена WeChat для обсуждения.

Наконец, эта статья была включена в JGrowing, всеобъемлющий и отличный маршрут изучения Java, совместно созданный сообществом.Если вы хотите участвовать в обслуживании проектов с открытым исходным кодом, вы можете создать его вместе.Адрес github:GitHub.com/Java растет…Пожалуйста, дайте мне маленькую звезду.

Если вы считаете, что в этой статье есть статьи для вас, вы можете подписаться на мой технический паблик.За последнее время автор собрал много свежих обучающих материалов,видео и материалов интервью.Вы можете получить их, обратив внимание.Ваше внимание и пересылка самая большая поддержка для меня. , O(∩_∩)O

Категории