Кэш давка - Cache stampede - Wikipedia

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

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

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

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

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

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

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

функция принести(ключ, ttl) {    ценить ← cache_read (ключ)    если (!ценить) {        ценить ← Recompute_value () cache_write (ключ, ценить, ttl)    }    возвращаться ценить}

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

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

Снижение давности кеширования

Было предложено несколько подходов к уменьшению паники кеша. (Также известна как профилактика собачьих скоплений). Их можно примерно сгруппировать в 3 основные категории.

Блокировка

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

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

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

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

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

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

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

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

Вероятно раннее истечение срока

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

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

функция x-выборка (ключ, ttl, бета=1) {    ценить, дельта, истечение срока ← cache_read (ключ)    если (!ценить || время () - дельта * бета * журнал (rand (0,1)) ≥ истечение срока) {        Начните ← время () ценить ← Recompute_value () дельта ← time () - запустить cache_write (ключ, (ценить, дельта), ttl)    }    возвращаться ценить}

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

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

Рекомендации

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

внешняя ссылка