Один хеш вместо нескольких: как Bloom-фильтры помогли Bluesky сэкономить миллионы запросов к базе

One Hash Bloom Filters

В бэкенде Bluesky Bloom-фильтры позволяют пропускать до 99% запросов к Scylla при проверке блокировок, мьютов и меток. Джим Калабро рассказывает, как переход на атомарные фильтры без мьютексов сократил время деплоя с 90 до 15 минут, а затем реализовал Bloom-фильтр с одним хешем (OHBF) на основе исследования Lu et al. Вместо k независимых хешей ключ хешируется один раз, а позиции битов вычисляются по модулю размеров взаимно простых партиций. Реализация gloom использует выравнивание по кэш-линиям и шардирование для минимизации конкуренции.