Паника в кэше — это тип каскадного сбоя , который может возникнуть, когда массово- параллельные вычислительные системы с механизмами кэширования подвергаются очень высокой нагрузке. Такое поведение иногда еще называют собачьей свалкой . [1] [2]
Чтобы понять, как возникают проблемы с кэшем, рассмотрим веб-сервер , который использует memcached для кэширования отображаемых страниц в течение некоторого периода времени, чтобы облегчить нагрузку на систему. При особенно высокой нагрузке на один URL-адрес система остается отзывчивой, пока ресурс остается в кэше, а запросы обрабатываются путем доступа к кэшированной копии. Это сводит к минимуму дорогостоящую операцию рендеринга.
При низкой нагрузке промахи в кэше приводят к однократному перерасчету операции рендеринга. Система продолжит работу в прежнем режиме, при этом средняя нагрузка будет оставаться очень низкой из-за высокой скорости попадания в кэш.
Однако при очень большой нагрузке, когда истекает срок действия кэшированной версии этой страницы, в ферме серверов может быть достаточно параллелизма , чтобы несколько потоков выполнения попытались одновременно отобразить содержимое этой страницы. Систематически ни один из параллельных серверов не знает, что другие одновременно выполняют тот же рендеринг. Если присутствует достаточно высокая нагрузка, этого само по себе может быть достаточно, чтобы вызвать коллапс системы из-за перегрузки из-за истощения общих ресурсов. Коллапс перегрузки приводит к невозможности полной повторной обработки и повторного кэширования страницы, поскольку время ожидания каждой попытки сделать это истекает. Таким образом, скопление кэша снижает частоту попаданий в кэш до нуля и постоянно удерживает систему в состоянии перегрузки, когда она пытается восстановить ресурс до тех пор, пока нагрузка остается очень большой.
В качестве конкретного примера предположим, что рендеринг рассматриваемой страницы занимает 3 секунды, а трафик составляет 10 запросов в секунду. Затем, когда срок действия кэшированной страницы истекает, у нас есть 30 процессов, одновременно пересчитывающих рендеринг страницы и обновляющих кеш с помощью отрендеренной страницы.
Ниже приведен типичный шаблон использования кэша для элемента, который необходимо обновлять каждые единицы времени ttl :
function fetch( key , ttl ) { value ←cache_read( key ) if (! value ) { value ← recompute_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))) ≥ срок действия ) { start ← time() value ← recompute_value() delta ← time() – start кэш_запись( ключ , ( значение , дельта ), ttl ) } возвращаемое значение}Для параметра beta можно установить значение больше 1, чтобы способствовать более ранним перерасчетам и дополнительно уменьшить панику, но авторы показывают, что установка beta = 1 хорошо работает на практике. Переменная дельта представляет время перерасчета значения и используется для соответствующего масштабирования распределения вероятностей.
Этот подход прост в реализации и эффективно снижает нагрузку на кэш, автоматически отдавая предпочтение ранним повторным вычислениям при увеличении скорости трафика. Одним из недостатков является то, что для этого требуется больше памяти в кеше, поскольку нам нужно связать дельту значения с элементом кеша - когда система кеширования не поддерживает получение времени истечения срока действия ключа, нам также необходимо хранить срок действия (то есть время( ) + ttl ) в связке.