Фільтр Блума

«Геніальна структура даних»: імовірнісний тест належності до множини, що ніколи не дає false negatives і має настроювану частку false positives, — її розмір залежить лише від кількості елементів і цільового FPR, а не від розміру ключів. Віктор реалізує фільтр руками на JavaScript і бенчмаркає проти всього підряд: 10 млн ключів вміщаються у фільтр на 11 МБ при 1% FPR і відповідають на 100 000 пошуків за ~55 мс — проти ~800 МБ для JS Map, ~17 с на 100k для MySQL з індексом і ~6 с на 100k для Redis/Memcached. Математика тюнінгу драматична: подвоєння розміру фільтра купує 100x точності, а заниження розміру вдвічі деградує 1% FPR до ~15%. Його аналогія для колізій: фейсконтрольник у клубі, що памʼятає відвідувачів лише за одягом — того, кого бачив, він не пропустить ніколи, але двоє людей в однаковій куртці для нього ідентичні (фільтр Блума і Firefox).

Кульмінація — CRLite у Firefox: каскад із ~13 рівнів фільтрів Блума, кожен з яких тримає false positives попереднього рівня, — і це перетворює імовірнісний фільтр на детермінований бінарний класифікатор, доставляючи всі ~4 млн відкликаних TLS-сертифікатів кожному браузеру в ~300 КБ щоденних оновлень; у продакшені з 2025 року (а npm-бібліотеки для каскадного варіанта не існує). Реальні впровадження, які він наводить: CRM «Сільпо» на 25 млн клієнтів, де фільтр дає 0.1 мс замість 50 мс при 1000 RPS, Cassandra, списки Google Safe Browsing, RTB-системи реклами і класифікація преміум-користувачів. Анонсовані продовження: Counting Bloom Filter, Count-Min Sketch, HyperLogLog (фільтр Блума і Firefox).