Bloom Filter 기반 부재 우선 조회
Bloom Filter는 집합의 모든 원소를 직접 저장하지 않고, bit 배열 하나와 여러 개의 hash 위치만으로 membership을 근사(approximate)하는 확률적 자료구조다. 결과가 “없다(negative)”이면 해당 원소는 집합에 확실히 없다고 판단할 수 있고, “있다(positive)”이면 실제로 존재할 수도 있고, false positive일 수도 있다. Burton Bloom의 1970년 논문은 이렇게 “허용 가능한 오류(false positive)”를 대가로 공간과 조회 시간을 크게 절약하는 구조를 제시했다.
· 연습 메모 · 54 min read · Hard
Bloom Filter란
Bloom Filter는 집합의 모든 원소를 직접 저장하지 않고, bit 배열 하나와 여러 개의 hash 위치만으로 membership을 근사(approximate)하는 확률적 자료구조다. 결과가 “없다(negative)”이면 해당 원소는 집합에 확실히 없다고 판단할 수 있고, “있다(positive)”이면 실제로 존재할 수도 있고, false positive일 수도 있다. Burton Bloom의 1970년 논문은 이렇게 “허용 가능한 오류(false positive)”를 대가로 공간과 조회 시간을 크게 절약하는 구조를 제시했다.1
왜 precheck가 필요한가
Bloom Filter는 결과가 대칭이 아니다. mightContain(key) == false는 그 key가 없다는 뜻으로 믿어도 되지만, true라고 해서 실제로 있다는 보장은 없다. 그래서 정답 저장소를 대신하는 물건이 아니고, 비싼 정확 조회 전에 수행하는 negative precheck로 쓴다.
false면 원격 조회는 건너뛴다.true면 원본 저장소까지 가서 정확히 확인한다.
양성을 존재로 읽어버리면, Bloom Filter가 허용해둔 false positive가 그대로 업무 오류가 된다.
예제: Artifact catalog
이번 예제는 SHA-256 digest로 식별되는 immutable artifact catalog를 다룬다. Artifact digest는 이미 균일한 32-byte 값이므로, digest 앞부분에서 두 개의 64-bit hash seed를 읽는다. 이후 h1+i⋅h2h1+i⋅h2 방식으로 여러 bit 위치를 만든다. Kirsch와 Mitzenmacher는 Bloom Filter에 필요한 여러 hash 위치를 두 hash의 선형 결합으로 생성해도 점근적 false-positive 성능을 유지할 수 있음을 보였다. 2
"False negative가 없다"는 말의 조건
"Bloom Filter에는 false negative가 없다"는 말은 조건부다. 수학적 구조가 보장하는 건 그 조건 안에서뿐이고, 조건은 이렇다.
삽입한 bit를 지운 적이 없고
동일한 key encoding과 hash 규칙을 쓰고
필터가 원본 집합의 원소를 하나도 빠뜨리지 않았고
bitset이 깨지지 않아야 한다.
이 조건 중 하나라도 깨지면 운영에서 false negative가 난다. 예를 들어 지금 원본에는 있는데 조회에 쓴 snapshot이 오래돼서 반영이 안 된 원소는 음성으로 떨어진다. 프로세스마다 hash protocol이 다른 경우도 같은데, 자료구조에 결함이 있는 게 아니라, 운영 환경이 안 맞아서 생기는 false negative인 거다.
트레이드오프와 한계
트레이드오프는 용량 계획과 기능 제한 쪽에 있다. 예상 원소 수를 넘겨서 계속 넣어도 자료구조가 당장 고장 나지는 않는데, 대신 bit 밀도가 올라가고 false-positive rate가 나빠진다. 정확성이 바로 깨지는 건 아니지만 Maybe 비율이 올라가서, 정확 조회를 생략하는 이득이 점점 줄어든다. 삭제, 열거, 정확한 원소 수 계산은 애초에 기본 Bloom Filter가 책임지는 일이 아니다.
Bloom Filter
= 고정 크기 bit 배열
+ k개의 결정적 bit 위치
Add(x):
각 index_i(x)의 bit를 1로 설정
MightContain(x):
모든 index_i(x)의 bit가 1
→ Maybe
하나라도 0
→ Definitely Not
설계식:
m ≈ -n · ln(p) / (ln 2)²
k ≈ (m / n) · ln 2
n = 예상 삽입 수
m = bit 수
k = hash 위치 수
p = 목표 false-positive rate
예상 false-positive rate:
p̂ = (1 - e^(-kn/m))^k1. 문제 시나리오
빌드 시스템이 content-addressed artifact 저장소를 쓴다고 치자.
Artifact ID:
SHA-256 digest 32 bytes
정확한 저장소:
원격 object storage
비싼 연산:
HEAD 또는 metadata DB 조회
Catalog snapshot:
특정 catalogVersion에 존재하는
모든 artifact digest의 목록Read path는 이런 흐름이다.
1. Artifact digest 형식 검증
2. Bloom Filter 조회
Definitely Not
→ 원격 I/O 없이 absent 반환
Maybe
→ 정확한 repository 조회
→ 실제 존재 여부 반환예를 들어 snapshot에 천만 개 artifact가 있고, 없는 digest를 조회하는 요청이 대부분이라 치자. 그러면 Bloom Filter가 원격 HEAD 요청을 대량으로 걷어낼 수 있다고 가정해볼 만하다. 다만 다음 구현은 안 된다.
Bloom Filter가 Maybe 반환
→ artifact가 존재한다고 바로 반환Maybe는 정확한 membership이 아니다. filter가 catalogVersion=42를 기준으로 만들어졌다면, 음성 결과도 같은 version의 catalog에서만 유효하다.
Filter version:
42
Repository query version:
43
Version 43에서 새로 추가된 artifact
→ Filter 42에는 bit가 없음
→ 운영상 false negative그래서 snapshot에는 다음 계약을 같이 묶는다.
ArtifactIndexSnapshot
- catalogVersion
- expectedItemCount
- insertedItemCount
- targetFalsePositiveRate
- bitCount
- hashCount
- hashProtocolVersion
- bitset2. 핵심 표현
C++23
C++ 구현은 32-byte digest를 값 타입으로 들고 있고, filter 내부는 uint64_t word 배열이며, 생성된 뒤에는 mutation API가 없다.
#include <algorithm>
#include <array>
#include <bit>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <expected>
#include <limits>
#include <span>
#include <utility>
#include <vector>
class ArtifactDigest final
{
public:
static constexpr std::size_t byteCount = 32;
explicit ArtifactDigest(
std::array<std::byte, byteCount> bytes) noexcept
: bytes_(std::move(bytes))
{
}
[[nodiscard]]
std::span<const std::byte, byteCount>
getBytes() const noexcept
{
return bytes_;
}
private:
std::array<std::byte, byteCount> bytes_;
};
struct BloomSpec final
{
std::size_t expectedItemCount;
double targetFalsePositiveRate;
};
enum class BloomError
{
InvalidExpectedItemCount,
InvalidFalsePositiveRate,
CapacityExceeded,
FilterTooLarge,
};
template<typename T>
using BloomResult = std::expected<T, BloomError>;
class ArtifactBloomFilter final
{
public:
[[nodiscard]]
static BloomResult<ArtifactBloomFilter> create(
std::span<const ArtifactDigest> digests,
const BloomSpec& spec)
{
auto layout = createLayout(spec);
if (!layout)
{
return std::unexpected(layout.error());
}
if (digests.size() > spec.expectedItemCount)
{
return std::unexpected(
BloomError::CapacityExceeded);
}
ArtifactBloomFilter filter{
*layout,
digests.size()};
for (const ArtifactDigest& digest : digests)
{
filter.addDigest(digest);
}
return filter;
}
[[nodiscard]]
bool mightContain(
const ArtifactDigest& digest) const noexcept
{
Probe probe = createProbe(digest);
for (std::uint32_t index = 0;
index < hashCount_;
++index)
{
if (!getBit(probe.bitIndex))
{
return false;
}
probe.advance(bitCount_);
}
return true;
}
[[nodiscard]]
std::size_t getBitCount() const noexcept
{
return bitCount_;
}
[[nodiscard]]
std::uint32_t getHashCount() const noexcept
{
return hashCount_;
}
[[nodiscard]]
std::size_t getInsertedItemCount() const noexcept
{
return insertedItemCount_;
}
[[nodiscard]]
double estimateFalsePositiveRate() const noexcept
{
const double m =
static_cast<double>(bitCount_);
const double n =
static_cast<double>(insertedItemCount_);
const double k =
static_cast<double>(hashCount_);
return std::pow(
-std::expm1(-k * n / m),
k);
}
[[nodiscard]]
double getFillRatio() const noexcept
{
std::size_t setBitCount = 0;
for (const std::uint64_t word : words_)
{
setBitCount +=
std::popcount(word);
}
return static_cast<double>(setBitCount)
/ static_cast<double>(bitCount_);
}
[[nodiscard]]
std::vector<std::byte> serializeBits() const
{
std::vector<std::byte> bytes;
bytes.reserve(bitCount_ / 8);
for (const std::uint64_t word : words_)
{
for (std::size_t shift = 0;
shift < 64;
shift += 8)
{
bytes.push_back(
static_cast<std::byte>(
(word >> shift) & 0xFFULL));
}
}
return bytes;
}
private:
static constexpr double ln2 =
0.69314718055994530942;
static constexpr std::size_t minimumBitCount =
64;
static constexpr std::size_t maximumExpectedItemCount =
std::size_t{1} << 30;
static constexpr std::size_t maximumBitCount =
std::size_t{1} << 30;
struct Layout final
{
std::size_t bitCount;
std::uint32_t hashCount;
};
struct Probe final
{
std::size_t bitIndex;
std::size_t step;
void advance(std::size_t bitCount) noexcept
{
bitIndex += step;
if (bitIndex >= bitCount)
{
bitIndex -= bitCount;
}
}
};
std::vector<std::uint64_t> words_;
std::size_t bitCount_;
std::uint32_t hashCount_;
std::size_t insertedItemCount_;
ArtifactBloomFilter(
const Layout& layout,
std::size_t insertedItemCount)
: words_(layout.bitCount / 64, 0),
bitCount_(layout.bitCount),
hashCount_(layout.hashCount),
insertedItemCount_(insertedItemCount)
{
}
void addDigest(
const ArtifactDigest& digest) noexcept
{
Probe probe = createProbe(digest);
for (std::uint32_t index = 0;
index < hashCount_;
++index)
{
setBit(probe.bitIndex);
probe.advance(bitCount_);
}
}
[[nodiscard]]
Probe createProbe(
const ArtifactDigest& digest) const noexcept
{
const auto bytes = digest.getBytes();
const std::uint64_t first =
readU64BigEndian(bytes.first<8>());
const std::uint64_t second =
readU64BigEndian(
bytes.subspan<8, 8>());
return Probe{
.bitIndex =
static_cast<std::size_t>(
first % bitCount_),
.step =
static_cast<std::size_t>(
(second | 1ULL) % bitCount_),
};
}
void setBit(std::size_t bitIndex) noexcept
{
const std::size_t wordIndex =
bitIndex >> 6;
const std::size_t bitOffset =
bitIndex & 63;
words_[wordIndex] |=
std::uint64_t{1} << bitOffset;
}
[[nodiscard]]
bool getBit(std::size_t bitIndex) const noexcept
{
const std::size_t wordIndex =
bitIndex >> 6;
const std::size_t bitOffset =
bitIndex & 63;
return (
words_[wordIndex]
& (std::uint64_t{1} << bitOffset)
) != 0;
}
[[nodiscard]]
static BloomResult<Layout> createLayout(
const BloomSpec& spec)
{
auto idealBitCount =
calculateIdealBitCount(spec);
if (!idealBitCount)
{
return std::unexpected(
idealBitCount.error());
}
Layout bestLayout{};
bool foundLayout = false;
for (std::uint32_t hashCount = 1;
hashCount <= 32;
++hashCount)
{
auto requiredBitCount =
calculateRequiredBitCountForHashCount(
spec.expectedItemCount,
hashCount,
spec.targetFalsePositiveRate);
if (!requiredBitCount)
{
continue;
}
std::size_t candidateBitCount =
alignToWord(
std::max(
minimumBitCount,
*requiredBitCount));
if (candidateBitCount > maximumBitCount)
{
continue;
}
double modeledRate =
calculateModeledFalsePositiveRate(
candidateBitCount,
spec.expectedItemCount,
hashCount);
if (!std::isfinite(modeledRate)
|| modeledRate
> spec.targetFalsePositiveRate)
{
if (candidateBitCount
> maximumBitCount - 64)
{
continue;
}
candidateBitCount += 64;
modeledRate =
calculateModeledFalsePositiveRate(
candidateBitCount,
spec.expectedItemCount,
hashCount);
}
if (std::isfinite(modeledRate)
&& modeledRate
<= spec.targetFalsePositiveRate)
{
const Layout candidateLayout{
.bitCount = candidateBitCount,
.hashCount = hashCount,
};
if (!foundLayout
|| candidateLayout.bitCount
< bestLayout.bitCount
|| (candidateLayout.bitCount
== bestLayout.bitCount
&& candidateLayout.hashCount
< bestLayout.hashCount))
{
bestLayout = candidateLayout;
foundLayout = true;
}
}
}
if (foundLayout)
{
return bestLayout;
}
return std::unexpected(
BloomError::FilterTooLarge);
}
[[nodiscard]]
static BloomResult<std::size_t>
calculateIdealBitCount(
const BloomSpec& spec)
{
if (spec.expectedItemCount == 0
|| spec.expectedItemCount
> maximumExpectedItemCount)
{
return std::unexpected(
BloomError::InvalidExpectedItemCount);
}
if (!std::isfinite(
spec.targetFalsePositiveRate)
|| spec.targetFalsePositiveRate <= 0.0
|| spec.targetFalsePositiveRate >= 1.0)
{
return std::unexpected(
BloomError::InvalidFalsePositiveRate);
}
const double ideal =
-static_cast<double>(
spec.expectedItemCount)
* std::log(
spec.targetFalsePositiveRate)
/ (ln2 * ln2);
if (!std::isfinite(ideal)
|| ideal > static_cast<double>(
maximumBitCount))
{
return std::unexpected(
BloomError::FilterTooLarge);
}
return std::max(
minimumBitCount,
static_cast<std::size_t>(
std::ceil(ideal)));
}
[[nodiscard]]
static BloomResult<std::size_t>
calculateRequiredBitCountForHashCount(
std::size_t itemCount,
std::uint32_t hashCount,
double targetRate)
{
const double n =
static_cast<double>(itemCount);
const double k =
static_cast<double>(hashCount);
const double root =
std::pow(targetRate, 1.0 / k);
const double denominator =
-std::log1p(-root);
const double required =
k * n / denominator;
if (!std::isfinite(required)
|| required > static_cast<double>(
maximumBitCount))
{
return std::unexpected(
BloomError::FilterTooLarge);
}
return std::max(
minimumBitCount,
static_cast<std::size_t>(
std::ceil(required)));
}
[[nodiscard]]
static double calculateModeledFalsePositiveRate(
std::size_t bitCount,
std::size_t itemCount,
std::uint32_t hashCount) noexcept
{
const double m =
static_cast<double>(bitCount);
const double n =
static_cast<double>(itemCount);
const double k =
static_cast<double>(hashCount);
return std::pow(
-std::expm1(-k * n / m),
k);
}
[[nodiscard]]
static std::size_t alignToWord(
std::size_t value) noexcept
{
return (value + 63) & ~std::size_t{63};
}
[[nodiscard]]
static std::uint64_t readU64BigEndian(
std::span<const std::byte, 8> bytes) noexcept
{
std::uint64_t result = 0;
for (const std::byte value : bytes)
{
result =
(result << 8)
| std::to_integer<std::uint8_t>(
value);
}
return result;
}
};호출 방식:
const BloomSpec spec{
.expectedItemCount = 1'000'000,
.targetFalsePositiveRate = 0.001,
};
const auto filterResult =
ArtifactBloomFilter::create(
artifactDigests,
spec);
if (!filterResult)
{
return filterResult.error();
}
const ArtifactBloomFilter filter =
std::move(*filterResult);
if (!filter.mightContain(requestedDigest))
{
return ArtifactLookup::absent();
}
// Maybe이므로 정확한 저장소를 확인한다.
return repository.exists(requestedDigest);ArtifactBloomFilter가 digest를 보관하지 않으므로 입력 span의 수명은 생성 호출까지만 유지되면 된다. 반환된 filter는 bitset을 직접 소유하게 된다.
또한 serializeBits()는 uint64_t word 배열을 little-endian byte 열로 내보내, byte 배열을 쓰는 나머지 세 구현과 같은 표현을 만든다.
개인적인 메모: 이 코드가 중국인이 짠 코드인데, 어디서 찾아서 저장해뒀는지 모르겠다.
Python
Python은 만드는 중에는 bytearray를 쓰고, 완성된 filter에는 immutable bytes를 담는다.
from __future__ import annotations
from dataclasses import dataclass
from enum import Enum
from math import ceil, expm1, isfinite, log, log1p
from typing import Generic, Sequence, TypeAlias, TypeVar
TValue = TypeVar("TValue")
_DIGEST_LENGTH = 32
_MINIMUM_BIT_COUNT = 64
_MAXIMUM_EXPECTED_ITEM_COUNT = 1 << 30
_MAXIMUM_BIT_COUNT = 1 << 30
_LN2 = 0.6931471805599453
class BloomError(str, Enum):
INVALID_EXPECTED_ITEM_COUNT = (
"invalid_expected_item_count"
)
INVALID_FALSE_POSITIVE_RATE = (
"invalid_false_positive_rate"
)
CAPACITY_EXCEEDED = "capacity_exceeded"
FILTER_TOO_LARGE = "filter_too_large"
INVALID_DIGEST = "invalid_digest"
@dataclass(frozen=True, slots=True)
class Success(Generic[TValue]):
value: TValue
@dataclass(frozen=True, slots=True)
class Failure:
error: BloomError
Result: TypeAlias = Success[TValue] | Failure
@dataclass(frozen=True, slots=True)
class BloomSpec:
expected_item_count: int
target_false_positive_rate: float
@dataclass(frozen=True, slots=True)
class _Layout:
bit_count: int
hash_count: int
class ArtifactBloomFilter:
def __init__(
self,
bits: bytes,
bit_count: int,
hash_count: int,
inserted_item_count: int,
) -> None:
self._bits = bits
self._bit_count = bit_count
self._hash_count = hash_count
self._inserted_item_count = (
inserted_item_count
)
@classmethod
def create(
cls,
digests: Sequence[bytes],
spec: BloomSpec,
) -> Result[ArtifactBloomFilter]:
layout_result = _create_layout(spec)
if isinstance(layout_result, Failure):
return layout_result
if len(digests) > spec.expected_item_count:
return Failure(
BloomError.CAPACITY_EXCEEDED
)
normalized_digests: list[bytes] = []
for digest in digests:
normalized = _normalize_digest(digest)
if normalized is None:
return Failure(
BloomError.INVALID_DIGEST
)
normalized_digests.append(normalized)
layout = layout_result.value
bits = bytearray(layout.bit_count // 8)
for digest in normalized_digests:
_add_digest(
bits,
layout,
digest,
)
return Success(
cls(
bits=bytes(bits),
bit_count=layout.bit_count,
hash_count=layout.hash_count,
inserted_item_count=len(digests),
)
)
def might_contain(
self,
digest: bytes,
) -> bool:
normalized = _normalize_digest(digest)
if normalized is None:
raise ValueError(
"Artifact digest는 32-byte여야 합니다."
)
bit_index, step = _create_probe(
normalized,
self._bit_count,
)
for _ in range(self._hash_count):
if not _get_bit(
self._bits,
bit_index,
):
return False
bit_index = (
bit_index + step
) % self._bit_count
return True
def get_bit_count(self) -> int:
return self._bit_count
def get_hash_count(self) -> int:
return self._hash_count
def get_inserted_item_count(self) -> int:
return self._inserted_item_count
def estimate_false_positive_rate(
self,
) -> float:
m = float(self._bit_count)
n = float(self._inserted_item_count)
k = float(self._hash_count)
return (
-expm1(-k * n / m)
) ** k
def get_fill_ratio(self) -> float:
set_bit_count = sum(
value.bit_count()
for value in self._bits
)
return (
set_bit_count
/ self._bit_count
)
def _create_layout(
spec: BloomSpec,
) -> Result[_Layout]:
validation = _validate_spec(spec)
if validation is not None:
return Failure(validation)
ideal = (
-spec.expected_item_count
* log(spec.target_false_positive_rate)
/ (_LN2 * _LN2)
)
if (
not isfinite(ideal)
or ideal > _MAXIMUM_BIT_COUNT
):
return Failure(
BloomError.FILTER_TOO_LARGE
)
best_layout: _Layout | None = None
for hash_count in range(1, 33):
required_bit_count = (
_calculate_required_bit_count_for_hash_count(
spec.expected_item_count,
hash_count,
spec.target_false_positive_rate,
)
)
if required_bit_count is None:
continue
candidate_bit_count = _align_to_word(
max(
_MINIMUM_BIT_COUNT,
required_bit_count,
)
)
if candidate_bit_count > _MAXIMUM_BIT_COUNT:
continue
modeled_rate = _modeled_false_positive_rate(
candidate_bit_count,
spec.expected_item_count,
hash_count,
)
if (
not isfinite(modeled_rate)
or modeled_rate
> spec.target_false_positive_rate
):
if candidate_bit_count > _MAXIMUM_BIT_COUNT - 64:
continue
candidate_bit_count += 64
modeled_rate = _modeled_false_positive_rate(
candidate_bit_count,
spec.expected_item_count,
hash_count,
)
if (
not isfinite(modeled_rate)
or modeled_rate
> spec.target_false_positive_rate
):
continue
candidate_layout = _Layout(
bit_count=candidate_bit_count,
hash_count=hash_count,
)
if (
best_layout is None
or candidate_layout.bit_count
< best_layout.bit_count
or (
candidate_layout.bit_count
== best_layout.bit_count
and candidate_layout.hash_count
< best_layout.hash_count
)
):
best_layout = candidate_layout
if best_layout is not None:
return Success(best_layout)
return Failure(BloomError.FILTER_TOO_LARGE)
def _validate_spec(
spec: BloomSpec,
) -> BloomError | None:
if (
type(spec.expected_item_count) is not int
or not (
1
<= spec.expected_item_count
<= _MAXIMUM_EXPECTED_ITEM_COUNT
)
):
return BloomError.INVALID_EXPECTED_ITEM_COUNT
rate = spec.target_false_positive_rate
if not _is_real_number(rate):
return BloomError.INVALID_FALSE_POSITIVE_RATE
if rate <= 0.0 or rate >= 1.0:
return BloomError.INVALID_FALSE_POSITIVE_RATE
try:
rate_as_float = float(rate)
except (OverflowError, ValueError):
return BloomError.INVALID_FALSE_POSITIVE_RATE
if not isfinite(rate_as_float):
return BloomError.INVALID_FALSE_POSITIVE_RATE
return None
def _is_real_number(
value: object,
) -> bool:
return (
isinstance(value, (int, float))
and not isinstance(value, bool)
)
def _calculate_required_bit_count_for_hash_count(
item_count: int,
hash_count: int,
target_rate: float,
) -> int | None:
n = float(item_count)
k = float(hash_count)
root = target_rate ** (1.0 / k)
denominator = -log1p(-root)
required = k * n / denominator
if (
not isfinite(required)
or required > _MAXIMUM_BIT_COUNT
):
return None
return max(
_MINIMUM_BIT_COUNT,
ceil(required),
)
def _add_digest(
bits: bytearray,
layout: _Layout,
digest: bytes,
) -> None:
bit_index, step = _create_probe(
digest,
layout.bit_count,
)
for _ in range(layout.hash_count):
_set_bit(bits, bit_index)
bit_index = (
bit_index + step
) % layout.bit_count
def _create_probe(
digest: bytes,
bit_count: int,
) -> tuple[int, int]:
first = int.from_bytes(
digest[0:8],
byteorder="big",
signed=False,
)
second = int.from_bytes(
digest[8:16],
byteorder="big",
signed=False,
)
step = (second | 1) % bit_count
return first % bit_count, step
def _set_bit(
bits: bytearray,
bit_index: int,
) -> None:
byte_index = bit_index >> 3
bit_offset = bit_index & 7
bits[byte_index] |= (
1 << bit_offset
)
def _get_bit(
bits: bytes,
bit_index: int,
) -> bool:
byte_index = bit_index >> 3
bit_offset = bit_index & 7
return (
bits[byte_index]
& (1 << bit_offset)
) != 0
def _align_to_word(
value: int,
) -> int:
return (value + 63) & ~63
def _modeled_false_positive_rate(
bit_count: int,
item_count: int,
hash_count: int,
) -> float:
m = float(bit_count)
n = float(item_count)
k = float(hash_count)
return (-expm1(-k * n / m)) ** k
def _normalize_digest(
digest: object,
) -> bytes | None:
if not isinstance(
digest,
(bytes, bytearray, memoryview),
):
return None
try:
normalized = bytes(digest)
except (TypeError, ValueError):
return None
return (
normalized
if len(normalized) == _DIGEST_LENGTH
else None
)Python에서는 digest 타입만 보고 판단하면 부족한데, memoryview의 len()이 항상 바이트 수는 아니다. 32개의 uint16 원소를 감싼 view는 len(view) == 32인데 실제 바이트 수는 64다.
_normalize_digest()가 먼저 bytes()로 복사하고 나서 길이를 보는 이유가 그거다.
이 경계(Boundary) 부분은 회귀 테스트로 남겨둘 만하다.
from array import array
view = memoryview(array("H", [0] * 32))
result = ArtifactBloomFilter.create(
[view],
BloomSpec(
expected_item_count=1,
target_false_positive_rate=0.01,
),
)
assert result == Failure(BloomError.INVALID_DIGEST)
assert ArtifactBloomFilter.create(
[],
BloomSpec(
expected_item_count=10**1000,
target_false_positive_rate=0.01,
),
) == Failure(BloomError.INVALID_EXPECTED_ITEM_COUNT)
assert ArtifactBloomFilter.create(
[],
BloomSpec(
expected_item_count=1,
target_false_positive_rate=10**1000,
),
) == Failure(BloomError.INVALID_FALSE_POSITIVE_RATE)큰 Python 정수가 들어와도 float()를 먼저 부르지 않고 범위와 경계부터 본다. 그래서 OverflowError가 API 밖으로 새지 않으며, 원소 상한은 다른 구현과 같은 2³⁰이다.
호출:
spec = BloomSpec(
expected_item_count=1_000_000,
target_false_positive_rate=0.001,
)
filter_result = ArtifactBloomFilter.create(
artifact_digests,
spec,
)
if isinstance(filter_result, Failure):
raise ValueError(filter_result.error)
artifact_filter = filter_result.value
if not artifact_filter.might_contain(
requested_digest
):
return False
return await repository.exists_async(
requested_digest,
catalog_version,
)순수 Python query loop가 hot path 전체라면, bit 검사보다 interpreter 비용이 더 크게 잡힐 수 있는데,
대규모 batch 조회라면 native extension, NumPy vectorization, 저장소가 제공하는 검증된 Bloom 구현을 놓고 비교해야 한다.
C#
C# 구현은 완성된 byte[]을 private으로 갖고 있고, 외부에 mutable view를 돌려주지 않는다.
using System;
using System.Buffers.Binary;
using System.Collections.Generic;
using System.Numerics;
public readonly record struct BloomSpec(
int ExpectedItemCount,
double TargetFalsePositiveRate);
public enum BloomError
{
InvalidExpectedItemCount,
InvalidFalsePositiveRate,
CapacityExceeded,
FilterTooLarge,
InvalidDigest,
}
public abstract record BloomResult<T>
{
public abstract bool TryGetValue(
out T value,
out BloomError error);
}
public sealed record BloomSuccess<T>(T Value)
: BloomResult<T>
{
public override bool TryGetValue(
out T value,
out BloomError error)
{
value = this.Value;
error = default;
return true;
}
}
public sealed record BloomFailure<T>(BloomError Error)
: BloomResult<T>
{
public override bool TryGetValue(
out T value,
out BloomError error)
{
value = default!;
error = this.Error;
return false;
}
}
public sealed class ArtifactBloomFilter
{
private const int DigestLength = 32;
private const int MinimumBitCount = 64;
private const int MaximumExpectedItemCount =
1 << 30;
private const int MaximumBitCount = 1 << 30;
private const double Ln2 =
0.6931471805599453;
private readonly byte[] bits;
private readonly int bitCount;
private readonly int hashCount;
private readonly int insertedItemCount;
private ArtifactBloomFilter(
byte[] bits,
int bitCount,
int hashCount,
int insertedItemCount)
{
this.bits = bits;
this.bitCount = bitCount;
this.hashCount = hashCount;
this.insertedItemCount = insertedItemCount;
}
public static BloomResult<ArtifactBloomFilter> Create(
IReadOnlyList<byte[]> digests,
BloomSpec spec)
{
if (digests is null)
{
return Failure(
BloomError.InvalidDigest);
}
if (!CreateLayout(spec).TryGetValue(
out Layout layout,
out BloomError layoutError))
{
return Failure(layoutError);
}
return Build(
digests,
spec,
layout);
}
private static BloomResult<ArtifactBloomFilter> Build(
IReadOnlyList<byte[]> digests,
BloomSpec spec,
Layout layout)
{
if (digests.Count > spec.ExpectedItemCount)
{
return Failure(
BloomError.CapacityExceeded);
}
if (!AllDigestsAreValid(digests))
{
return Failure(
BloomError.InvalidDigest);
}
byte[] bits =
new byte[layout.BitCount / 8];
foreach (byte[] digest in digests)
{
AddDigest(
bits,
layout,
digest);
}
return new BloomSuccess<ArtifactBloomFilter>(
new ArtifactBloomFilter(
bits,
layout.BitCount,
layout.HashCount,
digests.Count));
}
public bool MightContain(
ReadOnlySpan<byte> digest)
{
if (digest.Length != DigestLength)
{
throw new ArgumentException(
"Artifact digest는 32-byte여야 합니다.",
nameof(digest));
}
Probe probe =
CreateProbe(
digest,
this.bitCount);
for (
int index = 0;
index < this.hashCount;
index += 1)
{
if (!GetBit(
this.bits,
probe.GetBitIndex()))
{
return false;
}
probe.Advance(this.bitCount);
}
return true;
}
public int GetBitCount()
{
return this.bitCount;
}
public int GetHashCount()
{
return this.hashCount;
}
public int GetInsertedItemCount()
{
return this.insertedItemCount;
}
public double EstimateFalsePositiveRate()
{
double m = this.bitCount;
double n = this.insertedItemCount;
double k = this.hashCount;
return Math.Pow(
-ExponentialMinusOne(-k * n / m),
k);
}
public double GetFillRatio()
{
long setBitCount = 0;
foreach (byte value in this.bits)
{
setBitCount +=
BitOperations.PopCount(
(uint)value);
}
return (double)setBitCount
/ this.bitCount;
}
private static BloomResult<Layout> CreateLayout(
BloomSpec spec)
{
BloomError? error =
ValidateSpec(spec);
if (error is not null)
{
return new BloomFailure<Layout>(
error.Value);
}
double ideal =
-spec.ExpectedItemCount
* Math.Log(
spec.TargetFalsePositiveRate)
/ (Ln2 * Ln2);
if (!double.IsFinite(ideal)
|| ideal > MaximumBitCount)
{
return new BloomFailure<Layout>(
BloomError.FilterTooLarge);
}
Layout? bestLayout = null;
for (int hashCount = 1;
hashCount <= 32;
hashCount += 1)
{
double requiredBitCount =
CalculateRequiredBitCountForHashCount(
spec.ExpectedItemCount,
hashCount,
spec.TargetFalsePositiveRate);
if (!double.IsFinite(requiredBitCount)
|| requiredBitCount
> MaximumBitCount)
{
continue;
}
int candidateBitCount = AlignToWord(
Math.Max(
MinimumBitCount,
checked((int)Math.Ceiling(
requiredBitCount))));
if (candidateBitCount > MaximumBitCount)
{
continue;
}
double modeledRate =
CalculateModeledFalsePositiveRate(
candidateBitCount,
spec.ExpectedItemCount,
hashCount);
if (!double.IsFinite(modeledRate)
|| modeledRate
> spec.TargetFalsePositiveRate)
{
if (candidateBitCount
> MaximumBitCount - 64)
{
continue;
}
candidateBitCount += 64;
modeledRate =
CalculateModeledFalsePositiveRate(
candidateBitCount,
spec.ExpectedItemCount,
hashCount);
}
if (double.IsFinite(modeledRate)
&& modeledRate
<= spec.TargetFalsePositiveRate)
{
Layout candidateLayout = new(
candidateBitCount,
hashCount);
if (bestLayout is null
|| candidateLayout.BitCount
< bestLayout.Value.BitCount
|| (candidateLayout.BitCount
== bestLayout.Value.BitCount
&& candidateLayout.HashCount
< bestLayout.Value.HashCount))
{
bestLayout = candidateLayout;
}
}
}
if (bestLayout is not null)
{
return new BloomSuccess<Layout>(
bestLayout.Value);
}
return new BloomFailure<Layout>(
BloomError.FilterTooLarge);
}
private static BloomError? ValidateSpec(
BloomSpec spec)
{
if (spec.ExpectedItemCount < 1
|| spec.ExpectedItemCount
> MaximumExpectedItemCount)
{
return BloomError.InvalidExpectedItemCount;
}
double rate =
spec.TargetFalsePositiveRate;
if (!double.IsFinite(rate)
|| rate <= 0.0
|| rate >= 1.0)
{
return BloomError.InvalidFalsePositiveRate;
}
return null;
}
private static double
CalculateRequiredBitCountForHashCount(
int itemCount,
int hashCount,
double targetRate)
{
double n = itemCount;
double k = hashCount;
double root =
Math.Pow(targetRate, 1.0 / k);
double denominator =
-LogOneMinus(root);
return k * n / denominator;
}
private static double
CalculateModeledFalsePositiveRate(
int bitCount,
int itemCount,
int hashCount)
{
double m = bitCount;
double n = itemCount;
double k = hashCount;
return Math.Pow(
-ExponentialMinusOne(-k * n / m),
k);
}
private static double LogOneMinus(
double value)
{
if (Math.Abs(value) >= 0.0001)
{
return Math.Log(1.0 - value);
}
double term = value;
double sum = 0.0;
for (int index = 1; index <= 8; index += 1)
{
sum -= term / index;
term *= value;
}
return sum;
}
private static double ExponentialMinusOne(
double value)
{
if (Math.Abs(value) >= 0.0001)
{
return Math.Exp(value) - 1.0;
}
double term = value;
double sum = value;
for (int index = 2; index <= 8; index += 1)
{
term *= value / index;
sum += term;
}
return sum;
}
private static void AddDigest(
byte[] bits,
Layout layout,
ReadOnlySpan<byte> digest)
{
Probe probe =
CreateProbe(
digest,
layout.BitCount);
for (
int index = 0;
index < layout.HashCount;
index += 1)
{
SetBit(
bits,
probe.GetBitIndex());
probe.Advance(
layout.BitCount);
}
}
private static Probe CreateProbe(
ReadOnlySpan<byte> digest,
int bitCount)
{
ulong first =
BinaryPrimitives
.ReadUInt64BigEndian(
digest[..8]);
ulong second =
BinaryPrimitives
.ReadUInt64BigEndian(
digest[8..16]);
return new Probe(
(int)(first % (ulong)bitCount),
(int)((second | 1UL)
% (ulong)bitCount));
}
private static void SetBit(
byte[] bits,
int bitIndex)
{
int byteIndex = bitIndex >> 3;
int bitOffset = bitIndex & 7;
bits[byteIndex] |=
(byte)(1 << bitOffset);
}
private static bool GetBit(
byte[] bits,
int bitIndex)
{
int byteIndex = bitIndex >> 3;
int bitOffset = bitIndex & 7;
return (
bits[byteIndex]
& (1 << bitOffset)
) != 0;
}
private static bool AllDigestsAreValid(
IReadOnlyList<byte[]> digests)
{
foreach (byte[]? digest in digests)
{
if (digest is null
|| digest.Length != DigestLength)
{
return false;
}
}
return true;
}
private static int AlignToWord(int value)
{
return checked(
(value + 63) & ~63);
}
private static BloomFailure<ArtifactBloomFilter>
Failure(BloomError error)
{
return new BloomFailure<ArtifactBloomFilter>(
error);
}
private readonly record struct Layout(
int BitCount,
int HashCount);
private struct Probe
{
private int bitIndex;
private readonly int step;
public Probe(
int bitIndex,
int step)
{
this.bitIndex = bitIndex;
this.step = step;
}
public int GetBitIndex()
{
return this.bitIndex;
}
public void Advance(int bitCount)
{
this.bitIndex += this.step;
if (this.bitIndex >= bitCount)
{
this.bitIndex -= bitCount;
}
}
}
}호출:
BloomSpec spec = new(
ExpectedItemCount: 1_000_000,
TargetFalsePositiveRate: 0.001);
BloomResult<ArtifactBloomFilter> result =
ArtifactBloomFilter.Create(
artifactDigests,
spec);
if (result is
BloomFailure<ArtifactBloomFilter> failure)
{
return failure.Error;
}
ArtifactBloomFilter filter =
((BloomSuccess<ArtifactBloomFilter>)
result).Value;
if (!filter.MightContain(requestedDigest))
{
return false;
}
return await repository.ExistsAsync(
requestedDigest,
catalogVersion,
cancellationToken);ReadOnlySpan<byte>은 query 호출 동안만 빌리는 거라 filter가 digest를 들고 있지 않고, async state machine 안에 span을 넣지도 않는다. membership 계산을 동기로 끝내고 나서 repository I/O를 시작한다.
TypeScript
TypeScript 구현은 Uint8Array bitset을 private으로 갖고, 64-bit seed 계산에는 bigint를 쓴다.
export type BloomSpec = Readonly<{
expectedItemCount: number;
targetFalsePositiveRate: number;
}>;
export type BloomError =
| "invalidExpectedItemCount"
| "invalidFalsePositiveRate"
| "capacityExceeded"
| "filterTooLarge"
| "invalidDigest";
export type Result<TValue> =
| Readonly<{
kind: "success";
value: TValue;
}>
| Readonly<{
kind: "failure";
error: BloomError;
}>;
type Layout = Readonly<{
bitCount: number;
hashCount: number;
}>;
const bloomDigestLength = 32;
const minimumBloomBitCount = 64;
const maximumBloomExpectedItemCount =
2 ** 30;
const maximumBloomBitCount =
2 ** 30;
const bloomLn2 =
0.6931471805599453;
export class ArtifactBloomFilter
{
readonly #bits: Uint8Array;
readonly #bitCount: number;
readonly #hashCount: number;
readonly #insertedItemCount: number;
private constructor(
bits: Uint8Array,
layout: Layout,
insertedItemCount: number,
)
{
this.#bits = bits;
this.#bitCount = layout.bitCount;
this.#hashCount = layout.hashCount;
this.#insertedItemCount =
insertedItemCount;
}
public static create(
digests: readonly Uint8Array[],
spec: BloomSpec,
): Result<ArtifactBloomFilter>
{
const layoutResult =
createLayout(spec);
if (layoutResult.kind === "failure") {
return layoutResult;
}
if (digests.length
> spec.expectedItemCount) {
return failure(
"capacityExceeded",
);
}
if (!digests.every(isValidDigest)) {
return failure(
"invalidDigest",
);
}
const layout = layoutResult.value;
const bits =
new Uint8Array(
layout.bitCount / 8,
);
for (const digest of digests) {
addDigest(
bits,
layout,
digest,
);
}
return success(
new ArtifactBloomFilter(
bits,
layout,
digests.length,
),
);
}
public mightContain(
digest: Uint8Array,
): boolean
{
if (!isValidDigest(digest)) {
throw new RangeError(
"Artifact digest는 32-byte여야 합니다.",
);
}
const probe =
createProbe(
digest,
this.#bitCount,
);
let bitIndex =
probe.bitIndex;
for (
let index = 0;
index < this.#hashCount;
index += 1
) {
if (!getBit(
this.#bits,
bitIndex,
)) {
return false;
}
bitIndex += probe.step;
if (bitIndex >= this.#bitCount) {
bitIndex -= this.#bitCount;
}
}
return true;
}
public getBitCount(): number
{
return this.#bitCount;
}
public getHashCount(): number
{
return this.#hashCount;
}
public getInsertedItemCount(): number
{
return this.#insertedItemCount;
}
public estimateFalsePositiveRate(): number
{
const m = this.#bitCount;
const n = this.#insertedItemCount;
const k = this.#hashCount;
return (
-Math.expm1(-k * n / m)
) ** k;
}
public getFillRatio(): number
{
let setBitCount = 0;
for (const value of this.#bits) {
setBitCount +=
popCountByte(value);
}
return setBitCount
/ this.#bitCount;
}
public serializeBits(): Uint8Array
{
return this.#bits.slice();
}
}
function createLayout(
spec: BloomSpec,
): Result<Layout>
{
const validation =
validateSpec(spec);
if (validation !== undefined) {
return failure(validation);
}
const ideal =
-spec.expectedItemCount
* Math.log(
spec.targetFalsePositiveRate,
)
/ (bloomLn2 * bloomLn2);
if (!Number.isFinite(ideal)
|| ideal > maximumBloomBitCount) {
return failure(
"filterTooLarge",
);
}
let bestLayout: Layout | undefined;
for (let hashCount = 1;
hashCount <= 32;
hashCount += 1) {
const requiredBitCount =
calculateRequiredBitCountForHashCount(
spec.expectedItemCount,
hashCount,
spec.targetFalsePositiveRate,
);
if (!Number.isFinite(requiredBitCount)
|| requiredBitCount > maximumBloomBitCount) {
continue;
}
let candidateBitCount = alignToWord(
Math.max(
minimumBloomBitCount,
Math.ceil(requiredBitCount),
),
);
if (candidateBitCount > maximumBloomBitCount) {
continue;
}
let modeledRate =
modeledFalsePositiveRate(
candidateBitCount,
spec.expectedItemCount,
hashCount,
);
if (!Number.isFinite(modeledRate)
|| modeledRate
> spec.targetFalsePositiveRate) {
if (candidateBitCount
> maximumBloomBitCount - 64) {
continue;
}
candidateBitCount += 64;
modeledRate =
modeledFalsePositiveRate(
candidateBitCount,
spec.expectedItemCount,
hashCount,
);
}
if (Number.isFinite(modeledRate)
&& modeledRate
<= spec.targetFalsePositiveRate) {
const candidateLayout = {
bitCount: candidateBitCount,
hashCount,
};
if (bestLayout === undefined
|| candidateLayout.bitCount
< bestLayout.bitCount
|| (candidateLayout.bitCount
=== bestLayout.bitCount
&& candidateLayout.hashCount
< bestLayout.hashCount)) {
bestLayout = candidateLayout;
}
}
}
if (bestLayout !== undefined) {
return success(bestLayout);
}
return failure("filterTooLarge");
}
function validateSpec(
spec: BloomSpec,
): BloomError | undefined
{
if (!Number.isSafeInteger(
spec.expectedItemCount)
|| spec.expectedItemCount < 1
|| spec.expectedItemCount
> maximumBloomExpectedItemCount) {
return "invalidExpectedItemCount";
}
const rate =
spec.targetFalsePositiveRate;
if (!Number.isFinite(rate)
|| rate <= 0
|| rate >= 1) {
return "invalidFalsePositiveRate";
}
return undefined;
}
function calculateRequiredBitCountForHashCount(
itemCount: number,
hashCount: number,
targetRate: number,
): number
{
const n = itemCount;
const k = hashCount;
const root =
Math.exp(Math.log(targetRate) / k);
const denominator =
-Math.log1p(-root);
return k * n / denominator;
}
function modeledFalsePositiveRate(
bitCount: number,
itemCount: number,
hashCount: number,
): number
{
const m = bitCount;
const n = itemCount;
const k = hashCount;
return (
-Math.expm1(-k * n / m)
) ** k;
}
function addDigest(
bits: Uint8Array,
layout: Layout,
digest: Uint8Array,
): void
{
const probe =
createProbe(
digest,
layout.bitCount,
);
let bitIndex =
probe.bitIndex;
for (
let index = 0;
index < layout.hashCount;
index += 1
) {
setBit(bits, bitIndex);
bitIndex += probe.step;
if (bitIndex >= layout.bitCount) {
bitIndex -= layout.bitCount;
}
}
}
function createProbe(
digest: Uint8Array,
bitCount: number,
): Readonly<{
bitIndex: number;
step: number;
}>
{
const first =
readU64BigEndian(
digest,
0,
);
const second =
readU64BigEndian(
digest,
8,
);
const modulus =
BigInt(bitCount);
return {
bitIndex:
Number(first % modulus),
step:
Number((second | 1n) % modulus),
};
}
function readU64BigEndian(
bytes: Uint8Array,
offset: number,
): bigint
{
let result = 0n;
for (
let index = 0;
index < 8;
index += 1
) {
result =
(result << 8n)
| BigInt(bytes[offset + index]);
}
return result;
}
function setBit(
bits: Uint8Array,
bitIndex: number,
): void
{
const byteIndex =
bitIndex >> 3;
const bitOffset =
bitIndex & 7;
bits[byteIndex] |=
1 << bitOffset;
}
function getBit(
bits: Uint8Array,
bitIndex: number,
): boolean
{
const byteIndex =
bitIndex >> 3;
const bitOffset =
bitIndex & 7;
return (
bits[byteIndex]
& (1 << bitOffset)
) !== 0;
}
function popCountByte(
value: number,
): number
{
let current = value;
let count = 0;
while (current !== 0) {
current &= current - 1;
count += 1;
}
return count;
}
function alignToWord(
value: number,
): number
{
const remainder =
value % 64;
return remainder === 0
? value
: value + 64 - remainder;
}
function isValidDigest(
digest: Uint8Array,
): boolean
{
return digest instanceof Uint8Array
&& digest.byteLength
=== bloomDigestLength;
}
function success<TValue>(
value: TValue,
): Result<TValue>
{
return {
kind: "success",
value,
};
}
function failure<TValue = never>(
error: BloomError,
): Result<TValue>
{
return {
kind: "failure",
error,
};
}TypeScript의 #private field는 class 밖에서 못 건드린다. 그래서 여러 free function이 같이 쓰는 상수는 class static private field가 아니라 module scope에 둬야 한다. bloomDigestLength, minimumBloomBitCount, maximumBloomBitCount, bloomLn2가 거기 있다.
호출:
const result =
ArtifactBloomFilter.create(
artifactDigests,
{
expectedItemCount: 1_000_000,
targetFalsePositiveRate: 0.001,
},
);
if (result.kind === "failure") {
throw new Error(result.error);
}
const filter = result.value;
if (!filter.mightContain(
requestedDigest,
)) {
return false;
}
return await repository.existsAsync(
requestedDigest,
catalogVersion,
signal,
);3. 호출부
Bloom Filter의 음성 결과를 믿으려면, filter와 정확 저장소가 같은 catalog snapshot을 가리켜야 한다.
export type CatalogVersion = number;
export type ArtifactIndexSnapshot =
Readonly<{
catalogVersion: CatalogVersion;
filter: ArtifactBloomFilter;
}>;
export type ArtifactRepository =
Readonly<{
existsAtVersionAsync: (
digest: Uint8Array,
catalogVersion: CatalogVersion,
signal?: AbortSignal,
) => Promise<boolean>;
}>;
export class ArtifactExistenceService
{
readonly #snapshot: ArtifactIndexSnapshot;
readonly #repository: ArtifactRepository;
public constructor(
snapshot: ArtifactIndexSnapshot,
repository: ArtifactRepository,
)
{
this.#snapshot = snapshot;
this.#repository = repository;
}
public async existsAsync(
digest: Uint8Array,
signal?: AbortSignal,
): Promise<boolean>
{
validateArtifactDigest(digest);
if (!this.#snapshot
.filter
.mightContain(digest)) {
return false;
}
return await this.#repository
.existsAtVersionAsync(
digest,
this.#snapshot.catalogVersion,
signal,
);
}
}
function validateArtifactDigest(
digest: Uint8Array,
): void
{
if (!(digest instanceof Uint8Array)
|| digest.byteLength !== 32) {
throw new RangeError(
"Artifact digest는 32-byte여야 합니다.",
);
}
}책임 분리:
Catalog Loader
= DB·object storage에서 정확한 digest 목록 조회
= catalogVersion 획득
= I/O와 cancellation
ArtifactBloomFilter
= digest → Definitely Not | Maybe
= 외부 I/O 없음
= 정확한 존재 결과를 반환하지 않음
ArtifactRepository
= Maybe 결과의 정확한 존재 확인
= catalogVersion 일관성 보장
ArtifactExistenceService
= Validate
→ Negative precheck
→ 필요할 때만 정확 조회
Snapshot Publisher
= 새 filter 완성
→ 검증
→ version과 함께 원자적 교체Snapshot을 갈아끼울 때 기존 filter를 제자리에서 고치지 않는다.
개인적인 메모:사실을 저러한 클래스들이 필요하다라고 하지만, 프로젝트에 따라 달라진다. 어디까지나 원본 코드 구현이 다음처럼 되있었기때문에 저런식의 구성을 추천하는 것뿐이다. Bloom Filter를 운영에 안전하게 쓰기 위해 중요한 건 책임과 불변조건이지, 반드시
CatalogLoader,ArtifactRepository,SnapshotPublisher라는 클래스를 만들어야 한다는 뜻은 아니다.
Bloom Filter가 내놓는 건
Definitely Not | Maybe뿐이라서, 존재 여부를 확정하지 않는다.
Maybe면 authoritative source에서 정확 조회한다.filter가 어느
catalogVersion을 나타내는지가 분명해야 한다.새 snapshot은 완성하고 검증한 다음에 공개하고, 조회 중인 snapshot을 어설프게 부분 수정하지 않는다.
이 4가지 안에서 구현하고, 나머지는 구현의 선택지다. 다만 26년 최근 기조에 맞춰 적어두는데, 아마 나중에 27~28년도에는 더 간소화된 방식의 코딩 방식이 유행할 수도 있다고 본다.
개인
Reader A
→ Snapshot 42를 끝까지 사용
Builder
→ Snapshot 43을 별도 구축
검증 완료
→ currentSnapshot 참조를 43으로 교체
Reader B
→ Snapshot 43 사용이 구조라면 query 도중에 bitset이나 catalog version이 섞이는 일은 없다.
대형 snapshot의 운영 경계
2³⁰ bit면 약 128 MiB라서, C#에서 이 정도 byte[]는 Large Object Heap에 올라간다. 그래서 새 snapshot을 만드는 동안 이전 snapshot과 메타데이터까지 겹친 peak memory를 봐야 한다.
Node.js의 Uint8Array backing store는 일반 V8 heap과 따로 ArrayBuffer 메모리로 집계된다. memoryUsage()의 arrayBuffers와 RSS를 같이 봐야 한다.
개인적인 메모: 이 부분을 실제 관측을 하지 않으면 오해가 꽤 있는 지점으로 관측상 확인함. 힙 메모리가 얼마 안되는데 OOM으로 죽는걸 내 눈으로 확인했음.
필터가 이 상한에 가깝고 교체까지 잦다면 Memory-Mapped File이나 Python의 mmap을 검토할 만하다. 다만 이건 관리 힙으로 bitset 전체를 복사하는 비용을 줄이는 선택지다. 물리 메모리와 page fault 비용까지 없애주는 만능 zero-copy 해법은 아니다.
snapshot 전파와 Delta
복제본이 많고 snapshot 갱신이 잦으면, 매번 bitset 전체를 내려받는 네트워크 비용이 커진다. 이때는 추가된 artifact만 담은 Delta Filter를 Base Filter와 같이 조회하는데, Base와 Delta는 같은 key encoding과 hash protocol을 써야 한다. Delta가 어느 Base에서 어느 catalog version까지의 변경인지도 version chain으로 명시해야 하고.
예를 들어 Base 42에는 baseVersion=42, targetVersion=43짜리 Delta만 붙일 수 있다.
Delta를 여러 겹 쌓으면 조회 비용과 false positive가 나란히 늘어난다. Bloom Filter는 삭제를 직접 표현하지 못하니, 지워진 artifact가 오래된 Base에서 계속 Maybe를 만들 수도 있다.
그래서 append-heavy catalog에 어울리고, 삭제가 쌓이면 주기적인 Base rebuild/compaction이 필요하다. 모든 시스템의 기본값은 아니고, 전체 snapshot 재구축·전파 비용이 운영 예산을 넘을 때 꺼내는 확장이다.
4. 구현의 순서
정확한 원본 집합은 어디에 있는가
↓
Bloom 양성을 exact lookup으로 확인하는가
↓
음성 결과가 유효한 catalog version은 무엇인가
↓
예상 원소 수와 목표 FPP가 명시되어 있는가
↓
실제 bitCount와 hashCount를 기록하는가
↓
모든 구현이 같은 digest byte order를 사용하는가
↓
Hash 위치 계산이 deterministic한가
↓
삽입된 bit를 지우는 API가 없는가
↓
예상 capacity 초과를 감지하는가
↓
Filter snapshot이 완성 후 원자적으로 게시되는가
↓
Bit fill ratio와 observed FPP를 관측하는가가장 먼저 볼 건 hash보다 Bloom 양성과 음성인 지점이다.
Bloom 양성을 진실로 사용하는가,
Bloom 음성을 최적화 힌트로 사용하는가?이 의미가 뒤집혀 있으면 bit 연산이 아무리 정확해도 시스템은 잘못된다.
5. 흔히 하는 오해
양성은 존재 증명이 아니다
mightContain(key) == true
의미:
필요한 bit가 모두 1이다.
의미하지 않는 것:
그 key가 실제로 삽입됐다.Bloom Filter는 false positive를 허용해 공간을 줄이는 구조인데, 양성 결과로 결제 이력, 권한, 차단 여부, 중복 요청 처리 같은 업무 결정을 확정해서는 안 된다. 1
안전한 적용:
Maybe
→ 추가 I/O 발생
False Positive
→ 불필요한 정확 조회 1회위험한 적용:
Maybe
→ 실제 존재로 확정
False Positive
→ 업무 데이터 오판기본 Bloom Filter에서 bit를 지우면 안 된다
서로 다른 원소가 같은 bit를 같이 쓸 수 있다.
A의 위치:
[5, 17, 40]
B의 위치:
[17, 22, 61]A를 지우겠다고 bit 17을 0으로 만들면, B를 조회할 때 false negative가 난다. 삭제가 필요하면 counting Bloom Filter, Cuckoo Filter, 세대별 filter 교체 같은 다른 구조를 골라야 한다.
“False negative 없음”은 snapshot 완전성을 포함한다
수학적으로 filter가 올바르더라도, 다음 상황에서는 음성 결과를 못 믿는다.
- 신규 원소가 filter에 반영되지 않음
- 다른 key canonicalization 사용
- 일부 shard의 digest가 구축 입력에서 누락됨
- bitset serialization이 손상됨
- hash protocol version이 다름
- 잘못된 catalogVersion과 함께 사용됨그래서 운영 계약은 이런 쪽에 가깝다.
Filter에 성공적으로 삽입된
동일 byte key에 대해서는
bit 삭제가 없는 한 false negative가 없다.개인적인 메모:현재는 코드 블록으로 강조를 하는데, 이것에 대해서 따로 생각해봐야하는 지점인듯.
Capacity는 메모리 크기가 아니라 오류 예산
예상 삽입 수가 n=1,000,000인데 실제로 이백만 개를 넣어도 배열 범위 오류는 안 난다. 대신 1이 되는 bit가 늘고 Maybe 비율이 올라간다.
과포화 결과:
정확성:
양성을 exact lookup으로 검증하면 유지
성능:
원격 조회 생략률 저하
최종 상태:
거의 모든 조회가 Maybe
-> filter 가치 소멸그래서 생성 API에서는 capacity 초과를 명시적으로 거부하는지 확인했다.
개인적인 메모:잘못된 구현에서 생각보다 문제가 꽤 있다.
예상 FPP 공식은 근사식이다
estimateFalsePositiveRate()가 쓰는 p̂ = (1 - e^(-kn/m))^k는 정확한 값이 아니라 근사식이고,
Bose 등은 이 고전적 표현이 실제 false-positive rate보다 작은 값을 주며, 특히 m이 작을 때 오차가 커진다는 것을 보였다.3
근사식이 가정하는 것:
k개의 bit 위치가 독립이다
m이 충분히 크다
이번 구현이 어기는 것:
h₁ + i·h₂ 이중 hashing은
k개 위치를 독립적으로 뽑지 않는다운영에서 이 값은 용량 계획용 지표지 SLA 수치가 아니어서, 실제 판단은 관측된 false-positive rate로 해야 한다. targetFalsePositiveRate는 layout을 설계하려고 두는 모델상 목표값이지, 실제 workload에서 관측되는 FPP의 SLA가 아니다. 설계 값과 운영 값은 이렇게 갈린다.
설계 입력:
targetFalsePositiveRate
↓
모델 검증:
modeledFalsePositiveRate <= targetFalsePositiveRate
↓
운영 판단:
observedFalsePositiveRatehashCount 후보는 닫힌식으로 평가한다
이번 구현은 query hot path를 줄이려고 hashCount를 1부터 32까지로 제한한다. 연속적인 최적 hash 수를 반올림하고 양 끝에서 잘라 보정하는 대신, 실제로 쓸 수 있는 32개 후보를 다 평가한다. 후보마다 필요한 bit 수를 공식으로 내니 k=1이나 k=32에서 긴 선형 탐색이 생기지 않는다.
고정된 k에서 모델 FPP를 목표 p 이하로 만드는 조건은 이렇다.
이걸 m에 대해 풀면 필요한 최소 bit 수의 근사값이 나온다.
실제 계산에서는 log(1 - root) 대신 쓸 수 있는 언어에서는 log1p(-root)를 쓰고, 모델 FPP의 1 - exp(-x)는 -expm1(-x)로 계산한다. root나 x가 작을 때 앞의 뺄셈에서 유효 숫자를 잃지 않으려는 거다. C# 구현에는 같은 목적의 LogOneMinus와 ExponentialMinusOne 보조 함수가 있다.
구축기는 k 후보마다 계산한 다음 bit 수가 가장 작은 layout을 고른다. bit 수가 같으면 hash 수가 작은 쪽을 고른다.
for k = 1..32
→ m_required(k) 계산
→ 64 bit 단위로 올림
→ modeled FPP 검증
→ 가장 작은 bitCount 선택공식 계산 뒤 정렬 때문에 경계에서 modeled FPP가 아주 조금 넘으면 64 bit를 한 번 더 올려 재검증한다. 32개 후보가 모두 최대 bit 수를 넘거나 목표를 못 맞추면 생성은 FilterTooLarge로 실패한다. expectedItemCount도 네 구현 모두 2³⁰이 공통 상한이다.
중복 삽입도 capacity accounting에 영향을 준다
같은 digest를 여러 번 넣어도 bitset 결과는 그대로다. 그런데 입력 개수를 그대로 insertedItemCount에 적으면, unique 원소 수보다 큰 값으로 FPP를 추정하게 된다. 선택지는:
- 구축 입력을 DB에서 DISTINCT로 보장
- 정렬된 digest stream에서 중복 제거
- 정확한 unique count를 metadata로 제공
- 중복을 허용하고 보수적 추정 사용Bloom Filter 자체로 unique count를 정확히 세려고 하면 안 된다.
Key encoding은 자료구조 계약이다
이번 구현은 임의 문자열을 안 받고, 32-byte SHA-256 digest만 받는다. 문자열을 직접 다룬다면 다음은 고정해야 한다.
- 문자 encoding: UTF-8
- Unicode normalization: NFC 등
- 대소문자 규칙
- namespace prefix
- 길이 framing
- protocol version다음 값들은 업무상 같아 보여도 byte sequence가 다를 수 있다.
"é"
"e" + combining acute accentHash 전에 canonicalization을 안 하면 서로 다른 원소가 된다.
이중 hashing의 k개 위치는 서로 겹치지 않는다
h₁ + i·h₂ 방식은 step이 bitCount와 약수를 공유하면 같은 위치를 되풀이해 밟을 수 있는데, 이번 구현에서는 그 상황이 구조적으로 안 나온다.
step = (seed2 | 1) mod bitCount
→ 항상 홀수
bitCount = alignToWord(...)
→ 항상 64의 배수
bitCount = 2^a · b (a ≥ 6, b는 홀수)
gcd(step, bitCount)은 홀수
→ b의 약수
순회 주기 = bitCount / gcd
→ 최소 2^a ≥ 64
hashCount ≤ 32 < 64
→ k개 위치가 모두 서로 다르다같은 이유로 step이 0이 되는 일도 없다. 홀수는 짝수인 bitCount로 나누어떨어지지 않기 때문이다. 원래 코드에 있던 if (step == 0) step = 1; 보정은 네 언어 모두 도달할 수 없는 분기였다. 읽는 사람에게 "겹칠 수도 있다"는 인상만 남기므로, 보정은 지우고 불변식을 문서로 남기는 쪽이 정확하다.
Bit 배열의 직렬화 형식을 명시해야 한다
언어별 native integer 배열을 그대로 파일에 쓰면 다음이 불분명해진다.
- word endian
- word width
- bit numbering
- padding
- hash protocol version
- bitCount
- hashCount
- item count안전한 header 예시:
Magic:
"ABF1"
Fields:
formatVersion
hashProtocolVersion
catalogVersion
bitCount
hashCount
expectedItemCount
insertedItemCount
targetFpp
payloadLength
payloadChecksum이번 예제에서 이 문제가 실제로 갈라지는 곳은 C++이다.
C++만 bit를 uint64_t word에 담고, 나머지 셋은 byte 배열에 담는다. byteIndex = index / 8이라는 공통 규칙과 word 배열이 같은 byte 열이 되려면 word를 little-endian으로 직렬화해야 한다. Big-endian으로 내보내면 나머지 셋과 byte 단위로 어긋난다. 그래서 C++ 쪽에 serializeBits()를 두고 byte order를 코드로 못 박았다.
Checksum이 실패했을 때 filter를 빈 filter로 갈아끼우면 모든 원소가 음성이 되니 위험하다.
그럴 때는 filter를 포기하고 정확 조회로 fallback해야 한다는 걸 경험으로 알았다.
Mutable filter의 lock-free query는 자동으로 안전하지 않다
Bit set은 0 → 1만 생기니까 단일 machine word의 atomic OR로 하면 된다. 다만 여러 thread가 non-atomic byte나 word를 동시에 고치면 data race나 lost bit update가 난다. 이번 구현은 이쪽을 골랐다.
Build:
단일 owner
Publish:
완성된 immutable filter
Query:
read-only, 다중 thread 공유삽입이 계속 필요한 online filter라면, 언어별 atomic word 연산과 snapshot serialization 일관성을 따로 설계해야 한다.
Bloom Filter는 원소를 열거할 수 없다
Bitset만으로는 다음을 복원할 수 없다.
- 어떤 artifact가 들어 있는가
- 특정 bit를 누가 설정했는가
- 정확한 unique 원소 수
- 원소별 삽입 시각원본 catalog는 반드시 따로 있어야 한다.
공격자가 digest를 직접 선택할 수 있는가
이번 구조는 SHA-256 artifact digest를 신뢰된 content-hash pipeline에서 받는다는 전제 위에 있다. 외부 사용자가 임의 32-byte 값을 고를 수 있고 filter 구조를 반복해서 들여다볼 수 있다면, 특정 bit pattern을 노리는 입력을 찾아낼 가능성을 따져봐야 한다. 필요하면 다음을 쓴다.
- 서버 비밀 seed를 사용한 keyed hash
- tenant별 namespace
- 요청 rate limit
- filter query 결과 비공개아주 작은 집합에는 Set이 더 낫다
Bloom Filter는 다음이 다 성립할 때 쓸 만하다.
- 원소 수가 충분히 큼
- exact key 저장 메모리가 부담
- 부재 조회 비율이 높음
- 양성 exact lookup 비용이 큼
- 일정한 false-positive rate를 허용원소가 수백 개뿐이면 hash set이 더 단순하고 정확하고, 열거도 삭제도 된다. 프로덕션 실패 모드는:
- Maybe를 실제 존재로 반환함
- 원소 삭제 시 bit를 0으로 지움
- filter보다 최신 repository에 음성 결과를 적용함
- capacity를 초과해도 관측하지 않음
- 언어마다 다른 문자열 encoding을 사용함
- serialization header 없이 raw bitset만 저장함
- 손상된 filter를 빈 filter로 대체함
- mutable bitset을 non-atomic하게 공유함
- 중복 입력을 unique 원소로 오인함
- 권한·결제·보안 판정을 Bloom 양성만으로 확정함
- 잘못된 길이의 digest를 조회했을 때 음성을 반환함6. 잘못된 예제
export class ArtifactServiceBad
{
readonly #filter: MutableBloomFilter;
readonly #repository: ArtifactRepository;
public constructor(
filter: MutableBloomFilter,
repository: ArtifactRepository,
)
{
this.#filter = filter;
this.#repository = repository;
}
public async existsAsync(
digest: Uint8Array,
): Promise<boolean>
{
// Maybe를 정확한 존재 결과로 잘못 사용한다.
return this.#filter.mightContain(
digest,
);
}
public async deleteAsync(
digest: Uint8Array,
): Promise<void>
{
await this.#repository.deleteAsync(
digest,
);
// 공유 bit를 지워 다른 원소에 false negative를 만든다.
this.#filter.clearBitsFor(
digest,
);
}
}문제점 1:
Artifact X는 삽입되지 않음
하지만 X의 모든 bit가
다른 artifact들 때문에 이미 1
mightContain(X)
→ true
서비스 결과:
존재한다고 잘못 반환문제점 2:
A와 B가 bit 17을 공유
A 삭제
→ bit 17 제거
B 조회
→ bit 17이 0
→ false negative세 번째 문제는 snapshot version이 없다는 거다.
Repository는 갱신됐는데 filter가 옛 상태여도 호출부가 그걸 알아채지 못한다.
개인적인 메모:버전 체인으로 막을 수 있긴한데, 내 생각에는 snapshot version 체인에 대해서는 복잡도가 너무 높다 생각한다.
Bloom Filter는 본질적으로 메인 데이터베이스 앞단에 위치하는 '네거티브 캐시' 계층이다. 캐시 계층과 영속성 계층 사이의 일관성을 보장하려고 버전 벡터나 체인을 유지하는 건 배보다 배꼽이 커지기 쉽다. 다만 동기화 매커니즘을 아예 구현하지 않으면 필터의 False Positive 비율을 조절할 수 없어서, 신뢰할 수 없는 캐시가 된다.
사실 잘못된 예제가 이상한 건
deleteAsync로 명시적 삭제를 요구하기 때문이다. 일반적인 표준 Bloom Filter는 삭제 연산을 지원하지 않는데, 삭제가 일어나는 도메인에 삭제가 안 되는 자료구조를 태생적으로 넣었으니 문제가 터지는 거다.원본 C++ 코드 작성자의 생각은 존중하지만, 내 생각은 이렇다.
올바른 원칙:
Negative:
정확 조회 생략 가능
Maybe:
정확 조회 필수
Delete:
기본 Bloom Filter를 수정하지 않음
→ 새 snapshot 재구축7. 프로덕션 확장
모델 기반 정확성·확률 검증
Bloom Filter 테스트는 정확한 불변식과 확률적 품질을 갈라서 봐야 한다.
정확한 불변식:
삽입한 모든 digest
→ MightContain == true
구축 입력의 잘못된 digest 길이
→ InvalidDigest 실패
조회 입력의 잘못된 digest 길이
→ 예외
동일 입력과 spec
→ 동일 결과
Capacity 초과
→ 명시적 실패
공통 expected item count 상한 초과
→ InvalidExpectedItemCount 실패
최대 bitCount에서도 target FPP를 만족하지 못함
→ FilterTooLarge 실패확률적 품질:
삽입하지 않은 충분한 표본에 대해
observed FPP가 목표 범위 안인가TypeScript 테스트:
import assert from "node:assert/strict";
import {
createHash,
} from "node:crypto";
import test from "node:test";
test(
"삽입된 digest에서는 false negative가 없다",
() =>
{
const members =
createDigests(
"member",
10_000,
);
const result =
ArtifactBloomFilter.create(
members,
{
expectedItemCount: 10_000,
targetFalsePositiveRate: 0.01,
},
);
if (result.kind === "failure") {
assert.fail(result.error);
}
for (const digest of members) {
assert.equal(
result.value.mightContain(
digest,
),
true,
);
}
});
test(
"관측 false-positive rate가 통계 허용 범위 안이다",
() =>
{
const itemCount = 20_000;
const probeCount = 200_000;
const targetRate = 0.01;
const result =
ArtifactBloomFilter.create(
createDigests(
"member",
itemCount,
),
{
expectedItemCount: itemCount,
targetFalsePositiveRate:
targetRate,
},
);
if (result.kind === "failure") {
assert.fail(result.error);
}
let falsePositiveCount = 0;
for (
let index = 0;
index < probeCount;
index += 1
) {
const digest =
createDigest(
`non-member:${index}`,
);
if (result.value.mightContain(
digest,
)) {
falsePositiveCount += 1;
}
}
const observedRate =
falsePositiveCount / probeCount;
const modelRate =
result.value
.estimateFalsePositiveRate();
const standardDeviation =
Math.sqrt(
modelRate
* (1 - modelRate)
/ probeCount,
);
const upperBound =
modelRate
+ 5 * standardDeviation;
assert.ok(
observedRate <= upperBound,
`관측 FPP ${observedRate}가 `
+ `허용 상한 ${upperBound}를 초과했습니다.`,
);
});
test(
"잘못된 길이의 digest는 조회에서 거부한다",
() =>
{
const result =
ArtifactBloomFilter.create(
createDigests(
"member",
16,
),
{
expectedItemCount: 100,
targetFalsePositiveRate: 0.01,
},
);
if (result.kind === "failure") {
assert.fail(result.error);
}
assert.throws(
() =>
result.value.mightContain(
new Uint8Array(16),
),
RangeError,
);
});
test(
"설계 capacity 초과를 거부한다",
() =>
{
const result =
ArtifactBloomFilter.create(
createDigests(
"member",
101,
),
{
expectedItemCount: 100,
targetFalsePositiveRate: 0.01,
},
);
assert.deepEqual(result, {
kind: "failure",
error: "capacityExceeded",
});
});
test(
"모든 hashCount 후보에서 modeled FPP budget을 지킨다",
() =>
{
const expectedItemCount =
1_000_000;
const targetModeledRate = 1e-20;
const result =
ArtifactBloomFilter.create(
[],
{
expectedItemCount,
targetFalsePositiveRate:
targetModeledRate,
},
);
if (result.kind === "failure") {
assert.fail(result.error);
}
assert.equal(
result.value.getHashCount(),
32,
);
const m = result.value.getBitCount();
const k = result.value.getHashCount();
const modeledRate =
(-Math.expm1(-k * expectedItemCount / m))
** k;
assert.ok(modeledRate <= targetModeledRate);
});
test(
"낮은 hashCount 경계도 후보 평가로 계산한다",
() =>
{
const expectedItemCount =
1_000_000;
const targetModeledRate = 0.95;
const result =
ArtifactBloomFilter.create(
[],
{
expectedItemCount,
targetFalsePositiveRate:
targetModeledRate,
},
);
if (result.kind === "failure") {
assert.fail(result.error);
}
assert.equal(
result.value.getHashCount(),
1,
);
assert.equal(
result.value.getBitCount(),
333_824,
);
const modeledRate =
(-Math.expm1(
-expectedItemCount
/ result.value.getBitCount(),
));
assert.ok(modeledRate <= targetModeledRate);
});
function createDigests(
prefix: string,
count: number,
): readonly Uint8Array[]
{
return Array.from(
{ length: count },
(_, index) =>
createDigest(
`${prefix}:${index}`,
),
);
}
function createDigest(
value: string,
): Uint8Array
{
return createHash("sha256")
.update(value, "utf8")
.digest();
}구축 결과를 검사할 때 실패 분기에서 return으로 빠져나오면 안 된다. 그러면 filter를 못 만든 경우에도 테스트가 통과해버린다.
assert.fail은 반환 타입이 never라서, 실패를 확정하면서 뒤 코드에서 result를 성공 쪽으로 좁혀주는 역할까지 한다. 이 테스트는 입력과 난수원이 고정돼 있어서 실행마다 흔들리는 flaky 테스트는 아니다. 다만 유한 표본에서 관측값이 목표 FPP와 정확히 같기를 요구하는 검증은 통계적으로 맞지 않고, 구현을 조금만 바꿔도 깨지는 brittle 검증이다.
표본 수와 통계적 허용 범위는 명시해야 한다. 허용 범위는 목표 FPP에 바로 대지 말고, 실제 layout의 모델 FPP와 표본 오차를 기준으로 계산해야 한다. n = 20,000, p = 0.01이면 후보 k=1..32를 평가하고 그중 bitCount가 가장 작은 layout을 고른다. 이 테스트는 고른 layout의 모델 FPP 기준으로 상한을 세우고, 한쪽 방향만 본다. 항상 음성을 내는 고장 난 filter도 상한 검사만으로는 통과하니, 그 경우는 첫 번째 테스트가 잡는다.
운영 지표
artifact_bloom.bit_count
artifact_bloom.hash_count
artifact_bloom.expected_item_count
artifact_bloom.inserted_item_count
artifact_bloom.fill_ratio
artifact_bloom.estimated_fpp
artifact_bloom.negative.count
artifact_bloom.maybe.count
artifact_bloom.false_positive.count
artifact_bloom.catalog_version
artifact_bloom.snapshot.age_seconds
artifact_bloom.snapshot.load_failure.count실제 false positive는 이런 조건을 걸고 측정한다.
Bloom:
Maybe
Exact Repository:
Absent
→ False Positive 1건유용한 비율:
negativeBypassRatio
=
Negative / Total Queries
observedFalsePositiveRate
=
False Positives
/ (Negative Prechecks + False Positives)
falseDiscoveryRatio
=
False Positives
/ Maybe ResultsobservedFalsePositiveRate는 부재 요청 중에 Bloom이 잘못 양성을 낸 비율이다. falseDiscoveryRatio는 Maybe로 넘어간 조회 중 실제로 없던 비율이다. 앞은 Bloom의 분류 성능, 뒤는 정확 조회로 낭비된 Maybe 비율을 보여주니, 같은 지표로 합치면 안 된다. Bit fill ratio가 예상보다 급하게 올라가면 capacity 초과, 중복되지 않는 예상 밖 입력 증가, 잘못된 hash 분포를 의심한다.
8. C++ / Python / C# / TypeScript 비교 메모
언어 | Bit 저장 | 64-bit seed | 주요 위험 |
|---|---|---|---|
C++ |
|
| view 수명, 직렬화 endian |
Python | immutable | arbitrary precision | interpreter loop와 객체 비용 |
C# | private |
| 배열 alias, LOH, snapshot 복사 |
TypeScript | private |
| bitwise 32-bit 변환, runtime 차이 |
- 언어
C++
- Bit 저장
vector<uint64_t>- 64-bit seed
uint64_t- 주요 위험
view 수명, 직렬화 endian
- 언어
Python
- Bit 저장
immutable
bytes- 64-bit seed
arbitrary precision
int- 주요 위험
interpreter loop와 객체 비용
- 언어
C#
- Bit 저장
private
byte[]- 64-bit seed
ulong- 주요 위험
배열 alias, LOH, snapshot 복사
- 언어
TypeScript
- Bit 저장
private
Uint8Array- 64-bit seed
bigint- 주요 위험
bitwise 32-bit 변환, runtime 차이
C++
vector<uint64_t>는 64개 bit를 word 하나에 담아서 compact하다. Query에 allocation이 없다. Mutable concurrent filter로 늘릴 거라면 std::atomic<uint64_t> word 배열이 후보가 된다. 다만 일반 vector<uint64_t>와 같은 방식으로 직렬화·복사할 수 있다고 가정하면 안 된다. Immutable snapshot이 훨씬 단순하다. span이나 string_view를 filter 안에 두지 않으니, 구축 입력의 lifetime과 filter lifetime이 갈린다. Word 배열은 성능에는 좋은데 언어 간 호환에는 부담이다. 나머지 셋이 byte 배열을 쓰니까, C++만 word를 byte로 펴는 규칙을 따로 약속해야 한다.
serializeBits()가 little-endian을 강제해서 이 약속을 코드로 만든다.
Python 메모
bytes는 immutable snapshot에 어울리고, byte 단위 bitset은 Python 정수 객체를 원소마다 담는 list보다 훨씬 조밀하다. 대신 query 하나에 Python loop가 k번 도는데, 초당 수백만 query가 필요하면 C extension, Rust/C++ extension, NumPy batch query, 외부 probabilistic index를 검토한다. Python은 arbitrary-precision integer라 64-bit overflow 문제가 없다. 그래도 외부 입력 경계에서는 다른 구현과 같은 원소 수 상한과 32-byte digest 정규화를 적용해야 하고, byte order와 modulo 규칙도 다른 언어와 같아야 한다.
C# 메모
byte[]는 compact하지만 reference type이다. 외부 alias를 받거나 돌려주면 snapshot 불변성이 깨진다. 이번 구현은 구축 중에 자체 배열을 만들고, 외부에 배열을 노출하지 않는다. 대형 filter는 Large Object Heap에 들어간다. Snapshot을 자주 재구축하면 이전 filter가 reader에 남아 있는 동안 메모리가 두 배 가까이 쓰인다. 배포 가능성은 peak memory 기준으로 봐야 한다. ReadOnlySpan<byte>는 query input에는 맞지만 async 경계를 못 넘는다. membership 계산을 동기로 끝내고 I/O를 시작하는 분리가 자연스럽다.
TypeScript 메모
JavaScript의 일반 bitwise 연산은 signed 32-bit로 바뀐다. 64-bit seed를 number로 읽으면 정밀도가 날아가서 bigint를 썼다. Bit 수는 최대 2³⁰으로 막아두고 bit index는 일반 number로 다루게 해뒀다. 이 상한은 TypeScript만의 사정이 아닌데, C#은 int로 배열을 색인하고 alignToWord()는 값에 최대 63을 더한다. 상한을 2³¹에 두면 정렬 과정에서 부호 있는 32-bit 범위를 넘을 수 있어서, 네 구현 모두 2³⁰이다. Readonly<Uint8Array>는 backing storage의 다른 alias를 없애주지 않는다. Filter 생성자가 입력 bitset을 직접 받는 API를 추가한다면 복사하거나 ownership을 명시적으로 넘겨야 한다.
공통 계약
네 언어에서 같아야 하는 건 class 모양이 아니다.
Digest:
정확히 32 bytes
Seed 1:
digest[0..8] unsigned big-endian
Seed 2:
digest[8..16] unsigned big-endian
→ 최하위 bit를 1로 설정
Initial index:
seed1 mod bitCount
Step:
(seed2 | 1) mod bitCount
다음 index:
(index + step) mod bitCount
Hash count candidates:
k = 1..32를 모두 평가
bitCount candidate:
m_required(k) = -kn / ln(1 - targetFpp^(1/k))
를 계산한 뒤 64의 배수로 올림
선택 규칙:
가장 작은 bitCount
bitCount가 같으면 가장 작은 k
항상 최종 modeledFpp <= targetFpp를 검증
FPP layers:
targetFpp는 builder의 설계 목표
modeledFpp는 구축 시 확인하는 근사값
observedFpp는 운영에서 측정하는 값
Expected item count:
1 이상 2³⁰ 이하
Bit numbering:
byteIndex = index / 8
bitOffset = index % 8
LSB-first
Word 배열 구현의 직렬화:
word를 little-endian byte로 펼침
bitCount:
alignToWord로 64의 배수
상한 2³⁰Filter를 언어 간에 직렬화하거나 golden vector를 공유하려면, 이 protocol을 문서로 고정해야 한다.
특히 reader는 targetFpp로 layout을 다시 계산하지 말아야 한다. header의 bitCount와 hashCount를 wire contract 값으로 쓴다. targetFpp는 builder가 어떤 목표로 만들었는지 설명하는 metadata다. 이미 발행된 snapshot의 layout을 결정하는 값이 아니다. 같은 입력으로 네 구현을 돌려 bit 배열을 byte 단위로 비교하면 이 계약이 실제로 지켜지는지 확인된다. 입력은 SHA-256(member:0부터 member:999까지) digest 1,000개로 고정하고, expectedItemCount: 2000, targetFalsePositiveRate: 0.01을 쓴다.
네 구현 모두 bitCount = 19200, hashCount = 7, set bit 수 5858, fill ratio 0.3051041666666667을 내야 한다. LSB-first로 직렬화한 2,400-byte bitset의 SHA-256은 82a3be1c19b8d8576778c2d536b288f2b26fd50f4b1f42e932f276a15cd78fb6이다. C++만 little-endian으로 펼치면 맞고 big-endian으로 펼치면 어긋난다. 이 입력 규칙과 checksum을 CI에 두는 게 "문서로 고정"의 실제 형태다.
9. 추가로 생각해보기
Catalog가 계속 늘어날 때 고정 filter를 다시 구축할 건가, base filter와 delta filter를 같이 조회할 건가?
목표 FPP를 낮춰 메모리를 키우는 쪽과, false positive로 생기는 원격 I/O 비용 중에 실제로 싼 쪽은 어디인가?
Snapshot을 갈아끼울 때 이전 reader가 old version을 쓰는 동안, repository가 그 version의 정확 조회를 제공할 수 있나?
Digest가 이미 SHA-256일 때 두 64-bit 조각을 쓰는 것과 별도 keyed hash를 적용하는 것, 어느 위협 모델이 맞나?
삭제가 잦다면 counting Bloom Filter, Cuckoo Filter, 주기적 전체 rebuild 중에 뭐가 더 단순한가?
Filter가 손상됐거나 version이 안 맞을 때 서비스를 실패시킬 건가, Bloom 최적화를 끄고 모든 요청을 정확 조회로 fallback할 건가?
조회 입력의 길이 위반을 예외로 다룰지 Result로 다룰지, 어느 쪽이 호출부를 더 정직하게 만드나?
C++처럼 digest를 값 타입으로 감싸 길이 위반을 표현 불가능하게 만드는 비용을, 나머지 셋에서도 낼 만한가?
10. 요약
Bloom Filter의 음성은 부재이고, 양성은 존재 가능성일 뿐이다.
양성이 나왔다고 끝내지 말고 원본 저장소에서 정확 조회로 확인한다.
예상 원소 수와 설계 목표 false-positive rate로 bit 수와 hash 수를 설계한다.
hashCount후보 1부터 32까지 필요한 bit 수를 닫힌식으로 평가한다. 가장 작은 layout을 고른 다음, 최종 modeled FPP가 목표 이하인지 검증한다. 최대 크기에서도 못 맞추면FilterTooLarge로 실패시킨다.기본 Bloom Filter에서 bit를 지우면 공유 bit 때문에 false negative가 생긴다.
수학적으로 false negative가 없다는 건, filter가 완전하고 최신이며 hash protocol이 같다는 조건 위에서만 성립한다.
Immutable versioned snapshot으로 게시하고, fill ratio와 observed false-positive rate는 운영에서 측정한다.
targetFpp와modeledFpp는 설계·구축 값이다. 실제 SLA 판단에는observedFpp를 쓴다.음성만 믿는 설계에서는 조회 입력의 형식 위반을 음성으로 돌려주면 안 된다. 구축은 Result로 거부하고 조회는 예외로 끊는다.
Python의
memoryview는 요소 수와 바이트 수가 다를 수 있다. digest를bytes로 정규화한 뒤 길이를 검사하고, 큰 정수 입력도 공통 경계에서 명시적으로 거부한다.언어별
round차이를 피하려고hashCount후보를 직접 평가한다. reader는 target FPP가 아니라 header의bitCount/hashCount를 믿는다.Bit 배열의 byte 표현까지 계약에 넣어야 언어 간 filter 공유가 된다.
위에 학술적으로 길게 썼지만 다 외울 필요는 없다. 세상에서 제일 멍청한 건 남들이 잘 만들어둔 걸 안 쓰고 자체 구현하는 거다. 이건 그냥 내 취미라서 메모하는 것뿐이다.
Bloom Filter는 본질적으로 메인 데이터베이스 앞단에 위치하는 네거티브 캐시 전용 메타데이터 계층이다. 다르게 말하면 DB를 조회할 만한 데이터인지 아닌지를 가르는 검문소다.
여권이 아예 없는 사람(없는 데이터)은 입국을 거절해서, 그렇게 무의미한 최종 심사(DB I/O)를 완벽하게 막아준다.
단, 여권을 들고 있다고 해서 진짜인지(False Positive)는 이 검문소에서 확신할 수 없다. 통과한 사람만 최종 심사대(DB)로 보내 검증한다고 이해해두면, 실무에서는 충분히 쓸 만하다.
Bloom Filter를 정답표로 쓰지 말것
음성이면 비싼 조회를 생략하고,
양성이면 정확한 저장소에 확인하라.
공간을 절약하는 대신 허용한 오류는
추가 조회 비용으로만 끝나야 한다.각주
- Burton H. Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM 13(7), 1970. 허용 가능한 오류를 대가로 공간과 조회 시간을 줄이는 원 논문. ↩
- Adam Kirsch, Michael Mitzenmacher. Less hashing, same performance: Building a better Bloom filter. Random Structures & Algorithms 33(2), 2008. 두 hash의 선형 결합으로 k개 위치를 만들어도 점근적 false-positive 성능이 유지됨을 보인 논문. ↩
- Prosenjit Bose, Hua Guo, Evangelos Kranakis, Anil Maheshwari, Pat Morin, Jason Morrison, Michiel Smid, Yihui Tang. On the false-positive rate of Bloom filters. Information Processing Letters, 2008. 고전적 근사식이 실제 false-positive rate를 과소평가함을 보인 논문. 저자 preprint ↩