MVCC Garbage Collection Validation Architecture
MVCC Garbage Collection Validation Architecture
Version: 1.0 Created: November 28, 2025 Component: Storage Foundation Status: Production Validation (Weeks 3-5)
System Architecture Overview
┌─────────────────────────────────────────────────────────────────┐│ MVCC GC Validation Layer ││ ││ ┌──────────────────┐ ┌──────────────────┐ ┌──────────────┐ ││ │ GC Correctness │ │ Version Chain │ │ Performance │ ││ │ Validator │ │ Integrity │ │ Profiler │ ││ │ │ │ Validator │ │ │ ││ │ - Tombstone GC │ │ - Ordering │ │ - Latency │ ││ │ - Live versions │ │ - Duplicates │ │ - Memory │ ││ │ - Snapshots │ │ - Tombstones │ │ - Throughput│ ││ └────────┬─────────┘ └────────┬─────────┘ └──────┬───────┘ ││ │ │ │ │└───────────┼─────────────────────┼────────────────────┼─────────┘ │ │ │ ▼ ▼ ▼┌─────────────────────────────────────────────────────────────────┐│ Existing MVCC GC Implementation ││ (75% Complete) ││ ││ ┌──────────────┐ ┌──────────────┐ ┌────────────────────┐ ││ │ Tombstone │ │ Version │ │ Automatic │ ││ │ GC │ │ Chain │ │ Compaction │ ││ │ │ │ Trimming │ │ │ ││ │ compaction.rs│ │ mvcc.rs │ │ compaction.rs │ ││ │ │ │ │ │ │ ││ │ - Grace │ │ - Max │ │ - STCS/LCS │ ││ │ period │ │ versions │ │ - Background │ ││ │ - Age check │ │ - FIFO evict │ │ scheduler │ ││ └──────┬───────┘ └──────┬───────┘ └─────────┬──────────┘ ││ │ │ │ │└─────────┼─────────────────┼────────────────────┼──────────────┘ │ │ │ ▼ ▼ ▼┌─────────────────────────────────────────────────────────────────┐│ Storage Engine (LSM) ││ ││ ┌──────────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐ ││ │ MemTable │→ │ L0 SSTs │→ │ L1 SSTs │→ │ L2+ SSTs │ ││ │ (Write) │ │ (Flush) │ │(Compact) │ │ (Merge) │ ││ └──────────┘ └──────────┘ └──────────┘ └──────────┘ ││ ││ Version chains stored in SSTables with timestamps ││ Tombstones marked with is_tombstone flag ││ GC runs during compaction (merge_sstables_with_stats) │└─────────────────────────────────────────────────────────────────┘Component Interactions
1. GC Correctness Validator ↔ Storage Engine
Validator Storage Engine │ │ │ write(key, value) │ ├───────────────────────────>│ │ │ Create version │ │ Timestamp: T1 │ │ TxnID: 1 │ │ │ delete(key) │ ├───────────────────────────>│ │ │ Create tombstone │ │ Timestamp: T2 │ │ is_tombstone: true │ │ │ trigger_compaction() │ ├───────────────────────────>│ │ │ Check age: │ │ if (now - T2) > gc_grace: │ │ Remove tombstone │ │ │ tombstone_exists(key) │ ├───────────────────────────>│ │ │ Return: false │<────────────────────────────┤ │ │ │ Verify: PASS │ │ │2. Version Chain Integrity Validator ↔ MVCC Store
Validator MVCC Store │ │ │ Add 150 versions │ ├───────────────────────────>│ │ │ VersionChain: │ │ max_versions: 100 │ │ versions: [v150, v149, ..., v51] │ │ trimmed: [v50, v49, ..., v1] │ │ │ validate_chain(key) │ ├───────────────────────────>│ │ │ Check ordering: │ │ v150.ts > v149.ts > ... │ │ Check duplicates: │ │ No duplicates │ │ Check max_versions: │ │ 100 <= 100 │ │ │<────────────────────────────┤ │ ValidationReport: │ │ is_valid: true │ │ issues: [] │ │ │3. GC Performance Profiler ↔ GC Tuning Manager
Profiler GC Tuning Manager │ │ │ Start workload │ │ │ │ Write 10K keys │ ├───────────────────────────>│ │ │ Monitor heap usage │ │ Trigger threshold: 75% │ │ │ Compaction triggered │ │<────────────────────────────┤ │ │ start_gc_pause() │ │ Timestamp: T_start │ Measure latency │ │ │ │ │ GC execution... │ │ │ │ end_gc_pause() │ Latency recorded: 8ms │ Timestamp: T_end │<────────────────────────────┤ Pause: 8ms │ │ │ p99 latency: 8ms < 10ms │ │ │Data Flow: GC Execution
Phase 1: Tombstone Detection
SSTable Merge │ ├─> Read entry: {key: "user_1", is_tombstone: true, ts: 1000} │ ├─> Calculate age: now (10000) - ts (1000) = 9000 seconds │ ├─> Check grace period: 9000 > gc_grace_seconds (864000)? NO │ ├─> Decision: KEEP tombstone (within grace period) │ └─> Include in merged SSTablePhase 2: Age-Based Deletion
SSTable Merge (10 days later) │ ├─> Read entry: {key: "user_1", is_tombstone: true, ts: 1000} │ ├─> Calculate age: now (875000) - ts (1000) = 874000 seconds │ ├─> Check grace period: 874000 > gc_grace_seconds (864000)? YES │ ├─> Decision: DELETE tombstone (exceeded grace period) │ └─> Exclude from merged SSTablePhase 3: Version Chain Trimming
Version Chain: max_versions = 100 │ ├─> Current: [v150, v149, ..., v51] (100 versions) │ ├─> New write: v151 │ ├─> Insert: [v151, v150, ..., v51] (101 versions) │ ├─> Trim check: 101 > 100? YES │ ├─> Evict oldest: pop_back() → removes v51 │ └─> Final: [v151, v150, ..., v52] (100 versions)Validation Test Flow
Correctness Validation (Week 3)
┌─────────────────────────────────────────────────┐│ Day 1-2: GC Correctness Tests │├─────────────────────────────────────────────────┤│ 1. test_tombstone_gc_after_grace_period() ││ ├─> Write + Delete → Tombstone created ││ ├─> Wait 11 seconds ││ ├─> Trigger compaction ││ └─> Verify tombstone removed ││ ││ 2. test_tombstone_retention_within_grace() ││ ├─> Write + Delete → Tombstone created ││ ├─> Wait 5 seconds (< grace period) ││ ├─> Trigger compaction ││ └─> Verify tombstone retained ││ ││ 3. test_version_chain_trimming_correctness() ││ ├─> Write same key 150 times ││ ├─> Verify only 100 versions retained ││ └─> Verify latest version accessible │└─────────────────────────────────────────────────┘ │ ▼┌─────────────────────────────────────────────────┐│ Day 3: Version Chain Integrity Tests │├─────────────────────────────────────────────────┤│ 1. test_version_ordering_after_concurrent() ││ ├─> 10 threads × 100 versions ││ ├─> Validate ordering (newest first) ││ └─> Verify timestamp monotonicity ││ ││ 2. test_no_duplicate_versions() ││ ├─> Write 1000 versions ││ ├─> Validate no duplicate timestamps ││ └─> Each version unique │└─────────────────────────────────────────────────┘ │ ▼┌─────────────────────────────────────────────────┐│ Day 4-5: GC Stress Tests │├─────────────────────────────────────────────────┤│ 1. test_gc_at_100k_keys() ││ ├─> 100K keys × 5 versions = 500K writes ││ ├─> GC every 10K keys ││ ├─> Verify no data loss ││ └─> Measure throughput: 10K+ writes/sec ││ ││ 2. test_concurrent_gc_and_active_transactions() ││ ├─> Background GC loop ││ ├─> 10 threads × 1000 writes concurrently ││ ├─> Verify version chain integrity ││ └─> Zero memory corruption │└─────────────────────────────────────────────────┘Performance Validation (Week 4)
┌─────────────────────────────────────────────────┐│ Day 1-2: Performance Profiling │├─────────────────────────────────────────────────┤│ 1. benchmark_gc_latency_under_load() ││ ├─> 10K keys × 20 versions ││ ├─> Measure GC latency every 100 keys ││ ├─> Calculate p50, p99, max ││ └─> Verify p99 < 10ms ││ ││ 2. benchmark_memory_overhead() ││ ├─> Write 50K keys × 512 bytes ││ ├─> Measure actual vs expected memory ││ ├─> Calculate overhead ratio ││ └─> Verify overhead < 15% │└─────────────────────────────────────────────────┘ │ ▼┌─────────────────────────────────────────────────┐│ Day 3-4: Run All Tests & Collect Data │├─────────────────────────────────────────────────┤│ - Run all correctness tests (sequential) ││ - Run all stress tests (manual, #[ignore]) ││ - Collect performance metrics ││ - Generate validation reports │└─────────────────────────────────────────────────┘ │ ▼┌─────────────────────────────────────────────────┐│ Day 5: Performance Baseline Establishment │├─────────────────────────────────────────────────┤│ Baseline Metrics: ││ - GC latency p99: 8ms (target <10ms) ││ - Memory overhead: 12% (target <15%) ││ - Space reclamation: 75% (target >60%) ││ - Throughput impact: 3% (target <5%) │└─────────────────────────────────────────────────┘Integration Validation (Week 5)
┌─────────────────────────────────────────────────┐│ Day 1-2: SSI Integration Tests │├─────────────────────────────────────────────────┤│ 1. test_gc_with_serializable_snapshot_iso() ││ ├─> T1 reads key_a ││ ├─> T2 writes key_a, commits ││ ├─> Trigger GC ││ ├─> T1 detects conflict on commit ││ └─> Serialization conflict detected │└─────────────────────────────────────────────────┘ │ ▼┌─────────────────────────────────────────────────┐│ Day 3: Index MVCC Integration Tests │├─────────────────────────────────────────────────┤│ 1. test_gc_with_index_mvcc_version_tracking() ││ ├─> Create index on name field ││ ├─> Write 50 versions of same document ││ ├─> Trigger GC (trim to max_versions) ││ ├─> Verify index still works ││ └─> Verify index version consistency │└─────────────────────────────────────────────────┘ │ ▼┌─────────────────────────────────────────────────┐│ Day 4: Fix Issues (if any) │├─────────────────────────────────────────────────┤│ - Address any discovered bugs ││ - Re-run failed tests ││ - Tune GC configuration if needed │└─────────────────────────────────────────────────┘ │ ▼┌─────────────────────────────────────────────────┐│ Day 5: Final Validation & Documentation │├─────────────────────────────────────────────────┤│ Deliverables: ││ 1. Validation Report (all test results) ││ 2. GC Tuning Guide (configuration) ││ 3. Performance Baseline Report ││ 4. Troubleshooting Guide ││ ││ Sign-off: Production-validated GC subsystem │└─────────────────────────────────────────────────┘Configuration Matrix
Test Configurations
| Configuration | gc_grace_seconds | max_versions | Use Case |
|---|---|---|---|
| Default | 864000 (10 days) | 100 | Production |
| High-Retention | 7776000 (90 days) | 500 | Time-travel queries |
| Low-Latency | 3600 (1 hour) | 50 | OLTP workloads |
| Testing | 10 (10 seconds) | 100 | Fast validation |
Performance Targets by Configuration
| Configuration | GC Latency (p99) | Memory Overhead | Space Reclaim |
|---|---|---|---|
| Default | <10ms | <15% | >60% |
| High-Retention | <20ms | <25% | >50% |
| Low-Latency | <5ms | <10% | >70% |
| Testing | <50ms | <20% | >50% |
Success Criteria Breakdown
Correctness (100% Required)
- Zero data loss across 1M+ transactions
- Version chain integrity maintained 100% of time
- Snapshot isolation guarantees preserved
- No memory corruption or panics
- Tombstones collected correctly after grace period
- Live versions never deleted prematurely
Performance (Targets)
- GC latency <10ms (p99)
- Memory overhead <15%
- Space reclamation >60%
- Throughput impact <5% during GC
- Long-running snapshots supported (6+ hours)
Integration (Critical)
- SSI compatibility verified
- Index MVCC integration validated
- Concurrent safety guaranteed
- No deadlocks or race conditions
Risk Assessment
Low Risk
- Implementation already 75% complete
- No major architectural changes required
- Small VM sufficient for validation
- Clear pass/fail criteria
Medium Risk ⚠
- Edge cases in long-running snapshots
- Concurrent GC + active transactions timing
- jemalloc tuning on different platforms
Mitigations
- Comprehensive stress testing (100K+ keys)
- Chaos testing for concurrent scenarios
- Platform-specific configuration guides
- Extensive documentation and troubleshooting
Deliverables Checklist
Week 3 Deliverables
-
gc_correctness_validator.rs(500 LOC) -
version_chain_integrity.rs(400 LOC) -
gc_stress_test.rs(300 LOC) - Correctness validation report
Week 4 Deliverables
-
gc_performance_profiler.rs(350 LOC) - Performance baseline report
- Memory overhead analysis
- Throughput impact assessment
Week 5 Deliverables
-
mvcc_gc_integration_validator.rs(400 LOC) - SSI integration report
- Index MVCC integration report
- GC tuning guide
- Troubleshooting guide
- Final validation certification
Conclusion
The MVCC GC validation architecture provides a turnkey validation suite for HeliosDB’s already-implemented garbage collection subsystem. With 5 test modules (~2,350 LOC) and 4 documentation deliverables, this 3-week effort (Weeks 3-5) validates production readiness with:
- Zero implementation risk (75% already done)
- Clear success metrics (pass/fail criteria)
- Low resource requirements (1 engineer, small VM)
- High confidence boost (early completion milestone)
This is the quickest path to validating a production-critical subsystem and building stakeholder confidence in HeliosDB’s storage foundation.
Document Status: READY FOR EXECUTION Architecture Version: 1.0 Created: November 28, 2025 Last Updated: November 28, 2025