Ovaj članak je već drugi u temi kompresije podataka velike brzine. Prvi članak opisuje kompresor koji radi pri brzini od 10 GB/sec. po jezgri procesora (minimalna kompresija, RTT-Min).
Ovaj kompresor je već implementiran u opremu forenzičkih duplikatora za brzu kompresiju deponija medija za pohranu i povećanje snage kriptografije; može se koristiti i za kompresiju slika virtuelnih mašina i RAM swap datoteka prilikom njihovog spremanja na brzom SSD diskovi.
U prvom članku je također najavljen razvoj algoritma kompresije za komprimiranje rezervnih kopija HDD i SSD disk jedinica (srednja kompresija, RTT-Mid) sa značajno poboljšanim parametrima kompresije podataka. Do sada je ovaj kompresor potpuno spreman i ovaj članak je o tome.
Kompresor koji implementira RTT-Mid algoritam pruža omjer kompresije uporediv sa standardnim arhivatorima kao što su WinRar, 7-Zip, koji rade u režimu velike brzine. Istovremeno, njegova radna brzina je barem za red veličine veća.
Brzina pakovanja/raspakivanja podataka je kritičan parametar koji određuje obim primjene tehnologija kompresije. Malo je vjerovatno da bi ikome palo na pamet komprimirati terabajt podataka brzinom od 10-15 megabajta u sekundi (to je upravo brzina arhivatora u standardnom načinu kompresije), jer bi to trajalo skoro dvadeset sati uz puno opterećenje procesora. .
S druge strane, isti terabajt se može kopirati brzinom od 2-3 gigabajta u sekundi za desetak minuta.
Stoga je kompresija informacija velikog volumena važna ako se izvodi brzinom koja nije niža od brzine stvarnog ulaza/izlaza. Za moderne sisteme to je najmanje 100 megabajta u sekundi.
Moderni kompresori mogu proizvesti takve brzine samo u "brzom" načinu rada. U ovom trenutnom načinu rada ćemo uporediti RTT-Mid algoritam sa tradicionalnim kompresorima.
Uporedno testiranje novog algoritma kompresije
RTT-Mid kompresor je radio kao dio testnog programa. U stvarnoj "radnoj" aplikaciji radi mnogo brže, mudro koristi višenitno i koristi "normalan" kompajler, a ne C#.
Budući da su kompresori korišteni u uporednom testu izgrađeni na različitim principima i različiti tipovi podataka se različito komprimiraju, radi objektivnosti testa korištena je metoda mjerenja “prosječne temperature u bolnici”...
Napravljena je dump datoteka sektor po sektor logičkog diska sa Windows 10 operativnim sistemom; ovo je najprirodnija mješavina različitih struktura podataka koja je zapravo dostupna na svakom računalu. Kompresovanje ove datoteke će vam omogućiti da uporedite brzinu i stepen kompresije novog algoritma sa najnaprednijim kompresorima koji se koriste u modernim arhivarima.
Evo dump fajla:
Dump datoteka je komprimirana korištenjem PTT-Mid, 7-zip i WinRar kompresora. WinRar i 7-zip kompresor su postavljeni na maksimalnu brzinu.
Kompresor radi 7-zip:
Učitava procesor za 100%, dok je prosječna brzina čitanja originalnog dumpa oko 60 megabajta/sek.
Kompresor radi winrar:
Situacija je slična, opterećenje procesora je skoro 100%, prosječna brzina čitanja dump-a je oko 125 megabajta/sek.
Kao iu prethodnom slučaju, brzina arhivatora je ograničena mogućnostima procesora.
Program za testiranje kompresora je sada pokrenut RTT-Mid:
Na snimku ekrana se vidi da je procesor opterećen na 50% i da miruje sve ostalo vrijeme, jer nema gdje učitati komprimirane podatke. Disk za učitavanje podataka (Disk 0) je skoro potpuno učitan. Brzina čitanja podataka (Disk 1) veoma varira, ali u prosjeku više od 200 megabajta/sek.
Brzina kompresora je u ovom slučaju ograničena mogućnošću upisivanja komprimiranih podataka na Disk 0.
Sada omjer kompresije rezultirajućih arhiva:
Vidi se da je RTT-Mid kompresor najbolje obavio kompresiju; arhiva koju je kreirala bila je 1,3 gigabajta manja od WinRar arhive i 2,1 gigabajta manja od 7z arhive.
Vrijeme utrošeno na kreiranje arhive:
- 7-zip – 26 minuta 10 sekundi;
- WinRar – 17 minuta 40 sekundi;
- RTT-Mid – 7 minuta 30 sekundi.
Tako je čak i probni, neoptimizovani program, koristeći RTT-Mid algoritam, uspeo da napravi arhivu više od dva i po puta brže, dok se ispostavilo da je arhiva znatno manja od onih svojih konkurenata...
Oni koji ne vjeruju snimcima ekrana mogu sami provjeriti njihovu autentičnost. Program testiranja dostupan je na , preuzmite i provjerite.
Ali samo na procesorima sa AVX-2 podrškom, bez podrške za ove instrukcije kompresor ne radi, a ne testirajte algoritam na starijim AMD procesorima, oni su spori u pogledu izvršavanja AVX instrukcija...
Korištena metoda kompresije
Algoritam koristi metodu za indeksiranje ponovljenih fragmenata teksta u granularnosti bajtova. Ova metoda kompresije je poznata dugo vremena, ali se nije koristila jer je operacija uparivanja bila vrlo skupa u smislu potrebnih resursa i zahtijevala je mnogo više vremena od pravljenja rječnika. Dakle, RTT-Mid algoritam je klasičan primjer kretanja „nazad u budućnost“...
PTT kompresor koristi jedinstveni brzi skener za pretragu utakmica, koji nam omogućava da ubrzamo proces kompresije. Skener vlastite izrade, ovo je "moja čar...", "prilično je skup, jer je potpuno ručno rađen" (napisano u asembleru).
Skener za traženje poklapanja napravljen je prema dvostepenoj probabilističkoj šemi: prvo se skenira prisustvo "znaka" podudaranja, a tek nakon što se "znak" identifikuje na ovom mjestu, postupak za otkrivanje stvarnog podudaranja je pokrenut.
Prozor za pretraživanje podudaranja ima nepredvidivu veličinu, ovisno o stepenu entropije u obrađenom bloku podataka. Za potpuno nasumične (nekompresivne) podatke ima veličinu megabajta, za podatke s ponavljanjima uvijek je veći od megabajta.
Ali mnogi moderni formati podataka su nestišljivi i pokretanje skenera sa velikim resursima kroz njih je beskorisno i rasipno, tako da skener koristi dva načina rada. Prvo se pretražuju dijelovi izvornog teksta s mogućim ponavljanjima, a ova operacija se također izvodi probabilističkom metodom i izvodi se vrlo brzo (brzinom od 4-6 GigaBytes/sec). Područja s mogućim podudaranjima se zatim obrađuju od strane glavnog skenera.
Kompresija indeksa nije vrlo efikasna, morate zamijeniti duplirane fragmente indeksima, a niz indeksa značajno smanjuje omjer kompresije.
Da bi se povećao omjer kompresije, indeksiraju se ne samo kompletna podudaranja nizova bajtova, već i djelomična, kada niz sadrži podudarne i neusklađene bajtove. Da biste to učinili, format indeksa uključuje polje maske podudaranja koje ukazuje na podudarne bajtove dva bloka. Za još veću kompresiju, indeksiranje se koristi za superponiranje nekoliko djelomično podudarnih blokova na trenutni blok.
Sve je to omogućilo da se u PTT-Mid kompresoru dobije omjer kompresije uporediv s kompresorima napravljenim metodom rječnika, ali koji rade mnogo brže.
Brzina novog algoritma kompresije
Ako kompresor radi sa isključivom upotrebom keš memorije (potrebno je 4 megabajta po niti), tada se radna brzina kreće u rasponu od 700-2000 megabajta/sek. po procesorskoj jezgri, ovisno o vrsti podataka koji se komprimiraju i malo ovisi o radnoj frekvenciji procesora.
Sa višenitnom implementacijom kompresora, efektivna skalabilnost je određena veličinom keša trećeg nivoa. Na primjer, ako imate 9 megabajta keš memorije "na ploči", nema smisla pokretati više od dvije kompresijske niti; brzina se od toga neće povećati. Ali sa keš memorijom od 20 megabajta, već možete pokrenuti pet kompresijskih niti.
Također, latencija RAM-a postaje važan parametar koji određuje brzinu kompresora. Algoritam koristi nasumični pristup OP-u, od kojih neki ne ulaze u keš memoriju (oko 10%) i on mora da miruje, čekajući podatke iz OP-a, što smanjuje brzinu rada.
Značajno utiče na brzinu kompresora i rad sistema za unos/izlaz podataka. Zahtjevi do OP-a iz I/O blokiraju zahtjeve za podacima iz CPU-a, što također smanjuje brzinu kompresije. Ovaj problem je značajan za laptopove i desktop računare, a za servere je manje značajan zbog naprednije jedinice za kontrolu pristupa sistemskoj magistrali i višekanalne RAM memorije.
U cijelom tekstu u članku govorimo o kompresiji, a dekompresija ostaje izvan okvira ovog članka jer je “sve preliveno čokoladom”. Dekompresija je mnogo brža i ograničena je I/O brzinom. Jedno fizičko jezgro u jednoj niti lako pruža brzinu raspakivanja od 3-4 GB/sec.
To je zbog odsustva operacije pretraživanja podudaranja tokom procesa dekompresije, koja "jede" glavne resurse procesora i keš memorije tokom kompresije.
Pouzdanost skladištenja komprimiranih podataka
Kao što naziv čitave klase softvera koji koristi kompresiju podataka (arhivare) sugeriše, oni su dizajnirani za dugotrajno skladištenje informacija, ne godinama, već vekovima i milenijumima...
Tokom pohrane, mediji za pohranu gube neke podatke, evo primjera:
Ovaj "analogni" nosač informacija star je hiljadu godina, neki fragmenti su izgubljeni, ali generalno informacija je "čitka"...
Nijedan od odgovornih proizvođača savremenih digitalnih sistema za skladištenje podataka i digitalnih medija za njih ne daje garancije potpune bezbednosti podataka više od 75 godina.
I ovo je problem, ali odložen problem, rešiće ga naši potomci...
Digitalni sistemi za skladištenje podataka mogu izgubiti podatke ne samo nakon 75 godina, greške u podacima se mogu pojaviti u bilo kom trenutku, čak i tokom njihovog snimanja, pokušavaju da minimiziraju ova izobličenja koristeći redundantnost i ispravljaju ih sistemima za ispravljanje grešaka. Sistemi za redundantnost i korekcije ne mogu uvijek vratiti izgubljene informacije, a ako to učine, nema garancije da je operacija vraćanja ispravno završena.
I to je također veliki problem, ali ne odgođeni, već trenutni.
Savremeni kompresori koji se koriste za arhiviranje digitalnih podataka izgrađeni su na različitim modifikacijama metode rječnika, a za takve arhive gubitak informacije će biti fatalan, čak postoji i ustaljeni termin za takvu situaciju - "pokvarena" arhiva. ...
Niska pouzdanost pohranjivanja informacija u arhive sa kompresijom rječnika povezana je sa strukturom komprimiranih podataka. Informacije u takvoj arhivi ne sadrže izvorni tekst, u njemu se pohranjuju brojevi unosa u rječniku, a sam rječnik se dinamički modificira trenutnim komprimiranim tekstom. Ako se fragment arhive izgubi ili pokvari, svi naredni unosi arhive ne mogu se identificirati ni po sadržaju ni po dužini unosa u rječniku, jer nije jasno čemu odgovara broj unosa u rječniku.
Nemoguće je vratiti informacije iz takve "pokvarene" arhive.
RTT algoritam se zasniva na pouzdanijoj metodi skladištenja komprimovanih podataka. Koristi indeksnu metodu obračunavanja fragmenata koji se ponavljaju. Ovakav pristup kompresiji omogućava vam da minimizirate posljedice izobličenja informacija na mediju za pohranu i u mnogim slučajevima automatski ispravite izobličenja koja su nastala tijekom pohrane informacija.
To je zbog činjenice da arhivska datoteka u slučaju kompresije indeksa sadrži dva polja:
- izvorno tekstualno polje iz kojeg su uklonjeni dijelovi ponavljanja;
- indeksno polje.
Polje indeksa, koje je kritično za oporavak informacija, nije velike veličine i može se duplicirati radi pouzdanog skladištenja podataka. Stoga, čak i ako se izgubi fragment izvornog teksta ili indeksnog niza, sve ostale informacije će biti vraćene bez problema, kao na slici s “analognim” medijem za pohranu.
Nedostaci algoritma
Nema prednosti bez nedostataka. Metoda kompresije indeksa ne komprimira kratke sekvence koje se ponavljaju. To je zbog ograničenja metode indeksa. Indeksi su veličine najmanje 3 bajta i mogu biti veličine do 12 bajtova. Ako se naiđe na ponavljanje manje veličine od indeksa koji ga opisuje, onda se ono ne uzima u obzir, bez obzira koliko često se takva ponavljanja otkrivaju u komprimiranoj datoteci.
Tradicionalna metoda kompresije rječnika učinkovito komprimira višestruka ponavljanja kratke dužine i stoga postiže veći omjer kompresije od kompresije indeksa. Istina, to se postiže zbog velikog opterećenja centralnog procesora; da bi metoda rječnika počela efikasnije kompresirati podatke od indeksne, mora smanjiti brzinu obrade podataka na 10-20 megabajta u sekundi na stvarnom računarske instalacije sa punim CPU opterećenjem.
Ovako male brzine su neprihvatljive za moderne sisteme skladištenja podataka i više su od „akademskog“ interesa nego od praktičnog.
Stepen kompresije informacija biće značajno povećan u sledećoj modifikaciji RTT algoritma (RTT-Max), koja je već u razvoju.
Dakle, kao i uvek, nastavak...
izvor: www.habr.com