了解更多开源请访问：51CTO开源基础软件社区https://ost.51cto.com【What本期必看】FSST思想核心FSST的演进FSST与LZ4的对比FSST的再现【科技DNA】【智能场景】*****************************************************************************************************************************************************************************************************************************************************************************************************************************************************场景自动驾驶/AR语音信号流视频GPU渲染科学、云计算内存缩减科学应用医学图像数据库服务器人工智能图像文本传输GAN媒体压缩图像压缩文件同步数据库系统技术要点c大声压缩稀疏快速傅立叶变换有损视频压缩网格压缩压缩算法框架的动态选择无损压缩分层数据压缩医学图像压缩无损通用压缩人工智能图像压缩短字符串压缩开源项目Draco/基于深度学习算法/PCL/OctNetSFFTAV1/H.266编码/H.266解码/VP9MeshOpt/Draco战神LZ4HCompressDICOMBrotliRAISRAIMCSOMGDOpenJPEGrsyncFSSTFSST快速静态符号表(FSST)压缩，这是一种轻量级的字符串编码方案。简介：字符串在现实世界的数据集中无处不在。它们通常是数据密集型的并且处理起来很慢。在很多真实的数据库中，很大一部分数据都是用字符串来表示的。这是因为字符串通常用作各种数据的包罗万象的类型。人工生成的文本（描述或评论字段）。机器生成的标识符（网址、电子邮件地址、IP地址）。1.现有的字符串处理方案字符串通常是高度可压缩的，许多系统依赖于字典来压缩字符串。但是字典压缩需要精确重复字符串以减小大小，因此当字符串相似但不相等时，字典压缩没有优势。大多数存储在数据库中的字符串通常每个字符串少于30个字节。LZ4不适合压缩小的、单独的字符串，因为它们需要KB数量级的输入大小才能获得良好的压缩因子。但是，数据库系统通常要求随机访问单个字符串，而LZ4算法是通过访问数据块来实现的，不能满足数据库系统的要求。2.主要特点是随机访问（能够解压单个字符串而不解压更大的块）。快速解码（≈1-3周期/字节，或每个内核1-3GB/s）。文本字符串数据集的良好压缩因子(≈2×)。高编码性能（≈4个周期/字节，或≈1GB/秒/字节）。3.核心思想是将频繁出现的最大8字节的子串替换为1字节的代码，这些元素组成一个不可变的符号表。4.前人对数据库系统轻量级压缩的研究主要集中在整数数据上，但字符串在实际工作负载中的普遍性和性能挑战需要更多研究。压缩字符串的最常见方法是使用.字典去重。该字典将每个唯一字符串映射到一个整数代码，该代码使用整数压缩方案进行压缩。在大多数数据库系统中，字符串本身并没有被压缩。宾尼格等人。提出一个具有增量前缀压缩的保序字符串字典。字典表示为混合try/B-tree数据结构，它按排序顺序存储唯一字符串。虽然对某些数据集（例如url）有效，但许多其他常见的字符串数据集（例如uuid）没有长共享前缀，这使得该方案无效。全球词典也有更新成本高等缺点，这阻碍了它们的广泛采用。另一种压缩字符串字典的方法是由Arz和Fischer提出的，他们开发了LZ78的变体，允许对单个字符串进行解压。但是，使用这种方法进行解压非常昂贵，平均长度为19的字符串需要超过1微秒的时间。这相当于每个字符大约100个CPU周期或每秒数十兆字节，这对于许多数据管理用例来说太慢了。PostgreSQL。不使用字符串字典，而是实现了一种称为“超大属性存储技术”(TOAST)的方法。任何大于2KB的都被压缩，较小的值保持未压缩。字节对。该方案是为数不多的允许解压单个短字符串的压缩方案之一。它首先对数据进行全遍历，确定哪些字节值没有出现在输入中，并计算每对字节出现的频率。然后用未使用的字节值替换最常见的字节对。重复此过程，直到不再有未使用的字节为止。字节到字节对未使用字节的依赖意味着，在给定现有压缩表的情况下，无法压缩不可见数据。字节对的递归性质使得解压迭代，非常慢。递归配对。递归构造分层符号语法的随机访问压缩格式。初始语法由所有单字节符号组成，通过用新符号替换源文本中最频繁的连续符号对来递归扩展这些符号，重新计算所有符号对相对于扩展语法的频率。主要步骤是创建静态符号表。识别频繁出现的常见子串（称为符号），并用短的、固定大小的代码替换它们。出于效率原因，符号的长度和字节（而不是位）边界在1到8个字节之间。代码始终为1个字节长，这意味着最多可以有256个符号，其中一个保留为转义码。解压缩。解压相当简单。通过数组查找将每段代码转换为其符号，并将符号附加到输出缓冲区。为了高效解压缩，将每个符号表示为一个8字节（64位）字并将所有符号存储在一个数组中。此外，还有第二个数组存储每个单词的长度。使用这种表示，可以无条件地将64位字存储到输出缓冲区中，然后将输出缓冲区推进符号的实际长度以解压缩代码，这依赖于现代处理器上可用的快速未对齐存储，这种实现需要很少的指令并且没有分支。它的缓存效率也很高，因为符号表（2048字节）和长度数组（256字节）都可以很容易地放入L1CPU缓存中。一些解释。使用转义字符的优点PS：（转义代码不是绝对必要的；也可以只使用那些没有出现在输入字符串中的字节作为代码）。直接原因：代码255被保留为转义标记，表示输入中的后续字节需要按原样复制，无需符号表查找。三个优点：(1)支持使用现有符号表压缩任意（不可见）文本。(2)允许对数据样本进行符号表构建，从而加快压缩速度。(3)它释放了原本会被保留为低频字节的符号，从而提高了压缩因子。单字节符号的连续注入如果两个较短的符号组合成一个较长的符号，如果较长的符号在后续的增益排序中排在末尾，则将被其他具有较长增益的字符串替换，这也意味着原来的两个较短的字符串将消失。本质上，如果不考虑单字节，符号只会变得更长，如果更好的话，永远不可能回到更短的符号。连续注入单字节符号允许重新生成由于这种过于贪婪的选择而丢失的有价值的长符号。FSST的好属性。保留string属性：不会因为编码而转换成其他类型的文本。压缩查询处理。直接比较表中的符号即可。字符串匹配。还可以对压缩字符串执行更复杂的频繁出现的字符串操作（例如，LIKE模式匹配），通过转换为旨在在字节流中识别它们的自动机，将它们重新映射到代码流中。符号表很小。符号表的最大大小是8*255+255字节，但通常只需要几百字节，因为平均符号长度通常在2左右。所以用单独的符号表压缩每个字符串列的每一页是完全可行的，但也以较粗的粒度（按行组或整个表）。更细粒度的符号表构造会产生更好的压缩因子，因此符号表将更适合压缩数据。并行性。由于没有（解）压缩状态，FSST（解）压缩并行化很简单——只有符号表构造算法可能需要序列化。另一方面，让每个批量加载数据块的线程构造一个单独的符号表（应该放在每个块头中）也是可以接受的，这样压缩也变得非常并行。以0结尾的字符串。FSST可选择生成以零结尾的字符串，并且由于字节仅出现在以零结尾的字符串中每个字符串的末尾，因此实际上还有254个代码需要压缩。这略微降低了压缩级别（必须从符号表中删除具有最低值的255个符号，它的出现将使用转义字节进行处理），但这种可选模式允许FSST适应许多现有的基础设施。5.有问题的重复是先统计长度为1到8的子串在数据中出现的频率，然后根据GainOrder选择前255个符号。这种方法的问题是：所选符号可能重叠，因此计算出的增益将被高估。例如，在URL数据集中，8字节的符号http://w几乎出现在每个字符串中，并且最有可能被选中。但是符号ttp://ww和tp://www看起来同样有前途，将所有三个候选者添加到符号表中是对有限数量代码的浪费，并对压缩因子产生负面影响。GreedyGreedy在编码过程中选择最长的符号并不一定能最大化压缩效率。参考我们上面提到的连续单字节注入。总之，符号重叠与贪婪编码相结合会在符号之间产生依赖性问题，这使得难以估计增益以创建良好的符号表。优化方案（1）迭代语料库，使用当前符号表进行动态编码。这个阶段计算符号表的整体质量（压缩因子），但也计算每个符号在压缩表示中出现的频率，以及每对连续符号。(2)使用这些计数，通过选择表观增益最高的符号来构建新的符号表。在示例语料库“tumcwitumvldb”上进行4次迭代。为了使示例更易于说明，将最大符号长度限制为3（而不是8），并将最大符号表大小限制为5（而不是255）。每次迭代后，压缩字符串显示在顶部，但为了便于阅读，显示相应的符号而不是代码。“$”表示转义字节。这是原始的未压缩字符串。在第一次迭代中，压缩字符串的长度暂时加倍，并且由于符号表最初是空的，所以每个符号都必须进行转义。在图的底部我们显示了符号表，前5个符号基于静态增益。在迭代1之后，前5个静态增益是“um”、“tu”、“wi”、“cw”和“mc”。最上面的前两个符号（“um”、“tu”）出现了两次，所以增益为4，而最后三个符号（“wi”、“cw”和“mc”）只出现了一次，所以增益为2注意，符号“mv”、“vl”、“ld”、“db”、“m”、“t”、“u”也有增益2，也可以选择。换句话说，算法在选择顶部符号时任意选择。在迭代2、3和4中，符号表的质量稳步提高。在第4次迭代后，长度为13的语料最初被压缩为5个。从图中也可以看出算法也会出错，但这些错误会在下一次迭代中修复。例如，在迭代2中，符号“tu”看起来很有吸引力，静态增益为4，但由于“tum”也在符号表中，“tu”最终变得一文不值。并在第三次迭代中得到纠正。技术优化：AVX512压缩：第一步，FSSTAPI压缩一批字符串，将字符串复制到由512段组成的临时缓冲区中，必要时拆分长字符串，并添加终止符。在第二步中，作业队列数组首先按反向字符串长度进行基数排序——速度很快且只需要一次传递——因此首先处理最长的字符串，这有助于负载平衡。作业可能以非连续的顺序完成，因此由于排序而以非连续的作业顺序开始编码工作不会（进一步）使算法复杂化。第三步，AVX512的优势不在于内存访问，而是在压缩内核中利用了并行计算。不仅仅是一次启动SIMD内核来处理8个通道中的8个字符串（或24个通道中的24个字符串，3×展开），因为一些字符串会比其他字符串短得多，而一些字符串会比其他字符串压缩得更多。这意味着许多通道在编码工作结束时将是空的。因此，如果需要，512个作业被缓冲，并且在每次迭代中重新填充通道。退出作业（作业控制寄存器中的通道）使用compress_store指令，填充expand_load指令。FSSTvs.LZ4Speed上表分别显示了LZ4和FSST在每个数据集上的相对性能以及三个指标的平均性能。对于几乎所有的数据集，FSST在压缩因子和压缩速度上都优于LZ4。平均而言，除了产生更好的压缩因子外，FSST的压缩速度也提高了60%。对于解压速度，FSST在某些数据集上更快，而LZ4在其他数据集上更快——平均速度几乎相同。RandomAccess在数据库场景中，通常不存储大文件，而是使用字符串属性或包含大量相对较短字符串的字典。单独使用LZ4压缩这些字符串会产生非常差的压缩因子，而普通的LZ4（LZ4行）无法合理地处理短字符串——低于1的压缩因子意味着数据大小实际上会略有增加。LZ4还可以选择支持使用额外的字典，它需要与压缩数据一起提供。使用zstd预先生成适合语料库的字典（LZ4字典），一定程度上提高了压缩系数，但严重影响了压缩速度。测试结果如下图所示：在文本数据数据库环境之外，压缩社区经常在Silesia语料库上评估压缩方法，该语料库由11个文件组成，其中4个是文本文件（dick-ens、reymont、mr、webster)，1是XML，6是二进制文件。FSST将文本文件的压缩大小平均增加了10%，但将二进制文件的压缩大小平均减少了25%。虽然二进制被认为与FSST无关，但它的压缩比在大型XML和JSON文件上比LZ4差2-2.5倍，这是相关的。然而，数据库系统不应将这些组合值存储为简单的字符串，而应存储为允许查询处理的特殊类型。例如，Snowflake识别JSON列中的结构，并在内部将每个频繁出现的JSON属性存储在单独的内部列中。FSST的演变FSST压缩算法经过多次迭代才达到当前的设计。上表显示了7种变体的压缩因子（CF）、符号表构建成本（CS）和字符串编码速度（SE）第一种设计是基于后缀数组，实现了1.97的压缩因子，但符号表构造需要74.3个周期/字节，编码需要160个周期/字节。当前版本的AVX512（图中的变体7）在建表方面比第一个版本快90倍，在编码方面快40倍——同时提供更高的压缩因子。最终版本也比原始FSST版本（变体4）快得多，这要归功于损失完美哈希和AVX512——尽管与变体4相比不得不牺牲大约6%的空间增益。虽然需要多次迭代，但符号的构造表只占用编码时间的一小部分。优化构建需要将迭代次数从10次减少到5次，构建一个示例（随着每次迭代而增长），并缩小计数器的内存占用。重现流程的系统要求可以是Linux、Windows、MacOS，这里是Deepin20.5/Linux环境。源码准备首先来到FSST的开源仓库https://github.com/cwida/fsst，如果已经配置好Git环境，可以复制如图所示的https或ssh地址克隆源码到当地；如果没有配置Git，可以参考github或者gitee的相关说明配置运行。不过这里Git并不是必要条件，你也可以手动“下载ZIP”获取压缩包并解压。上面提到，对于Git环境，在终端输入如下命令：gitclonehttps://github.com/cwida/fsst.git#如果已经配置了SSH公钥，可以在如下所示的表格。cdfsst/:环境搭建CMake安装。FSST是用C++语言实现的，因此依赖CMake工具进行编译构建。在Debian系统下，可以很方便的使用apt来实现工具的安装和初始化。键入并执行以下命令：sudoaptupdatesudoaptinstallcmake，可以看到之前已经安装了cmake，版本为3.18.4：Zstd和LZ4库的安装。FSST在压缩过程中需要调用zstd和lz4的相关API生成相应的字典，所以还需要准备相应的动态库：sudoaptinstallzstd*lz4*libzstd*liblz4*#cmake安装完成后,你可以在/usr/lib/x86_64-linux-gnu/中使用可以看到已经生成了相关的文件：另外需要建立一个到/usr/lib/的软链接，避免后续链接找不到default目录：#注意，下面'1.4.8''1.8.3'等版本号需要根据实际情况相应替换cd/usr***/lib/x86_64-linux-gnu/echo'../libzstd.so../libzstd.so.1../libzstd.so.1.4.8'|sudoxargs-n1ln-slibzstd.so.1.4.8echo'../liblz4.so../liblz4.so.1../liblz4.so.1.8.3'|sudoxargs-n1ln-sliblz4.so.1.8.3编译搭建环境部署基本完成，下面开始编译。cd-cmake./make-j8&&makebinary100%完成后说明编译成功。查看目录，可以看到已经生成了fsst的二进制程序：为了后续操作的方便，建议添加到环境变量中：vim~/.bashrcexportPATH=/home/yanxu/ELT.ZIP/fsst:$PATH#在行尾添加：wq#保存退出即可正常使用，输入fsst查看说明：中提供了足够数量的数据集评估测试自动化测试仓库是用来对算法进行评估的，还有自动化脚本帮助一键跑全流程。我们试试看：cdpaper/chmod+x*.shresults作者的测试结果已经存放在该目录下，不过我们也可以在自己的机器上再次运行测试，执行以下命令：makeexperiments会花很长时间，耐心等待吧。下面是笔者的一个例子：最左边一栏是各种字符集，另外三个方框分别代表压缩率、压缩速度、解压速度。其中，左边是LZ4，右边是FSST。不难看出，在压缩率方面，FSST在url方面仅略弱于LZ4；在压缩速度方面，LZ4只在hex上略有优势；被忽略。除了手动测试，您还可以手动比较更多算法。了解更多开源信息，请访问：51CTO开源基础软件社区https://ost.51cto.com。
