03.08.2026 08:05
DrArgentum 1 5200 Источник

Представим, что вы имеете сервер, который обрабатывает и анализирует 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 $. Самая простая версия из статьи:

k_0(q) = \frac{\delta}{2} \cdot q

Это линейная шкала. Она даёт равномерные кластеры — как обычная гистограмма. Интерес начинается с другой функции:

k_1(q) = \frac{\delta}{2\pi} \cdot \arcsin(2q - 1)

При $ q = 0.5 $ (медиана) арксинус от нуля даёт ноль. При $ q = 0 $ — -\delta/4. При $ q = 1 $ — \delta/4. График этой функции показывает, почему алгоритм работает: если провести горизонтальные линии на равном расстоянии по оси $ k $, то на краях (где $ q $ близко к 0 или 1) вертикальные проекции на ось $ q $ будут гуще. Это и есть кластеры.

Теперь — главное. Для каждого центроида мы знаем его левый и правый квантильные ранги. Пусть у нас есть центроид с весом w, а суммарный вес всех центроидов слева от него равна W_{\text{left}}. Общее количество точек — n. Тогда:

q_{\text{left}} = \frac{W_{\text{left}}}{n}q_{\text{right}} = \frac{W_{\text{left}} + w}{n}

А центр центроида (его медиана) находится в точке:

q_{\text{center}} = \frac{W_{\text{left}} + w/2}{n}

Ограничение размера центроида формулируется через scale function:

k_1(q_{\text{right}}) - k_1(q_{\text{left}}) \leq 1

То есть «размер» центроида в шкале $ k $ не должен превышать 1. Для линейной шкалы $ k_0 $ это ограничение можно переписать в виде:

\text{weight} \leq \frac{4\delta}{q(1-q)}

Для шкалы с арксинусом $ k_1 $ ограничение другое, но идея остаётся той же: на хвостах допустимый вес центроида меньше, чем в центре.

Посмотрим на знаменатель: q(1-q). На краях, где q = 0.01, знаменатель равен 0.0099, и допустимый вес получается очень маленьким — около 400\delta. А вот в центре, где q = 0.5, знаменатель максимален (0.25), и вес ограничен 16\delta. В итоге мы получаем асимметричное сжатие: на краях — высокая точность за счёт маленьких кластеров, в центре — низкая точность за счёт больших.

Параметр $ \delta $ (дельта) управляет основными формулами создания центроидов. Чем больше $ \delta $, тем больше допустимый вес и тем больше центроидов мы можем создать. При $ \delta = 100 $ число центроидов будет около 50–100. При $ \delta = 1000 $ — около 500–1000. Память растёт линейно с $ \delta $, точность — примерно как $ 1/\sqrt{\delta} $.

На практике T-Digest работает не с отсортированными данными, а в потоке. Для этого используется буферизация:

  1. Новые точки складываются в буфер.

  2. Когда буфер переполняется (или по запросу), все центроиды (старые + новые из буфера) сортируются по среднему значению.

  3. Делается жадный проход слева направо: склеиваем центроиды, пока не превысим лимит веса, затем начинаем новый.

Этот алгоритм называется 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.

❯ Источники:

Новости, обзоры продуктов и конкурсы от команды Timeweb.Cloud — в нашем Telegram-канале ↩

Комментарии (1)


  1. zzzzzzerg
    03.08.2026 09:35
    #30292198

    На моих данных из gcmon T-Digest работал не правильно, а вот DDSketch от DataDog работал и работает отлично. А вот тут отличная статья от них Computing accurate percentiles with DDSketch