iOS 블룸 필터 검증: 거짓 음성, 오탐과 스냅샷 경계

오프라인 목록을 동기화할 때 클라이언트는 각 레코드가 이전에 확인한 항목인지 판단해야 합니다. 매번 디스크를 조회하면 비용이 커질 수 있습니다. 블룸 필터로 확실히 존재하지 않는 키를 먼저 걸러낼 수 있지만, “존재할 수 있음”을 “이미 처리함”으로 받아들이면 새 레코드가 아무런 경고 없이 누락됩니다. 이 로직을 클라우드 Mac의 정기 테스트 작업에 넣어 두면, 배포 후 데이터 누락을 추적하는 것보다 문제를 쉽게 찾아낼 수 있습니다.

확률적 인덱스가 필요한지 먼저 판단하기

정확한 집합 자료구조, 데이터베이스 인덱스, 블룸 필터는 각각 적합한 용도가 있습니다. 데이터가 적고 즉시 확정적인 답을 얻어야 한다면 정확한 집합을 사용합니다. 데이터가 이미 디스크에 저장되어 있고 조회 비용을 감당할 수 있다면 데이터베이스 인덱스를 우선합니다. 존재하지 않는 키에 대한 비싼 조회가 대량으로 발생할 때만 필터 계층 추가를 고려합니다.

블룸 필터는 키 하나를 여러 해시 위치의 비트로 표시합니다. 조회할 때 비트가 하나라도 0이면 존재하지 않는다고 답할 수 있습니다. 모든 비트가 1이면 존재할 수 있다고만 답할 수 있습니다. 원래 키 목록을 복원할 수 없으며, 기준이 되는 원본 저장소를 대체할 수도 없습니다.

“거짓 음성이 없다”는 보장은 키가 이미 삽입되었고, 비트맵이 손상되지 않았으며, 조회에 같은 알고리즘을 사용하고, 갱신이 유실되지 않았다는 전제에서만 성립합니다. 전체 비즈니스 시스템에 대한 무조건적인 보장이 아닙니다.

이 예제의 검증 대상은 추가 전용 필터입니다. 레코드를 삭제한다고 해당 비트를 바로 0으로 바꾸면 안 됩니다. 다른 키가 같은 비트를 공유할 수 있기 때문입니다. 삭제 기능이 필요하다면 필터를 다시 만들거나 삭제를 지원하는 다른 자료구조를 선택해야 합니다.

키 인코딩과 비트 인덱스 알고리즘 고정하기

영속화할 필터는 Swift의 Hasher에 직접 의존해서는 안 됩니다. 프로세스가 달라도 같은 결과를 낸다는 보장이 없기 때문입니다. 먼저 키의 UTF-8 인코딩을 명확히 정하고, 다이제스트 알고리즘과 비트 인덱스 계산 방식도 고정해야 합니다. 대소문자 변환이나 앞뒤 공백 제거 같은 비즈니스 규칙은 입력 지점에서 일관되게 적용해야 하며, 호출자가 그때그때 결정하게 두어서는 안 됩니다.

아래는 학습용으로 고정한 구성입니다. 비트 수는 1024개이고, 비트 인덱스는 네 개입니다. 코드를 bloom-check.swift로 저장합니다. 다이제스트를 네 구간으로 나누어 각각 비트맵의 위치에 매핑합니다. 모든 데이터 규모에 맞게 최적화된 운영용 매개변수는 아닙니다.

import Foundation
import CryptoKit

enum SnapshotError: Error {
    case invalidLength
}

struct Bloom {
    private var bytes: [UInt8]

    init() {
        bytes = [UInt8](repeating: 0, count: 128)
    }

    init(snapshot: Data) throws {
        guard snapshot.count == 128 else {
            throw SnapshotError.invalidLength
        }
        bytes = Array(snapshot)
    }

    var snapshot: Data {
        Data(bytes)
    }

    private func positions(_ key: String) -> [Int] {
        let digest = Array(SHA256.hash(data: Data(key.utf8)))
        return stride(from: 0, to: 32, by: 8).map { start in
            let value = digest[start..<(start + 8)].reduce(UInt64(0)) {
                ($0 << 8) | UInt64($1)
            }
            return Int(value % 1024)
        }
    }

    mutating func insert(_ key: String) {
        for bit in positions(key) {
            bytes[bit / 8] |= UInt8(1 << (bit % 8))
        }
    }

    func mightContain(_ key: String) -> Bool {
        positions(key).allSatisfy { bit in
            bytes[bit / 8] & UInt8(1 << (bit % 8)) != 0
        }
    }
}

여기서는 빈 문자열도 유효한 키입니다. 비즈니스 규칙상 빈 키를 허용하지 않는다면 필터가 조용히 무시하게 할 것이 아니라 비즈니스 로직의 입력 지점에서 거부해야 합니다. 문자열 정규화 정책도 버전으로 관리해야 합니다. 그렇지 않으면 눈으로 보기에 같은 텍스트가 서로 다른 바이트를 만들 수 있습니다.

결정적 단언으로 기본 계약 검증하기

다음 내용을 같은 파일에 추가한 뒤 명령을 실행합니다. 테스트는 실제 배포 경로에서 사용하는 구현을 그대로 사용해야 합니다. 테스트 전용 복사본을 별도로 만들어 장기간 유지해서는 안 됩니다.

var filter = Bloom()
precondition(!filter.mightContain(""))

let keys = (0..<80).map { "record-\($0)" } + [""]
for key in keys {
    filter.insert(key)
}
for key in keys {
    precondition(filter.mightContain(key))
}

let before = filter.snapshot
for key in keys {
    filter.insert(key)
}
precondition(filter.snapshot == before)

let restored = try Bloom(snapshot: before)
for key in keys {
    precondition(restored.mightContain(key))
}

do {
    _ = try Bloom(snapshot: Data(repeating: 0, count: 127))
    preconditionFailure("Invalid snapshot accepted")
} catch SnapshotError.invalidLength {
}

let saturated = try Bloom(
    snapshot: Data(repeating: 255, count: 128)
)
precondition(saturated.mightContain("never-inserted"))

xcrun swift bloom-check.swift

단언이 실패하면 작업도 실패합니다. 단언 검사를 비활성화하는 최적화 설정으로 이 검증 스크립트를 실행해서는 안 됩니다. 모든 비트가 1인 비트맵 예제는 삽입한 적이 없는 키에도 필터가 양성을 반환할 수 있음을 보여 주기 위한 것입니다.

긴 키, 중국어 키, 서로 다른 Unicode 표현도 테스트에 포함해야 합니다. 삽입하지 않은 모든 키가 반드시 음성을 반환한다고 단언해서는 안 됩니다. 그렇게 하면 허용되는 오탐을 구현 오류로 취급하게 됩니다.

오탐률 측정과 스냅샷 호환성 검증 분리하기

오탐률은 비트 수, 해시 횟수, 삽입한 키 수에 따라 달라집니다. 검증할 때는 삽입 키 집합을 고정하고, 그 집합과 겹치지 않는 것이 확실한 조회 집합으로 양성 응답 수를 집계합니다. 표본 크기와 알고리즘 버전도 함께 저장합니다. 작은 표본으로 한 번 측정했을 때 오탐이 없었다고 해서 실제 오탐률이 0인 것은 아닙니다.

운영용 스냅샷에는 위의 원시 비트맵만 저장해서는 안 됩니다. 이를 감싸는 포맷에 최소한 버전, 비트 수, 해시 횟수, 키 인코딩 규칙, 데이터셋 세대를 기록하고 페이로드 무결성도 검사해야 합니다. 길이가 맞는다는 사실만으로는 잘림 여부만 확인할 수 있을 뿐, 특정 비트가 1에서 0으로 바뀐 손상은 발견할 수 없습니다.

프로세스 간 호환성 픽스처 추가하기

같은 프로세스에서 내보낸 뒤 복원하는 테스트로는 로직의 일부만 검증할 수 있습니다. 고정된 키로 생성한 스냅샷을 저장소의 테스트 픽스처로 포함하고, 다른 프로세스에서 읽어 삽입된 모든 키를 조회하는 테스트도 필요합니다. 그래야 알고리즘 업그레이드나 인코딩 변경으로 인한 호환성 문제를 발견할 수 있습니다. 포맷이 호환되지 않으면 이전 매개변수를 추측하지 말고 원본 데이터로 다시 생성해야 합니다.

파이프라인에 연결할 때 안전한 우회 경로 유지하기

동시 삽입을 위해 이 값 타입 구현을 그대로 공유해서는 안 됩니다. 읽기-수정-쓰기 과정에서 비트 갱신이 유실될 수 있습니다. 하나의 소유자가 직렬로 처리하도록 하거나 잠금을 적용하고, 스냅샷을 생성하는 동안에는 동시 쓰기가 없도록 보장해야 합니다. 비트맵 갱신과 원본 데이터 갱신의 선후 관계도 복구 프로토콜에 명시해야 합니다.

필터가 데이터베이스보다 뒤처지면 음성 결과를 더는 신뢰할 수 없습니다. 재생성 중에는 필터 계층을 우회해 원본 저장소를 직접 조회해야 합니다. 일관성이 보장되는 전환을 마친 뒤에 필터를 다시 활성화해야 하며, 불완전한 새 비트맵으로 요청을 처리해서는 안 됩니다.

최종 점검 항목에는 삽입한 키가 모두 양성을 반환하는지, 중복 삽입으로 스냅샷이 바뀌지 않는지, 손상된 포맷을 거부하는지, 이전 픽스처를 여전히 읽을 수 있는지, 그리고 비즈니스 로직이 양성 결과를 받았을 때 실제로 정확한 재조회를 수행하는지가 포함되어야 합니다. 필터 장애로 조회가 느려질 수는 있어도 새 레코드가 사라져서는 안 됩니다.

자주 묻는 질문