Ситуация: сервер держит 100 000 RPS, а на дашборде нужен p99 — задержка, выше которой только 1% самых медленных запросов. Хранить все значения не выйдет: за час набегает 360 млн чисел, а за сутки 8,6 млрд. Сортировать такое на каждый запрос дашборда долго и дорого.
Тут пригодится T-Digest. Он не хранит числа, а группирует их в кластеры-центроиды: маленькие и точные на хвостах, крупные и приблизительные в центре. Вместо всех 100 000 значений остается около 100 центроидов.
Как это работает и почему ошибка p99 держится в пределах 0,01–0,08% → разобрали в статье.
А вы внедряли когда-нибудь алгоритм из статьи в свой проект?
👀 — приходилось
😎 — не работаю с высоконагруженными системами