Count-min: частоты миллиона ключей в таблице фиксированного размера

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

Как думаешь, в какую сторону ошибается таблица

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

Ответь себе до чтения: если в таком сжатом виде счётчики разных адресов неизбежно смешиваются, оценка для данного адреса может быть и больше, и меньше истинной? Только больше. И именно поэтому из нескольких оценок надо брать наименьшую.

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

Четыре гардероба в четырёх залах театра, в каждом двести крючков. Зритель вешает пальто во всех четырёх, на крючок, номер которого каждый гардероб вычисляет по фамилии своим способом. На одном крючке в одном гардеробе висят пальто нескольких людей.

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

Механизм: минимум из завышенных оценок

Count-min - таблица C из d строк по w счётчиков, сначала все нули. Хеш-функции h₁, …, h_d независимы, каждая отображает ключ в номер столбца от 0 до w − 1.

пришёл ключ x:      для каждой строки j:  C[j][hⱼ(x)] увеличить на 1
оценка частоты x:   наименьшее из C[1][h₁(x)], …, C[d][h_d(x)]

Пусть истинная частота ключа x равна f. В ячейке C[j][hⱼ(x)] лежит f плюс частоты всех ключей, которым функция hⱼ дала тот же столбец. Чужие частоты неотрицательны, поэтому каждая из d ячеек не меньше f, и минимум тоже. Ошибка односторонняя.

Насколько велика добавка в одной строке. Возьмём другой ключ y с частотой g. Он попадает в тот же столбец, что и x, с вероятностью 1/w, и тогда добавляет g. Индикаторы и линейность: ожидаемая добавка от всех чужих ключей -

E[шум в строке] = (сумма частот остальных ключей) / w ≤ N / w

где N - общее число пришедших ключей. Шум неотрицателен, и неравенство Маркова даёт: шум превышает удвоенное ожидание, 2N/w, с вероятностью не больше 1/2.

Одна строка надёжна наполовину - мало. Но строк d, функции независимы, и минимум плох, только если плохи все строки сразу:

P(оценка − f > 2N/w) ≤ (1/2)ᵈ

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

Параметры выбирают от желаемого. Нужна ошибка не больше доли ε от длины потока с вероятностью не меньше 1 − δ: тогда w = 2/ε, d = log₂(1/δ). Для ε = 0,1% и δ = 1% это 2000 столбцов и 7 строк - 14 000 счётчиков при любом числе ключей; от длины потока зависит только разрядность счётчика.

Правило

Count-min с d строками и w столбцами: вставка увеличивает C[j][hⱼ(x)] в каждой строке, оценка - минимум этих d ячеек. Оценка никогда не меньше истинной частоты и превышает её больше чем на 2N/w с вероятностью не больше 1/2ᵈ, где N - сумма всех частот. Для ошибки εN с надёжностью 1 − δ берут w = 2/ε, d = log₂(1/δ). Две таблицы с одинаковыми функциями объединяются поэлементным сложением.

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

Поток: половина запросов приходится на десять «тяжёлых» ключей от 1 до 10, вторая половина размазана по ключам от 11 до 4000. Таблица - 4 строки по 200 столбцов, 800 счётчиков. Хеш-функция строки s - генератор, засеянный числом klyuch * 10 + s. Рядом ведётся точный словарь, чтобы сравнить.

import random

shirina = 200
strok = 4
tablica = []
for s in range(strok):
    tablica.append([0] * shirina)

def stolbec(klyuch, s):
    random.seed(klyuch * 10 + s)
    return random.randrange(shirina)

def dobavit(klyuch):
    for s in range(strok):
        j = stolbec(klyuch, s)
        tablica[s][j] = tablica[s][j] + 1

def ocenka(klyuch):
    luchshaya = tablica[0][stolbec(klyuch, 0)]
    for s in range(1, strok):
        luchshaya = min(luchshaya, tablica[s][stolbec(klyuch, s)])
    return luchshaya

potok = []
random.seed(43)
for i in range(8000):
    if random.random() < 0.5:
        potok.append(random.randint(1, 10))
    else:
        potok.append(random.randint(11, 4000))

tochno = {}
for klyuch in potok:
    tochno[klyuch] = tochno.get(klyuch, 0) + 1
    dobavit(klyuch)

dopusk = 2 * len(potok) / shirina
hudshaya = 0
vyshe_dopuska = 0
nizhe = 0
for klyuch in tochno:
    oshibka = ocenka(klyuch) - tochno[klyuch]
    hudshaya = max(hudshaya, oshibka)
    if oshibka > dopusk:
        vyshe_dopuska = vyshe_dopuska + 1
    if oshibka < 0:
        nizhe = nizhe + 1
print(len(tochno), dopusk, hudshaya, vyshe_dopuska, nizhe)
for klyuch in [1, 2, 3, 11, 12, 5000]:
    print(klyuch, tochno.get(klyuch, 0), ocenka(klyuch))

2549 80.0 28 0 0
1 386 400
2 410 424
3 409 423
11 0 19
12 2 16
5000 0 21

Первая строка: в потоке 2549 разных ключей, допуск 2N/w = 80, наибольшее завышение среди всех ключей - 28, ключей с завышением больше допуска нет, ключей с заниженной оценкой нет. Формула обещала для каждого отдельного ключа вероятность превышения не больше 1/2⁴ ≈ 6%; среди 2549 ключей таких не оказалось вовсе.

Словарь хранит 2549 счётчиков, таблица - 800, и останется на 800, если ключей станет двадцать миллионов.

Разбор: кому из ключей оценка годится

Посмотри на вторую часть вывода. Тяжёлые ключи 1, 2 и 3: истинные частоты 386, 410 и 409, оценки 400, 424 и 423. Завышение 14 при частоте около четырёхсот - три с половиной процента.

Редкие ключи. Ключ 12 встретился дважды, оценка 16 - ошибка в восемь раз. Ключ 11 не встретился ни разу, оценка 19. Ключ 5000 вообще не мог встретиться, оценка 21. Для редкого ключа оценка состоит почти целиком из шума, и отличить «был два раза» от «не было» таблица не может.

Это не поломка, а смысл гарантии. Ошибка ограничена долей от длины потока, а не от частоты ключа: εN одинаково для всех. Ключу, на который приходится 5% потока, прибавка в 0,3% не мешает. Ключу с долей в сотую процента она превышает саму частоту в десятки раз. Count-min отвечает на вопрос «этот ключ тяжёлый или нет» и на вопрос «сколько у тяжёлого», и не отвечает на вопрос «сколько у произвольного».

Шум можно уменьшить, не меняя размеров. Осторожное обновление: при вставке увеличивать не все d ячеек, а только те, что равны текущему минимуму. Оценка по-прежнему не занижается, а лишние прибавки к чужим счётчикам пропадают. Плата - таблицы с осторожным обновлением уже нельзя просто складывать и из них нельзя вычитать.

Родственная структура, count sketch, в каждой строке ещё и умножает прибавку на знак +1 или −1, зависящий от ключа, а оценкой берёт медиану. Чужие ключи приходят с разными знаками и в среднем гасят друг друга: оценка становится несмещённой, ошибка - двусторонней, а её размер определяется не длиной потока, а его «неравномерностью», что выгоднее, когда несколько ключей доминируют.

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

Оценку считают нижней границей. «Не меньше 21 запроса» для ключа, которого не было, - ошибка чтения. Оценка count-min - верхняя граница: частота не больше оценки.

По таблице ищут редкое. Список «ключи, встретившиеся ровно один раз» из count-min не получить: у всех редких ключей оценка - это шум.

Складывают таблицы с разными хеш-функциями. Объединение работает, только если обе стороны считают столбцы одинаково: одни и те же функции, одни и те же размеры.

Экономят на ширине, добавляя строки. Строки снижают вероятность промаха, ширина - его размер. Сорок строк по двадцать столбцов дают допуск N/10 с огромной надёжностью - надёжно плохую оценку.

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

Сетевой мониторинг: какие адреса или потоки дают основную долю трафика. Ключей - миллионы, памяти на линейной карте - килобайты, а нужны именно тяжёлые.

Кеши с допуском по частоте. Политика TinyLFU, на которой работает библиотека Caffeine для Java, решает, стоит ли помещать новый объект в кеш вместо старого, сравнивая их частоты обращений; частоты хранятся в таблице count-min с четырёхбитными счётчиками, которые периодически делят пополам, чтобы старые обращения забывались.

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

Теперь сам

1. Таблица шириной 1000 столбцов, в потоке миллион ключей. Какое завышение в одной строке не будет превышено с вероятностью не меньше 1/2?
2. В таблице 10 строк. Оцени вероятность того, что оценка завышена больше чем на 2N/w.
3. Нужна ошибка не больше 1% длины потока с надёжностью 99,9%. Сколько столбцов, строк и всего счётчиков? log₂ 1000 ≈ 10.
4. Для ключа прочитаны ячейки 57, 41 и 44. Какова оценка и что известно об истинной частоте?
5. Поток - миллион запросов. Ключ A встретился 50 000 раз, ключ B - 30 раз. Таблица шириной 2000. Насколько полезна оценка для каждого?