tests/test_bloom.cpp - master - smychkov/SStorage

tests/test_bloom.cpp
123 строки4 KB
Андрей Смычков
feat: Bloom filter (MurmurHash3 double hashing)
25 апр 2026, 09:05
25 апр 2026, 09:059951796
//============================================================================
// Тесты для Bloom filter
//============================================================================
#include "../src/sstable/bloom.hpp"
#include <iostream>
#include <set>
#include <string>
#include <unordered_set>

using namespace sstorage;

static int g_passed = 0;
static int g_failed = 0;

#define CHECK(cond) do { \
    if (cond) { ++g_passed; } \
    else { ++g_failed; std::cerr << "FAIL: " #cond " at line " << __LINE__ << "\n"; } \
} while (0)

int main() {
    // 1. Пустой Bloom — ничего не содержит
    {
        BloomFilter bf(100);
        CHECK(!bf.mayContain("anything"));
    }

    // 2. No false negatives: добавили ключ — гарантированно mayContain==true
    {
        BloomFilter bf(1000);
        for (int i = 0; i < 1000; ++i) {
            bf.add("key_" + std::to_string(i));
        }
        for (int i = 0; i < 1000; ++i) {
            CHECK(bf.mayContain("key_" + std::to_string(i)));
        }
    }

    // 3. False positive rate ~1% при bitsPerKey=10
    {
        BloomFilter bf(10000, 10);
        std::unordered_set<std::string> added;
        for (int i = 0; i < 10000; ++i) {
            std::string k = "added_" + std::to_string(i);
            bf.add(k);
            added.insert(k);
        }

        int falsePositives = 0;
        int tested = 0;
        for (int i = 0; i < 10000; ++i) {
            std::string k = "not_added_" + std::to_string(i);
            if (added.count(k)) continue;   // пропустить настоящие
            ++tested;
            if (bf.mayContain(k)) ++falsePositives;
        }
        double fpRate = static_cast<double>(falsePositives) / tested;
        std::cout << "  FP rate: " << fpRate << " (" << falsePositives
                  << "/" << tested << ")\n";
        // Теоретически должно быть ~0.008, допускаем до 0.03
        CHECK(fpRate < 0.03);
    }

    // 4. Sanity check: правильное число хэшей для bitsPerKey=10
    {
        BloomFilter bf(100, 10);
        // k ≈ 0.693 * 10 ≈ 7
        CHECK(bf.numHashes() >= 5 && bf.numHashes() <= 9);
    }

    // 5. Roundtrip через сериализацию
    {
        BloomFilter bf(500, 10);
        for (int i = 0; i < 500; ++i) {
            bf.add("item_" + std::to_string(i));
        }

        std::string buf;
        bf.serialize(buf);

        BloomFilter restored;
        size_t consumed;
        CHECK(restored.deserialize(buf.data(), buf.size(), consumed));
        CHECK(consumed == buf.size());
        CHECK(restored.numHashes() == bf.numHashes());
        CHECK(restored.bitsSize() == bf.bitsSize());

        // Все добавленные ключи должны находиться
        for (int i = 0; i < 500; ++i) {
            CHECK(restored.mayContain("item_" + std::to_string(i)));
        }
    }

    // 6. Маленький фильтр (минимум 64 бита)
    {
        BloomFilter bf(1, 10);
        CHECK(bf.bitsSize() >= 64);
        bf.add("only_key");
        CHECK(bf.mayContain("only_key"));
    }

    // 7. Бинарные ключи
    {
        BloomFilter bf(10);
        std::string binary_key("\x00\x01\xFF\xFE", 4);
        bf.add(binary_key);
        CHECK(bf.mayContain(binary_key));
    }

    // 8. Поломанный буфер при десериализации
    {
        BloomFilter restored;
        size_t consumed;
        CHECK(!restored.deserialize("", 0, consumed));

        // Невалидное numHashes (0)
        std::string buf;
        buf.push_back(0);   // numHashes = 0
        CHECK(!restored.deserialize(buf.data(), buf.size(), consumed));
    }

    std::cout << "test_bloom: passed=" << g_passed << " failed=" << g_failed << "\n";
    return g_failed == 0 ? 0 : 1;
}