Почему BPF LPM trie замедляется с ростом таблицы префиксов

Обстоятельный разбор сбоя Cloudflare в продакшене начинается с блокировки процессора: освобождение BPF-карты с миллионами записей заняло более 10 секунд. Автор объясняет устройство trie, поиск самого длинного префикса и ограничения реализации в ядре Linux.

Узлы лишь с двумя потомками заставляют плотную карту проходить цепочку однобитовых сравнений; сжатия уровней нет. Разрозненные адреса узлов дают промахи кэша L1, а примерно с 80 000 записей узким местом становятся промахи dTLB при преобразовании адресов. При миллионе записей скорость поиска падает примерно до 1,5 млн операций в секунду.

Читать стоит разработчикам сетевых сервисов и тем, кто эксплуатирует BPF-карты. Прогоните поиск и освобождение карты на своей плотности ключей и объёме данных: распределение префиксов определяет эффективность сжатия путей.