Представим, что вы имеете сервер, который обрабатывает и анализирует 100.000 RPS. Вам нужно высчитать и показать на дашборде 99-й перцентиль задержки — значение, выше которого только 1% самых медленных запросов. Если вы сохраните все 100 000 чисел за секунду, через час это 360 миллионов чисел. Через день — 8.6 миллиардов. Каждый раз хранить, сортировать и высчитывать? Нереально долго и ресурсозатратно.
Но для этой задачи существует алгоритм T-Digest. Вместо того, чтобы хранить все числа, он группирует их в кластеры — центроиды. А все дело в том, что кластеры на краях распределения (там, где наши хвосты) он делает маленькими и точными, а в центре — большими и «приблизительными». В результате для 100 000 точек нам нужно всего ~100 центроидов вместо 100 000 чисел. Это в сотни раз меньше памяти. И притом что ошибка при вычислении 95-го перцентиля в среднем составляет всего 0.001–0.06% (в зависимости от параметра сжатия).
В этой статье я разберу математику алгоритма, почему алгоритм такой быстрый и малозатратный, разберём графики и бенчмарки, а также покажу реализацию алгоритма на C.
Перед началом хочется поведать, что за квантили, перцентили, какие есть наивные способы решения подсчёта.
q-квантиль — значение, ниже которого лежит q-доля данных. Медиана — это 0.5-квантиль. 95-й перцентиль — 0.95-квантиль. 99-й — 0.99-квантиль. В мониторинге важны именно хвосты: p99 показывает, что происходит с 1% самых медленных запросов. Если p99 растёт — у вас проблема, даже если медиана в норме.
Как посчитать квантиль? Самый простой способ: сохранить все числа, отсортировать, взять элемент под индексом q×N. Работает, конечно, без проблем, но память в итоге O(N), и при 100k RPS за час набегает 360 млн чисел. А время исполнения целых O(N log N) на сортировку.
Можно сэмплировать — брать каждое сотое значение. Памяти меньше, но выбросы (те самые редкие 1%) с высокой вероятностью не попадут в выборку, а выбросы — это как раз то, что мы ищем.
Можно построить равномерную гистограмму: разбить числовую ось на равные интервалы, считать попадания. Но если данные скошены (а в реальности они почти всегда скошены), интервалы в хвостах либо пустые, либо огромные, и в итоге точность падает.
А T-Digest решает эту проблему — он не хранит все данные, не теряет выбросы и даёт высокую точность в хвостах.
❯ Суть T-Digest
T-Digest был создан Тедом Дантингом в начале 2010-х годов, а в 2019 году совместно с Отмаром Эртлом вышла улучшенная версия алгоритма. До них были Q-Digest, GK01, но они давали постоянную абсолютную ошибку для всех квантилей. Даже если ошибка «всего» 1% — для медианы это ±1%, и для 99-го перцентиля тоже ±1%. Но в реальности нам важнее точность именно на хвостах, где 1% скорее всего будет невероятно критичным.
Дантинг и Эртл пошли с другой стороны. Они решили, что ошибка должна зависеть от позиции: чем ближе к краям, тем точнее. Медиану можно посчитать с ошибкой 5%, а p99 — с ошибкой 0.1%.
Сам концепт не такой уж и сложный: группируем числа в кластеры — центроиды. Каждый центроид хранит среднее (mean) и вес (weight) — сколько чисел в него попало.
Но как группировать? Если делать равномерные кластеры по числовой оси — получим гистограмму.
В итоге T-Digest группирует не по значению, а по позиции в отсортированном порядке. И размер кластера зависит от того, где он находится: на краях кластеры маленькие, в центре — большие. Кластеры формируются жадным проходом слева направо, пока не превышен лимит веса. Для краёв допустимый вес маленький, поэтому там кластеры получаются точными. Для центра допустимый вес большой, поэтому там кластеры жирные и неточные.
То есть, вместо того чтобы хранить отдельные числа, T-Digest группирует их в кластеры — центроиды. Это структура из двух полей: среднее (mean) как центр масс кластера, и вес (weight) — сколько оригинальных чисел в этом кластере.
p99 вычисляется по маленькому кластеру на краю, p50 — по большому кластеру в центре.
Кстати, сам алгоритм T-Digest не детерминирован: при разном порядке поступления данных результат может отличаться. Можно сделать его детерминированным, но это может убить адаптивность и скорость.
Дальше мы разберём математику: как именно вычисляется допустимый размер кластера, что такое scale function и как параметр дельта управляет точностью.
Математика T-Digest: scale function, size bound и слияние
Когда я только начал разбираться с T-Digest, меня интересовало то, как именно алгоритм решает, сколько чисел можно запихнуть в один центроид, как высчитываются маленькие центроиды для хвостов и большие для середины.
Вместо того чтобы делить числовую ось на равные интервалы, T-Digest использует scale function — функцию, которая переводит квантиль $ q $ в некоторый индекс $ k $. Самая простая версия из статьи:
Это линейная шкала. Она даёт равномерные кластеры — как обычная гистограмма. Интерес начинается с другой функции:
При $ q = 0.5 $ (медиана) арксинус от нуля даёт ноль. При $ q = 0 $ — 
. При $ q = 1 $ — 
. График этой функции показывает, почему алгоритм работает: если провести горизонтальные линии на равном расстоянии по оси $ k $, то на краях (где $ q $ близко к 0 или 1) вертикальные проекции на ось $ q $ будут гуще. Это и есть кластеры.
Теперь — главное. Для каждого центроида мы знаем его левый и правый квантильные ранги. Пусть у нас есть центроид с весом 
, а суммарный вес всех центроидов слева от него равна 
. Общее количество точек — 
. Тогда:
А центр центроида (его медиана) находится в точке:
Ограничение размера центроида формулируется через scale function:
То есть «размер» центроида в шкале $ k $ не должен превышать 1. Для линейной шкалы $ k_0 $ это ограничение можно переписать в виде:
Для шкалы с арксинусом $ k_1 $ ограничение другое, но идея остаётся той же: на хвостах допустимый вес центроида меньше, чем в центре.
Посмотрим на знаменатель: 
. На краях, где 
, знаменатель равен 
, и допустимый вес получается очень маленьким — около 
. А вот в центре, где 
, знаменатель максимален (
), и вес ограничен 
. В итоге мы получаем асимметричное сжатие: на краях — высокая точность за счёт маленьких кластеров, в центре — низкая точность за счёт больших.
Параметр $ \delta $ (дельта) управляет основными формулами создания центроидов. Чем больше $ \delta $, тем больше допустимый вес и тем больше центроидов мы можем создать. При $ \delta = 100 $ число центроидов будет около 50–100. При $ \delta = 1000 $ — около 500–1000. Память растёт линейно с $ \delta $, точность — примерно как $ 1/\sqrt{\delta} $.
На практике T-Digest работает не с отсортированными данными, а в потоке. Для этого используется буферизация:
Новые точки складываются в буфер.
Когда буфер переполняется (или по запросу), все центроиды (старые + новые из буфера) сортируются по среднему значению.
Делается жадный проход слева направо: склеиваем центроиды, пока не превысим лимит веса, затем начинаем новый.
Этот алгоритм называется buffer-and-merge. Его сложность — $ O(n \log n) $ на один мёрж, но мержи происходят редко (каждые $ \delta $ точек). Амортизированно — очень быстро.
Важно понимать: T-Digest не даёт строгих математических гарантий ошибки. Как написано в документации Apache Datasketches (мы разберем анализ оттуда ниже), алгоритм эмпирический, и его точность зависит от входных данных. На практике для большинства распределений он работает отлично, но для pathological cases (например, данные с очень резкими скачками) ошибка может быть выше.
Теперь, когда математика ясна, перейдём к реализации на C.
❯ Эмпирические особенности и смещения
В документации Apache Datasketches прямо говорят, что T-Digest — эмпирический алгоритм. У него нет строгого математического доказательства ошибки, и его поведение зависит от входных данных.
Измерения показывают систематическое смещение (bias):
T-Digest занижает низкие ранги (малые квантили);
T-Digest завышает высокие ранги (большие квантили).
Эффект усиливается с ростом объёма данных. Вот как выглядит ошибка ранга для разных размеров выборки (2×10¹⁰, 2×10¹⁵, 2×10²⁰, 2×10²⁵):
На графиках видно, что смещение растёт с увеличением количества точек, но в районе экстремальных квантилей (q ≈ 0 или q ≈ 1) ошибка всё равно остаётся малой.
Зависимость ошибки ранга от размера потока:
При малых объёмах данных (до 10⁴) ошибка может быть заметной, но после 10⁵ она стабилизируется и не растёт. Это объясняется тем, что алгоритму нужно «настроиться» — накопить достаточно центроидов.
Сравнение T-Digest с REQ-скетчем (другой структурой для квантилей из библиотеки Datasketches, ссылка):
REQ-скетч позволяет выбрать приоритет: точность на низких или высоких рангах (HRA — High Rank Accuracy). T-Digest даёт хорошую точность на обоих концах одновременно, но, увы, жертвует точностью в центре. На графиках видно, что T-Digest проигрывает REQ в точности для конкретного ранга, но выигрывает в универсальности и компактности.
Реализация на C
Я взял за основу реализацию ajwerner/tdigestc. Она написана на чистом C, не использует динамическую аллокацию внутри структур и поддерживает слияние двух гистограмм.
Исходный код моего репозитория доступен по этой ссылке, реализация доступна в файлах src/tdigest.c, src/tdigest.h и src/tests.c.
typedef struct node { double mean; double count; } node_t; struct td_histogram { double compression; int cap; int merged_nodes; int unmerged_nodes; double merged_count; double unmerged_count; node_t nodes[0]; };
У каждого центроида два поля: среднее значение (mean) и вес (count). Гистограмма хранит два массива центроидов в одном буфере: сначала «слитые» (merged_nodes), затем «буферные» (unmerged_nodes). Это позволяет добавлять точки без пересортировки всего массива. Поле nodes[0] — гибкий массив (flexible array member), память под него выделяется сразу в td_new.
❯ Основные функции
Создание и удаление:
td_histogram_t* td_new(double compression) { size_t memsize = td_required_buf_size(compression); return td_init(compression, memsize, (char*)(malloc(memsize))); }
Ёмкость вычисляется как 6 * compression + 10. Коэффициент 6 взят с запасом — экспериментально подтверждено, что число центроидов не превышает compression.
Добавление точки:
void td_add(td_histogram_t* h, double mean, double count) { if (should_merge(h)) { merge(h); } h->nodes[next_node(h)] = (node_t){.mean = mean, .count = count}; h->unmerged_nodes++; h->unmerged_count += count; }
Точка всегда попадает в буфер. Когда merged_nodes + unmerged_nodes == cap, вызывается merge().
Слияние (ядро алгоритма):
static void merge(td_histogram_t* h) { if (h->unmerged_nodes == 0) return; int N = h->merged_nodes + h->unmerged_nodes; qsort(h->nodes, N, sizeof(node_t), &compare_nodes); double total_count = h->merged_count + h->unmerged_count; double denom = 2 * M_PI * total_count * log(total_count); double normalizer = h->compression / denom; int cur = 0; double count_so_far = 0; for (int i = 1; i < N; i++) { double proposed_count = h->nodes[cur].count + h->nodes[i].count; double z = proposed_count * normalizer; double q0 = count_so_far / total_count; double q2 = (count_so_far + proposed_count) / total_count; bool should_add = (z <= (q0 * (1 - q0))) && (z <= (q2 * (1 - q2))); if (should_add) { h->nodes[cur].count += h->nodes[i].count; double delta = h->nodes[i].mean - h->nodes[cur].mean; double weighted_delta = (delta * h->nodes[i].count) / h->nodes[cur].count; h->nodes[cur].mean += weighted_delta; } else { count_so_far += h->nodes[cur].count; cur++; h->nodes[cur] = h->nodes[i]; } } h->merged_nodes = cur + 1; h->merged_count = total_count; h->unmerged_nodes = 0; h->unmerged_count = 0; }
Здесь видно что все центроиды (и старые, и новые из буфера) сортируются по mean. Затем вычисляется эвристический нормализатор (он используется в этой реализации, можно было бы использовать более сложный на основе арксинуса, но на практике в 99% случаев подходит и наш упрощенный вариант) normalizer = compression / (2π · total_count · log(total_count)). Затем для каждого центроида высчитывается z = proposed_count · normalizer, и если он не превышает q0(1-q0) и q2(1-q2), центроиды склеиваются. Ну и при склеивании вес суммируется, среднее пересчитывается как взвешенное.
В коде используется эмпирический нормализатор с log(total_count) вместо оригинальной scale function с арксинусом. Арксинус точнее на хвостах, но чуть медленнее и менее точен в остальном. Для практических задач упрощенной реализации хватит с головой.
Реализация с arcsin
Если вы хотите использовать ее, можете заменить функцию merge на эту:
static void merge(td_histogram_t* h) { if (h->unmerged_nodes == 0) { return; } int N = h->merged_nodes + h->unmerged_nodes; qsort((void*)(h->nodes), N, sizeof(node_t), &compare_nodes); double total_count = h->merged_count + h->unmerged_count; int cur = 0; double count_so_far = 0; for (int i = 1; i < N; i++) { double proposed_count = h->nodes[cur].count + h->nodes[i].count; double q_left = count_so_far / total_count; double q_right = (count_so_far + proposed_count) / total_count; double k_left = (h->compression / (2 * M_PI)) * asin(2 * q_left - 1); double k_right = (h->compression / (2 * M_PI)) * asin(2 * q_right - 1); bool should_add = (k_right - k_left) <= 1.0; if (should_add) { h->nodes[cur].count += h->nodes[i].count; double delta = h->nodes[i].mean - h->nodes[cur].mean; double weighted_delta = (delta * h->nodes[i].count) / h->nodes[cur].count; h->nodes[cur].mean += weighted_delta; } else { count_so_far += h->nodes[cur].count; cur++; h->nodes[cur] = h->nodes[i]; } } h->merged_nodes = cur + 1; h->merged_count = total_count; h->unmerged_nodes = 0; h->unmerged_count = 0; }
На моей машине результаты такие:
$ ./tdigest 200 123 100000 0.95 10 iteration,delta,n_points,quantile,exact_quantile,td_quantile,error_percent,n_centroids,add_time_ms 1,200,100000,0.950000,13.281110,13.280132,0.007366,117,20 2,200,100000,0.950000,13.267992,13.271599,0.027183,119,20 3,200,100000,0.950000,13.287434,13.288471,0.007805,117,19 4,200,100000,0.950000,13.301317,13.301405,0.000663,117,19 5,200,100000,0.950000,13.284268,13.286617,0.017681,118,19 6,200,100000,0.950000,13.275179,13.277275,0.015786,115,19 7,200,100000,0.950000,13.290458,13.288705,0.013186,116,19 8,200,100000,0.950000,13.255895,13.255401,0.003722,114,20 9,200,100000,0.950000,13.308071,13.309063,0.007458,116,19 10,200,100000,0.950000,13.280319,13.281976,0.012479,118,20 $ ./tdigest test it took 0.234611 or 0.000000 per 0.000000: 0.001071 0.010000: 0.996055 0.100000: 9.965649 0.200000: 19.985839 0.300000: 29.987103 0.400000: 40.024585 0.500000: 50.052244 0.600000: 60.061319 0.700000: 70.060907 0.800000: 80.029807 0.900000: 89.992459 0.990000: 99.001447 1.000000: 99.999165 Tests run: 5 ALL TESTS PASSED
В этой статье я взял упрощенную версию. Эталонная не сильно отличается, разница незначительна в практических задачах - arcsin версия показала немного лучшую точность на хвостах (0.011% vs 0.017%), но создает на ~15% больше центроидов и работает на ~8% медленнее. На хвостах arcsin-версия немного точнее, но для практических задач разница незначительна.
Вычисление квантиля:
double td_value_at(td_histogram_t* h, double q) { merge(h); double goal = q * h->merged_count; double k = 0; int i = 0; node_t* n = NULL; for (i = 0; i < h->merged_nodes; i++) { n = &h->nodes[i]; if (k + n->count > goal) break; k += n->count; } // интерполяция между соседними центроидами double delta_k = goal - k - (n->count / 2); if (is_very_small(delta_k)) return n->mean; // ... линейная интерполяция }
Сначала принудительный merge() — все буферные точки должны быть обработаны. Затем линейный проход для поиска нужного центроида. Если точка попадает ровно в середину центроида — возвращается его mean. Иначе — линейная интерполяция между соседними центроидами.
Количество центроидов:
int td_centroid_count(td_histogram_t* h) { merge(h); return h->merged_nodes; }
Функция, которую я добавил для бенчмарков. Принудительно сливает буфер и возвращает число центроидов.
Бенчмарки и графики
Я прогнал шесть серий тестов на своём рабочем ноутбуке (Ryzen 7 5825U, 16 ГБ ОЗУ). Для этого я написал обвязку main.c, которая выдаёт данные в CSV-формате. Она принимает аргументы: дельту, сид, количество точек, нужный квантиль, количество итераций.
Кстати, также если первый аргумент — test, то показываются результаты тестирования:
it took 0.214939 or 0.000000 per 0.000000: 0.000066 0.010000: 0.995485 0.100000: 9.993548 0.200000: 19.924544 0.300000: 29.907734 0.400000: 39.924446 0.500000: 49.945036 0.600000: 59.963827 0.700000: 69.994960 0.800000: 80.031804 0.900000: 89.987173 0.990000: 99.002407 1.000000: 99.999976 Tests run: 5 ALL TESTS PASSED
А вот пример получения данных по входным параметрам:
./tdigest 200 123 100000 0.95 10 iteration,delta,n_points,quantile,exact_quantile,td_quantile,error_percent,n_centroids,add_time_ms 1,200,100000,0.950000,13.281110,13.278724,0.017967,106,17 2,200,100000,0.950000,13.267992,13.268716,0.005454,103,17 3,200,100000,0.950000,13.287434,13.286071,0.010256,104,17 4,200,100000,0.950000,13.301317,13.301515,0.001489,102,18 5,200,100000,0.950000,13.284268,13.289138,0.036659,101,17 6,200,100000,0.950000,13.275179,13.277912,0.020580,102,17 7,200,100000,0.950000,13.290458,13.285319,0.038662,101,18 8,200,100000,0.950000,13.255895,13.258903,0.022696,104,17 9,200,100000,0.950000,13.308071,13.309755,0.012658,100,17 10,200,100000,0.950000,13.280319,13.276395,0.029541,101,18
Далее я написал Python-скрипт, который читает вывод и генерирует графики. Входные данные — нормальное распределение с μ=10, σ=2, ограниченное [0, 100]. Каждый тест повторялся несколько раз.
❯ 1. Зависимость ошибки от δ (compression factor)
Параметры: n_points=100000, quantile=0.99, δ ∈ [10, 20, 50, 100, 200, 500, 1000]
Результат: ошибка падает с ростом δ. При δ=10 ошибка ~0.8%, при δ=1000 — ~0.01%. Зависимость примерно логарифмическая.
❯ 2. Зависимость ошибки от размера выборки
Параметры: δ=100, quantile=0.99, n ∈ [1000, 5000, 10000, 50000, 100000, 500000, 1000000]
Результат: ошибка стабильна (~0.02–0.04%) на всём диапазоне. T-Digest одинаково хорошо работает и на 1000, и на 1 000 000 точек.
❯ 3. Зависимость времени от размера выборки
Параметры: δ=100, quantile=0.99, n ∈ [1000, 5000, 10000, 50000, 100000, 500000, 1000000]
Результат: время растёт почти линейно: 1000 точек — 2 мс, 100 000 — 16 мс, 1 000 000 — ~150 мс. На 100k точек укладывается в 8–18 мс.
❯ 4. Количество центроидов vs δ
Параметры: n_points=100000, δ ∈ [10, 20, 50, 100, 200, 500, 1000]
Результат: число центроидов примерно равно δ/2 при малых δ и δ при больших. Для δ=200 — ~100 центроидов.
❯ 5. Зависимость ошибки от квантиля
Параметры: δ=100, n_points=100000, q ∈ [0.5, 0.9, 0.95, 0.99, 0.999, 0.9999]
Результат: ошибка минимальна на хвостах (0.001% для p9999) и максимальна в центре (0.08% для медианы). Именно так и задумано.
❯ 6. Распределение ошибки (30 запусков)
Параметры: δ=100, n_points=100000, quantile=0.99, 30 повторений
Результат: средняя ошибка ~0.03%, стандартное отклонение ~0.005%. Алгоритм стабилен.
❯ Итоговые цифры
Метрика | Значение |
|---|---|
Ошибка p95 при δ=200 | 0.001–0.02% |
Ошибка p99 при δ=100 | 0.01–0.08% |
Время на 100k точек | 8–18 мс |
Число центроидов при δ=100 | ~50–80 |
Сравнение с точным вычислением показало, что T-Digest даёт результаты, неотличимые от полной сортировки для практических задач мониторинга, при этом использует в сотни раз меньше памяти.
Бенчмарки arcsin-версии
Графики бенчмарков arcsin-версии можете увидеть ниже:
Заключение
T-Digest — крайне интересный алгоритм, мне он сразу понравился за счет того, что его концепция понятна, а также есть реальная нужда, тот же подсчет квантилей. Кстати, если вам интересна тема разбора алгоритмов, вы можете почитать статью о фильтре Блума или статью об алгоритме HyperLogLog.
❯ Источники:
arxiv / Computing Extremely Accurate Quantiles Using t-Digests
sciencedirect / The t-digest: Efficient estimates of distributions
Новости, обзоры продуктов и конкурсы от команды Timeweb.Cloud — в нашем Telegram-канале ↩
