Maph

I’m happy to help translate the article, but I need the text you’d like translated. Could you please paste the content (or the portion you want translated) here? I’ll keep the source line and all formatting exactly as you requested.

Overview

一个高性能、内存映射的数据库以及用于空间高效近似数据结构的通用框架，支持 O(1) 查找。基于完美哈希函数，maph 提供对任意映射 (f : X → Y) 的亚微秒级访问，具备可配置的存储和自定义解码器。

关键特性

性能概览

int main() {
    // Create a new maph store
    auto store = maph::Maph::create("mystore.maph", 1'000'000);

    // Store JSON key‑value pairs
    store->set(R"({"user":"alice"})", R"({"score":95})");

    // Retrieve with O(1) lookup
    auto value = store->get(R"({"user":"alice"})");
    if (value) {
        std::cout << *value << std::endl;
    }

    // Batch insert
    std::unordered_map<std::string, std::string> batch = {
        {R"({"id":1})", R"({"name":"item1"})"},
        {R"({"id":2})", R"({"name":"item2"})"}
    };
    store->mset(batch);
}

守护进程 & CLI

# Start the maph daemon
./maph_daemon --port 8080 --threads 4

# CLI operations
./maph_cli set mystore '{"key":"user:1"}' '{"name":"Alice","age":30}'
./maph_cli get mystore '{"key":"user:1"}'
./maph_cli scan mystore --limit 100

REST API

# Create a store
curl -X POST http://localhost:8080/stores \
     -d '{"name":"products","slots":1000000}'

# Insert a key
curl -X PUT "http://localhost:8080/stores/products/keys/sku:12345" \
     -d '{"name":"Laptop","price":999}'

# Retrieve the key
curl http://localhost:8080/stores/products/keys/sku:12345

# Optimise for perfect hash (O(1) guaranteed)
curl -X POST http://localhost:8080/stores/products/optimize

架构概览

Core Library (include/maph.hpp)          → Memory‑mapped storage + atomic ops
Approximate Maps (include/maph/approximate_map.hpp) → Generalised X→Y mappings
Decoders (include/maph/decoders.hpp)    → Configurable output transformations
Applications:
  • CLI tool (maph_cli)
  • Daemon (maph_daemon) – JSON DB server
  • REST API (integrations/rest_api) – HTTP interface + web UI

文件布局（磁盘上）

┌─────────────────────┐
│ Header (512 B)       │  Magic, version, slot counts, generation
├─────────────────────┤
│ Slot 0 (512 B)      │  Hash (32 b) + Version (32 b) + Data (504 B)
├─────────────────────┤
│ Slot 1 (512 B)      │  …
├─────────────────────┤
│      …              │
└─────────────────────┘

从源码构建

# 克隆仓库
git clone https://github.com/yourusername/maph.git
cd maph

# 构建
mkdir build && cd build
cmake .. -DCMAKE_BUILD_TYPE=Release \
         -DBUILD_TESTS=ON \
         -DBUILD_REST_API=ON \
         -DBUILD_EXAMPLES=ON
make -j$(nproc)

# 运行测试
ctest --verbose

# 安装
sudo make install

CMake 选项

自定义解码器

// Threshold filter – maps values to bool based on a threshold
template <typename StorageType>
struct ThresholdDecoder {
    using output_type = bool;
    float threshold;

    bool operator()(StorageType value, StorageType max_val) const {
        return static_cast<float>(value) / max_val > threshold;
    }
};

// Quantisation decoder – maps to discrete levels
template <typename StorageType>
struct QuantizeDecoder {
    using output_type = int;
    int levels;

    int operator()(StorageType value, StorageType max_val) const {
        return (value * levels) / (max_val + 1);
    }
};

并行操作

// Parallel batch insert with custom thread count
store->parallel_mset(large_batch, 8);   // 8 threads

// Parallel scan using visitor pattern
std::atomic<size_t> count{0};
store->parallel_scan(
    [&count](uint64_t idx, uint32_t hash, JsonView value) {
        if (value.size() > 100) ++count;
    },
    4   // 4 threads
);

持久性

// Background sync manager (e.g., every 5 s or 1000 ops)
auto manager = store->start_durability_manager(
    std::chrono::seconds(5),   // interval
    1000                       // max ops before sync
);

// Manual sync
store->sync();

存储类型及特性

Comparative Overview

示例用例

• 高性能缓存 – 热数据的亚微秒查找。
• 特征存储 – 具备保证延迟的机器学习特征服务。
• 会话存储 – Web 会话数据的即时访问。
• 近似过滤器 – 可配置精度的布隆过滤器替代方案。
• 速率限制 – 具备 O(1) 检查的令牌桶实现。
• 去重 – 数据流中快速重复检测。
• 图数据库 – 具备完美哈希的邻接表存储。
• 时间序列索引 – 快速时间戳到数据的映射。

API 代码片段 – 创建 / 打开

// Create a new store
auto store = maph::Maph::create("path/to/store.maph", total_slots);

// Open an existing store (read‑only)
auto store = maph::Maph::open("path/to/store.maph", /*read_only=*/true);

API 参考

c_slots = 0);
static std::unique_ptr open(path, readonly = false);

// Basic operations
std::optional get(JsonView key);
bool set(JsonView key, JsonView value);
bool remove(JsonView key);
bool exists(JsonView key);

// Batch operations
void mget(keys, callback);
size_t mset(key_value_pairs);

// Parallel operations
void parallel_mget(keys, callback, threads = 0);
size_t parallel_mset(pairs, threads = 0);
void parallel_scan(visitor, threads = 0);

// Utilities
Stats stats();
void sync();
void close();

贡献

我们欢迎贡献！请参阅 CONTRIBUTING.md 获取指南。

关键贡献领域

• 完美哈希函数实现
• 针对特定用例的额外解码器
• 语言绑定（Python、Rust、Go、Java）
• 性能优化
• 文档和示例

参考文献

这项工作的理论基础：

@inproceedings{rdphfilter2024,
  title   = {Rate-Distorted Perfect Hash Filters},
  author  = {...},
  booktitle = {...},
  year    = {2024}
}

许可证

MIT 许可证 – 请参阅 LICENSE 获取详细信息。

基于完美哈希函数、近似数据结构和空间高效算法的研究。特别感谢 CHD、BBHash 以及其他启发本工作的最小完美哈希算法的作者们。