Bluesky, 단일 해시 블룸 필터로 배포 시간을 90분에서 15분으로 줄이다
One Hash Bloom Filters
Bluesky 백엔드에서 블룸 필터는 초당 수백만 건의 데이터베이스 쿼리를 절약한다. 기존 라이브러리의 뮤텍스 경합으로 배포가 90분씩 걸리던 문제를 원자적 연산으로 해결한 뒤, 저자는 단일 해시만으로 동작하는 블룸 필터 구현 'gloom'을 만들어 9개월째 운영 중이다. 64바이트 캐시 라인 정렬과 단일 MUL 명령어 최적화로 최악의 경우에도 캐시 미스 한 번만 발생한다.
pprof는 뮤텍스 경합이 실제로 프로세스 시작의 병목이었음을 보여주었다. 이 때문에 단일 배포가 완전히 롤아웃되는 데 90분이 걸리곤 했다!
HN 토론
10- aappleby
꼭 이렇게 할 필요는 없습니다. 크기가 2의 거듭제곱인 테이블을 그대로 쓰고 해시 값을 살짝 섞어서 각 추가 비트 인덱스를 얻으면 됩니다.
(출처 - 제가 MurmurHash/SMHasher를 작성했고 제 블룸 필터와 쿠쿠 해시 테이블에서 위 방법을 사용했습니다)
- FreakLegion
참고: 여기서 무시할 수 없는 공간 효율성을 희생하는 것인데, 거짓 양성률을 낮출수록 더 나빠집니다. 파티셔닝은 파티션 간 점유율이 불균등해진다는 뜻이고, 낮은 점유율을 감수하거나(전체 필터 크기 증가) 아니면 핫 블록이 생길 가능성이 거의 확실합니다(특정 파티션의 거짓 양성률 증가).
- cperciva
디스크로 가는 것보다 훨씬 저렴하지만, 키당 k개의 독립 해시를 계산하는 것은 매우 고성능 시스템에서는 여전히 다소 비쌉니다.
블룸 필터의 크기에 따라 다릅니다. 대부분의 해시는 크고 그 비트들은 독립적입니다.