Production-grade структуры: LRU, Bloom, Trie, Union-Find, Consistent Hashing

Это финальный урок алгоритмической под-серии. Уроки 09 и 10 закрывали учебные паттерны: Big-O, поиск, сортировки, графы, парадигмы. Сегодняшний урок прыгает оттуда внутрь продакшена. Каждая структура здесь это ответ на конкретную инженерную проблему, которую ты уже видел в коде Postgres, Redis, Elasticsearch, ClickHouse, Kong и Cloudflare.

После урока ты не путаешь LRU и LFU, понимаешь, почему Bloom не даёт false negative, видишь Trie за автокомплитом и Union-Find за Kruskal MST. И главное, ты закрываешь все 18 NeetCode-паттернов финальной картой самопроверки.

Сцена · алгоритмы внутри инструментов

Открой EXPLAIN ANALYZE любого SELECT в Postgres и почитай вывод. Hash join, merge join, B-tree scan, bitmap heap scan. Каждое слово это структура данных, которую ты раньше учил для собеса, и которую сейчас postgres использует для тебя. То же про Redis: HSET, ZADD, PFADD, BITCOUNT. Каждая команда дёргает специально отобранную структуру.

Production-разработчик не пишет эти структуры с нуля каждую неделю. Но он должен видеть их на первый взгляд, чтобы понять, что в его сервисе тормозит, что нужно заменить и где скрытые квадратичные циклы. Этот урок про развитие именно этого зрения.

Карта урока · что заберёшь домой через 270 минут

Через четыре с половиной часа у тебя в голове будет:

• Кеши и фильтры. LRU как shared_buffers Postgres. Bloom как антиспам. HyperLogLog как uniq() ClickHouse. Count-Min Sketch как Heavy Hitters в стриме.
• Поиск и группировка. Trie как автокомплит. Inverted Index как Lucene. Union-Find как Kruskal MST.
• Сечение деревом. Segment Tree, Fenwick (BIT), Heap.
• Распределение и rate-limit. Consistent Hashing для шардирования. Token bucket, sliding window и counter rate-limit-ы.
• Финал. Таблица 18 NeetCode-паттернов: где каждый покрыт, какая якорная задача, частота на интервью.

Раздел 1 · Web-кеш и LRU

Сцена

Postgres держит горячие страницы базы в памяти. Когда страница нужна и её нет в shared_buffers, Postgres читает её с диска и кладёт в кеш. Когда буфер кончился, нужно кого-то выселить. Стратегия “выселяй того, к кому давно не обращались” это и есть LRU.

LRU делается двусвязным списком (для порядка доступа) плюс хеш-мапой (для O(1) поиска по ключу). Когда обращаешься к ключу, его узел переезжает в голову списка. Когда вставляешь и кеш полный, выселяется хвост.

Идея словами

Двусвязный список даёт два движения за O(1): добавить узел в голову и удалить произвольный узел (если у тебя есть на него ссылка). Хеш-мапа даёт ссылку по ключу за O(1). Вместе они и есть LRU.

LFU (Least Frequently Used) и ARC (Adaptive Replacement Cache) старшие братья LRU. LFU считает число обращений и выселяет самый редкий. ARC балансирует между LRU и LFU динамически. В реальном проде на чтении обычно LRU или его варианты вроде clock-sweep (упрощённый LRU без двусвязного списка).

Упражнения

Что взять с собой

• LRU = двусвязный список плюс мапа. O(1) на get и put. Память O(capacity) плюс постоянный множитель на узлы.
• Stale-while-revalidate, refresh-ahead и write-through это не альтернативы LRU, а паттерны invalidation. LRU отвечает за политику выселения, не за обновление.
• Thundering herd (стампида запросов на холодный кеш) лечится request-coalescing или SELECT FOR UPDATE блокировками, не LRU.

Раздел 2 · Антиспам и Bloom filter

Сцена

Twitter не хочет показывать тебе один и тот же твит дважды. Один из способов: при каждом просмотре сохранять (user_id, tweet_id) в базу и проверять перед показом. Дорого: миллионы пользователей, миллиарды просмотров. Другой способ: держать в памяти Bloom filter на 10MB, который для каждой пары говорит “возможно показывали” или “точно нет”.

False negative невозможен (если все биты установлены, ключ был). False positive возможен и предсказуем. Twitter готов показывать тебе случайный твит дважды в 1% случаев, лишь бы база работала.

Идея словами

Структура: битовый массив длины m (например, m = 10^9) плюс k хеш-функций. На вставку считаешь k хешей ключа, ставишь соответствующие биты в 1. На запрос считаешь те же k хешей, проверяешь, все ли биты в 1. Если все, ключ возможно был. Если не все, точно не был.

Параметры выбираются по формуле:

• false positive rate ≈ (1 - e^(-kn/m))^k где n это число вставленных ключей,
• оптимальное k = (m / n) ln 2.

В реальном Bloom filter хеши делают разными константами одной функции (одна MurmurHash, разные seed-ы) или комбинацией двух хешей по формуле g_i(x) = h1(x) + i * h2(x). Cuckoo filter и Counting Bloom это расширения с поддержкой удаления; чистый Bloom удалять не умеет.

Что взять с собой

• Bloom = битовый массив + k хешей. False negative невозможен, false positive контролируется параметрами.
• Используется в антиспам URL (Chrome safe browsing), в ClickHouse set skip-index, в Cassandra read-path для решения “есть ли ключ в SSTable до открытия файла”, в Akamai CDN.
• Если нужно удалять, Counting Bloom (с массивом счётчиков) или Cuckoo filter. Если нужны точные операции пересечения и объединения, не Bloom, а битовая мапа на полном множестве (только если m влезает).

Раздел 3 · Счётчик уников и HyperLogLog

Сцена

ClickHouse считает SELECT uniq(user_id) FROM events. На таблице с 10 миллиардами строк это O(n) времени и O(unique) памяти на наивном SELECT COUNT(DISTINCT user_id). ClickHouse использует HyperLogLog: 12KB памяти оценивают count distinct для миллиардов значений с точностью ≈ 1%.

Идея словами

Идея в одно предложение: возьми хеш ключа, посчитай число подряд идущих нулей в начале хеша, и используй это как оценку log2 мощности множества. Чем больше уникальных хешей видим, тем длиннее максимальный ноль-префикс. Усреднение по m bucket-ам даёт HyperLogLog.

В bucket идём по первым log2(m) битам хеша. В этот bucket пишем максимальное число ведущих нулей, увиденное у любого хеша, попавшего в bucket. На запрос count distinct усредняем по всем bucket-ам с поправкой на смещения и получаем оценку.

Картинка для запоминания: представь, что бросаешь монету, пока не выпадет орёл. Чем дольше выпадал хвост, тем реже такой исход встречается. Если ты увидел 10 хвостов подряд хотя бы один раз, ты точно сделал больше 2^10 бросков.

Виджета для HyperLogLog в этом уроке нет, формулы коротко: для m bucket-ов погрешность около 1.04 / sqrt(m). ClickHouse использует m = 2^14, что даёт погрешность ≈ 0.81%.

Что взять с собой

• HyperLogLog считает приблизительный count distinct за O(n) времени и O(m) памяти, где m это число bucket-ов (обычно 8-16 KB).
• Используется в Redis (PFADD/PFCOUNT), в ClickHouse (uniq и uniqExact для точного, медленнее), в Google BigQuery (APPROX_COUNT_DISTINCT), в Druid и в любой аналитике на миллиардах событий.
• Если нужна точность, не HLL, а count(distinct) с hash-aggregation. Память при этом будет линейной по уникальным.

Раздел 4 · Топ-N в стриме и Count-Min Sketch

Сцена

Cloudflare смотрит на трафик и хочет знать, какие 100 IP сейчас бомбят сервис. Память не разрешает хранить полный hash-map ip -> count, потому что IP-адресов в час бывает миллиарды. Решение, Count-Min Sketch: матрица счётчиков, на каждый запрос инкрементим d ячеек по разным хешам, на запрос частоты возвращаем минимум.

Идея словами

Структура: двумерный массив counts[d][w] (например, d = 4, w = 2^16) плюс d хеш-функций. Insert: для каждой строки i инкрементируем counts[i][h_i(key)]. Query: возвращаем min(counts[i][h_i(key)]) для всех i.

Гарантии: min всегда >= истинной частоте (потому что коллизии могут только переоценить, не недооценить), и ошибка <= ε * total с вероятностью 1 - δ где ε = e/w, δ = e^-d.

Heavy Hitters это применение поверх CMS: держим heap топ-K элементов по их CMS-оценке. На каждое событие обновляем CMS, потом проверяем, надо ли обновить heap.

Таблица примерного состояния после 100 вставок: на матрице 4×2^16 с 4 хешами CMS даёт погрешность не больше 1-2 единиц на ключ; heap топ-10 будет содержать корректные 8-9 из настоящих топ-10.

Упражнения

Что взять с собой

• Count-Min Sketch отвечает на “сколько раз я видел ключ” с односторонней ошибкой (не недооценит). Память O(d * w), настраивается ε и δ.
• Heavy Hitters = CMS плюс heap топ-K. Реальные кейсы: обнаружение DDoS по топ-IP, топ трендов в Twitter, горячие ключи в KV-хранилищах.
• Если нужна точность, сортировка по частоте плюс топ-K из кучи. Для миллиардных потоков точность нереалистична.