本文已经是高速数据压缩主题的第二篇了。第一篇文章描述了以 10 GB/秒的速度运行的压缩器。每个处理器核心（最小压缩，RTT-Min）。
该压缩器已在取证复印机设备中实现，用于高速压缩存储介质转储并增强加密强度；还可以用于在高速保存虚拟机映像和 RAM 交换文件时对其进行压缩SSD 驱动器。
第一篇文章还宣布开发了一种压缩算法，用于压缩 HDD 和 SSD 磁盘驱动器的备份副本（中度压缩，RTT-Mid），并显着改进了数据压缩参数。到现在为止，这个压缩器已经完全准备好了，这篇文章就是关于它的。
实现 RTT-Mid 算法的压缩器提供的压缩比可与在高速模式下运行的标准归档器（例如 WinRar、7-Zip）相媲美。同时，其运行速度至少高出一个数量级。
数据打包/解包的速度是决定压缩技术应用范围的关键参数。不太可能有人会想到以每秒 10-15 兆字节的速度压缩 XNUMX TB 的数据（这正是标准压缩模式下归档器的速度），因为在满处理器负载的情况下，这将花费近 XNUMX 个小时。 。
另一方面，相同 TB 的数据可以在大约 2 分钟内以每秒 3-XNUMXGB 的速度复制。
因此，如果以不低于实际输入/输出速度的速度执行大容量信息的压缩就很重要。对于现代系统来说，该速度至少为每秒 100 兆字节。
现代压缩机只能在“快速”模式下产生这样的速度。正是在这种当前模式下，我们将 RTT-Mid 算法与传统压缩器进行比较。
新压缩算法的对比测试
RTT-Mid 压缩器是测试程序的一部分。在真正的“工作”应用程序中，它的工作速度要快得多，它明智地使用多线程并使用“普通”编译器，而不是 C#。
由于对比测试中使用的压缩机原理不同，不同类型的数据压缩方式不同，为了测试的客观性，采用了测量“医院平均温度”的方法……
创建了 Windows 10 操作系统的逻辑磁盘的逐扇区转储文件；这是每台计算机上实际可用的各种数据结构的最自然的混合。压缩此文件将使您能够将新算法的压缩速度和程度与现代归档器中使用的最先进的压缩器进行比较。
这是转储文件：
转储文件使用 PTT-Mid、7-zip 和 WinRar 压缩器进行压缩。 WinRar 和 7-zip 压缩器设置为最大速度。
压缩机运行 7-ZIP:
它使处理器加载 100%，而读取原始转储的平均速度约为 60 MB/秒。
压缩机运行 WinRAR的:
情况类似，处理器负载几乎为100%，平均转储读取速度约为125 MB/秒。
与前一种情况一样，归档器的速度受到处理器功能的限制。
压缩机测试程序现已运行 RTT-中:
截图显示处理器负载为50%，其余时间空闲，因为没有地方可以上传压缩数据。数据上传盘（Disk 0）几乎已满。数据读取速度（磁盘1）差异很大，但平均超过200兆字节/秒。
在这种情况下，压缩器的速度受到将压缩数据写入磁盘 0 的能力的限制。
现在生成的档案的压缩比：
可以看出，RTT-Mid 压缩器的压缩效果最好；它创建的压缩包比 WinRar 压缩包小 1,3 GB，比 2,1z 压缩包小 7 GB。
创建档案所花费的时间：
- 7-zip – 26 分 10 秒；
- WinRar – 17 分 40 秒；
- RTT-中 – 7 分 30 秒。
因此，即使是使用 RTT-Mid 算法的测试、非优化程序，创建存档的速度也快了两倍半以上，而存档却比竞争对手的存档小得多……
不相信截图的人可以自行验证其真实性。测试程序可在 ，下载并检查。
但仅在支持 AVX-2 的处理器上，如果不支持这些指令，压缩器将无法工作，并且不要在较旧的 AMD 处理器上测试算法，它们在执行 AVX 指令方面速度很慢......
使用的压缩方法
该算法使用一种以字节粒度索引重复文本片段的方法。这种压缩方法早已为人所知，但并未被使用，因为匹配操作所需的资源非常昂贵，并且比构建字典需要更多的时间。所以RTT-Mid算法是“回到未来”的经典例子......
PTT 压缩器使用独特的高速匹配搜索扫描器，这使我们能够加快压缩过程。自制扫描仪，这就是“我的魅力……”，“它相当昂贵，因为它完全是手工制作的”（用汇编程序编写）。
匹配搜索扫描器是根据两级概率方案进行的：首先，扫描匹配的“标志”的存在，并且只有在该位置识别出“标志”之后，才执行检测真实匹配的过程已开始。
匹配搜索窗口的大小是不可预测的，具体取决于处理的数据块中的熵程度。对于完全随机（不可压缩）的数据，其大小为兆字节，对于具有重复的数据，其大小始终大于兆字节。
但许多现代数据格式是不可压缩的，并且通过它们运行资源密集型扫描仪是无用且浪费的，因此扫描仪使用两种操作模式。首先，搜索源文本中可能重复的部分；此操作也是使用概率方法执行的，并且执行速度非常快（速度为 4-6 GB/秒）。然后，主扫描仪会处理可能匹配的区域。
索引压缩效率不是很高，必须用索引替换重复的片段，并且索引数组显着降低了压缩率。
为了提高压缩率，不仅对字节字符串的完整匹配进行索引，而且当字符串包含匹配和不匹配的字节时，还对部分匹配进行索引。为此，索引格式包括一个匹配掩码字段，该字段指示两个块的匹配字节。为了获得更大的压缩，索引用于将几个部分匹配的块叠加到当前块上。
所有这些使得在 PTT-Mid 压缩器中获得与使用字典方法制作的压缩器相当的压缩比成为可能，但工作速度更快。
新压缩算法的速度
如果压缩器以独占高速缓存的方式运行（每个线程需要 4 MB），则运行速度范围为 700-2000 MB/秒。每个处理器核心，取决于被压缩的数据类型，并且几乎不依赖于处理器的工作频率。
对于压缩器的多线程实现，有效的可扩展性由第三级高速缓存的大小决定。例如，“板载”有 9 MB 高速缓存，启动两个以上的压缩线程是没有意义的；速度不会因此而提高。但有了 20 MB 的缓存，您就可以运行 XNUMX 个压缩线程。
此外，RAM 的延迟成为决定压缩器速度的重要参数。该算法使用对OP的随机访问，其中一些没有进入高速缓冲存储器（大约10％）并且它必须空闲，等待来自OP的数据，这降低了操作速度。
显着影响压缩机的速度和数据输入/输出系统的操作。 I/O块向OP的请求向CPU请求数据，这也降低了压缩速度。这个问题对于笔记本电脑和台式机来说很重要；对于服务器来说，由于更先进的系统总线访问控制单元和多通道 RAM，这个问题不太重要。
在本文的全文中，我们讨论压缩；减压仍然超出了本文的范围，因为“一切都被巧克力覆盖”。解压速度要快得多，并且受到 I/O 速度的限制。一个线程中的一个物理核心可轻松提供 3-4 GB/秒的解包速度。
这是由于解压缩过程中没有进行匹配搜索操作，从而在压缩过程中“吃掉”了处理器和缓存的主要资源。
压缩数据存储的可靠性
正如使用数据压缩（归档器）的整个软件类别的名称所暗示的那样，它们是为长期存储信息而设计的，不是数年，而是数百年和数千年......
在存储过程中，存储介质会丢失一些数据，下面是一个例子：
这种“模拟”信息载体已经有一千多年的历史了，一些碎片已经丢失，但总的来说，信息是“可读的”......
现代数字数据存储系统和数字媒体的负责任制造商都没有提供超过 75 年的完整数据安全保证。
而这是一个问题，但却是一个推迟的问题，我们的子孙后代会解决它……
数字数据存储系统不仅会在 75 年后丢失数据，而且数据错误随时可能出现，甚至在记录过程中也是如此，他们试图通过使用冗余并使用纠错系统来纠正这些失真，从而最大限度地减少这些失真。冗余和校正系统不能总是恢复丢失的信息，即使恢复，也不能保证恢复操作正确完成。
这也是一个大问题，但不是推迟的问题，而是当前的问题。
用于归档数字数据的现代压缩器是建立在字典方法的各种修改的基础上的，对于这种档案来说，丢失一条信息将是致命的事件；甚至有一个既定的术语来描述这种情况 - “损坏的”档案...
使用字典压缩在档案中存储信息的低可靠性与压缩数据的结构有关。这种档案中的信息不包含源文本，字典中的条目数量存储在那里，并且字典本身由当前压缩文本动态修改。如果归档片段丢失或损坏，则所有后续归档条目都无法通过内容或字典中条目的长度来识别，因为不清楚字典条目编号对应的内容。
从这样一个“损坏”的档案中恢复信息是不可能的。
RTT 算法基于一种更可靠的压缩数据存储方法。它使用索引方法来计算重复片段。这种压缩方法使我们能够最大限度地减少存储介质上信息失真的后果，并且在许多情况下自动纠正信息存储过程中出现的失真。
这是因为索引压缩情况下的归档文件包含两个字段：
- 删除了重复部分的源文本字段；
- 索引字段。
索引字段对于信息恢复至关重要，其大小并不大，并且可以复制以实现可靠的数据存储。因此，即使源文本或索引数组的一个片段丢失，所有其他信息也将毫无问题地恢复，就像使用“模拟”存储介质的图片一样。
该算法的缺点
没有缺点就没有优点。索引压缩方法不压缩短重复序列。这是由于指数法的局限性造成的。索引的大小至少为 3 个字节，最大可达 12 个字节。如果遇到大小小于描述它的索引的重复，则不会考虑该重复，无论在压缩文件中检测到此类重复的频率如何。
传统的字典压缩方法有效地压缩了短长度的多次重复，因此获得了比索引压缩更高的压缩率。确实，这是由于中央处理器的高负载而实现的；为了使字典方法开始比索引方法更有效地压缩数据，它必须将数据处理速度实际上降低到每秒10-20兆字节CPU 负载满的计算装置。
如此低的速度对于现代数据存储系统来说是不可接受的，并且其“学术”兴趣大于实际意义。
信息压缩程度将在RTT算法的下一次修改（RTT-Max）中显着提高，该算法已经在开发中。
所以，一如既往，待续……
来源： habr.com