Мы в вебе живём хорошо, потому что все данные у нас отдаются из кешей.
А что если их там нет? А что, если их там теперь нет? Обрекаем базу данных на хабраэффект?

А что будет, если даже кеш не справляется с нагрузкой?

Дисклеймер

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

Термины

Кеш - любое хранилище посчитанных результатов вычислений, отвечающее заметно быстрее классической базы данных.
Ключ - строка, по которой мы адресуем данные в кеше.
TTL - time to live - время жизни ключа в кеше, по истечении которого он исчезает из кеша.
Во всех примерах будем класть данные в кеш на минуту.
Протухнуть - "Ключ протух" - когда ключ перестал существовать из-за достижения TTL.
RPS - requests per second - число запросов в секунду со стороны пользователей.
QPS - queries per second - число запросов в секунду в базу данных со стороны веб-серверов.
Спайки или удары - моменты аномально резкого роста числа запросов, которые тут же возвращаются к обычному уровню запросов. Если термин "спайки" (от англ spike - шип) ещё распространён среди людей, смотрящих на графики и видящих эти самые рисунки шипов, то термин "удар" - чисто моя авторская выдумка. Буду чаще использовать его, так как это моя прямая ассоциация с тем, что мы делаем с базой данных в такие моменты: наносим удар кувалдой по серверу и смотрим, выдержал ли он.
Норм - оценка для production-ready решения.

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

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

Дисклеймер 2

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

Вероятность наступления события в 80% - это всё ещё 80%, а не 100%, как мозг хочет округлить. В 2 из 10 вселенных событие так и не наступит.
Вероятность наступления события в 99.99% не гарантирует его наступление. Именно у вас оно не наступит.
Вероятность наступления события в 0.01% не гарантирует, что оно не случится. Именно у вас оно случится.
Теорвер работает на больших числах. Чем меньше событий, тем сильнее реальный мир отличается от предсказанного теорвером. А потому найдите ложь в первом тезисе про 80%.

Теперь к статье.

Просто добавь кеш, и проблемы уйдут

Кеш - чаще первое, что приходит на ум, когда приходит продакт и говорит: "эээ, блин, а чего у вас приложение отвечает 2-3 секунды? Юзеры отваливаются, сократите ответ до 50мс".
Кеш - первое, что приходит на ум, когда приходит базовик и говорит: "а чего у вас такой бешеный QPS на базу? Она не выдерживает".
Кеш - первое, что приходит на ум, когда приходит сетевик и говорит: "а чего у вас гигабит трафика между серверами? Канал переполнен".

Создадим аварию в лабораторных условиях

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

Распределение трафика. Толщина линий соответствует количеству запросов

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

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

Целую минуту нам хорошо - необходимые данные берутся из кеша.

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

На среднем сайте никто бы этого не заметил. Но у нас хайлод-перехайлод.
Если обновление значения занимает хотя бы 50 миллисекунд, то при 1млн rps за эти 50мс наберётся 50 000 запросов, которые тоже провалились в базу.
База умирает от внезапной нагрузки (50к запросов за 50мс, Карл!), и перестаёт отвечать не только для популярного видоса, но и вообще для всего сайта.

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

Садимся решать проблему, и кто-то задаст вопрос:
- а мы можем не посылать 1 миллион запросов в базу?
- да, но...

Нужен распределённый лок на запись

Если читаете статью по диагонали - не вздумайте применять!

Наивное решение: пусть кто-то один обновит кеш для всех, а остальные подождут. И тогда для выбора "избранного" нужен какой-то распределённый лок внутри сети. Кто захватил лок - тот избранный, обновляющий кеш. Остальные ждут, пока он отпустит лок.

Пусть у нас есть в сети будет сервер, который будет заведовать локами. Назовём его "Железка L". У идеи заведения такой железки сразу вылезают недостатки эксплуатации.

1 млн запросов хотят захватить лок. Как бы вы ни реализовали эту схему, железка L офигеет от нагрузки. Что делать серверам, которые в ответ на захват лока получили от железки не true, не false, а connection timeout ? Им всем надо идти в базу? или надо чего-то ждать? Чего? И как долго? Все эти вопросы не имеют хороших ответов.

Если железка L, всё-таки прилегла от нагрузки, то выполняющий работу веб-сервер может не суметь снять свой лок. Например, его запрос слишком долго стоит в очереди на исполнение железкой L и тоже у��ирает по таймауту. Что тогда делать коду избранного сервера? Повторно ддосить запросом на снятие лока? Как долго? А если это "долго" истекло, что делать?

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

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

Нужен нераспределённый лок на запись? (нууу, возможно)

Идею можно упростить и убрать все минусы распределённости: пусть лок будет не где-то в сети, а внутри веб-сервера. По одному локу ключа на сервер. Если сервер держит 5 000 rps, то для обработки 1млн запросов нам нужно 200 серверов, каждый из которых выставит себе внутренний лок, блокирующий 4999 запросов, и каждый из которых сделает только один запрос в базу. Звучит более реалистично, база может выдержать 200 qps.

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

И с этим решением всё ещё может выстрелить проблема нехватки тредов и коннектов при простаивающем процессоре.

Лочимся без локов

Как известно, лучший код тот, которого не существует. То же самое относится и к локам.
Нашего лока не будет существовать, нашим локом будет теорвер.

Подход 1: линейная вероятность обновления ключа

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

$P = \frac{t_{passed}}{TTL}$

Визуализация вероятности по этой формуле

Её логика такая: давайте попробуем обновить кеш пораньше.
Если сейчас не получилось, то давайте в следующий раз попробуем обновить кеш с шансом побольше.
ОЙ, У НАС НЕ ПОЛУЧАЕТСЯ, ДАВАЙТЕ ОБНОВИМ С ЕЩЁ БОЛЬШИМ ШАНСОМ, ПОКА ОН НЕ ПРОТУХ ОКОНЧАТЕЛЬНО!

Чем ближе к "катастрофе", тем выше шанс на попытку её предотвращения.

Кто догадается, почему в нашем проекте точки (0.5, 0.5) не существует? Почему база данных не будет получать запрос для обновления кеша с вероятностью в 50% после истечения 0.5 TTL?

Разнос линейной вероятности

У игроков D'n'D есть понятие "преимущества" - когда бросается 2 кубика и берётся результат лучшего. И игроки знают, насколько приятно меняется распределение вероятностей, когда у тебя есть вторая попытка на прохождение проверки.

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

Если у нас 10 rps, и прошло 10% от TTL, то вероятность, что хотя бы один пойдёт за обновлением, равна 1 - (1 - 0.1)^10 = 0.65, а мат.ожидание уже равно 1. А не дофига ли это?

А что будет при других rps?
Смоделируем шансы.

Воу, как плющит графики уже на 50 rps.

Разберём подробнее ситуацию с 10k rps. Если прошло 0.001TTL, мат.ожидание нам говорит, что 1 запрос дойдёт до базы, 9999 - нет. База уже заметно разгружена. Успех? Да. И нет. Мы положили ключ в кеш на минуту, а уже где-то через 6мс (!!!) кто-то идёт за ним снова. Это совсем не тот тайминг, который хотел бы видеть базовик, когда ему разрабы говорят, что у них есть кеш.

К формуле есть костыль: мы можем попробовать опустить графики, поделив вероятность на коэффициент k. Коэффициент подбирается пальцем в небо.

$P = \frac{1}{k} * \frac{t_{passed}}{TTL}$

И хороший теоретик сейчас должен разбить лоб 🤦‍♂️. Потому что в формуле заложена ошибка в виде невозможности плавного достижения вероятности в 100%. При достижении t = TTL ключ протухает, и все запросы гарантированно уйдут в базу, как при резком скачке P до 1.

С этой ошибкой попробуем промоделировать шансы на обновление кешей с разными rps.
Тыкаем пальцем в небо, и небо говорит: пусть k = 300.

Вероятности с учётом rps и коэффициента k

Как будто для 1000 rps сделали лучше, для 10k - всё ещё плохо, а для остальных rps всё сломали.

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

Так как нет ни одного видео с абсолютно одинаковым rps, мы всегда будем промазывать с оценкой k в обе стороны. Но может вам норм, если линия на 100 rps будет бить по базе? И может у вас никогда не будет 10 000 rps, и k = 300 хватит всем?
Надо тестить.

Минусы подхода:

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

Подход 2: гнём кривую вероятности по экспоненте.

Возьмём формулу, хорошо знакомую из школы: экспоненту. Помните, как мы в старших классах бесконечно рисовали параболы? Так вот, это она. Точнее её фрагмент. Вот эта формула:

$P = (\frac{t_{passed}}{TTL})^e$

Просто примем тот факт, что она хороша. Она проходит через точки (0,0) и (1,1). В ней есть тот самый изгиб вниз, которого нам не хватало в прошлом подходе.

Экспоненциальная вероятность обновления кеша одним запросом

Давайте посмотрим, каковы шансы на походы в базу при разных rps.

Экспоненциальная вероятность обновления кеша хотя бы одним запросом с учётом rps

Что ж, на 10 000 rps всё ещё ходим в базу, но уже не каждые 6мс, а каждые 60мс. Лучше, но ещё плохо.

Попробуем применить снова хак с коэффициентом k, просто поменяв показатель степени, и посмотрим, на что он повлияет. От показателя зависит, насколько выгнутой будет парабола на отрезке [0; 1.0]

$P = (\frac{t_{passed}}{TTL})^\frac{e}{k}$

Снова спрашиваем пальцем у неба, какое взять k. Небо говорит: k = 5.
И вот как будут выглядеть распределения вероятностей на хотя бы один поход в базу.

Уже лучше: где-то до 0.4 TTL кеш живёт спокойной жизнью на нагруженных видосах с 10k rps. Это целых 24 секунды покоя для всех, в том числе для базы данных.

А дальше мы где-то в начале подъёма графиков будем пускать несколько запросов обновить ключ, создавая совсем маленькую нагрузку на базу.

Минус подхода: кривые слишком вертикальные, если нам по какой-то причине не повезло обновить кеш в начале подъёма графика, то довольно быстро мы поднимаемся к его верху и почти все запросы отправляем мимо кеша. Это сравнимо с тем самым "ударом".

Уменьшаем боль базы, когда нам не повезло

Мы всячески снижаем шансы на получение удара по базе данных вынужденным обновлением ключей. Но что делать, если удар всё-таки случился?
Оказывается, базе можно сделать менее больно.

Подход 3: N ключей.

Давайте заведём не 1 ключ, а N. Например, vid1#1, vid1#2, vid1#3, ..., vid1#N. И поделим между ними запросы равномерно.

Главный трюк: каждому из ключей выставим случайное время жизни
MAX_TTL * rand(0.8, 1.0)

Мы всё ещё получаем удары запросами по базе, но их размеры уменьшены в N раз, и они разнесены во времени.

Помните Спайка? При N = 3 теперь и спайков 3, и все в 3 раза меньше исходного.

Возможно, на вашем проекте этот способ норм сам по себе без связки с другими. Да пусть стабильно будут мелкие удары. Но они мелкие! База может выдержать. Зато не надо писать математику в коде, и в кеш льём в N раз меньше данных за раз.

Минусы подхода:

нужно xN памяти в кеше.
С каждой копией ключа добавляем больше источников знаний (но не истины), повышаем риск, что они будут хранить разные данные после ошибок.
Примеры ошибок: сетевые; перегрузка cpu кеша и отвал запроса по таймауту.

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

Из личного опыта ещё дам наблюдение, что лучше всем им жить и обновляться раздельно. То есть если протух vid1#3 , то сервер должен обновить не все ключи, а только vid1#3. На реально больших нагрузках я ловил эффект укладывания кеша по CPU на попытке записать данные во все N ключей с нескольких веб-серверов, обнаруживших пропажу единственного ключаvid1#3.

Кеш тоже можно упороть чтением.

Поэтому делаем больше чтений!

Будем честными: даже кеширующий сервер со всеми данными в памяти не сможет ответить на миллион запросов в секунду. Более правдоподобно - тысячи обработанных rps на ядро процессора. Делить данные по N ключам на разных шардах - уже обязательное требование.

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

Попадание двух особо популярных ключей на один шард

Костыль на этот случай из моей практики: пробовать читать из нескольких ключей по очереди. vid2#2 - таймаут. vid2#12 - успех. Упоротый шард с vid2#2 не провоцирует запросы в базу. Часто такое решение норм.

Но что будет, если запасной шард с vid2#12 тоже упорот совместной нагрузкой от другого популярного ключа vid3#6? Костыль снизил шанс проблемы, но не убрал её.

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

Такое желание приводит к решению: будем задавать разные значения N для разного контента.

Подбираем N, N, и потом подберём N.

Обратимся к реальным данным. Посмотрите на таблицу пиковых трансляций у стримеров твича.
Только 10 стримеров собирают больше миллиона зрителей в моменте.
Всего 457 стримеров собирают больше 100 000.

10 и 457 - довольно маленькое количество авторов, но именно они создают нам все проблемы. Делать одинаковые формулы для них и для миллионов других пользователей - не вариант.

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

Во-первых, можно вручную посадить всё на жёсткий конфиг на основе уже имеющейся аналитики. Пропишем, что вот конкретно у этих 457 стримеров N = 20, а у топ10 - N = 200.

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

Предлагаю сделать так:

$N = ceil(\frac{зрители}{10\_000})$

Для большинства видео N будет достаточно маленьким. Выберем, что N < 5 мы вообще не будем помещать в конфиг, чтобы не он не разрастался. Число 5 я снова взял пальцем в небо.

Событие подключения и отключения от трансляции очень частое. Чтобы не занимать все CPU датацентра пересчётом нового N, его тоже можно делать вероятностным. Будем пересчитывать N только в 1/5_000 случаев.
Поверьте, нагрузку это снимет, а теорвер отработает как надо. Ну сработаает он из-за дисперсии при 92_342 юзерах, а не строго при 90_000 - и пофиг же. N к тому моменту уже будет выставлено в 9, и будет пересчитано на 10. Разница уже не такая большая, от небольшой задержки пересчёта шарды испытают в этом случае аж 11% избыточной нагрузки. И пофиг!

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

Фух, кажется, живём.

Итого

На самом деле фиг его знает, как готовить кеш правильно. Но базовые советы получились такими:

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

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

Давим шипы костылями — о методах борьбы с проливом запросов мимо кешей