【Cassandra】 Compaction Strategyの種類とその特徴を理解する 

# はじめに
CassandraではCompactionの実行ルールであるCompaction Strategyを選択することができます。
この記事では各種のCompaction Strategyを紹介し、Cassandra5.0系から導入されるUnified Compaction Strategyによって達成される課題などを紹介していきます。

# Compaction Strategyの種類
Compaction Strategyは以下のものが存在しております。
- Size Tiered Compaction Strategy (STCS)
- Leveled Compaction Strategy (LCS)
- Time Window Compaction Strategy (TWCS)
- Unified Compaction Strategy (UCS)

それぞれのStrategyの特徴について記載していきます。

## [Size Tiered Compaction Strategy (STCS)](https://cassandra.apache.org/doc/stable/cassandra/operating/compaction/stcs.html)の紹介
```sql
ALTER TABLE example WITH compaction = {
    'class': 'SizeTieredCompactionStrategy',
    'min_threshold': 4,
    'bucket_low': 0.5,
    'bucket_high': 1.5
};
```
### STCSの特徴
SSTableサイズごとに階層が分かれており、階層内のSSTable数が一定数(min_threshold)を満たした場合にCompactionを実施します。
割り振られる階層は以下の条件で決定されます。
`階層内平均SSTableサイズ * bucket_low(default:0.5) ~ 階層内平均SSTableサイズ * bucket_high(default:1.5)`
該当する階層が存在しない場合には新しい階層を形成します。

### STCSの例
以下でbucket_low:0.5, bucket_high:1.5, min_threshold:4の場合の例を説明します。
![first_stcs.drawio.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3647913/edf01260-408f-6941-abcd-f3d7e4441dad.png)
最初のSSTableの場合、該当する階層が存在しないため新しい階層 `150(300*0.5) ~ 450(300*1.5)` を形成します

---
![first_stcs.drawio2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3647913/af84b09a-f5ab-fde4-76b5-2f7b0f57d441.png)
続いて80MiBのSSTableが作成された場合についても、適切な階層が存在しないため新しい階層 `40(80*0.5) ~ 120(80*1.5)` を形成します。

---
![first_stcs.drawio3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3647913/68b06de9-561f-752f-27dd-39965b5cc860.png)
250MiBのSSTableが作成された場合には右のサイズの範囲を満たすため、300MiBのSSTαbleと同じ階層になります。

---
![first_stcs.drawio4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3647913/18d36680-de93-71ff-9cd3-bcad795b7158.png)
その後階層内のSSTable数がmin_thresholdに達した場合、Compaction実行により1つのSSTableへとマージされて新たな階層を形成します。

---

以上がSTCSの特徴と例になりますが、次のサイズ階層への移動時に必要となるCompactionは一回かつ対象のSSTable数も少ないため、Write負荷は低くなります。したがって、Write負荷が高いワークロードで利用されます。

### STCSの短所
STCSには以下のような短所が存在します。
- 同一階層内の複数SSTableにまたがって同一Keyに対するデータを保持している可能性があるため、Read負荷が高い
- Writeが非常に多いワークロードの場合、Minor Compactionが追いつかずに大量の不要データの読み込みによるレイテンシ悪化が発生するため、定期的なMajor Compactionが必要となるケースがある
- Compaction実施時に実データの2倍のディスク容量が必要とされるため、リソースを余分に確保する必要がある
- SSTableのサイズが大きい場合にはCompactionに時間がかかる
- 大きなSSTableに古い更新データが含まれることにより、不要なデータが残り続けてしまう

STCSについての紹介は以上になります。続いてLeveled Compaction Strategyを説明します。

## [Leveled Compaction Strategy (LCS)](https://cassandra.apache.org/doc/stable/cassandra/operating/compaction/lcs.html)の紹介
```sql
ALTER TABLE example WITH compaction = {
    'class': 'LeveledCompactionStrategy',
    'sstable_size_in_mb': 160,
    'fanout_size': 10
};
```
### LCSの特徴
階層内の合計SSTableサイズが閾値を超過すると次の階層のSSTableとマージされ階層を移動します。
1つのSSTableサイズは `sstable_size_in_mb` (default:160MB)で指定されており、各階層の合計SSTableサイズの閾値は `fanout_size` (default:10)の乗数ごとに増加します。(例: L1:10B, L2:100MB, L3:1000MB...)

### LCSの例
LCSの例を図で示します。
![lcs1.drawio.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3647913/eb515402-155d-13a0-b2d2-3d4bd0a40ee2.png)
まず最初にL0の階層にデータがフラッシュされてSSTableが作成されます。
L0内で大量のSSTableが発生してしまう場合には、L1とのCompaction前にL0内でSTCSが実行されます。

---
![lcs1.drawio2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3647913/12f2ee42-d6bf-bf4a-abe2-ea21874aba40.png)
続いてL0のSSTableがCompactionされL1へと移動します。複数のSSTableで重複している10と100はマージされて、L1内では一つのSSTableでデータを保持します。
SSTableサイズはsstable_size_in_mbで指定した値をもとに決定されます。

---
![lcs1.drawio3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3647913/bbc9e415-3857-aba4-33cb-9cc25fc75db9.png)
L1階層のSSTableサイズがL1閾値以上になった場合には、超過したSSTableは次の階層のSSTableとマージされL2へと移動します。この時L2に1のデータがすでに存在する場合などはL2内で一つのSSTableがデータを保持するようにデータがマージされます。
L2階層のSSTable閾値はL1閾値にfanout_size(default:10)をかけたサイズになり、L2階層が閾値以上になった場合は超過分のSSTableがL3のSSTableとマージされて移動します。

---
LCSでは特定Keyのデータが同一階層に一つしか存在しないようにCompactionが実施されます。
読み込みの際には各階層分で1つのSSTableを読み込むだけで良く、Read負荷が低いため、読み込みの多いワークロードで利用されます。また、STCSに比べると余分なディスク消費がなくリソースを有効活用することができます。

### LCSの短所
LCSにも以下のような短所があります。
- 頻繁にCompactionが発生するため、Write負荷が高い
- 下位階層にSSTableが残り続けることにより、不要なデータが残り続ける(garbagecollectの実行などで対応する必要がある)
- 下位階層に残り続ける不要なデータ削減のためにMajor Compactionを実施すると、全ての階層をリセットしてSSTableを再構築するため、膨大なディスクリソースが必要となる
- 下位階層のCompactionに時間がかかる

LCSについての紹介は以上になります。続いてTime Window Compaction Strategyを説明します。

## [Time Window Compaction Strategy (TWCS)](https://cassandra.apache.org/doc/stable/cassandra/operating/compaction/twcs.html)の紹介
```sql
ALTER TABLE example WITH compaction = {
    'class': 'TimeWindowCompactionStrategy',
    'compaction_window_unit': 'days'
    'compaction_window_size': '1'
};
```
### TWCSの特徴
設定された時間間隔のWindow内データを単一のSSTableへとCompactionします。
すべてのデータにTTLが設定されているデータに対して特に効果的で、時間の経過とともにSSTable全体を削除することでリソースの有効活用が可能になります。
Windowサイズは時間単位の `compaction_window_unit`(default: days)と単位数の `compaction_window_size`(default: 1)で指定します。

### TWCSの例
以下がTWCSの参考図です。
![twcs.drawio.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3647913/b9abcd5a-e9d4-24e8-fcce-06dc2625ef9a.png)

Time Windowが終わるまではWindow内のSSTableはSTCSでCompactionされます。(図の右側になります。)
Time Windowが終わるとWindow内のSSTableは単一になるようにCompactionが実行されます。(図の左側になります。)

特性上、各時間帯で1つのSSTableにマージされた後はCompactionが実行されないため、時間経過とともにSSTable内のデータ全体が削除されない場合には推奨されません。

## [Unified Compaction Strategy (UCS)](https://cassandra.apache.org/doc/latest/cassandra/managing/operating/compaction/ucs.html)の紹介
```sql
ALTER TABLE example WITH compaction = {
    'class': 'UnifiedCompactionStrategy',
    'scaling_parameters': '2, 0, -8',  # 階層ごとに設定可能で 'T4, N, L10' など設定可能
    'target_sstable_size': '1GiB',
    'base_shard_count': '4'
};
```
### UCSの特徴
Cassandra5.0から導入される新しいCompaction Strategyです。
STCSとLCSを包含する特徴を持っており、ワークロードに合わせた細かいパラメータチューニングが可能になります。
以下ではUCSの特徴を紹介します。

#### scaling parameterについて
UCSのscaling_parametersに設定する値で、階層ごとに設定が可能です。
scaling parameterを変化させることにより、ワークロードに合わせた柔軟な設定変更を選択可能になります。
scaling parameterを `w`、下位階層への移動に必要なfanout係数を `f`、Compactionがトリガーされる重複データSSTable数を `t` としたときに以下のように設定が可能です。

##### w>0, f=2+w, t=fの場合
同一階層内に同一Keyに対する重複SSTableが存在し、STCS類似のStrategyになります。
wの値を大きくすることでCompactionの実行数が減少しWrite負荷を低減させますが、複数SSTableにまたがったデータが増加するためRead負荷を増大させます。

##### w<0, f=2-w, t=2の場合
同一階層内の特定Keyに対するSSTableが一つになり、LCS類似のStrategyになります。
LCS同様に同一階層内の特定Keyに対するSSTableが1つであるためRead負荷は減少しますが、CompactionによるWrite負荷が増加します。

##### w=0, f=t=2の場合
STCSとLCSの中間的な設定になります。

scaling parameterとRead/Write負荷の詳細については以下などを参照ください。

https://cassandra.apache.org/doc/latest/cassandra/managing/operating/compaction/ucs.html#read-and-write-amplification


#### Densityについて
UCSは従来のサイズを基準としたStrategyとは異なり、Density(密度)を基準として階層の移動を行います。
後ほど紹介するShardingと合わせることでCompactionの並列化や不要なCompactionの削減を実現することが可能になります。
Densityは `SSTableサイズ/トークン範囲の割合` によって決定されます。

Densityを示す簡単な例を示します。
![density.drawio.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3647913/aa861f75-6f21-4994-2269-41293bf5168c.png)
Compaction前の1つのSSTableのDensityは、Token Rangeが1/1でSSTableサイズが100MiBであるため、100MiBになります。一方、Compaction後のDensityは、Token Rangeが1/4でSSTableが100MiBであるため、400MiBになります。
このように同じSSTableサイズであってもDensityは4倍になります。

#### Shardingについて
ShardingによってSSTableを指定のサイズに分割し、SSTableの肥大化を防ぐことができます。
SSTableの分割数はDensityを `d` 、テーブル作成時に指定する `target_sstable_size` を `t` 、 `base_shard_count` を `b` として以下のようになります。
```math
S = 2^{\log_2\left( \frac{d}{t} \cdot \frac{1}{b} \right)} \cdot b
```
※ sstable_growthによって修正が加えられ、d < tb の場合は b で分割されます。

例: Density: 1200MiB, target_sstable_size: 100MiB, base_shard_count: 4の場合
SSTable分割数 = 2 ^ 2 * 4 = 16 より
分割後のSSTable1つあたりのToken Rangeは 1/16 になります。

### UCSの例
![ucs_ex.drawio.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3647913/edf2fe9b-2dde-dfdc-48d3-1ca6f5632c68.png)
Densityによる階層管理とShardingによって、Token Rangeの重複しないCompactionを並行して実行することが可能になっております。(図のように左右のCompactionを並列に実行可能です)
また、Token Rangeが分割されているので、従来発生していた部分的な重なりしかない余分なCompactionの抑制にもつながっております。

### 従来のStrategyへの効果
UCSはSTCSやLCSで内在している問題点に対して効果を期待することができます。
- SSTableサイズを安定させることができ、ディスクを効率的に利用することが可能になる
- ユースケースに合わせて柔軟な設定を行うことができるため、Read/Write負荷の状況に合わせて調整ができる
- Token RangeでのSSTable分割により、並列化による高速化や部分的にしか重なりのない不要なCompactionを削減できる

以上がUCSの紹介になります。
Cassandra5.0を利用の際には、UCSを利用することでより効率的なCassandra利用が期待されます。

# おわりに
利用状況に合わせてCompaction Strategyを選択することで、レイテンシ改善やリソースの効率化が可能になります。Cassandraを利用の際には是非とも念頭に置いていただければと思います。

# 参考
https://cassandra.apache.org/doc/latest/cassandra/managing/operating/compaction/

https://github.com/apache/cassandra/blob/trunk/src/java/org/apache/cassandra/db/compaction/UnifiedCompactionStrategy.md

https://cwiki.apache.org/confluence/display/CASSANDRA/CEP-26%3A+Unified+Compaction+Strategy

https://docs.datastax.com/en/dse/6.9/architecture/database-internals/how-data-maintain.html

https://www.youtube.com/watch?v=qs2xEoFoYZI&list=PLbzoR-pLrL6rgDn-2Yo-d5liFEnuCCi85&index=40