분산 스트리밍 환경의 원소 판별 트릭: 블룸 필터(Bloom Filter)와 카운트-민 스케치 확률론의 위력

대용량 유저의 이벤트 로그를 실시간으로 밀어 넣는 카프카 커슈머 파이프라인에서 "이 유저가 오늘 광고를 본 적이 있는가?"라는 단순한 중복 판별 캐시를 올리려다, 레디스 클러스터 호스트 메모리가 1테라바이트를 초과하여 파산할 뻔한 무시무시한 비용 설계 위기가 있었습니다. 정확성(100%)을 포기하는 대신 공간 복잡도 효율을 수천 배로 구원하는 차원 축소의 마법이 바로 '확률적 자료 구조(Probabilistic Data Structure)' 분야입니다. 그중 정점인 블룸 필터(Bloom Filter)는 거대한 비트(Bit) 배열 캔버스와 여러 개의 독립된 해시 함수들을 잉크 삼아 구현됩니다. 유저의 아이디가 인입될 때마다, 3~4개의 해시 암호 모듈이 그 아이디를 전혀 다른 숫자 좌표로 반환하고 해당 비트맵 보드의 전구들을 1(On)로 켭니다. 이후 방문 여부를 조회할 때는 동일한 해시 좌표의 전구들이 모두 불이 켜져 있는지 확인하면 그만입니다. 만일 단 하나라도 꺼져있다면 이 유저는 "단언컨대 100% 확률로 접근한 적이 없다"라고 오판 없이 단호히 증명할 수 있습니다. 반면 모두 불이 켜져 있다면 "아마도 방문했을 것이다"라는 근사 판정을 내리게 됩니다 (False Positive). 비록 다른 유저들의 해시가 우연히 겹쳐 거짓 양성 반응이 나올 확률이 1% 이하로 존재하지만, 1TB의 램 메모리를 낭비하는 대신 단 5MB 짜리 비트맵 공간만으로 수억 명의 일일 중복 필터링을 방어할 수 있었던 압도적 가성비는 이루 말할 수 없었습니다. 현대의 대규모 추천 시스템이나 스팸 방어 프레임워크들은 이 확률적 오차를 비즈니스 도메인 내의 허용 가능한 리스크로 흡수하며, Count-Min Sketch 등의 변형된 무기들을 탑재해 실시간 빅데이터 스트림 파이프라인의 아키텍처적 불가능성을 철저한 확률 수학의 힘으로 기만하고 있다는 것을 깊숙이 체감할 수 있었습니다.