Cloudflare удалось освободить более 100 ТБ оперативной памяти в своей глобальной сети после переработки части алгоритма распределения запросов в сервисе Pingora Backend Router (PBR). Улучшение стало результатом сочетания сжатия представления точек хеширования, сокращения их количества на основе статистического анализа и поэтапного перехода, сохранившего стабильность кэширования и трафика к исходным серверам.
Проблема распределения запросов
Cloudflare использует библиотеку pingora-ketama для реализации consistent hashing — метода, который помогает по возможности направлять кэшируемые запросы на один и тот же сервер. Это позволяет хранить одну копию файла внутри центра обработки данных и обеспечивать стабильный путь доступа к нему.
Однако использование одной точки хеширования на сервер может привести к значительному различию в размерах диапазонов, которыми серверы владеют на кольце хеширования, а значит, и к различиям в рабочих нагрузках. Поэтому Pingora использует большое количество виртуальных хешей для каждого сервера с весами, связанными с объёмом хранилища. Кроме того, отдельные кольца создаются для разных наборов характеристик и ограничений. Накопление этих колец в некоторых случаях приводило к потреблению до 6 ГБ на процесс.
Оптимизация представления данных и сокращение числа хешей
Каждый элемент, представлявший точку на кольце, состоял из 32-битного хеш-значения и 32-битного указателя на сервер — всего восемь байт в памяти. Команда Cloudflare пришла к выводу, что указателю практически не требуется более 16 бит, поскольку сервис одновременно не будет координировать более примерно 65 тысяч серверов.
Одного уменьшения типа указателя оказалось недостаточно из-за правил выравнивания в Rust: размер структуры всё равно составлял бы восемь байт. Поэтому Cloudflare стала хранить значение и указатель в необработанном массиве размером шесть байт, добавив функции доступа к каждому из них. Это изменение сократило потребление памяти хешированием на 25%.
Однако наибольший выигрыш дала пересмотренная оценка количества хешей. Ранее сервис использовал базовое значение 160 точек на сервер, умноженное на вес сервера, связанный с объёмом хранилища. Анализ показал, что большое увеличение количества хешей даёт уменьшающееся улучшение погрешности: в рассмотренном Cloudflare примере добавление последних 90 тысяч хешей снизило погрешность лишь примерно на 0,7%.
Кроме того, использование 32-битных хеш-значений повышает вероятность коллизий при увеличении числа точек, что может добавить к распределению непредсказуемую погрешность. На основании расчётов и моделирования Cloudflare сократила количество хешей на сервер на 90% без заметного увеличения погрешности, что внесло вклад в итоговую экономию.
Что меняется на практике?
Одновременная замена кольца хеширования во всей сети не была безопасным вариантом, поскольку она перераспределила бы запросы и фактически привела к значительной потере эффективности кэширования, а также могла бы увеличить трафик к исходным серверам. Поэтому PBR временно хранил в памяти оба кольца — старое и новое — и выбирал между ними для каждого запроса, обеспечивая понятный путь отката.
Переход выполнялся поэтапно: сначала на небольших тестовых площадках, затем в более крупных центрах обработки данных. Управление долей запросов, использующих новое кольцо, было отделено от определения центров обработки данных, которым разрешено участвовать. Cloudflare отслеживала влияние выбора сервера, версии кольца, ошибки соединений, потребление памяти, время запуска, поведение кэширования и трафик к исходным серверам, прежде чем удалить старый путь.
Инженерное значение
Этот опыт показывает, что низкоуровневые оптимизации — например, выбор размера поля внутри структуры данных или определение подходящего количества точек хеширования — могут иметь масштабный эффект при применении в сети с тысячами серверов. В то же время результат не означает, что сокращение памяти безопасно в любой системе: перед изменением необходимо измерить точность распределения, вероятность коллизий, веса серверов, ограничения функций и способ выполнения перехода.
Изменения стали доступны в пакете pingora-ketama через пока не объявленную возможность Cargo. Версия v2 поддерживает сжатый формат хранения, более быстрый метод сортировки и возможность настраивать базовое количество хешей. При этом сохраняется версия v1, а также возможность одновременно запускать оба кольца и принимать решение на уровне запроса.