TinyStoreDB: Asynchronous Compaction Strategy (Custom Design)

Overview

This document outlines a custom asynchronous compaction strategy designed to avoid blocking read/write operations during compaction. The approach ensures consistency, atomicity, and isolation without stopping traffic or impacting user experience.

Motivation

Traditional compaction strategies pause write/read traffic to rewrite the store, which causes latency spikes or potential downtime. This custom design introduces a non-blocking compaction mechanism with versioned stores and a temporary tracking map to maintain correctness.

---

Key Concepts

• V1: Current live store (map, val.bin, vallog.bin)
• V2: New store created during compaction
• InProgressDeleteV1Map: Temporary in-memory map storing keys deleted from V1 after compaction started
• Timestamp-based Resolution: Set operations use timestamps to determine the latest version

---

Core Flow

Trigger

• Compaction starts via a sync trigger (manual or scheduled).
• A new store version (V2) is created:
  • map
  • val.bin
  • vallog.bin

Step 1: Prepare for Write Switch

• Before switching writes to V2, create:
  • A InProgressDeleteV1Map
  • This map stores all keys deleted from V1 during the compaction process.

Step 2: Switch Live Writes

• All write (Set) operations are redirected to V2.
• All delete operations update both V2 (by marking delete) and InProgressDeleteV1Map.

---

Read Path (Get)

The Get operation resolves using the following order:

1. Check key in V2.
2. If found in V2:
   • Return it (skip V1).
3. If not found in V2:
   • Check InProgressDeleteV1Map.
     • If key exists → return "not found"
     • If not → lookup in V1
       • If found → return value
       • Else → return "not found"

This ensures reads never return deleted keys during compaction.

---

Write Path (Set)

• All new writes go to V2.
• If a Set targets a key already present:
  • Timestamps are compared
  • Only newer values override existing ones
  • Ensures atomicity and avoids stale writes

---

Delete Path

• All deletes after compaction starts:
  • Add the key to InProgressDeleteV1Map
  • Delete from V2 if present

This ensures:

• Keys deleted during compaction don’t get restored from V1.
• Data correctness and delete visibility is preserved.

---

Final Phase: Compaction Completion

Once all keys from V1 are processed and written to V2:

1. Validate compaction is complete
2. Delete all V1 disk files:
   • val.bin, vallog.bin, map
3. Free memory by deleting:
   • V1 in-memory map
   • InProgressDeleteV1Map
4. Reads no longer check V1 or the delete map

---

Benefits

Property	Maintained?	Notes
Atomicity	✅ Yes	Timestamp-based resolution ensures no stale writes are applied
Consistency	✅ Yes	Deleted keys aren't returned; correct values are served
Isolation	✅ Yes	V1 and V2 operate independently during compaction
Availability	✅ Yes	No read/write traffic is blocked

---

Summary

This custom compaction algorithm:

• Uses versioned storage (V1 → V2)
• Maintains a temporary delete index to handle in-flight deletes
• Preserves all guarantees (ACID-like)
• Supports seamless asynchronous compaction with no downtime

---

Status

✅ Tested and validated in theory
🛠️ Production integration or fuzz testing recommended