p99 0 мс на автодополнение 240 миллионов доменов

Автор поставил себе дерзкую цель: показывать подсказки раньше, чем пользователь успеет отпустить клавишу. Задержку он меряет от момента keyUp до готового результата и закладывает бюджет p99 в 121 мс на два нажатия с паузой между ними. Чтобы в него уложиться, выдача должна быть готова почти мгновенно.

Архитектура делится на две части по распределению запросов:
🔘голова, миллион самых частых доменов из списка Tranco, лежит в памяти как символьный trie с заранее посчитанным топ-8 для каждого префикса;
🔘хвост, все 240 миллионов доменов из CZDS, лежит на SSD как memory-mapped блочный индекс с дельта-сжатием: 27 МБ оглавления в памяти и 2,5 ГБ на диске;
🔘большинство запросов к API отвечают за 2 мс, на нагрузке 1600 запросов в секунду p99 связки nginx и API держится около 15 мс;
🔘оставшаяся задержка упирается в сетевой путь через Cloudflare, поэтому для дальних регионов нужна геобалансировка.

По дороге видно, как требование «мгновенно» раскладывается на конкретные структуры данных и бюджеты по миллисекундам.

Сохранять тем, кто проектирует поиск и автодополнение под нагрузкой и любит, когда задержку считают по слоям.

Полная статья: https://ruurtjan.com/articles/p99-0ms-autocomplete-for-240-million-domain-names

@prog_stuff