# Shared-dictionary compression for SSTables

## Overview

Scylla now supports dictionary-based compression for SSTables, which improves
compression ratios by sharing compression dictionaries across compression
chunks.

## Background

Traditional SSTable compression in Scylla works on a chunk-by-chunk basis. Each
chunk is compressed independently, which means patterns that occur across chunks
cannot be effectively leveraged for better compression.

Dictionary-based compression addresses this limitation by training a dictionary
on representative data samples and using it across all compression chunks,
providing the compression algorithm with additional context for referencing.

## How it works

1. **Dictionary training**: Scylla samples data chunks from across the cluster
to build an optimized compression dictionary for a specific table.

2. **Dictionary distribution**: Dictionaries are stored in the `system.dicts`
table (managed by group0). Each table has its own (possibly absent) row there.

3. **Shared Compression**: When opening an SSTable for writing, if the table
has compression dictionaries enabled, the current
recommended dictionary for a table (i.e. the one in `system.dicts`)
is used to compress the data, and is written into the header of
`CompressionInfo.db`.

4. **Decompression**: When opening an SSTable for reading, the dictionary blob
is loaded from `CompressionInfo.db` and used to decompress the data.

## Implementation details

### New persistent data structures

There are two new persistent data structures involved:
- An extension to the SSTable format. `CompressionInfo.db` gains two new
  compressor IDs (lz4 with dicts, zstd with dicts) and new "compressor options"
  which store the dictionary blob used by this SSTable.
- An extension to `system.dicts`, which (in addition to the RPC compression
  dict) now also stores the current recommended SSTable compression dict
  for each table.

### SSTable format extension

The *structure* of the format isn't affected. Instead, we add two new compressor
identifiers (`LZ4WithDictsCompressor` and `ZstdWithDictsCompressor`), which
use the "compressor options" map in CompressionInfo.db to store the dict.

Since the structure isn't affected, we don't increment the SSTable version for
this. Naturally, the dict-compressed SSTables won't be readable by older
versions of Scylla (or by Cassandra), but they should complain about an unknown
compressor rather than consider the SSTable malformed.

If a downgrade is necessary, it can be done by disabling dictionaries
(through schema, or by setting `sstable_compression_dictionaries_enable_writing`
to `false` on all nodes) and rewriting the SSTables
(with `nodetool upgradesstables -a` or similar).

The extension is hidden behind the `SSTABLE_COMPRESSION_DICTS` cluster feature.

#### New entries in CompressionInfo.db

We store the dictionary blob in the "options" map in the header of
`CompressionInfo.db`, under the keys `.dictionary.00000000`,
`.dictionary.00000001`, ...

(It's split into several parts, because the "options" have 16-bit lengths,
and dictionaries are usually bigger than that).

### `system.dicts` extension

If a `system.dicts` partition with key `sstables/{table_uuid}` exists,
it provides the current recommended dict for this table, which is used
to compress new SSTables.

If a table doesn't have a matching row in `system.dicts`, then there's no
current dictionary for this table, and new SSTables should fall back to
dictionaryless compression.

### Compressor factory

With "traditional" compression, a compressor was just a function in the code,
not involving any data. This meant that the creation of compressors was
cheap and easy.

But with dictionaries involved, each unique compressor has its own RAM and cache
footprint. Therefore we want to deduplicate compressors as much as possible.

For this, we create new compressors through a central "compressor factory"
which contacts other shards and ensures that there are no redundant copies
of dictionaries in memory.

### Automatic training

To create a dictionary, some training data is needed.
This means that the dictionary can't be created immediately for a new table,
some data must accumulate in it first.

Also, the dataset can change over time, and a dictionary might become outdated.
In this case, it could be good to retrain it.

But it would be impractical to manually pick the right moments to train new
dicts. So there's `sstable_dict_autotrainer`, which periodically trains
new dicts, if it seems that the given dict-aware table deserves one.
Refer to the implementation for up-to-date details.

### New interfaces

- To enable dictionaries for a given table, the user sets its
  `sstable_compression` entry in the schema to one of the new compressor IDs.
  (The autotrainer will eventually train a dict for it.)
- REST API `storage_service/retrain_dict` can be used to trigger a dictionary
  training for a table manually, without waiting for the automatic training.
- REST API `storage_service/estimate_compression_ratios` can be used to generate
  a report with estimations of compression ratios (on the given table) for
  various compression configs (algorithm, level, chunk size), to guide the
  choice of configuration.

### New RPCs

- `SAMPLE_SSTABLES` is used by a dictionary-training node to gather SSTable
  samples from other nodes.
- `ESTIMATE_SSTABLE_VOLUME` is a helper RPC used by a dictionary-training node
  to find out how much data other nodes have, so that it can later request
  the right (i.e. proportional) amount of samples from each node.
  It's also used by the autotrainer to find out if the table is big enough for
  dictionary training.

### New config entries

There are several new config knobs related to this feature, all named like
`sstable_compression_dictionaries_*`.
Refer to `config.hh` for up-to-date details.