Bloom Filter-Based Absence-First Lookup

Bloom Filter
= Fixed-size bit array

k deterministic bit positions

Add(x):
Set the bit at each index_i(x) to 1

MightContain(x):
All bits at index_i(x) are 1
→ Maybe
Any one of them is 0
→ Definitely Not

Design formulas:
m ≈ -n · ln(p) / (ln 2)²
k ≈ (m / n) · ln 2

n = expected number of insertions
m = number of bits
k = number of hash positions
p = target false-positive rate

Estimated false-positive rate:
p̂ = (1 - e^(-kn/m))^k

Artifact ID:
SHA-256 digest 32 bytes
Authoritative store:
remote object storage
Expensive operation:
HEAD or metadata DB lookup
Catalog snapshot:
list of all artifact digests present in a specific
catalogVersion

1. Artifact digest format validation
2. Bloom Filter lookup
Definitely Not
→ Returns absent without any remote I/O
Maybe
→ Exact repository lookup
→ Returns actual existence result

Bloom Filter returns Maybe
→ immediately return that the artifact exists

Filter version:
42
Repository query version:
43
Artifact newly added in Version 43
→ Bit not present in Filter 42
→ Operational 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();
}
// Since the result is Maybe, check the exact repository to confirm.
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(
                "The artifact digest must be 32 bytes."
            )
        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(
                "The artifact digest must be 32 bytes.",
                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(
        "The artifact digest must be 32 bytes.",
      );
    }
    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 digests must be 32 bytes.",
    );
  }
}

Catalog Loader
= Retrieve exact digest list from DB/object storage
= Acquire catalogVersion
= I/O and cancellation

ArtifactBloomFilter
= digest → Definitely Not | Maybe
= No external I/O
= Does not return exact existence results

ArtifactRepository
= Verify exact existence for Maybe results
= Guarantee catalogVersion consistency

ArtifactExistenceService
= Validate
→ Negative precheck
→ Only query exact results when needed

Snapshot Publisher
= Complete new filter
→ Validate
→ Atomically replace with version

Reader A
→ Continue using Snapshot 42 until done
Builder
→ Build Snapshot 43 separately
Validation complete
→ Replace `currentSnapshot` reference to 43
Reader B
→ Use Snapshot 43

Where does the exact source set live?
↓
Are Bloom positives confirmed with an exact lookup?
↓
Which catalog version are negative results valid for?
↓
Are the expected element count and target false-positive rate (FPP) specified explicitly?
↓
Are the actual `bitCount` and `hashCount` recorded?
↓
Do all implementations use the same digest byte order?
↓
Is hash position calculation deterministic?
↓
Is there no API that clears inserted bits?
↓
Is exceeding the expected capacity detected?
↓
Is the filter snapshot published atomically after it is complete?
↓
Are bit fill ratio and observed FPP monitored?

Do you treat a Bloom positive as ground truth,
or do you use a Bloom negative as an optimization hint?

mightContain(key) == true
Meaning:
All required bits are 1.
What it does NOT mean:
That the key was actually inserted.

Maybe
Additional I/O overhead
False Positive
1 unnecessary exact lookup

Maybe
Confirmed Present
False Positive
Business Data Misclassification

Position of A:
[5, 17, 40]
Position of B:
[17, 22, 61]

- New elements not reflected in the filter
- Different key canonicalization used
- Digest of some shards missing from the build input
- bitset serialization is corrupted
- Different hash protocol version
- Used with incorrect `catalogVersion`

Successfully inserted into the Filter,
for the same byte key,
there are no false negatives as long as no bits are deleted.

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

What the approximation assumes:
k bit positions are independent
m is sufficiently large
What this implementation violates:
double hashing with h₁ + i·h₂
does not sample k positions independently

Design input:
targetFalsePositiveRate
    ↓
Model validation:
modeledFalsePositiveRate <= targetFalsePositiveRate
    ↓
Operational judgment:
observedFalsePositiveRate

for k = 1..32
→ Calculate m_required(k)
→ Round up to 64-bit units
→ Verify modeled FPP
→ Select the smallest bitCount

- Guarantee uniqueness via DISTINCT in the DB for build inputs
- Deduplicate from a sorted digest stream
- Provide an exact unique count as metadata
- Allow duplicates and use a conservative estimate

- Character encoding: UTF-8
- Unicode normalization: NFC, etc.
- Case rules
- namespace prefix
- Length framing
- protocol version

"é"
"e" + combining acute accent

step = (seed2 | 1) mod bitCount
→ Always odd

bitCount = alignToWord(...)
→ Always a multiple of 64

bitCount = 2^a · b (a ≥ 6, b is odd)

gcd(step, bitCount) is odd
→ A divisor of b

Traversal period = bitCount / gcd
→ At least 2^a ≥ 64

hashCount ≤ 32 < 64
→ All k positions are distinct

- 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:
Single owner
Publish:
Completed immutable filter
Query:
Read-only, shared across multiple threads

- Which artifacts are contained
- Which hash function set a specific bit
- The exact number of unique elements
- Insertion timestamp per element

- Keyed hash using server secret seed
- Per-tenant namespace
- Request rate limiting
- Filter query results kept private

- The number of elements is sufficiently large
- Memory for storing exact keys is a burden
- The ratio of negative lookups is high
- The cost of positive exact lookups is high
- A certain false-positive rate is acceptable

Returning Maybe as a definitive positive
Clearing bits to 0 when deleting an element
Applying negative results to a repository newer than the filter
Not observing when capacity is exceeded
Using different string encodings across languages
Storing only a raw bitset without a serialization header
Replacing a corrupted filter with an empty filter
Sharing a mutable bitset non-atomically
Mistaking duplicate inputs for unique elements
Finalizing authorization, payment, or security decisions based solely on a Bloom positive
Returning a negative when a digest of incorrect length is queried

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>
  {
    // Using Maybe as an exact existence result incorrectly.
    return this.#filter.mightContain(
      digest,
    );
  }
  public async deleteAsync(
    digest: Uint8Array,
  ): Promise<void>
  {
    await this.#repository.deleteAsync(
      digest,
    );
    // Clearing a shared bit introduces a false negative for another element.
    this.#filter.clearBitsFor(
      digest,
    );
  }
}

Artifact X was never inserted
but all bits for X are
already 1 due to other artifacts
mightContain(X)
→ true
Service result:
incorrectly returns "exists"

A and B share bit 17
Delete A
→ bit 17 removed
Query B
→ bit 17 is 0
→ false negative

Negative:
Exact lookup can be skipped
Maybe:
Exact lookup required
Delete:
Base Bloom Filter is not modified
→ Rebuild new snapshot

All inserted digests
→ MightContain == true
Invalid digest length in build input
→ InvalidDigest failure
Invalid digest length in lookup input
→ Exception
Same input and spec
→ Same result
Capacity exceeded
→ Explicit failure
Common expected item count upper bound exceeded
→ InvalidExpectedItemCount failure
Target FPP not satisfied even at maximum bitCount
→ FilterTooLarge failure

For a sufficient sample of elements that were not inserted
Is the observed FPP within the target range?

import assert from "node:assert/strict";
import {
  createHash,
} from "node:crypto";
import test from "node:test";
test(
  "No false negatives exist for inserted digests",
  () =>
{
  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(
  "The observed false-positive rate falls within the statistically acceptable range",
  () =>
{
  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,
    `The observed FPP ${observedRate}`
      + `exceeds the allowed upper bound ${upperBound}.`,
  );
});
test(
  "Digests of incorrect length are rejected at query time",
  () =>
{
  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(
  "Exceeding the designed capacity is rejected",
  () =>
{
  const result =
    ArtifactBloomFilter.create(
      createDigests(
        "member",
        101,
      ),
      {
        expectedItemCount: 100,
        targetFalsePositiveRate: 0.01,
      },
    );
  assert.deepEqual(result, {
    kind: "failure",
    error: "capacityExceeded",
  });
});
test(
  "The modeled FPP budget is maintained across all `hashCount` candidates",
  () =>
{
  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(
  "The lower `hashCount` boundary is also computed via candidate evaluation",
  () =>
{
  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
1 False Positive

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

falseDiscoveryRatio
=
False Positives
/ Maybe Results

Digest:
Exactly 32 bytes

Seed 1:
digest[0..8] unsigned big-endian

Seed 2:
digest[8..16] unsigned big-endian
→ Set the lowest bit to 1

Initial index:
seed1 mod bitCount

Step:
(seed2 | 1) mod bitCount

Next index:
(index + step) mod bitCount

Hash count candidates:
Evaluate all k = 1..32

bitCount candidate:
Compute m_required(k) = -kn / ln(1 - targetFpp^(1/k))
Then round up to a multiple of 64

Selection rule:
Choose the smallest bitCount
If bitCount is tied, choose the smallest k
Always verify final modeledFpp <= targetFpp

FPP layers:
targetFpp is the builder's design goal
modeledFpp is the approximation verified at build time
observedFpp is the value measured in operation

Expected item count:
Between 1 and 2³⁰

Bit numbering:
byteIndex = index / 8
bitOffset = index % 8
LSB-first

Serialization of word array implementation:
Expand words into little-endian bytes

bitCount:
Rounded to a multiple of 64 by alignToWord
Upper bound 2³⁰

Do not use a Bloom Filter as an answer table.
If the result is negative, skip the expensive lookup;
if positive, verify against the authoritative store.
The error you accept in exchange for space savings
must cost nothing more than an extra lookup.