Библиотека для кэширования Caffeine: анализ кода

18 мин

1.9K

Программирование*Java*Алгоритмы*Высокая производительность*

Перевод

То и дело, прожигая время за чтением reddit, я натыкаюсь на очередной пост, в котором упоминается метод S3 FIFO и говорится, что он лучше LRU (вытеснение реже всего используемых значений) — потому что даёт более низкий процент промахов кэша. Видные компании, в частности, RedPandas, Rising Wave и Cloudflare уже внедрили S3 FIFO у себя на различных мощностях, что только подогрело мой интерес к нему. Кэши — чертовски интересная тема, а по работе мне приходится сильно полагаться на работу с кэшами при обслуживании нескольких сервисов. Так что я был уверен, что рано или поздно мне потребуется протестировать S3 FIFO или, как минимум, удостовериться, что я понимаю ключевые идеи, заложенные в этой технологии.

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

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

Caffeine — это высокопроизводительная библиотека для кэширования, на практике близкая к идеалу. В ней предоставляются потрясающие возможности, в частности, автоматическая загрузка записей, вытеснение записей в зависимости от размера, статистика, устаревание с привязкой по времени. Библиотека используется во многих очень влиятельных проектах, среди которых — Kafka, Solr, Cassandra, HBase или Neo4j.

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

Политика вытеснения: окно TinyLFU

Главная цель кэширования — довести до максимума процент попаданий, то есть гарантировать, что в кэше будут надолго сохраняться именно те данные, которые используются чаще всего. Политика вытеснения – это алгоритм; когда кэш полон, именно на основе этого алгоритма решается, какие записи сохранить, а от каких избавиться.

В качестве отправной точки хорошо подойдёт традиционная политика LRU (вытеснение записей, используемых реже всего) – она проста и отличается хорошей производительностью на самых разных рабочих нагрузках. Но современные кэши вполне могут работать лучше, так как учитывают и частотность, и недавность обращений к данным. Недавность количественно выражает вероятность того, что мы вскоре вновь обратимся к тому элементу, к которому недавно обращались. Частотность количественно выражает вероятность того, что частые обращения к некоторому элементу в дальнейшем окажутся столь же частыми. В Caffeine применяется политика под названием «окно TinyLFU», одновременно учитывающая оба этих сигнала. Более того, библиотека обеспечивает высокую точность попаданий со сложностью по времени O(1), а также занимает мало места в памяти (подробнее об этом см. BoundedLocalCache.java). Вот как она работает:

Окно допуска: при добавлении новой записи она сначала проходит через «окно допуска», и лишь затем полноценно заносится в главное пространство. Благодаря такому подходу удаётся поддерживать высокий процент попаданий в ситуациях, когда обращения к определённым записям концентрируются в виде всплесков.
Ориентировочная частота: в Caffeine используется компактная структура данных под названием CountMinSketch. С её помощью отслеживается, как часто происходят обращения к тем или иным записям в кэше. Если основное пространство уже заполнено, и при этом требуется добавить новую запись, то Caffeine проверяет ориентировочную частоту. Новая запись будет добавлена лишь при условии, что по оценке алгоритма обращаться к ней станут чаще, чем к другой записи — той, что потребуется вытеснить из кэша, чтобы освободить место для новой.

/**
   * Определяем, принять ли в главное пространство запись-кандидат, это зависит от 
   
* ориентировочной частности обращений к этой записи по сравнению с обращениями к той, которой потребуется пожертвовать. В этот процесс привносится небольшой элемент случайности. Он нужен, чтобы защититься от атак на коллизию хеша,
   * где частота «жертвы» автоматически повышается — в результате чего не допускается никаких новых записей 

   *
   * @param candidateKey — это ключ записи, предлагаемой для долговременного хранения 
   * @param victimKey — это ключ записи, которую решено удалить из кэша в соответствии с политикой вытеснения 
   * @return — если кандидата требуется принять, а «жертву» — вытеснить 
   */
  @GuardedBy("evictionLock")
  boolean admit(K candidateKey, K victimKey) {
    int victimFreq = frequencySketch().frequency(victimKey);
    int candidateFreq = frequencySketch().frequency(candidateKey);
    if (candidateFreq > victimFreq) {
      return true;
    } else if (candidateFreq >= ADMIT_HASHDOS_THRESHOLD) {
      // Максимальная частота 15 уменьшена более чем наполовину до 7 после сброса, для планового устаревания истории. При атаке 
      // эксплуатируется тот факт, что востребованный кандидат отвергается в пользу востребованной жертвы. Задавая порог для условно востребованного кандидата,
      // удаётся сократить количество случайных допусков и минимизировать влияние этого фактора на частоту попаданий.
      int random = ThreadLocalRandom.current().nextInt();
      return ((random & 127) == 0);
    }
    return false;
  }

Устаревание: чтобы история кэша оставалась свежей, Caffeine периодически «состаривает» ориентировочную частоту, уменьшая значения всех счётчиков наполовину. Благодаря такому подходу кэш со временем приспосабливается к изменению паттернов доступа.
Политика сегментированного LRU: В главном пространстве Caffeine задействует политику сегментированного LRU. Существование записи начинается в «апробационном» сегменте. Когда защищённый сегмент полон, записи возвращаются обратно в апробационный сегмент, откуда они в конечном счёте могут быть удалены окончательно. Такой подход призван обеспечить, чтобы самые востребованные записи сохранялись, а те, повторные обращения к которым происходят реже, первыми попадали в кандидаты на вытеснение.

Ориентировочная частотность

Как упоминалось выше, класс FrequencySketch — это ключевой элемент политики вытеснения кэша, поскольку в нём реализован эффективный способ оценки популярности записей в кэше (как часто к ним обращаются). Реализация этого класса приводится в файле FrequencySketch.java, сам класс представляет собой 4-разрядный CountMinSketch. CountMinSketch задуман как эффективная и компактная вероятностная структура данных, позволяющая оценивать, насколько часто те или иные элементы встречаются в потоке данных. В ней применяется множество хеш-функций, отображающих элементы на массив счётчиков, имеющий фиксированный размер. Так обеспечивается компактное представление информации о частоте:

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

Это очень умный подход, поскольку при нём тратится константное время как на операции, так и на запросы, независимо от того, сколько уникальных элементов сейчас в кэше. Этот подход хорошо масштабируется, и при нём эффективно используется память (есть возможность отслеживать информацию о частоте, тратя на это фиксированный объём памяти). Рассмотрим некоторые изюминки реализации Caffeine:

1. Структура данных сама ориентировка представлена как одномерный массив из 64-разрядных значений в формате long (table). В каждом long-значении содержится 16 4-разрядных счётчиков, соответствующих 16 различным хеш-цепочкам. Такая компоновка выбирается с целью повышения эффективности, так как счётчики для каждой конкретной записи удерживаются в пределах одной кэш-линии. Обратите внимание: в качестве длины массива table выбирается ближайшая степень двух, так, чтобы она была больше или равна максимальному размеру кэша. Таким образом создаются условия для эффективных операций над битовыми масками.

2. Хеширование. В ориентировке используются две хеширующие функции spread() и rehash(), задача которых — применять дополнительные хеш-функции к хеш-коду нормального элемента.

...
    int blockHash = spread(e.hashCode());
    int counterHash = rehash(blockHash);
...

 /** Применяет дополнительную хеш-функцию ради защиты от низкокачественного хеша. */
  static int spread(int x) {
    x ^= x >>> 17;
    x *= 0xed5ad4bb;
    x ^= x >>> 11;
    x *= 0xac4c1b51;
    x ^= x >>> 15;
    return x;
  }

  /** Запускает ещё один раунд хеширования для дополнительной рандомизации. */
  static int rehash(int x) {
    x *= 0x31848bab;
    x ^= x >>> 14;
    return x;
  }

3. Извлечение частоты

Частота извлекается в методе frequency(), который принимает минимум 4 релевантных счётчика (в качестве хорошего приближения):

  @NonNegative
  public int frequency(E e) {
    if (isNotInitialized()) {
      return 0;
    }

    int[] count = new int[4];
    int blockHash = spread(e.hashCode());
    int counterHash = rehash(blockHash);
    int block = (blockHash & blockMask) << 3;
    for (int i = 0; i < 4; i++) {
      int h = counterHash >>> (i << 3);
      int index = (h >>> 1) & 15;
      int offset = h & 1;
      count[i] = (int) ((table[block + offset + (i << 1)] >>> (index << 2)) & 0xfL);
    }
    return Math.min(Math.min(count[0], count[1]), Math.min(count[2], count[3]));
  }

Когда я в первый раз прочитал этот код, я в нём почти ничего не понял. Пришлось вооружиться карандашом и бумагой и выполнить кое-какие манипуляции вручную. Более того, такая же ситуация складывается с методом increment, который увеличивает на единицу уровень популярности элемента. По очереди разберём ключевые моменты этого кода:

blockHash = spread(e.hashCode()): здесь размазывается хеш-код входного элемента e, чтобы получить более качественное распределение хеш-значений.
counterHash = rehash(blockHash): здесь дополнительно перемешивается содержимое blockHash, чтобы получить иное хеш-значение, которое будет использовано для индексирования на 16 разных хеш-цепочек.
int block = (blockHash & blockMask) << 3: Чтобы понять эту часть, сначала потребуется заглянуть в blockMask и понять, как она создаётся. Она вычисляется как (table.length >> 3 ) - 1. Мы сдвигаем длину таблицы вправо на 3 разряда потому, что эта операция эквивалентна делению на 8. Учитывая, что каждый блок в массиве table содержит 16 счётчиков, а ширина каждого счётчика составляет 4 разряда, общий размер каждого блока равен 16*4=64 разряда (8 байт). Таким образом, сдвигая таблицу вправо на 3, мы, фактически, узнаём, сколько блоков содержится в табличном массиве. После этого вычитаем 1, получая в результате этой операции все возможные значения. Например, если длина таблицы равна 256, то table.length >> 3 даст нам 32; мы вычитаем отсюда единицу и получаем 31, что в двоичном формате равно 11111. Здесь заключены все 32 возможных значения от 0 до 31.

Следовательно, накладывая на blockHash маску blockMask, мы гарантируем, что получающийся в результате блокирующий индекс в любом случае останется в диапазоне, заданном массивом table.

Затем на каждой итерации (от 0 до 3) мы вычисляем 4 индекса счётчиков:

int h = counterHash >>> (i << 3): здесь мы извлекаем 8-разрядное значение из counterHash, делая сдвиг вправо на i * 8 разрядов. В результате получаем хеш-значение для актуального 4-разрядного счётчика.
int index = (h >>> 1) & 15: Сначала выполняем логический сдвиг h вправо на 1 (что равноценно делению на 2), чтобы взять наименьший значимый разряд. Мы это делаем с расчётом на будущее, когда эта операция пригодится нам для расчёта смещения. Затем мы маскируем её при помощи 15 (1111 в двоичном формате), чтобы получить 4 наименьших значимых разряда. В результате получаем индекс счётчика внутри блока (поскольку там заключено 16 счётчиков)
int offset = h & 1: В этой строке вычисляется смещение внутри 64-разрядного блока, равное 0 или 1. Для этого берётся наименьший значимый разряд из 8-разрядного хеш-значения
count[i] = (int) ((table[block + offset + (i << 1)] >>> (index << 2)) & 0xfL): здесь мы извлекаем 4-разрядное значение счётчика из таблицы вот так:

Вычисляем индекс в массиве таблицы, где расположены 4 счётчика для заданного элемента: block + offset + (i << 1):

block — это тот индекс, с которого начинается блок в массиве table
offset равен 0 или 1, в зависимости от того, к какому из двух 8-байтных сегментов внутри блока мы обращаемся.
(i << 1) — это смещение внутри того 8-байтного сегмента, в котором содержится 4 счётчика, где i — это индекс счётчика (от 0 до 3). Здесь мы фактически умножаем i на 2, в результате чего получаем смещения 0, 2, 4 или 6 внутри 16-байтового сегмента.

Затем сдвигаем это 64-разрядное значение вправо на index * 4 разрядов при помощи >>> (index << 2). Таким образом, мы выравниваем наш 4-разрядный счётчик с наименьшим значимым разрядом long-значения. Умножаем его на 4, поскольку ширина каждого счётчика составляет 4 байта. Наконец, накладываем битовую маску на извлечённое значение счётчика, чтобы гарантировать, что это 4-разрядное беззнаковое целое & 0xfL (1111 в двоичном формате).

Наконец, метод возвращает минимальное значение из тех 4 показателей частоты, которые сохранены в массиве.

4. Устаревание. Периодически, когда количество наблюдаемых событий достигает определённого порога (sampleSize), вызывается метод reset(). Этот метод вполовину уменьшает значение всех счётчиков и вычитает количество нечётных счётчиков.

Истечение времени с применением упорядоченных очередей и иерархического кольца таймеров

Если вы хотите подробно разобраться, как именно сущности устаревают в кэше и вытесняются из него, нам нужно немного глубже разобраться в деталях. Например, те политики удаления реже всего используемых элементов (LRU), которые мы видели ранее при изучении сегментированного подхода к LRU и окна допуска, реализуются с применением очереди порядка обращений. В свою очередь, политика времени жизни (TTL), при которой вытеснение из кэша зависит от того, сколько времени прошло с последней операции записи, основана на очереди порядка записи. Устаревание переменных определяется по иерархическому кольцу таймеров. Все эти стратегии эффективно реализуются со сложностью по времени O(1).

Упорядоченные очереди

В кэше Caffeine используются две главные очереди, обеспечивающие политику быстрого вытеснения. Идея политик на основе очередей заключается в том, чтобы можно было заглянуть в самую старую запись и проверить, истёк ли срок её годности. Если нет, то и срок годности более свежих записей не должен был истечь. Все они основаны на классе AbstractLinkedDeque.java, предоставляющем оптимизированный двойной связный список. В этой реализации есть несколько интересных аспектов:

1. Без сигнальных узлов

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

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

То есть, всё ради сокращения количества проверок на null. Правда, оба элемента объявляются как @Nullable:

@Nullable E first;
@Nullable E last;

Как же в таком случае удаётся сократить проверки на null? В реализации на основе сигнальных узлов головной узел и хвостовой узел у нас всегда будут ненулевыми. Это значит, что можно без опаски обращаться к head.next и tail.prev, не выполняя проверок на null. Однако в рассматриваемой реализации без сигнальных узлов как первый, так и последний элемент могут быть равны нулю. Не требуются ли в таком случае дополнительные проверки на null? Суть в том, как JVM обрабатывает проверки на null. Когда вы обращаетесь к полю или методу у потенциально нулевого объекта, JVM автоматически вставляет в байт-код проверки на null. Если объект равен null, он выбрасывает исключение NullPointerException. Аккуратно структурируя код так, чтобы в нём случаи возникновения null обрабатывались явно, авторы данной реализации добиваются того, что удаётся обойтись в критических путях без этих автоматических проверок на null и потенциально возможных NullPointerExceptions.

Например, рассмотрим метод linkFirst:

void linkFirst(final E e) {
  final E f = first;
  first = e;

  if (f == null) {
    last = e;
  } else {
    setPrevious(f, e);
    setNext(e, f);
  }
  modCount++;
}

Этот метод обрабатывает случай, в котором список пуст (f == null) отдельно от случая, в котором он не пуст. Так исключается необходимость для JVM вставлять автоматические проверки на null при обращении к полям или методам f. В реализации с сигнальными узлами у нас мог бы быть подобный код:

void linkFirst(final E e) {
  Node newNode = new Node(e);
  newNode.next = head.next;
  newNode.prev = head;
  head.next.prev = newNode;  // Потенциальная автоматическая проверка на null 
  head.next = newNode;       // Потенциальная автоматическая проверка на null
}

Здесь JVM может вставлять автоматические проверки на null для head.next, пусть нам и известно, что null здесь не возникнет никогда.

2. Отслеживание структурных модификаций

Этот класс ведёт целочисленный счёт modCount, при помощи которого отслеживаются структурные модификации. Так на каждой итерации можно обнаружить конкурирующие модификации. Значение счётчика увеличивается на единицу всякий раз при удалении или добавлении элемента. Основное назначение этого класса — поддерживать в итераторах поведение быстрого отказа:

При создании итератора фиксируется актуальное состояние modCount:

AbstractLinkedIterator(@Nullable E start) {
  expectedModCount = modCount;
  cursor = start;
}

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

void checkForComodification() {
if (modCount != expectedModCount) {
  throw new ConcurrentModificationException();
}
}

Значение modCount увеличивается в тех методах, которые вносят в список структурные изменения, в частности, linkFirst(), linkLast(), unlinkFirst(), unlinkLast() и unlink().

Очередь порядка обращений: AccessOrderDeque.java

Очередь порядка обращений (Access Order Queue) отслеживает все содержащиеся в хеш-таблице записи в зависимости от того, насколько недавно к каждой из них в последний раз обращались. Это двойной связный список, в котором ведётся порядок записей в кэше в зависимости от частотности обращений к ним.

После того, как к записи обратились, она переходит в хвост списка. Так гарантируется, что та запись, к которой обращались реже всего (LRU), всегда остаётся в голове списка. Это жизненно важно для реализации стратегии вытеснения LRU. Например, если у нас в кэше находятся записи [A <-> B <-> C], где к A обращались реже всего, а к C обращались совсем недавно, и мы при этом обращаемся к B, то она переместится в конец очереди. Очередь при этом будет иметь вид [A <-> C <-> B]

Очередь порядка записи: WriteOrderDeque.java

Очередь порядка записи (Write Order Queue) подобно очереди порядка обращений упорядочивает записи в зависимости от того, когда именно они создавались или обновлялись. Очередь порядка записи отслеживает элементы в зависимости от того, насколько давно в них вносилась информация. Это особенно полезно в случаях, когда мы хотим, чтобы запись автоматически устаревала по истечении определённого периода после последнего внесения информации (expireAfterWrite).

Например, рассмотрим сценарий, в котором происходят записи [A <-> B <-> C], именно в таком порядке. Если обновить A, то она переместится в конец очереди: [B <-> C <-> A].

Иерархическое кольцо таймеров: TimerWheel.java

Кольцо таймеров (timer wheel) — это структура данных для эффективного управления событиями, зависящими от времени. В сущности, идея такова: эта структура представляет собой кольцевой буфер, в котором события с привязкой ко времени хранятся партиями. Каждая партия соответствует конкретному промежутку времени, выражаемому, например, в секундах или минутах.

Применительно к библиотеке Caffeine записи добавляются в эти партии в зависимости от того, когда истекает срок актуальности конкретной записи. Так обеспечивается эффективное добавление, удаление или истечение элементов, сложность алгоритма по времени составляет O(1). В каждой партии содержится связный список, в который добавляются элементы. Учитывая, что размер кольцевого буфера ограничен, у нас возникли бы проблемы, если событие нужно назначить на отдалённый момент в будущем, и требуемый промежуток времени не умещается в кольцевой буфер. Именно поэтому нам пригодится иерархическое кольцо таймеров. В такой структуре данных просто накладывается друг на друга множество подобных колец, и у каждого из них — своё разрешение.

Давайте кратко рассмотрим код TimerWheel.java:

1. Иерархическая структура: партии и промежутки

Каждый элемент в массиве BUCKETS представляет, сколько партий предусмотрено на этом уровне кольца таймеров. В свою очередь, SPANS определяет, промежуток какой длительности укладывается в каждую партию. Как упоминалось выше, такая иерархическая структура позволяет каскадировать события от менее детализированных промежутков времени к более детализированным. Вот какие значения были выбраны для реализации, применяемой в Caffeine:

static final int[] BUCKETS = { 64, 64, 32, 4, 1 };
static final long[] SPANS = {
    ceilingPowerOfTwo(TimeUnit.SECONDS.toNanos(1)), // 1,07 с
    ceilingPowerOfTwo(TimeUnit.MINUTES.toNanos(1)), // 1,14 мин
    ceilingPowerOfTwo(TimeUnit.HOURS.toNanos(1)),   // 1,22 ч
    ceilingPowerOfTwo(TimeUnit.DAYS.toNanos(1)),    // 1,63 дн
    BUCKETS[3] * ceilingPowerOfTwo(TimeUnit.DAYS.toNanos(1)), // 6,5 дн
    BUCKETS[3] * ceilingPowerOfTwo(TimeUnit.DAYS.toNanos(1)), // 6,5 дн
};

2. Умная манипуляция битами

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

long ticks = (time >>> SHIFT[i]);
int index = (int) (ticks & (wheel[i].length - 1));

Так мы обходимся без ресурсозатратных расчётов по модулю. Разберём подробнее, как всё это работает:

static final long[] SPANS = {
ceilingPowerOfTwo(TimeUnit.SECONDS.toNanos(1)), // 1,07 с
    ceilingPowerOfTwo(TimeUnit.MINUTES.toNanos(1)), // 1,14 мин
    // ...
};

static final long[] SHIFT = {
    Long.numberOfTrailingZeros(SPANS[0]),
    Long.numberOfTrailingZeros(SPANS[1]),
    // ...
};

Каждое значение SPAN округляется до ближайшей степени 2, а в массиве SHIFT хранится количество завершающих нулей для каждого значения SPAN. Оно эквивалентно

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

long ticks = (time >>> SHIFT[i]);
int index = (int) (ticks & (wheel[i].length - 1));

time >> SHIFT[i]: здесь выполняется сдвиг вправо на нужную величину в актуальном кольце. Данная операция эквивалентна делению на SPANS[i]
wheel[i].length - 1: это битовая маска. Поскольку wheel[i].length — это всегда степень 2, здесь мы создаём на нижних разрядах маску, состоящую из одних единиц.
ticks & (wheel[i].length - 1): здесь над маской выполняется операция побитового И, что эквивалентно ticks % wheel[i].length, но, опять же, выполняется гораздо быстрее.

Рассмотрим пример. Допустим, у нас есть:

time = 1,500,000,000 nanoseconds (1.5 seconds)
SPANS[i] = 1,073,741,824 (2^30, about 1.07 seconds)
SHIFT[i] = 30

В двоичном формате:

time = 1011001010000000000000000000000

Теперь при операции time >>> SHIFT[i]мы выполняем сдвиг вправо на 30 разрядов:

1011001010000000000000000000000 >>> 30 = 1

Этот результат 1 означает, что истёк 1 полный такт данного кольца. На следующем этапе будем исходить из того, что wheel[i].length равно 64. В двоичном формате:

ticks = 00000000000000000000000000000001
wheel[i].length - 1 = 00000000000000000000000000111111

выполняем побитовое И:

  00000000000000000000000000000001
& 00000000000000000000000000111111
  --------------------------------
  00000000000000000000000000000001

В результате получаем 1 — то есть, наш индекс равен 1. На практике это означает, что за 1,5 секунды кольцо сдвигается на один такт, и поэтому рассматриваемое событие попадает во вторую партию. Этот подход особенно красив тем, что процесс закольцовывается автоматически. По прошествии 64 тактов индекс снова будет равен 0, поскольку 64 & 63 = 0. Предположим, в следующий раз нам попадётся значение 3 000 000 000 наносекунд (3 секунды):

3,000,000,000 >>> 30 = 2 (ticks)
2 & 63 = 2 (index)

Таким образом, это событие попадёт в третью партию кольца (индекс 2).

Адаптивная политика кэширования

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

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

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

Проведя тщательное тестирование, разработчики Caffeine предпочли вносить нечастые, но относительно крупные изменения. Например, рассмотрим код, который корректирует размер окна (источник: BoundedLocalCache.java):

  /** Вычисляет, на какую величину следует откорректировать размер окна и соответствующим образом устанавливает {@link #adjustment()}. */
  @GuardedBy("evictionLock")
  void determineAdjustment() {
    // проверяет, инициализирована ли ориентировочная частота
    if (frequencySketch().isNotInitialized()) {
      setPreviousSampleHitRate(0.0);
      setMissesInSample(0);
      setHitsInSample(0);
      return;
    }

    int requestCount = hitsInSample() + missesInSample();
    if (requestCount < frequencySketch().sampleSize) {
      return;
    }

    double hitRate = (double) hitsInSample() / requestCount;
    double hitRateChange = hitRate - previousSampleHitRate();
    double amount = (hitRateChange >= 0) ? stepSize() : -stepSize();
    double nextStepSize = (Math.abs(hitRateChange) >= HILL_CLIMBER_RESTART_THRESHOLD)
        ? HILL_CLIMBER_STEP_PERCENT * maximum() * (amount >= 0 ? 1 : -1)
        : HILL_CLIMBER_STEP_DECAY_RATE * amount;
    setPreviousSampleHitRate(hitRate);
    setAdjustment((long) amount);
    setStepSize(nextStepSize);
    setMissesInSample(0);
    setHitsInSample(0);
  }

Процент попаданий вычисляется на основе количества попаданий в пересчёте на общее количество обращений к выборке. Текущий процент попаданий сравнивается с тем, что был раньше. Если процент попаданий улучшился (или остался прежним), то делается шаг в положительном направлении, если нет — в отрицательном. Если процент попаданий изменился значительно, то вычисляется более крупный размер шага (в зависимости от процента от максимума). В противном случае шаг постепенно сужается, благодаря чему магнитуда наступающих изменений также угасает. Наконец, состояние обновляется.

Благодаря такой адаптивной политике Caffeine тонко подстраивает собственное поведение с учётом потребностей каждого конкретного приложения. Производительность оптимизируется, и ручное вмешательство при этом не требуется. Это свидетельствует о том, что библиотека Caffeine тщательно спроектирована и выгодно выделяется на фоне других решений для кэширования.

Заключение

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

Такое глубокое погружение в Caffeine ошеломляет — поистине, это инженерный шедевр. Здесь нашлось место и умным манипуляциям с битами, и хорошо спроектированным структурам данных. На каждом уровне виден продуманный и эффективный дизайн.

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

Теги:

Хабы: