없는 키 조회가 DB에 많이 들어옵니다. 블룸 필터로 존재 여부를 먼저 검사해 어떤 조회를 생략할 수 있나요?

블룸 필터는 키가 없을 가능성이 큰 요청을 먼저 검사해 DB 조회를 줄이는 보조 구조입니다. 필터가 없다고 답하면 올바르게 갱신된 표준 필터에서는 실제로 없다고 판단할 수 있지만, 있다고 답해도 반드시 DB나 권위 있는 저장소에서 다시 확인해야 합니다. 쓰기와 필터 반영 사이에 지연이 있다면 존재하는 키를 없다고 잘못 거를 수 있으므로, 최신성이 필요한 최종 판정에는 사용하지 않겠습니다.

갱신과 장애 정책을 정합니다

키를 여러 해시 함수로 비트 배열의 위치에 매핑하고 삽입 때 해당 비트를 켭니다. 조회한 키의 비트가 하나라도 꺼져 있으면 그 키는 삽입된 적이 없다고 볼 수 있습니다. 반대로 모든 비트가 켜져 있어도 여러 키가 같은 위치를 공유했을 수 있어 실제 원소라고 확정할 수 없습니다. 실제로 있는 키를 없다고 하는 오류는 거짓 음성, 없는 키를 있을 수 있다고 하는 오류는 거짓 양성이라고 부르며, 표준 삽입 전용 블룸 필터는 보통 거짓 음성을 없애고 거짓 양성만 허용하는 방향으로 설계합니다. 이를 확률적 멤버십 필터(probabilistic membership filter)라고 부릅니다.

없는 상품 ID가 악성 또는 단순 오류로 반복 요청되는 상황에서는 필터가 음성으로 응답한 요청을 DB까지 보내지 않아 효과를 얻습니다. 그러나 새 상품을 DB에 먼저 저장하고 필터 전파가 늦으면 실제 상품 조회가 누락됩니다. 그래서 쓰기 경로에서 DB 커밋과 필터 갱신의 순서를 정하고, 갱신 실패 때 재시도·재구축·일시적 원본 조회 우회를 마련해야 합니다. 필터가 차단한 응답에는 캐시나 권위 저장소의 최신성 계약도 함께 고려해야 합니다.

용량과 삭제 정책을 함께 설계합니다

예상 원소 수보다 많은 키를 넣으면 비트가 포화되어 거짓 양성이 증가합니다. 메모리를 늘리면 보통 오탐률을 낮출 수 있지만 해시 계산과 전송 비용도 늘어납니다. 일반 블룸 필터에서 삭제 시 해당 비트를 끄면 다른 키가 함께 사라진 것처럼 보일 수 있으므로, 삭제 가능한 counting Bloom filter를 쓰거나 원본에서 새 필터를 재구축해야 합니다. counting 방식은 카운터 메모리와 갱신 비용을 추가로 부담합니다.

검증에서는 실제 부재 키 가운데 필터가 양성으로 나온 비율(거짓 양성률), 필터 양성 중 원본에도 없는 비율, 쓰기 후 부재 오판, 재구축 중 누락을 따로 측정하겠습니다. 캐시 무효화와 결합한다면 필터를 캐시의 대체품으로 착각하지 않고, 캐시 miss 뒤 원본 조회를 생략할 수 있는지에만 사용하겠습니다. 핵심은 적중률보다 잘못된 부재 응답이 허용되는지와 갱신 전제입니다.

필터를 캐시 앞에 둘 때도 개인정보나 권한 정보를 필터에 넣지 않겠습니다. 필터는 해시된 키의 존재 가능성만 요약할 뿐 원본을 복원하는 저장소가 아니지만, 키 공간이 작거나 공격자가 후보를 알면 추측 보조 정보가 될 수 있습니다. 또한 필터가 너무 오래되면 음성 차단을 중단하는 것이 안전합니다. 이때 DB 부하가 급증할 수 있으므로 회로 차단기와 요청 제한으로 보호하고, 필터 복구가 끝났을 때만 차단 경로를 다시 켜겠습니다. 정확성·가용성·원본 비용 사이의 선택을 장애 모드별로 명시하겠습니다.

비트 수 m, 삽입 원소 수 n, 해시 수 k일 때 독립적이고 균등한 해시를 가정한 거짓 양성률 근사는 (1-exp(-kn/m))^k입니다. k를 무조건 늘리면 모든 비트가 빨리 채워지고 해시 계산도 늘어납니다. 이 모델의 최적 k는 약 (m/n)·ln 2이지만 실제 해시 상관과 예상보다 큰 n을 부하 시험에 포함하겠습니다.