Сохраняем еще 100 ТБ оперативной памяти с помощью математики (и Rust)

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

В таком масштабе небольшие улучшения дают огромный эффект, поэтому даже оптимизации на 1% за раз заслуживают внимания. А некоторые доработки в сумме дают гораздо больший результат: в этой статье мы рассмотрим, как небольшие изменения в одном алгоритме значительно снизили потребление памяти одной из наших служб на базе Pingora. Это позволило нам высвободить более 100 ТБ оперативной памяти по всему миру в дополнение к тем 100 ТБ памяти, которые команда DNS смогла сэкономить в прошлом месяце.

Никаких отходов

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

Эта история начинается с тикета, созданного Иваном, который обнаружил: Чрезмерное использование памяти pingora-ketama в Pingora Backend Router. Выяснилось, что наша внутренняя служба балансировки нагрузки 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 базовое количество хэшей на сервер составляет hardcoded to 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$. Это позволяет нам задать «вес» для каждого сервера, который масштабирует количество хэшей, связанных с этим сервером. К сожалению, это не заменяет тот постоянный масштабный коэффициент, который мы добавили в предыдущем разделе. Такое масштабирование необходимо для задания минимальной погрешности, которая будет проявляться на серверах с наименьшими весами.

Для нас, поскольку мы хотим, чтобы рабочая нагрузка масштабировалась в зависимости от хранилища, мы можем использовать дисковое пространство в качестве веса, что и делает команда Pingora на протяжении многих лет. В других подразделениях компании, где рабочие нагрузки более требовательны к вычислениям, веса могут основываться на количестве ЦП или ГП.

Что если добавить еще больше хэшей???

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

Дублирование на основе комбинаций — это классический рецепт экспоненциального взрыва. В нашем случае у нас есть горстка различных функций, ведущая к $m2^\text{горстка} = \text{десяткам}m$ отдельных колец консистентного хэширования. Так что, как вы, вероятно, уже догадались, «чрезмерное использование памяти» (в некоторых случаях 6 ГБ), обнаруженное Иваном, было обусловлено огромным количеством хэшей для обеспечения всей необходимой нам функциональности, которые должны храниться в оперативной памяти.

Усовершенствования хранения

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

В памяти она представлена как восемь байт, где четыре уходят на хэш (чего нельзя избежать), а четыре — на индекс, указывающий на сервер, который хранится в другом массиве. Идея Зайдуна заключалась в том, что 32-битное целое число для этого индекса является избыточным, поскольку PBR вряд ли когда-либо придется координировать более чем $m2^{16} \approx 65\text{тыс.} m$ серверов одновременно, поэтому подойдет и 16-битное целое число. Таким образом, мы можем заменить приведенную выше структуру на эту:

К сожалению, Rust не делает это простым. Изменение размера индекса, как мы сделали выше, никак не снижает объем занимаемой памяти. Это происходит потому, что в Rust действуют правила выравнивания, которые требуют, чтобы размер структуры в памяти был кратен ее наибольшему (или «наиболее выровненному») полю. В данном случае хэш является самым большим с четырьмя байтами, поэтому при хранении в памяти Point должен иметь размер $mN \times 4m$, то есть минимальный размер составляет восемь байт.

К счастью, существуют хорошо известные способы обойти это. У вас (то есть у меня) может возникнуть соблазн использовать #[repr(packed)], но это является спорным по уважительным причинам. Более безопасное, но менее читаемое решение заключается в хранении хэша и индекса в виде сырого массива байтов и обращении к ним с помощью геттеров. Оба метода компилируются в одно и то же.

Это простое (хотя и многословное) изменение сокращает объем памяти, используемой для консистентного хэширования, на целых 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$ выявляет потенциальную проблему менталитета «просто добавь больше хэшей» (мимо перерасхода оперативки).

Вы можете видеть, что каждый шаг уменьшения погрешности требует (почти) на порядок большего увеличения количества хэшей на сервер, поэтому добавление новых хэшей приносит все меньшее и меньшее улучшение. Напомним, что мы используем базу из 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% без возникновения какой-либо заметной погрешности, и именно это мы и решили сделать.

Миграция без перегрузки серверов-источников

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

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

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

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

В ходе миграции мы следили за трассировками выбора бэкенда, счетчиками версий колец, ошибками соединения PBR, памятью процессов, временем запуска, поведением кэша и трафиком источников. Как только миграция достигла 100%, мы удалили временный путь со старым кольцом, и вуаля!

На графике выше показано сравнение памяти, используемой PBR на неделе изменения, с данными за несколько недель до этого, а также результат вычитания одного из другого. Резкий спад — это день, когда версия PBR с большими (теперь неиспользуемыми) хэш-кольцами была выведена из эксплуатации навсегда. Глядя на разницу, мы получаем впечатляющий результат: наши изменения сократили используемую память на 100 ТБ!

Попробуйте сами

Все изменения, о которых мы рассказали в этом посте, теперь доступны в крейте pingora-ketama в виде (пока еще) неанонсированной функции cargo. Кольцо v2 имеет компактный формат хранения, более быстрый метод сортировки и возможность масштабировать базовое количество хэшей на узел. Нашим приоритетом при внесении этих изменений были стабильность и контроль, поэтому кольцо v1 идентично тому, что всегда использовал pingora ketama, а библиотека позволяет запускать их оба одновременно и решать для каждого запроса индивидуально, какое из них и когда использовать.

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