59. 블룸 필터 (Bloom Filter)

⚠️ 이 문서는 빅데이터나 NoSQL 데이터베이스(Cassandra, HBase) 환경에서 1억 개의 데이터가 들어있는 거대한 디스크 파일을 매번 무식하게 다 뒤져서 "홍길동이 있냐?"를 확인하느라 낭비되는 막대한 디스크 I/O를 없애기 위해, 메모리에 올려둔 아주 얇은 비트(Bit) 배열만 훑어보고 "여기 홍길동이 '절대 없음'을 100% 보장"하여 헛수고(디스크 접근)를 막아주는 기발한 확률적 자료구조인 블룸 필터를 다룹니다.

핵심 인사이트 (3줄 요약)

  1. 본질: 데이터 자체를 저장하지 않고 0과 1로 된 수만 개의 스위치 배열(Bit Array)만 둔다. 데이터가 들어올 때 여러 개의 해시 함수를 거쳐 스위치 여러 개를 '1(켜짐)'로 켜두어 데이터가 들어온 '흔적'만 남겨두는 방식이다.
  2. 가치: "홍길동 있냐?"고 물었을 때 필터가 "없다"고 하면 100% 확실하므로 헛되이 디스크를 뒤질 필요가 없어져 탐색 속도가 미친 듯이 빨라진다. 반면 "있다"고 하면 진짜 있을 수도 있고 억울하게 우연히 스위치가 겹친 것(긍정 오류, False Positive)일 수도 있으므로 그때만 디스크를 열어 확인한다.
  3. 기술 체계: 거짓말(긍정 오류) 확률을 1% 이하로 낮추려면 스위치 판(Bit Array)의 크기를 키우거나 해시 함수의 개수를 적절히 튜닝해야 하며, 한 번 켜진 스위치는 절대 끌 수 없으므로 '삭제(Delete)' 기능이 불가능하다는 치명적 제약이 있다.

Ⅰ. 거대 디스크 검색의 고통과 랜덤 I/O

디스크를 한 번 여는 것은 메모리를 10만 번 여는 것보다 비싸다.

  1. LSM 트리의 읽기 패널티 (Read Amplification):
    • 카산드라(Cassandra) 같은 분산 DB는 쓰기를 빨리하기 위해 수천 개의 SSTable 파일(파편화된 블록)을 디스크에 계속 찍어낸다.
    • 사용자가 SELECT * FROM users WHERE name='홍길동'을 날렸다. DB는 홍길동이 최신 파일 1번에 있는지, 옛날 파일 100번에 있는지 모른다. 결국 1번부터 100번까지 디스크 파일을 하나하나 다 열어서 찾아야 하는 끔찍한 병목(랜덤 I/O)이 발생한다.
  2. 블룸 필터의 도입 (골키퍼 배치):
    • 파일 100개를 열어보는 짓을 막기 위해, DB는 파일 100개 각각의 앞에 '블룸 필터'라는 문지기를 메모리(RAM)에 세워둔다.
    • 이 문지기는 단 몇 메가바이트(MB)밖에 안 되어 메모리에 상주하며, 디스크를 열어젖히기 전에 **"야, 이 파일 안에 홍길동 무조건 없어! 헛수고하지 말고 닫고 다음 파일로 가!"**라고 0.01초 만에 알려준다.

📢 섹션 요약 비유: 아파트 100동을 뒤져서 홍길동을 찾아야 하는데 건물마다 일일이 문을 따고 들어가 방을 다 뒤지면(디스크 스캔) 평생이 걸립니다. 블룸 필터는 각 동의 경비 아저씨입니다. 경비 아저씨가 명부를 보고 "우리 동엔 홍길동 절대 안 살아!"라고 외치면, 우리는 그 건물에 들어갈 필요 없이 바로 다음 동으로 넘어가 탐색 시간을 1/100로 줄이는 원리입니다.

Ⅱ. 블룸 필터의 수학적 원리 (스위치 켜기)

단 1바이트도 낭비하지 않는 극한의 공간 효율성을 자랑한다.

  1. 데이터 저장 (Bit 켜기):
    • 10개의 전구(0부터 9번 비트)가 꺼진 상태(0)로 있다.
    • '홍길동'을 저장할 때, 각기 다른 해시 함수 3개에 넣었더니 2, 4, 7이라는 결과가 나왔다. 그러면 2번, 4번, 7번 전구를 '1'로 켠다. 데이터 원본 글자는 버린다.
    • 다음 '이순신'을 해시했더니 4, 8, 9가 나왔다. 4번은 이미 켜져 있으니 두고 8번, 9번 전구를 켠다.
  2. 데이터 검색 (Bit 검사):
    • "임꺽정 있냐?" -> 해시했더니 1, 4, 5가 나왔다. 1번과 5번 전구가 꺼져(0) 있다. 결론: "임꺽정은 과거에 절대 들어온 적이 없다. 100% 확신!"
    • "홍길동 있냐?" -> 해시했더니 2, 4, 7이 나왔다. 세 전구가 모두 켜져 있다. 결론: "아마도 있을 것 같다(Probably in set)."
  3. 긍정 오류 (False Positive)의 발생:
    • 한 번도 들어온 적 없는 '유관순'을 찾는다. 해시했더니 우연히 2, 8, 9가 나왔다. 공교롭게도 이 세 전구는 홍길동과 이순신 때문에 이미 다 켜져 있다!
    • 필터는 "유관순 아마도 있어!"라고 거짓말을 한다(긍정 오류). 이 말을 믿고 헛되이 디스크를 열어보니 없었다. (약간의 손해 발생)

📢 섹션 요약 비유: 방문자가 올 때마다 투명한 도화지에 각기 다른 모양의 도장 3개를 마구잡이로 찍게 합니다. 나중에 "이 사람 왔었어?"라고 물을 때, 도장 3개의 모양 중 하나라도 빈 곳이 있으면 "절대 안 왔어(100% 부재)"라고 확신할 수 있습니다. 하지만 우연히 앞서 온 수많은 사람들의 도장 모양이 절묘하게 겹쳐서 도장이 다 찍혀있는 것처럼 보이면 "어? 온 것 같은데?"라고 착각(긍정 오류)하게 되는 확률적 마술입니다.

Ⅲ. 치명적 단점과 파라미터 튜닝 (Trade-off)

블룸 필터는 한 번 물든 색을 지우지 못하는 치명적 약점이 있다.

  1. 삭제(Delete) 연산의 불가능:
    • '홍길동(2, 4, 7)'이 회원 탈퇴를 했다고 4번 전구를 꺼(0)버리면 어떻게 될까? 애꿎게 4번 전구를 공유하던 '이순신(4, 8, 9)' 데이터마저 "존재하지 않음"으로 인식되어 데이터가 통째로 증발해 버리는 초대형 참사가 터진다.
    • 따라서 블룸 필터는 구조적으로 데이터의 추가(Add)와 검색(Test)만 가능하며 삭제가 불가능하다. (이를 극복하기 위해 숫자 카운트를 올리는 Counting Bloom Filter 등이 나왔다.)
  2. 거짓말 확률(False Positive Rate) 튜닝:
    • 데이터가 꽉 차서 전구가 다 켜져 버리면, 무조건 다 "있어!"라고 대답하는 바보 필터가 된다.
    • 에러율을 1%로 맞추기 위해, 저장할 데이터 개수($N$)에 맞춰 필터의 길이($M$, 전구 개수)를 충분히 크게 길게 늘여야 하며, 최적의 해시 함수 개수($K$) 공식을 적용해야 한다.

📢 섹션 요약 비유: 수백 명이 들어와 도화지에 도장을 찍다 보면 결국 도화지가 새까맣게 먹물로 뒤덮이게 됩니다. 도화지가 까매지면 누구를 물어보든 무조건 도장이 찍혀있다고 대답하는 바보가 되므로(에러율 폭증), 애초에 들어올 사람 수를 예측해서 도화지를 운동장만큼 크게 만들거나(메모리 투자), 도장 크기를 아주 작게 만들어(해시 최적화) 오랫동안 흰 여백을 유지하는 튜닝이 필수적입니다.