Acest articol este deja al doilea în subiectul compresiei de mare viteză a datelor. Primul articol descria un compresor care funcționează la o viteză de 10 GB/sec. per nucleu de procesor (compresie minimă, RTT-Min).
Acest compresor a fost deja implementat în echipamentele duplicatoarelor criminalistice pentru comprimarea de mare viteză a depozitelor de medii de stocare și îmbunătățirea puterii criptografiei; poate fi, de asemenea, utilizat pentru comprimarea imaginilor mașinilor virtuale și a fișierelor de schimb RAM atunci când le salvează pe viteză mare. Unități SSD.
Primul articol a anunțat și dezvoltarea unui algoritm de compresie pentru comprimarea copiilor de rezervă ale unităților de disc HDD și SSD (compresie medie, RTT-Mid) cu parametrii de compresie a datelor îmbunătățiți semnificativ. Până acum, acest compresor este complet gata și acest articol este despre el.
Un compresor care implementează algoritmul RTT-Mid oferă un raport de compresie comparabil cu arhivele standard, cum ar fi WinRar, 7-Zip, care funcționează în modul de mare viteză. În același timp, viteza sa de funcționare este cu cel puțin un ordin de mărime mai mare.
Viteza de împachetare/despachetare a datelor este un parametru critic care determină domeniul de aplicare al tehnologiilor de compresie. Este puțin probabil ca cineva să se gândească la comprimarea unui terabyte de date cu o viteză de 10-15 megaocteți pe secundă (aceasta este exact viteza arhivelor în modul de compresie standard), deoarece ar dura aproape douăzeci de ore cu o încărcare completă a procesorului. .
Pe de altă parte, același terabyte poate fi copiat la viteze de ordinul a 2-3 gigaocteți pe secundă în aproximativ zece minute.
Prin urmare, compresia informațiilor de volum mare este importantă dacă este efectuată la o viteză nu mai mică decât viteza de intrare/ieșire reală. Pentru sistemele moderne, aceasta este de cel puțin 100 de megaocteți pe secundă.
Compresoarele moderne pot produce astfel de viteze numai în modul „rapid”. În acest mod curent vom compara algoritmul RTT-Mid cu compresoarele tradiționale.
Testarea comparativă a unui nou algoritm de compresie
Compresorul RTT-Mid a funcționat ca parte a programului de testare. Într-o aplicație „funcțională” reală funcționează mult mai rapid, folosește multithreading cu înțelepciune și folosește un compilator „normal”, nu C#.
Întrucât compresoarele folosite în testul comparativ sunt construite pe principii diferite și diferite tipuri de date se comprimă diferit, pentru obiectivitatea testului s-a folosit metoda de măsurare a „temperaturii medii în spital”...
A fost creat un fișier dump sector cu sector al unui disc logic cu sistemul de operare Windows 10; acesta este cel mai natural amestec de diferite structuri de date disponibile efectiv pe fiecare computer. Comprimarea acestui fișier vă va permite să comparați viteza și gradul de compresie al noului algoritm cu cele mai avansate compresoare utilizate în arhivatoarele moderne.
Iată fișierul dump:
Fișierul dump a fost comprimat folosind compresoare PTT-Mid, 7-zip și WinRar. WinRar și compresorul cu 7 zip au fost setate la viteza maximă.
Compresorul in functiune 7-zip:
Încarcă procesorul cu 100%, în timp ce viteza medie de citire a documentului original este de aproximativ 60 Megaocteți/sec.
Compresorul in functiune WinRar:
Situația este similară, încărcarea procesorului este de aproape 100%, viteza medie de citire a dump-ului este de aproximativ 125 Megaocteți/sec.
Ca și în cazul precedent, viteza arhivatorului este limitată de capacitățile procesorului.
Programul de testare a compresorului rulează acum RTT-Mid:
Captura de ecran arată că procesorul este încărcat la 50% și este inactiv în restul timpului, deoarece nu există unde să încărcați datele comprimate. Discul de încărcare a datelor (Disc 0) este aproape complet încărcat. Viteza de citire a datelor (Disc 1) variază foarte mult, dar în medie mai mult de 200 MegaBytes/sec.
Viteza compresorului este limitată în acest caz de capacitatea de a scrie date comprimate pe discul 0.
Acum raportul de compresie al arhivelor rezultate:
Se poate observa că compresorul RTT-Mid a făcut cea mai bună treabă de compresie; arhiva creată a fost cu 1,3 GigaBytes mai mică decât arhiva WinRar și cu 2,1 GigaBytes mai mică decât arhiva 7z.
Timpul petrecut creând arhiva:
- 7-zip – 26 minute 10 secunde;
- WinRar – 17 minute și 40 de secunde;
- RTT-Mid – 7 minute și 30 de secunde.
Astfel, chiar și un program de testare, neoptimizat, folosind algoritmul RTT-Mid, a fost capabil să creeze o arhivă de peste două ori și jumătate mai rapid, în timp ce arhiva s-a dovedit a fi semnificativ mai mică decât cea a concurenților săi...
Cei care nu cred capturile de ecran își pot verifica ei înșiși autenticitatea. Programul de testare este disponibil la , descărcați și verificați.
Dar numai pe procesoarele cu suport AVX-2, fără suport pentru aceste instrucțiuni compresorul nu funcționează și nu testați algoritmul pe procesoarele AMD mai vechi, sunt lente în ceea ce privește executarea instrucțiunilor AVX...
Metoda de compresie utilizată
Algoritmul folosește o metodă de indexare a fragmentelor de text repetate în granularitate de octeți. Această metodă de compresie este cunoscută de mult timp, dar nu a fost folosită deoarece operația de potrivire a fost foarte costisitoare în ceea ce privește resursele necesare și a necesitat mult mai mult timp decât construirea unui dicționar. Deci algoritmul RTT-Mid este un exemplu clasic de mutare „înapoi în viitor”...
Compresorul PTT folosește un scaner unic de căutare a potrivirilor de mare viteză, care ne permite să accelerăm procesul de compresie. Un scaner făcut de sine, acesta este „farmecul meu...”, „este destul de scump, pentru că este complet manual” (scris în asamblator).
Scanerul de căutare a potrivirii este realizat conform unei scheme probabilistice cu două nivele: în primul rând, este scanată prezența unui „semn” al unei potriviri și numai după ce „semnul” este identificat în acest loc, procedura de detectare a unei potriviri reale este pornit.
Fereastra de căutare a potrivirii are o dimensiune imprevizibilă, în funcție de gradul de entropie din blocul de date procesat. Pentru datele complet aleatorii (incompresibile) are o dimensiune de megaocteți, pentru datele cu repetări este întotdeauna mai mare decât un megaoctet.
Dar multe formate de date moderne sunt incompresibile și rularea unui scaner cu resurse intensive prin ele este inutilă și risipitoare, astfel încât scanerul folosește două moduri de operare. În primul rând, se caută secțiuni din textul sursă cu posibile repetări; această operație se efectuează, de asemenea, folosind o metodă probabilistică și se realizează foarte rapid (cu o viteză de 4-6 GigaBytes/sec). Zonele cu posibile potriviri sunt apoi procesate de scanerul principal.
Comprimarea indexului nu este foarte eficientă, trebuie să înlocuiți fragmentele duplicate cu indici, iar matricea indexului reduce semnificativ raportul de compresie.
Pentru a crește raportul de compresie, nu sunt indexate doar potrivirile complete ale șirurilor de octeți, ci și cele parțiale, atunci când șirul conține octeți potriviți și nepotriviți. Pentru a face acest lucru, formatul de index include un câmp de masca de potrivire care indică octeții potriviți ai două blocuri. Pentru o compresie și mai mare, indexarea este utilizată pentru a suprapune mai multe blocuri care se potrivesc parțial pe blocul curent.
Toate acestea au făcut posibilă obținerea în compresorul PTT-Mid a unui raport de compresie comparabil cu compresoarele realizate prin metoda dicționarului, dar funcționând mult mai rapid.
Viteza noului algoritm de compresie
Dacă compresorul funcționează cu utilizarea exclusivă a memoriei cache (sunt necesari 4 Megaocteți per fir), atunci viteza de funcționare variază între 700-2000 Megaocteți/sec. pe nucleu de procesor, în funcție de tipul de date care sunt comprimate și depinde puțin de frecvența de funcționare a procesorului.
Cu o implementare multi-threaded a compresorului, scalabilitatea efectivă este determinată de dimensiunea cache-ului de al treilea nivel. De exemplu, având 9 Megaocteți de memorie cache „la bord”, nu are rost să lansați mai mult de două fire de compresie; viteza nu va crește din aceasta. Dar cu un cache de 20 de megaocteți, puteți rula deja cinci fire de comprimare.
De asemenea, latența RAM devine un parametru important care determină viteza compresorului. Algoritmul folosește acces aleatoriu la OP, dintre care unele nu intră în memoria cache (aproximativ 10%) și trebuie să fie inactiv, așteptând date din OP, ceea ce reduce viteza de operare.
Afectează semnificativ viteza compresorului și funcționarea sistemului de intrare/ieșire a datelor. Solicitările către OP din blocul I/O solicită date de la CPU, ceea ce reduce și viteza de compresie. Această problemă este semnificativă pentru laptopuri și desktop-uri; pentru servere este mai puțin semnificativă datorită unei unități de control al accesului magistralei de sistem mai avansate și RAM multicanal.
În tot textul din articol vorbim despre compresie; decompresia rămâne în afara domeniului acestui articol, deoarece „totul este acoperit de ciocolată”. Decompresia este mult mai rapidă și este limitată de viteza I/O. Un nucleu fizic într-un fir oferă cu ușurință viteze de despachetare de 3-4 GB/sec.
Acest lucru se datorează absenței unei operațiuni de căutare a potrivirii în timpul procesului de decompresie, care „mâncă” principalele resurse ale procesorului și ale memoriei cache în timpul compresiei.
Fiabilitatea stocării datelor comprimate
După cum sugerează și numele întregii clase de software care utilizează compresia de date (arhive), acestea sunt concepute pentru stocarea pe termen lung a informațiilor, nu de ani de zile, ci de secole și milenii...
În timpul stocării, mediile de stocare pierd unele date, iată un exemplu:
Acest purtător de informații „analogic” are o vechime de o mie de ani, unele fragmente s-au pierdut, dar în general informațiile sunt „lizibile”...
Niciunul dintre producătorii responsabili de sisteme moderne de stocare a datelor digitale și medii digitale pentru acestea nu oferă garanții de siguranță completă a datelor de mai bine de 75 de ani.
Și aceasta este o problemă, dar o problemă amânată, urmașii noștri o vor rezolva...
Sistemele digitale de stocare a datelor pot pierde date nu numai după 75 de ani, erorile în date pot apărea oricând, chiar și în timpul înregistrării lor, ele încearcă să minimizeze aceste distorsiuni prin utilizarea redundanței și corectarea lor cu sisteme de corectare a erorilor. Sistemele de redundanță și corecție nu pot restabili întotdeauna informațiile pierdute, iar dacă o fac, nu există nicio garanție că operația de restaurare a fost finalizată corect.
Și aceasta este și o problemă mare, dar nu una amânată, ci una actuală.
Compresoarele moderne utilizate pentru arhivarea datelor digitale sunt construite pe diferite modificări ale metodei dicționarului, iar pentru astfel de arhive pierderea unei informații va fi un eveniment fatal; există chiar și un termen stabilit pentru o astfel de situație - o arhivă „stricată” ...
Fiabilitatea scăzută a stocării informațiilor în arhive cu compresie de dicționar este asociată cu structura datelor comprimate. Informația dintr-o astfel de arhivă nu conține textul sursă, numărul de intrări din dicționar sunt stocate acolo, iar dicționarul în sine este modificat dinamic de textul comprimat curent. Dacă un fragment de arhivă este pierdut sau corupt, toate intrările de arhivă ulterioare nu pot fi identificate nici după conținut, nici după lungimea intrării din dicționar, deoarece nu este clar căruia îi corespunde numărul intrării din dicționar.
Este imposibil să restabiliți informații dintr-o astfel de arhivă „stricată”.
Algoritmul RTT se bazează pe o metodă mai fiabilă de stocare a datelor comprimate. Utilizează metoda indexului de contabilizare a fragmentelor repetate. Această abordare a compresiei vă permite să minimizați consecințele distorsiunii informațiilor pe mediul de stocare și, în multe cazuri, să corectați automat distorsiunile apărute în timpul stocării informațiilor.
Acest lucru se datorează faptului că fișierul de arhivă în cazul comprimării indexului conține două câmpuri:
- un câmp de text sursă cu secțiuni repetate eliminate din acesta;
- câmp index.
Câmpul index, care este esențial pentru recuperarea informațiilor, nu este de dimensiuni mari și poate fi duplicat pentru stocarea fiabilă a datelor. Prin urmare, chiar dacă se pierde un fragment din textul sursă sau din matricea de index, toate celelalte informații vor fi restaurate fără probleme, ca în imagine cu un mediu de stocare „analogic”.
Dezavantajele algoritmului
Nu există avantaje fără dezavantaje. Metoda de compresie a indexului nu comprimă secvențe scurte care se repetă. Acest lucru se datorează limitărilor metodei indexului. Indecii au o dimensiune de cel puțin 3 octeți și pot avea o dimensiune de până la 12 octeți. Dacă o repetiție este întâlnită cu o dimensiune mai mică decât indexul care o descrie, atunci nu este luată în considerare, indiferent cât de des sunt detectate astfel de repetiții în fișierul comprimat.
Metoda tradițională de compresie a dicționarului comprimă în mod eficient mai multe repetări de lungime scurtă și, prin urmare, obține un raport de compresie mai mare decât compresia index. Adevărat, acest lucru se realizează datorită încărcării mari a procesorului central; pentru ca metoda dicționarului să înceapă să comprima datele mai eficient decât metoda indexului, trebuie să reducă viteza de procesare a datelor la 10-20 megaocteți pe secundă pe real. instalații de calcul cu o încărcare completă a procesorului.
Astfel de viteze mici sunt inacceptabile pentru sistemele moderne de stocare a datelor și prezintă un interes mai mult „academic” decât practic.
Gradul de compresie a informațiilor va fi crescut semnificativ în următoarea modificare a algoritmului RTT (RTT-Max), care este deja în dezvoltare.
Așa că, ca întotdeauna, de continuat...
Sursa: www.habr.com