Nezha: A Key-Value Separated Distributed Store with Optimized Raft Integration

Nezha is a distributed key-value store that resolves the I/O overhead caused by overlapping persistence operations in Raft-based systems by integrating key-value separation with an optimized persistence strategy and leveled garbage collection, thereby achieving significant throughput improvements while maintaining strong consistency.

The Gist

Imagine you run a massive, high-speed library where millions of people are constantly borrowing and returning books. In the world of computers, this library is a Distributed Key-Value Store, and the "books" are data like user profiles, shopping carts, or social media posts.

To keep this library running smoothly across many different buildings (servers), the librarians need a strict rulebook to ensure everyone agrees on which book is where. This rulebook is called Raft.

The Problem: The "Double-Entry" Nightmare

In traditional libraries (like the ones built with standard Raft), every time a librarian writes a new book entry, they have to do it three times to be safe:

1. The Log Book: They write the request in a master log to prove it happened.
2. The Draft: They write it in a temporary "to-do" list (WAL) to make sure it doesn't get lost if the power goes out.
3. The Final Shelf: They finally put the book on the shelf (the storage engine).

The Analogy: Imagine you are a chef writing a recipe. To be safe, you write the recipe in a notebook, then copy it onto a sticky note, and then you actually cook the meal. If the recipe is a huge, complex 50-page novel (a large data value), copying it three times takes forever and wears out your pen (the hard drive). This is called Write Amplification, and it slows everything down.

The Solution: Nezha (The Smart Librarian)

The researchers created a new system called Nezha (named after a powerful Chinese deity known for speed and agility). Nezha changes the rules of the game by separating the "Key" (the book title) from the "Value" (the actual book content).

Here is how Nezha works, using simple metaphors:

1. The "One-Time Write" Trick (KVS-Raft)

Instead of copying the whole 50-page novel three times, Nezha changes the workflow:

• Step 1: The chef writes the entire recipe once into a special, fast "Append-Only Log" (like a scroll that only grows, never shrinks).
• Step 2: The chef writes a tiny index card (just the title and a page number) into the main database.
• The Magic: The database never stores the heavy recipe again. It just stores the tiny index card. When someone wants the recipe, the system looks at the index card, finds the page number in the scroll, and grabs the recipe.

Result: Instead of writing 150 pages of text (3 copies of 50), you only write 50 pages once. This is why Nezha is 460% faster at writing data.

2. The "Smart Cleanup" Crew (Raft-Aware Garbage Collection)

There's a catch: If you only write to a scroll that keeps growing, it eventually becomes a giant, messy pile of paper. Finding a specific page in a messy pile is slow. Also, if you delete a book, the old page is still there, wasting space.

In normal systems, cleaning this up (Garbage Collection) is like trying to reorganize a library while people are still checking out books. It's chaotic and slows everything down.

Nezha introduces a Three-Phase Cleanup:

• Phase 1 (Pre-GC): The library is open. People check out books from the "Active" section.
• Phase 2 (During-GC): The cleaners start working on the "Old" section. But instead of stopping the library, they open a brand new "New" section. All new requests go there. The cleaners sort the old section into neat, alphabetical rows in the background.
• Phase 3 (Post-GC): Once the old section is perfectly sorted and compacted, the library swaps the sections. The messy "Active" section becomes the new "Old" section, and the "New" section becomes the main one.

The Analogy: Imagine a restaurant kitchen. Instead of stopping service to clean the counters, the chefs just move to a second set of clean counters. The cleaners tidy up the first set while the restaurant stays open. When the first set is clean, they switch back. No one ever waits for the cleaning to finish.

3. The "Speedy Search" (Read Performance)

Because Nezha sorts the data during the cleanup, finding a book becomes incredibly fast.

• Before: You had to search through messy piles of old logs and new logs simultaneously.
• Now: The system has a "Hash Index" (like a super-fast phonebook) that tells you exactly where the book is. Even for large data, reading is fast because the data is organized in neat, sequential rows.

The Results: Why Nezha Wins

The paper tested Nezha against other top-tier systems (like TiKV and standard Raft) and found:

• Writing (Put): It was 4.6 times faster because it stopped doing redundant copying.
• Reading Single Items (Get): It was 12.5% faster because the cleanup crew organized the data perfectly.
• Reading Lists (Scan): It was 72.6% faster because the data was sorted, making it easy to grab a whole list of books at once.

Summary

Nezha is like a library that realized it was wasting time copying the same heavy books three times. It decided to write the heavy books once in a special archive and just keep a tiny map in the main room. When the archive gets messy, it uses a clever "switching" trick to clean it up without ever closing the doors.

The result? A system that is incredibly fast at writing, surprisingly fast at reading, and never stops working, even while it's cleaning up its own mess.

Technical Summary

Here is a detailed technical summary of the paper "Nezha: A Key-Value Separated Distributed Store with Optimized Raft Integration."

1. Problem Statement

Distributed key-value stores (KVS) typically rely on the Raft consensus protocol for data consistency and LSM-tree-based storage engines (like RocksDB) for persistence. While effective, this architecture suffers from significant redundant I/O overhead and write amplification due to the decoupled nature of the consensus and storage layers.

Specifically, a single write operation in a traditional Raft-based KVS with an LSM-tree engine requires at least three distinct disk writes:

1. Raft Log Persistence: Writing the log entry to the ValueLog to ensure consensus safety.
2. Storage Engine WAL: Writing the entry to the LSM-tree's Write-Ahead Log (WAL).
3. Memtable Flush: Persisting data to Sorted String Table (SST) files when the MemTable fills up.

Additionally, the LSM-tree's background compaction process introduces further write amplification. This redundancy creates a performance bottleneck, particularly as hardware I/O speeds (e.g., NVMe SSDs) outpace software optimization, making redundant disk writes the primary limiter of throughput.

2. Methodology: The Nezha Architecture

To address these bottlenecks, the authors propose Nezha, a distributed storage system that deeply integrates Key-Value (KV) Separation with the Raft protocol. The system is built on three core architectural innovations:

A. KVS-Raft (Optimized Consensus Layer)

Nezha introduces KVS-Raft, a consensus protocol variant that treats the Raft log itself as the primary value store.

• Mechanism: Instead of storing full key-value pairs in the state machine and the storage engine, the system stores only the value in the Raft ValueLog (an append-only log). The state machine (and the underlying RocksDB instance) stores only lightweight offsets pointing to the value's location in the ValueLog.
• Benefit: This eliminates the need for a separate storage engine WAL and the initial Memtable flush for values. A value is written to disk exactly once (in the ValueLog) rather than three times.

B. Raft-Aware Garbage Collection (GC) Framework

A major challenge of KV separation is that values are stored in an append-only log, leading to fragmentation and poor read performance (random I/O) for range queries. Nezha solves this with a specialized GC framework:

• Dual Storage Strategy: The system maintains Unordered Log Files (for new, raw Raft entries) and Ordered Log Files (compacted, sorted data).
• Three-Phase Request Processing: To ensure consistency and availability during GC, the system divides operations into three phases:
  1. Pre-GC: Reads/Writes go to the Active Storage (Unordered).
  2. During-GC: New requests are redirected to a New Storage module. The system performs asynchronous compaction of the old data into a Final Compacted Storage (Ordered, sorted by key).
  3. Post-GC: The system switches to the Final Compacted Storage and New Storage, discarding the old Active Storage.
• Read Optimization: The GC process reorganizes scattered values into sorted files with hash indexes. This allows point queries to use a hash lookup for the offset and range queries to perform sequential reads on the sorted ValueLog, mitigating the random I/O penalty of KV separation.

C. Three-Phase Request Handling Mechanism

Nezha implements a unified algorithm for handling Put, Get, and Scan operations across the GC lifecycle.

• Writes: Always directed to the current active log, ensuring atomicity.
• Reads: The system intelligently queries multiple storage modules (e.g., New Storage vs. Compacted Storage) in parallel to ensure the most recent data is retrieved without blocking, maintaining strong consistency.

3. Key Contributions

1. Identification of Redundancy: The paper systematically analyzes and quantifies the redundant persistence operations (3x writes) in traditional Raft+LSM architectures, identifying them as the primary performance bottleneck.
2. KVS-Raft Protocol: The design of a novel consensus protocol that integrates KV separation directly into Raft, reducing value persistence from three times to once while preserving Raft's safety guarantees.
3. Raft-Aware GC Framework: A novel garbage collection mechanism that balances read/write performance by reorganizing data into sorted, indexed structures without compromising system availability or consistency.
4. Three-Phase Processing: A robust mechanism to handle concurrent requests during storage reorganization, ensuring correct data retrieval across different GC states.

4. Experimental Results

The authors implemented Nezha in Go and evaluated it against baselines including Original (Raft + RocksDB), TiKV, PASV, LSM-Raft, and Dwisckey (distributed WiscKey).

• Throughput Improvements:
  • Put (Write): 460.2% improvement over the traditional Raft-based system. The advantage grows with larger value sizes (up to 256 KB) due to reduced write amplification.
  • Get (Point Query): 12.5% improvement. While KV separation alone (Nezha-NoGC) hurts read performance by 21.3% due to offset lookups, Nezha's GC and hash indexing recover this loss and surpass the baseline.
  • Scan (Range Query): 72.6% improvement. The sorted data layout in the Final Compacted Storage converts random I/O into sequential I/O, drastically outperforming systems that must traverse multiple SSTable levels.
• Latency: Significant reductions in both write and read latency across various value sizes and YCSB workloads.
• Scalability: Nezha maintains robust performance scaling from 3 to 7 nodes, showing 3.5x to 5.3x higher throughput than the baseline as cluster size increases.
• Recovery: Fault recovery time is reduced by ~33% compared to the baseline due to the smaller data footprint in the state machine (offsets vs. full values).

5. Significance

Nezha represents a paradigm shift in distributed storage design by moving from a layered architecture (where consensus and storage are independent) to a co-designed architecture.

• Efficiency: It fundamentally solves the "double/triple logging" problem, making it highly suitable for modern high-performance NVMe storage and cloud environments where I/O costs and latency are critical.
• Consistency: It proves that aggressive optimizations like KV separation and garbage collection can be implemented without sacrificing the strong consistency guarantees of the Raft protocol.
• Practicality: The system demonstrates that integrating consensus logic with storage management can yield massive performance gains (up to 4.6x) for write-heavy and mixed workloads, offering a viable path forward for next-generation distributed databases.