Шары и корзины: пустые ячейки, самая полная и сила двух выборов

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

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

Двадцать тысяч запросов раздают двадцати тысячам серверов: каждый запрос уходит на случайный сервер. В среднем на сервер приходится один запрос.

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

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

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

Случайность не выравнивает. Ровную раздачу даёт только учёт: кто-то смотрит, где уже мокро.

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

Пустые корзины. Один шар не попадает в данную корзину с вероятностью 1 − 1/n. Шары независимы, поэтому все n шаров пролетают мимо с вероятностью (1 − 1/n)ⁿ. При росте n это число стремится к 1/e ≈ 0,368; число e ≈ 2,718 как раз и определяют через этот предел. По индикаторам ожидаемое число пустых корзин - n / e, то есть 36,8% от всех.

Корзины с k шарами. Тем же способом считается доля корзин, в которых ровно k шаров. При n шарах на n корзин она близка к 1 / (e · k!), где k! - факториал:

шаров в корзине      0       1       2       3       4       5       6       7
доля корзин        0,368   0,368   0,184   0,061   0,015   0,0031  0,0005  0,00007

Откуда эта форма. Набор из k шаров, попавших в корзину, можно выбрать примерно nᵏ / k! способами: n вариантов для каждого из k шаров, и деление на k!, чтобы не считать один набор в разном порядке. Все шары набора попадают в данную корзину с вероятностью (1/n)ᵏ, остальные пролетают мимо с вероятностью около 1/e. Множители nᵏ и (1/n)ᵏ сокращаются, остаётся 1 / (e · k!).

Самая полная корзина. Ожидаемое число корзин с k шарами - n / (e · k!). Пока оно намного больше единицы, такие корзины почти наверняка есть; когда падает заметно ниже единицы, их, скорее всего, нет; около единицы - как повезёт. Граница проходит там, где k! ≈ n / e. Факториал растёт быстрее любой степени, поэтому k растёт медленнее логарифма: точная асимптотика - ln n / ln ln n.

Два выбора. Для каждого шара берут две случайные корзины и кладут в ту, где шаров меньше. Пусть βᵢ - доля корзин, в которых не меньше i шаров. Чтобы корзина доросла до i + 1, какой-то шар должен был выбрать две корзины, в каждой из которых уже не меньше i. В любой момент раздачи таких корзин не больше, чем в конце, поэтому для каждого шара вероятность этого не больше βᵢ · βᵢ, а шаров всего n: корзин, доросших до i + 1, в среднем не больше n · βᵢ². Строгое доказательство аккуратнее обходится со случайностью самих долей, но идея в этом:

βᵢ₊₁ ≲ βᵢ²          доли:  1/2 → 1/4 → 1/16 → 1/256 → 1/65 536 → …

Возведение в квадрат на каждом уровне - это удвоение показателя: за i уровней доля падает до 2 в степени −2ⁱ. Она становится меньше 1/n, когда 2ⁱ ≈ log₂ n, то есть через i ≈ log₂ log₂ n уровней. При одном выборе доля на каждом уровне делится на k - сначала на 2, потом на 3, потом на 4. Разница между «делить на небольшое число» и «возводить в квадрат» и есть разница между логарифмом и двойным логарифмом.

Правило

При n шарах в n корзин доля пустых корзин близка к 1/e ≈ 0,368, доля корзин с k шарами - к 1 / (e · k!), а наибольшая загрузка почти наверняка равна Θ(ln n / ln ln n). Если каждый шар кладут в менее загруженную из двух случайных корзин, наибольшая загрузка равна ln ln n / ln 2 + O(1). При d случайных корзинах - ln ln n / ln d + O(1): переход от одной к двум меняет порядок роста, дальнейшее увеличение d - только постоянный множитель.

Разбор: один выбор

import random

random.seed(12)
n = 20000
korziny = [0] * n
for shar in range(n):
    k = random.randrange(n)
    korziny[k] = korziny[k] + 1

po_zagruzke = [0] * 12
for k in korziny:
    po_zagruzke[k] = po_zagruzke[k] + 1
print(max(korziny), po_zagruzke[:8])
print(round(po_zagruzke[0] / n, 4), round(po_zagruzke[1] / n, 4), round(po_zagruzke[2] / n, 4))

7 [7403, 7285, 3704, 1222, 304, 71, 7, 4]
0.3701 0.3643 0.1852

Список во второй части первой строки - сколько корзин получили 0, 1, 2 и так далее шаров. Доли первых трёх значений - 0,370, 0,364 и 0,185 при предсказанных 0,368, 0,368 и 0,184.

Самая полная корзина получила семь шаров, и таких корзин четыре. Проверка по формуле: n / e = 7358, 7! = 5040, 8! = 40 320. Ожидаемое число корзин с семью шарами - 7358 / 5040 ≈ 1,5, с восемью - 7358 / 40 320 ≈ 0,18. Семёрки есть, восьмёрок нет - как и предсказано.

Что это значит для хеш-таблицы с цепочками при заполнении 1: средняя цепочка длиной один, но 37% ячеек пусты, а самая длинная цепочка - семь. Поиск «в среднем за O(1)» и «самый неудачный поиск» - разные вопросы, и на второй ответ - Θ(ln n / ln ln n).

Разбор: два выбора

Та же раздача, но каждый шар смотрит на две случайные корзины.

import random

random.seed(12)
n = 20000
korziny = [0] * n
for shar in range(n):
    a = random.randrange(n)
    b = random.randrange(n)
    if korziny[b] < korziny[a]:
        a = b
    korziny[a] = korziny[a] + 1

po_zagruzke = [0] * 12
for k in korziny:
    po_zagruzke[k] = po_zagruzke[k] + 1
print(max(korziny), po_zagruzke[:5])

3 [4777, 10632, 4405, 186, 0]

Максимум упал с семи до трёх, и корзин с тремя шарами всего 186 из двадцати тысяч. Пустых стало 4777 вместо 7403, корзин ровно с одним шаром - больше половины.

Цепочка квадратов из механизма видна на этих числах. Доля корзин с двумя и более шарами: (4405 + 186) / 20 000 = 0,23. Её квадрат - 0,053, и доля корзин с тремя шарами обязана быть не больше: она 0,0093. Квадрат этой доли - 0,00009, на 20 000 корзин ожидается меньше двух штук; в опыте корзин с четырьмя шарами не оказалось ни одной.

Граница приёма - слово «два». Если смотреть на три корзины вместо двух, максимум изменится с ln ln n / ln 2 на ln ln n / ln 3: при n = 20 000 это 3,3 против 2,1, разница около единицы. А если смотреть на все корзины и класть в самую пустую, раздача станет идеально ровной, но каждому шару придётся знать состояние всей системы. Два выбора - почти весь выигрыш за два обращения.

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

«Хеш-функция хорошая, значит цепочки ровные». Идеально случайная функция даёт распределение из первой таблицы: треть ячеек пуста, самая длинная цепочка растёт с размером таблицы. Неровность - свойство случайной раздачи, а не дефект функции.

Запас по среднему. Сервер выдерживает три запроса одновременно, в среднем приходит один - кажется, что запас тройной. При случайной раздаче 20 000 запросов больше трёх получат 304 + 71 + 7 + 4 = 386 серверов.

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

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

Балансировщики нагрузки. В nginx для группы серверов есть метод random two least_conn: взять два случайных сервера и отправить запрос тому, у кого меньше соединений. Это буквально правило двух выборов, и нужен он как раз тогда, когда балансировщиков несколько и ни один не видит полной картины.

Хеш-таблицы. Вариант «два места на ключ, клади в более короткую цепочку» снижает самую длинную цепочку с ln n / ln ln n до ln ln n. Следующий урок показывает, что из двух мест на ключ можно получить и больше: поиск за две пробы в худшем случае.

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

Теперь сам

1. В хеш-таблицу на 1000 ячеек положили 1000 ключей идеальной хеш-функцией. Сколько примерно ячеек пусты?
2. В той же таблице сколько примерно ячеек с цепочкой длины 3?
3. n = 1 000 000, один выбор. Какую загрузку самой полной корзины предсказывает правило k! ≈ n / e? Используй n / e ≈ 367 900 и факториалы: 8! = 40 320, 9! = 362 880, 10! = 3 628 800.
4. При двух выборах доля корзин, в которых не меньше трёх шаров, равна 0,01. Оцени сверху долю корзин, в которых не меньше четырёх.
5. Шаров вдвое больше, чем корзин: 2n шаров в n корзин, один выбор. Какая доля корзин останется пустой?