Compaction¶

How Scylla Writes Data¶

Scylla’s write path follows the well-known Log Structured Merge (LSM) design for efficient writes that are immediately available for reads. Scylla is not the first project to use this method. Popular projects to use this method include Lucene Search Engine, Google BigTable, and Apache Cassandra.

Scylla writes its updates to a memory table (MemTable), and when that becomes too big, it is flushed to a new file. This file is sorted to make it easy to search and later merge. This is why the tables are known as Sorted String Tables or SSTables.

In time, two major problems start to appear. First, data in one SSTable which is later modified or deleted in another SSTable wastes space as both tables are present in the system. Second, when data is split across many SSTables, read requests are processed slower as many SSTables need to be read. Scylla mitigates the second problem by using a bloom filter and other techniques to avoid reading from SSTables that do not include the desired partition. However, as the number of SSTables grows, inevitably so do the number of disk blocks from which we need to read on every read query. For these reasons, as soon as enough SSTables have accumulated, Scylla performs a compaction.

Compaction Overview¶

Compaction merges several SSTables into new SSTable(s) which contain(s) only the live data from the input SSTables. Merging several sorted files to get a sorted result is an efficient process, and this is the main reason why SSTables are kept sorted.

There are two types of compactions:

• Minor Compaction

  Scylla automatically triggers a compaction of some SSTables, according to a compaction strategy (as described below). This is the recommended method.

• Major Compaction

  A user triggers (using nodetool) a compaction over all SSTables, merging the individual tables according to the selected compaction strategy.

View Compaction Statistics¶

Scylla has tools you can use to see the status of your compactions. These include nodetool (compactionhistory and compactionstats) and the Grafana dashboards which are part of the Scylla Monitoring Stack which display the compaction statistics on a per cluster and per node basis. Compaction errors can be seen in the logs.

Compaction strategy¶

A compaction strategy is what determines which of the SSTables will be compacted, and when. The following compaction strategies are available and are described in greater detail below. For a matrix which compares each strategy to its workload, refer to Compaction Strategy Matrix

• Size-tiered compaction strategy (STCS) - (default setting) triggered when the system has enough similarly sized SSTables.

• Leveled compaction strategy (LCS) - the system uses small, fixed-size (by default 160 MB) SSTables divided into different levels and lowers both Read and Space Amplification.

• Incremental compaction strategy (ICS) - Available for Enterprise customers, uses runs of sorted, fixed size (by default 1 GB) SSTables in a similar way that LCS does, organized into size-tiers, similar to STCS size-tiers. If you are an Enterprise customer ICS is an updated strategy meant to replace STCS. It has the same read and write amplification, but has lower space amplification due to the reduction of temporary space overhead is reduced to a constant manageable level.

• Time-window compaction strategy (TWCS) - designed for time series data and puts data in time order. This strategy replaced Date-tiered compaction. TWCS uses STCS to prevent accumulating SSTables in a window not yet closed. When the window closes, TWCS works towards reducing the SSTables in a time window to one.

• Date-tiered compaction strategy (DTCS) - designed for time series data, but TWCS should be used instead.

Size-tiered Compaction Strategy (STCS)¶

The premise of SizeTieredCompactionStrategy (STCS) is to merge SSTables of approximately the same size. All SSTables are put into different buckets depending on their size. An SSTable is added to an existing bucket if size of the SSTable is within the parameters: bucket_low and bucket_high, which is based on calculating the current average size of the SSTables already in the bucket.

This will create several buckets and when the threshold number of tables(min_threshold) within a bucket is reached, the tables in that bucket are compacted. Following the compaction, the tables are merged, resulting in one larger SSTable. As time progresses and several large SSTables have accumulated, they will be merged to form one even-larger SSTable and so on.

This means that the system has several size tiers/buckets (small SSTables, large SSTables, even-larger SSTables) and in each tier, there is roughly the same number of SSTables. When one tier is full (the threshold has been reached), the system merges all its tables to create one SSTable which falls roughly into the next size tier.

Leveled Compaction Strategy (LCS)¶

Leveled Compaction uses small, fixed-size (by default 160 MB) SSTables divided into different levels. Each level represents a run of a number of SSTables.

A run of SSTables¶

A run is a log-structured-merge (LSM) term for a large SSTable split into several smaller SSTables. In other words, a run is a collection of SSTables with non-overlapping key ranges. The benefit of a run is that when a compaction is done, only parts of it (small individual SSTables) are compacted and deleted. Following a compaction, SSTables are smaller and there is no need to compact a huge SSTable all at once.

The compaction method works as follows:

1. New SSTables (created from MemTables) are created in Level 0. All other levels are each a run of SSTables, of exponentially increasing size as follows:

   • Level 1 is a run of 10 SSTables (160 MB each table * 10)

   • Level 2 is a run of 100 SSTables (160 MB each table * 100), etc.

2. When there are 4 SSTables in Level 0, they are compacted with the 10 SSTables in Level 1. This compaction works as follows:

   • Read in parallel 4 SSTables in level 0 and 10 in Level 1.

   • Write new SSTables for Level 1 (replacing the 10 old tables which were compacted).

   • Instead of creating one large SSTable, several SSTables are written as follows: One SSTable is created. When it reaches the size limit (160 MB), a new table starts. As the data is merged on the sorted keys, this generates a run (see A run of SSTables), with non-overlapping key ranges.

3. If after the compaction from Level 0 into Level 1, if there are at least 10 SSTables in Level 1, the excess SSTables from Level 1 are compacted and put into Level 2 as follows:

   • Take one SSTable from Level 1 (this SSTable will be deleted after the compaction)

   • Look at this SSTable’s key range, and find all SSTables in Level 2 which overlap with it. Typically, there are about 12 of these (the Level 1 SSTable spans roughly 1/10th of the keys, while each Level 2 SSTable spans roughly 1/100th of the keys, so 10 Level 2 SSTables will overlap the Level 1 SSTable’s range, plus two more on the edges).

   • As before, compact the 1 SSTable from Level 1 and the 12 SSTables from Level 2 and create new SSTables in Level 2 (and delete the 1+12 original SSTables).

   • If after this compaction of Level 1 into Level 2, there are excess SSTables in Level 2 (as Level 2 can only take 100 tables), merge them into Level 3.

Incremental Compaction Strategy (ICS)¶

One of the issues with Size-tiered compaction is that it needs temporary space because SSTables are not removed until they are fully compacted. ICS takes a different approach and splits each large SSTable into a run of sorted, fixed-size (by default 1 GB) SSTables (a.k.a. fragments) in the same way that LCS does, except it treats the entire run and not the individual SSTables as the sizing file for STCS. As the run-fragments are small, the SSTables compact quickly, allowing individual SSTables to be removed as soon as they are compacted. This approach uses low amounts of memory and temporary disk space.

ICS uses the same philosophy as STCS, where the SSTables are sorted in buckets according to their size. However, unlike STCS, ICS compaction uses SSTable runs as input, and produces a new run as output. It doesn’t matter if a run is composed of only one fragment that could have come from STCS migration. From an incremental compaction perspective, everything is a run.

The strategy works as follows:

1. ICS looks for candidates for compaction that are similar in size. These candidates are called Input Runs.

   • The input runs may contain one or more SSTables each.

2. ICS compacts two or more similar-sized input runs into a single Output run (* See note ).

3. Incremental Compaction progressively works on two or more fragments at a time, one from each input run.

   • It reads mutations from all input fragments and merges them together into a single output fragment.

   • As long as the resulting fragment is smaller than the sstable_size_in_mb, no further action is needed.

   • If the fragment is larger than the sstable_size_in_mb:

     1. Stop when the size threshold is reached, and seal the output fragment.

     2. Create a new run fragment and continue compacting the remaining input fragments, until the size threshold is reached.

     3. When an input fragment is exhausted, take it out of the list of SSTables to compact, and delete it from disk.

     4. Repeat until there are no input fragments left.

4. Take all of the output fragments and feed them back into compaction as an SSTable run.

5. Stop when all fragments from input runs were exhausted and released.

Incremental compaction as a solution for temporary space overhead in STCS¶

We fixed the temporary space overhead on STCS by applying the incremental compaction approach to it, which resulted in the creation of Incremental Compaction Strategy (ICS). The compacted SSTables, that become increasingly larger over time with STCS, are replaced with sorted runs of SSTable fragments, together called “SSTable runs” – which is a concept borrowed from Leveled Compaction Strategy (LCS).

Each fragment is a roughly fixed size (aligned to partition boundaries) SSTable and it holds a unique range of keys, a portion of the whole SSTable run. Note that as the SSTable-runs in ICS hold exactly the same data as the corresponding SSTables created by STCS, they become increasingly longer over time (holding more fragments), in the same way that SSTables grow in size with STCS, yet the ICS SSTable fragments’ size remains the same.

For example, when compacting two SSTables (or SSTable runs) holding 7GB each: instead of writing up to 14GB into a single SSTable file, we’ll break the output SSTable into a run of 14 x 1GB fragments (fragment size is 1GB by default).

Time-window Compaction Strategy (TWCS)¶

Time-window compaction strategy was introduced as a replacement for Date-tiered Compaction Strategy (DTCS) for handling time series workloads. Time-Window Compaction Strategy compacts SSTables within each time window using Size-tiered Compaction Strategy (STCS). SSTables from different time windows are never compacted together.

The strategy works as follows:

1. A time window is configured. The window is determined by the compaction window size compaction_window_size and the time unit (compaction_window_unit).

2. SSTables created within the time window are compacted using Size-tiered Compaction Strategy (STCS).

3. Once a time window ends, take all SSTables which were created during the time window and compact the data into one SSTable.

4. The final resulting SSTable is never compacted with other time-windows’ SSTables.

With this explanation, if the time window was for one day, at the end of the day, the SSTables accumulated for that day only would be compacted into one SSTable.

Date-tiered compaction strategy (DTCS)¶

Date-Tiered Compaction is designed for time series data. It is only suitable for time-series data. This strategy has been replaced by Time-window compaction strategy (TWCS).

Date-tiered compaction strategy works as follows:

• First it sorts the SSTables by time and then compacts adjacent (time-wise) SSTables.

• This results in SSTables whose sizes increase exponentially as they grow older.

For example, at some point we can have the last minute of data in one SSTable (by default, base_time_seconds = 60), another minute before that in another SSTable, then the 4 minutes before that in one SSTable, then the 4 minutes before that, then an SSTable of the 16 minutes before that, and so on. This structure can easily be maintained by compaction, very similar to size-tiered compaction. When there are 4 (the default value for min_threshold) small (one-minute) consecutive SSTables, they are compacted into one 4-minute SSTable. When there are 4 of the bigger SSTables one after another (time-wise), they are merged into a 16-minute SSTable, and so on.

Antique SSTables older than max_SSTable_age_days (by default 365 days) are not compacted as doing these compactions would not be useful for most queries, the process would be very slow, and the compaction would require huge amounts of temporary disk space.

Changing Compaction Strategies or Properties¶

Which Strategy is best to use¶

Use the table in Which strategy is best to determine the right strategy for your needs.

References¶

• CQL Reference for Compaction

• How to Choose a Compaction Strategy.

• Blog: Scylla’s Compaction Strategies Series: Write Amplification in Leveled Compaction

• Blog: Scylla’s Compaction Strategies Series: Space Amplification in Size-Tiered Compaction

• Size Tiered: Shrikant Bang’s Notes