Отпечаток мультимножества и второй момент: два потока в одном числе

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

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

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

Ответь себе до чтения: достаточно ли сравнить количество записей и сумму их значений? Нет: потоки 3, 5 и 4, 4 имеют одинаковое количество и одинаковую сумму. Сумма квадратов различит эту пару и пропустит другую. Нужна свёртка, которую нельзя обмануть заранее подобранной подменой, - и она снова получается из случайной точки.

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

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

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

Механизм: многочлен вместо потока и знаки вместо частот

Мультимножество - набор, в котором важно, сколько раз входит каждый элемент, и не важен порядок.

Отпечаток. Пусть элементы - целые числа от 0 до p − 1, где p - простой модуль (другие данные сначала инъективно кодируют в такие числа: разные элементы должны иметь разные коды). Если просто взять остатки произвольных целых, 1 и p + 1 станут неразличимы. Сопоставим потоку a₁, a₂, …, aₙ многочлен, у которого эти числа - корни:

F(x) = (x − a₁) · (x − a₂) · … · (x − aₙ)

От порядка множителей произведение не зависит. А многочлен однозначно определяется своими корнями с кратностями, поэтому разным мультимножествам соответствуют разные многочлены. Дальше работает проверка из прошлой главы: выбрать случайную точку x по простому модулю p и сравнить значения. Значение считается по ходу потока одной переменной: y = y · (x − a) mod p на каждый элемент. Два разных многочлена степени не больше n совпадают не больше чем в n точках поля. Для заранее фиксированных разных мультимножеств и равномерного x вероятность совпадения не больше n / p; выбирают p существенно больше n. Это не вероятность различия входов при условии совпавших отпечатков: для неё нужна модель входов.

Точку обе стороны обязаны использовать одну и ту же, и выбрать её нужно так, чтобы автор данных не знал её заранее.

Второй момент. Пусть ключ i встретился в потоке fᵢ раз. Сумма F₂ = f₁² + f₂² + … называется вторым моментом потока. Она мала, когда поток ровный, и велика, когда несколько ключей доминируют: для тысячи разных ключей по одному разу F₂ = 1000, для одного ключа тысячу раз - миллион. Это ещё и число упорядоченных пар одинаковых элементов, считая пару элемента с самим собой, то есть размер соединения таблицы с самой собой по этому ключу.

Оценка в один счётчик. Каждому ключу назначают знак s = +1 или −1 - случайный, но постоянный: при каждом появлении ключа знак тот же. Счётчик Z начинается с нуля, и приход ключа прибавляет к нему знак этого ключа. В конце Z = s₁·f₁ + s₂·f₂ + …. Возведём в квадрат:

Z² = (f₁² + f₂² + …)  +  сумма по парам разных ключей: 2 · sᵢ·sⱼ · fᵢ·fⱼ

В первой скобке знаки исчезли: s² = 1 при любом знаке. Во второй каждое слагаемое содержит произведение двух независимых знаков, а оно равно +1 и −1 с равной вероятностью, в среднем ноль. Значит, E[Z²] = F₂: квадрат счётчика - несмещённая оценка второго момента.

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

Одна оценка ненадёжна: дисперсия Z² бывает до 2 · F₂², то есть стандартное отклонение сравнимо с самой величиной. Дальше - схема из главы про хвостовые оценки: завести несколько независимых счётчиков, со своими знаками у каждого; среднее t квадратов уменьшает дисперсию в t раз, а медиана нескольких таких средних поднимает надёжность.

Правило

Отпечаток мультимножества: y = y · (x − a) mod p, где p простое, элементы инъективно закодированы числами 0 ≤ a < p, а x равномерно выбран из поля и общий для потоков. Разные отпечатки доказывают различие. Для любых фиксированных разных мультимножеств длины не больше n вероятность совпадения отпечатков по случайному x не больше n / p. Оценка второго момента: счётчик Z прибавляет постоянный случайный знак каждого приходящего ключа, E[Z²] = F₂; для точности ε усредняют порядка 1/ε² счётчиков и берут медиану нескольких средних. Счётчик Z объединённого потока равен сумме счётчиков частей.

Разбор: три потока с одинаковой суммой

Первый поток, его перестановка и поток, в котором пара 3, 5 заменена на 4, 4.

import random

p = 67108859

def otpechatok(potok, x):
    y = 1
    for a in potok:
        y = y * (x - a) % p
    return y

pervyj = [3, 5, 8, 8, 13, 21, 5]
perestavlen = [8, 5, 21, 3, 5, 13, 8]
podmenyon = [4, 4, 8, 8, 13, 21, 5]

random.seed(57)
x = random.randrange(p)
print(sum(pervyj), sum(perestavlen), sum(podmenyon))
print(otpechatok(pervyj, x), otpechatok(perestavlen, x), otpechatok(podmenyon, x))

63 63 63
21341961 21341961 40733743

Суммы у всех трёх - 63, количество элементов одинаковое: простые накопители подмену не видят. Отпечатки первого потока и его перестановки совпали, у подменённого - другой. Вероятность, что отпечатки двух разных потоков из семи элементов совпадут в случайной точке, не больше 7 / 67 108 859. Зерно здесь задано ради повторяемости урока; в настоящей сверке точку берут из стойкого генератора уже после того, как оба потока зафиксированы.

Для потока из миллиарда элементов с таким модулем оценка n / p бесполезна: n больше p. Модуль берут порядка 2⁶¹ и считают в длинных числах или проверяют в двух независимых точках.

Разбор: второй момент потока из четырёх тысяч ключей

Поток: 40% приходится на пять тяжёлых ключей, остальное размазано по ключам от 6 до 300. Знак ключа для счётчика с номером nomer - один случайный бит от генератора, засеянного ключом и номером. Счётчиков 60: пять групп по двенадцать.

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

import random

def znak(klyuch, nomer):
    random.seed(klyuch * 1000 + nomer)
    return random.getrandbits(1) * 2 - 1

random.seed(58)
chastoty = {}
for i in range(4000):
    if random.random() < 0.4:
        klyuch = random.randint(1, 5)
    else:
        klyuch = random.randint(6, 300)
    chastoty[klyuch] = chastoty.get(klyuch, 0) + 1

tochno = 0
for klyuch in chastoty:
    tochno = tochno + chastoty[klyuch] ** 2

grupp = 5
v_gruppe = 12
srednie = []
for g in range(grupp):
    summa = 0
    for t in range(v_gruppe):
        nomer = g * v_gruppe + t
        z = 0
        for klyuch in chastoty:
            z = z + znak(klyuch, nomer) * chastoty[klyuch]
        summa = summa + z * z
    srednie.append(round(summa / v_gruppe))
print(tochno, len(chastoty))
print(srednie, sorted(srednie)[grupp // 2])

488874 300
[510670, 475705, 899380, 155281, 139294] 475705

Точное значение - 488 874 при трёхстах разных ключах. Пять групповых средних: от 139 тысяч до 899 тысяч. Разброс огромен, хотя каждое - среднее двенадцати оценок: поток сильно перекошен, и Z в основном определяется тем, как выпали знаки пяти тяжёлых ключей. Медиана пяти средних - 475 705, ошибка 2,7%.

Здесь видно, зачем нужны обе ступени. Среднее по всем шестидесяти счётчикам равнялось бы 436 066: его тянут вниз две неудачные группы. Медиана на них не реагирует.

Граница приёма - цена точности. Точность ε требует порядка 1/ε² счётчиков в группе: для 10% - сотни, для 1% - десятки тысяч, и каждый приходящий ключ обновляет их все. Практические реализации раскладывают ключ по ячейкам хешем, как в count-min, и обновляют одну ячейку в строке. И второе условие: знаки разных ключей должны быть независимы - для доказательства дисперсии достаточно независимости любых четырёх ключей, но меньшим не обойтись. Такие знаки получают без таблицы всех ключей - например, из многочлена третьей степени со случайными коэффициентами по простому модулю.

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

Сверка по сумме или по исключающему ИЛИ. Сумму обманывает замена 3, 5 на 4, 4. Исключающее ИЛИ не замечает пару одинаковых записей: два дубликата гасят друг друга, и поток с двумя лишними копиями одной записи неотличим от исходного.

Знак назначают заново при каждом появлении ключа. Тогда Z - это сумма независимых ±1 по всем элементам потока, и E[Z²] равно длине потока при любых данных. Счётчик перестаёт что-либо измерять. Знак обязан быть функцией ключа.

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

Одно среднее вместо медианы средних. В разборе оно ошиблось на 11%, медиана - на 2,7%.

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

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

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

Наблюдение за трафиком. Резкий рост второго момента при той же интенсивности означает, что поток стал неравномерным: один адрес или один ключ начал занимать заметную долю. Это ранний признак и атаки, и «горячего» ключа в распределённом хранилище.

Теперь сам

1. Частоты трёх ключей - 3, 1 и 2. Чему равен второй момент?
2. В потоке тысяча элементов. Чему равен второй момент, если все элементы разные, и чему - если все одинаковые?
3. Ключам A, B, C назначены знаки +1, −1, +1, частоты - 3, 1 и 2. Чему равны Z и Z²?
4. Два потока сравнивают по исключающему ИЛИ всех элементов: 5, 5, 7 и 7. Что покажет сравнение?
5. Отпечаток мультимножества из миллиона элементов считают по модулю около 10⁹. Какова оценка вероятности ошибки и как её уменьшить?