src/sstable/bloom.cpp - master - smychkov/SStorage

src/sstable/bloom.cpp
128 строк5 KB
Андрей Смычков
docs: перевод оставшихся комментариев на русский + актуализация AGENTS
25 апр 2026, 10:08
25 апр 2026, 10:08f2b9fd9
#include "bloom.hpp"
#include "../util/murmur3.hpp"
#include "../util/varint.hpp"

#include <algorithm>
#include <cmath>
#include <cstring>

namespace sstorage {

//============================================================================
// Конструктор
//============================================================================
// Оптимальное число хэшей: k = (bitsPerKey * ln(2)) ≈ 0.693 * bitsPerKey.
// При bitsPerKey=10 получаем k≈7, FP rate ≈ 0.008 (0.8%).
//============================================================================
BloomFilter::BloomFilter(size_t expectedItems, size_t bitsPerKey) {
    // Общее число бит
    size_t totalBits = expectedItems * bitsPerKey;
    if (totalBits < 64) totalBits = 64;  // минимум, чтобы не было вырожденных случаев

    // Округляем до байт
    size_t totalBytes = (totalBits + 7) / 8;
    bits_.assign(totalBytes, 0);

    // k ≈ 0.693 * bitsPerKey
    numHashes_ = static_cast<uint32_t>(std::round(bitsPerKey * 0.693));
    if (numHashes_ < 1) numHashes_ = 1;
    if (numHashes_ > 30) numHashes_ = 30;   // защита от паранойи
}

//============================================================================
// Базовые хэши
//============================================================================
// Используем два разных seed для MurmurHash3 — получаем два независимых
// 32-битных хэша.
//============================================================================
std::pair<uint32_t, uint32_t> BloomFilter::baseHashes(const std::string& key) {
    uint32_t h1 = util::murmur3(key.data(), key.size(), 0);
    uint32_t h2 = util::murmur3(key.data(), key.size(), 0xBC9F1D34);
    return {h1, h2};
}

//============================================================================
// Добавление ключа в Bloom filter
//============================================================================
// Устанавливаем k битов: bit_i = (h1 + i * h2) mod bitsSize.
// Это и есть техника двойного хэширования Kirsch-Mitzenmacher.
//============================================================================
void BloomFilter::add(const std::string& key) {
    auto [h1, h2] = baseHashes(key);
    const size_t bits = bits_.size() * 8;
    for (uint32_t i = 0; i < numHashes_; ++i) {
        uint32_t combined = h1 + i * h2;
        size_t bitIdx = combined % bits;
        bits_[bitIdx / 8] |= static_cast<uint8_t>(1u << (bitIdx % 8));
    }
    ++keyCount_;
}

//============================================================================
// Проверка наличия ключа (может дать false positive, но никогда negative)
//============================================================================
// Если хотя бы один бит из k не установлен — точно нет.
// Если все установлены — может быть (или false positive).
//============================================================================
bool BloomFilter::mayContain(const std::string& key) const {
    if (bits_.empty()) return false;

    auto [h1, h2] = baseHashes(key);
    const size_t bits = bits_.size() * 8;
    for (uint32_t i = 0; i < numHashes_; ++i) {
        uint32_t combined = h1 + i * h2;
        size_t bitIdx = combined % bits;
        if ((bits_[bitIdx / 8] & (1u << (bitIdx % 8))) == 0) {
            return false;
        }
    }
    return true;
}

//============================================================================
// Сериализация
//============================================================================
void BloomFilter::serialize(std::string& out) const {
    util::encodeVarint(numHashes_, out);
    util::encodeVarint(bits_.size(), out);
    out.append(reinterpret_cast<const char*>(bits_.data()), bits_.size());
}

bool BloomFilter::deserialize(const char* data, size_t len, size_t& consumed) {
    consumed = 0;
    if (data == nullptr && len > 0) return false;

    // Жёсткий лимит на размер Bloom filter (разумный максимум — 128 МБ).
    // Защита от вредоносно большого bitsSize в заголовке.
    constexpr uint64_t kMaxBloomBytes = 128ULL * 1024 * 1024;

    size_t offset = 0;
    uint64_t nHashes;
    size_t n;

    if (!util::decodeVarint(data + offset, len - offset, nHashes, n)) return false;
    offset += n;
    if (nHashes == 0 || nHashes > 30) return false;
    // Защита от integer underflow: offset не может превышать len
    if (offset > len) return false;
    numHashes_ = static_cast<uint32_t>(nHashes);

    uint64_t bitsBytes;
    if (!util::decodeVarint(data + offset, len - offset, bitsBytes, n)) return false;
    offset += n;
    if (offset > len) return false;

    // Лимит на размер битового массива
    if (bitsBytes > kMaxBloomBytes) return false;
    // Проверка через вычитание (len - offset гарантированно >= 0)
    if (bitsBytes > len - offset) return false;

    bits_.assign(data + offset, data + offset + static_cast<size_t>(bitsBytes));
    offset += static_cast<size_t>(bitsBytes);

    consumed = offset;
    keyCount_ = 0;   // точного значения после десериализации не знаем
    return true;
}

}