Cuckoo Filter실험-false negative

Intro

이전 글에서 이어지는 내용이에요

Redis Bloom Filter 문서에는 BF가 집합에서 특정 항목이 “존재하지 않음을 보장”한다고 말해요: A Bloom filter can guarantee the absence of an item from a set. 하지만 Redis Cuckoo Filter 문서에는 “존재 여부를 확인할 수 있다”고만 말하고, 보장이라는 표현은 없죠.

여러 자료들에서는(심지어 위키피디아에도) CF는 false negative가 없다고 설명하지만, 소스 코드를 뜯어보니 충분히 가능할 것 같아 직접 실험해봤어요.

실험 결과

일단 결론부터 말할게요. 이렇게 “존재하지 않는 원소를 삭제 ”하면 false negative가 발생할 수 있어요:

# 1. Cuckoo 필터 초기화
127.0.0.1:6379> CF.RESERVE myfilter 1000

# 2. A 삽입
127.0.0.1:6379> CF.ADD myfilter "xx0rlpx!xxsXъВ"
(integer) 1

# 3. B 삭제 시도 (A와 해시 충돌하는 문자열)
127.0.0.1:6379> CF.DEL myfilter "xxsXъВxx0rlpx!"
(integer) 1  #❓ 없는데 1?

# 4. A 존재 확인
127.0.0.1:6379> CF.EXISTS myfilter "xx0rlpx!xxsXъВ"
(integer) 0  #❗ false negative 발생!

왜?

CF는 단 하나의 해시 함수를 사용해서 두 후보 버킷 위치와 지문을 결정해요. 원본 데이터를 저장하지 않아서, 서로 다른 원소여도 해시값이 충돌한다면 확인할 방법이 없죠.

위에서 xxsXъВxx0rlpx! 와 xx0rlpx!xxsXъВ 의 해시값이 충돌했기 때문에, CF가 엉뚱한 원소를 삭제해버린 거예요.

엄밀히 말하면 이건 “있는데 없다”고 판단한 건 아니고, 있는 원소를 잘못 삭제해버린 거에요. 하지만 조회하는 입장에서는 결국 false negative와 동일하죠 .

공식 답변

포스트를 작성하면서 Redis 커뮤니티(레딧,디스코드)에 문의글을 올렸는데, 개발자분께 답변을 받았어요:

요지는 앞선 실험과 동일해요: false negative는 없지만, 존재하지 않는 원소를 삭제하면 필터 자체를 오염시킬 수 있기 때문에 false negative와 동일한 결과가 나온다는 거죠.

추가로 안전하게 CF.DEL 를 사용하려면 항상 “확실히 존재하는” 원소에만 사용해야 한다고 해요.

(물론 CF자체가 확률적 자료구조니깐, CF.EXISTS 로 보장할 순 없어요.)

Final

사실, 위와 같은 예시가 벌어질 일은 거의 없을 거에요. 하지만 100%와 99.9%는 분명히 달라요.

CF에서 false negative 확률을 완전히 막으려면, 삭제 시엔 RDB 등에서 이미 원소가 존재하는지를 확인후 삭제해야 해요. 다만 그만큼 성능 이점은 줄어들겠죠(사실 대부분은 그냥 쓸 것 같아요).

마지막으로 Reddit은 서브레딧에 따라 매운맛인 곳들도 많은데, 친절한 답변을 빠르게 받아서 좋았어요.

3-Point

1. 없는 원소를 삭제했을 때 해시 충돌로 다른 원소가 지워질 수 있다.
2. 그렇게 잘못 삭제되면, false negative와 동일하다.
3. Reddit은 뉴비에게 친절하다. (thx, Lior)