자바에서 블룸 필터를 구현하는 방법을 이해하기 전에 먼저 비트맵(bitmap)의 기본 개념을 살펴보겠습니다. 비트맵은 대규모 데이터 집합에서 요소 존재 여부를 효율적으로 확인하는 데 사용되는 자료 구조입니다.

1. 비트맵(bitmap)의 기본 원리

비트맵은 각 비트가 0 또는 1의 값을 가지는 긴 배열입니다. int 타입(32비트)을 예로 들면, 하나의 int 값은 32개의 서로 다른 정수를 표현할 수 있습니다. 예를 들어, 10억 개의 정수를 저장할 때 int 배열은 약 3.72GB가 필요하지만, 비트맵은 약 120MB만 필요합니다.

비트맵 저장 예시:

• int 타입 배열로 비트맵 구현: 하나의 int는 32비트이므로 32개의 정수를 표현
• 저장: 정수 100을 저장하려면 배열 인덱스 = 100/32, 비트 오프셋 = 100%32 계산 후 해당 비트를 1로 설정
• 조회: 같은 방식으로 인덱스와 오프셋을 계산한 후 해당 비트가 1인지 확인

비트맵 코드 예시:

public class BitMapExample {
    private int[] bitmap;
    
    public BitMapExample(int capacity) {
        this.bitmap = new int[(capacity / 32) + 1];
    }
    
    public void insert(int value) {
        int idx = value / 32;
        int offset = value % 32;
        bitmap[idx] = bitmap[idx] | (1 << offset);
    }
    
    public boolean exists(int value) {
        int idx = value / 32;
        int offset = value % 32;
        return (bitmap[idx] & (1 << offset)) > 0;
    }
}

비트맵의 한계

• 정수만 처리 가능하며 문자열 같은 다른 데이터 타입은 직접 처리 불가
• 데이터가 희소한 경우(예: 100개의 큰 값) 메모리 낭비가 심함
• 해시 충돌이 발생하지 않으므로 100% 정확함(정수만 해당)

2. 블룸 필터의 구현 원리

블룸 필터는 비트맵과 여러 개의 해시 함수를 결합하여 문자열 같은 비정수 데이터도 처리할 수 있게 합니다. 기본 아이디어는 문자열을 해시 함수를 통해 정수로 변환한 후 비트맵에 저장하는 것입니다.

핵심 동작 방식:

• 여러 개의 해시 함수를 사용하여 각 입력값을 여러 비트 위치에 매핑
• 존재 여부 확인 시 모든 해당 비트가 1인지 검사
• 하나라도 0이면 해당 요소는 확실히 존재하지 않음
• 모든 비트가 1이면 존재할 가능성이 있음(해시 충돌로 인한 오탐 가능)

해시 충돌과 오탐율

블룸 필터의 주요 특징은 '존재하지 않음'은 확실히 알 수 있지만 '존재함'은 확률적으로만 알 수 있다는 점입니다. 이는 해시 함수의 충돌 때문입니다. 여러 해시 함수를 사용하면 충돌 확률이 낮아지지만 완전히 제거되지는 않습니다.

삭제 연산의 문제

블룸 필터는 일반적으로 삭제를 지원하지 않습니다. 한 요소의 비트가 다른 요소와 공유될 수 있기 때문에, 삭제 시 다른 요소의 존재 여부를 잘못 판단할 수 있습니다.

3. Guava를 이용한 블룸 필터 구현

구글의 Guava 라이브러리는 BloomFilter 클래스를 제공합니다. 다음은 간단한 사용 예시입니다:

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import java.nio.charset.Charsets;
import java.util.*;

public class BloomFilterDemo {
    public static void main(String[] args) {
        int capacity = 100000;
        // 기본 오탐율 0.03(3%)
        BloomFilter<String> filter = BloomFilter.create(
            Funnels.stringFunnel(Charsets.UTF_8), capacity
        );
        
        Set<String> realSet = new HashSet<>();
        List<String> allData = new ArrayList<>();
        
        // 10만 개의 UUID 삽입
        for (int i = 0; i < capacity; i++) {
            String uuid = UUID.randomUUID().toString();
            filter.put(uuid);
            realSet.add(uuid);
            allData.add(uuid);
        }
        
        int realCount = 0;
        int filterCount = 0;
        
        // 1만 개의 데이터 검증(100개는 실제, 9900개는 랜덤)
        for (int i = 0; i < 10000; i++) {
            String testData = (i % 100 == 0) ? 
                allData.get(i / 100) : UUID.randomUUID().toString();
            
            if (filter.mightContain(testData)) {
                filterCount++;
                if (realSet.contains(testData)) {
                    realCount++;
                }
            }
        }
        
        double errorRate = (filterCount - realCount) / 10000.0;
        System.out.println("실제 존재: " + realCount);
        System.out.println("필터 판단 존재: " + filterCount);
        System.out.println("오탐율: " + String.format("%.3f", errorRate));
    }
}

결과 예시:

실제 존재: 100
필터 판단 존재: 441
오탐율: 0.030

오탐율을 0.01로 낮추면 결과가 개선됩니다:

BloomFilter<String> filter = BloomFilter.create(
    Funnels.stringFunnel(Charsets.UTF_8), capacity, 0.01
);

실제 존재: 100
필터 판단 존재: 186
오탐율: 0.010

오탐율은 0으로 설정할 수 없습니다. 이론적으로 완벽한 블룸 필터는 존재하지 않기 때문입니다.

4. 블룸 필터 핵심 소스 분석

생성 과정

public static <T> BloomFilter<T> create(
    Funnel<? super T> funnel, 
    long expectedInsertions, 
    double fpp) {
    
    checkArgument(fpp > 0.0, "오탐율은 0보다 커야 합니다");
    checkArgument(fpp < 1.0, "오탐율은 1보다 작아야 합니다");
    
    long numBits = optimalNumOfBits(expectedInsertions, fpp);
    int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
    
    return new BloomFilter<>(
        new LockFreeBitArray(numBits), 
        numHashFunctions, 
        funnel, 
        BloomFilterStrategies.MURMUR128_MITZ_64
    );
}

요소 삽입

public <T> boolean put(T object, Funnel<? super T> funnel, 
                       int numHashFunctions, LockFreeBitArray bits) {
    long bitSize = bits.bitSize();
    long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong();
    int hash1 = (int) hash64;
    int hash2 = (int) (hash64 >>> 32);
    
    for (int i = 1; i <= numHashFunctions; i++) {
        int combinedHash = hash1 + (i * hash2);
        if (combinedHash < 0) {
            combinedHash = ~combinedHash; // 양수로 변환
        }
        bits.set(combinedHash % bitSize);
    }
    return true;
}

요소 존재 여부 확인

public <T> boolean mightContain(T object, Funnel<? super T> funnel,
                                 int numHashFunctions, LockFreeBitArray bits) {
    long bitSize = bits.bitSize();
    long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong();
    int hash1 = (int) hash64;
    int hash2 = (int) (hash64 >>> 32);
    
    for (int i = 1; i <= numHashFunctions; i++) {
        int combinedHash = hash1 + i * hash2;
        if (combinedHash < 0) {
            combinedHash = ~combinedHash;
        }
        if (!bits.get(combinedHash % bitSize)) {
            return false; // 하나라도 없으면 확실히 없음
        }
    }
    return true; // 모두 있으면 있을 가능성 있음
}

5. 블룸 필터의 실제 적용 사례

Redis 캐시 방어

블룸 필터를 사용하여 캐시 관통(cache penetration) 문제를 해결할 수 있습니다. 먼저 모든 허용된 키를 블룸 필터에 저장하고, 요청이 들어오면 블룸 필터에서 먼저 확인합니다. 필터에 없으면 바로 거부하여 불필요한 DB 조회를 방지합니다.

기타 응용 분야

• 웹 크롤러에서 URL 중복 제거
• 이메일 스팸 필터링 및 블랙리스트 관리
• 대용량 파일 정렬: 예를 들어 10GB 파일(약 27억 개 정수)을 320MB 메모리로 정렬
• 데이터베이스 쿼리 최적화

대용량 정렬 예시

10GB 크기의 자연수 파일을 정렬해야 하는데 메모리가 2GB뿐이라면, 블룸 필터를 활용할 수 있습니다. 27억 개의 정수를 비트맵에 저장하면 약 320MB가 필요하므로 충분히 가능합니다. 1부터 최대값까지 순회하며 비트맵에 존재하는 값만 출력하면 정렬된 결과를 얻을 수 있습니다.