Геніальна структура даних й як її покращив Firefox

Головне

• Драбина бенчмарків для «чи є ключ у множині?» на 10 млн ключів: JS Map у пам'яті блискавично швидкий, але файл даних на 219 МБ роздувається до ~800 МБ пам'яті процесу; MySQL без індексу — ~18 с лише на 10 промахів (повне сканування); з індексом ~17 с на 100 000 запитів; Redis ~6 с на 100 000; фільтр Блума робить 100 000 перевірок за ~55 мс в 11 МБ RAM — про індексний бік цієї історії див. індекси в базах даних.
• Фільтр Блума ніколи не дає хибнонегативних відповідей — «якщо він каже, що ключа немає, то його немає на 100%», — але має настроюваний рівень хибнопозитивних. Його розмір залежить лише від кількості елементів і цільового FPR, і ніколи — від довжини ключа; довгі URL хешуй і зберігай відбиток (хешування).
• Розмін «точність/розмір» асиметричний і прекрасний: перехід від 1% до 0.01% FPR (у 100 разів точніше) збільшив фільтр лише з 11 МБ до 22 МБ. Але заниження розміру б'є так само: виділи під 5 млн елементів, а вклади 10 млн — і FPR стрибає з 1% до ~15%.
• Його аналогія: викидайло в клубі, який не пам'ятає облич забанених — лише чекбокси їхнього одягу (жовті кросівки, червона шапка…). «Червоної шапки не бачив» → точно пускаємо; але хтось у шапці одного забаненого і взутті іншого отримує хибне спрацювання — це колізія хешів, і додавання атрибутів (розмір, бренд = більше бітів/хеш-функцій) зменшує частку хибнопозитивних.
• Трюки реалізації: бітовий масив, запакований у Uint32Array; швидкий xxHash — порахуй один 64-бітний хеш, розріж його на дві 32-бітні половини h1 і h2, і виводь будь-яку кількість хеш-функцій як h1 + i*h2 (математично доведена схема подвійного хешування), тож k хешів коштують приблизно як один. Наївні хеші типу «сума кодів символів» провалюються, бо ніколи не дотягнуться до дальнього краю масиву на 10 млн бітів — потрібен рівномірний розподіл.
• Ідея каскаду у Firefox: поклади весь 1 млн відкликаних («поганих») сертифікатів у фільтр №1; прожени крізь нього всі 9 млн хороших, збери ~1% хибнопозитивних у фільтр №2; його хибнопозитивні йдуть у фільтр №3… ~13 рівнів, поки не лишиться жменька винятків. Результат: детерміністичний бінарний класифікатор (classify() замість has()), FPR рівно 0 у його бенчмарку, і 1 млн відкликаних із 10 млн ключів вміщаються в ~1 МБ. Це «як машинне навчання, тільки без генералізації». Працює всюди, де повний простір ключів можна перелічити.
• Практичні застосування, які він наводить: перевірка доступності юзернейма/email без походу в базу; списки шкідливих URL у стилі Google Safe Browsing (лише ~1 із 10 000 відвідувань потребує звернення до сервера при 0.01% FPR); нутрощі Cassandra; системи real-time bidding, що рахують покази реклами на сотнях тисяч RPS; класифікатор преміум/безкоштовних користувачів (10 млн користувачів, 1 млн преміум → структура на ~1 МБ, оновлювана маленькими дельтами, як щоденні 30–50 КБ у Firefox); і свіжий пост українського ритейлера «Сільпо», чия CRM на 25 млн клієнтів використовує фільтр Блума для перевірок за 0.1 мс замість 50 мс — «дрібниця? на 1000 RPS вона вирішує все».
• Тизери для допитливих: Counting Bloom Filter, Count-Min Sketch, HyperLogLog (приблизна потужність множини); атаки колізіями на хеш-таблиці (стара вразливість Python) заслуговують окремого відео; колись він читав доповідь про те, як топологічне сортування врятувало JS-таблицю, а багато з цих алгоритмів вивчив, готуючись до співбесіди в Google.