Привет, Хабр!

Меня зовут Виктор Пряжников, я работаю в SRV-команде Badoo. Наша команда занимается разработкой и поддержкой внутреннего API для наших клиентов со стороны сервера, и кэширование данных — это то, с чем мы сталкиваемся каждый день.

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


Wild horses stampeding. Оригинал картинки.

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

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

Деление данных между кэширующими серверами


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

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

Самый очевидный способ разбивки данных — вычисление номера сервера псевдослучайным образом в зависимости от ключа кэширования.

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

$cache_server_index = crc32($cache_key) % count($cache_servers_list);

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

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

Я написал небольшой скрипт, который продемонстрирует эту проблему.

В нём генерируется 1 млн уникальных ключей, распределённых по пяти серверам с помощью хеширования по модулю и CRC32. Я эмулирую выход из строя одного из серверов и перераспределение данных по четырём оставшимся.

В результате этого «сбоя» примерно 80% ключей изменят своё местоположение, то есть окажутся недоступными для последующего чтения:

Total keys count: 1000000
Shards count range: 4, 5

LostKeysPercent ShardsAfter LostKeysPercent LostKeys
5 4 80.03% 800345

Самое неприятное тут то, что 80% — это далеко не предел. С увеличением количества серверов процент потери кэша будет расти и дальше. Единственное исключение — это кратные изменения (с двух до четырёх, с девяти до трёх и т. п.), при которых потери будут меньше обычного, но в любом случае не менее половины от имеющегося кэша:


Я выложил на GitHub скрипт, с помощью которого я собрал данные, а также ipynb-файл, рисующий данную таблицу, и файлы с данными.

Для решения этой проблемы есть другой алгоритм разбивки — согласованное хеширование (англ. consistent hashing). Основная идея этого механизма очень простая: здесь добавляется дополнительное отображение ключей на слоты, количество которых заметно превышает количество серверов (их могут быть тысячи и даже больше). Сами слоты, в свою очередь, каким-то образом распределяются по серверам.

При изменении количества серверов количество слотов не меняется, но меняется распределение слотов между этими серверами:

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

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



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

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

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

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

Наряду с согласованным хешированием есть и другие способы решения этой проблемы (например, rendezvous hashing), но они гораздо менее распространены.

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

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

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

См. также:


Параллельные запросы на обновление данных


Посмотрите на такой простой кусочек кода:

public function getContactsCountCached(int $user_id) : ?int
{
   $contacts_count = \Contacts\Cache::getContactsCount($user_id);
   if ($contacts_count !== false) {
       return $contacts_count;
   }

   $contacts_count = $this->getContactsCount($user_id);
   if (is_null($contacts_count)) {
       return null;
   }

   \Contacts\Cache::setContactsCount($user_id, $contacts_count);
   return $contacts_count;
}

Что произойдёт при отсутствии запрашиваемых данных в кэше? Судя по коду, должен запуститься механизм, который достанет эти данные. Если код выполняется только в один поток, то всё будет хорошо: данные будут загружены, помещены в кэш и при следующем запросе взяты уже оттуда. А вот при работе в несколько параллельных потоков всё будет иначе: загрузка данных будет происходить не один раз, а несколько.

Выглядеть это будет примерно так:



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

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

Предположим, у вас есть какой-то функционал, использующий кэш с нагрузкой 200 запросов в секунду. Если на на загрузку данных нужно 50 мс, то за это время вы получите 50 / (1000 / 200) = 10 запросов.

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

Эта проблема называется cache stampede (русского аналога этого термина я не нашёл, дословно это можно перевести как «паническое бегство кэша», и картинка в начале статьи показывает пример этого действия в дикой природе), hit miss storm («шторм непопаданий в кэш») или dog-pile effect («эффект собачьей стаи»). Есть несколько способов её решения:

Блокировка перед началом выполнения операции пересчёта/ загрузки данных


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

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

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

Вынос обновлений в фон


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

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

Этот вариант мы в Badoo используем, например, для счётчика общего количества пользователей, про который ещё пойдёт речь дальше.

Вероятностные методы обновления


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

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

function xFetch($key, $ttl, $beta = 1)
{
    [$value, $delta, $expiry] = cacheRead($key);
    if (!$value || (time() ? $delta * $beta * log(rand())) > $expiry) {
        $start  = time();
        $value  = recomputeValue($key);
        $delta  = time() – $start;
        $expiry = time() + $ttl;
        cacheWrite(key, [$value, $delta, $expiry], $ttl);
    }

    return $value;
}

В данном примере $ttl — это время жизни значения в кэше, $delta — время, которое потребовалось для генерации кэшируемого значения, $expiry — время, до которого значение в кэше будет валидным, $beta — параметр настройки алгоритма, изменяя который, можно влиять на вероятность пересчёта (чем он больше, тем более вероятен пересчёт при каждом запросе). Подробное описание этого алгоритма можно прочитать в white paper «Optimal Probabilistic Cache Stampede Prevention», ссылку на который вы найдёте в конце этого раздела.

Нужно понимать, что при использовании подобных вероятностных механизмов вы не исключаете параллельные обновления, а только снижаете их вероятность. Чтобы исключить их, можно «скрестить» несколько способов сразу (например, добавив блокировку перед обновлением).

См. также:


«Холодный» старт и «прогревание» кэша


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

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

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

  • плавным включением нового функционала. Для этого необходим механизм, который позволит это сделать. Простейший вариант реализации — выкатывать новый функционал включённым на небольшую часть пользователей и постепенно её увеличивать. При таком сценарии не должно быть сразу большого вала обновлений, так как сначала функционал будет доступен только части пользователей, а по мере её увеличения кэш уже будет «прогрет».
  • разным временем жизни разных элементов набора данных. Данный механизм можно использовать, только если система в состоянии выдержать пик, который наступит при выкатке всего функционала. Его особенность заключается в том, что при записи данных в кэш у каждого элемента будет своё время жизни, и благодаря этому вал обновлений сгладится гораздо быстрее за счёт распределения последующих обновления во времени. Простейший способ реализовать такой механизм — умножить время жизни кэша на какой-то случайный множитель:

public function getNewSnapshotTTL()
{
    $random_factor = rand(950, 1050) / 1000;
    return intval($this->getSnapshotTTL() * $random_factor);
}

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

Пример


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

Вот как выглядит график количества hit miss-ов в ситуации с фиксированным (fixed_cache_misses_count) и различным (random_cache_misses_count) сроками жизни кэша:



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

«Горячие» ключи


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



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



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

Мы в Badoo решаем эту проблему тем, что пишем данные во все кэширующие серверы сразу. Благодаря этому при чтении мы можем использовать общий механизм выбора сервера — в коде можно использовать обычный механизм шардирования по User ID, и при чтении не нужно ничего знать про специфику этого «горячего» ключа. В нашем случае это работает, поскольку у нас сравнительно немного серверов (примерно десять на площадку).

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

Если вы используете определение сервера по ключу кэша, то можно добавить к нему ограниченное количество псевдослучайных значений (сделав из total_users_count что-то вроде total_users_count_1, total_users_count_2 и т. д.). Подобный подход используется, например, в Etsy.

Если вы используете явные указания параметра шардирования, то просто передавайте туда разные псевдослучайные значения.

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

См. также:


Сбои в работе


Система не может быть надёжной на 100%, поэтому нужно предусмотреть, как она будет вести себя при сбоях. Сбои могут быть как в работе самого кэша, так и в работе базы данных.

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

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

Заключение


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

Комментарии (15)


  1. Loki3000
    28.03.2018 17:23

    А какова логика перераспределения слотов? Отвалился один сервер — его слоты перераспределили между оставшимися. Потом сервер вернулся — какие слоты ему отдали? Те же что и забрали или произвольные? А если вернулся не один сервер, а два? Там какая-то сложная логика или точно так же вычисляем от ключа, но на этот раз не кэша а слота?


    1. bikutoru Автор
      28.03.2018 18:12
      +1

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


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


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


  1. paw-p
    28.03.2018 18:24
    +1

    Проблема cache stampede (hit miss storm) также называется dog-pile effect и вариант решения описывался здесь habrahabr.ru/post/43540


    1. bikutoru Автор
      28.03.2018 18:24
      +1

      Спасибо за замечание, добавил еще один вариант названия


  1. velvetcat
    28.03.2018 20:40

    Посмотрите на такой простой кусочек кода:

    Если это продакшен-код (или создан из такового), тогда он очень, очень плох… И дело не в неправильной работе с кешом, а в самом коде. Да даже и пример можно было сделать, используя нормальные практики программирования, заодно выиграв в читаемости.


    1. nizkopal
      28.03.2018 21:50

      Этот код приведен как раз для того, чтобы продемонстрировать определенную проблему, о чем сказано ниже. Как он может быть боевым? ;)


      1. velvetcat
        29.03.2018 07:51

        Прочитайте, пожалуйста, мой коммент внимательнее. Сам код, а не что он делает, плох.


        1. Sannis
          29.03.2018 14:18

          А можете привести пример как бы вы его написали читабельнее, используя нормальные практики программирования ?


  1. nizkopal
    28.03.2018 21:48

    Ошибся веткой… :(


  1. Hixon10
    28.03.2018 22:13

    Мы в Badoo решаем эту проблему тем, что пишем данные во все кэширующие серверы сразу. Благодаря этому при чтении мы можем использовать общий механизм выбора сервера — в коде можно использовать обычный механизм шардирования по User ID, и при чтении не нужно ничего знать про специфику этого «горячего» ключа. В нашем случае это работает, поскольку у нас сравнительно немного серверов (примерно десять на площадку).

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


    А вы полностью сами написали распределенный кэш? Почему индустриальный лидеры: hazelcast и ignite — не подошли? Там и шардирование есть, и репликация.

    Записывать кэш на все 10 серверов — это, кажется, супер дорого, поправьте меня, пожалуйста. Особенно, если вы ждёте Аков от всех нод, а не какого-то кворума.


    1. bikutoru Автор
      29.03.2018 10:34

      Да, писать в 10 кэширующих серверов долго и дорого, но мы используем это крайне редко. Обычно мы пишем ключ и читаем его только из одного сервера.


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


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


  1. Arik
    29.03.2018 07:11

    Вынос обновлений в фон

    А если проекты маленькие, но проблема с параллельными вычислениями все же присутствует? Выносить в фон выглядит немного дороговато- переписывать чужой код, кто-то должен
    поддерживать, помнить про это, убедить остальную команду, клиента…
    Тоже есть небольшой опыт с метками (boolean), метками времени, но если что перегружается, то все остается в «воздухе». Что если на момент вычисления блокировать какой-нибудь файл? Если основной процесс с вычислениями помрет, то файл будет автоматом разблокирован(?) и другой процесс в очереди сможет подхватить работу, при этом основной процесс может записывать какие-то промежуточные вычисления в этот файл, что позволит следующему начать уже не с нуля. Это конечно все нагрузка на диск, но опять же это не для крупных проектов.
    Дальше можно нарастить более сложную логику: если на «холодный старт» много что нужно вычислить, то может не ставить в очередь другие процессы, а дать им что «повычислять»? Т.е. по кол-ву «вычислений» появятся что-то вроде «мастер» процессов, а остальные останутся в очереди, когда «мастер» процесс завершает свой кусочек вычислений для кэша он становится в очередь к остальным, как-то только все «мастер» процессы выполнят свои задачи, то все процессы отдадут ответы из кэша. -Пока лишь фантазии…


  1. bikutoru Автор
    29.03.2018 11:02

    Честно говоря, вариант с мастер-процессом не выглядит проще в реализации, чем фоновое обновление (хотя сложно "лечить по фотографии").


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


  1. Lexx918
    29.03.2018 14:40

    Я себе такой велосипед изобретал против параллельного обновления кэша: обернул методы set/get кэша, добавил внутри сеттера в сам кэш данные о ttl и датах создания-протухания, а потом в геттере проверял, сколько кэш уже живёт в момент обращения к нему. Если прожил 90% от своего срока, то продлевал ему время жизни ещё немного, но наружу всё равно возвращал false. В итоге код, запрашивающий данные, получал false и шёл обновлять их думая что их нет, но все прочие клиенты получали старые данные следующие пару секунд.


  1. bikutoru Автор
    29.03.2018 15:05

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