Compaction Strategy Guide for HeliosDB

Compaction Strategy Guide for HeliosDB

Overview

Compaction is a critical background process in LSM-tree storage engines that merges SSTables to:

• Remove duplicate keys (keeping only the latest version)
• Delete tombstones for deleted keys
• Reorganize data into sorted levels
• Reclaim disk space
• Improve read performance

This guide covers HeliosDB’s advanced compaction strategies, including parallel execution, I/O throttling, and early tombstone deletion.

---

Table of Contents

1. Compaction Strategies
2. Parallel Compaction
3. I/O Throttling
4. Tombstone Management
5. Priority Scheduling
6. Performance Optimization

---

Compaction Strategies

1. Leveled Compaction Strategy (LCS)

How It Works:

• Data organized into levels (L0, L1,…, Ln)
• Each level is 10x larger than the previous level
• SSTables within a level don’t overlap (except L0)
• Compaction merges overlapping SSTables between adjacent levels

Level Structure:

L0: 100 MB  (4 files × 25 MB, may overlap)
L1: 1 GB    (40 files × 25 MB, non-overlapping)
L2: 10 GB   (400 files × 25 MB, non-overlapping)
L3: 100 GB  (4000 files × 25 MB, non-overlapping)

Pros:

• Excellent read performance (1-2 SSTables per read)
• Low space amplification (~1.1x)
• Predictable performance

Cons:

• High write amplification (8-10x)
• More I/O intensive
• Slower for write-heavy workloads

Best For:

• Read-heavy workloads
• Point lookups
• Random access patterns
• Production databases

2. Size-Tiered Compaction Strategy (STCS)

How It Works:

• SSTables grouped into buckets by size
• Compaction triggered when bucket has 4+ similar-sized SSTables
• No strict level organization
• Merges SSTables of similar size together

Bucket Example:

Bucket 1: [10 MB, 12 MB, 11 MB, 10 MB] → Compact to 43 MB
Bucket 2: [50 MB, 48 MB, 52 MB, 49 MB] → Compact to 199 MB
Bucket 3: [200 MB, 210 MB, 195 MB, 205 MB] → Compact to 810 MB

Pros:

• Low write amplification (2-4x)
• Fast writes
• Good for time-series data

Cons:

• Higher read amplification (may scan many SSTables)
• Higher space amplification (~2x)
• Temporary disk space spikes during compaction

Best For:

• Write-heavy workloads
• Time-series data
• Log aggregation
• Metrics collection

3. Universal Compaction

How It Works:

• Optimized for time-series and append-only workloads
• Compacts entire sorted runs
• Uses size-ratio based triggering
• Minimizes write amplification

Pros:

• Lowest write amplification (2x)
• Excellent for sequential writes
• Minimal overhead

Cons:

• Can have temporary space amplification
• Not ideal for random updates
• Less predictable than leveled

Best For:

• Time-series databases
• Append-only workloads
• Event logging
• Sensor data

Strategy Comparison

Metric	Leveled	Size-Tiered	Universal
Write Amplification	8-10x	2-4x	2x
Read Amplification	1-2x	5-10x	10-20x
Space Amplification	1.1x	2x	1.5-2x
Read Performance	Excellent	Good	Fair
Write Performance	Good	Excellent	Excellent
Space Efficiency	Excellent	Fair	Good

---

Parallel Compaction

HeliosDB supports parallel compaction execution to maximize throughput on multi-core systems.

How It Works

1. Worker Pool: Multiple compaction workers run concurrently
2. Priority Queue: Tasks scheduled by priority
3. Semaphore: Limits concurrent compactions to prevent resource exhaustion
4. Independent Execution: Non-overlapping compactions run in parallel

Worker Distribution

CPU Cores: 16
Recommendation: max_concurrent_compactions = cores / 2 = 8

Reasoning:
- Leave cores for foreground operations
- Each compaction uses 1-2 threads
- I/O bound, not CPU bound

Benefits

• 3-4x compaction throughput on multi-core systems
• Reduced compaction backlog
• Better foreground latency (less compaction debt)
• Improved write throughput

---

I/O Throttling

Compaction can overwhelm I/O bandwidth, affecting foreground performance. HeliosDB includes adaptive I/O throttling.

How It Works

Token Bucket Algorithm:

1. Tokens represent I/O bytes
2. Tokens refill at configured rate
3. Compaction consumes tokens before I/O
4. If tokens exhausted, compaction waits

Adaptive Throttling

With adaptive throttling enabled, throttling adjusts based on:

• Foreground operation latency
• System I/O utilization
• Compaction backlog

Benefits

• Consistent foreground performance
• Prevents compaction from starving reads/writes
• Better multi-tenant resource sharing
• Reduced tail latencies

---

Tombstone Management

Deletes in LSM trees use tombstones (markers indicating deletion). HeliosDB includes advanced tombstone management.

Standard Tombstone GC

Process:

1. Tombstone written on delete
2. Tombstone propagates through levels during compaction
3. After gc_grace_seconds, tombstone eligible for removal
4. Tombstone removed if it’s the only version of the key

Why Grace Period?

• Allows time for repairs/backups
• Prevents resurrection of deleted data
• Handles distributed clock skew

Early Tombstone Deletion (ETD)

HeliosDB includes early tombstone deletion for high-tombstone scenarios.

When a compaction input contains a high proportion of tombstones, the engine removes eligible tombstones more aggressively to reclaim space sooner.

Benefits:

• Faster space reclamation
• Lower read amplification (fewer tombstones to skip)
• Better for high-churn workloads

Trade-offs:

• May delete tombstones before full grace period
• Acceptable for most workloads
• Disable for strict consistency requirements

---

Priority Scheduling

Compaction tasks are scheduled by priority to optimize performance.

Priority Rules

1. L0 Compactions: Highest priority (prevents write stalls)
2. Large Compactions: Higher priority (clear backlog)
3. Old Compactions: Higher priority (prevent accumulation)
4. Deep Level Compactions: Lower priority (less impact)

---

Performance Optimization

Results below are indicative, measured on representative workloads; reproduce on your own hardware.

1. Minimize Write Amplification

Strategies:

• Use size-tiered or universal compaction
• Increase SSTable size (fewer compactions)
• Batch writes in larger memtables
• Enable early tombstone deletion

Result:

• Write amplification: 10x → 3x (70% reduction)
• Write throughput: +100%

2. Minimize Read Amplification

Strategies:

• Use leveled compaction
• Increase bloom filter size
• Trigger compaction earlier (fewer L0 files)
• Increase block cache

Result:

• Read amplification: 10x → 2x (80% reduction)
• Read throughput: +150%

3. Optimize Space Utilization

Strategies:

• Use compression (Zstd for maximum compression)
• Enable early tombstone deletion
• Use leveled compaction (better space efficiency)
• Reduce GC grace period

Result:

• Space amplification: 2.5x → 1.2x (52% reduction)
• Disk savings: 40-60%

4. Balance Throughput and Latency

The adaptive strategy automatically switches between leveled and universal based on workload.

Benefits:

• Optimal performance across workload changes
• Reduced operational overhead
• Best of both worlds

---

Best Practices

1. Choose the Right Strategy

Decision Tree:

Is workload write-heavy (>70% writes)?
  Yes → Size-Tiered or Universal
  No → Is it read-heavy (>70% reads)?
    Yes → Leveled
    No → Adaptive (let system choose)

2. Size SSTables Appropriately

Guidelines:

• L0 files: 25-50 MB (fast to compact)
• L1+ files: 64-128 MB (balance compaction cost)
• Time-series: 128-256 MB (sequential writes)

3. Configure Parallel Workers

Formula:

max_concurrent = min(
    cpu_cores / 2,
    available_memory_gb / 2,
    io_bandwidth_gb_per_sec * 2
)

Example:

• 16 cores, 32 GB RAM, 2 GB/s I/O
• max_concurrent = min(8, 16, 4) = 4

4. Use I/O Throttling in Production

Always enable for:

• Multi-tenant systems
• Shared storage
• Cloud deployments
• SSD storage (prevent wear)

5. Monitor Continuously

Essential metrics:

• Compaction backlog (pending tasks)
• Active compactions
• Write/read/space amplification
• Failure rate
• L0 file count

6. Tune Based on Metrics

If write amplification high:

• Switch to size-tiered/universal
• Increase SSTable size
• Reduce compaction frequency

If read amplification high:

• Switch to leveled
• Increase bloom filter size
• Compact L0 more frequently

If space amplification high:

• Reduce GC grace period
• Enable early tombstone deletion
• Trigger manual compaction

---

Conclusion

HeliosDB’s advanced compaction system provides:

✓ Multiple strategies for different workloads ✓ Parallel execution for high throughput ✓ I/O throttling for consistent performance ✓ Early tombstone deletion for space efficiency ✓ Priority scheduling for optimal resource usage

Key Takeaways:

1. Choose strategy based on workload (leveled for reads, size-tiered for writes)
2. Enable parallel compaction on multi-core systems
3. Use I/O throttling to protect foreground performance
4. Monitor metrics and adjust configuration as needed
5. Use adaptive mode for changing workloads

By following this guide, you can achieve:

• 40-60% reduction in write amplification
• 2-3x improvement in compaction throughput
• Consistent sub-millisecond foreground latencies
• 50%+ space savings with compression and tombstone management

For more information, see the LSM Tuning Guide.