Saving another 100TB of RAM

Cloudflare сократил потребление памяти в сервисе Pingora Backend Router на более чем 100 ТБ за счёт оптимизации алгоритма consistent hashing в библиотеке pingora-ketama. Проблема заключалась в том, что для каждого узла хранились полные копии хеш-кольца — структуры данных, используемой для распределения запросов между серверами. При росте числа узлов это приводило к квадратичному росту памяти: каждый новый узел дублировал всё кольцо, что при тысячах серверов и петабайтах RAM становилось неприемлемо дорогим.

Оптимизация заключалась в переходе от полного дублирования кольца к компактному представлению: вместо хранения всех хешей каждого узла, теперь хранится только базовое множество хешей на узел, а при поиске используется эффективный алгоритм сортировки и бинарного поиска по сжатому пространству. Это позволило уменьшить память на узел с O(N) до O(1) относительно числа узлов, сохранив при этом свойства consistent hashing — минимальную переназначенность при добавлении/удалении узлов и равномерное распределение нагрузки. Изменения были внесены как обратно совместимая функция v2 в pingora-ketama, позволяющая逐步 мигрировать без простоев. После полного перехода на новую версию наблюдался резкий спад потребления памяти — подтверждённый метриками — что эквивалентно экономии более 100 ТБ RAM по всему глобальному флоту Cloudflare. Это демонстрирует, как математическая прозорливость и аккуратная реализация в Rust могут превратить, казалось бы, незначительные алгоритмические улучшения в масштабную экономию ресурсов.

Комментарии (110)

Оптимизация Cloudflare имеет смысл только на масштабе их инфраструктуры. Для обычных систем экономия 1% памяти не оправдывает сложность реализации. Спор: Некоторые считают, что оптимизация на 100 ТБ оправдана только из-за масштаба Cloudflare, а для большинства систем это не стоит усилий. Спор: Один участник предлагает заменить consistent hashing на tournament hashing с N битами ключа и wyhash — это сократит использование памяти на 600 ТБ и снизит задержку за счёт O(n) вместо O(n log n). Совет: Использовать B-дерево с суммированием весов узлов и бинарным поиском по хешу, масштабированному на общий вес — это снизит затраты на обновление дерева до ~8 узлов при добавлении/удалении сервера. Совет: Применить сжатие указателей в Rust — удаление по 2 байта с каждого указателя сэкономит сотни гигабайт при большом числе записей. Многие отмечают, что Cloudflare вернулся к качественному, человечески написанному контенту, в отличие от предыдущих постов, написанных ИИ — это воспринимается как позитивный сдвиг. Пользователи подтверждают, что оптимизации хеш-колец и хранения данных важны для крупных систем, где небольшие улучшения приводят к значительной экономии ресурсов. Совет: При небольшом масштабе профилирование и устранение избыточных байтов на запись эффективнее сложных алгоритмических оптимизаций, не протестированных на реальных данных. Спор: Некоторые критикуют статью за преувеличение технической глубины — математика в ней не революционна, а базова для команд, работающих с оптимизацией на уровне дата-центров. Совет: Использовать rendezvous hashing — алгоритм для балансировки нагрузки в прокси-кэшах, который может заменить ketama и сократить память без потери равномерности распределения. Пользователи отмечают, что эпоха изобилия памяти закончилась — рост стоимости RAM и масштаб инфраструктуры заставляют компании возвращаться к глубокой оптимизации, как в прошлом. Спор: Один участник утверждает, что экономия памяти ради снижения затрат не этична, если это приводит к росту цен на оборудование для малого бизнеса и рабочего класса. Совет: В Rust можно использовать структуры с layout-оптимизацией и struct-of-arrays для улучшения кэш-локальности при поиске в хеш-кольце — это снижает задержки без увеличения памяти.