Bluesky 블룸 필터에 해시 하나만 쓰는 One Hashing 기법 소개

이 one hash 논문 처음 봤는데 진짜 괜찮은 최적화인 듯. 입력 크기별 벤치마크 있음? 필터 병합도 용량 안 넘는 선에서는 될 것 같음.

근데 공간 효율 손해가 큼. 파티션마다 점유율이 고르지 않아서 false positive를 낮출수록 손해가 더 커짐. 핫 블록 생기면 특정 파티션 오탐률만 뜀.

그건 partitioned가 아니라 blocked 블룸 필터 얘기임. k개 해시가 블록 하나 안에서 돌아가니까 불균형이 생기는 거고, partitioned는 해시마다 파티션이 따로라 그 문제 없음.

캐시 라인 크기로 쪼개는 건 시간이랑 공간 트레이드오프라기보다 동시 쓰기 성능 때문인 듯. 두 CPU가 같은 캐시 라인에 동시에 못 쓰니까 그럼.

굳이 이렇게 안 해도 됨. 2의 거듭제곱 테이블 두고 해시 값을 살짝 섞어서 비트 인덱스 뽑으면 됨. 나도 MurmurHash랑 cuckoo 해시 테이블에서 그렇게 씀.

그럼 64비트 해시 하나에서 9비트씩 뽑아서 64바이트 캐시 라인 안 비트 7개 주소를 만드는 식임?

one hashing이 기술적으로는 더 낫긴 함. 근데 서로소 파티션 때문에 생기는 상관관계 문제랑 해시 충돌은 피할 방법이 있을 것 같음.

해시 여러 개 계산이 비싸다는 말은 필터 크기에 따라 다름. 대부분 해시는 크고 비트들이 서로 독립적이라 큰 걱정은 아님.