Extend a Key-Value Store with Commits and Explicit Rollover Semantics

Scenario

Collaborative editing and transcription platforms often require client-facing storage where users can stage edits, create point-in-time checkpoints ("commits"), inspect previous revisions, and roll back if necessary. You are tasked with designing an in-memory, versioned key-value store service with explicit commit milestones and a defined rollover policy to prevent unbounded memory growth.

Requirements

Functional Requirements

• Staging Operations: Support put(key, value) and delete(key) within an active, uncommitted working buffer.
• Commit: Support commit() -> commit_id to atomically persist staged changes as an immutable snapshot with a monotonically increasing integer identifier. Discard the active staging buffer upon commit.
• Snapshot Read: Support get(key, commit_id=None) to read the value of a key at a specific commit_id (defaulting to the latest committed version). If the key was deleted or never existed at that commit, return null/not found.
• Rollover / Compaction: Maintain at most K historical commits (e.g., K = 50). When commit N causes the history to exceed K, the oldest commits must roll over: collapse them into a base snapshot, freeing obsolete intermediate versions and tombstones.

Non-Functional Requirements

• Snapshot Isolation: Readers querying a specific commit_id must see a consistent snapshot unaffected by concurrent staging or new commits.
• Memory Efficiency: Avoid duplicating entire datasets across commits; use structural sharing or delta-based versioning.
• Low Latency: Staging operations and reads should complete in O(1) or O(log N) time.

Scale Assumptions

• Average workspace: 50,000 active keys with value sizes around 1 KB.
• Retention limit: K = 50 historical commits per workspace.
• Throughput: Up to 5,000 operations/sec per instance.

What Your Answer Should Cover

1. Data Model & In-Memory Structures: How keys, values, versions, and tombstones are stored to facilitate fast reads and structural sharing.
2. Read & Write Lifecycle: Step-by-step mechanics for staging, committing, and point-in-time querying.
3. Rollover & Garbage Collection: Detailed strategy for compacting commits beyond the K limit without blocking active readers.
4. Edge Cases & Trade-offs: Trade-offs between persistent tree structures (e.g., Path Copying / Copy-on-Write HAMT) versus per-key version lists (MVCC).