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

When a dataset is loaded or optimized, maph constructs a minimal perfect hash function for the known key set K. For these keys, the perfect hash function $h_p:K\to [0,n-1]$ guarantees collision-free mapping:

This provides O(1) worst-case lookup time with exactly one memory access per query—no probing required. The perfect hash function stores minimal metadata to identify which keys it was built for.

Keys not in the original dataset K (inserted after optimization or before initial optimization) use a standard FNV-1a hash function $h_s$ combined with linear probing:

The maximum probe distance (default 10) ensures bounded worst-case latency. If all probe positions are occupied, the insertion fails with a table-full error.

Each slot stores a hash identifier in its metadata. During lookup, the system:

1. 1.

   Computes the initial slot position using the appropriate hash function

2. 2.

   Reads the slot’s hash identifier atomically

3. 3.

   Compares it with the expected hash of the key

4. 4.

   If matching, returns the value; otherwise probes the next slot

5. 5.

   Terminates on empty slot (key not found) or after MAX_PROBES attempts

This approach provides false positive rates dependent on hash collision probability. For a 32-bit hash identifier, the false positive rate is approximately $2^{-32}\approx 2.3\times {10}^{-10}$ per comparison.

Modern CPUs fetch data in 64-byte cache lines. Aligning slots to cache line boundaries prevents false sharing—a performance pathology where independent updates to adjacent memory locations contend for the same cache line. With 512-byte slots aligned to 64 bytes, each slot spans exactly 8 cache lines, ensuring updates to different slots never conflict.

Each slot contains:

• •

  Metadata (16 bytes):

  • –

    Atomic hash_version (8 bytes): Upper 32 bits store the key’s hash identifier for verification; lower 32 bits store a version counter for lock-free updates

  • –

    Size field (4 bytes): Length of stored value in bytes

  • –

    Reserved (4 bytes): Padding for future extensions

• •

  Data (496 bytes): Actual value storage

The fixed size simplifies memory management—slot addresses can be computed directly:

This eliminates pointer indirection and enables SIMD operations on slot arrays.

Fixed-size slots waste space for small values but provide predictable performance. The default 512-byte size targets typical JSON documents (100-400 bytes) with acceptable overhead. Applications with different value size distributions can select alternative slot sizes at compile time:

• •

  Small values: mmap_storage<128> reduces waste for counters and flags

• •

  Large values: mmap_storage<4096> accommodates documents without external storage

The compile-time parameterization allows applications to optimize the space-performance tradeoff for their specific workload without sacrificing predictability.

Each slot maintains a 64-bit atomic value combining the key hash (high 32 bits) and version number (low 32 bits). The version increments on each modification, allowing readers to detect concurrent updates:

Writers use a two-phase protocol:

1. 1.

   Increment version to odd (marking slot as updating)

2. 2.

   Write new data

3. 3.

   Increment version to even (marking update complete)

This ensures readers either see the old value or new value completely, never partial updates.

We use acquire-release memory ordering to ensure visibility across threads:

• •

  Acquire loads: Prevent subsequent memory operations from being reordered before the load

• •

  Release stores: Prevent previous memory operations from being reordered after the store

These guarantees are sufficient for our versioning protocol while being more efficient than sequential consistency.

The core maph library is a generic template-based framework with configurable slot sizes:

The slot size is a compile-time template parameter, allowing instantiation with arbitrary sizes optimized for specific workloads:

• •

  mmap_storage<128>: Small values (counters, flags, short strings)

• •

  mmap_storage<512>: Default for typical JSON documents (100-400 bytes)

• •

  mmap_storage<1024>: Larger structured data

• •

  mmap_storage<4096>: Page-aligned for large objects

The 512-byte default balances cache line alignment (8$\times$ 64-byte cache lines), typical value sizes, and space efficiency. Applications with different requirements can select appropriate slot sizes at compile time without modifying the core library.

For inter-process communication, we implement a JSON-based key-value store using the default 512-byte slot instantiation. Both keys and values are JSON values (strings, numbers, objects, arrays), providing:

• •

  Universal format readable across programming languages

• •

  Human-readable debugging and inspection

• •

  Rich data types beyond simple strings

• •

  Standard serialization via libraries like nlohmann::json

The JSON store instantiates mmap_storage<512> with string keys and JSON-serialized values, demonstrating how the general C++ library applies to practical IPC scenarios. The 512-byte slot size accommodates typical JSON documents while maintaining cache efficiency.

The mmap-based design enables a powerful hybrid architecture where different processes access the same data store through different mechanisms:

Pattern 1: Single Writer, Multiple Readers (Recommended)

The recommended deployment pattern uses a REST API server as the single writer, with local C++ applications reading directly via mmap:

This pattern provides:

• •

  Zero-IPC overhead: Local reads bypass HTTP entirely, achieving $\sim$300ns latency versus $\sim$1-2ms via REST

• •

  Safety: Single writer eliminates race conditions without coordination overhead

• •

  Flexibility: Remote clients use HTTP, local apps use direct mmap access

• •

  5,000$\times$ speedup: Direct mmap reads are approximately 5,000$\times$ faster than HTTP requests for local access

Pattern 2: Multi-Writer with Coordination

For applications requiring multiple C++ writers, explicit synchronization is necessary. While atomic slot operations ensure individual writes are consistent, they do not prevent read-modify-write races between concurrent writers:

File locking adds approximately 2$\mu$s overhead per operation but prevents lost updates in multi-writer scenarios. Alternative coordination mechanisms include:

• •

  Application-level tokens (Redis, etcd)

• •

  Partitioning (different processes own different key ranges)

• •

  Message queue coordination

The provided REST API server (using libmicrohttpd) demonstrates practical deployment:

• •

  HTTP endpoints: GET, PUT, DELETE for key-value operations

• •

  Store management: CREATE, LIST, DELETE for store lifecycle

• •

  Optimization: POST /stores/{name}/optimize for perfect hash construction

• •

  Shared mmap: All stores memory-mapped for direct C++ access

The server acts as the single writer, ensuring safety while enabling zero-overhead local reads by collocated C++ applications. Remote clients access via HTTP, trading latency ($\sim$1-2ms) for network transparency and language interoperability.

Table I compares access patterns:

The hybrid architecture enables applications to choose the optimal access pattern based on deployment requirements, achieving both ultra-low latency for local access and network transparency for distributed access.

Safety: The single-writer pattern is strongly recommended. Multi-writer scenarios require explicit coordination (file locks, application tokens) to prevent race conditions. While atomic operations ensure individual slot writes are consistent, they do not prevent lost updates from concurrent read-modify-write operations.

Monitoring: The REST API server provides HTTP endpoints for monitoring store statistics, enabling operational visibility without custom tooling.

Language Interoperability: The JSON format and HTTP API enable polyglot systems where different components use different programming languages while sharing the same data store.

The Fowler-Noll-Vo 1a variant provides good distribution with minimal computational overhead:

The algorithm processes one byte at a time with only XOR and multiplication operations, achieving 3-4 cycles per byte on modern CPUs.

For longer keys, xxHash [26] provides superior throughput by processing 32-bit chunks:

• •

  Processes 4 bytes per iteration

• •

  Exploits instruction-level parallelism

• •

  Achieves 13 GB/s on a single core

We use FNV-1a for keys under 16 bytes and xxHash for longer keys, selected at compile time based on profiling data.

While mmap provides automatic persistence, we offer explicit durability control for applications requiring guaranteed persistence:

MS_ASYNC initiates asynchronous writeback without blocking, while MS_SYNC forces synchronous write for strong durability guarantees.

The OS’s copy-on-write mechanism enables efficient snapshots:

1. 1.

   Fork the process to create a snapshot

2. 2.

   Child process inherits the memory mapping

3. 3.

   Pages are copied only when modified

4. 4.

   Snapshot remains consistent during export

This provides point-in-time backups without blocking writers or duplicating unchanged data.

Latency measurements use std::chrono::high_resolution_clock with nanosecond precision. Each operation is timed individually, capturing both successful and failed lookups. We report min, median, p90, p95, p99, p99.9, and p99.99 percentiles to characterize tail latency behavior.

For single-threaded latency tests, we execute 10,000 warmup iterations to ensure caches are hot, followed by 1 million measured operations. Throughput tests measure elapsed wall-clock time for a fixed number of operations across all threads.

Keys are pre-generated strings of the form "key:N" where N ranges from 0 to the dataset size. Values are JSON-like strings with consistent size (default 200 bytes) to simulate typical web application data. For realistic access patterns, we use a Zipfian distribution with skew parameter $\theta =0.99$, modeling the 80-20 rule where a small fraction of keys receives most accesses.

All tests use in-memory operation to isolate hash table performance from I/O effects. The maph database is configured with slot count set to $2\times$ the number of keys (50% load factor) to balance space efficiency with probe distance. For comparison baselines:

• •

  maph: In-memory heap storage, perfect hash disabled for standard hash mode

• •

  std::unordered_map: Default hash function, load factor 1.0

• •

  Redis/Memcached: Accessed via loopback network (unavoidable for architecture)

• •

  RocksDB: In-memory mode, bloom filters enabled, block cache sized to hold working set

All experiments are repeated 3 times with different random seeds. We report median values across runs with standard deviation. For latency distributions, we collect per-operation measurements and compute percentiles over the full sample. Throughput is computed as total operations divided by elapsed wall-clock time.

Note: The performance numbers in Tables I-V below are preliminary estimates based on expected performance. Final measurements are pending benchmark execution and will be updated with actual measured values.

Figure LABEL:fig:latency-cdf shows the cumulative distribution of GET operation latencies for 1 million random keys from a 10 million key database.

maph achieves sub-microsecond median latency (351ns for random GET), demonstrating the effectiveness of memory-mapped perfect hashing. Tail latency (p99.99) remains under 10 microseconds, providing predictable performance. Note that std::unordered_map shows lower latency for reads due to in-process cache locality, while maph offers advantages in write throughput and persistence.

Figure LABEL:fig:throughput-scaling illustrates throughput scaling with increasing thread counts for read-only workloads.

maph exhibits near-linear scaling up to 4 threads (110% efficiency), demonstrating the effectiveness of our lock-free read design. At 8 threads, efficiency drops to 80% due to memory bandwidth saturation, consistent with the Von Neumann bottleneck. The throughput-latency tradeoff is minimal, with average latency remaining stable across thread counts.

Table IV compares bulk insert performance between maph and std::unordered_map:

maph achieves 1.88$\times$ faster bulk inserts than std::unordered_map, demonstrating the efficiency of memory-mapped I/O for write operations. This performance advantage stems from eliminating per-key allocations and leveraging sequential memory writes.

Each storage instantiation uses a fixed slot size chosen at compile time. While the size is configurable (mmap_storage<SlotSize>), it remains constant for a given database file. Applications with heterogeneous value sizes may experience space overhead—for example, the default 512-byte slots waste space for small counters. Variable-size allocation would improve space efficiency but would complicate memory management and destroy performance predictability. Applications can mitigate this by choosing appropriate slot sizes for their workload or using multiple stores with different slot sizes.

The perfect hash optimization provides O(1) lookups only for keys in the original dataset. New keys use standard FNV-1a hashing with linear probing, which may experience degraded performance if the table becomes full. Workloads with highly dynamic key sets must provision sufficient slots or periodically rebuild the perfect hash function.

maph operates on a single machine, limited by available memory and CPU cores. Distributed operation would require additional coordination protocols, likely sacrificing the sub-microsecond latency guarantee. Applications requiring horizontal scaling must implement sharding at the application level.

While mmap provides durability, it does not guarantee crash consistency for multi-slot transactions. Applications requiring ACID semantics must implement their own transaction protocols or use maph as a cache with a backing transactional store.

While maph currently supports compile-time slot size selection, runtime-adaptive slot allocation could further improve space efficiency. A hybrid approach with multiple slot classes (64B, 512B, 4KB) dynamically selected based on value size could reduce waste while maintaining predictability. This would require metadata to track slot classes and complicate the memory layout but could benefit workloads with highly variable value sizes.

Machine learning models could replace perfect hash functions, learning the key distribution online [28]. Neural networks or decision trees could provide better collision rates than traditional hash functions for skewed distributions.

Intel Optane DC Persistent Memory provides byte-addressable persistence with DRAM-like latency. Adapting maph for persistent memory could eliminate the page cache layer while maintaining durability, potentially reducing latency further.

Integrating consensus protocols like Raft [29] could enable distributed operation while maintaining consistency. Carefully designed protocols could minimize latency impact for the common case of no failures.