블룸 필터(bloom filter)는 "키 X가 이 집합에 들어 있는가?"라는 질문에 "확실히 없음" 또는 "아마도 있음" 중 하나로 답하는 확률적 자료구조다. 허용 가능한 오탐율(false positive rate)을 먼저 정한 뒤 키를 넣고, 나중에 존재 여부를 조회한다. 핵심 가치는 비용에 있다. 집합의 원소 수에 비해 적은 메모리를 쓰고 연산도 매우 저렴해서, 고성능 데이터 시스템에서 널리 쓰인다. 대표적인 쓰임새가 데이터베이스다. 행을 조회하기 전에 메모리에 올려둔 블룸 필터를 먼저 확인하면, 느린 디스크 IO를 상당 부분 건너뛸 수 있다.
짐 칼라브로(Jim Calabro)는 분산형 SNS 블루스카이의 백엔드에서 블룸 필터가 어떻게 쓰이는지를 구체적인 수치와 함께 설명한다. 블루스카이는 차단, 뮤트, 라벨 등을 조회할 때 블룸 필터로 ScyllaDB에 대한 초당 수백만 건의 질의를 절약한다. 예컨대 "사용자 X가 사용자 Y를 차단했는가"를 데이터베이스에 접근하지 않고도 답하는 경우가 많다. 공개한 수치에 따르면 어떤 필터의 양성 적중률은 약 1%로, 99%의 경우 데이터베이스 질의를 완전히 생략한다. 이는 사이트를 저렴하게 확장·운영하는 데 결정적이었다.
동작 원리와 해시 줄이기
구조 자체는 단순하다. 비트 배열 하나와 k개의 해시 함수로 이뤄진다. 배열 크기와 k는 미리 정하는데, 목표 오탐율에 맞게 작업 부하에 맞춰 적정 크기를 잡는 것이 관건이다. 키를 추가할 때는 k개의 해시를 돌려 나온 위치의 비트를 모두 1로 세팅한다. 조회할 때도 k번 해시해 각 위치를 확인한다. 하나라도 0이면 그 키는 들어온 적이 없는 것이고, 전부 1이면 "있을 수도 있다"는 뜻이다. 모든 비트가 우연히 1로 채워져 실제로는 없는 키를 있다고 판단하는 상황이 바로 오탐이다.
디스크 접근보다야 훨씬 싸지만, 키마다 k개의 독립 해시를 계산하는 것은 초고성능 시스템에서는 여전히 부담이다. 2008년 커시(Kirsch)와 미첸마허(Mitzenmacher)는 두 개의 해시만으로 같은 결과를 낼 수 있음을 보였다. i번째 위치를 (hash_1 + i*hash_2) % n으로 유도하면 k개의 독립 해시를 쓸 때와 사실상 동일한 오탐율이 나온다. 대니얼 르메르(Daniel Lemire)가 관리하는 Go 구현체 bits-and-blooms/bloom은 이 방식을 쓴다. 128비트 murmur3를 두 번 돌려 네 개의 64비트 값을 얻고, 이를 조합해 모든 비트 위치를 만들어낸다. 블루스카이도 오랫동안 이 라이브러리를 운영 환경에서 사용했다.
진짜 병목은 해시가 아니라 경합이었다
블루스카이의 운영 방식에서 흥미로운 교훈이 나온다. 각 프로세스는 시작할 때 차단·뮤트·리스트 항목 등을 통째로 읽어와 블룸 필터에 넣고, 동시에 atproto 파이어호스 소비자가 실시간으로 항목을 계속 삽입한다. 여기서 경쟁 상태(race condition)가 생긴다. bits-and-blooms는 내부적으로 스레드 안전하지 않아 모든 접근을 뮤텍스로 감싸야 했는데, pprof로 분석해보니 정작 프로세스 기동의 병목이 바로 그 뮤텍스 경합이었다. 한 번 배포를 전부 롤아웃하는 데 90분이 걸릴 정도였다.
동료 재스민(Jasmine)은 라이브러리를 포크해 atomic-bloom을 만들었다. 뮤텍스 대신 원자적(atomic) CPU 명령으로 같은 로직을 안전하게 수행하는 방식이다. 경합이 크게 줄면서 배포 시간은 90분에서 약 15분으로 떨어졌다. 여기서 주목할 점은, 해시 횟수를 더 줄이는 것이 블루스카이에 추가 이득을 주지는 않았다는 사실이다. 애초 문제는 해시 개수가 아니라 경합이었기 때문에, 암달의 법칙(Amdahl's Law)대로 체감할 만한 추가 속도 향상은 없었다. 성능 최적화에서 "무엇이 실제 병목인지"를 먼저 측정해야 한다는 전형적인 사례다.
한 번의 해시, 그리고 캐시 친화적 설계
그럼에도 저자는 더 파고들어, 루(Lu) 등이 제시한 단일 해시 블룸 필터 기법을 바탕으로 Go 구현체 jcalabro/gloom(OHBF)을 만들었다. 이 구현은 지난 9개월간 블루스카이 백엔드와 고성능 동기화 서비스 jetstream에서 안정적으로 돌아가고 있다. 단일 해시라는 점 외에도 저수준 최적화가 여럿 들어갔다. 먼저 필터를 CPU 캐시 라인 크기에 맞춰 64바이트 블록 여러 개로 쪼갠다. Go의 할당자가 블록을 캐시 정렬 상태로 보장하지 않기 때문에, 약간 초과 할당한 뒤 unsafe를 써서 정렬을 맞춘다. 이 둘을 합치면 최악의 경우에도 조회 한 번에 캐시 미스가 한 번만 발생하도록 보장된다.
르메르에게서 가져온 또 다른 기법은 블록 선택에 비싼 나눗셈(modulo) 대신 단일 MUL 명령을 쓰는 것이다. 마지막으로 ShardedAtomicFilter는 쓰기를 여러 백킹 필터 샤드에 분산해, 최고 사양 베어메탈 서버에서 여러 코어가 같은 데이터를 두고 다투는 경합 가능성을 낮춘다. 전체적으로 이 글은 화려한 알고리즘 교체보다 측정 기반의 병목 제거, 그리고 하드웨어 특성(캐시 라인, 정렬, 코어 간 경합)에 맞춘 세밀한 조정이 실제 운영 비용과 배포 속도를 좌우한다는 점을 보여준다. 다만 공개된 수치는 블루스카이의 특정 워크로드에 한정된 것이므로, 자신의 시스템에서 병목이 어디인지는 직접 프로파일링으로 확인해야 한다.