Экономия еще 100 ТБ оперативной памяти с помощью математики (и Rust)
Cloudflare работает в таких масштабных объемах, что даже после долгих лет работы здесь это кажется нереальным. У нас есть тысячи серверов по всему миру с петабайтами оперативной памяти и миллионами ядер процессоров, и все это используется на пределе возможностей. Какими бы огромными ни казались эти ресурсы, они все же конечны, и когда вам нужно, чтобы каждый сервис запускался на каждом узле, места для пустующего пространства не остается.
В таких масштабах небольшие улучшения дают огромный прирост, поэтому даже оптимизации уровня 1% за раз заслуживают того, чтобы их отметить. А некоторые доработки в сумме дают гораздо больше: в этой статье мы рассмотрим, как небольшие изменения в одном алгоритме значительно сократили потребность в памяти для одного из наших сервисов на базе Pingora. Это позволило нам высвободить более 100 ТБ оперативной памяти по всему миру — вдобавок к тем 100 ТБ памяти, от которых команда DNS смогла избавиться в прошлом месяце.
Никаких отходов
Поддерживать справедливое распределение ресурсов между командами непросто, особенно в крупных организациях. Один из способов, с помощью которого Cloudflare обеспечивает этот баланс — неустанная работа замечательной команды производительности (Performance team).
Эта история начинается с тикета, созданного Иваном (Ivan), который обнаружил следующее: Чрезмерное потребление памяти со стороны pingora-ketama в маршрутизаторе бэкендов Pingora. Выяснилось, что наш внутренний службы балансировки нагрузки, Pingora Backend Router (да, PBR), использует значительно больше памяти, чем ожидалось — в частности, в структурах, связанных с pingora-ketama, нашей библиотекой с открытым исходным кодом для реализации согласованного хэширования (consistent hashing).
Чтобы рассказать о том, как мы справились с этим мнимым перерасходом памяти, нам нужно поговорить о том, что вообще такое согласованное хэширование, почему мы используем его в PBR и как оно стало таким «прожорливым» до памяти. Попутно мы немного изучим Rust и даже затронем математику.
Согласованное хэширование
Согласованное хэширование — это широко используемый метод распределения задач по нескольким серверам таким образом, чтобы не требовалось масштабных изменений при добавлении или удалении серверов. Внутри компании мы используем его для маршрутизации кэшируемых запросов к серверам по URL-адресу. Это позволяет нам хранить только одну копию файла в каждом дата-центре и дает стабильный способ найти местонахождение каждого файла. Мы уже упоминали этот систему ранее, но давайте найдем время и разберем, как и почему используется этот алгоритм и как он работает.
Ключевая концепция согласованного хэширования заключается в том, что хотя хэш-функции могут принимать любые входные данные, их вывод ограничен одним целым беззнаковым числом (32-, 64- или 128-битными целыми числами в зависимости от хэш-функции). Это позволяет нам связывать задачи и серверы между собой согласованным образом. В большинстве обсуждений согласованного хэширования предлагается представлять это пространство вывода как непрерывное цикличное кольцо, которое замыкается от максимального значения до нуля. Такое изображение позволяет получить наглядные визуализации, но оно также может сделать простую концепцию диапазонов целых чисел более сложной, чем нужно. Для нашего обсуждения мы представим 32-битный вывод нашей хэш-функции в виде числовой прямой.
Теперь предположим, что у нас есть набор серверов (A, B и C) и набор задач (t–z). Мы можем отобразить каждую из них на числовой прямой на основе хэша их репрезентативных значений (например, IP-адресов для серверов и ключей кэша для задач).
Назначение задач серверам теперь сводится к поиску первого сервера слева от каждой задачи. Мы можем представить это визуально, закрасив область хэшей, которая будет связана с каждым сервером. Обратите внимание, что диапазон, охватываемый сервером C, закольцовывается и уходит в начало — отсюда и идея о том, что хэши существуют в виде кольца.
Вот и все. На базовом уровне согласованное хэширование устроено очень просто, но вскоре становится очевидно, что здесь есть простор для улучшений. Обратите внимание, что диапазон, охватываемый сервером A в нашем примере, значительно больше, чем у B или C. Это проблема, поскольку доля запросов, обрабатываемых сервером, будет пропорциональна размеру его диапазона на числовой прямой. В идеале мы хотели бы гарантировать, что у каждого сервера будет одинаковый размер, но поскольку хэши по сути являются случайными числами, нам приходится говорить о размерах областей в терминах статистики.
Математика и ее последствия
Во-первых: без паники. Обещаю, я не собираюсь вас обманывать, и мы останемся в безопасных рамках вводного урока по теории вероятностей. Когда мы говорим о статистических распределениях, есть два важных фактора, которые помогают нам полезным образом оценить неопределенность: математическое ожидание и среднеквадратичное отклонение. Говоря (слишком) простым языком, математическое ожидание дает нам точку, вокруг которой будут сосредоточены измерения на основе распределения, а стандартное отклонение показывает, насколько близко к этой центральной точке находится большинство измерений.
Для согласованного хэширования мы можем рассчитать эти факторы для относительного размера диапазона, связанного с одним из N серверов. (Подробности о том, откуда берется эта формула, будут позже).
$$m
\begin{align*} \text{Exp} &= \frac{1}{N} \\ \text{SD} &= \frac{1}{N}\sqrt{\frac{N-1}{N+1}} \end{align*}
m$$
Говоря о конкретных цифрах, предположим, что у нас есть 100 серверов. Приведенные выше формулы дают:
$$m
\text{Exp}=1/100 = 1\% \\
\text{SD}= \frac{1}{100}\sqrt{\frac{100–1}{100+1}} \approx 0.99\%
m$$
Это говорит нам о том, что диапазон, обслуживаемый каждым сервером, будет центрирован примерно на 0.99% от общей длины, и большая часть значений попадет в пределы 1% от ожидаемого. Это звучит неплохо, пока мы не осознаем, что речь идет о 0.99% от общей длины. Нам нужно масштабировать среднеквадратичное отклонение по математическому ожиданию, чтобы увидеть, насколько велика погрешность в долях от целевого размера. Это значение называется коэффициентом вариации.
$$m
\text{CV} = \frac{\text{SD}}{\text{Exp}} = \sqrt{\frac{N-1}{N+1}}
m$$
При $m N=100, \text{CV} \approx 99\% m$ — это означает, что некоторые серверы, вероятнее всего, будут работать на 99% интенсивнее, чем следует (обрабатывая в два раза больше запросов), в то время как другие могут практически бездельничать! Теперь, когда у нас есть способ предсказать равномерность нагрузки на серверы при согласованном хэшировании, мы можем приступить к улучшениям.
Что, если мы добавим хэши?
Простота согласованного хэширования — это палка о двух концах. Его легко понять и реализовать, потому что все преобразуется в легко сопоставимые хэши на одной числовой прямой, но любые улучшения системы также должны быть привязаны к этой числовой прямой. Это означает, что решением любой проблемы согласованного хэширования могут быть только новые хэши. Это меньше похоже на золотой молоток (инструмент, с которым любая проблема кажется гвоздем) и больше на золотой гвоздь, который превращает любые инструменты в молотки.
Чтобы решить проблему несбалансированных рабочих нагрузок, мы можем добавить несколько хэшей для представления каждого сервера вместо одного. Мы вернемся к стоящей за этим математике чуть позже, но интуитивно должно быть понятно, что хотя каждый отдельный диапазон имеет большое среднеквадратичное отклонение, объединение их множества должно сгладить их общий размер. Если мы возьмем наш пример с тремя серверами из предыдущих схем и случайно добавим еще два хэша для каждого сервера, мы увидим, что это помогает выровнять нагрузку каждого сервера.
Это, по признанию, надуманный пример. Случайный характер системы означает отсутствие гарантий того, насколько улучшится ситуация при добавлении 2 дополнительных хэшей на сервер, но интуитивно понятно, что объединение большего количества таких сегментов хэшей приводит к более равномерному распределению. Каждый сегмент в сумме имеет шанс сбалансировать другой. Возможно, один слишком короткий, а другой слишком длинный. Именно об этом говорит нам закон больших чисел… Очевидная проблема заключается в том, что он работает только для больших чисел. В NGINX базовое число хэшей на сервер жестко зашито на уровне 160, и Pingora использует такое же значение по умолчанию. Я избавлю вас от математических выкладок, но если мы вернемся к нашему примеру со 100 серверами и используем 160 точек на сервер вместо одной, коэффициент вариации (который можно воспринимать как погрешность) упадет примерно с 99% до примерно 8%, что является значительным улучшением.
Что, если мы добавим еще больше хэшей?
Как мы видели выше, увеличение числа хэшей на сервер на постоянную величину позволяет улучшить равномерность распределения нагрузки по серверам, но что если мы не хотим распределять работу равномерно? В случае Cloudflare у некоторых серверов больше дискового пространства, чем у других, поэтому было бы лучше, чтобы количество запросов, выделяемых серверу, было пропорционально его дисковому пространству. Один из способов добиться этого — алгоритм ketama. У этого названия забавное происхождение: алгоритм назван в честь библиотеки, в которой он был впервые реализован, а библиотека была названа… ну, вы можете погуглить это ️.
Весь алгоритм сводится к следующему: для любых двух серверов, $m S_1m$ и $mS_2m$, если мы хотим, чтобы запросы, обслуживаемые $mS_1m$, составляли $mw\timesm$ от запросов, обслуживаемых $mS_2m$, количество хэшей, связанных с $mS_1m$, должно быть равно $mH_1 = w\times H_2m$. Это позволяет нам установить «вес» (weight) для каждого сервера, который масштабирует количество связанных с ним хэшей. К сожалению, это не заменяет тот постоянный масштабный коэффициент, который мы добавили в предыдущем разделе. Это масштабирование необходимо для задания минимальной погрешности, которая будет проявляться на серверах с наименьшими весами.
Поскольку мы хотим, чтобы рабочая нагрузка масштабировалась в зависимости от объема хранилища, мы можем использовать дисковое пространство в качестве веса — именно так команда Pingora поступала на протяжении многих лет. В других подразделениях компании, где рабочие нагрузки более ресурсоемкие, веса могут основываться на количестве ядер CPU или GPU.
Что, если мы добавим еще больше хэшей???
Последняя проблема, которую нам нужно решить, заключается в том, что до сих пор мы исходили из допущения, будто любой сервер может обработать любой запрос, но на практике это не так. Требования комплаенса или включенные функции кэширования означают, что только подмножество серверов может обработать тот или иной запрос. К сожалению, в отличие от прошлого раза, мы не можем решить эту проблему, просто добавив больше хэшей в то же кольцо. Нам приходится добавлять совершенно новые кольца, и мало того — каждая комбинация функций потенциально требует собственного специфического кольца!
Дублирование на основе комбинаций — классический рецепт экспоненциального взрыва. В нашем случае у нас есть горстка различных функций, что приводит к появлению $m2^\text{handful} = \text{dozens}m$ отдельных колец согласованного хэширования. Так что, как вы, вероятно, уже догадались, «избыточное использование памяти» (в некоторых случаях достигающее 6 ГБ), обнаруженное Иваном, было обусловлено колоссальным количеством хэшей для обеспечения всей необходимой нам функциональности, которые приходится хранить в памяти. И что же нам делать?
Оптимизация хранения
Одно крупное улучшение предложил Зайдун (Zaidoon), которого осенило озарение относительно нашей структуры (struct) для хранения хэшей в PBR. Эта структура выглядит следующим образом:
struct Point {
hash: u32,
index: u32,
}
В памяти она представляется в виде восьми байт: четыре уходят на хэш (чего не избежать) и четыре — на индекс, указывающий на сервер, который хранится в другом массиве. Инсайт Зайдуна заключался в том, что 32-битное целое число для этого индекса неэффективно, поскольку PBR вряд ли когда-либо придется координировать более $m2^{16} \approx 65\text{k} m$ серверов одновременно, так что будет достаточно 16-битного целого числа. Таким образом, мы можем заменить описанную выше структуру следующей:
struct PointV2 {
hash: u32,
index: u16,
}
К сожалению, в Rust все не так просто. Изменение размера индекса, как мы сделали выше, ничего не дает для сокращения потребления памяти. Все потому, что в Rust действуют правила выравнивания (alignment), которые требуют, чтобы размер структуры в памяти был кратен ее наибольшему (или «наиболее выровненному») полю. В данном случае хэш является самым крупным полем (четыре байта), поэтому при хранении в памяти структура Point обязана иметь размер $mN \times 4m$, то есть минимальный размер составляет восемь байт.
К счастью, существуют хорошо известные способы обхода этого ограничения. У вас (то есть у меня) может возникнуть искушение использовать #[repr(packed)], но это спорное решение по веским причинам. Более безопасное, хотя и менее читаемое решение — хранить хэш и индекс в виде сырого массива байтов и получать к ним доступ с помощью геттеров. Оба метода компилируются в один и тот же машинный код.
struct Point([u8; 6]);
impl Point {
fn hash(&self) -> u32 {
u32::from_ne_bytes(self.0[0..4].try_into().unwrap())
}
fn index(&self) -> u16 {
u16::from_ne_bytes(self.0[4..6].try_into().unwrap())
}
}
Это простое (пусть и многословное) изменение сокращает объем памяти, используемой для согласованного хэширования, на колоссальные 25%! Чтобы добиться лучшего результата, нам нужно снова вернуться к математике, так что держитесь крепче — это финишная прямая.
Что, если мы попробуем использовать меньше хэшей?
Возможно, вы заметили, что мы привели формулу стандартного отклонения для случая, когда на каждый сервер приходится только один хэш. Вывод формулы для случая, когда на сервер приходится $m k m$ хэшей, непрост, и большинство источников дают лишь приближение или асимптотический предел, но только не мы. Я, может, и не статистик, но вырос с преподавателем математики (привет, мам!) и хотел узнать реальное значение. Полный вывод приведен в дополнительной статье, но вот результат.
$$m
\text{Exp}_k = \frac{1}{N},
\text{SD}_k=\sqrt{\frac{(k+1)}{N (kN+1)}-\frac{1}{N^2}}
m$$
Чтобы увидеть, как увеличение количества хэшей повышает точность, нам нужно снова взглянуть на коэффициент вариации.
$$m
\text{CV}_k=\frac{\text{SD}_k}{\text{Exp}_k}=\sqrt{\frac{N-1}{(N*k+1)}}
m$$
Построение графика $m\text{CV}_km$ выявляет потенциальную проблему подхода «просто добавьте больше хэшей» (помимо чрезмерного расхода RAM).
Как видите, каждое снижение погрешности требует (почти) на порядок большего количества хэшей на сервер, поэтому добавление новых хэшей дает все меньший и меньший прирост эффективности. Напомним, что мы используем базовое значение в 160 хэшей, масштабируемое по размеру хранилища сервера. Для простоты вычислений предположим, что весовой коэффициент $m{m_w}m$ для сервера равен 625, то есть мы получаем $m{k = 160\times625 = 100{,}000}m$. Из графика выше видно, что последние 90 000 добавленных хэшей дают нам микроскопическое снижение погрешности на 0,7%. К сожалению, дальше становится только хуже.
Предсказания на основе моей прекрасной математики работают только в том случае, если мы рассматриваем хэши в непрерывном кольце, но на практике мы используем 32-битные числа для хэшей, которые могут вызывать коллизии, и вероятность коллизий возрастает на удивление быстро по мере увеличения числа хэшей (см. парадокс дней рождения). Коллизии имеют значение, потому что в идеальном случае каждый хэш вносит свой вклад в объем и распределение запросов, обрабатываемых соответствующим сервером, но коллизия означает, что некоторые вклады случайно отбрасываются, привнося непредсказуемую погрешность. Если сравнить результаты симуляции с 32-битными хэшами с предсказанным уровнем погрешности, мы увидим, что для дата-центров с 2048 серверами уровень погрешности возрастает в диапазоне от 10 000 до 100 000 хэшей на сервер.
В конечном счете, хотя это осознание кажется не самым приятным, это отличная новость для нашего плана по высвобождению оперативной памяти! Теперь, когда у нас есть математическое обоснование, мы определили, что можем уменьшить количество хэшей, генерируемых для каждого сервера, на 90% без возникновения какой-либо заметной погрешности, и именно это мы и решили сделать.
Миграция без плавления источников
Оставалась еще одна проблема: изменение хэш-кольца меняет маршруты некоторых кэшируемых запросов. Даже если новое кольцо лучше, единовременное переключение всей сети фактически сделало бы недействительным практически весь кэшированный контент. Это превратило бы оптимизацию памяти в апокалиптический рост трафика на исходных серверах (origin traffic).
Поэтому мы не стали делать это единым глобальным переключением. Некоторое время PBR держал в памяти обе версии кэшируемого балансировщика нагрузки: старое кольцо ketama и новое, меньшего размера. Каждый запрос использовал наш стандартный фреймворк миграции для определения того, какое кольцо должно выбирать бэкенд. Это означало, что решение о выкатке было стабильным для каждого хэша запроса, а также давало нам чистый путь для отката. Если что-то шло не так, мы могли отправить новые запросы обратно через старое кольцо без переразвертывания PBR.
Затем мы развертывали миграцию послойно. Мы начали с небольших проверочных локаций, перешли к постепенно увеличивающимся группам дата-центров и только после этого продолжили распространение на остальной мир.
Важно отметить, что мы независимо контролировали два параметра: какой объем трафика использует новое кольцо и куда этому трафику разрешено перемещаться. Простая глобальная выкатка по процентам привела бы к распространению вытеснения кэша (cache churn) повсюду одновременно. Выкатка в рамках дата-центров позволила сохранить малый радиус поражения и значительно упростила определение того, действительно ли изменение безопасно.
В ходе миграции мы следили за трассировками выбора бэкенда, счетчиками версий колец, ошибками соединения PBR, памятью процессов, временем запуска, поведением кэша и трафиком бэкендов. Как только миграция достигла 100%, мы удалили временный путь со старым кольцом — и вуаля!
На графике выше показано сравнение памяти, используемой PBR на неделе внедрения изменений, с данными за несколько недель до этого, а также результат вычитания одного из другого. Резкое падение приходится на день, когда версия PBR с большими (теперь уже неиспользуемыми) хэш-кольцами была выведена из эксплуатации навсегда. Глядя на разницу, мы получаем впечатляющий результат: наши изменения сократили используемую память на 100 ТБ!
Попробуйте сами
Все изменения, о которых мы рассказали в этой статье, уже доступны в крейте pingora-ketama в виде (пока еще) неанонсированной функции cargo. Кольцо v2 имеет компактный формат хранения, более быстрый метод сортировки и возможность масштабирования базового количества хэшей на узел. Привнося эти изменения, мы были обязаны сосредоточиться на стабильности и контроле, поэтому кольцо v1 идентично тому, что всегда использовалось в pingora-ketama, а библиотека позволяет запускать оба кольца одновременно и на основе каждого конкретного запроса решать, какое из них и когда использовать.
Помимо использования наших конкретных изменений в согласованном хэшировании, я бы хотел, чтобы вы вынесли из этой истории вдохновение копнуть вглубь собственных систем и посмотреть, какие «простые» или «очевидные» решения скрывают потенциальные победы, если вы готовы погрузиться в цифры. Возможно, вы не сможете решить все свои проблемы с помощью Rust, но математика универсальна.
