NexusKV

NexusKV is a distributed, strongly-consistent, high-performance key-value store built from scratch in Go. It uses a custom Raft consensus implementation for replication and safety, and a custom log-structured merge-tree (LSM-tree) storage engine for persistent node-level storage.

Designed as a high-signal portfolio project, NexusKV demonstrates a deep understanding of distributed systems internals, storage engine design, memory-to-disk serialization, and crash-resiliency patterns without relying on third-party consensus or embedded database libraries.

---

Current Status: Phase 1 Complete (Standalone LSM Storage)

The project is structured in incremental build phases to isolate complexity. Currently, Phase 1 is fully complete and verified. The storage engine operates as a standalone, thread-safe, single-process library with passing unit/integration tests and zero external runtime dependencies.

                  ┌──────────────────────────────┐
                  │      Put / Get / Delete      │
                  └──────────────┬───────────────┘
                                 │
                        [storage.Engine]
                                 │
                 ┌───────────────┴───────────────┐
                 ▼                               ▼
        ┌─────────────────┐             ┌─────────────────┐
        │   Append-Only   │             │   In-Memory     │
        │   Write-Ahead   │             │    Memtable     │
        │    Log (WAL)    │             │   (Skip List)   │
        └────────┬────────┘             └────────┬────────┘
                 │ (fsync)                       │
                 ▼                               ▼ (Flushed when size >= 4MB)
            ┌─────────┐                 ┌─────────────────┐
            │  Disk   │                 │  SSTable files  │
            └─────────┘                 │  (000001.sst)   │
                                        └────────┬────────┘
                                                 │
                                                 ▼ (Merged when count >= 4)
                                        ┌─────────────────┐
                                        │   Compacted     │
                                        │  SSTable file   │
                                        └─────────────────┘

---

Core LSM-Tree Components

1. In-Memory Memtable (Custom Skip List)

• Backing Structure: A custom skip list built from scratch (no external library).
• Parameters: Configured with a maximum level of 18 and a node promotion probability of p = 0.25 for optimal average-case $\mathcal{O}(\log N)$ access time.
• Tombstones: Deletions are written as tombstone markers (logical deletes) rather than immediate disk/memory removals, ensuring consistency across flushes.
• Concurrney: Protected by a sync.RWMutex to guarantee safe concurrent reads and writes.

2. Durability Layer (Write-Ahead Log)

• Append-Only writes: Every mutation (Put/Delete) is appended to the WAL and fsync'd to disk before the in-memory Memtable is updated, adhering to ACID durability guidelines.
• Record Format:

  ┌─────────────────┬─────────┬──────────────┬─────────┬──────────────┬───────────┬──────────────┐
  │ Payload Len (4B)│ Op (1B) │ Key Len (4B) │   Key   │ Val Len (4B) │   Value   │  CRC32 (4B)  │
  └─────────────────┴─────────┴──────────────┴─────────┴──────────────┴───────────┴──────────────┘
  

• Crash Recovery & Torn-Write Resilience: Upon startup, the engine replays the WAL sequentially to reconstruct the Memtable state. If it encounters a partial write or a checksum mismatch (CRC32 checked over the length and payload), it halts replay silently, truncates the corrupted tail, and seeks to that boundary to prevent file corruption.

3. On-Disk Storage (SSTables)

• Data Block: Key-value pairs are written sequentially in lexicographically sorted order.
• Sparse Index: An in-memory index stores the offset of every $100\text{-th}$ key. Reads binary-search this sparse index to find the starting file offset of the target data block, keeping memory footprint low.
• Bloom Filter: Serialized at the end of each SSTable. Lookups query the filter first to short-circuit reads for absent keys.
• Footer: A fixed 32-byte tail containing offsets for index/bloom sections, key count, and the magic number 0x4E5855534B563031 ("NXUSKV01").

4. Size-Tiered Compaction

• Automatically triggers when $\ge 4$ SSTables accumulate.
• Performs a multi-way merge of the oldest SSTables, removing duplicate keys (keeping the newest term) and purging tombstones.
• Tombstone Garbage Collection: To prevent data resurrection, tombstones are safely garbage-collected (dropped) only if the compaction group includes the absolute oldest SSTable in the system.
  • Correctness Guarantee: Since compaction is always triggered on e.sstables[n-4:] (the oldest 4 SSTables in the system, where n = len(e.sstables)), the compaction group is guaranteed to always include the absolute oldest active SSTable in the database. Thus, there are no active SSTables older than the compaction group, which ensures that no stale value can survive and resurrect after a tombstone shadowing it is dropped.

---

Read Path Resolution

When Get(key) is invoked, the engine resolves the query using a newest-wins search order:

  Step 1: Check active Memtable (in-memory)
    ├── Found -> Return value / ErrKeyNotFound (if tombstone)
    └── Not Found -> Continue
          │
  Step 2: Check immutable Memtables pending flush (in-memory)
    ├── Found -> Return value / ErrKeyNotFound (if tombstone)
    └── Not Found -> Continue
          │
  Step 3: Check SSTables from newest to oldest (disk)
    ├── Query Bloom Filter
    │     ├── "Definitely Absent" -> Skip SSTable
    │     └── "Maybe Present" -> Continue
    │           │
    │           └── Binary-search Sparse Index to find block range
    │                 └── Scan range sequentially
    │                       ├── Found -> Return value / ErrKeyNotFound (if tombstone)
    │                       └── Not Found -> Continue
          │
  Step 4: Return ErrKeyNotFound

---

Getting Started

Prerequisites

• Go: Version 1.22 or higher.

Installation

Clone the repository and verify the storage engine:

git clone https://github.com/onlyarnav/nexus-kv.git
cd nexus-kv
go test -v ./internal/storage/...

Usage Example

Here is how you can import and use the standalone LSM storage engine:

package main

import (
	"fmt"
	"log"
	"nexuskv/internal/storage"
)

func main() {
	// Configure the storage engine
	cfg := storage.Config{
		DataDir:           "./data",
		MemtableSizeBytes: 4 * 1024 * 1024, // 4MB flush threshold
		BloomFilterBits:   10,               // 10 bits per item for Bloom Filter
	}

	// Open or recover the engine
	engine, err := storage.Open(cfg)
	if err != nil {
		log.Fatalf("Failed to open storage engine: %v", err)
	}
	defer engine.Close()

	// 1. Put key-value pair (durable, fsync'd to WAL)
	err = engine.Put([]byte("name"), []byte("NexusKV"))
	if err != nil {
		log.Fatalf("Write failed: %v", err)
	}

	// 2. Get key-value pair
	val, err := engine.Get([]byte("name"))
	if err != nil {
		log.Fatalf("Read failed: %v", err)
	}
	fmt.Printf("Retrieved name: %s\n", string(val))

	// 3. Delete key-value pair
	err = engine.Delete([]byte("name"))
	if err != nil {
		log.Fatalf("Delete failed: %v", err)
	}

	// 4. Verify deletion
	_, err = engine.Get([]byte("name"))
	if err == storage.ErrKeyNotFound {
		fmt.Println("Key 'name' was successfully deleted!")
	}
}

---

Verification & Metrics

All metrics documented below are measured directly from the test runs in internal/storage:

1. Bloom Filter Efficiency

• Zero False Negatives: Verified across 100,000 inserted keys.
• False-Positive Rate: Measured at 0.86% with 10 bits/item (861 false positives out of 100,000 queries for absent keys).

2. SSTable Read Short-Circuiting

• Bloom Filter Exclusion: Verified over 10,000 queries for absent keys.
• Efficiency: Only 1.53% of queries reached the disk search stage. 98.47% of absent lookups were short-circuited instantly by the bloom filter, bypassing disk binary-search and block scans completely.

3. Crash Recovery Correctness

• State Restoration: Replaying a WAL filled with 100 uncommitted writes fully recovers the active memtable state.
• Resiliency: Partial record writes (torn writes) or corrupted CRC records are truncated automatically, restoring the engine database files to the last coherent, fsync-committed transaction.