▲

블룸 필터 예제로 이해하기

 (llimllib.github.io)
2P by GN⁺ 7일전 | ★ favorite | 댓글 1개
  • 블룸 필터는 메모리 효율적으로 집합 내에 요소의 존재 여부를 빠르게 확인하는 확률적 자료구조임
  • 요소가 집합에 확실히 없는지, 또는 있을지도 모른다고만 알려주며, 가짜 양성의 확률이 존재함
  • 기본 구조는 비트 벡터와 여러 해시 함수를 사용하여 각 요소에 해당하는 비트를 1로 설정함
  • 필터 크기와 해시 함수 개수에 따라 오차율과 성능이 결정되며, 활용 용도에 맞게 조정 가능함
  • 추천 해시 함수 및 최적 설정 방법, 공간 효율성, 실제 적용사례 등도 소개됨

블룸 필터란 무엇인가

  • 블룸 필터는 특정 요소가 집합에 존재하는지 빠르고 메모리 효율적으로 판별하는 자료구조임
  • 이 효율성을 위하여 블룸 필터는 확률적 자료구조로, 검사 결과가 "집합에 확실히 없음" 또는 "집합에 있을 수도 있음"으로 나뉨
  • 블룸 필터의 핵심 구조는 비트 벡터임
  • 원소를 추가할 때 각 원소를 여러 번 해시해서 그 인덱스의 비트를 1로 설정함
  • 각 해시 함수별로 나온 인덱스에 해당하는 비트가 모두 1일 경우 "존재할 수도 있음"이라고 판별하고, 그렇지 않으면 "확실히 없음"으로 처리함

동작 원리 예시

  • 여러 개의 해시 함수(ex: Fnv, Murmur)를 통해 원소를 여러 개 비트 인덱스로 매핑함
  • 원소 추가 시 계산된 인덱스의 비트를 1로 변경함
  • 특정 원소의 존재 여부를 검사할 때, 같은 해시 함수와 동일한 방식의 인덱스가 모두 1이면 "존재할 수도 있음"으로 간주함
  • 만약 하나라도 해당 비트가 0이면 "집합에 없음"으로 확실히 판단 가능함
  • 이로 인해, 거짓 긍정(가짜 양성) 의 가능성이 생김

고급 주제

주의: 작성자는 실제로 대규모 서비스에 블룸 필터를 적용해 본 경험이 없음

해시 함수 선택

  • 독립적이고 균등 분포를 가지는 해시 함수가 권장됨
  • 암호학적 해시 함수(sha1 등)는 느리기 때문에 적합하지 않음
  • 빠르고 단순한 해시 함수 예시는: Murmur, xxHash, Fnv, HashMix 등임
  • 실제 사례에서는 md5에서 murmur로 변경 시 800% 이상 속도 향상을 경험함

블룸 필터의 크기 결정

  • 필터 크기(m) 가 클수록 거짓 긍정률이 줄어듦
  • 거짓 긍정률은 보통 (1-e^(-kn/m))^k으로 근사 가능함
  • 기대 원소 수(n), 필터 크기(m), 해시 함수 개수(k)를 적절히 정해야 함

해시 함수 개수는?

  • 해시 함수 수가 많을수록 속도가 느려지고 필터가 더 빨리 채워짐
  • 너무 적으면 거짓 긍정률이 높아짐
  • 이상적인 k는 *(m/n)ln(2)*로 계산됨
  • 설계시 다음 절차로 진행:
    • 기대 원소 수 n을 추정
    • 비트수 m을 정하고
    • 최적 k를 산출
    • 원하는 오차율이 나오는지 확인, 안 되면 m을 조절

성능 및 공간 효율

  • 블룸 필터에서 원소 추가/존재 검사는 O(k)의 시간 복잡도 가짐
  • 공간 효율성은 오차율 허용 범위와 원소 범위에 따라 결정됨
  • 원소 범위를 대략적으로나마 예측하지 못하면 해시 테이블이나 확장형 블룸 필터가 나을 수 있음

활용 사례

  • 자세한 활용예는 Wikipedia 참고
  • C. Titus Brown는 블룸 필터의 바이오인포매틱스 적용사례를 제시함

참고 자료

▲
GN⁺ 7일전  [-]
Hacker News 의견
  • 이 글은 저 같은 사람들에게 딱 맞는 내용이라는 느낌. 이름은 들어봤지만 그때마다 찾아보려 하다가 계속 미뤘었음. 이번에 글을 보고 드디어 찾아봤는데, 내가 원하던 딱 그 입문서 같은 느낌
    • iBooks의 검색 기능 구현을 위해 Bloom filter를 처음 알게 되었던 경험. 벌써 10년이 넘은 이야기
    • Bloom filter는 정말 재미있음. 문제를 풀면서 Bloom filter가 필요할 때가 오면 정말 신나는데, 도메인에 따라 그런 상황이 적어 아쉬움
  • 글쓴이에게 한 가지 제안 사항. 인터랙티브한 부분 아주 만족. Bloom filter의 특성을 더 잘 이해시키기 위해 두 문자열이 해시 충돌을 일으키는 예시를 주고 하나를 입력해보고, 다른 하나를 두 번째 입력창에 입력해보게 하면 좋겠음. 이렇게 하면 "집합 안에 있는지 확실하지 않고 아마도 있다(maybe)"라는 특유의 결과 논리가 왜 나오는지 쉽게 이해할 수 있음
    • 예시로 "bloom"과 "demonstrators "(마지막 공백 포함)가 fnv: 7, murmur: 12에서 충돌함
  • 2009년 대학 시절 CUDA로 Bloom filter를 구현한 경험. 지도교수님이 전 Nvidia 출신이었음. 그런데 커리어에선 GPU 프로그래밍과 전혀 상관없는 길로 감. 다른 선택을 했더라면 1억 달러를 벌 수 있었을지도 모르겠다는 생각
    • 1970년에 나온 컴퓨터 과학 아이디어라 불가능했을 거라는 생각. GPGPU 관련 아이디어는 이미 충분히 연구된 느낌. 나도 GPU로 Hashcash 구현을 10년 전에 했는데, 지금 봐선 가치가 0에 가까움
    • 대학 졸업 프로젝트로 머신러닝 알고리즘을 CUDA로 포팅한 뒤, 별 일 아니라는 생각으로 임베디드 프로그래밍으로 진로 전환
    • 나도 비슷한 경험. 2009년 GeForce 8과 CUDA v1(!)로 GPU 최적화된 바이오인포매틱스 툴킷을 아마 최초로 만들었던듯. 그냥 호기심으로 만든 뒤엔 완전히 다른 길로 갔고, 큰 돈을 벌 찬스를 놓침
    • 비트코인을 샀더라면 더 큰 돈을 벌 수 있었을 것이라는 농담 섞인 말
  • 내가 좋아하는 트릭이 있음. 원소 개수가 적을 수도 있고, 멤버십 체크를 자주 하게 되는 작은 set에 대해, 64비트 Bloom filter를 아주 간단한 해시 함수와 함께 넣어두는 방식. 바보 같아 보여도, 비용이 너무 낮아서 일종의 도박처럼 써볼 수 있음. 안 맞아도 멤버십 체크나 insert에서 10ns정도만 추가되고 그만이지만, 잘 맞을 때는 엄청난 작업량을 줄일 수 있음
    • Chromium도 곳곳에 이런 트릭을 사용. 글에는 Safe Browsing만 언급되지만, Blink 레이어에선 rapidhash와 이런 마이크로-필터를 적극적으로 씀. 예시로 querySelector(), CSS 버킷에서 해시 룩업 사전필터, 접근성 위해 Aria 속성 탐색에서 rapid reject 등. 32비트, 64비트 작은 filter도 실제로 잘 동작함. 더 큰 Bloom filter도 적절히 활용, 나도 이런 기능을 직접 추가했습니다
  • 최근 로그 메시지 안티-스팸 기능에 Bloom filter를 활용한 경험. 로그 메시지를 해싱해서 filter에 넣고, 이미 filter에 있으면 출력하지 않음. 주기적으로 filter의 비트를 싹 지움. 원자적으로 비트 전체를 클리어할 필요 없이, 메시지가 들어오면서 일부 비트가 지워졌어도 로그가 다시 찍힘. 이전엔 메시지별 카운트를 따로 유지했지만, 이 방식이 훨씬 효율적이었음. 실제로 직접 이 용도에 Bloom filter를 적용해서 만족도가 높았던 경험
  • Bloom filter 시각화 예시로 이 페이지 마지막 부분에 좋은 자료가 있음
  • Eli Bendersky가 쓴 또 다른 Bloom filter 입문글을 추천. 더 자세히 알고 싶으면 여기 참고
  • Bloom filter, set, 해시테이블을 이해하는 데 필요한 개념이 거의 95%는 겹친다는 생각. set은 key만 신경 쓰는 해시 테이블이고, Bloom filter는 해싱의 충돌 특성을 적극적으로 이용하는 set임. 일부러 충돌이 잘 일어나도록 만든 해시함수 사용. 특정 key가 들어간 적이 있다면 무조건 맞아떨어짐. 하지만 같은 해시값을 만든 다른 key가 있을 수 있음. 그래서 이건 버그가 아니라 의도한 특성
    • 나도 Bloom filter를 해시테이블에서 데이터 자체는 빼고, 버킷만 추적하는 방식처럼 생각하는 편. 이런 마인드셋을 가진 사람이 나만이 아니라서 반가움
    • Bloom filter가 충돌을 줄이기 위해 여러 개의 해시함수를 쓴다는 부분이 추가로 보완되면 좋을 듯. 예를 들어 3개의 해시함수가 모두 맞아야 set에 있다고 판단. 이런 구조 덕분에 false positive 확률은 낮추면서 false negative는 절대 안 나옴
    • Bloom filter를 이해했다면, 랜덤 프로젝션이나 Locality Sensitive Hashes의 일부 구현도 곧 이해가 가능
  • Cassandra read spike 디버깅 중 Bloom filter 활용에 깊이 빠졌던 경험. 존재하지 않는 key임에도 sstable 조회가 너무 많아서 이상했음. sstable마다 붙는 Bloom filter의 의미를 뒤늦게 파악. 기본 false positive 비율이 0.1이라서 우리 상황엔 너무 높았음. 대부분 cache miss였고 false positive 때문에 무의미한 조회가 너무 많았음. 비율을 0.01로 낮췄더니 메모리 사용은 소폭 늘었지만 쓸데없는 read가 크게 줄어서 p99 read latency가 16~18%나 줄었음
  • Bloom filter를 정말 좋아함. 기술 이야기할 때 꼭 알려주는 세 가지 핵심 개념이 Bloom filter, Random Weight Hashing(Rendezvous Hashing, Highest Random Weight Hashing), 그리고 Cumulative flow diagram임. 이 세 개념이 복잡한 분산 시스템 운영에 필수적이라는 생각
    • 분산 해시 테이블 구조도 동일하게 중요한 주제라는 생각. 예를 들어 circle, chord, CAN, kademlia 등 다양한 아키텍처
답변달기