80% запросов — это вопросы о том, чего нет. Bloom filter сократил кластер Cassandra на 60%
Most lookups are for things that don't exist
Сервис проверял, встречался ли хеш файла раньше, и держал для этого кластер Cassandra на несколько миллионов запросов в секунду. Оказалось, что четыре из пяти обращений возвращают «не найдено», и именно промахи, а не попадания, создавали нагрузку: координатор, fan-out по репликам, проверка всех SSTable. Кэш промахов бесполезен — такие хеши почти не повторяются. Автор поставил перед Cassandra Bloom filter в Redis: фильтр может ошибиться только в сторону лишнего похода в кластер, но никогда не ответит «нет» о том, что у него есть. Кластер уменьшился на 60%.
Он может ошибаться только в одну сторону: сказать «возможно» о хеше, которого у нас нет, — это стоит одного запроса и всё равно даёт верный ответ. Ошибиться в другую сторону он не может.