블루스카이 개발자가 디비 부하 99% 줄인 블룸 필터 최적화 썰

요약 블루스카이(Bluesky) 엔지니어 짐 칼라브로(Jim Calabro)가 블로그를 통해 블룸 필터(Bloom Filter)를 활용해 대규모 백엔드 트래픽을 처리하고 성능을 끌어올린 기술적 경험을 공유했습니다. 블룸 필터는 특정 데이터가 집합에 존재하는지 빠르게 확인해 주는 확률적 자료구조로, '절대 없음' 또는 '있을 가능성 높음'이라는 답을 제공합니다. 데이터베이스 디스크 접근을 거치지 않고 메모리 상에서 판별할 수 있어, 블루스카이에서는 사용자 차단, 뮤트, 라벨링 확인 등에 활용해 Scylla DB로 향하는 초당 수백만 건의 쿼리를 절감하고 있었습니다. 실제로 긍정 적중률이 1% 수준에 불과해 전체 요청의 99%는 DB 접근 없이 메모리 수준에서 거를 수 있었다고 합니다. 기존 블룸 필터는 여러 번의 독립 해시 연산이 필요해 연산 비용이 드는데, 이를 보완한 것이 2개의 해시만 사용하는 '더블 해싱(Double Hashing)' 기법입니다. 블루스카이 역시 Go 언어 기반 라이브러리를 사용해 왔으나, 프로세스 시작 시 대량의 데이터를 로딩하면서 뮤텍스 락 경합(contention)이 심각하게 발생했습니다. 이 때문에 단 한 번의 배포 작업에 무려 90분이 소요되는 병목 현상을 겪었습니다. 동료 엔지니어가 CPU 원자적(atomic) 명령어를 적용한 라이브러리로 대체하자 배포 시간은 15분으로 대폭 단축되었습니다. 나아가 연구 논문을 통해 해시 함수를 단 한 번만 계산하는 '단일 해시 블룸 필터(One Hash Bloom Filter)' 기법을 접하게 되었고, 이를 구현한 Go 라이브러리 gloom을 직접 개발했습니다. 이 방식은 비트 배열을 서로소(pairwise coprime) 크기를 갖는 k개의 파티션으로 나눈 뒤 한 번의 해시값에 모듈러 연산을 적용해 비트 위치를 도출합니다. 저자는 블루스카이의 경우 주요 병목이 락 경합이었기에 단일 해시 도입으로 드라마틱한 체감 속도 향상이 더 나타나지는 않았지만(암달의 법칙), gloom 라이브러리는 9개월 동안 프로덕션과 데이터 동기화 서비스(Jetstream)에서 안정적으로 구동 중이라고 밝혔습니다.