Vercel ускорила глобальную маршрутизацию с помощью фильтров Блума: снижение TTFB на 10%

Фильтры Блума — это вероятностная структура данных, которая позволяет быстро проверять принадлежность элемента множеству с минимальным потреблением памяти. Vercel внедрила их в свой глобальный сервис маршрутизации, что привело к снижению времени до первого байта (TTFB) на 10% для процентилей 75 и выше, а также к уменьшению использования памяти на 15%. Это особенно заметно для сайтов с сотнями тысяч статических путей, таких как интернет-магазины или документационные порталы, которые ранее создавали узкие места в инфраструктуре.

Проблема заключалась в том, что при каждом запросе сервису маршрутизации приходилось проверять, существует ли запрошенный путь, путем парсинга больших JSON-файлов. Для сайтов с десятками тысяч путей это приводило к значительным задержкам, особенно когда такие сайты составляли небольшую долю, но создавали диспропорциональную нагрузку. Фильтры Блума позволили заменить медленный парсинг на почти мгновенную проверку, что улучшило показатели для всех пользователей платформы.

Как фильтры Блума решили проблему маршрутизации

Фильтр Блума работает следующим образом: он использует несколько хеш-функций для отображения элементов в битовый массив. При проверке наличия элемента вычисляются хеши, и если все соответствующие биты установлены в единицу, элемент считается возможным членом множества. Если хотя бы один бит равен нулю, элемент точно отсутствует. Это позволяет с высокой скоростью отвечать на вопрос «есть ли элемент?» с возможностью ложноположительных срабатываний, но без ложноотрицательных.

Vercel встроила фильтры Блума непосредственно в сервис глобальной маршрутизации, работающий на границе сети. Каждый сайт получил свой собственный фильтр, построенный на основе списка его статических путей. Когда поступает запрос, сервис сначала обращается к фильтру. Если фильтр сообщает, что путь не существует, запрос сразу направляется на ближайший сервер обработки, минуя полную проверку. Если фильтр указывает на возможное существование, выполняется полная проверка по JSON, но такие случаи редки. Это снизило нагрузку на центральный сервис маршрутизации и улучшило TTFB.

Какие метрики улучшились и насколько?

Согласно данным Vercel, внедрение фильтров Блума привело к снижению TTFB на 10% для процентилей 75 и выше, то есть для самых медленных запросов. Кроме того, использование памяти сократилось на 15%, что особенно важно для масштабирования инфраструктуры. Для сайта с 500 000 статических путей фильтр Блума занимает около 1 МБ, тогда как JSON-файл с теми же данными мог весить десятки мегабайт. Это позволило обслуживать больше запросов с меньшими ресурсами.

Технические детали реализации

Инженеры Vercel выбрали фильтры Блума из-за их эффективности по памяти и скорости. В отличие от хеш-таблиц или деревьев, фильтр Блума не хранит сами элементы, а только их хеши, что позволяет экономить память. Размер фильтра настраивается таким образом, чтобы вероятность ложноположительного срабатывания была минимальной — менее 1%. Это обеспечивает баланс между скоростью и точностью: в 99% случаев фильтр точно определяет отсутствие пути, а в 1% случаев требуется дополнительная проверка.

Фильтры были встроены непосредственно в сервис глобальной маршрутизации, который работает на границе сети Vercel. Каждый сайт получил свой собственный фильтр, построенный на основе списка его статических путей. Это позволило изолировать нагрузку: сайты с большим количеством путей не влияют на производительность других сайтов. Кроме того, фильтры обновляются динамически при добавлении или удалении путей, что обеспечивает актуальность данных.

Почему именно фильтры Блума, а не другие структуры данных?

Альтернативы, такие как хеш-таблицы или деревья поиска, требуют хранения самих элементов, что приводит к большему расходу памяти. Для сайтов с сотнями тысяч путей это было бы неэффективно. Фильтры Блума, напротив, используют фиксированный объем памяти независимо от количества элементов, что делает их идеальными для данной задачи. Кроме того, время проверки в фильтре Блума постоянно и не зависит от размера множества, в то время как в хеш-таблицах оно может расти при коллизиях.

Кого затронет это улучшение

Оптимизация в первую очередь выгодна владельцам сайтов с большим количеством статических страниц, таких как интернет-магазины, новостные порталы и платформы документации. Для них улучшение TTFB означает более быструю загрузку страниц для посетителей, что положительно сказывается на пользовательском опыте и SEO. Например, интернет-магазин с тысячами товарных страниц может заметить ускорение загрузки на 10% для самых медленных запросов, что напрямую влияет на конверсию.

Кроме того, все пользователи Vercel косвенно выиграли от снижения общей нагрузки на инфраструктуру маршрутизации. Уменьшение времени обработки запросов на границе сети позволило быстрее обслуживать трафик для всех сайтов, независимо от их размера. Это особенно важно в периоды пиковых нагрузок, когда каждый миллисекунда имеет значение.

Как это повлияет на разработчиков?

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

Что будет дальше

Vercel продолжает искать способы оптимизации своих сервисов. Фильтры Блума могут быть применены и в других компонентах платформы, например, для ускорения проверки прав доступа или кэширования. Компания также рассматривает возможность использования других вероятностных структур данных, таких как HyperLogLog для подсчёта уникальных элементов или MinHash для оценки схожести множеств. Это позволит еще больше повысить производительность и масштабируемость.

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

Итог

Внедрение фильтров Блума позволило Vercel решить проблему масштабирования сервиса глобальной маршрутизации, улучшив производительность для всех клиентов. Это пример того, как продуманное применение фундаментальных алгоритмов может дать ощутимый бизнес-результат без кардинальной смены архитектуры. Снижение TTFB на 10% и уменьшение использования памяти на 15% — это значимые улучшения, которые делают платформу еще более привлекательной для разработчиков и владельцев сайтов.