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

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

Ничего лишнего

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

Эта история начинается с тикета, созданного Иваном, который обнаружил: Чрезмерное использование памяти pingora-ketama в Pingora Backend Router. Выяснилось, что наша внутренняя служба балансировки нагрузки Pingora Backend Router (да, PBR) использует значительно больше памяти, чем ожидалось, в частности, в структурах, связанных с pingora-ketama, нашей библиотекой с открытым исходным кодом для реализации консистентного хеширования.

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

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

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

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

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

Улучшения хранения

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

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