Давка с кэшем

Паника в кэше — это тип каскадного сбоя , который может возникнуть, когда массово- параллельные вычислительные системы с механизмами кэширования подвергаются очень высокой нагрузке. Такое поведение иногда еще называют собачьей свалкой . ^[1]^[2]

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

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

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

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

Типичное использование кэша

Ниже приведен типичный шаблон использования кэша для элемента, который необходимо обновлять каждый раз. ttl единицы времени:

function fetch(key, ttl) {    value ← cache_read(key)    if (!value) {        value ← recompute_value()        cache_write(key, value, ttl)    }    return value}

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

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

Уменьшение давки в кэше

Было предложено несколько подходов для уменьшения давки на кеш-память (также известной как предотвращение «собачьей кучи»). Их можно условно сгруппировать в 3 основные категории.

Блокировка

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

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

Подождите, пока значение не будет пересчитано
Верните «не найдено» и попросите клиента правильно обработать отсутствие значения.
Сохраняйте устаревший элемент в кеше, чтобы использовать его, пока новое значение пересчитывается.

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

Внешний перерасчет

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

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

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

Вероятностное досрочное истечение

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

Следующая реализация, основанная на экспоненциальном распределении, оказалась оптимальной с точки зрения ее эффективности в предотвращении давок и возможности ранних перерасчетов. ^[3]

function x-fetch(key, ttl, beta=1) {    value, delta, expiry ← cache_read(key)    if (!value || (time() - delta * beta * log(rand(0,1))) ≥ expiry) {        start ← time()        value ← recompute_value()        delta ← time() – start        cache_write(key, (value, delta), ttl)    }    return value}

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

Этот подход прост в реализации и эффективно снижает нагрузку на кэш, автоматически отдавая предпочтение ранним повторным вычислениям при увеличении скорости трафика. Одним из недостатков является то, что для этого требуется больше памяти в кеше, поскольку нам необходимо связать дельту значения с элементом кеша. Когда система кеширования не поддерживает получение времени истечения срока действия ключа, нам также необходимо хранить срок действия (т. time() + ttl ) в комплекте.

Ссылки

^ Гэлбрейт, Патрик (2009), Разработка веб-приложений с помощью Apache, MySQL, memcached и Perl , John Wiley & Sons, стр. 353, ISBN 9780470538326 .
^ Оллспау, Джон; Роббинс, Джесси (2010), Веб-операции: своевременное хранение данных , O'Reilly Media, стр. 128–132, ISBN 9781449394158 .
^ Ваттани, А.; Кьеричетти, Ф.; Ловенштейн, К. (2015), «Оптимальное вероятностное предотвращение панического скопления кэша» (PDF) , Proceedings of VLDB Endowment , 8 (8), VLDB: 886–897, doi : 10.14778/2757807.2757813 , ISSN 2150-8097 .

Внешние ссылки

Минимизация давок с тайниками , Джошуа Тийссен, 2010 г.
Проблемы и решения типичного использования кэша Perl , Джонатан Шварц, 2008 г.

[1] Гэлбрейт, Патрик (2009), Разработка веб-приложений с помощью Apache, MySQL, memcached и Perl , John Wiley & Sons, стр. 353, ISBN 9780470538326 .

[2] Оллспау, Джон; Роббинс, Джесси (2010), Веб-операции: своевременное хранение данных , O'Reilly Media, стр. 128–132, ISBN 9781449394158 .

[3] Ваттани, А.; Кьеричетти, Ф.; Ловенштейн, К. (2015), «Оптимальное вероятностное предотвращение панического скопления кэша» (PDF) , Proceedings of VLDB Endowment , 8 (8), VLDB: 886–897, doi : 10.14778/2757807.2757813 , ISSN 2150-8097 .

[1]

[2]

[3]