블룸 필터는 작은 메모리 공간을 사용하여 데이터 존재 여부를 빠르게 판단할 수 있는 특수한 해시 테이블입니다. .NET의 HashSet과 같은 전통적인 해시 테이블 대비 다음과 같은 장단점이 있습니다.

주요 특징

• 장점: 원본 데이터를 저장하지 않아 메모리 절약이 가능합니다.
• 단점:
• 존재하지 않는 데이터는 항상 없음을 보장하지만, 존재한다고 판정된 데이터는 실제로 존재하지 않을 수도 있습니다(즉, 일정한 오류율이 발생합니다).
• 데이터 삭제가 불가능합니다.

비트맵 활용

블룸 필터는 내부적으로 비트맵(Bitmap)을 사용하여 데이터를 저장합니다. 비트맵은 단순히 0 또는 1로 구성된 이진 배열입니다. 각 비트는 블룸 필터의 "버킷"으로 간주됩니다. 데이터 삽입 시 여러 해시 함수를 통해 해당 버킷이 활성화(1로 설정)됩니다.

C#을 활용한 비트맵 구현

C#에서는 직접 비트를 다룰 수 없지만, 비트 연산을 통해 byte 등의 데이터 유형을 기반으로 비트맵을 구현할 수 있습니다.

비트 연산 소개

비트맵 클래스 작성

class BitMap
{
    private readonly byte[] _data;
    private readonly int _size;

    public BitMap(int size)
    {
        _size = size;
        _data = new byte[(size + 7) / 8];
    }

    public void SetBit(int index)
    {
        if (index < 0 || index >= _size) throw new ArgumentOutOfRangeException(nameof(index));
        int byteIndex = index / 8;
        int bitIndex = index % 8;
        _data[byteIndex] |= (byte)(1 << bitIndex);
    }

    public void ClearBit(int index)
    {
        if (index < 0 || index >= _size) throw new ArgumentOutOfRangeException(nameof(index));
        int byteIndex = index / 8;
        int bitIndex = index % 8;
        _data[byteIndex] &= (byte)~(1 << bitIndex);
    }

    public bool GetBit(int index)
    {
        if (index < 0 || index >= _size) throw new ArgumentOutOfRangeException(nameof(index));
        int byteIndex = index / 8;
        int bitIndex = index % 8;
        return (_data[byteIndex] & (1 << bitIndex)) != 0;
    }
}

블룸 필터 구현

다음으로 블룸 필터를 구현하겠습니다. 이를 위해 MurmurHash3와 같은 해시 함수를 사용합니다.

MurmurHash3 적용

MurmurHash3는 임의 길이의 바이트 배열을 128비트(16바이트)의 해시 값으로 변환합니다. 이를 활용해 다양한 유형의 데이터를 처리할 수 있습니다.

using System.Text;

public class BloomFilter<T>
{
    private readonly BitMap _bitMap;
    private readonly int _hashCount;
    private readonly Func<T, long[]> _hashFunctions;

    public BloomFilter(int size, int hashCount, Func<T, long[]> hashFunctions)
    {
        _bitMap = new BitMap(size);
        _hashCount = hashCount;
        _hashFunctions = hashFunctions;
    }

    public void Add(T item)
    {
        var hashes = _hashFunctions(item);
        for (int i = 0; i < _hashCount && i < hashes.Length; i++)
        {
            int index = (int)(Math.Abs(hashes[i]) % _bitMap.Size);
            _bitMap.SetBit(index);
        }
    }

    public bool MightContain(T item)
    {
        var hashes = _hashFunctions(item);
        for (int i = 0; i < _hashCount && i < hashes.Length; i++)
        {
            int index = (int)(Math.Abs(hashes[i]) % _bitMap.Size);
            if (!_bitMap.GetBit(index)) return false;
        }
        return true;
    }
}

public static class HashUtility
{
    public static long[] ComputeHashes(string input)
    {
        byte[] data = Encoding.UTF8.GetBytes(input);
        HashAlgorithm murmur128 = MurmurHash.Create128(managed: false);
        byte[] hash = murmur128.ComputeHash(data);

        Span<byte> span = hash.AsSpan();
        long lower = BinaryPrimitives.ReadInt64LittleEndian(span.Slice(0, 8));
        long upper = BinaryPrimitives.ReadInt64LittleEndian(span.Slice(8, 8));

        return new long[] { lower, upper };
    }
}

예제 코드 실행

var filter = new BloomFilter<string>(1024, 2, input => HashUtility.ComputeHashes(input));
filter.Add("hello");
Console.WriteLine(filter.MightContain("hello")); // True
Console.WriteLine(filter.MightContain("world")); // False

확장 사항

카운팅 블룸 필터

기본 블룸 필터는 삭제를 지원하지 않습니다. 그러나 각 버킷을 카운터로 대체하면 데이터 삭제를 부분적으로 지원할 수 있습니다. 다만 이는 메모리 소비량이 증가하는 단점이 있습니다.

분산 환경에서의 블룸 필터

RedisBloom과 같은 라이브러리를 사용하면 분산 환경에서도 블룸 필터를 효율적으로 구현할 수 있습니다.