maph

Space-efficient approximate mappings using perfect hash functions

View the Project on GitHub queelius/maph

Maph Architecture Documentation

Table of Contents

Overview

Maph (Memory-mapped Approximate Perfect Hash) is a high-performance key-value database that combines memory-mapped I/O with approximate perfect hashing to achieve sub-microsecond lookups. The system is designed for read-heavy workloads where lookup performance is critical.

Key Design Goals

System Design

Architecture Layers

┌─────────────────────────────────────────┐
│         Application Layer               │
│   (REST API, CLI, Client Libraries)     │
├─────────────────────────────────────────┤
│           Maph Core API                 │
│  (get, set, remove, batch operations)   │
├─────────────────────────────────────────┤
│         Hash Function Layer             │
│    (FNV-1a, SIMD optimization)          │
├─────────────────────────────────────────┤
│        Storage Management               │
│   (Slot allocation, version control)    │
├─────────────────────────────────────────┤
│      Memory-Mapped I/O (mmap)           │
│    (OS page cache, virtual memory)      │
├─────────────────────────────────────────┤
│          File System                    │
│      (Persistent storage)               │
└─────────────────────────────────────────┘

Component Interactions

  1. Client Request: Application makes a get/set request
  2. Hash Computation: Key is hashed using FNV-1a algorithm
  3. Slot Location: Hash determines slot index via modulo
  4. Memory Access: Direct memory read/write via mmap
  5. OS Sync: Operating system handles page cache and disk sync

Memory Layout

The database file consists of a header followed by a fixed array of slots:

┌────────────────┐
│   Header       │ 512 bytes
│   (Metadata)   │
├────────────────┤
│   Slot 0       │ 512 bytes
├────────────────┤
│   Slot 1       │ 512 bytes
├────────────────┤
│      ...       │
├────────────────┤
│   Slot N-1     │ 512 bytes
└────────────────┘

Header Structure (512 bytes)

Field Size Description
magic 4 bytes File format identifier (0x4D415048 = “MAPH”)
version 4 bytes Database format version
total_slots 8 bytes Total number of slots
static_slots 8 bytes Number of perfect hash slots
generation 8 bytes Global modification counter
reserved 480 bytes Future extensions

Slot Structure (512 bytes)

Field Size Description
hash_version 8 bytes Atomic 64-bit: hash (32) + version (32)
size 4 bytes Value data size
reserved 4 bytes Future use
data 496 bytes Actual value storage

Memory Alignment

Perfect Hash Function

FNV-1a Algorithm

The system uses FNV-1a (Fowler-Noll-Vo) hash function for its simplicity and good distribution:

uint32_t fnv1a(const char* data, size_t len) {
    uint32_t hash = 2166136261u;  // FNV offset basis
    for (size_t i = 0; i < len; i++) {
        hash ^= data[i];
        hash *= 16777619u;  // FNV prime
    }
    return hash;
}

Hash Properties

Slot Index Calculation

slot_index = hash % total_slots

For static slots (perfect hashing region):

Collision Handling

The database uses a two-tier approach:

Static Slots (Default: 80% of total)

Dynamic Slots (Default: 20% of total)

Probing Strategy

for (size_t i = 0; i < MAX_PROBE_DISTANCE; i++) {
    uint32_t idx = (base_index + i) % total_slots;
    if (slots[idx].empty() || slots[idx].hash() == target_hash) {
        // Found target slot
    }
}

Concurrency Model

Thread Safety Guarantees

Operation Thread Safety Notes
get() ✅ Safe Lock-free reads via atomic operations
set() ⚠️ Unsafe Requires external synchronization
remove() ⚠️ Unsafe Requires external synchronization
scan() ✅ Safe Read-only operation
parallel_* ✅ Safe Internal thread management

Atomic Operations

The hash_version field uses atomic operations for consistency:

  1. Version Increment: Odd version = updating, Even version = stable
  2. Double-Write Pattern:
    • Write hash with version+1 (mark as updating)
    • Copy data
    • Write hash with version+2 (mark as complete)

Lock-Free Reads

Readers can safely access slots without locks:

Performance Optimizations

CPU Cache Optimization

SIMD Acceleration

Memory Access Patterns

Zero-Copy Design

Storage Tiers

Tier 1: CPU Cache (L1/L2/L3)

Tier 2: RAM (Page Cache)

Tier 3: Disk (SSD/HDD)

The OS transparently manages data movement between tiers via the page cache.

Durability and Persistence

Automatic Persistence

Explicit Durability Options

  1. sync(): Request async flush to disk (MS_ASYNC)
  2. sync_now(): Force synchronous flush (MS_SYNC)
  3. DurabilityManager: Background thread for periodic sync

Recovery Semantics

Best Practices

Design Trade-offs

Advantages

Limitations

When to Use Maph

✅ Good fit for:

❌ Not ideal for:

Future Enhancements

Planned Improvements

Research Areas