단 하나의 해시로 블룸 필터 구현하기
Key Point
Bluesky 같은 대규모 시스템에서 블룸 필터의 실제 병목(스레드 경합)을 단일 해시로 해결한 사례로, 고성능 인프라 개선 시 이론만이 아닌 구체적인 최적화 기법을 배울 수 있다.
핵심 요약
- 블룸 필터는 '특정 키가 집합에 있는가'를 빠르게 판별하는 확률적 자료구조로, 작은 메모리로 높은 성능을 제공해 Bluesky 백엔드에서 데이터베이스 쿼리를 99% 줄이는 데 활용 중이다.
- 전통적 블룸 필터는 k개의 독립적 해시 함수를 사용하지만, 2008년 Kirsch와 Mitzenmacher의 논문에 따르면 단 2개 해시로도 동일한 오류율을 달성할 수 있다.
- Bluesky는 bits-and-blooms 라이브러리를 사용했으나 스레드 안전성 부족으로 뮤텍스 경합이 병목이 되어 배포 시간이 90분에 달했고, atomic-bloom으로 개선해 15분대로 단축했다.