Как оценить медианное время ответа сервиса при большом объеме логов, не помещающихся в память

Что проверяют

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

Как отвечать

Сначала уточните требования: нужна точная медиана или приближённая, разово или постоянно, на одной машине или по кластеру. От этого зависит выбор:

• гистограмма в один проход: время ответа ограничено сверху, например таймаутом в 30 секунд. Заводим массив счётчиков по миллисекундам на 30 000 ячеек, читаем логи потоком и находим ячейку, где накопленная сумма перевалила за половину. Память не зависит от объёма логов, точность равна ширине корзины;
• два прохода: если диапазон неизвестен, первый проход строит грубую гистограмму, второй уточняет только ту корзину, где лежит медиана;
• скетчи: t-digest, KLL, HdrHistogram хранят сжатое распределение с контролируемой ошибкой и, главное, сливаются. Скетчи с разных серверов или за разные дни объединяются, а медианы нет;
• выборка: reservoir sampling даёт равномерную выборку из потока. Ошибка по рангу порядка sqrt(p(1-p)/n), для медианы и 10 000 элементов это около половины процента;
• внешняя сортировка: точный, но самый дорогой вариант, O(n log n) с чтением и записью на диск.

На практике это готовые функции: percentile_approx в Spark, quantileTDigest и quantileExact в ClickHouse, histogram_quantile в Prometheus поверх бакетов гистограммы.

Где спотыкаются

Предлагают две кучи, max-heap и min-heap. Это классика для медианы потока, но кучи хранят все элементы, то есть память снова O(n), и условие задачи нарушено. То же с QuickSelect: ему нужен весь массив сразу.

Усредняют медианы по часам или по файлам. Среднее медиан не равно медиане целого, особенно когда нагрузка по часам неравномерна.

Называют Kafka или Flink как решение. Это транспорт и движок обработки, они не отвечают на вопрос, какой алгоритм считает квантиль внутри.