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))^k

Artifact ID:
SHA-256 digest 32 bytes
정확한 저장소:
원격 object storage
비싼 연산:
HEAD 또는 metadata DB 조회
Catalog snapshot:
특정 catalogVersion에 존재하는
모든 artifact digest의 목록

1. Artifact digest 형식 검증
2. Bloom Filter 조회
Definitely Not
→ 원격 I/O 없이 absent 반환
Maybe
→ 정확한 repository 조회
→ 실제 존재 여부 반환

Bloom Filter가 Maybe 반환
→ artifact가 존재한다고 바로 반환

Filter version:
42
Repository query version:
43
Version 43에서 새로 추가된 artifact
→ Filter 42에는 bit가 없음
→ 운영상 false negative

ArtifactIndexSnapshot
- catalogVersion
- expectedItemCount
- insertedItemCount
- targetFalsePositiveRate
- bitCount
- hashCount
- hashProtocolVersion
- bitset

#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);

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
    )

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)

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,
)

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);

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,
  };
}

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,
);

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과 함께 원자적 교체

Reader A
→ Snapshot 42를 끝까지 사용
Builder
→ Snapshot 43을 별도 구축
검증 완료
→ currentSnapshot 참조를 43으로 교체
Reader B
→ Snapshot 43 사용

정확한 원본 집합은 어디에 있는가
↓
Bloom 양성을 exact lookup으로 확인하는가
↓
음성 결과가 유효한 catalog version은 무엇인가
↓
예상 원소 수와 목표 FPP가 명시되어 있는가
↓
실제 bitCount와 hashCount를 기록하는가
↓
모든 구현이 같은 digest byte order를 사용하는가
↓
Hash 위치 계산이 deterministic한가
↓
삽입된 bit를 지우는 API가 없는가
↓
예상 capacity 초과를 감지하는가
↓
Filter snapshot이 완성 후 원자적으로 게시되는가
↓
Bit fill ratio와 observed FPP를 관측하는가

Bloom 양성을 진실로 사용하는가,
Bloom 음성을 최적화 힌트로 사용하는가?

mightContain(key) == true
의미:
필요한 bit가 모두 1이다.
의미하지 않는 것:
그 key가 실제로 삽입됐다.

Maybe
→ 추가 I/O 발생
False Positive
→ 불필요한 정확 조회 1회

Maybe
→ 실제 존재로 확정
False Positive
→ 업무 데이터 오판

A의 위치:
[5, 17, 40]
B의 위치:
[17, 22, 61]

- 신규 원소가 filter에 반영되지 않음
- 다른 key canonicalization 사용
- 일부 shard의 digest가 구축 입력에서 누락됨
- bitset serialization이 손상됨
- hash protocol version이 다름
- 잘못된 catalogVersion과 함께 사용됨

Filter에 성공적으로 삽입된
동일 byte key에 대해서는
bit 삭제가 없는 한 false negative가 없다.

과포화 결과:
정확성:
양성을 exact lookup으로 검증하면 유지
성능:
원격 조회 생략률 저하
최종 상태:
거의 모든 조회가 Maybe
-> filter 가치 소멸

근사식이 가정하는 것:
k개의 bit 위치가 독립이다
m이 충분히 크다
이번 구현이 어기는 것:
h₁ + i·h₂ 이중 hashing은
k개 위치를 독립적으로 뽑지 않는다

설계 입력:
targetFalsePositiveRate
    ↓
모델 검증:
modeledFalsePositiveRate <= targetFalsePositiveRate
    ↓
운영 판단:
observedFalsePositiveRate

for k = 1..32
→ m_required(k) 계산
→ 64 bit 단위로 올림
→ modeled FPP 검증
→ 가장 작은 bitCount 선택

- 구축 입력을 DB에서 DISTINCT로 보장
- 정렬된 digest stream에서 중복 제거
- 정확한 unique count를 metadata로 제공
- 중복을 허용하고 보수적 추정 사용

- 문자 encoding: UTF-8
- Unicode normalization: NFC 등
- 대소문자 규칙
- namespace prefix
- 길이 framing
- protocol version

"é"
"e" + combining acute accent

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개 위치가 모두 서로 다르다

- word endian
- word width
- bit numbering
- padding
- hash protocol version
- bitCount
- hashCount
- item count

Magic:
"ABF1"
Fields:
formatVersion
hashProtocolVersion
catalogVersion
bitCount
hashCount
expectedItemCount
insertedItemCount
targetFpp
payloadLength
payloadChecksum

Build:
단일 owner
Publish:
완성된 immutable filter
Query:
read-only, 다중 thread 공유

- 어떤 artifact가 들어 있는가
- 특정 bit를 누가 설정했는가
- 정확한 unique 원소 수
- 원소별 삽입 시각

- 서버 비밀 seed를 사용한 keyed hash
- tenant별 namespace
- 요청 rate limit
- filter query 결과 비공개

- 원소 수가 충분히 큼
- exact key 저장 메모리가 부담
- 부재 조회 비율이 높음
- 양성 exact lookup 비용이 큼
- 일정한 false-positive rate를 허용

- Maybe를 실제 존재로 반환함
- 원소 삭제 시 bit를 0으로 지움
- filter보다 최신 repository에 음성 결과를 적용함
- capacity를 초과해도 관측하지 않음
- 언어마다 다른 문자열 encoding을 사용함
- serialization header 없이 raw bitset만 저장함
- 손상된 filter를 빈 filter로 대체함
- mutable bitset을 non-atomic하게 공유함
- 중복 입력을 unique 원소로 오인함
- 권한·결제·보안 판정을 Bloom 양성만으로 확정함
- 잘못된 길이의 digest를 조회했을 때 음성을 반환함

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,
    );
  }
}

Artifact X는 삽입되지 않음
하지만 X의 모든 bit가
다른 artifact들 때문에 이미 1
mightContain(X)
→ true
서비스 결과:
존재한다고 잘못 반환

A와 B가 bit 17을 공유
A 삭제
→ bit 17 제거
B 조회
→ bit 17이 0
→ false negative

Negative:
정확 조회 생략 가능
Maybe:
정확 조회 필수
Delete:
기본 Bloom Filter를 수정하지 않음
→ 새 snapshot 재구축

삽입한 모든 digest
→ MightContain == true
구축 입력의 잘못된 digest 길이
→ InvalidDigest 실패
조회 입력의 잘못된 digest 길이
→ 예외
동일 입력과 spec
→ 동일 결과
Capacity 초과
→ 명시적 실패
공통 expected item count 상한 초과
→ InvalidExpectedItemCount 실패
최대 bitCount에서도 target FPP를 만족하지 못함
→ FilterTooLarge 실패

삽입하지 않은 충분한 표본에 대해
observed FPP가 목표 범위 안인가

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();
}

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

Bloom:
Maybe
Exact Repository:
Absent
→ False Positive 1건

negativeBypassRatio
=
Negative / Total Queries
observedFalsePositiveRate
=
False Positives
/ (Negative Prechecks + False Positives)

falseDiscoveryRatio
=
False Positives
/ Maybe Results

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³⁰

Bloom Filter를 정답표로 쓰지 말것
음성이면 비싼 조회를 생략하고,
양성이면 정확한 저장소에 확인하라.
공간을 절약하는 대신 허용한 오류는
추가 조회 비용으로만 끝나야 한다.