블룸 필터: 원소가 집합에 들어 있을까?

블룸 필터(Bloom filter)는 어떤 원소 x가 집합 M에 들어 있는지를 어느 정도의 확률로 알려 주는 확률적 자료 구조이다.

예를 들어 시스템에서 사용자가 광고 배너를 몇 번 클릭했는지 측정해야 한다고 하자. 클릭할 때마다 사용자 XYZ가 광고 123을 클릭했다는 HTTP GET 요청이 들어온다. 그런데 사용자가 실수로 마우스를 두 번 클릭해서 요청이 두 개 들어올 때가 있다. 이런 요청을 걸러 내어 데이터베이스에는 클릭 한 번으로 기록하고 싶다.

그래서 클릭 메시지 채널을 읽으면서 중복을 걸러 내는 애플리케이션이 필요하다. 어떻게 만들면 될까? 메시지마다 ID가 있으므로 메시지 전체를 비교할 필요 없이, 같은 ID의 메시지를 이미 처리한 적이 있는지만 확인하면 된다. 메시지 스트림(여기서는 간단히 배열)에서 중복을 없애는 간단한 자바스크립트 코드는 다음과 같다.

var messages = [{id: "123"}, {id:"456"}, {id:"123"}, {id: "789"}]
var processedIds = {};

messages.forEach(function(message) {
    if (!processedIds[message.id]) {
        processedIds[message.id] = true;
        console.log(message);
    }
});

// 출력: { id: "123" } { id: "456" } { id: "789" }

이 방법은 메모리가 부족해지기 전까지는 충분하다. 그런데 집합 processedIds는 시간이 지날수록 커지기만 하므로 언젠가는 메모리가 부족해진다. 물론 데이터 만료 기능을 넣을 수도 있다. 예를 들어 1시간보다 오래된 메시지를 늘 지우는 식이다.

그것으로도 부족하면 더 곤란하다. 집합 processedIds에 적어도 하루치 데이터를 두어야 하고, 예를 들어 1초에 메시지를 1만 개씩 처리한다면 어떨까? 최악의 경우 ID를 864,000,000개까지 저장해야 한다. uuid v4를 쓰면 ID 하나의 길이가 36이므로 하루에 적어도 31 GB를 저장해야 한다. 조금 많다. 메모리 사용량을 줄일 수는 없을까?

블룸 필터

ID 전체를 저장하는 대신 그 해시값만 저장할 수 있다. 문자열마다 32비트 정수를 돌려주고 분포도 좋은 보통의 murmurhash를 쓰면 된다.

var murmurhash = require("murmurhash");

var messages = [{id: "123"}, {id:"456"}, {id:"123"}, {id: "789"}];
var processedHashedIds = {};

messages.forEach(function(message) {
    var hashedId = murmurhash.v2(message.id);
    if (!processedHashedIds[hashedId]) {
        processedHashedIds[hashedId] = true;
        console.log(message);
    }
});

// 출력: { id: "123" } { id: "456" } { id: "789" }

다음으로 비트 배열 기법을 쓴다. 비트 배열은 0과 1만 저장하는 배열이다. n비트 해시 함수가 있으면 해시 함수의 가능한 출력을 모두 배열에서 가리킬 수 있도록 크기가 2ⁿ인 비트 배열이 필요하다. 아이디어는 이렇다. 처음에 배열은 0으로만 채워져 있다. 그리고 해시 함수가 입력 "123"에 대해 수 47을 돌려주면 배열의 인덱스 47에 1을 넣으면 된다. 이렇게 해시값 47을 이미 보았다고 표시한다.

var n = 8;
var numberOfValues = Math.pow(2, n);
var messages = [{id: "123"}, {id:"456"}, {id:"123"}, {id: "789"}];
var bitVector = new Array(numberOfValues);

messages.forEach(function(message) {
    var hashedId = murmurhash.v2(message.id) % numberOfValues;
    if (!bitVector[hashedId]) {
        bitVector[hashedId] = true;
        console.log(message);
    }
});

// 출력: { id: "123" } { id: "456" } { id: "789" }

코드 % numberOfValues는 murmurhash를 잘라서 n비트 해시 함수로 만들 뿐이다. 이것이 블룸 필터이다. 물론 아주 퇴화한 버전이다. 이 방법의 문제는 당연히 반드시 생기는 충돌이다. 서로 다른 입력값이 같은 해시값을 가질 수 있다. 그래서 충돌이 생길 확률을 줄이기 위해 해시 함수를 하나만 쓰지 않고 여러 개 쓴다. 해시 함수 여러 개는 예를 들어 입력값에 솔트를 덧붙여 만들 수 있다. 서로 다른 n비트 해시 함수를 만드는 간단한 함수는 다음과 같다.

var murmurhash = require("murmurhash");

function createNBitHashFunction(n, salt) {
    var upperBound = Math.pow(2, n);
    return function(inputString) {
        return murmurhash.v2(inputString + salt) % upperBound;
    }
}

var firstHashFunction = createNBitHashFunction(8, "someSalt");
var secondHashFunction = createNBitHashFunction(8, "anotherSalt");

console.log(firstHashFunction("123")); // 42
console.log(secondHashFunction("123")); // 174

블룸 필터를 나타내는 클래스는 다음과 같이 쓸 수 있다.

function BloomFilter(numberOfHashFunctions, numberOfBits) {
    this.reset(numberOfHashFunctions, numberOfBits);
}

BloomFilter.prototype.reset = function(numberOfHashFunctions, numberOfBits) {
    this.bitVector = new Array(Math.pow(2, numberOfBits));
    this.hashFunctions = [];

    for (var i = 0; i < numberOfHashFunctions; i++) {
        this.hashFunctions.push(createNBitHashFunction(numberOfBits, i.toString()));
    }
}

BloomFilter.prototype.add = function(item) {
    var checksum;
    for (var i = 0; i < this.hashFunctions.length; i++) {
        checksum = this.hashFunctions[i](item);
        this.bitVector[checksum] = true;
    }
}

BloomFilter.prototype.contains = function(item) {
    var checksum;
    for (var i = 0; i < this.hashFunctions.length; i++) {
        checksum = this.hashFunctions[i](item);
        if (!this.bitVector[checksum]) {
            return false;
        }
    }
    return true;
}

메서드 add는 블룸 필터에 원소를 추가한다. 모든 해시 함수로 해시값을 계산하고 해당 인덱스에 true를 저장한다.
메서드 contains는 주어진 원소가 블룸 필터에 들어 있는지 확인한다.

블룸 필터는 쉽게 쓸 수 있다.

var bloomFilter = new BloomFilter(3, 8);
var messages = [{id: "123"}, {id:"456"}, {id:"123"}, {id: "789"}];

messages.forEach(function(message) {
    if (!bloomFilter.contains(message.id)) {
        bloomFilter.add(message.id);
        console.log(message);
    }
});

// 출력: { id: "123" } { id: "456" } { id: "789" }

이것이 기본 블룸 필터의 마법 전부이다. 기본 블룸 필터에는 다음과 같은 성질이 있다.

메서드 contains가 주어진 원소가 블룸 필터에 없다고 답하면, 그 원소는 정말로 한 번도 넣은 적이 없다.
메서드가 주어진 원소가 블룸 필터에 있다고 답해도, 그 원소를 정말로 넣었다는 뜻은 아닐 수 있다. 해시 함수의 충돌이 생겼을 수 있기 때문이다.
일반적으로 틀린 답을 할 확률을 줄이려면 해시 함수의 개수를 늘리거나 해시 함수의 크기(출력값의 크기)를 늘리면 된다.
해시 함수를 많이 쓸수록 블룸 필터는 느려진다.
해시 함수가 클수록 블룸 필터는 메모리를 많이 차지한다.
블룸 필터에 한 번 넣은 원소는 다시 제거할 수 없다.

« 이전: HyperLogLog: 서로 다른 값의 개수를 매우 정확하게 추정하는 방법

다음: 카이사르 암호 »