Kytyre kjo është artikulli i dytë në temën e kompresionit të shpejtë të të dhënave. Në artikullin e parë u përshkrua një kompresor që punon me shpejtësinë 10GB/sec. për çdo bërthamë procesori (kompresim minimal, RTT-Min).
Ky kompresor është tashmë i integruar në pajisjet e duplikatorëve kriminalistike për kompresionin me shpejtësi të skedarëve të informacionit dhe rritjen e qëndrueshmërisë së kriptografisë; gjithashtu mund të përdoret për kompresionin e imazheve të makinave virtuale dhe skedarëve swap të memories gjatë ruajtjes së tyre në SSD të shpejtë.
Në artikullin e parë u njoftua gjithashtu zhvillimi i një algoritmi kompresimi për kompresionin e kopjeve rezervë të disqeve HDD dhe SSD (kompresim mesatar, RTT-Mid) me parametrat e përmirësuara të kompresionit të të dhënave. Deri tani, ky kompresor është plotësisht i gatshëm dhe ky artikull është pikërisht për të.
Kompresori që implementon algoritmin RTT-Mid ofron një shkallë kompresimi që është krahasuese me arkivuesit standardë si WinRar, 7-Zip, që punojnë në modalitetin e shpejtë. Ndërkohë, shpejtësia e tij të paktën është një rend tjetër më e lartë.
Shpejtësia e paketimit dhe shpaketimit të të dhënave është një parametr kritik që përcakton fushën e aplikacionit të teknologjive të kompresimit. E vështirë se dikujt do t'i vie në mendje të kompresojë një tera byte të dhëna me shpejtësi 10-15 MegaByte në sekondë (kjo është shpejtësia e arkivuesve në modin standard të kompresimit), pasi do të duhet të kalojmë gati njëzet orë me procesorin e ngarkuar plotësisht...
Nga ana tjetër, është e mundur të kopjosh të njëjtin tera byte me shpejtësi prej 2-3 GigaByte në sekondë brenda dhjetë minutash.
Prandaj, kompresimi i informacionit të madh është aktual nëse bëhet me një shpejtësi jo më të ulët se shpejtësia reale e hyrje/daljes. Për sistemet moderne kjo është të paktën 100 MegaByte në sekondë.
Këto shpejtësi kompjuterat modernë mund t'i arrijnë vetëm në modalitetin "fast". Pra, në këtë modalitet aktual do të krahasojmë algoritmin RTT-Mid me arkivuesit tradicionalë.
Testimi krahasues i algoritmit të ri të kompresimit
Kompresori RTT-Mid punoi si pjesë e programit të testimit. Në një aplikacion "punues" në realitet, ai punon shumë më shpejt, aty përdoret në mënyrë të mençur multithreading dhe aplikohet një përkthyes "normal", jo C#.
MeqenĂ«se kompresorĂ«t e pĂ«rdorur nĂ« testin krahasues janĂ« ndĂ«rtuar nĂ« principe tĂ« ndryshme dhe llojet e ndryshme tĂ« tĂ« dhĂ«nave kompresohen ndryshe, pĂ«r objektivitetin e testit u pĂ«rdor njĂ« metodĂ« matjeje "temperaturĂ«s mesatare nĂ« spital"âŠ
U krijua një skedari i diskut logjik me sistemin operativ Windows 10, kjo është përzierja më natyrale e strukturave të ndryshme të të dhënave që aktualisht ekziston në çdo kompjuter. Kompresimi i këtij skedari do të lejojë krahasimin e shpejtësisë dhe gradës së kompresimit të algoritmit të ri me kompresorët më të avancuar të përdorur në arkivatorët modernë.
Ky është skedari i dump-it:
Skedari i dump-it u kompresua nga kompresorët RTT-Mid, 7-zip, WinRar. Kompresori WinRar dhe 7-zip u vendosën për maksimalin në shpejtësi të punës.
Kompresori po punon 7-zip:
Ai ngarkon procesorin në 100%, ndërkohë që shpejtësia mesatare e leximit të dump-it origjinal është rreth 60 Megabajt/sekund.
Kompresori po punon WinRar:
Situata është e ngjashme, ngarkesa e procesorit është pothuaj 100%, shpejtësia mesatare e leximit të dump-it është rreth 125 Megabajt/sekund.
Si në rastin e mëparshëm, shpejtësia e punës së arkivatorit është e kufizuar nga mundësitë e procesorit.
Tani po punon programi testues i kompresorit RTT-Mid:
Screenshot-i tregon se procesori është ngarkuar në 50% dhe është në pritje për pjesën tjetër të kohës, sepse nuk ka ku të shkarkohet të dhënat e kompresuara. Disku i shkarkimit të të dhënave (Disku 0) është ngarkuar pothuajse plotësisht. Shpejtësia e përpunimit të të dhënave (Disku 1) luhatet shumë, por në mesatarisht është mbi 200 Megabajt/sekund.
Shpejtësia e punës së kompresorit është e kufizuar në këtë rast nga mundësitë e shkruarjes së të dhënave të kompresuara në Diskun 0.
Tani shkalla e kompresimit të arkivave të fituara:
E dukshme është se kompresori RTT-Mid u përball me kompresimin më mirë se të tjerët, arkivi i krijuar prej tij është 1.3 Gigabajt më i vogël se arkivi WinRar dhe 2.1 Gigabajt më i vogël se arkivi 7z.
Koha e shpenzuar për krijimin e arkivit:
- 7-zip â 26 minuta 10 sekonda;
- WinRar â 17 minuta 40 sekonda;
- RTT-Mid â 7 minuta 30 sekonda.
KĂ«shtu, edhe programi testues, i pa optimizuar, duke pĂ«rdorur algoritmin RTT-Mid, arriti tĂ« krijojĂ« njĂ« arkiv mĂ« shumĂ« se dy herĂ« e gjysmĂ« mĂ« shpejt, ndĂ«rkohĂ« qĂ« arkivi doli tĂ« ishte ndjeshĂ«m mĂ« i vogĂ«l se ai i konkurrentĂ«veâŠ
Ata që nuk besojnë screenshot-et, mund të verifikojnë saktësinë e tyre vetë. Programi testues është i disponueshëm në , shkarkoni dhe kontrolloni.
Poros, vetĂ«m nĂ« procesorĂ«t qĂ« pĂ«rkrahin AVX-2, pa mbĂ«shtetje pĂ«r kĂ«to instruktime, kompaktori nuk funksionon, dhe mos e testoni algoritmin nĂ« procesorĂ«t e vjetĂ«r AMD, ata janĂ« tĂ« ngadalshĂ«m nĂ« ekzekutimin e komandave AVXâŠ
Metoda e kompresimit të përdorur
Algoritmi pĂ«rdor njĂ« metodĂ« indeksimi tĂ« fragmenteve tĂ« pĂ«rsĂ«ritura tĂ« tekstit nĂ« granula byte. Kjo metodĂ« kompresimi Ă«shtĂ« e njohur prej njĂ« kohe tĂ« gjatĂ«, por nuk Ă«shtĂ« pĂ«rdorur deri tani, pasi operacioni i kĂ«rkimit tĂ« pĂ«rputhjeve ishte shumĂ« i kushtueshĂ«m nĂ« burimet e nevojshme dhe kĂ«rkonte shumĂ« mĂ« shumĂ« kohĂ« sesa ndĂ«rtimi i njĂ« fjalori. Pra, algoritmi RTT-Mid Ă«shtĂ« njĂ« shembull klasik i lĂ«vizjes "mbrapa nĂ« tĂ« ardhmen"âŠ
NĂ« kompaktorin RTT pĂ«rdoret njĂ« skaner unik i shpejtĂ« pĂ«r kĂ«rkimin e pĂ«rputhjeve, i cili mundĂ«son pĂ«rshpejtimin e procesit tĂ« kompresimit. Skaneri i prodhimit tĂ« vet, Ă«shtĂ« "prerogativa imeâŠ", "çmimi i tij nuk Ă«shtĂ« i vogĂ«l, pasi Ă«shtĂ« krejt manual" (shkruar nĂ« assembler).
Skaneri i kërkimit të përputhjeve është realizuar sipas një skeme probabiliste me dy nivele, fillimisht skanohet prania e "shenjës" së përshtatjes, dhe vetëm pas identifikimit të "shenjës" në atë vend aktivizohet procedura e zbulimit të përshtatjes reale.
Dritarja e kërkimit të përputhjeve ka një madhësi të paparashikueshme, e cila varet nga niveli i entropisë në bllokun e dhënave që po përpunohet. Për të dhëna krejtësisht të rastësishme (të pandjeshme), ajo ka madhësi megabajt, për të dhënat që kanë përsëritje gjithmonë ka një madhësi mbi megabajt.
Por shumë formate moderne të të dhënave janë të pandjeshme dhe "ta gjuajmë" nëpër to skanerin që konsumon burime është e kotë dhe e shpenzuar, prandaj skaneri përdor dy mënyra operimi. Fillimisht kërkohen segmente të tekstit origjinal me përsëritje të mundshme, ky operacion kryhet gjithashtu me një metodë probabiliste dhe ekzekutohet shumë shpejt (në shpejtësi prej 4-6 Gigabajt/s). Pastaj segmentet me përputhje të mundshme merren në dorë nga skaneri kryesor.
Kompresimi me indeks nuk është shumë efikas, pasi duhet të zëvendësohen fragmentet e përsëritura me indekse, dhe masa e indekseve zvogëlon ndjeshëm koeficientin e kompresimit.
Për të rritur gradën e kompresimit, jo vetëm përputhjet e plota të vargjeve të bajtëve indeksohen, por edhe ato të pjesshme, kur në varg ka bajtë të përputhur dhe të papërputhur. Për këtë, në formatin e indeksit është përfshirë një fushë maskë përshtatjesh që tregon për bajtët e përputhur të dy blokjeve. Për kompresim edhe më të madh, përdoret indeksimi me mbivendosje të disa blloqeve të pjesshëm të përputhura në bllokun aktual.
Të gjitha këto ndihmuan në arritjen e një shkalle kompresimi në kompresorin RTT-Mid, e cila është e krahasueshme me kompresorët e realizuar me metodën e fjalorit, por punon shumë më shpejt.
Shpejtësia e punës së algoritmit të ri të kompresimit
Nëse kompresori punon me përdorim monopol të memores cache (për një rrjedhë kërkohen 4 MegaBajt), atëherë shpejtësia e punës varion nga 700 në 2000 MegaBajt/sec. për çdo bërthamë procesori në varësi të llojit të të dhënave të kompresuara dhe ka pak ndikim nga frekuenca e punës së procesorit.
Në realizimin me shumë rrjedha të kompresorit, shkalla efektive e shkallëzimit përcaktohet nga sasia e memorjes cache të nivelit të tretë. Për shembull, duke pasur "në bord" 9 MegaBajt memorie cache nuk ka kuptim të nisin më shumë se dy rrjedha kompresimi, shpejtësia nuk do të rritet. Por me 20 MegaBajt cache, tashmë mund të nisin pesë rrjedha kompresimi.
Një parametër tjetër i rëndësishëm që përcakton shpejtësinë e punës së kompresorit është vonesa e memores operative. Algoritmi përdor kërkesa të rastësishme për nënshkronje në OP, një pjesë e të cilave nuk arrin në memorien cache (rreth 10%) dhe i duhet të presë për të dhënat nga OP, çka e ul shpejtësinë e punës.
Shpejtësinë e kompresorit e ndikon ndjeshëm edhe puna e sistemit të hyrjes/daljes së të dhënave. Kërkesat për OP nga hyrja/dalja bllokojnë kërkesat për të dhëna nga CP, çka gjithashtu ul shpejtësinë e kompresimit. Ky problem është i rëndësishëm për laptopët dhe desktopët, për servera ai është më pak i rëndësishëm falë një blloku më të avancuar të menaxhimit të aksesit në shiritin sistemor dhe memores operative shumëkanal.
Kudohe në tekstin e artikullit flitet për kompresimin, dekompresimi mbetet jashtë kësaj artikulli sepse aty "gjithçka është në rregull". Dekompresimi kryhet dukshëm më shpejt dhe kufizohet nga shpejtësia e hyrjes/daljes. Një bërthamë fizike në një rrjedhë siguron qetësisht shpejtësi ekstraktimi në nivelin 3-4 Gigabajtë/sekondë.
Kjo është e lidhur me mungesën në procesin e ekstraktimit të operacionit për kërkimin e përputhjeve, i cili "ha" burimet kryesore të procesorit dhe memorizimit gjatë kompresimit.
Besueshmëria e ruajtjes së të dhënave të kompresuara
Siç tregohet nga emri i tĂ« gjithĂ« klasĂ«s sĂ« mjeteve softuerike qĂ« pĂ«rdorin kompresionin e tĂ« dhĂ«nave (arkivuesit), ato janĂ« tĂ« destinuara pĂ«r ruajtje afatgjatĂ« tĂ« informacionit, jo pĂ«r vite, por pĂ«r shekuj dhe mijĂ«ra vjetâŠ
Gjatë ruajtjes, bartësit e informacionit humbasin një pjesë të të dhënave, ja një shembull:
Ky bartĂ«s informacioni "analogjik" ka njĂ« mijĂ« vjet, disa fragmente janĂ« humbur, por nĂ« pĂ«rgjithĂ«si informacioni Ă«shtĂ« "i lexueshĂ«m"âŠ
Asnjë nga prodhuesit e përgjegjshëm të sistemeve moderne digjitale të ruajtjes së të dhënave dhe bartësve digjitalë nuk ofron garanci për ruajtjen e plotë të të dhënave për më shumë se 75 vjet.
Dhe kjo është një problem, por një problem i shtyrë, do ta zgjidhin pasardhësit tanë...
Sistemet e ruajtjes së të dhënave digjitale mund të humbasin të dhëna jo vetëm pas 75 vjetësh, gabimet në të dhëna mund të shfaqen në çdo moment, madje edhe gjatë regjistrimit të tyre, këto devijime përpiqen të minimizohen duke përdorur tepricën dhe duke korrigjuar me sistemet e korrigjimit të gabimeve. Teprica dhe sistemet e korrigjimit nuk mund të rikthejnë informacionin e humbur gjithmonë, dhe nëse e bëjnë, nuk ka garanci që operacioni i rikthimit kaloi siç duhet.
Dhe kjo është gjithashtu një problem i madh, por jo i shtyrë, por aktual.
KompresorĂ«t modernĂ« tĂ« pĂ«rdorur pĂ«r arkivimin e tĂ« dhĂ«nave digjitale janĂ« ndĂ«rtuar mbi modifikime tĂ« metodĂ«s sĂ« fjalorit dhe pĂ«r kĂ«to arkiva, humbja e njĂ« fragmenti informacioni do tĂ« jetĂ« njĂ« ngjarje fatale, madje ekziston njĂ« term i vendosur pĂ«r njĂ« situatĂ« tĂ« tillĂ« â "arkiv i dĂ«mtuar"...
Përfshirja e informacionit të ulët në arkivat me kompresim fjalë për fjalë lidhet me strukturën e të dhënave të kompresuara. Informacioni në një arkiv të tillë nuk përmban tekstin origjinal, aty ruhen numrat e regjistrimeve në fjalor, ndërsa fjalori vetë modifikohet dinamikisht nga teksti aktual në kompresim. Në rast se humbet ose keqinterpretohet një fraksion i arkivës, të gjitha regjistrimet e mëvonshme në arkiv nuk mund të identifikohen as nga përmbajtja, as nga gjatësia e regjistrimit në fjalor, pasi nuk është e qartë se çfarë i përgjigjet numrit të regjistrimit në fjalor.
Për të rikuperuar informacionin nga një arkiv të tillë "të prishur" është e pamundur.
Algoritmi RTT është ndërtuar mbi një metodë më të besueshme të ruajtjes së të dhënave të kompresuara. Në të aplikohet metoda indeksuese për të mbajtur mend fragmentet e përsëritura. Kjo qasje për kompresionin lejon minimizimin e pasojave të keqinterpretimit të informacionit në mbajtës, dhe në shumë raste automatikisht korrigjon keqinterpretimet që kanë ndodhur gjatë ruajtjes së informacionit.
Kjo lidhet me faktin se skedari arkivor, në rastin e kompresimit me indeks, përmban dy fusha:
- fusha e tekstit origjinal me pjesĂ«t e pĂ«rsĂ«ritura tĂ« hequra nga tĂ«;â
- fusha e indekseve.
Fusha e indekseve është kritike për rikuperimin e informacionit, nuk është e madhe në madhësi dhe mund të dyfishohet për sigurinë e ruajtjes së të dhënave. Prandaj, edhe nëse humbet një fraksion i tekstit origjinal ose i masës së indekseve, e gjithë informacioni tjetër do të rikuperohet pa probleme, si në imazhin me mbajtësin e informacionit "analog".
Mangësitë e algoritmit
Nuk ka merita pa mangësi. Metoda indeksuese e kompresionit nuk kompreson sekuenca përsëritëse me gjatësi të vogël. Kjo lidhet me kufizimet e metodës indeksuese. Indekset kanë madhësi jo më pak se 3 byte dhe mund të jenë deri në 12 byte. Nëse shfaqet një përsëritje me një madhësi më të vogël se ajo që përshkruan indeksi, atëherë ajo nuk llogaritet, pavarësisht se sa shpesh shfaqen ato përsëritje në skedarin në kompresim.
Metoda tradicionale, e bazuar në fjalor, kompreson shumë përsëritje të shkurtra në mënyrë efektive dhe, për këtë arsye, arrin një koeficient më të lartë kompresimi sesa kompresimi indekseve. E vërteta është se kjo arrihet përmes një ngarkese të lartë të procesorit qendror, sepse për të filluar kompresimin e të dhënave më efektivisht se metoda e indekseve, i duhet të ulë shpejtësinë e procesimit të të dhënave deri në 10-20 megabajt në sekondë në instalime reale të kompjuterëve gjatë ngarkesës maksimale të CPU-së.
Këto shpejtësi të ulëta janë të papranueshme për sistemet moderne të ruajtjes së të dhënave dhe përbëjnë më shumë një interes «akademik» sesa praktik.
Niveli i kompresimit të informacionit do të rritet ndjeshëm në modifikimin e ardhshëm të algoritmit RTT (RTT-Max), i cili është duke u zhvilluar.
Pra, si gjithmonë, vazhdimi ndjek...
Burimi: habr.com
