Квантили потока: что это такое и что даёт случайная выборка

Если ты дашь определение квантиля и ошибки по рангу, посчитаешь размер выборки для заданной точности и объяснишь, почему перцентили нельзя усреднять, - листай до «Теперь сам».

Как думаешь, что сказать о времени ответа

Сервис обрабатывает запросы; большинство быстрые, немногие очень медленные. Среднее время ответа - 76 мс.

Ответь себе до чтения: значит ли это, что типичный запрос длится около 76 мс? В данных, на которых получено это число, половина запросов быстрее 38 мс, а каждый сотый медленнее 643 мс. Среднее вдвое больше того, что видит типичный пользователь, и в восемь раз меньше того, что видит невезучий. Время ответа описывают не средним, а квантилями, и считать их в потоке труднее.

На что это похоже

Очередь по росту. Медиана - рост человека, стоящего ровно посередине. 99-й перцентиль - рост того, кто стоит на расстоянии одной сотой от высокого конца. Чтобы назвать их, не нужно знать ничей рост в отдельности - нужно знать, кто на каком месте стоит.

В этом и трудность: место определяется всеми остальными. Средний рост можно накапливать по одному человеку. А кто окажется посередине, неизвестно, пока не пришли все, - и любой уже пришедший может им оказаться.

Механизм: ранг, допуск по рангу и выборка

Ранг значения в наборе - число элементов, меньших его; если значения повторяются, равные элементы занимают соседние места, и рангом считается любое из них. Квантиль порядка φ - значение с рангом φ · n: если данные отсортировать, это элемент на месте φ · n. Перцентиль - квантиль, порядок которого записан в процентах: p99 - это φ = 0,99.

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

Ошибка по рангу ε: ответом на запрос квантиля φ годится любое значение, ранг которого лежит между (φ − ε) · n и (φ + ε) · n. При ε = 0,01 вместо медианы разрешено вернуть что угодно между 49-м и 51-м перцентилями.

Почему случайная выборка годится. Возьмём любое значение x; пусть ниже него лежит доля F всех данных. Каждый элемент выборки оказывается ниже x с вероятностью F - это индикатор. Доля таких элементов в выборке - среднее s индикаторов, и по границе Хёфдинга она отличается от F больше чем на ε с вероятностью не больше 2e^(−2sε²). Для всех значений сразу, а не для одного заранее выбранного, верна оценка того же вида - это отдельная теорема, здесь без доказательства. Значит, ранги в выборке, поделённые на её размер, повторяют ранги в данных с точностью ε, и квантиль выборки - квантиль данных с ошибкой по рангу не больше ε:

s = ln(2/δ) / (2ε²)        ε = 0,05 → 738      ε = 0,01 → 18 445      ε = 0,001 → 1 844 440

Числа посчитаны для δ = 0,05 и те же, что в расчёте размера опроса: это одна и та же задача. Размер выборки не зависит от длины потока, но растёт как 1/ε²: за один процент точности по рангу - восемнадцать тысяч хранимых элементов.

Саму выборку из потока даёт резервуар.

Правило

Квантиль порядка φ - элемент на месте φ · n в отсортированных данных. Приближённый ответ с ошибкой по рангу ε - любое значение с рангом от (φ − ε) · n до (φ + ε) · n. Квантиль случайной выборки размера s имеет ошибку по рангу не больше ε с вероятностью не меньше 1 − δ при s ≥ ln(2/δ) / (2ε²). Ошибка по рангу ничего не обещает об ошибке по значению. Квантили частей данных не усредняются.

Разбор: выборка в четыреста из восьми тысяч

Поток - восемь тысяч «времён ответа» с длинным хвостом: большинство значений от 20 до 60, редкие доходят до тысячи. Резервуар на 400 элементов. Ради сверки все значения сохраняются и сортируются. Для каждого из трёх квантилей печатаются: точное значение, оценка по выборке и истинный ранг этой оценки, делённый на n.

import random

random.seed(63)
n = 8000
k = 400
vse = []
vyborka = []
for i in range(n):
    x = int(20 / (random.random() + 0.02))
    vse.append(x)
    if i < k:
        vyborka.append(x)
    else:
        j = random.randrange(i + 1)
        if j < k:
            vyborka[j] = x

vse = sorted(vse)
vyborka = sorted(vyborka)
for dolya in [0.5, 0.9, 0.99]:
    tochno = vse[int(dolya * n)]
    ocenka = vyborka[int(dolya * k)]
    rang = 0
    while rang < n and vse[rang] < ocenka:
        rang = rang + 1
    print(dolya, tochno, ocenka, round(rang / n, 3))
print(vse[int(0.98 * n)], vse[int(0.999 * n)], vse[n - 1], vyborka[k - 1], round(sum(vse) / n, 1))

0.5 38 38 0.489
0.9 160 181 0.913
0.99 643 693 0.991
482 963 997 954 76.4

Медиана: точно 38, по выборке 38. 90-й перцентиль: 160 против 181; значение 181 стоит на месте 0,913 - ошибка по рангу 0,013. 99-й: 643 против 693, место 0,991.

Формула для выборки в 400 элементов при δ = 0,05 обещает ошибку по рангу не больше √(ln 40 / 800) = 0,068. Все три ошибки - около одной сотой и меньше: гарантия выполнена с большим запасом. Последнее число последней строки - среднее, 76,4: вдвое больше медианы.

Разбор: хвост, где ранг и значение расходятся

Посмотри на 90-й перцентиль ещё раз. Ошибка по рангу - 1,3%, а значения 160 и 181 различаются на 13%. В хвосте распределения соседние места занимают далёкие значения, и малая ошибка по рангу превращается в большую по значению.

Дальше в хвост - хуже. Вторая строка вывода - значения на местах 0,98 и 0,999, наибольшее в потоке и наибольшее в выборке: 482, 963, 997 и 954. Пусть нужен 99-й перцентиль с гарантией ε = 0,01. Гарантия разрешает ответ между местами 0,98 и 1,0, то есть любое значение от 482 до 997. Честно выполненная гарантия по рангу здесь означает «где-то между пятьюстами и тысячей».

99,9-й перцентиль по этой выборке получить нельзя вовсе. Выше него лежит одна тысячная данных; в выборке из четырёхсот элементов таких в среднем 0,4, то есть обычно ни одного. Всё, что выборка может ответить, - свой наибольший элемент, 954, и к искомому 963 он близок по случайности. Чтобы квантиль порядка φ оценивался выборкой осмысленно, выше него должно лежать хотя бы несколько десятков элементов выборки: размер нужен много больше 1 / (1 − φ).

Вторая граница - объединение. Два сервера обработали по сто запросов. У первого все запросы по 10 мс; у второго 99 запросов по 10 мс и один в 1000 мс. 99-й перцентиль первого - 10 мс, второго - 1000 мс. А у всех двухсот запросов вместе на месте 0,99 · 200 = 198 стоит запрос в 10 мс. Среднее двух перцентилей - 505 мс, наибольший - 1000 мс, правильный ответ - 10 мс. По квантилям частей квантиль целого не восстановить ни одной формулой; объединять нужно сводки, из которых квантили считаются.

Что ломается без этого

Среднее время вместо перцентилей. Сервис со средним 76 мс и 99-м перцентилем 643 мс и сервис, у которого все запросы длятся 76 мс, - разные сервисы с одинаковым средним.

Усреднение перцентилей по серверам. График «средний p99 по кластеру» показывает число, которое не является перцентилем ничего. На панели должен быть перцентиль, посчитанный из объединённой сводки.

Дальний перцентиль по малой выборке. p99,9 по тысяче наблюдений - это одно наибольшее значение. Запас должен быть в десятки раз.

Обещание точности по значению. Сводка с гарантией ε = 1% по рангу может ошибаться в хвосте вдвое по значению и при этом работать правильно.

Зачем это в работе

Целевые показатели сервиса формулируют в перцентилях: «99% запросов быстрее 300 мс». Чтобы проверять такое условие, система мониторинга должна уметь оценивать перцентили по потоку на каждом сервере и объединять оценки.

Планировщик запросов в базе данных хранит для столбца границы, делящие значения на равные по числу строк доли, - это квантили. PostgreSQL строит их командой ANALYZE по случайной выборке строк, по умолчанию около тридцати тысяч, и по ним оценивает, какую часть таблицы отберёт условие цена < 100.

Распределённая сортировка. Чтобы разложить данные по ста узлам на диапазоны равного размера, нужны 99 границ - квантили с шагом в один процент. Их находят по выборке, и ошибка по рангу прямо переводится в неравномерность загрузки узлов.

Теперь сам

1. Отсортированные данные: 3, 5, 8, 9, 12, 15, 20, 22, 30, 41. Найди квантили порядка 0,5 и 0,9 как элементы на местах φ · n, считая с нуля.
2. Какой размер выборки нужен для ошибки по рангу 0,02 при δ = 0,05? ln 40 ≈ 3,69.
3. В потоке миллион элементов, сводка гарантирует ε = 0,01. На сколько мест может отстоять ответ от настоящей медианы?
4. По выборке из 500 элементов хотят оценить 99,9-й перцентиль. Сколько элементов выборки в среднем лежит выше него и что из этого следует?
5. У сервера A 99-й перцентиль равен 50 мс, у сервера B - 400 мс. Можно ли по этим двум числам сказать, каков 99-й перцентиль всех запросов?