The Unified Compaction Strategy in Cassandra 5

Introduction

Cassandra, a distributed database built on the Apache Foundation, relies on the LSM (Log-Structured Merge-Tree) architecture to manage data efficiently. At its core, the LSM tree structure enables fast write operations by leveraging local storage and sequential I/O, while read operations require compaction to maintain performance. Over time, the accumulation of SSTables (Sorted String Tables) necessitates a robust compaction strategy to balance read/write amplification. Traditional approaches like Size-Tiered and Leveled Compaction have trade-offs in handling varying workloads. Cassandra 5 introduces the Unified Compaction Strategy (UCS), a novel approach that merges the strengths of existing methods to optimize compaction for diverse use cases.

Technical Overview

LSM Tree and Compaction Fundamentals

Cassandra’s LSM tree organizes data into SSTables, which are immutable files stored in levels. Writes are appended to a memtable, which is periodically flushed to disk as SSTables. As data ages, compaction merges SSTables to eliminate redundancies, reduce disk space, and improve query performance. However, compaction introduces read/write amplification: reads may scan multiple SSTables, and writes may involve rewriting data across layers.

Existing Compaction Strategies

1. Size-Tiered Compaction (STC)

   • Mechanism: SSTables are grouped by size, with each tier containing up to fun factor files.
   • Strengths: Efficient for key-value workloads and leverages Bloom Filters for quick lookups.
   • Limitations: Can generate large SSTables, leading to inefficiencies during repair or node restarts. Not ideal for high-read or partition-heavy scenarios.

2. Leveled Compaction (LC)

   • Mechanism: SSTables are partitioned by token ranges, with each level containing a single SSTable.
   • Strengths: Minimizes read amplification, suitable for high-write workloads.
   • Limitations: High write amplification and throughput bottlenecks, particularly during Level 0 to Level 1 transitions.

Unified Compaction Strategy (UCS) Design

UCS integrates the advantages of STC and LC by introducing a dynamic, workload-aware framework. Its core objectives include:

• Balanced Amplification: Adjusts compaction based on workload characteristics.
• SSTable Size Control: Uses density and overlap metrics to prevent oversized SSTables.
• Configurable Flexibility: A single parameter (fun factor) allows fine-tuning of compaction behavior.

Key Technical Components

1. Hierarchical Layering

   • SSTables are organized into layers based on size, with each layer containing up to fun factor files. Token coverage per layer is determined by the fun factor.

2. Density Metric

   • Density is calculated as SSTable size divided by token coverage. This metric guides compaction decisions to maintain optimal data density.

3. Overlap Management

   • Only overlapping SSTables are merged, reducing unnecessary read amplification. Non-overlapping SSTables are left untouched to preserve query performance.

4. Dynamic Sharding

   • Compaction splits SSTables into shards based on their size relative to a target. For example, a 400MB SSTable with a target of 100MB is divided into 4 shards, ensuring balanced distribution.

Parameter Tuning

• Fun Factor Adjustment: A single parameter controls compaction behavior. Negative values prioritize read efficiency, while positive values optimize write performance.
• Layer-Specific Configuration: Different layers can use distinct fun factor values. For instance, lower layers might use T4 for write optimization, while upper layers use T3 for read efficiency.

Compaction Workflow Example

1. Initial State: Level 0 contains 4 SSTables (400MB) covering the full token space. With fun factor=4, compaction splits them into 4 shards (100MB each).
2. New Data Ingestion: 4 new 60MB SSTables (240MB total) are added. With fun factor=4, they are split into 2 shards (120MB each), covering half the token space.
3. Higher-Level Compaction: Level 1 has 4 SSTables (430MB) covering half the token space. With fun factor=3, overlapping SSTables (CDF, G) are merged into 8 shards, resulting in 4 final SSTables.

Key Optimizations

• Avoiding Oversized SSTables: Density and overlap metrics ensure SSTables remain within manageable sizes.
• Reducing Redundant Compaction: Fixed shard boundaries prevent unnecessary recompression due to data movement.
• Workload Adaptability: The fun factor allows real-time adjustments to balance read/write amplification.

Future Extensions

UCS is designed for scalability, with planned enhancements such as:

• Whole Table Exploration: Supports time-series workloads by enabling full-table compaction.
• Hierarchical Prioritization: Ensures compaction layers remain aligned with workload demands.
• Time-Based Layers: Future iterations may introduce time-based partitioning (e.g., 4-week intervals) and Tombstone cleanup mechanisms.
• Automated Tuning: Development is underway for self-adjusting compaction strategies based on runtime metrics.

Conclusion

Cassandra 5’s Unified Compaction Strategy represents a significant advancement in managing LSM tree efficiency. By dynamically balancing read/write amplification, UCS addresses the limitations of traditional compaction methods while offering flexibility for diverse workloads. Its integration of density, overlap, and sharding metrics ensures optimal performance in distributed environments. For developers, tuning the fun factor and leveraging layer-specific configurations can unlock substantial improvements in throughput and latency. As distributed databases continue to evolve, UCS sets a new benchmark for compaction in the Apache ecosystem.