高速フェールセーフ圧縮 (続き)

この記事は、高速データ圧縮に関するトピックの 10 番目の記事です。最初の記事では、XNUMX GB/秒の速度で動作するコンプレッサーについて説明しました。プロセッサ コアごと (最小圧縮、RTT-Min)。

このコンプレッサーは、ストレージ メディア ダンプの高速圧縮と暗号強度の強化を目的として、フォレンジック デュプリケータの機器にすでに実装されており、仮想マシンのイメージや RAM スワップ ファイルを高速で保存する際の圧縮にも使用できます。 SSDドライブ。

最初の記事では、データ圧縮パラメータが大幅に改善された、HDD および SSD ディスク ドライブのバックアップ コピーを圧縮するための圧縮アルゴリズム (中圧縮、RTT-Mid) の開発についても発表しました。ここまでで、このコンプレッサーは完全に準備が整ったので、この記事ではそれについて説明します。

RTT-Mid アルゴリズムを実装したコンプレッサーは、高速モードで動作する WinRar、7-Zip などの標準アーカイバーに匹敵する圧縮率を提供します。同時に、その動作速度は少なくとも一桁高速です。

データのパッキング/アンパッキングの速度は、圧縮テクノロジーの適用範囲を決定する重要なパラメーターです。テラバイトのデータを 10 秒あたり 15 ～ XNUMX メガバイトの速度 (これはまさに標準圧縮モードのアーカイバの速度です) で圧縮することを考える人は誰もいないでしょう。プロセッサのフル負荷ではほぼ XNUMX 時間かかるからです。 。

一方、同じテラバイトを 2 秒あたり 3 ～ XNUMX ギガバイト程度の速度で約 XNUMX 分でコピーできます。

したがって、大容量の情報の圧縮は、実際の入出力速度以上の速度で行うことが重要である。最新のシステムの場合、これは少なくとも 100 メガバイト/秒です。

最新のコンプレッサーは、「高速」モードでのみこのような速度を実現できます。 RTT-Mid アルゴリズムと従来のコンプレッサーを比較するのは、この現在のモードです。

新しい圧縮アルゴリズムの比較テスト

RTT-Mid コンプレッサーはテスト プログラムの一部として機能しました。実際に「動作する」アプリケーションでは、はるかに高速に動作し、マルチスレッドを賢明に使用し、C# ではなく「通常の」コンパイラを使用します。

比較テストで使用されたコンプレッサーは異なる原理に基づいて構築されており、データの種類によって圧縮方法が異なるため、テストの客観性を考慮して、「病院内の平均気温」を測定する方法が使用されました。

Windows 10 オペレーティング システムで論理ディスクのセクタごとのダンプ ファイルが作成されました。これは、すべてのコンピュータで実際に使用できるさまざまなデータ構造の最も自然な組み合わせです。このファイルを圧縮すると、新しいアルゴリズムの速度と圧縮の程度を、最新のアーカイバーで使用されている最先端の圧縮プログラムと比較できます。

ダンプファイルは次のとおりです。

ダンプ ファイルは、PTT-Mid、7-zip、および WinRar コンプレッサーを使用して圧縮されました。 WinRar および 7-zip コンプレッサーは最大速度に設定されました。

コンプレッサー稼働中 7ジップ:

プロセッサーの負荷は 100% ですが、元のダンプの読み取りの平均速度は約 60 メガバイト/秒です。

コンプレッサー稼働中 WinRARの:

状況も同様で、プロセッサの負荷はほぼ 100%、平均ダンプ読み取り速度は約 125 メガバイト/秒です。

前のケースと同様に、アーカイバの速度はプロセッサの能力によって制限されます。

コンプレッサーのテスト プログラムが実行中です RTT-ミッド:

スクリーンショットは、圧縮データをアップロードする場所がないため、プロセッサーの負荷が 50% であり、残りの時間はアイドル状態であることを示しています。データ アップロード ディスク (ディスク 0) はほぼ完全にロードされています。データ読み取り速度 (ディスク 1) は大きく異なりますが、平均して 200 メガバイト/秒以上です。

この場合、コンプレッサーの速度は、圧縮データをディスク 0 に書き込む機能によって制限されます。

結果として得られるアーカイブの圧縮率は次のようになります。

RTT-Mid コンプレッサーが圧縮の最良の仕事をしたことがわかります。作成されたアーカイブは、WinRar アーカイブより 1,3 ギガバイト、2,1z アーカイブより 7 ギガバイト小さくなりました。

アーカイブの作成に費やした時間:

• 7-zip – 26 分 10 秒。
• WinRar – 17 分 40 秒。
• RTT-Mid – 7 分 30 秒。

したがって、RTT-Mid アルゴリズムを使用した、最適化されていないテスト プログラムでも、アーカイブを 2.5 倍以上高速に作成できましたが、そのアーカイブは競合他社のプログラムよりも大幅に小さいことが判明しました。

スクリーンショットが信じられない人は、自分でスクリーンショットの信頼性を確認してください。テスト プログラムは次の場所から入手できます。 リンク, ダウンロードして確認してください。

ただし、AVX-2 をサポートするプロセッサ上でのみ、これらの命令をサポートしていないとコンプレッサーは機能せず、古い AMD プロセッサではアルゴリズムをテストしないため、AVX 命令の実行が遅くなります...

使用される圧縮方法

このアルゴリズムでは、繰り返されるテキストの断片をバイト粒度でインデックス化する方法が使用されます。この圧縮方法は古くから知られていましたが、必要なリソースの点で照合操作に非常にコストがかかり、辞書を構築するよりもはるかに長い時間を必要としたため、使用されませんでした。つまり、RTT-Mid アルゴリズムは「未来へ戻る」典型的な例です...

PTT コンプレッサーは独自の高速一致検索スキャナーを使用しており、これにより圧縮プロセスを高速化できます。自作スキャナー、これは「私の魅力です…」「完全手作りなので結構高価です」（アセンブラで書いています）。

一致検索スキャナは 2 レベルの確率スキームに従って作成されます。まず、一致の「兆候」の存在がスキャンされ、その「兆候」がその場所で特定された後にのみ、実際の一致を検出する手順が実行されます。が開始されます。

一致検索ウィンドウのサイズは、処理されたデータ ブロックのエントロピーの程度によって異なります。完全にランダムな (非圧縮) データの場合、サイズはメガバイトになりますが、繰り返しのあるデータの場合、サイズは常に 1 メガバイトより大きくなります。

しかし、最新のデータ形式の多くは非圧縮であり、それらを介してリソースを大量に消費するスキャナーを実行することは役に立たず無駄であるため、スキャナーは 4 つの動作モードを使用します。まず、ソース テキストの繰り返しの可能性のあるセクションが検索されますが、この操作も確率的方法を使用して実行され、非常に高速に (6 ～ XNUMX ギガバイト/秒の速度で) 実行されます。次に、一致する可能性のある領域がメイン スキャナによって処理されます。

インデックス圧縮はあまり効率的ではなく、重複したフラグメントをインデックスに置き換える必要があり、インデックス配列により圧縮率が大幅に低下します。

圧縮率を高めるために、バイト文字列の完全一致だけでなく、文字列に一致したバイトと一致しないバイトが含まれている場合は、部分的な一致にもインデックスが付けられます。これを行うために、インデックス形式には、2 つのブロックの一致するバイトを示す一致マスク フィールドが含まれています。さらに圧縮を高めるには、インデックス付けを使用して、部分的に一致するいくつかのブロックを現在のブロックに重ね合わせます。

これらすべてにより、PTT-Mid コンプレッサーでは、辞書方式を使用して作成されたコンプレッサーと同等の圧縮率を得ることが可能になり、しかも動作がはるかに高速になりました。

新しい圧縮アルゴリズムの速度

コンプレッサーがキャッシュ メモリを排他的に使用して動作する場合 (スレッドごとに 4 メガバイトが必要)、動作速度の範囲は 700 ～ 2000 メガバイト/秒になります。圧縮されるデータの種類に応じてプロセッサ コアごとに異なり、プロセッサの動作周波数にはほとんど依存しません。

コンプレッサーのマルチスレッド実装では、効果的なスケーラビリティは 9 番目のレベルのキャッシュのサイズによって決まります。たとえば、20 メガバイトのキャッシュ メモリが「オンボード」にある場合、XNUMX つ以上の圧縮スレッドを起動しても意味がなく、これによって速度は向上しません。ただし、XNUMX メガバイトのキャッシュがあれば、すでに XNUMX つの圧縮スレッドを実行できます。

また、RAM のレイテンシーもコンプレッサーの速度を決定する重要なパラメーターになります。このアルゴリズムでは OP へのランダム アクセスが使用されますが、その一部 (約 10%) はキャッシュ メモリに入らず、OP からのデータを待機してアイドル状態になる必要があるため、動作速度が低下します。

コンプレッサーの速度やデータ入出力システムの動作に大きく影響します。 I/O から OP へのリクエストは CPU からのデータのリクエストをブロックするため、圧縮速度も低下します。この問題は、ラップトップおよびデスクトップでは重大ですが、サーバーでは、より高度なシステム バス アクセス制御ユニットとマルチチャネル RAM のおかげで、それほど重大ではありません。

この記事の本文全体で圧縮について説明しますが、「すべてがチョコレートで覆われている」ため、解凍についてはこの記事の範囲外となります。解凍ははるかに高速ですが、I/O 速度によって制限されます。 3 つのスレッドに 4 つの物理コアを配置すると、XNUMX ～ XNUMX GB/秒の解凍速度が簡単に得られます。

これは、圧縮解除プロセス中に一致検索操作が行われないため、圧縮中にプロセッサとキャッシュ メモリの主要なリソースが「消費」されます。

圧縮データストレージの信頼性

データ圧縮を使用するソフトウェア (アーカイバ) のクラス全体の名前が示すように、それらは情報を何年もではなく、何世紀、何千年にもわたって長期保存できるように設計されています。

保管中に、ストレージ メディアは一部のデータを失います。例を次に示します。

この「アナログ」情報媒体は千年前のもので、一部の断片は失われていますが、一般的に情報は「読み取り可能」です...

最新のデジタル データ ストレージ システムとそのデジタル メディアの責任あるメーカーのどれも、75 年以上にわたって完全なデータの安全性を保証していません。
そして、これは問題ですが、先送りされた問題です、私たちの子孫がそれを解決します...

デジタル データ ストレージ システムは、75 年を経過するとデータが失われる可能性があるだけでなく、データのエラーはいつでも発生する可能性があり、記録中であっても、冗長性を使用し、エラー訂正システムで修正することで、これらの歪みを最小限に抑えようとします。冗長性および修正システムでは、失われた情報を常に復元できるとは限りません。また、復元できたとしても、復元操作が正しく完了したという保証はありません。

そして、これも大きな問題ですが、先送りの問題ではなく、現在の問題です。

デジタル データのアーカイブに使用される最新の圧縮プログラムは、辞書方式のさまざまな修正に基づいて構築されており、そのようなアーカイブにとって、情報の一部の損失は致命的な出来事になります。そのような状況を表す用語「壊れた」アーカイブさえ確立されています。 ...

辞書圧縮によるアーカイブ内の情報保存の信頼性の低さは、圧縮データの構造に関係しています。このようなアーカイブ内の情報にはソース テキストは含まれず、辞書内のエントリ数がそこに保存され、辞書自体は現在の圧縮テキストによって動的に変更されます。アーカイブ フラグメントが紛失または破損した場合、辞書エントリ番号が何に対応しているかが明確ではないため、後続のすべてのアーカイブ エントリは、内容または辞書内のエントリの長さによって識別できなくなります。

このような「壊れた」アーカイブから情報を復元することは不可能です。

RTT アルゴリズムは、圧縮データを保存するためのより信頼性の高い方法に基づいています。これは、繰り返しフラグメントを考慮するインデックス方法を使用します。この圧縮アプローチにより、記憶媒体上の情報の歪みによる影響を最小限に抑えることができ、多くの場合、情報の保存中に発生した歪みを自動的に修正できます。
これは、インデックス圧縮の場合のアーカイブ ファイルには次の 2 つのフィールドが含まれるためです。

• 繰り返しセクションが削除されたソース テキスト フィールド。
• インデックスフィールド。

情報の回復に重要なインデックス フィールドはサイズが大きくないため、信頼性の高いデータ ストレージのために複製することができます。したがって、たとえソーステキストまたはインデックス配列の断片が失われたとしても、「アナログ」記憶媒体の場合と同様に、他のすべての情報は問題なく復元されます。

アルゴリズムの欠点

デメリットのないメリットはありません。インデックス圧縮方法では、短い繰り返しシーケンスは圧縮されません。これはインデックス方式の制限によるものです。インデックスのサイズは少なくとも 3 バイト、最大 12 バイトです。繰り返しを説明するインデックスよりも小さいサイズの繰り返しが見つかった場合、圧縮ファイル内でそのような繰り返しがどれほど頻繁に検出されたとしても、その繰り返しは考慮されません。

従来の辞書圧縮方法は、短い長さの複数の繰り返しを効果的に圧縮するため、インデックス圧縮よりも高い圧縮率を実現します。確かに、これは中央プロセッサの負荷が高いために達成されます。辞書方式でインデックス方式よりも効率的にデータの圧縮を開始するには、実際のデータ処理速度を 10 秒あたり 20 ～ XNUMX メガバイトに下げる必要があります。 CPU にフル負荷がかかるコンピューティング インストール。

このような低速は現代のデータ ストレージ システムには受け入れられず、実用的というよりも「学術的」な関心が高まっています。

すでに開発中の RTT アルゴリズム (RTT-Max) の次の修正では、情報圧縮の度合いが大幅に向上します。

ということで、いつものように続きは・・・

出所： habr.com