요약
블룸 필터는 해시를 한 번만 계산해도 여러 해시를 쓴 것처럼 동작하게 만들 수 있습니다.
블루스카이 개발자 짐 칼라브로가 Go 언어로 만든 블룸 필터 라이브러리 gloom을 소개했습니다. 블룸 필터는 어떤 값이 집합에 없으면 확실히, 있으면 '아마도'라고 답하는 작은 자료구조입니다. 블루스카이는 이것으로 차단·뮤트·라벨 조회 때 데이터베이스 조회를 대부분 건너뜁니다.
왜 중요한가
- 키마다 해시를 여러 번 계산하던 비용을 한 번으로 줄여, 초당 수백만 건을 거르는 시스템의 부담을 덜 수 있습니다.
- 블루스카이에서는 이 기법으로 체감할 만한 개선이 없었고, 잠금 경합(스레드들이 잠금을 두고 서로 기다리는 현상)을 없앤 것이 훨씬 큰 효과를 냈습니다.
핵심 내용
- 비트 배열을 크기가 서로소(1 말고는 공약수가 없는 수)인 k개 구획으로 나누고, 해시값을 각 구획 크기로 나눈 나머지를 비트 위치로 씁니다.
- 루 등(Lu et al.)의 논문에서 가져온 방법으로, 해시 두 개로 k개를 흉내 내는 기존 이중 해싱을 한 개로 더 줄였습니다.
- 블록을 CPU 캐시 라인 크기인 64바이트에 맞춰, 조회 한 번에 캐시 미스가 많아야 한 번만 나게 했습니다.
- 앞서 기존 라이브러리의 뮤텍스(한 번에 한 스레드만 들어가게 하는 잠금)를 원자적 연산으로 바꾸자 배포 시간이 약 90분에서 15분으로 줄었습니다.
- gloom은 약 9개월째 블루스카이 백엔드와 동기화 서비스 Jetstream에서 쓰이고 있습니다.
HN 반응
- MurmurHash를 만든 개발자 등은 서로소 구획 없이도 해시값을 조금씩 섞거나 64비트 해시의 비트를 나눠 쓰면 된다고 했습니다.
- 64바이트 블록으로 나누면 블록마다 채워지는 정도가 달라 공간 효율이 떨어진다는 지적에, 속도를 얻으려는 절충이라는 설명이 뒤따랐습니다.
사실 굳이 이렇게 하지 않아도 됩니다. 2의 거듭제곱 크기 테이블을 그대로 쓰면서, 해시 값을 살짝 섞어 추가 비트 인덱스를 하나씩 얻으면 됩니다.
(출처: 제가 MurmurHash/SMHasher를 만들었고, 제 블룸 필터와 쿠쿠 해시 테이블에도 위 방식을 써 왔습니다)
해시 하나만 쓰는 방식이 기술적으로는 더 나아야 합니다.
다만 서로소 분할과 그로 인해 블록 분할에서 생기는 준상관(semi-correlated) 순열 문제를 피하면서, 그 과정에서 해시 충돌도 피할 수 있을 것 같습니다.
이런 식인가요? 64비트 해시에서, 64바이트 캐시 라인의 모든 비트를 가리키려면 9비트가 필요하니까, 64비트 해시 하나에서 캐시 라인 안의 비트를 가리키는 해시 함수 7개를 뽑아낼 수 있다는 거죠?
맞아요. 완전한 독립성까지는 필요 없어요. 일부 겹치는 비트를 써도 반쯤 독립적인 해시를 얻을 수 있거든요.
참고로 여기서는 상당한 공간 효율을 내주고 있고, 오탐률을 낮출수록 그 손해가 더 커집니다. 분할하면 파티션마다 점유율이 고르지 않게 됩니다. 그러면 낮은 점유율을 받아들이거나(필터 전체 크기가 커집니다), 핫 블록이 생기는 걸 사실상 피할 수 없게 됩니다(특정 파티션의 오탐률이 올라갑니다).
캐시 라인 크기의 블록으로 분할하는 걸 보면, 시간과 공간을 맞바꾸려고 분할한 것 같은데요?
[edit]
그 부분을 더 꼼꼼히 다시 읽어 보니, 블룸 필터에 동시에 쓸 때의 성능이 걱정이었던 거네요. CPU 두 개가 같은 캐시 라인에 병렬로 쓸 수는 없으니, 성능 때문에 한 게 틀림없어요.
속도 최적화가 맞습니다. 쓰기보다는 읽기 쪽 효과가 더 크지만요. 64바이트 캐시 라인 단위로 나누는 건 표준적인 블록 블룸 필터(blocked Bloom filter)입니다. 여기에 SIMD 질의를 더하면 이런 구조로 낼 수 있는 속도는 거의 최대입니다.
트레이드오프의 반대편에는 bumped ribbon retrieval이 있습니다. 블록 블룸 필터는 BuRR보다 약 50% 더 큽니다.
지금 설명하신 건 "블록(blocked)" 블룸 필터입니다(즉 k개의 해시 함수를 해시로 먼저 고른 단일 블록 안에서 계산하는 방식). "파티션(partitioned)" 블룸 필터(즉 각 해시 함수를 별도의 파티션에서 계산하는 방식)에는 말씀하신 불균형 문제가 없습니다.
저는 글에 나온 자료구조를 설명한 겁니다. 이 구조는 두 번 분할됩니다. 먼저 64바이트로, 그다음 서로 쌍마다 서로소인 크기의 조각으로 나눕니다. 말씀하신 "블록"이 64바이트 조각이고, "파티션"이 서로소 크기의 조각입니다. 제가 말한 공간 비효율은 64바이트 조각에 해당하는 이야기입니다.
디스크에 가는 것보다야 훨씬 싸지만, 키마다 k개의 독립적인 해시를 계산하는 것은 초고성능 시스템에서는 여전히 좀 비싸다.
블룸 필터가 얼마나 크냐에 달렸죠. 대부분의 해시는 크고, 그 비트들은 서로 독립적이니까요.
Gnutella와 Gnutella2는 단일 해시 블룸 필터 비슷한 것을 써서, P2P 파일 질의를 메시 전체에 덜 낭비적인 방식으로 라우팅했습니다. 완벽하진 않았지만, 아주 많은 사용자 수까지 확장될 만큼은 충분히 동작했습니다.
https://rickcarlino.com/notes/p2p/how-gnutella-scaled-to-handle-query-traffic.html
단일 해시 논문은 처음 봤습니다. 미첸마허(Miztenmacher)의 방식을 정말 멋지게 최적화했네요. 입력 크기별 벤치마크 수치를 공유해 주실 수 있나요?
논문과 코드를 더 읽어 봐야겠지만, (새 크기가 필터 용량을 넘지 않는 한) 필터 병합도 지원하기에 알맞은 구조로 보입니다.
이걸 블록 블룸 필터나 binary fuse 필터와 비교해서 벤치마크해 본 사람 있나요?
좋은 글이네요!