An in-memory key-value store engine built from scratch in Java with Spring Boot. Features a custom open-addressing hash table, TTL-based expiration, snapshot persistence, and a REST API — no external dependencies beyond Spring Boot itself.

Key-value stores are at the heart of systems like Redis, Memcached, and DynamoDB. This project implements the core mechanics from scratch:

• Custom hash table with open addressing and linear probing (no java.util.HashMap)
• TTL expiration using both lazy eviction (on access) and active eviction (scheduled sweep)
• Snapshot persistence with atomic file writes (inspired by Redis RDB)
• Thread-safe concurrent access via ReadWriteLock

# Set a key
curl -X PUT http://localhost:8080/api/kv \
  -H "Content-Type: application/json" \
  -d '{"key": "user:1", "value": "Mo Shirmohammadi", "ttlMs": -1}'

# {"success":true,"message":"Key 'user:1' set"}

# Get a key
curl http://localhost:8080/api/kv/user:1

# {"success":true,"key":"user:1","value":"Mo Shirmohammadi"}

# Set with TTL (expires in 5 seconds)
curl -X PUT http://localhost:8080/api/kv \
  -H "Content-Type: application/json" \
  -d '{"key": "session:abc", "value": "token123", "ttlMs": 5000}'

# Delete a key
curl -X DELETE http://localhost:8080/api/kv/user:1

# View all keys
curl http://localhost:8080/api/kv

# {"user:1":"Mo Shirmohammadi","session:abc":"token123"}

# Internal hash table stats
curl http://localhost:8080/api/stats

# {"size":2,"capacity":64,"loadFactor":0.03125,"totalGets":1,"totalSets":2,...}

# Persist to disk
curl -X POST http://localhost:8080/api/snapshot/save

# Restore from disk
curl -X POST http://localhost:8080/api/snapshot/load

Prerequisites: Java 17+, Maven 3.8+

git clone https://github.com/mohosy/kv-store-engine.git
cd kv-store-engine

# Build
mvn clean package

# Run
java -jar target/kv-store-engine-1.0.0.jar

# Run tests
mvn test

Docker:

docker build -t kv-store-engine .
docker run -p 8080:8080 kv-store-engine

src/main/java/com/mohosy/kvstore/
├── KvStoreApplication.java        # Spring Boot entry point
├── engine/
│   ├── HashTable.java             # Custom hash table (open addressing, linear probing)
│   ├── Entry.java                 # Key-value entry with TTL metadata
│   ├── EvictionScheduler.java     # Scheduled active TTL eviction
│   ├── SnapshotManager.java       # Binary snapshot persistence
│   └── EngineConfig.java          # Spring bean configuration
├── service/
│   └── KvStoreService.java        # Business logic layer
├── controller/
│   └── KvController.java          # REST API endpoints
└── dto/
    ├── SetRequest.java            # Request body DTO
    ├── KvResponse.java            # Unified response envelope
    └── StatsResponse.java         # Stats response DTO

The hash table uses open addressing with linear probing instead of separate chaining:

• Cache locality: Entries are stored inline in a contiguous array, reducing pointer chasing compared to linked-list chaining.
• FNV-1a hash function with bit-spreading to minimize clustering with power-of-2 table sizes.
• Tombstone deletion: Deleted entries are marked rather than removed, preserving probe sequences. Tombstones are cleaned up during rehashing.
• Dynamic resizing: The table doubles when the load factor exceeds 0.75, keeping amortized O(1) insertions.

Space complexity: O(n) where n = table capacity.

Two-phase eviction modeled after Redis:

1. Lazy eviction: On every GET, if the entry is expired, it's evicted immediately. This is O(1) and handles hot keys efficiently.
2. Active eviction: A scheduled task sweeps the entire table at a configurable interval (default: 1s), removing expired entries. This prevents memory leaks from write-heavy workloads where keys are set but never read.

Inspired by Redis RDB snapshots:

• Binary format with a magic header (KVS\x01) for validation.
• Writes to a temp file, then performs an atomic rename to prevent corruption on crash.
• On restore, expired entries are discarded and remaining TTLs are recalculated.

24 tests covering the hash table engine and REST API:

$ mvn test

Tests run: 24, Failures: 0, Errors: 0, Skipped: 0
BUILD SUCCESS

Unit tests (HashTableTest): SET/GET, overwrite, delete, TTL expiration, resize, collision handling, eviction, stats.

Integration tests (KvControllerIntegrationTest): Full HTTP round-trip tests using Spring MockMvc — CRUD operations, validation, snapshot save/load.

• Java 17 - Language
• Spring Boot 3.2 - Web framework and dependency injection
• JUnit 5 - Unit and integration testing
• Maven - Build tool

Mo Shirmohammadi - github.com/mohosy