블룸 필터 기초 개념

블룸 필터는 비트 배열과 해시 함수를 결합한 확률적 데이터 구조로, 원소 존재 여부를 효율적으로 판단합니다. 핵심 원리:

• 크기 m의 비트 배열 초기화
• k개의 해시 함수를 통해 원소를 k개의 비트 위치에 매핑
• 삽입 시 해당 위치 비트를 1로 설정
• 검색 시 모든 위치가 1인지 확인하여 존재 여부 판단

장점 및 한계

효율성 측면에서 다음과 같은 특징을 가집니다:

• 메모리 절약: 원소 자체 대신 해시 값만 저장 가능
• 고속 처리: 삽입/검색 모두 O(k) 시간 복잡도
• 분산 확장성: 노드 간 분산 저장 가능
• 단점: 오류 발생 가능성(정확도 감소), 삭제 지원 불가, 파라미터 최적화 어려움

실용적 적용 사례

다양한 시스템에서 활용되는 주요 용例:

• 캐시 허브: 미존재 데이터 접근 방지
• 이메일 필터링: 스팸 판별 최적화
• 웹 스크래퍼: 중복 URL 제거
• 데이터베이스: 중복 기록 방지
• 분산 네트워크: 데이터 위치 검색 최적화

분산 블룸 필터 설계

Redis 기반 분산 구현을 위한 핵심 요소:

• 비트 배열 분산 저장: 노드별 부하 균형
• 해시 알고리즘: 동등 분포 보장
• 일관성 해시: 노드 변화 시 데이터 재분배

구현 코드 예시

// 일관성 해시 관리 클래스
public class HashRing {
    private final Map nodeMap = new TreeMap<>();
    private final int virtualNodes;

    public HashRing(int virtualNodes) {
        this.virtualNodes = virtualNodes;
    }

    public void registerNode(String host, int port) {
        for (int i = 0; i < virtualNodes; i++) {
            String key = String.format("%s:%d:%d", host, port, i);
            nodeMap.put(hash(key), host + ":" + port);
        }
    }

    public String findNode(String key) {
        if (nodeMap.isEmpty()) return null;
        int hash = hash(key);
        if (!nodeMap.containsKey(hash)) {
            Map.Entry entry = nodeMap.tailMap(hash).firstEntry();
            return entry != null ? entry.getValue() : nodeMap.firstEntry().getValue();
        }
        return nodeMap.get(hash);
    }

    private int hash(String str) {
        return Math.abs(str.hashCode());
    }
}

// 분산 블룸 필터 클래스
public class DistributedBloom {
    private final HashRing hashRing;
    private final int bitSize;
    private final int hashCount;

    public DistributedBloom(int virtualNodes, int bitSize, int hashCount) {
        this.hashRing = new HashRing(virtualNodes);
        this.bitSize = bitSize;
        this.hashCount = hashCount;
    }

    public void add(String value) {
        int[] positions = computeHashPositions(value);
        String node = hashRing.findNode(value);
        try (Jedis jedis = new Jedis(node.split(":")[0], Integer.parseInt(node.split(":")[1]))) {
            for (int pos : positions) {
                jedis.setbit("bloom_key", pos, true);
            }
        }
    }

    public boolean check(String value) {
        int[] positions = computeHashPositions(value);
        String node = hashRing.findNode(value);
        try (Jedis jedis = new Jedis(node.split(":")[0], Integer.parseInt(node.split(":")[1]))) {
            for (int pos : positions) {
                if (!jedis.getbit("bloom_key", pos)) return false;
            }
        }
        return true;
    }

    private int[] computeHashPositions(String value) {
        int[] positions = new int[hashCount];
        for (int i = 0; i < hashCount; i++) {
            positions[i] = Math.abs(Murmur3.hash(value.getBytes()).asInt() % bitSize);
        }
        return positions;
    }
}