Сводки квантилей: уплотнение, Гринвальд-Ханна и что выбрать для хвоста

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

Как думаешь, можно ли выбросить половину данных и не потерять квантили

В буфере 32 отсортированных числа. Памяти мало, и половину надо выбросить - так, чтобы медиана, 90-й перцентиль и любой другой квантиль остались почти на месте.

Попробуй угадать до чтения, какую половину выбросить: случайные шестнадцать, меньшие, или через одно? Через одно. Если оставить каждое второе число и считать, что каждое оставшееся представляет двоих, то ниже любой отметки останется половина прежних чисел двойного веса - столько же, сколько было, с точностью до одного. Случайные шестнадцать сохранили бы квантили гораздо хуже.

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

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

Если так делать много раз и всегда выводить из строя вторых, строй будет понемногу съезжать в одну сторону - каждый раз чуть-чуть в пользу низких. Чтобы сдвиги не накапливались, перед каждым расчётом бросают монету: кому выходить, первым или вторым.

Механизм: буферы, веса и монетка

Уплотнение буфера. В буфере лежат элементы одного веса w - каждый представляет w элементов потока. Буфер сортируют и оставляют элементы на чётных либо на нечётных местах, по монетке. Оставшиеся получают вес 2w.

Что происходит с рангом. Пусть ниже некоторого значения x в буфере лежало r элементов. После уплотнения ниже x осталась половина из них, округлённая вверх или вниз, и каждый весит вдвое больше:

было:    r · w
стало:   (r/2, округлённое вверх или вниз) · 2w        отличается от прежнего не больше чем на w

При чётном r ошибки нет вовсе. При нечётном оценка ранга сдвигается на w - вверх или вниз в зависимости от монетки, с равной вероятностью. В среднем сдвиг нулевой.

Уровни. Сводка - список буферов. Буфер уровня 0 принимает элементы потока, у них вес 1. Когда буфер уровня u заполняется, он уплотняется, и оставшаяся половина переходит на уровень u + 1 с весом 2ᵘ⁺¹. Уровней получается около log₂(n / ёмкость).

Запрос. Собрать все хранимые элементы с их весами, отсортировать, идти по порядку, накапливая вес. Квантиль порядка φ - элемент, на котором накопленный вес впервые превысил долю φ от полного; для элементов единичного веса это элемент на месте φ · n, как в прошлом уроке.

Зачем монетка. Каждое уплотнение сдвигает оценку ранга на плюс или минус свой вес, а таких уплотнений тысячи. Если бы сдвиги всегда шли в одну сторону, они складывались бы, и ошибка росла бы пропорционально их числу. Независимые случайные знаки складываются иначе: сумма m слагаемых ±1 имеет стандартное отклонение √m, а не m. Это тот же закон корня, по которому усреднение уменьшает шум, и то же рассуждение, что в оценке второго момента.

Что добавляет KLL. Ошибку определяют верхние уровни: там веса велики. Нижние уровни вносят сдвиги весом 1, 2, 4 - на общую ошибку они почти не влияют. Поэтому в сводке KLL ёмкость буферов убывает от верхнего уровня к нижним в постоянное число раз. Суммарная память перестаёт расти с длиной потока и составляет порядка (1/ε) · √(log(1/ε)) элементов.

Сводка Гринвальда-Ханны решает задачу без случайности. Она хранит отобранные значения, и при каждом - два числа: сколько элементов потока оно представляет и насколько неопределённо его место. Запись сливают с соседней, пока у получившейся записи сумма этих двух чисел не превышает 2ε · n. Памяти нужно порядка (1/ε) · log(ε · n) записей, и гарантия выполняется всегда, а не с вероятностью.

Правило

Уплотнение: отсортировать буфер элементов веса w, оставить каждый второй, начиная со случайного из двух первых, и присвоить оставшимся вес 2w; оценка любого ранга меняется не больше чем на w, в среднем на ноль. Сводка из уровней с уплотнением хранит порядка ёмкость · log₂(n / ёмкость) элементов, а с убывающими ёмкостями - порядка 1/ε с логарифмическим множителем, против 1/ε² у выборки. Гарантия таких сводок - ошибка по рангу, одинаковая для всех квантилей. Сводки одного устройства объединяются слиянием буферов по уровням.

Разбор: сводка на буферах по 32 и по 128

Поток - четыре тысячи значений с длинным хвостом, как в прошлом уроке. Функция dobavit кладёт элемент на уровень 0 и уплотняет заполненные буферы; kvantil возвращает ответ и число хранимых элементов. Ёмкость всех буферов здесь одинаковая - это упрощённая схема, без убывания ёмкостей. Для каждой ёмкости печатается строка: ёмкость, число уровней, затем для квантилей 0,5, 0,9 и 0,99 - оценка и её истинное место, и в конце число хранимых элементов. Последняя строка вывода - точные квантили.

import random

def dobavit(urovni, x, emkost):
    urovni[0].append(x)
    u = 0
    while len(urovni[u]) >= emkost:
        bufer = sorted(urovni[u])
        if u + 1 == len(urovni):
            urovni.append([])
        i = random.randint(0, 1)
        while i < len(bufer):
            urovni[u + 1].append(bufer[i])
            i = i + 2
        urovni[u] = []
        u = u + 1

def kvantil(urovni, dolya):
    pary = []
    ves = 1
    vsego = 0
    for bufer in urovni:
        for x in bufer:
            pary.append([x, ves])
            vsego = vsego + ves
        ves = ves * 2
    nakopleno = 0
    for para in sorted(pary):
        nakopleno = nakopleno + para[1]
        if nakopleno > dolya * vsego:
            return [para[0], len(pary)]
    return [0, 0]

random.seed(64)
n = 4000
potok = []
for i in range(n):
    potok.append(int(20 / (random.random() + 0.02)))
po_poryadku = sorted(potok)

for emkost in [32, 128]:
    urovni = [[]]
    for x in potok:
        dobavit(urovni, x, emkost)
    stroka = [emkost, len(urovni)]
    for dolya in [0.5, 0.9, 0.99]:
        otvet = kvantil(urovni, dolya)
        rang = 0
        while po_poryadku[rang] < otvet[0]:
            rang = rang + 1
        stroka.append(otvet[0])
        stroka.append(round(rang / n, 3))
    stroka.append(otvet[1])
    print(stroka)
print(po_poryadku[n // 2], po_poryadku[n * 9 // 10], po_poryadku[n * 99 // 100])

[32, 8, 37, 0.488, 230, 0.928, 806, 0.993, 96]
[128, 6, 37, 0.488, 170, 0.901, 676, 0.987, 352]
37 168 741

Точные значения - 37, 168 и 741. Сводка с буферами по 32 хранит 96 элементов в восьми уровнях: медиана точна, 90-й перцентиль - 230 вместо 168, место 0,928, ошибка по рангу почти три процента. Сводка с буферами по 128 хранит 352 элемента в шести уровнях: 90-й перцентиль - 170, место 0,901; 99-й - 676, место 0,987.

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

Разбор: хвост и сводки с другой гарантией

99-й перцентиль в сводке на 128: значение 676 при точном 741, место 0,987. Ошибка по рангу - три тысячных, меньше, чем у 90-го перцентиля в сводке на 32. А по значению - 9%. Это тот же эффект, что в прошлом уроке: в хвосте соседние места занимают далёкие значения.

Сводки с уплотнением и сводка Гринвальда-Ханны держат одну и ту же ошибку по рангу для всех квантилей - и для медианы, где она не нужна такой малой, и для p99,9, где её не хватает. Когда важен хвост, берут сводки с другой гарантией.

Гистограмма с заданными границами. Заранее выбирают пороги - 10, 50, 100, 500 мс - и считают, сколько значений попало в каждый промежуток. Сводка - несколько счётчиков; объединение - сложение. Квантиль определяется с точностью до ширины промежутка, поэтому границы ставят густо там, где нужна точность. Недостаток - границы надо знать заранее.

Гистограмма с растущими промежутками. Границы идут геометрической прогрессией: каждая на 2% больше предыдущей. Вместо значения возвращают середину его промежутка, и она отличается от любого значения в нём не больше чем на 1% - включая самый дальний хвост, а промежутков на диапазон от миллисекунды до часа нужно несколько сотен. Так устроена сводка DDSketch.

t-digest хранит набор точек-средних с весами и делает их мелкими у краёв распределения и крупными в середине: память тратится на хвосты. Строгой гарантии в общем случае у неё нет, но на практике дальние перцентили она даёт точнее сводок с равномерной ошибкой по рангу.

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

Уплотнение без монетки. Если всегда оставлять нечётные места, каждое уплотнение сдвигает ранги в одну сторону, и сдвиги складываются: ошибка растёт пропорционально числу уплотнений, а не корню из него.

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

Гистограмма с неудачными границами. Если время ответа выросло и все запросы попали в последний промежуток «больше 500 мс», гистограмма сообщает о перцентилях одно: они больше 500.

Объединение сводок разного устройства. Сливать можно сводки с одинаковой ёмкостью и одинаковыми правилами; гистограммы - только с одинаковыми границами.

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

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

Аналитические базы. Приближённые перцентили в Elasticsearch и одна из функций квантилей в ClickHouse построены на t-digest. Библиотека Apache DataSketches содержит KLL и применяется в хранилищах вроде Druid. В Spark метод approxQuantile работает на варианте сводки Гринвальда-Ханны.

Выбор определяется вопросом. Нужны медиана и квартили для отчёта - любая сводка с ошибкой по рангу. Нужен p99,9 времени ответа с точностью до процентов по значению - сводка с относительной точностью. Нужно складывать данные тысяч экземпляров - гистограмма со счётчиками, проще всего объединяемая.

Теперь сам

1. Буфер элементов веса 1: 1, 3, 4, 7, 9, 12. Монетка выбрала первое, третье и пятое места. Какие элементы останутся и с каким весом? Как изменится оценка ранга значения 5?
2. Поток - миллион элементов, все буферы ёмкостью 128. Сколько примерно уровней и какой памятью ограничена сводка? 10⁶ / 128 ≈ 7800, log₂ 7800 ≈ 13.
3. Гистограмма: до 10 мс - 500 запросов, от 10 до 50 - 300, от 50 до 100 - 150, от 100 до 500 - 50. В каком промежутке лежит 90-й перцентиль?
4. Уплотнений было 10 000, каждое сдвигает ранг на плюс или минус единицу. Каков порядок суммарного сдвига при случайных знаках и при одинаковых?
5. Границы гистограммы растут в 1,02 раза. Сколько промежутков нужно, чтобы покрыть диапазон от 1 до 1 000 000? ln 10⁶ ≈ 13,8, ln 1,02 ≈ 0,0198.