CS
Задачник Базовый курс EN

Задача

Память для фильтров

оптимизация есть ли элемент вероятностная структура базы данных в проде

У LSM-дерева на диске k прогонов, в i-м — ni ключей. На фильтры Блума для них выделено M бит памяти. Фильтр из b бит на n ключей при лучшем числе хеш-функций ошибается — говорит «возможно, есть» про отсутствующий ключ — с вероятностью

$$p(b, n) = e^{-\frac{b}{n} (\ln 2)^2}.$$

Если прогону не дать ни бита, фильтра нет, и p = 1: прогон читают всегда. Поиск ключа, которого нет нигде, читает в среднем Σ pi прогонов. Распределите память — любые неотрицательные вещественные bi с суммой не больше M — так, чтобы это число было наименьшим, и выведите его. Среди тестов — деревья из статьи, через которые прошла история git этого сайта.

Вход

В первой строке — число вариантов q (1 ≤ q ≤ 104). Каждый вариант — две строки: k и M (1 ≤ k ≤ 60, 0 ≤ M ≤ 1012), затем k чисел ni (1 ≤ ni ≤ 109). Сумма всех k не больше 105.

Выход

Для каждого варианта — наименьшее среднее число прочитанных прогонов, с относительной или абсолютной ошибкой не больше 10−6.

В первом примере у дерева три уровня по 1000, 10 000 и 100 000 ключей и по 10 бит на ключ. Поровну — по 10 бит на ключ каждому — выходит 0,0246 прочитанного прогона на поиск, а лучшее распределение даёт 0,0117. В третьем варианте прогоны одинаковые, и лучше поровну.

Примеры

Пример 1

Вход
3
3 1110000
1000 10000 100000
3 555000
1000 10000 100000
4 40000
1000 1000 1000 1000
Выход
0.01166407113
0.128866675
0.03277019787

Пример 2

Вход
3
3 0
7 70 700
3 10
7 70 700
3 3000
7 70 700
Выход
3
2.503404404
0.2227416257

Ограничения

Время · Python
4000 мс
Время · Go
1000 мс
Память
256 МБ
Проверка
5 тестов

Разбор

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

1Подсказка 1

Отдайте один бит от большого прогона маленькому. На сколько вырастет ошибка большого фильтра и на сколько упадёт маленького? Производная p по b равна −(ln 2)²·p/n.

2Подсказка 2

В оптимуме перекладывание бита ничего не меняет: у всех прогонов с фильтром производная одна и та же. Что это говорит об отношении pi / ni?

3Идея

Обозначим c = (ln 2)². Функция e−cb/n выпукла по b, поэтому минимум суммы при Σ bi = M — там, где у всех прогонов с фильтром одинакова скорость убывания: c·pi/ni = const. Значит, pi = λ·ni: ошибка фильтра пропорциональна размеру прогона. Маленьким прогонам — почти безошибочные фильтры, большим — похуже, ведь бит на ключ у большого стоит в сотни раз дороже. Вероятность не бывает больше 1, поэтому прогоны, у которых λ·ni ≥ 1, остаются без фильтра совсем. Это результат Нива Даяна, Маноса Атанассулиса и Стратоса Идреоса (система Monkey, 2017) — в статье о нём абзац.

4Разбор

Пусть фильтры есть у множества прогонов S. Из pi = λni биты bi = (ni/c)·ln(1/(λni)), и условие Σ bi = M даёт

$$\ln \lambda = -\frac{c M + \sum_{S} n_i \ln n_i}{\sum_{S} n_i}.$$

Без фильтра остаются самые большие прогоны: если какой-то прогон стоит за чертой, то и все больше него. Поэтому начинаем со всех прогонов, считаем λ и, пока у самого большого λ·n ≥ 1, убираем его из S и пересчитываем. Ответ — (k − |S|) + λ·ΣS ni. Логарифм λ — чтобы не терять точность, когда λ около 10−12.

Насколько это выгоднее, видно на дереве сайта: в конце истории у ярусного дерева с ростом в 10 раз одиннадцать прогонов от 89 до 3432 ключей. При 10 битах на ключ поровну выходит 0,090 лишнего чтения на поиск, а при лучшем распределении — 0,051, в 1,8 раза меньше, и ни одного лишнего бита. Чем больше уровней и чем сильнее различаются прогоны, тем больше выигрыш: в одном из моментов истории — в 3,5 раза.

4+Решение
5Сложность

O(k log k) на вариант: сортировка, потом каждый прогон убирается из S не больше одного раза, а суммы пересчитываются вычитанием.

6Типичные ошибки
  • Поровну на ключ. По M/N бит на ключ каждому прогону — так делают по умолчанию, и в первом примере это вдвое хуже лучшего.
  • Отрицательные биты. Формула с λ без отбрасывания больших прогонов даёт им отрицательное число бит, а значит, вероятность больше единицы.
  • Без логарифмов. λ бывает около 10−12 и меньше, а n — до 109; считайте ln λ, а не само λ.

Алгоритмы задачи

SYS Структура данных LSM-дерево Записи копятся в памяти и ложатся на диск отсортированными прогонами; фоновые слияния держат число прогонов малым. запись O(1) амортизированно в памяти плюс O(L·T/B) на перезапись при слиянии; чтение — по прогону на уровень 2 задачи DS Структура данных Фильтр Блума Отвечает «точно нет» или «возможно, да» о членстве в множестве, тратя около 10 бит на элемент. O(k) 2 задачи
Каталог алгоритмов