이 글은 저 같은 사람들에게 딱 맞는 내용이라는 느낌. 이름은 들어봤지만 그때마다 찾아보려 하다가 계속 미뤘었음. 이번에 글을 보고 드디어 찾아봤는데, 내가 원하던 딱 그 입문서 같은 느낌
iBooks의 검색 기능 구현을 위해 Bloom filter를 처음 알게 되었던 경험. 벌써 10년이 넘은 이야기
Bloom filter는 정말 재미있음. 문제를 풀면서 Bloom filter가 필요할 때가 오면 정말 신나는데, 도메인에 따라 그런 상황이 적어 아쉬움
글쓴이에게 한 가지 제안 사항. 인터랙티브한 부분 아주 만족. Bloom filter의 특성을 더 잘 이해시키기 위해 두 문자열이 해시 충돌을 일으키는 예시를 주고 하나를 입력해보고, 다른 하나를 두 번째 입력창에 입력해보게 하면 좋겠음. 이렇게 하면 "집합 안에 있는지 확실하지 않고 아마도 있다(maybe)"라는 특유의 결과 논리가 왜 나오는지 쉽게 이해할 수 있음
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를 적용해서 만족도가 높았던 경험
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 등 다양한 아키텍처
Hacker News 의견