Счётчик Морриса: досчитать до миллиарда в пяти битах

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

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

У каждого из ста миллионов объектов есть счётчик обращений. Обращений к одному объекту бывает до миллиарда. Точному счётчику нужно 30 бит, на все объекты - 375 мегабайт.

Ответь себе до чтения: можно ли уместить счётчик в один байт, если достаточно знать число обращений примерно - отличать тысячу от миллиона? А в пять бит? В пять бит можно: счётчик от 0 до 31 описывает числа до двух миллиардов. Только считать ему придётся не каждое событие.

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

Турист считает пройденные километры, но в блокноте у него место для одной цифры. Он договаривается с собой: цифра c значит «пройдено около 2ᶜ километров». Чтобы перейти от 5 к 6, то есть от 32 к 64, нужно пройти ещё 32 километра. Отсчитывать их негде - места нет.

Тогда он после каждого километра бросает жребий, который выпадает раз в 32 попытки, и увеличивает цифру, когда выпало. В среднем жребий выпадет как раз через 32 километра. Иногда раньше, иногда позже - отсюда неточность, - но ни одного лишнего знака в блокноте не понадобилось.

Механизм: вероятность, обратная весу шага

Счётчик хранит целое c, сначала ноль.

событие:   с вероятностью 1/2ᶜ увеличить c на единицу
оценка:    2ᶜ − 1

Почему вероятность именно 1/2ᶜ. Переход от c к c + 1 увеличивает оценку на 2ᶜ - таков «вес» этого шага. Чтобы каждое событие добавляло к оценке в среднем единицу, шаг весом 2ᶜ должен случаться один раз на 2ᶜ событий: вес, умноженный на вероятность, равен единице.

То же рассуждение точно. Пусть сейчас в счётчике c, и пришло событие. Величина 2ᶜ превращается в 2ᶜ⁺¹ с вероятностью 1/2ᶜ и остаётся прежней с вероятностью 1 − 1/2ᶜ:

новое среднее значение = 1/2ᶜ · 2ᶜ⁺¹ + (1 − 1/2ᶜ) · 2ᶜ = 2 + 2ᶜ − 1 = 2ᶜ + 1

Каждое событие увеличивает ожидание величины 2ᶜ ровно на единицу, каким бы ни было c. В начале 2⁰ = 1, значит после n событий E[2ᶜ] = n + 1, и оценка 2ᶜ − 1 в среднем равна n. Про такую оценку говорят, что она несмещённая: её ожидание совпадает с оцениваемой величиной.

Несмещённость - не то же, что точность. Оценка принимает только значения 0, 1, 3, 7, 15, …: между соседними - разница вдвое. Дисперсия оценки считается тем же приёмом, через среднее значение 4ᶜ, и равна n(n − 1) / 2 - вывод здесь опущен; стандартное отклонение - около 0,7 · n. Один счётчик сообщает порядок величины, не больше.

Разброс уменьшают двумя способами, и оба платят памятью.

Усреднение. Завести k независимых счётчиков и усреднить оценки. Среднее несмещённых оценок несмещённое, а его стандартное отклонение в √k раз меньше.

Меньшее основание. Вместо двойки взять b, например 1,125. Вероятность шага - 1/bᶜ, оценка - (bᶜ − 1) / (b − 1). Ступени оценки становятся мельче, дисперсия - не больше (b − 1) · n² / 2. Зато c растёт быстрее: до миллиарда при b = 2 счётчик доходит до 30, при b = 1,125 - до 158.

Правило

Счётчик Морриса с основанием b: на каждое событие увеличивать c с вероятностью 1/bᶜ; оценка числа событий - (bᶜ − 1) / (b − 1), для b = 2 это 2ᶜ − 1. Оценка несмещённая, её дисперсия не больше (b − 1) · n² / 2. Память - около log₂ log_b n бит. Среднее k независимых счётчиков уменьшает стандартное отклонение в √k раз.

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

Событие с вероятностью 1/2ᶜ - это c случайных битов, которые все оказались нулями. random.getrandbits(c) возвращает число из c случайных битов; при c = 0 это всегда ноль, и первый шаг делается наверняка.

import random

random.seed(42)
sobytij = 5000
schetchiki = [0] * 8
for sobytie in range(sobytij):
    for i in range(8):
        if random.getrandbits(schetchiki[i]) == 0:
            schetchiki[i] = schetchiki[i] + 1

ocenki = []
for c in schetchiki:
    ocenki.append(2 ** c - 1)
print(schetchiki)
print(ocenki, round(sum(ocenki) / 8))

[12, 13, 13, 11, 12, 11, 11, 11]
[4095, 8191, 8191, 2047, 4095, 2047, 2047, 2047] 4095

Все восемь счётчиков остановились между 11 и 13 - им хватило бы четырёх бит каждому. Отдельные оценки - от 2047 до 8191 при истинных 5000: промах до двух с половиной раз вниз и в 1,6 раза вверх. Среднее по восьми - 4095, ошибка 18%. По формуле стандартное отклонение одного счётчика 0,7 · 5000 = 3500, среднего по восьми - 3500 / √8 ≈ 1240; промах на 905 в эту оценку укладывается.

Восемь счётчиков по четыре бита - 32 бита. Точный счётчик до 5000 занимает 13 бит и не ошибается вовсе. На таком малом числе событий приём не окупается: он нужен, когда счётчиков миллионы, а события идут миллиардами.

Разбор: основание 1,125 и цена точности

Те же пять тысяч событий, основание 1,125. Вероятность шага уже не степень двойки, поэтому сравнивается случайное дробное число с 1/bᶜ.

import random

random.seed(42)
osnovanie = 1.125
sobytij = 5000
schetchiki = [0] * 8
for sobytie in range(sobytij):
    for i in range(8):
        if random.random() < osnovanie ** (-schetchiki[i]):
            schetchiki[i] = schetchiki[i] + 1

ocenki = []
for c in schetchiki:
    ocenki.append(round((osnovanie ** c - 1) / (osnovanie - 1)))
print(schetchiki)
print(ocenki, round(sum(ocenki) / 8))

[52, 55, 55, 53, 51, 56, 53, 54]
[3648, 5198, 5198, 4105, 3242, 5848, 4105, 4619] 4495

Счётчики теперь от 51 до 56, им нужно по шесть бит. Отдельные оценки лежат от 3242 до 5848 - разброс в два с лишним раза уже, чем при основании 2. Среднее по восьми - 4495, ошибка 10%. По формуле стандартное отклонение одного счётчика не больше √(0,125 / 2) · 5000 = 1250.

Обмен виден в числах: два лишних бита на счётчик сузили разброс одного счётчика с 3500 до 1250. Тот же эффект дало бы усреднение восьми счётчиков с основанием 2 - но это 32 бита вместо шести.

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

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

Оценку читают как точное число. «Объект запрошен 8191 раз» на деле значит «от нескольких тысяч до десяти с лишним тысяч». По таким счётчикам сравнивают порядки, а не разницу в проценты.

Жребий заменяют правилом «каждое 2ᶜ-е событие». Чтобы пропустить ровно 2ᶜ − 1 событий, их надо отсчитать, а для этого нужен второй счётчик того же размера, что и точный. Случайность здесь - способ обойтись без памяти о том, сколько событий прошло с последнего шага.

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

Малые числа. До первых десятков событий точный счётчик занимает те же несколько бит и не ошибается.

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

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

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

И сама идея «хранить показатель степени вместо числа» повторится в этой главе ещё раз: HyperLogLogРазбирается в разделе 20, глава «Фильтр Блума, count-min, HyperLogLog»: HyperLogLog: сколько разных, если помнить только нули держит в каждой ячейке не количество, а длину серии нулей - тоже логарифм, и тоже в пяти-шести битах.

Теперь сам

1. В счётчике с основанием 2 записано 10. Какова оценка числа событий?
2. В счётчике записано 6. С какой вероятностью следующее событие его увеличит?
3. В счётчике записано 3. Посчитай ожидаемое значение 2ᶜ после одного события и убедись, что оно выросло на единицу.
4. Усредняют 16 независимых счётчиков с основанием 2. Каким будет стандартное отклонение среднего в долях от n?
5. Сколько бит нужно счётчику с основанием 2, чтобы досчитать до триллиона? 2⁴⁰ ≈ 1,1 · 10¹².