Learning Platform
Глоссарий Troubleshooting
Урок 10.06 · 35 мин
Продвинутый
FSSTString CompressionSymbol TableRandom AccessLate DecompressionDuckDBFSST12

FSST: сжатие строк таблицей символов

В Модуле 08, Урок 04 мы видели проблему строковых кодировок: dictionary работает только при низкой кардинальности. Когда словарь переполняется (>1M unique строк), Parquet падает на PLAIN, ORC — на DIRECT stream. Строки занимают 60–80% размера типичных аналитических таблиц.

FSST (VLDB 2020, Boncz, Neumann & Leis) решает проблему иначе: вместо замены целых строк на индексы (dictionary) — замена частей строк на однобайтовые коды через обучаемую таблицу символов. Ключевое отличие от LZ-семейства: FSST сохраняет random access к отдельным строкам без декомпрессии блока.

Символьная таблица: 256 символов × 1–8 байт

FSST строит таблицу из 256 «символов» — частых подстрок длиной 1–8 байт. Каждый символ кодируется одним байтом (0x00–0xFF). 256 кодов — это всё пространство одного байта.

FSST: структура символьной таблицы

Обучающая выборка: 1000+ строк из блока

Обучающая выборка: 1000–5000 строк из блока. FSST анализирует частотность подстрок длиной 1–8 байт и выбирает 256, дающих максимальное суммарное сжатие.
Алгоритм обучения: 5 итераций greedy selection
Символьная таблица: 256 entriesТаблица: массив из 256 записей. Каждая запись — подстрока 1–8 байт. Code 0x00 → 'http://' (7 байт). Code 0x01 → '.com' (4 байта). Code 0x02 → 'www.' (4 байта). ... Code 0xFE → 'e' (1 байт). Code 0xFF = escape byte (следующий байт — литерал). Суммарный размер таблицы: ≤ 256 × 8 = 2048 байт (но обычно ~1 KB).
Overhead таблицы

Overhead: ~1–2 KB на блок. Для 10 MB данных: < 0.02%

Overhead символьной таблицы: ~1–2 KB на блок. Для блока из 65K строк (10+ MB) — overhead < 0.02%. Таблица хранится один раз в начале блока. Декодер читает таблицу, затем поточно декодирует строки.

Алгоритм обучения таблицы

FSST обучает таблицу за 5 итераций greedy-алгоритма:

FSST: обучение символьной таблицы за 5 итераций
Итерация 1: частотность одиночных байтовПервая итерация: считаем частоту каждого байта в обучающей выборке. 256 самых частых однобайтовых символов заполняют начальную таблицу. Кодируем sample этой таблицей → считаем compression ratio.
Итерация 2: конкатенация пар
Итерация 2: пары символовВторая итерация: для каждой пары соседних символов в текущей таблице — пробуем объединить в один новый символ. 'h'+'t' → 'ht'. Если пара встречается чаще, чем отдельные символы — заменяем. Сохраняем 256 лучших. Кодируем заново → ratio улучшается.
Итерации 3–5: рост символов
Итерации 3–5: символы растут до 8 байтКаждая следующая итерация объединяет частые пары предыдущих символов. К 5-й итерации символы достигают максимальной длины 8 байт: 'http://' (7B), '/api/v1' (7B), '.com/us' (7B). Ratio стабилизируется к 5-й итерации — дальнейшие улучшения < 1%.

5 итераций → таблица готова. Время обучения: < 1 мс

5 итераций — фиксированное число, не зависит от данных. Время обучения: O(sample_size × 5 × 256). На практике: < 1 мс на 5000 строк. Результат: таблица из 256 символов, оптимизированная для конкретного блока данных.

Кодирование и декодирование

Кодирование — замена подстрок на коды. Декодирование — замена кодов на подстроки. Обе операции — поточные: один проход слева направо, без lookback.

FSST: encode и decode пошагово

Вход: ‘http://www.example.com/api/users’ (33 байта)

Входная строка: 'http://www.example.com/api/users' — 33 байта.
Encode: greedy longest-match, слева направо
КодированиеКодер идёт слева направо, на каждой позиции ищет самый длинный символ из таблицы: 'http://' → 0x00 (7 байт → 1 байт). 'www.' → 0x02 (4→1). 'exam' не в таблице → 'e' → 0xFE (1→1), 'x' → escape 0xFF+'x' (1→2), 'a' → 0x10 (1→1), 'm' → 0x11 (1→1). 'ple' → 0x20 (3→1). '.com' → 0x01 (4→1). '/api/' → 0x03 (5→1). 'user' → 0x05 (4→1). 's' → 0x12 (1→1).
Результат
Закодированная строка33 байта → 12 байт: [00][02][FE][FF][78][10][11][20][01][03][05][12]. Ratio: 33/12 ≈ 2.75x. Escape byte 0xFF используется только для байтов, не входящих ни в один символ таблицы.
Decode: table lookup, слева направо
ДекодированиеДекодер читает байт за байтом: [00] → table[0x00] = 'http://' (7B, записать). [02] → table[0x02] = 'www.' (4B). [FE] → table[0xFE] = 'e' (1B). [FF] → escape: следующий байт [78] = 'x' (литерал). [10] → 'a'. [11] → 'm'. [20] → 'ple'. [01] → '.com'. [03] → '/api/'. [05] → 'user'. [12] → 's'. Декодирование: O(compressed_size) — один проход, table lookup по индексу = O(1).

Выход: ‘http://www.example.com/api/users’ (33 байта, lossless)

Восстановленная строка: 'http://www.example.com/api/users' — побайтово идентична оригиналу. Throughput декодирования: 1–3 GB/s (сравнимо с LZ4).

Random access: ключевое отличие от LZ

FSST сохраняет random access к отдельным строкам — свойство, которого нет ни у LZ4, ни у Zstd, ни у GZIP:

Random access: FSST vs block compression
ОперацияЧто нужно сделать
Zstd / LZ4 (block)Block compression: весь блок сжат как единое целое
FSSTFSST: каждая строка сжата независимо
Прочитать строку #500Нужно получить одну строку из блока с 65K строками.
Распаковать весь блок → найти #500Zstd/LZ4: блок = единый сжатый поток. Чтобы прочитать строку #500, нужно декомпрессировать весь блок (64 KB – 1 MB), найти offset строки, прочитать. Стоимость: O(block_size). Для 1 MB блока — ~0.3 мс на Zstd.
Offset table → decode строки #500FSST: каждая строка — независимый сжатый буфер. Offset table (массив смещений) указывает на начало строки #500 в сжатых данных. Читаем байты строки #500, декодируем через symbol table. Стоимость: O(string_length). Не трогаем остальные 64999 строк.
Сравнить 2 строкиWHERE name = 'Alice': нужно сравнить каждую строку с константой.
Распаковать → сравнить plainZstd/LZ4: распаковать обе строки (или весь блок) → сравнить plain текст. Стоимость: O(block_size) + O(string_length).
Закодировать константу → memcmpFSST: закодировать 'Alice' той же symbol table → сжатые байты. Сравнить сжатые байты с memcmp — без декодирования строки! Если сжатые представления равны → строки равны. Стоимость: O(compressed_len). Late decompression: предикат работает на сжатых данных.
Параллельная обработкаМожно ли разбить блок на части и обрабатывать параллельно?
Нельзя: поток зависит от историиLZ77: каждый match ссылается на предыдущие данные в потоке. Нельзя начать декодирование с середины блока — нужен весь контекст от начала.
Trivially parallel: каждая строка — independentFSST: каждая строка декодируется через ту же symbol table, без зависимости от других строк. 8 threads → decode 8 строк одновременно. Идеально для SIMD и GPU.
NOTE

Late decompression (сравнение в сжатом виде) — одно из ключевых преимуществ FSST для аналитических query engines. DuckDB использует это: WHERE url LIKE '%example%' может выполняться на FSST-сжатых строках, декомпрессируя только финальные match’и для вывода. Предикат = работает через encode-and-compare; LIKE — через частичное декодирование.

FSST12: 4096 символов для JSON/XML

Стандартный FSST использует 8-bit коды (256 символов). Для данных с широким алфавитом (JSON, XML, HTML — теги, атрибуты, namespaces) 256 символов может не хватить. FSST12 расширяет коды до 12 бит:

FSST vs FSST12: 256 vs 4096 символов
ПараметрХарактеристика
FSST (8-bit)Стандартный FSST: 256 символов
FSST12 (12-bit)Расширенный FSST12: 4096 символов
КодыКоличество кодов в таблице символов
256 (1 байт)256 кодов = полное пространство одного байта. Каждый символ адресуется 1 байтом.
4096 (1.5 байта)4096 кодов = 12-bit пространство. Код занимает 1.5 байта. Два кода пакуются в 3 байта.
Overhead таблицыРазмер символьной таблицы
≤ 2 KB256 × 8 = 2048 байт максимум. На практике ~1 KB (средний символ 3–4 байта).
≤ 32 KB4096 × 8 = 32 KB максимум. Больший overhead, оправдан только для данных с широким алфавитом.
Лучше дляТип данных, где вариант оптимален
Текст, URLs, emailsДанные с ограниченным алфавитом: ASCII текст, URL-паттерны, email-адреса. 256 символов покрывают основные повторяющиеся подстроки.
JSON, XML, HTMLДанные со структурными тегами: JSON ключи, XML namespaces, HTML атрибуты. Тысячи уникальных подстрок — 256 символов недостаточно для покрытия всех тегов и ключей.
Типичный ratioСтепень сжатия на типичных данных
~3x на тексте~3x на текстовых данных (URLs, emails, names). Сравнимо с LZ4 по ratio, но с random access.
~4x на JSON~4x на JSON: больше символов → больше длинных подстрок покрыто → лучше ratio. Но overhead таблицы выше.

Adoption: кто использует FSST

FSST — одна из самых широко адаптированных CWI-кодировок. Три крупных аналитических движка интегрировали её:

FSST adoption: DuckDB, Hyrise, Velox
DuckDBDuckDB (CWI spin-off). FSST интегрирован через PR #4366 (2022). Используется для string columns в native storage format. Автоматически выбирается для VARCHAR columns с кардинальностью выше порога dictionary encoding. Late decompression включён: предикаты WHERE работают на FSST-строках.
HyriseHyrise — in-memory OLAP от Hasso Plattner Institute. FSST используется для string compression в memory-resident columns. Преимущество: random access без декомпрессии блоков — критично для in-memory систем, где latency доступа = наносекунды.
VeloxVelox — execution engine от Meta (ex-Facebook). Используется в Presto и Spark-based pipelines. FSST интегрирован для string vectors. Velox обрабатывает петабайты данных — FSST экономит memory bandwidth.
Open-source реализации
C++ (reference)Оригинальная реализация от авторов paper. GitHub: cwida/fsst. MIT license. Production-quality C++.
Rust: spiraldb/fsstRust-реализация от SpiralDB. В разработке. Crate fsst-rs.
Go: axiomhq/fsstGo-реализация от Axiom (observability platform). Используется в production для сжатия log-строк.
TIP

FSST, ALP и FastLanes — три кодировки от одной группы (CWI Amsterdam), решающие три разных типа данных: FastLanes — integers (SIMD-оптимизация), ALP — floats (decimal→integer трансформация), FSST — strings (символьные таблицы). Все три интегрированы в DuckDB. Вместе они покрывают ~95% типов данных в аналитических workloads.

Итог

FSST — string compression через обучаемую символьную таблицу. Ключевые свойства:

  • 256 символов × 1–8 байт — таблица обучается за 5 итераций greedy selection (менее 1 мс)
  • Random access — каждая строка декодируется независимо, без декомпрессии блока
  • Late decompression — предикаты (=, LIKE) работают на сжатых строках
  • ~3x на текстовых данных при throughput 1–3 GB/s (сравнимо с LZ4)
  • FSST12 — 12-bit коды (4096 символов) для JSON/XML с широким алфавитом
  • Adopted: DuckDB, Hyrise, Velox, реализации на C++/Rust/Go

В следующем уроке — как все эти техники складываются в будущее кодирования: compressed execution, partial decompression, AnyBlox, и куда движутся исследования.

Закончили урок?

Отметьте его как пройденный, чтобы отслеживать свой прогресс

Войдите чтобы оценить урок
Вернуться к курсу
Прогресс модуля
0 из 7