Cloudflare высвободила ещё 100 ТБ RAM с помощью математики

История началась с тикета инженера Ивана: он обнаружил, что pingora-ketama, открытая библиотека Cloudflare для consistent hashing (консистентного хеширования), потребляет в внутреннем балансировщике нагрузки Pingora Backend Router (PBR) значительно больше памяти, чем ожидалось. Разбираться пришлось с самим алгоритмом.

Consistent hashing распределяет задачи (в случае Cloudflare, кэшируемые запросы по URL) между серверами так, чтобы при добавлении или удалении серверов не приходилось массово перераспределять всё заново: и серверы, и запросы превращаются в числа на одной шкале (хеши), и каждый запрос уходит к ближайшему слева серверу. Проблема в том, что при одном хеше на сервер диапазоны получаются неравными, а значит и нагрузка распределяется неровно. Cloudflare посчитала это математически через ожидаемое значение и стандартное отклонение, а конкретно, через коэффициент вариации (отношение стандартного отклонения к ожидаемому размеру диапазона, показывающее относительную погрешность). На примере из 100 серверов: при одном хеше на сервер коэффициент вариации, около 99%; если добавить по 160 хешей на каждый сервер (это захардкоженное в NGINX и используемое по умолчанию в Pingora число), погрешность падает примерно до 8%. Дополнительно Cloudflare использует взвешенный вариант такой схемы, алгоритм ketama, чтобы серверам с большим объёмом диска доставалась пропорционально бОльшая доля запросов; для наборов серверов, которые из-за требований комплаенса или включённых функций кэширования могут обслуживать не любой запрос, приходится заводить отдельные кольца хешей под каждую комбинацию условий.

Первое улучшение памяти нашёл инженер Зайдун (Zaidoon): он предложил переупаковать структуру Point, в которой PBR хранит каждый хеш вместе с индексом сервера. Изначально структура состояла из двух полей, hash: u32 и index: u32 (позже index сократили до u16), но из-за правил выравнивания Rust (размер структуры в памяти обязан быть кратен размеру её самого большого поля) простое уменьшение поля index память не экономило, минимальный размер структуры всё равно оставался восемь байт. Вместо небезопасного атрибута #[repr(packed)] (в тексте он назван спорным решением) команда хранит хеш и индекс как сырой массив из 6 байт (struct Point([u8; 6])) и достаёт значения через геттеры на from_ne_bytes. Это сократило память, которую consistent hashing занимает под сами точки, на 25%.

Второе улучшение, сокращение количества хешей на сервер. Для этого команда сначала вывела точную формулу дисперсии для схемы с несколькими хешами на сервер (для одного хеша формула была известна и раньше, но для нескольких большинство источников дают только приближение). Затем учли, что на практике хеши, не непрерывные, а 32-битные числа, а значит возможны коллизии, вероятность которых растёт с ростом числа хешей (эффект, знакомый по «парадоксу дней рождения»). Сравнив предсказанную по формуле ошибку с результатами симуляции, Cloudflare увидела, что для дата-центров с 2048 серверами ошибка от коллизий заметно растёт в диапазоне от 10 000 до 100 000 хешей на сервер. Опираясь на эти расчёты, команда определила, что может сократить число генерируемых хешей на сервер на 90% без заметного роста ошибки распределения нагрузки, и реализовала это сокращение.

В сумме два изменения (переупаковка структуры Point и сокращение числа хешей на сервер) позволили высвободить более 100 ТБ RAM по всей инфраструктуре Cloudflare, сверх отдельных 100 ТБ, которые команда DNS сэкономила месяцем ранее независимо от этой работы. Как именно новая, уменьшенная схема хешей раскатывалась на продакшене без потери балансировки нагрузки, в доступном фрагменте текста не описано, изложение обрывается на середине соответствующего раздела.

Ключевые факты

Тикет инженера Ивана вскрыл, что библиотека pingora-ketama для consistent hashing потребляет в балансировщике Pingora Backend Router больше памяти, чем ожидалось.
Инженер Зайдун предложил хранить хеш и индекс сервера как сырой массив из 6 байт вместо двух отдельных полей (u32 + u16), обойдя правила выравнивания Rust, которые держали структуру на минимум 8 байтах, это сократило память под consistent hashing на 25%.
Расчёт коэффициента вариации и анализ вероятности коллизий 32-битных хешей (по аналогии с парадоксом дней рождения) показали, что для дата-центров с 2048 серверами ошибка заметно растёт в диапазоне 10 000, 100 000 хешей на сервер, это позволило безопасно сократить число хешей на сервер на 90%.
На примере в 100 серверов: при одном хеше на сервер погрешность распределения нагрузки (коэффициент вариации) около 99%, а при стандартных для NGINX и Pingora 160 хешах на сервер падает примерно до 8%.
В сумме изменения высвободили более 100 ТБ RAM по всей инфраструктуре Cloudflare, сверх отдельных 100 ТБ, которые команда DNS сэкономила месяцем раньше.

Почему это важно

Cloudflare управляет тысячами серверов с петабайтами RAM, и на таком масштабе даже улучшение на доли процента на один сервис даёт десятки и сотни терабайт экономии, здесь два относительно небольших изменения (переупаковка одной структуры данных и пересчёт числа хешей) в сумме дали больше 100 ТБ. Кейс показывает и более общий принцип: вместо того чтобы менять параметр производительности на глаз, команда сначала вывела точную математическую модель погрешности и уже по ней приняла решение, на сколько можно безопасно сократить нагрузку на память.

Кому это важно

Инженерам, которые работают с consistent hashing, балансировкой нагрузки и распределёнными системами на большом числе серверов; Rust-разработчикам, которые сталкиваются с непрозрачным ростом памяти из-за правил выравнивания структур; тем, кто принимает решения об оптимизации инфраструктуры и хочет опираться на расчёт, а не на интуицию.

Как это применить

Два переносимых приёма из текста. Первый, для экономии памяти в Rust-структурах: если правила выравнивания раздувают размер структуры (как в случае hash: u32 + index: u32/u16), вместо небезопасного #[repr(packed)] можно хранить поля как сырой массив байт и доставать значения через геттеры на from_ne_bytes, это дало 25% экономии без unsafe-кода. Второй, прежде чем менять числовой параметр системы (в данном случае число хешей на сервер) по интуиции, стоит явно посчитать: вывести формулу погрешности (коэффициента вариации) для нужной схемы, оценить риск коллизий для конкретного размера кластера и только затем определить безопасный диапазон изменения параметра.

Можно ли доверять

Источник, официальный инженерный блог Cloudflare, написанный от первого лица инженером, участвовавшим в работе; в тексте приведены конкретные имена причастных (Иван, тикет, Зайдун, идея по структуре), код структур на Rust, формулы и числовые примеры (100 и 2048 серверов, 8 и 6 байт, 99% и 8% коэффициента вариации), что делает изложение проверяемым. Полный математический вывод формул компания вынесла в отдельный дополнительный пост, на который ссылается основной текст.

Риски и подводные камни

Доступный фрагмент текста обрывается на середине раздела о раскатке изменений в продакшен («There was one more pr…»), как именно сокращение числа хешей на 90% выкатывали и проверяли на реальных серверах без потери баланса нагрузки, в нём не описано. Не указано, как более 100 ТБ суммарной экономии распределяются между двумя изменениями по отдельности (25%-ное сокращение памяти под структуру Point и отдельное 90%-ное сокращение числа хешей на сервер, это две независимые, не просуммированные в тексте величины). Ни для одной из двух оптимизаций PBR не названа календарная дата, только «в прошлом месяце» для отдельной, не связанной с этой работой экономии DNS-команды. Сама природа решения, компромисс, а не бесплатное улучшение: меньше хешей на сервер означает более грубое распределение нагрузки, и 90%-ное сокращение безопасно только потому, что заранее посчитан допустимый для конкретного масштаба (2048 серверов, 32-битные хеши) диапазон, механическое повторение этой цифры для кластера другого размера было бы ошибкой.

«Я не статистик, но вырос с мамой, учителем математики, и хотел знать точное значение.»

— автор поста в инженерном блоге Cloudflare