단 하나의 해시로 블룸 필터 구현하기
원제 One Hash Bloom Filters
102 포인트댓글 11
Key Point
Bluesky 같은 대규모 시스템에서 블룸 필터의 실제 병목(스레드 경합)을 단일 해시로 해결한 사례로, 고성능 인프라 개선 시 이론만이 아닌 구체적인 최적화 기법을 배울 수 있다.
핵심 요약
- 블룸 필터는 '특정 키가 집합에 있는가'를 빠르게 판별하는 확률적 자료구조로, 작은 메모리로 높은 성능을 제공해 Bluesky 백엔드에서 데이터베이스 쿼리를 99% 줄이는 데 활용 중이다.
- 전통적 블룸 필터는 k개의 독립적 해시 함수를 사용하지만, 2008년 Kirsch와 Mitzenmacher의 논문에 따르면 단 2개 해시로도 동일한 오류율을 달성할 수 있다.
- Bluesky는 bits-and-blooms 라이브러리를 사용했으나 스레드 안전성 부족으로 뮤텍스 경합이 병목이 되어 배포 시간이 90분에 달했고, atomic-bloom으로 개선해 15분대로 단축했다.
- Lu et al. 논문의 기법을 바탕으로 단일 해시 블룸 필터(OHBF)를 개발했으며, k개의 서로소(coprime) 크기를 가진 파티션으로 나뉜 배열에서 hash%size_p로 각 파티션의 비트 위치를 계산한다.
- jcalabro/gloom이라는 Go 구현체를 Bluesky와 jetstream 동기화 서비스에 9개월간 배포 중이다.
- CPU 캐시 라인(64바이트)에 맞춰 블록으로 분할하고 unsafe를 사용해 캐시 정렬을 보장함으로써 최악의 경우 캐시 미스가 1회만 발생하도록 최적화했다.
- 모듈로 대신 단일 MUL 명령어로 블록을 선택하는 최적화와 여러 샤드에 쓰기를 분산해 경합을 줄이는 ShardedAtomicFilter를 구현했다.