Tento článek je již druhým v tématu vysokorychlostní komprese dat. První článek popisoval kompresor pracující rychlostí 10 GB/s. na jádro procesoru (minimální komprese, RTT-Min).
Tento kompresor byl již implementován do vybavení forenzních duplikátorů pro vysokorychlostní kompresi výpisů paměťových médií a zvýšení síly kryptografie, lze jej také použít pro kompresi obrazů virtuálních strojů a odkládacích souborů RAM při jejich ukládání na vysokorychlostní SSD disky.
První článek také oznámil vývoj kompresního algoritmu pro kompresi záložních kopií HDD a SSD disků (střední komprese, RTT-Mid) s výrazně vylepšenými parametry komprese dat. Nyní je tento kompresor zcela připraven a tento článek je o něm.
Kompresor, který implementuje algoritmus RTT-Mid, poskytuje kompresní poměr srovnatelný se standardními archivátory, jako je WinRar, 7-Zip, pracující ve vysokorychlostním režimu. Jeho provozní rychlost je přitom minimálně o řád vyšší.
Rychlost sbalení/rozbalení dat je kritickým parametrem, který určuje rozsah použití kompresních technologií. Je nepravděpodobné, že by někoho napadlo komprimovat terabajt dat rychlostí 10-15 MegaBytes za sekundu (to je přesně rychlost archivátorů ve standardním režimu komprese), protože by to při plné zátěži procesoru trvalo téměř dvacet hodin. .
Na druhou stranu lze stejný terabajt kopírovat rychlostí řádově 2–3 GB za sekundu za zhruba deset minut.
Proto je komprese velkoobjemových informací důležitá, pokud se provádí rychlostí ne nižší, než je rychlost skutečného vstupu/výstupu. U moderních systémů je to alespoň 100 megabajtů za sekundu.
Moderní kompresory mohou produkovat takové rychlosti pouze v „rychlém“ režimu. Právě v tomto aktuálním režimu porovnáme algoritmus RTT-Mid s tradičními kompresory.
Srovnávací testování nového kompresního algoritmu
Kompresor RTT-Mid fungoval jako součást testovacího programu. Ve skutečné „pracovní“ aplikaci funguje mnohem rychleji, moudře používá multithreading a používá „normální“ kompilátor, nikoli C#.
Jelikož kompresory použité ve srovnávacím testu jsou postaveny na jiných principech a různé typy dat různě komprimují, byla pro objektivitu testu použita metoda měření „průměrné teploty v nemocnici“...
Byl vytvořen sektorový soubor výpisu logického disku s operačním systémem Windows 10, což je nejpřirozenější směs různých datových struktur, která je skutečně dostupná na každém počítači. Komprese tohoto souboru vám umožní porovnat rychlost a stupeň komprese nového algoritmu s nejpokročilejšími kompresory používanými v moderních archivátorech.
Zde je soubor výpisu:
Soubor výpisu byl komprimován pomocí kompresorů PTT-Mid, 7-zip a WinRar. WinRar a 7-zip kompresor byly nastaveny na maximální rychlost.
Kompresor běží 7-zip:
Zatěžuje procesor na 100 %, přičemž průměrná rychlost čtení původního výpisu je asi 60 MegaBytes/sec.
Kompresor běží WinRAR:
Situace je podobná, vytížení procesoru je téměř 100%, průměrná rychlost čtení výpisu je cca 125 Megabajtů/sec.
Stejně jako v předchozím případě je rychlost archivátoru omezena možnostmi procesoru.
Nyní běží testovací program kompresoru RTT-střed:
Screenshot ukazuje, že procesor je zatížen na 50 % a po zbytek času je nečinný, protože komprimovaná data není kam nahrát. Disk pro nahrávání dat (Disk 0) je téměř plně nabitý. Rychlost čtení dat (Disk 1) se značně liší, ale v průměru více než 200 megabajtů/s.
Rychlost kompresoru je v tomto případě omezena schopností zapisovat komprimovaná data na Disk 0.
Nyní kompresní poměr výsledných archivů:
Je vidět, že kompresor RTT-Mid odvedl kompresi nejlépe, archiv, který vytvořil, byl o 1,3 GigaBytu menší než archiv WinRar a o 2,1 GigaBytu menší než archiv 7z.
Čas strávený vytvářením archivu:
- 7-zip – 26 minut 10 sekund;
- WinRar – 17 minut 40 sekund;
- RTT-Mid – 7 minut 30 sekund.
I testovací, neoptimalizovaný program, využívající algoritmus RTT-Mid, tedy dokázal vytvořit archiv více než dvaapůlkrát rychleji, přičemž se ukázalo, že archiv je výrazně menší než u jeho konkurentů...
Kdo screenshotům nevěří, může si jejich pravost ověřit sám. Testovací program je k dispozici na , stáhnout a zkontrolovat.
Ale pouze na procesorech s podporou AVX-2, bez podpory těchto instrukcí kompresor nefunguje a algoritmus netestujte na starších procesorech AMD, ty jsou pomalé z hlediska provádění instrukcí AVX...
Použitá kompresní metoda
Algoritmus používá metodu pro indexování opakovaných textových fragmentů v bajtové granularitě. Tato metoda komprese je známá již dlouhou dobu, ale nebyla použita, protože operace párování byla velmi nákladná z hlediska potřebných zdrojů a vyžadovala mnohem více času než vytvoření slovníku. Algoritmus RTT-Mid je tedy klasickým příkladem pohybu „zpět do budoucnosti“...
Kompresor PTT využívá unikátní vysokorychlostní skener vyhledávání shody, který nám umožňuje urychlit proces komprese. Vlastnoručně vyrobený skener, to je „moje kouzlo...“, „je to docela drahé, protože je to úplně ruční práce“ (napsáno v assembleru).
Skener vyhledávání shody je vyroben podle dvouúrovňového pravděpodobnostního schématu: nejprve se naskenuje přítomnost „znaku“ shody a teprve poté, co je na tomto místě identifikován „znak“, postup detekce skutečné shody je spuštěno.
Okno vyhledávání shody má nepředvídatelnou velikost v závislosti na stupni entropie ve zpracovávaném datovém bloku. U zcela náhodných (nestlačitelných) dat má velikost megabajtů, u dat s opakováním je vždy větší než megabajt.
Ale mnoho moderních datových formátů je nestlačitelných a provozovat přes ně skener náročný na zdroje je zbytečné a plýtvání, takže skener používá dva provozní režimy. Nejprve se prohledají úseky zdrojového textu s možnými opakováními, tato operace je rovněž provedena pravděpodobnostní metodou a je provedena velmi rychle (rychlostí 4-6 GigaBytes/s). Oblasti s případnými shodami jsou pak zpracovány hlavním skenerem.
Komprese indexu není příliš efektivní, duplicitní fragmenty musíte nahradit indexy a pole indexů výrazně snižuje kompresní poměr.
Pro zvýšení kompresního poměru se indexují nejen úplné shody bajtových řetězců, ale i částečné, kdy řetězec obsahuje shodné a neshodné bajty. Za tímto účelem obsahuje formát indexu pole masky shody, které označuje odpovídající bajty dvou bloků. Pro ještě větší kompresi se indexování používá k superponování několika částečně shodných bloků na aktuální blok.
To vše umožnilo získat v kompresoru PTT-Mid kompresní poměr srovnatelný s kompresory vyrobenými pomocí slovníkové metody, ale pracující mnohem rychleji.
Rychlost nového kompresního algoritmu
Pokud kompresor pracuje s výhradním využitím mezipaměti (jsou vyžadovány 4 MB na vlákno), pak se provozní rychlost pohybuje v rozmezí 700-2000 MB/s. na jádro procesoru, v závislosti na typu komprimovaných dat a málo závisí na provozní frekvenci procesoru.
S vícevláknovou implementací kompresoru je efektivní škálovatelnost určena velikostí mezipaměti třetí úrovně. Například s 9 megabajty vyrovnávací paměti „na desce“ nemá smysl spouštět více než dvě kompresní vlákna; rychlost se z toho nezvýší. Ale s mezipamětí 20 megabajtů už můžete spustit pět kompresních vláken.
Také latence RAM se stává důležitým parametrem, který určuje rychlost kompresoru. Algoritmus využívá náhodný přístup k OP, z nichž některé se nedostanou do vyrovnávací paměti (cca 10%) a musí nečinně čekat na data z OP, což snižuje rychlost provozu.
Výrazně ovlivňuje rychlost kompresoru a provoz systému vstupu/výstupu dat. Požadavky na OP z I/O blokují požadavky na data z CPU, což také snižuje rychlost komprese. Tento problém je významný u notebooků a stolních počítačů, u serverů je méně významný kvůli pokročilejší jednotce řízení přístupu k systémové sběrnici a vícekanálové paměti RAM.
V celém textu v článku mluvíme o kompresi, dekomprese zůstává mimo rozsah tohoto článku, protože „všechno je pokryto čokoládou“. Dekomprese je mnohem rychlejší a je omezena rychlostí I/O. Jedno fyzické jádro v jednom vláknu snadno poskytuje rychlost rozbalování 3-4 GB/s.
To je způsobeno absencí operace vyhledávání shody během procesu dekomprese, která během komprimace „požírá“ hlavní zdroje procesoru a mezipaměti.
Spolehlivost úložiště komprimovaných dat
Jak už název celé třídy software, který využívá kompresi dat (archivátory) napovídá, jsou určeny pro dlouhodobé uchovávání informací nikoli na roky, ale na staletí a tisíciletí...
Během ukládání ztrácejí paměťová média některá data, zde je příklad:
Tento „analogový“ nosič informací je starý tisíc let, některé fragmenty se ztratily, ale obecně jsou informace „čitelné“...
Žádný z odpovědných výrobců moderních systémů pro ukládání digitálních dat a digitálních médií pro ně neposkytuje záruky úplné bezpečnosti dat po dobu delší než 75 let.
A to je problém, ale odložený problém, naši potomci to vyřeší...
Digitální systémy pro ukládání dat mohou ztratit data nejen po 75 letech, chyby v datech se mohou objevit kdykoli, dokonce i během jejich záznamu, snaží se tato zkreslení minimalizovat pomocí redundance a korigovat je pomocí systémů pro opravu chyb. Redundantní a opravné systémy nemohou vždy obnovit ztracené informace, a pokud ano, neexistuje žádná záruka, že operace obnovy byla dokončena správně.
A to je také velký problém, ale ne odložený, ale aktuální.
Moderní kompresory používané pro archivaci digitálních dat jsou postaveny na různých modifikacích slovníkové metody a pro takové archivy bude ztráta informace fatální událostí, pro takovou situaci existuje dokonce zažitý termín - „rozbitý“ archiv ...
Nízká spolehlivost ukládání informací do archivů se slovníkovou kompresí souvisí se strukturou komprimovaných dat. Informace v takovém archivu neobsahují zdrojový text, jsou tam uloženy počty záznamů ve slovníku a samotný slovník je dynamicky upravován aktuálním komprimovaným textem. Pokud dojde ke ztrátě nebo poškození fragmentu archivu, nelze všechny následující položky archivu identifikovat ani podle obsahu, ani podle délky položky ve slovníku, protože není jasné, čemu odpovídá číslo položky ve slovníku.
Z takto „rozbitého“ archivu není možné obnovit informace.
Algoritmus RTT je založen na spolehlivější metodě ukládání komprimovaných dat. Používá indexovou metodu účtování opakujících se fragmentů. Tento přístup ke kompresi umožňuje minimalizovat důsledky zkreslení informací na paměťovém médiu a v mnoha případech automaticky korigovat zkreslení, která vznikla při ukládání informací.
To je způsobeno skutečností, že archivní soubor v případě komprese indexu obsahuje dvě pole:
- zdrojové textové pole s odstraněnými částmi opakování;
- pole indexu.
Pole indexu, které je kritické pro obnovu informací, není velké a lze jej duplikovat pro spolehlivé ukládání dat. Proto, i když dojde ke ztrátě fragmentu zdrojového textu nebo indexového pole, všechny ostatní informace budou obnoveny bez problémů, jako na obrázku s „analogovým“ paměťovým médiem.
Nevýhody algoritmu
Neexistují žádné výhody bez nevýhod. Metoda komprese indexu nekomprimuje krátké opakující se sekvence. To je způsobeno omezeními metody indexu. Indexy mají velikost alespoň 3 bajty a mohou mít velikost až 12 bajtů. Pokud dojde k opakování s menší velikostí, než je index, který jej popisuje, pak se nebere v úvahu, bez ohledu na to, jak často jsou taková opakování v komprimovaném souboru detekována.
Tradiční metoda slovníkové komprese efektivně komprimuje více opakování krátké délky, a proto dosahuje vyššího kompresního poměru než indexová komprese. Je pravda, že toho je dosaženo díky vysoké zátěži centrálního procesoru; aby slovníková metoda začala komprimovat data efektivněji než indexová metoda, musí snížit rychlost zpracování dat na 10-20 megabajtů za sekundu na reálném výpočetní instalace s plnou zátěží CPU.
Tak nízké rychlosti jsou pro moderní systémy ukládání dat nepřijatelné a jsou spíše „akademickým“ než praktickým.
Stupeň komprese informací bude výrazně zvýšen v další modifikaci algoritmu RTT (RTT-Max), která je již ve vývoji.
Takže jako vždy pokračování...
Zdroj: www.habr.com