maph: Maps Based on Perfect Hashing for Sub-Microsecond Key-Value Storage

// Traditional approach: Multiple copies
std::vector<uint8_t> data = read_from_disk(key);  // Kernel -> user copy
Value v = deserialize(data);                      // Another copy
process(v);                                        // Yet another copy

// maph approach: Direct memory access
auto store = maph::Maph::open("mystore.maph");
auto value = store->get(key);  // Zero copies. Direct pointer into mmap region

// Lock-free read
uint64_t v1 = slot.hash_version.load(acquire);
uint32_t hash = v1 >> 32;
if (hash != hash(key)) return nullopt;  // Key not found

// Copy data while checking version
data = copy(slot.data);
uint64_t v2 = slot.hash_version.load(acquire);

if (v1 == v2 && (v1 & 1) == 0) {  // Even version = consistent
    return data;
}
// Retry if version changed

Slot Structure (512 bytes):
+-----------------------------+
| Metadata (16 bytes)         |
|  - hash_version (8B atomic) |  Upper 32 bits: hash identifier
|  - size (4B)                |  Lower 32 bits: version counter
|  - reserved (4B)            |
+-----------------------------+
| Data (496 bytes)            |  Actual value storage
+-----------------------------+

mmap_storage<128> counters;     // Small values
mmap_storage<512> json_store;   // Default
mmap_storage<4096> documents;   // Large values

void compute_batch_avx2(const char** keys, uint32_t* hashes, size_t count) {
    __m256i fnv_prime = _mm256_set1_epi32(16777619u);
    __m256i fnv_offset = _mm256_set1_epi32(2166136261u);

    for (size_t i = 0; i + 8 <= count; i += 8) {
        __m256i h = fnv_offset;
        size_t min_len = find_min_length(keys + i, 8);

        for (size_t j = 0; j < min_len; ++j) {
            __m256i chars = gather_chars(keys + i, j);
            h = _mm256_xor_si256(h, chars);
            h = _mm256_mullo_epi32(h, fnv_prime);
        }

        _mm256_storeu_si256((__m256i*)(hashes + i), h);
    }
}

+----------------------------------+
| Shared mmap Files (data/*.maph)  |
+----------+-------------+---------+
           |             |
     (write)|             |(read-only)
   +--------v---+  +------v----------+
   | REST API   |  | C++ App         |
   | Server     |  | (direct mmap)   |
   +------------+  +-----------------+
        |
   (HTTP)|
   +-----v----------+
   | Remote Clients |
   +----------------+

// Local C++ application: Direct read-only access (~300ns latency)
auto db = maph::Maph::open("/var/lib/maph/data/cache.maph",
                           true);  // readonly
auto value = db->get("hot_key");  // Zero IPC overhead

# Start 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"}'

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

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

curl 'http://localhost:8080/stores/products/keys/"sku:12345"'

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

class DurabilityManager {
    void sync_thread() {
        while (running) {
            sleep_for(sync_interval);
            msync(mapped_region, region_size, MS_ASYNC);  // Async writeback
        }
    }
};

// Configure background sync
auto manager = store->start_durability_manager(
    std::chrono::seconds(5),  // Sync every 5 seconds
    1000                       // Or after 1000 operations
);

// Manual sync for strong durability
store->sync();  // MS_SYNC forces synchronous write

void parallel_scan(std::function<void(Slot&)> visitor, size_t num_threads) {
    std::atomic<size_t> next_chunk{0};
    constexpr size_t CHUNK_SIZE = 1024;

    std::vector<std::thread> threads;
    for (size_t t = 0; t < num_threads; ++t) {
        threads.emplace_back([&] {
            size_t chunk;
            while ((chunk = next_chunk.fetch_add(1)) < total_slots / CHUNK_SIZE) {
                size_t start = chunk * CHUNK_SIZE;
                size_t end = std::min(start + CHUNK_SIZE, total_slots);

                for (size_t i = start; i < end; ++i) {
                    if (!slots[i].empty()) {
                        visitor(slots[i]);
                    }
                }
            }
        });
    }

    for (auto& t : threads) t.join();
}

git clone https://github.com/queelius/maph.git
cd maph
mkdir build && cd build
cmake .. -DCMAKE_BUILD_TYPE=Release \
         -DBUILD_TESTS=ON \
         -DBUILD_REST_API=ON
make -j$(nproc)
ctest --verbose
sudo make install

#include <maph.hpp>

auto store = maph::Maph::create("mystore.maph", 1000000);

store->set(R"({"user": "alice"})", R"({"score": 95})");

auto value = store->get(R"({"user": "alice"})");
if (value) {
    std::cout << *value << std::endl;
}

// Batch operations
std::vector<std::pair<JsonView, JsonView>> batch = {
    {R"({"id": 1})", R"({"name": "item1"})"},
    {R"({"id": 2})", R"({"name": "item2"})"}
};
store->mset(batch);

// Parallel batch processing
store->parallel_mset(large_batch, 8);  // Use 8 threads