FSST一种短字符串轻量压缩算法

FSST简介

VLDB 2020的paper《FSST: Fast Random Access String Compression》提出了一种针对短字符串的轻量压缩算法Fast Static Symbol Table(简称FSST)，算法根据给定文本生成symbol table，将高频的pattern映射到0~255的空间，字符串根据symbol table进行重新编码。如图1示，未压缩文本第一行为http://in.tum.de，其中http://，in.tum和.de是高频pattern，在symbol table的位置为0, 6和3，因此压缩后的编码为063，压缩比达到5.3。pattern和symbol意义相近，都表示子字符串，后文会交替使用symbol和pattern。

区别于通用块压缩算法，例如LZ4、ZSTD，由于symbol table记录了待压缩文本的全局信息，**FSST压缩比不受数据顺序的影响，**而LZ4和ZSTD基于窗口匹配的算法对于乱序数据的压缩比低于有序的数据。在数据解压方面，FSST不需要对整块数据解码即可解压单个字符串，可以支持压缩数据的随机访问。

从图2的解码编码算法看，假设symbol table已经确定，字符串的压缩和解压过程是非常直观的。实际上，使用静态的symbol table编码字符串的做法并不罕见，github中存在类似的项目，例如总代码量200行不到的smaz，可以对常见的英文文本压缩40~50%。论文的主要贡献在于设计symbols table构建算法和压缩速率的优化。

构建Symbol Table

根据FSST的设计，symbol的长度为1byte ~ 8 bytes，这种设计可以将字符串比较优化为64bits数字的比较，基于该设计，FSST的最优压缩比是8。symbol table预留一个位置作为转义字符，在最坏情况下字符串编码后是原长度的2倍。symbol table构建包括symbol candidates的收集和统计。一种简单的做法是扫描一遍待压缩数据，收集其中1byte ~ 8 bytes的pattern，计算pattern长度和频率的乘积作为gains，对pattern进行排序挑选top-255生成symbol table，但这种做法存在缺陷，因为pattern之间存在相关性，对部分pattern的gains统计是overestimated，导致生成的symbol table压缩比不高。例如urls文本集合的“http://w”，“ttp://ww”和“tp://www”的gains是相同的，将三种pattern作为symbol加入symbol table，将浪费symbol table有限的空间且不利于压缩比的提升。
通过穷举symbol的组合再验证压缩比可以避免symbol gains的错估，但这种方法搜索空间过大：假设symbol的总数为N，那么symbol table的组合数有C(N, 255)种，当N为3000时，总数是一个378位数。
论文设计了一种自底向上生成symbol的启发式算法。算法每轮迭代时遍历未压缩的数据，在symbol table中寻找和当前位置最长匹配的symbol，根据匹配结果收集symbol candidate，并计算gains值，最后选出top-255作为本轮生成的symbol table。压缩数据中上一轮相邻symbol组合成当前symbol candidate。为避免symbol长度单调增加以及增加symbol的多样性，symbol candidate的考虑较复杂，包括：

1. 匹配的symbol本身。
2. 与上一步匹配的symbol的concatenation。
3. 匹配的symbol的首字母。
4. 匹配的symbol的首字母和上一步匹配的symbol的concatenation。
5. 若匹配失败，字符不在symbol table中，则symbol candidate是未匹配的字符。并且该字符视为匹配的symbol，可以参与下一步的concatenation。

启发式算法中symbol的gains计算：gains为symbol出现在压缩后的数据的频率与symbol长度的乘积。上文提到的“http://w”，“ttp://ww”和“tp://www”三种symbol在压缩后的数据不会重复统计，因此能避免gains的overestimate。
迭代次数：算法使用上一轮迭代的symbol组合构建新的symbol candidates，每次组合symbol的长度最多增加一倍，最多需要三轮迭代，symbol即可达到8bytes，论文观察到五轮迭代可以收敛到较好的压缩比。
下面使用论文中的例子说明这种自底向上的启发式算法。在该例子中，symbol table的大小是5，symbol最长为3，在算法初始化阶段，symbol table为空。第一轮迭代产生两种symbol candidate：根据上述的e，所有的未匹配的单个字符t, u, m, c, w, i, v, l, d, b将作为symbol candiate；根据b和e，相邻的字符concatenation组成长度为2的symbol，即图中的um, tu, wi, cw和mc。经过四轮迭代后，数据被压缩为5个字符。

该算法的伪代码如下。实现时symbol table的数据结构经过优化，与伪代码所示不同。另，该伪代码的存在部分错误且未考虑letter在压缩文本中不存在的情况，笔者提供修改后的python版本见repo。

优化压缩速率

论文使用SIMD加速编码优化压缩速率。具体思路是将findLongestSymbol方法使用hashmap替代，以及在symbol table和原字符串后增加特殊的terminator字符，将循环结束的判断转化为terminator字符的比较，便于使用SIMD实现编码过程。
encodeScalar是优化后编码单个symbol的主体部分，hashtable的hashkey为symbol的前3个字符，1或2个字符的symbol存储在shortCodes[]中。对比Algorithm 2的encode方法，寻找最长的匹配的symbol简化为在hashtable或者shortCodes中找到匹配的symbol。

在encodeScalar仅包含简单的计算和一次分支后赋值，分支赋值可以转化为SIMD的mask_mov，论文将该方法使用SIMD改写，每次处理一个batch的字符串(大小不超过512KB)，流程图如下，具体的细节详见论文和源代码。经过AVX-512 unrolling-3优化后，在i9-7900X CPU上可以达到920MB/s的编码速度。

FSST与LZ4对比

论文设计了充分的实验验证FSST各项优化对性能的提升以及与baseline通用压缩算法LZ4的对比，本文主要关注FSST的压缩比和TPC-H上系统性能测试的结果。

压缩比

论文构建了dbtext数据集，包含各类string数据，从压缩比测试看，FSST整体上优于LZ4，同时在压缩速率上存在明显优势。但从LZ4的官方数据(4000MB/s ~ 4900MB/s， 见https://github.com/lz4/lz4)有较大出入，可能与LZ4压缩block大小和LZ4算法参数配置有关。

系统性能测试
论文将FSST和LZ4压缩算法集成到其实验系统Umbra数据库上，并使用TPC-H 10G验证全内存场景下的性能。从图10测试结果看FSST，LZ4对比非压缩数据在全内存场景下性能相近。论文解释原因在TPC-H的join操作集中在integer列上，FSST支持压缩数据上等值比较的优势不能体现。从另一个角度看该实验结果，压缩和解压在全内存场景上似乎对系统查询性能影响较小，但笔者在更大的数据集上，例如TPC-H 100G，发现解压涉及较多的额外内存操作，会引起一定程度的查询性能退化。实际上，10G的数据集相对常见AP查询涉及数据量来看过小，受实验误差影响较大，例如TPC-H Q1只包含integer, decimal和char(1)数据计算，FSST无法压缩char(1)数据，因此uncompressed和FSST的结果应该无显著区别，而实验结果中FSST却有接近10%的性能提升，可见存在一定的实验误差。

总结

FSST学术上分类为Grammar-Based Compressor，在压缩前需要遍历数据以生成编码的"语法"，之后再进行数据的编码, 典型方法有Sequitur，Re-Pair。区别于LZ4, ZSTD等基于滑动窗口的流式压缩算法，FSST优势在于：

1. 支持单个字符串的压缩和解压，因此可以压缩数据上的随机访问。
2. Symbol table包含全局信息，字符串的排列顺序不影响压缩结果，压缩比更稳定。
3. 轻量化，有较高的压缩和解压速率。

支持压缩数据上的随机访问使得FSST有利于集成到数据库系统。例如join等操作需要随机访问数据，可以在压缩数据上直接进行随机访问和等值比较。和保序字典压缩方法例如Dictionary-based order-preserving string compression for main memory column stores一文提出的方法相比，FSST编码后的数据缺少对like和range查询的支持。论文最后提到未来的工作中将设计新的算法使更多算子可以在FSST压缩的数据上直接执行，还考虑结合FSST编码的硬件实现。这些工作将有利于FSST方法在数据库领域的推广。

参考

1. smaz repo https://github.com/antirez/smaz
2. smaz algorithm https://ayende.com/blog/172865/reverse-engineering-the-smaz-compression-library
3. Peter Boncz, Thomas Neumann, and Viktor Leis. 2020. FSST: fast random access string compression. Proc. VLDB Endow. 13, 12 (August 2020), 2649–2661. DOI:https://doi.org/10.14778/3407790.3407851
4. LZ4 repo https://github.com/lz4/lz4
5. ZSTD repo https://github.com/facebook/zstd
6. FSST repo https://github.com/cwida/fsst
7. Grammar-Based Code https://en.wikipedia.org/wiki/Grammar-based_code
8. C. Binnig, S. Hildenbrand, and F. Färber. Dictionary-based order-preserving string compression for main memory column stores. In SIGMOD, pages 283–296, 2009.