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

Не тратьте впустую Поддержание справедливого распределения ресурсов между командами — задача непростая, особенно в крупных организациях. Один из способов, с помощью которых Cloudflare обеспечивает баланс, — это неустанные усилия замечательной команды Performance. Эта история начинается с тикета, поданного Ivan, который обнаружил: Чрезмерное использование памяти 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. Это проблема, потому что доля запросов, обрабатываемых сервером, будет пропорциональна размеру его диапазона на числовой прямой. В идеале мы хотели бы гарантировать, что каждый сервер будет иметь одинаковый размер, но поскольку хеши по сути являются случайными числами, нам приходится...