Phase 1 PRD — Embedded Log-Structured Key-Value Store (Core Persistence)

Version 0.1
Scope: Single-process • Single-writer • Embedded library
No concurrency, no compaction, no mmap yet.

---

1️⃣ Goal

Deliver a minimal embedded key–value store that:

• Persists data to disk using an append-only log
• Supports put, get, and delete
• Recovers correctly after process restart
• Maintains an in-memory index for fast reads

This phase prioritizes correctness, crash recovery, and clear invariants over performance.

---

2️⃣ Core Concepts & Invariants

2.1 Record

A record is an immutable entry appended to the log.

Each record represents one logical operation:

• Insert / update
• Delete (tombstone)

---

2.2 Log

• A single append-only file
• Never modified in place
• Only appended to
• Replayed in full at startup

Invariant:

The log is the source of truth.
The in-memory index is always reconstructible from the log.

---

2.3 Index

• In-memory HashMap<Key, LogOffset>
• Points to the latest record for a given key
• Built by replaying the log on startup

---

2.4 Deletion Model

• Deletes are represented by tombstone records
• Tombstones override previous values
• Tombstones are retained indefinitely in Phase 1

---

3️⃣ Functional Requirements

3.1 Store Initialization

API

pub fn open(path: impl AsRef<Path>) -> Result<KvStore>;

Behavior

• If file does not exist:
  • Create it
  • Initialize empty index
• If file exists:
  • Open for read + append
  • Replay log from byte 0
  • Rebuild index
• Truncated tail record:
  • Ignore partial record
  • Log warning (not fatal)

---

3.2 Put (Insert / Update)

API

pub fn put(&mut self, key: &[u8], value: &[u8]) -> Result<()>;

Behavior

1. Append record to log
2. Flush write buffer
3. Update index to new record offset

Constraints

• key.len() <= 1024
• value.len() <= 1 MB
• Reject empty key

Durability

• Record must reach OS buffers before returning
• fsync is not required in Phase 1

---

3.3 Get (Read)

API

pub fn get(&self, key: &[u8]) -> Result<Option<Vec<u8>>>;

Behavior

• If key not in index → Ok(None)
• Read record from log at stored offset
• If tombstone → Ok(None)
• Otherwise return value bytes

---

3.4 Delete

API

pub fn delete(&mut self, key: &[u8]) -> Result<()>;

Behavior

• Append tombstone record
• Update index to point to tombstone offset

Idempotency

• Deleting a non-existent key is allowed
• Subsequent get must return None

---

4️⃣ On-Disk Format (Version 1)

All values stored in little-endian.

| magic (u32) | key_len (u32) | val_len (u32) | key bytes | value bytes |

Field Definitions

Field	Description
magic	Constant 0xBEEFCAFE for record validation
key_len	Length of key in bytes
val_len	Length of value in bytes; 0 indicates tombstone
key bytes	Raw key
value bytes	Raw value

---

Record Validity Rules

• key_len > 0
• key_len ≤ 1024
• val_len ≤ 1 MB
• Record must be fully readable
• Partial trailing record is ignored at startup

---

5️⃣ Error Model

Public Error Type

pub enum KvError {
    Io(std::io::Error),
    InvalidKey,
    ValueTooLarge,
    CorruptRecord { offset: u64 },
}

Error Behavior

• Corrupt record in middle of file → fatal
• Truncated record at end → ignored
• No panics in public API

---

6️⃣ Non-Functional Requirements

Aspect	Requirement
Durability	Survives process restart
Performance	≥ 10k ops/sec on local SSD
Memory	Index entirely in memory
Threading	Single-threaded
Dependencies	Std only (no serde, no mmap, no async)
Logging	Optional debug logging (feature-gated)

---

7️⃣ Operational Constraints

• One open writer at a time
• Store directory contains:
  • data.log only
• Caller controls lifecycle (library, not daemon)
• No background threads

---

8️⃣ Acceptance Criteria (Sanity Tests)

1. Basic Persistence

   • Put key
   • Restart process
   • Get key → value matches

2. Overwrite

   • Put key A = 1
   • Put key A = 2
   • Get A → 2

3. Delete

   • Put key
   • Delete key
   • Restart
   • Get key → None

4. Truncated File Recovery

   • Kill process mid-write
   • Restart
   • All previous keys intact

5. Corruption Detection

   • Modify middle of file
   • Restart → error returned

---

9️⃣ Explicit Non-Goals (Phase 1)

• Compaction
• Multiple log segments
• Concurrency
• Memory-mapped IO
• Checksums
• Compression
• Snapshots

---

🔜 Phase 2 Preview (Not Implemented)

• Structured checksums
• Multiple segments
• Background compaction
• Stronger durability guarantees (fsync modes)

---

10️⃣ Definition of “Done”

Phase 1 is complete when:

• All acceptance tests pass
• Log replay is deterministic
• Index can be deleted and rebuilt with no data loss
• You can explain every invariant without notes