Ta članek je že drugi na temo hitrega stiskanja podatkov. Prvi članek opisuje kompresor, ki deluje s hitrostjo 10 GB/s. na procesorsko jedro (minimalna kompresija, RTT-Min).
Ta kompresor je bil že implementiran v opremo forenzičnih razmnoževalcev za visokohitrostno stiskanje izpisov pomnilniških medijev in izboljšanje moči kriptografije; lahko se uporablja tudi za stiskanje slik virtualnih strojev in izmenjevalnih datotek RAM, ko jih shranjujete pri visoki hitrosti. SSD diski.
Prvi članek je napovedal tudi razvoj kompresijskega algoritma za stiskanje varnostnih kopij HDD in SSD diskov (srednje stiskanje, RTT-Mid) z bistveno izboljšanimi parametri stiskanja podatkov. Do zdaj je ta kompresor popolnoma pripravljen in ta članek govori o tem.
Kompresor, ki izvaja algoritem RTT-Mid, zagotavlja kompresijsko razmerje, primerljivo s standardnimi arhivatorji, kot sta WinRar, 7-Zip, ki delujejo v hitrem načinu. Hkrati je njegova hitrost delovanja vsaj za red velikosti višja.
Hitrost pakiranja/razpakiranja podatkov je kritičen parameter, ki določa obseg uporabe tehnologij stiskanja. Malo verjetno je, da bi komu prišlo na misel, da bi stisnil terabajt podatkov s hitrostjo 10-15 megabajtov na sekundo (natančno to je hitrost arhivarjev v standardnem načinu stiskanja), saj bi to ob polni obremenitvi procesorja trajalo skoraj dvajset ur. .
Po drugi strani pa je mogoče isti terabajt kopirati s hitrostjo reda 2-3 gigabajtov na sekundo v približno desetih minutah.
Zato je stiskanje obsežnih informacij pomembno, če se izvaja s hitrostjo, ki ni nižja od hitrosti realnega vhoda/izhoda. Za sodobne sisteme je to najmanj 100 megabajtov na sekundo.
Sodobni kompresorji lahko ustvarijo takšne hitrosti samo v "hitrem" načinu. V tem trenutnem načinu bomo primerjali algoritem RTT-Mid s tradicionalnimi kompresorji.
Primerjalno testiranje novega algoritma stiskanja
Kompresor RTT-Mid je deloval kot del testnega programa. V pravi "delujoči" aplikaciji deluje veliko hitreje, pametno uporablja večnitnost in uporablja "običajen" prevajalnik, ne C#.
Ker so uporabljeni kompresorji v primerjalnem testu zgrajeni na različnih principih in se različni tipi podatkov različno stiskajo, je bila za objektivnost testa uporabljena metoda merjenja “povprečne temperature v bolnišnici”...
Ustvarjena je bila sektorsko-sektorska dump datoteka logičnega diska z operacijskim sistemom Windows 10, ki je najbolj naravna mešanica različnih podatkovnih struktur, ki je dejansko na voljo na vsakem računalniku. Stiskanje te datoteke vam bo omogočilo primerjavo hitrosti in stopnje stiskanja novega algoritma z najnaprednejšimi kompresorji, ki se uporabljajo v sodobnih arhivarjih.
Tukaj je datoteka izpisa:
Datoteka izpisa je bila stisnjena s kompresorji PTT-Mid, 7-zip in WinRar. WinRar in kompresor 7-zip sta bila nastavljena na največjo hitrost.
Kompresor deluje 7-zip:
Obremeni procesor za 100%, medtem ko je povprečna hitrost branja originalnega dumpa približno 60 megabajtov/s.
Kompresor deluje WinRAR:
Situacija je podobna, obremenitev procesorja je skoraj 100%, povprečna hitrost branja dumpa je približno 125 megabajtov / sekundo.
Tako kot v prejšnjem primeru je hitrost arhivarja omejena z zmogljivostmi procesorja.
Testni program kompresorja se zdaj izvaja RTT-sredina:
Posnetek zaslona kaže, da je procesor obremenjen na 50%, preostali čas pa miruje, ker stisnjenih podatkov ni kam naložiti. Disk za nalaganje podatkov (Disk 0) je skoraj v celoti naložen. Hitrost branja podatkov (Disk 1) je zelo različna, vendar v povprečju več kot 200 megabajtov/sek.
Hitrost kompresorja je v tem primeru omejena z možnostjo zapisovanja stisnjenih podatkov na disk 0.
Zdaj pa kompresijsko razmerje nastalih arhivov:
Vidimo, da je kompresor RTT-Mid najbolje opravil stiskanje; arhiv, ki ga je ustvaril, je bil za 1,3 Gigabajta manjši od arhiva WinRar in za 2,1 Gigabajta manjši od arhiva 7z.
Čas, porabljen za ustvarjanje arhiva:
- 7-zip – 26 minut 10 sekund;
- WinRar – 17 minut 40 sekund;
- RTT-Mid – 7 minut 30 sekund.
Tako je tudi testni, neoptimizirani program z algoritmom RTT-Mid uspel ustvariti arhiv več kot dvainpolkrat hitreje, arhiv pa se je izkazal za bistveno manjšega kot pri konkurentih...
Kdor posnetkom zaslona ne verjame, lahko sam preveri njihovo pristnost. Testni program je na voljo na , prenesite in preverite.
Ampak samo na procesorjih s podporo AVX-2, brez podpore za ta navodila kompresor ne deluje, na starejših procesorjih AMD pa ne testiraj algoritma, so počasni glede izvajanja navodil AVX...
Uporabljena metoda stiskanja
Algoritem uporablja metodo za indeksiranje ponovljenih fragmentov besedila v zrnatosti bajtov. Ta metoda stiskanja je poznana že dolgo, vendar se ni uporabljala, ker je bila operacija ujemanja zelo draga glede na potrebna sredstva in je zahtevala veliko več časa kot izdelava slovarja. Torej je algoritem RTT-Mid klasičen primer premikanja "nazaj v prihodnost" ...
Kompresor PTT uporablja edinstven hitri skener za iskanje ujemanja, ki nam omogoča pospešitev postopka stiskanja. Sam izdelan skener, to je "moj čar ...", "precej drago je, ker je popolnoma ročno izdelano" (napisano v asemblerju).
Skener za iskanje ujemanja je izdelan po dvonivojski verjetnostni shemi: najprej se skenira prisotnost "znaka" ujemanja in šele potem, ko je "znak" identificiran na tem mestu, se začne postopek za odkrivanje pravega ujemanja. se začne.
Ujemajoče se okno ima nepredvidljivo velikost, odvisno od stopnje entropije v obdelanem bloku podatkov. Za povsem naključne (nestisljive) podatke ima velikost megabajtov, za podatke s ponovitvami pa je vedno večja od megabajta.
Vendar je veliko sodobnih podatkovnih formatov nestisljivih in izvajanje skenerja, ki zahteva veliko virov, je neuporabno in potratno, zato skener uporablja dva načina delovanja. Najprej se preiščejo deli izvornega besedila z možnimi ponovitvami; ta operacija se prav tako izvaja z verjetnostno metodo in se izvaja zelo hitro (s hitrostjo 4-6 GigaBytes/s). Območja z možnimi ujemanji se nato obdelajo z glavnim skenerjem.
Indeksno stiskanje ni zelo učinkovito, podvojene fragmente morate zamenjati z indeksi, indeksni niz pa bistveno zmanjša kompresijsko razmerje.
Za povečanje kompresijskega razmerja se ne indeksirajo samo popolna ujemanja bajtnih nizov, temveč tudi delna, ko niz vsebuje ujemajoče se in neujemajoče se bajte. Da bi to naredili, oblika indeksa vključuje polje maske ujemanja, ki označuje ujemanje bajtov dveh blokov. Za še večjo kompresijo se uporablja indeksiranje za prekrivanje več delno ujemajočih se blokov na trenutni blok.
Vse to je omogočilo kompresorju PTT-Mid doseči kompresijsko razmerje, ki je primerljivo s kompresorji, izdelanimi po slovarski metodi, vendar deluje veliko hitreje.
Hitrost novega algoritma stiskanja
Če kompresor deluje z izključno uporabo predpomnilnika (potrebni so 4 megabajti na nit), se hitrost delovanja giblje od 700-2000 megabajtov/s. na procesorsko jedro, odvisno od vrste podatkov, ki se stisnejo in je malo odvisno od delovne frekvence procesorja.
Pri večnitni izvedbi kompresorja je učinkovita razširljivost določena z velikostjo predpomnilnika tretje ravni. Na primer, če imate na krovu 9 megabajtov predpomnilnika, nima smisla zagnati več kot dveh niti stiskanja; hitrost se zaradi tega ne bo povečala. Toda s predpomnilnikom velikosti 20 megabajtov lahko že izvajate pet niti stiskanja.
Tudi zakasnitev RAM-a postane pomemben parameter, ki določa hitrost kompresorja. Algoritem uporablja naključni dostop do OP, od katerih nekateri ne pridejo v predpomnilnik (približno 10%) in mora mirovati, čakajoč na podatke iz OP, kar zmanjša hitrost delovanja.
Bistveno vpliva na hitrost kompresorja in delovanje vhodno/izhodnega sistema podatkov. Zahteve za OP iz I/O blokirajo zahteve za podatke iz CPE, kar prav tako zmanjša hitrost stiskanja. Ta težava je pomembna za prenosnike in namizne računalnike; za strežnike je manj pomembna zaradi naprednejše enote za nadzor dostopa do sistemskega vodila in večkanalnega RAM-a.
Skozi celotno besedilo v članku govorimo o kompresiji, dekompresija pa ostaja izven obsega tega članka, saj je »vse v čokoladi«. Dekompresija je veliko hitrejša in je omejena s hitrostjo I/O. Eno fizično jedro v eni niti zlahka zagotavlja hitrosti razpakiranja 3–4 GB/s.
To je posledica odsotnosti operacije iskanja ujemanja med postopkom dekompresije, ki med stiskanjem »požre« glavne vire procesorja in predpomnilnika.
Zanesljivost shranjevanja stisnjenih podatkov
Kot pove že ime celotnega razreda programske opreme, ki uporablja stiskanje podatkov (arhiverji), so ti namenjeni dolgoročnemu shranjevanju informacij, ne več let, temveč stoletja in tisočletja ...
Med shranjevanjem mediji za shranjevanje izgubijo nekaj podatkov, tukaj je primer:
Ta »analogni« nosilec informacij je star tisoč let, nekaj drobcev je izgubljenih, a na splošno so informacije »berljive« ...
Nobeden od odgovornih proizvajalcev sodobnih sistemov za shranjevanje digitalnih podatkov in digitalnih medijev zanje ne zagotavlja garancije popolne varnosti podatkov več kot 75 let.
In to je problem, a odložen problem, rešili ga bodo naši zanamci...
Digitalni sistemi za shranjevanje podatkov lahko izgubijo podatke ne šele po 75 letih, napake v podatkih se lahko pojavijo kadarkoli, tudi med njihovim zapisom, ta popačenja skušajo zmanjšati z uporabo redundance in jih popraviti s sistemi za odpravljanje napak. Sistemi redundance in popravkov ne morejo vedno obnoviti izgubljenih informacij, in če jih, ni nobenega zagotovila, da je bila operacija obnovitve pravilno zaključena.
In tudi to je velik problem, a ne odložen, ampak trenuten.
Sodobni kompresorji, ki se uporabljajo za arhiviranje digitalnih podatkov, so zgrajeni na različnih modifikacijah slovarske metode in za take arhive bo izguba podatka usoden dogodek, za takšno situacijo obstaja celo uveljavljen izraz - »pokvarjen« arhiv. ...
Nizka zanesljivost shranjevanja informacij v arhivih s stiskanjem slovarjev je povezana s strukturo stisnjenih podatkov. Informacije v takem arhivu ne vsebujejo izvornega besedila, tam so shranjene številke vnosov v slovarju, sam slovar pa se dinamično spreminja s trenutnim stisnjenim besedilom. Če se arhivski fragment izgubi ali poškoduje, vseh nadaljnjih arhivskih vnosov ni mogoče identificirati ne po vsebini ne po dolžini vnosa v slovarju, saj ni jasno, čemu ustreza številka slovarskega vnosa.
Podatkov iz tako "pokvarjenega" arhiva ni mogoče obnoviti.
Algoritem RTT temelji na zanesljivejši metodi shranjevanja stisnjenih podatkov. Uporablja metodo indeksa za upoštevanje ponavljajočih se fragmentov. Ta pristop k stiskanju nam omogoča, da zmanjšamo posledice popačenja informacij na pomnilniškem mediju in v mnogih primerih samodejno popravimo popačenja, ki nastanejo med shranjevanjem informacij.
To je posledica dejstva, da arhivska datoteka v primeru stiskanja indeksa vsebuje dve polji:
- izvorno besedilno polje z odstranjenimi ponavljajočimi se odseki;
- indeksno polje.
Indeksno polje, ki je ključnega pomena za obnovitev informacij, ni veliko in ga je mogoče podvojiti za zanesljivo shranjevanje podatkov. Torej, tudi če se izgubi del izvornega besedila ali indeksnega polja, bodo vse druge informacije brez težav obnovljene, kot na sliki z "analognim" medijem za shranjevanje.
Slabosti algoritma
Ni prednosti brez slabosti. Metoda stiskanja indeksa ne stisne kratkih ponavljajočih se zaporedij. To je posledica omejitev indeksne metode. Indeksi so veliki vsaj 3 bajte in so lahko veliki do 12 bajtov. Če se pojavi ponovitev, ki je manjša od indeksa, ki jo opisuje, se ne upošteva, ne glede na to, kako pogosto so takšne ponovitve zaznane v stisnjeni datoteki.
Tradicionalna metoda stiskanja slovarja učinkovito stisne več ponovitev kratke dolžine in tako doseže višje razmerje stiskanja kot stiskanje indeksa. Res je, da je to doseženo zaradi velike obremenitve osrednjega procesorja; da bi slovarska metoda začela bolj učinkovito stiskati podatke kot indeksna metoda, mora zmanjšati hitrost obdelave podatkov na 10-20 megabajtov na sekundo v realnem računalniške instalacije s polno obremenitvijo procesorja.
Tako nizke hitrosti so nesprejemljive za sodobne sisteme za shranjevanje podatkov in so bolj "akademskega" interesa kot praktičnega.
Stopnja kompresije informacij bo bistveno povečana v naslednji modifikaciji algoritma RTT (RTT-Max), ki je že v razvoju.
Torej, kot vedno, se nadaljuje ...
Vir: www.habr.com