해시 한 번으로 만드는 블룸 필터

AI 요약

블룸 필터(Bloom filter)는 집합에 특정 키가 있는지 빠르게 확인하는 확률적 자료구조입니다. 결과는 "없음" 또는 "있을 가능성이 있음"으로 나뉘며, 거짓 양성률(false positive rate)을 정해 메모리 사용량과 정확도를 맞춥니다. Bluesky는 차단, 뮤트, 라벨 등의 조회에 블룸 필터를 써서 Scylla 데이터베이스 질의를 줄입니다. 한 사례에서는 필터가 약 1%의 양성률을 보여 데이터베이스 질의의 99%를 건너뛰었습니다.

잠금 경합을 줄인 과정

전통적인 블룸 필터는 비트 배열과 k개의 해시 함수를 씁니다. 키를 추가할 때 해시 함수마다 계산한 위치의 비트를 켜고, 조회할 때 해당 비트가 모두 켜져 있으면 키가 있을 가능성이 있다고 판단합니다. Kirsch와 Mitzenmacher는 2008년 논문에서 두 해시값으로 k개의 위치를 계산해 독립 해시 k개를 쓰는 경우와 사실상 같은 거짓 양성률을 얻는 방법을 보였습니다. 식은 (hash_1 + i * hash_2) % n입니다.

Bluesky는 Go 라이브러리 bits-and-blooms/bloom을 사용했지만, 라이브러리가 스레드 안전하지 않아 접근마다 뮤텍스를 걸어야 했습니다. 프로세스 시작 중 데이터베이스에서 기존 항목을 읽어 필터를 채우는 작업과 atproto firehose에서 새 항목을 넣는 작업이 동시에 일어나 경합이 생겼습니다. 프로파일링 결과 뮤텍스 경합이 프로세스 배포의 병목이었습니다. 동료 Jasmine은 CPU 원자 연산을 사용하는 atomic-bloom을 만들어 잠금 없이 같은 작업을 처리했습니다. 그 결과 배포 시간이 90분에서 약 15분으로 줄었습니다.

해시 한 번으로 위치 계산하기

글쓴이는 Lu 등의 논문을 바탕으로 단일 해시 블룸 필터(one-hash Bloom filter)를 구현했습니다. 하나의 비트 배열을 k개의 파티션으로 나누고 파티션마다 서로소인 크기를 지정합니다. 키를 한 번 해시한 뒤 각 파티션에서 hash % size_p로 위치를 고릅니다. 파티션마다 크기가 달라 하나의 해시값으로도 서로 다른 k개 위치를 얻습니다. Go 구현체 gloom은 Bluesky 백엔드에서 9개월간 사용됐고, 동기화 서비스 jetstream에서도 쓰입니다.

구현은 xxh3의 128비트 해시 결과를 나눠 사용합니다. 상위 64비트로 블록을 고르고 하위 64비트를 블록 안의 위치 계산에 씁니다. 필터는 흔한 CPU 캐시 라인 크기에 맞춰 64바이트 블록으로 나눕니다. Go 메모리 할당기가 캐시 정렬을 보장하지 않으므로 메모리를 조금 더 할당한 뒤 unsafe를 써 정렬합니다. 글쓴이는 두 기법으로 최악의 경우 조회 한 번에 캐시 미스 한 번만 발생한다고 설명합니다. 블록 선택에는 나눗셈이 필요한 나머지 연산 대신 곱셈 명령 하나를 사용하는 최적화도 적용합니다. ShardedAtomicFilter는 쓰기를 여러 필터 샤드로 분산해 코어 간 경합을 줄입니다.

다만 글쓴이는 Bluesky에서 병목은 해시 함수 개수가 아니라 잠금 경합이었으며, 단일 해시 방식으로는 눈에 띄는 추가 속도 향상을 얻지 못했다고 밝힙니다. 단일 해시 구현은 성능 탐구의 결과이자 실제 서비스에서 운영 중인 구현이지만, 원문에는 기존 방식과의 직접 성능 비교 수치가 없습니다.

Lobsters 반응

• @subnut — 링크는 아마 https://www.calabro.io/ohbf 여야 했습니다.
  • @pushcx — 네, 고맙습니다. 잘못된 rel=canonical 태그를 저자에게 이메일로 알리겠습니다.
  • @jcalabro — 수정했습니다. 고맙습니다!
• @neilmadden — Kirsch와 Mitzenmacher의 기법은 Google Guava에서 처음 알았습니다. 흥미롭게도 Guava도 Murmur-128을 쓰지만 처음 64비트만 가져와 논문에 나온 방식으로 32비트 해시 두 개로 나눕니다. 저도 그 아이디어를 바탕으로 Murmur 대신 SipHash를 쓰는 구현을 몇 가지 만들었습니다. 하나는 유출이 확인된 비밀번호를 빠르게 조회하는 메모리 매핑 방식이고, 다른 하나는 JWT 로그아웃용입니다. BBC에서 대규모 사용량을 예상해 2016년에 쓴 글에 설명했는데 지금도 쓰는지는 모르겠습니다.
• @dbath — 링크된 논문은 k개의 해시 함수와 나머지 연산을 쓰는 방식을 "표준 블룸 필터"라고 설명합니다. 간단한 블룸 필터를 만든다면 비트 배열 크기를 2의 거듭제곱으로 정해 나머지 연산 대신 비트 마스크를 쓰겠습니다. 유연성은 떨어지지만 메모리 크기를 아주 정밀하게 맞춰야 하는 경우가 아니라면 괜찮을 것 같습니다. 해시 함수 하나의 출력을 나누고 마스크를 씌워 k개의 해시를 만들 수도 있습니다. 예를 들어 64비트 해시에서 21비트 값 세 개를 얻거나, 추가 비용 없이 128비트 이상을 내는 해시 함수를 쓸 수 있습니다. 좋은 해시 함수라면 각 위치도 서로 다른 해시 함수처럼 독립적이어야 합니다. 이 방식이 관련 연구나 논문 뒷부분에 나오는지는 모르겠지만, "해시 한 번 블룸 필터"를 만드는 일은 간단해 보입니다. 이 단순한 방식이 실제로 작동하지 않는 이유가 있을까요?
• @gkoos — 이런 내용이 정말 좋습니다. 수학적 아이디어와 캐시 지역성, 동시성 최적화를 함께 다루는 점이 흥미롭습니다. 개선 효과 중 단일 해시 방식과 캐시 라인 블로킹, 경합 감소가 각각 얼마나 기여했는지 궁금합니다. 같은 메모리 예산과 거짓 양성률로 기존 이중 해시 필터와 블록형 블룸 필터를 비교하면 좋겠습니다. 필터 크기가 L3 캐시 안팎일 때와 쓰기 부하가 달라질 때도 보고 싶습니다.

원문: Calabro.io / 번역·요약: Trawling