Ovaj članak je već drugi na temu kompresije podataka velike brzine. Prvi članak opisuje kompresor koji radi brzinom od 10 GB/s. po jezgri procesora (minimalna kompresija, RTT-Min).
Ovaj kompresor je već implementiran u opremu forenzičkih duplikatora za brzu kompresiju ispisa medija za pohranu i povećanje snage kriptografije; također se može koristiti za komprimiranje slika virtualnih strojeva i RAM swap datoteka kada se spremaju velikom brzinom SSD diskovi.
U prvom članku također je najavljen razvoj kompresijskog algoritma za kompresiju sigurnosnih kopija HDD i SSD diskova (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 usporediv sa standardnim arhivarima kao što su WinRar, 7-Zip, koji rade u brzom načinu rada. Istodobno, njegova radna brzina je barem jedan red veličine veća.
Brzina pakiranja/otpakiravanja podataka kritični je parametar koji određuje opseg primjene tehnologija kompresije. Malo je vjerojatno da bi ikome palo na pamet sažimanje terabajta podataka brzinom od 10-15 megabajta u sekundi (to je upravo brzina arhivara u standardnom načinu sažimanja), jer bi to uz puno opterećenje procesora trajalo gotovo dvadeset sati. .
S druge strane, isti terabajt može se kopirati brzinom od 2-3 gigabajta u sekundi za desetak minuta.
Stoga je kompresija podataka velikog volumena važna ako se izvodi brzinom koja nije niža od brzine stvarnog ulaza/izlaza. Za moderne sustave to je najmanje 100 megabajta u sekundi.
Moderni kompresori mogu proizvesti takve brzine samo u "brzom" načinu rada. Upravo u ovom trenutnom načinu rada usporedit ćemo RTT-Mid algoritam s tradicionalnim kompresorima.
Usporedno testiranje novog algoritma kompresije
Kompresor RTT-Mid radio je kao dio programa testiranja. U pravoj "radnoj" aplikaciji radi mnogo brže, mudro koristi višenitnost i koristi "normalan" kompajler, a ne C#.
Budući da su kompresori korišteni u usporednom testu izgrađeni na različitim principima te se različite vrste podataka različito komprimiraju, radi objektivnosti testa korištena je metoda mjerenja “prosječne temperature u bolnici”...
Stvorena je sektorska po sektorska dump datoteka logičkog diska s Windows 10 operativnim sustavom; to je najprirodnija mješavina različitih struktura podataka zapravo dostupna na svakom računalu. Sažimanje ove datoteke omogućit će vam da usporedite brzinu i stupanj sažimanja novog algoritma s najnaprednijim kompresorima koji se koriste u modernim arhivarima.
Ovo je dump datoteka:
Datoteka ispisa komprimirana je pomoću kompresora PTT-Mid, 7-zip i WinRar. WinRar i 7-zip kompresor postavljeni su na maksimalnu brzinu.
Kompresor radi 7-zip:
Opterećuje procesor 100%, dok je prosječna brzina čitanja originalnog dumpa oko 60 megabajta/sek.
Kompresor radi WinRAR:
Situacija je slična, opterećenje procesora je gotovo 100%, prosječna brzina čitanja dumpa je oko 125 megabajta/sek.
Kao iu prethodnom slučaju, brzina arhivara ograničena je mogućnostima procesora.
Testni program kompresora je sada pokrenut RTT-Sred:
Na snimci zaslona se vidi da je procesor opterećen na 50%, a ostalo vrijeme miruje, jer se komprimirani podaci nemaju kamo uploadati. Disk za učitavanje podataka (Disk 0) gotovo je u potpunosti napunjen. Brzina čitanja podataka (Disk 1) jako varira, ali u prosjeku više od 200 megabajta/sek.
Brzina kompresora ograničena je u ovom slučaju mogućnošću pisanja komprimiranih podataka na Disk 0.
Sada omjer kompresije rezultirajućih arhiva:
Vidi se da je RTT-Mid kompresor odradio najbolji posao kompresije, arhiva koju je napravio bila je 1,3 gigabajta manja od WinRar arhive i 2,1 gigabajta manja od 7z arhive.
Vrijeme potrošeno na izradu arhive:
- 7-zip – 26 minuta 10 sekundi;
- WinRar – 17 minuta 40 sekundi;
- RTT-sredina – 7 minuta i 30 sekundi.
Tako je čak i testni, neoptimizirani program, koristeći RTT-Mid algoritam, uspio napraviti arhivu više od dva i pol puta brže, dok je arhiva ispala znatno manja od one kod konkurencije...
Oni koji ne vjeruju screenshotovima mogu sami provjeriti njihovu autentičnost. Program testiranja dostupan je na , preuzmite i provjerite.
Ali samo na procesorima s podrškom za AVX-2, bez podrške za ove instrukcije kompresor ne radi, a algoritam ne testirajte na starijim AMD procesorima, spori su što se tiče izvršavanja AVX instrukcija...
Korištena metoda kompresije
Algoritam koristi metodu za indeksiranje ponovljenih fragmenata teksta u granularnosti bajtova. Ova metoda sažimanja poznata je već duže vrijeme, ali se nije koristila jer je operacija sparivanja bila vrlo skupa u smislu potrebnih resursa i zahtijevala je mnogo više vremena od izrade rječnika. Dakle, RTT-Mid algoritam je klasičan primjer kretanja “natrag u budućnost”...
PTT kompresor koristi jedinstveni skener za traženje podudaranja velike brzine, koji nam omogućuje ubrzanje procesa kompresije. Samostalni skener, ovo je "moj šarm ...", "prilično je skup, jer je potpuno ručni rad" (napisano u asembleru).
Skener za traženje podudarnosti izrađen je prema probabilističkoj shemi na dvije razine: prvo se skenira prisutnost "znaka" podudarnosti, a tek nakon što je "znak" identificiran na ovom mjestu, postupak za otkrivanje stvarnog podudarnosti je pokrenut.
Prozor za traženje podudaranja ima nepredvidivu veličinu, ovisno o stupnju entropije u obrađenom bloku podataka. Za potpuno slučajne (nekomprimirane) podatke ima veličinu od megabajta, za podatke s ponavljanjem uvijek je veći od megabajta.
Ali mnogi moderni formati podataka nisu komprimirani i pokretanje skenera koji zahtijeva velike resurse 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; ova se operacija također provodi pomoću probabilističke metode i izvodi se vrlo brzo (brzinom od 4-6 GigaBytes/sec). Područja s mogućim podudarnostima zatim obrađuju glavni skener.
Kompresija indeksa nije vrlo učinkovita, duplicirane fragmente morate zamijeniti indeksima, a niz indeksa značajno smanjuje omjer kompresije.
Kako bi se povećao omjer kompresije, indeksiraju se ne samo potpuna 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 označava podudarne bajtove dvaju blokova. 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 kompresoru PTT-Mid postigne omjer kompresije usporediv s kompresorima napravljenim metodom rječnika, ali rade puno brže.
Brzina novog algoritma kompresije
Ako kompresor radi s isključivom upotrebom predmemorije (potrebno je 4 megabajta po niti), tada se radna brzina kreće od 700-2000 megabajta/sek. po procesorskoj jezgri, ovisno o vrsti podataka koji se komprimiraju i malo ovisi o radnoj frekvenciji procesora.
Uz implementaciju kompresora s više niti, učinkovita skalabilnost određena je veličinom predmemorije treće razine. Na primjer, s 9 megabajta predmemorije "na brodu", nema smisla pokretati više od dvije niti kompresije; brzina se time neće povećati. Ali s predmemorijom od 20 megabajta već možete pokrenuti pet komprimiranih niti.
Također, latencija RAM-a postaje važan parametar koji određuje brzinu kompresora. Algoritam koristi slučajni pristup OP-u, od kojih dio ne ulazi u predmemoriju (oko 10%) i mora mirovati, čekajući podatke iz OP-a, što smanjuje brzinu rada.
Značajno utječe na brzinu kompresora i rad sustava za unos/izlaz podataka. Zahtjevi OP-u iz I/O blokiraju zahtjeve za podacima iz CPU-a, što također smanjuje brzinu kompresije. Ovaj problem je značajan za prijenosna i stolna računala; za poslužitelje je manje značajan zbog naprednije jedinice za kontrolu pristupa sistemskoj sabirnici i višekanalnog RAM-a.
U cijelom tekstu u članku govorimo o kompresiji, a dekompresija ostaje izvan okvira ovog članka jer je “sve u čokoladi”. Dekompresija je puno brža i ograničena je I/O brzinom. Jedna fizička jezgra u jednoj niti lako osigurava brzine raspakiranja od 3-4 GB/s.
To je zbog nepostojanja operacije traženja podudaranja tijekom procesa dekompresije, što "pojede" glavne resurse procesora i predmemoriju tijekom kompresije.
Pouzdanost pohrane komprimiranih podataka
Kao što naziv cijele klase softvera koji koriste kompresiju podataka (arhivatori) govori, oni su dizajnirani za dugotrajnu pohranu informacija, ne godinama, već stoljećima i tisućljećima...
Tijekom pohrane mediji za pohranu gube neke podatke, evo primjera:
Ovaj “analogni” nositelj informacija star je tisuću godina, neki su fragmenti izgubljeni, ali općenito su informacije “čitljive”...
Nitko od odgovornih proizvođača suvremenih digitalnih sustava za pohranu podataka i digitalnih medija za njih ne jamči potpunu sigurnost podataka dulje od 75 godina.
I to je problem, ali odgođeni problem, riješit će ga naši potomci...
Digitalni sustavi za pohranu podataka mogu izgubiti podatke ne samo nakon 75 godina, pogreške u podacima mogu se pojaviti u bilo kojem trenutku, čak i tijekom njihovog snimanja, pokušavaju minimizirati te distorzije koristeći redundanciju i ispravljajući ih sustavima za ispravljanje pogrešaka. Sustavi zalihosti i ispravljanja ne mogu uvijek vratiti izgubljene informacije, a ako to učine, nema jamstva da je operacija vraćanja ispravno dovršena.
I to je također veliki problem, ali ne odgođeni, nego trenutni.
Suvremeni kompresori koji se koriste za arhiviranje digitalnih podataka izgrađeni su na raznim modifikacijama rječničke metode, a za takve će arhive gubitak podatka biti fatalan događaj, pa čak postoji i ustaljeni izraz za takvu situaciju - „pokvarena“ arhiva ...
Niska pouzdanost pohranjivanja informacija u arhive s kompresijom rječnika povezana je sa strukturom komprimiranih podataka. Informacije u takvoj arhivi ne sadrže izvorni tekst, tamo se pohranjuju brojevi unosa u rječniku, a sam rječnik se dinamički mijenja trenutnim komprimiranim tekstom. Ako se arhivski fragment izgubi ili ošteti, sve naredne arhivske natuknice ne mogu se prepoznati ni po sadržaju ni po duljini natuknice u rječniku, jer nije jasno čemu odgovara broj rječničke natuknice.
Nemoguće je obnoviti podatke iz tako "pokvarene" arhive.
RTT algoritam temelji se na pouzdanijoj metodi pohranjivanja komprimiranih podataka. Koristi metodu indeksa za obračun fragmenata koji se ponavljaju. Ovaj pristup kompresiji omogućuje vam da minimizirate posljedice izobličenja informacija na mediju za pohranu, au mnogim slučajevima automatski ispravite izobličenja koja su nastala tijekom pohranjivanja informacija.
To je zbog činjenice da arhivska datoteka u slučaju kompresije indeksa sadrži dva polja:
- polje izvornog teksta s uklonjenim odjeljcima koji se ponavljaju;
- polje indeksa.
Indeksno polje, koje je kritično za oporavak podataka, nije veliko i može se duplicirati za pouzdanu pohranu podataka. Stoga, čak i ako se izgubi fragment izvornog teksta ili polja indeksa, sve ostale informacije bit će vraćene bez problema, kao na slici s "analognim" medijem za pohranu.
Nedostaci algoritma
Nema prednosti bez nedostataka. Metoda kompresije indeksa ne komprimira kratke nizove koji se ponavljaju. To je zbog ograničenja metode indeksa. Indeksi su veličine najmanje 3 bajta, a mogu biti i do 12 bajtova. Ako se naiđe na ponavljanje s manjom veličinom od indeksa koji ga opisuje, ono se ne uzima u obzir, bez obzira koliko često se takva ponavljanja otkrivaju u komprimiranoj datoteci.
Tradicionalna metoda sažimanja rječnika učinkovito sažima višestruka ponavljanja kratke duljine i stoga postiže veći omjer sažimanja od sažimanja indeksa. Istina, to se postiže velikim opterećenjem središnjeg procesora; kako bi rječnička metoda počela komprimirati podatke učinkovitije od metode indeksa, mora smanjiti brzinu obrade podataka na 10-20 megabajta u sekundi u stvarnom vremenu. računalne instalacije s punim CPU opterećenjem.
Tako male brzine neprihvatljive su za moderne sustave za pohranu podataka i više su od "akademskog" interesa nego od praktičnog.
Stupanj kompresije informacija značajno će se povećati u sljedećoj modifikaciji RTT algoritma (RTT-Max), koja je već u razvoju.
Dakle, kao i uvijek, nastavak slijedi...
Izvor: www.habr.com