See all blog posts

Incremental Compaction 2.0: A Revolutionary Space and Write Optimized Compaction Strategy

Introduction

Let’s go through a brief history of compaction strategies. It all started with Size Tiered strategy (STCS), which is optimized for writes. Later, it was realized that STCS has bad space and read amplification with overwrite-intensive workloads. Then, Leveled strategy (LCS) was introduced to solve that problem, but it introduced another problem which is its write amplification.

So what do I do if I care about space but cannot afford the write amplification of LCS?

Early in 2020, Incremental Compaction Strategy (ICS) came to the rescue. ICS solved the temporary space requirement issue in STCS, however, it didn’t solve the space amplification issue with overwrite workloads, which was unfortunately inherited from STCS. For example, when STCS and ICS are facing an overwrite workload, a given partition may be redundantly found in all sstables, leading to the space and read amplification issues aforementioned.

What if we come up with an idea for ICS where both space and write are optimized when running overwrite workloads?

Turns out that’s possible. The RUM conjecture states that only two out of the three amplification factors can be reduced at once. STCS, for example, optimizes for writes, while sacrificing read and space. LCS optimizes for space and read, while sacrificing writes.

With the ScyllaDB Enterprise 2020.1.6 release, ICS gained a new feature called Space Amplification Goal (SAG), which enables space optimization without killing the write optimized nature of the strategy. In simpler words, SAG will allow you to maximize your disk utilization without killing the write performance of ICS. Maximizing disk utilization is very important, from a business perspective, because your cluster will be able to store more data without having to expand its storage capacity. You’ll learn in the next section how that was made possible.

Maximizing Disk Utilization in ICS with Overwrite Workloads

Before the space optimization with SAG is explained, let’s first understand the write optimized nature of both STCS and ICS.

The picture above describes the size-tiered structure of STCS and ICS. The low write amplification is achieved by allowing accumulation of SSTables in a size tier, and when the tier reaches a certain size, its SSTables are compacted into the next larger tier. Therefore, a given piece of data only has to be copied once per each existing tier, allowing for high write performance.

Last but not least, let’s understand the space optimized nature of LCS.

The picture above describes the leveled structure of LCS. The low space amplification is achieved by not allowing data redundancy in a given level L. When a SSTable from level L is promoted to L+1, it will be compacted with all the overlapping SSTables in level L+1. This approach comes with a high write amplification cost though.

With all this knowledge in mind, how could SAG possibly lead ICS to being both space and write optimized?

Turns out that’s possible with a hybrid approach, where ICS combines both the leveled and the size-tiered structures into a single one.

With SAG turned on, the largest tier in ICS will behave exactly like a level in LCS. Data from the second-largest tier will be compacted with the data in the largest one, when the time comes, in a process known as cross-tier compaction, very similar to when LCS compacts SSTables in level 0 with all SSTables in level 1. So the largest tier becomes space optimized, as there’s no data redundancy in it. Given that it contains most of the data in a given table, overall space amplification is significantly reduced as a result of this optimization.

All tiers but the largest one will keep the original size-tiered behavior, where SSTables can still be accumulated in them, so they’re still write optimized.

With the largest tier being space optimized, while all the others being write optimized, ICS becomes both write and space optimized. So ICS + SAG, or ICS 2.0, is now a potential candidate for users with overwrite workloads who care about space.

Configuring SAG to Enable Space Optimization in ICS

Space amplification goal (SAG) was implemented as a new strategy option for ICS, that can be easily configured to make the strategy both space and write optimized. That means space optimization is disabled by default, which is reasonable because write-only (no overwrites) workloads don’t need it.

As the name implies, SAG is a goal for space amplification imposed on the strategy. To configure it, you must choose a value between 1 and 2. Value of 1.5 implies the aforementioned cross-tier compaction when the second-largest tier is half the size of the largest one. In simpler words, with a goal value of 1.5, strategy will be continuously working to reduce the space amplification to below 1.5. Keep in mind that the configured value is not an actual upper bound on space amplification, but rather a goal which the strategy will strive to achieve.

Let’s see ICS + SAG in action with different configuration values:

SAG=0 means that SAG was disabled, meaning ICS was only optimized for writes.

In the graph above, it can be seen that the lower the SAG value the lower the disk usage but the higher the compaction aggressiveness. In other words, the lower the SAG value the lower the space amplification but the higher the write amplification.

A simple schema change as follows will enable the SAG behavior:

ALTER TABLE foo.bar
    WITH compaction = {
        'class': 'IncrementalCompactionStrategy',
        'space_amplification_goal': '1.75' };

For starters, set SAG initially to 1.75 and conservatively decrease it by 0.25, for example, after checking from monitoring that the cluster can sustain the write rate without compaction falling behind. It’s not recommended to set it below 1.25, unless you really know what you’re doing.

Recommendation: write amplification can be further reduced by setting ScyllaDB option --compaction-enforce-min-threshold true, which guarantees the minimum threshold, 4 by default, is respected.

ICS+SAG vs. LCS. Which one should I pick as my compaction strategy?

ICS + SAG isn’t a complete replacement for LCS. LCS’ write amplification may be good enough if running an overwrite workload with a high time locality, where recently written data has a high probability of being modified again soon. Provided LCS has poor write amplification for your particular workload, ICS + SAG becomes definitely a better choice.

Conclusion

Until recently, ICS users had to live with a suboptimal space amplification in face of overwrite-intensive workloads. With the ScyllaDB Enterprise 2020.1.6 release, ICS gained a new feature called Space Amplification Goal (SAG) which will make the strategy both space and write optimized, fixing the problem aforementioned. The space optimization translates into disk utilization being maximized, which in turn translates into your cluster being able to store more data without having to add more nodes. So everybody out there who is either unhappy with LCS or uses ICS on tables with overwrite workload, please go ahead and try ICS + SAG in order to maximize your disk usage and save costs as a result, without having to give up good write performance.

Stay tuned!

About Raphael S. Carvalho

Raphael S. Carvalho is an engineer working on the ScyllaDB storage layer for the past 7 years. Previously, he worked on bringing new file system support for the Syslinux project, which is a suite of bootloaders for starting up Linux. He’s passionate about OS development too, which led him to work on OSv, an operating system for virtualized environments, and make contributions to the Linux kernel as well.