Artikulu hau dagoeneko bigarrena da abiadura handiko datuen konpresioaren gaian. Lehenengo artikuluan 10 GB/seg-ko abiaduran funtzionatzen duen konpresore bat deskribatu zen. prozesadorearen nukleo bakoitzeko (gutxieneko konpresioa, RTT-Min).
Konpresore hau bikoizle forentseen ekipoetan ezarri da biltegiratze-euskarrien zabortegien abiadura handiko konpresioa egiteko eta kriptografiaren indarra hobetzeko; gainera, makina birtualen irudiak konprimitzeko eta RAM trukatzeko fitxategiak abiadura handiko gordetzean erabil daiteke. SSD unitateak.
Lehen artikuluak HDD eta SSD disko-unitateen babeskopiak konprimitzeko konpresio-algoritmo baten garapena ere iragarri zuen (konpresio ertaina, RTT-Mid) datuen konpresio-parametroak nabarmen hobetuta. Honezkero, konpresore hau guztiz prest dago eta artikulu hau horri buruzkoa da.
RTT-Mid algoritmoa inplementatzen duen konpresore batek konpresio-erlazioa eskaintzen du WinRar, 7-Zip bezalako artxibo estandarren parekoa, abiadura handiko moduan funtzionatzen dutenak. Aldi berean, bere funtzionamendu-abiadura, gutxienez, magnitude ordena handiagoa da.
Datuak paketatzearen/deskonprimitzearen abiadura konpresio-teknologien aplikazio-esparrua zehazten duen parametro kritikoa da. Nekez da norbaitek datu terabyte bat segundoko 10-15 MegaByte-ko abiaduran konprimitzea pentsatuko zuela (hau da artxibatzaileen abiadura konpresio-modu estandarrean), ia hogei ordu beharko lituzkeelako prozesadore osoa kargatuta. .
Bestalde, terabyte bera segundoko 2-3 Gigabyte inguruko abiaduran kopiatu daiteke hamar minutu ingurutan.
Beraz, bolumen handiko informazioaren konpresioa garrantzitsua da sarrera/irteera errealaren abiadura baino abiadura txikiagoan egiten bada. Sistema modernoetarako, gutxienez 100 Megabyte segundoko da.
Konpresore modernoek halako abiadurak ekoitzi ditzakete "azkar" moduan soilik. Gaur egungo modu honetan RTT-Mid algoritmoa konpresore tradizionalekin alderatuko dugu.
Konpresio-algoritmo berri baten proba konparatiboa
RTT-Mid konpresoreak proba-programaren barruan funtzionatu zuen. Benetako "lanean" aplikazio batean askoz azkarrago funtzionatzen du, multithreading zentzuz erabiltzen du eta konpilatzaile "normal" bat erabiltzen du, ez C#.
Proba konparatiboan erabilitako konpresoreak printzipio ezberdinetan eraikitzen direnez eta datu mota desberdinak modu ezberdinean konprimitzen direnez, probaren objektibotasunerako, "ospitaleko batez besteko tenperatura" neurtzeko metodoa erabili zen...
Windows 10 sistema eragilea duen disko logiko baten sektorez sektoreko iraulketa-fitxategi bat sortu zen; hau da ordenagailu guztietan eskuragarri dauden hainbat datu-egituren nahasketarik naturalena. Fitxategi hau konprimitzeak algoritmo berriaren abiadura eta konpresio-maila artxibo modernoetan erabiltzen diren konpresore aurreratuenekin alderatzeko aukera emango du.
Hona hemen dump fitxategia:
Zaborketa fitxategia PTT-Mid, 7-zip eta WinRar konpresoreen bidez konprimitu zen. WinRar eta 7 zip konpresoreak abiadura maximoan ezarri ziren.
Konpresoreak martxan 7-zip:
Prozesadorea % 100ean kargatzen du, jatorrizko zabortegia irakurtzeko batez besteko abiadura 60 MegaByte/seg ingurukoa den bitartean.
Konpresoreak martxan WINRAR:
Egoera antzekoa da, prozesadorearen karga ia % 100ekoa da, isurketa irakurtzeko batez besteko abiadura 125 Megabyte/seg ingurukoa da.
Aurreko kasuan bezala, artxibatzailearen abiadura prozesadorearen gaitasunek mugatuta dago.
Konpresorea probatzeko programa martxan dago RTT-Erdialdea:
Pantaila-argazkiak erakusten du prozesadorea %50ean kargatuta dagoela eta gainerako denboran inaktibo dagoela, ez dagoelako inon konprimitutako datuak kargatzeko. Datuak kargatzeko diskoa (0 diskoa) ia guztiz kargatuta dago. Datuak irakurtzeko abiadura (1. diskoa) asko aldatzen da, baina batez beste 200 megabyte/seg baino gehiago.
Konpresorearen abiadura kasu honetan konprimitutako datuak 0 diskoan idazteko gaitasunak mugatzen du.
Orain ondoriozko artxiboen konpresio-erlazioa:
Ikus daiteke RTT-Mid konpresoreak konpresio lan onena egin zuela; sortutako artxiboa WinRar artxiboa baino 1,3 GigaByte txikiagoa zen eta 2,1z artxiboa baino 7 GigaByte txikiagoa.
Artxiboa sortzen emandako denbora:
- 7-zip - 26 minutu 10 segundo;
- WinRar - 17 minutu 40 segundo;
- RTT-Mid - 7 minutu 30 segundo.
Horrela, optimizatu gabeko programa proba batek ere, RTT-Mid algoritmoa erabiliz, artxibo bat bi aldiz eta erdi baino azkarrago sortzeko gai izan zen, eta artxiboa lehiakideena baino nabarmen txikiagoa zen bitartean...
Pantaila-argazkiak sinesten ez dituztenek beren benetakotasuna egiazta dezakete. Proba programa helbidean dago eskuragarri , deskargatu eta egiaztatu.
Baina AVX-2 euskarria duten prozesadoreetan bakarrik, argibide hauetarako laguntzarik gabe konpresoreak ez du funtzionatzen, eta ez du algoritmoa probatu AMD prozesadore zaharretan, motelak dira AVX argibideak exekutatzeko...
Erabilitako konpresio metodoa
Algoritmoak metodo bat erabiltzen du errepikatutako testu-zatiak byte-kopurutasunean indexatzeko. Konpresio-metodo hau aspalditik ezagutzen da, baina ez zen erabiltzen, parekatzeko eragiketa oso garestia zelako beharrezko baliabideei dagokienez eta hiztegi bat eraikitzea baino askoz denbora gehiago behar zuelako. Beraz, RTT-Mid algoritmoa "etorkizunera itzultzeko" adibide klasiko bat da...
PTT konpresoreak abiadura handiko partiden bilaketa-eskaner berezia erabiltzen du, eta horrek konpresio-prozesua bizkortzeko aukera ematen digu. Norberak egindako eskanerra, hau da “nire xarma...”, “nahiko garestia da, guztiz eskuz egina baita” (muntatzailean idatzia).
Partiduen bilaketa-eskanera bi maila probabilistikoko eskema baten arabera egiten da: lehenik eta behin, bat-etortze baten "seinale" baten presentzia aztertzen da, eta "seinalea" leku honetan identifikatu ondoren, benetako bat-etortze bat detektatzeko prozedura. hasi da.
Partiduen bilaketa-leihoak ezusteko tamaina du, prozesatutako datu-blokearen entropia-mailaren arabera. Datu guztiz ausazkoak (konprimiezinak) megabyte-ko tamaina du, errepikapenak dituzten datuetarako beti megabyte bat baino handiagoa da.
Baina datu-formatu moderno asko konprimiezinak dira eta horien bidez baliabideak behar dituen eskaner bat exekutatzen alferrikakoa eta xahutzea da, beraz, eskanerrak bi funtzionamendu modu erabiltzen ditu. Lehenik eta behin, errepikapen posibleak dituzten sorburu-testuaren atalak bilatzen dira; eragiketa hori ere metodo probabilistiko baten bidez egiten da eta oso azkar egiten da (4-6 GigaByte/seg-ko abiaduran). Bat-etortze posibleak dituzten eremuak eskaner nagusiak prozesatzen ditu.
Indizearen konpresioa ez da oso eraginkorra, bikoiztutako zatiak indizeekin ordezkatu behar dituzu eta indize-matrizeak nabarmen murrizten du konpresio-erlazioa.
Konpresio-erlazioa handitzeko, byte-kateen konbinazio osoak ez ezik, partzialak ere indexatzen dira, kateak bat datozen eta bat ez diren byteak dituenean. Horretarako, indize-formatuak bat-etortze-maskara eremu bat barne hartzen du, bi blokeren bat datozen byteak adierazten dituena. Are konpresio handiagoa lortzeko, indexatzea erabiltzen da partzialki bat datozen hainbat bloke uneko blokeari gainjartzeko.
Horrek guztiak ahalbidetu zuen PTT-Mid konpresorean hiztegi metodoa erabiliz egindako konpresoreen pareko konpresio-erlazioa lortzea, baina askoz azkarrago lan eginez.
Konpresio algoritmo berriaren abiadura
Konpresoreak cache memoriaren erabilera esklusiboarekin funtzionatzen badu (4 Megabyte behar dira hari bakoitzeko), orduan funtzionamendu-abiadura 700-2000 Megabyte/seg bitartekoa da. prozesadorearen nukleo bakoitzeko, konprimitzen den datu motaren arabera eta prozesadorearen funtzionamendu-maiztasunaren araberakoa gutxi.
Konpresorearen hari anitzeko ezarpenarekin, eskalagarritasun eraginkorra hirugarren mailako cachearen tamainaren arabera zehazten da. Esate baterako, 9 Megabyte-ko cache-memoria "ontzian" edukitzea, ez du balio bi konpresio hari baino gehiago abiarazteko; abiadura ez da handituko. Baina 20 Megabyte-ko cachearekin, dagoeneko bost konpresio hari exekutatu ditzakezu.
Gainera, RAMaren latentzia konpresorearen abiadura zehazten duen parametro garrantzitsu bihurtzen da. Algoritmoak OPrako ausazko sarbidea erabiltzen du, eta horietako batzuk ez dira cache memorian sartzen (% 10 inguru) eta inaktibo egon behar du, OPko datuen zain, eta horrek eragiketa-abiadura murrizten du.
Konpresorearen abiaduran eta datuen sarrera/irteera sistemaren funtzionamenduan nabarmen eragiten du. I/O blokearen eskaerak PUZaren datuen eskaerak, eta horrek konpresio abiadura murrizten du. Arazo hau garrantzitsua da ordenagailu eramangarrientzat eta mahaigainentzat; zerbitzarientzat ez da hain esanguratsua sistema-busen sarbide-kontrolerako unitate aurreratuagoa eta kanal anitzeko RAMagatik.
Artikuluko testuan zehar konpresioari buruz hitz egiten dugu; deskonpresioak artikulu honen esparrutik kanpo geratzen dira, “dena txokolatez estalita baitago”. Deskonpresioa askoz azkarragoa da eta I/O abiadurak mugatuta dago. Hari bakarreko nukleo fisiko batek 3-4 GB/seg deskonprimitzeko abiadura erraz eskaintzen du.
Deskonpresio-prozesuan bat-etortze-bilaketa-eragiketarik ez dagoelako gertatzen da hori, konpresioan prozesadorearen eta cache-memoriaren baliabide nagusiak "jaten" dituena.
Datu konprimituen biltegiratzearen fidagarritasuna
Datuen konpresioa (artxiboak) erabiltzen duen software klase osoaren izenak iradokitzen duen bezala, informazioa epe luzerako biltegiratzeko diseinatuta daude, ez urteetarako, mendeetan eta milurtekoetan baizik...
Biltegiratzean, biltegiratze euskarriak datu batzuk galtzen ditu, hona hemen adibide bat:
Informazio-eramaile “analogiko” honek mila urte ditu, zati batzuk galdu dira, baina orokorrean informazioa “irakurgarria” da...
Datu digitalak biltegiratzeko sistema modernoen eta horien euskarri digitalen fabrikatzaile arduratsuetako batek ere ez du datuen segurtasun osoa bermatzen 75 urte baino gehiagoz.
Eta hau arazo bat da, baina arazo atzeratua, gure ondorengoek konponduko dute...
Datu digitalak biltegiratzeko sistemek datuak gal ditzakete 75 urte igaro ondoren, datuetan akatsak edozein unetan ager daitezke, grabatzean ere, distortsio horiek gutxitzen saiatzen dira erredundantzia erabiliz eta akatsak zuzentzeko sistemekin zuzentzen. Erredundantzia- eta zuzenketa-sistemek ezin dute beti galdutako informazioa berreskuratu, eta hala egiten badute, ez dago bermerik zaharberritze-eragiketa behar bezala burutu zenik.
Eta hau ere arazo handia da, baina ez atzeratua, oraingoa baizik.
Datu digitalak artxibatzeko erabiltzen diren konpresore modernoak hiztegi-metodoaren hainbat aldaketetan eraikitzen dira, eta artxibo horietarako informazio zati bat galtzea gertaera larria izango da; egoera horretarako termino finkatu bat ere badago - "hautsita" artxibo bat. ...
Hiztegi-konpresioa duten artxiboetan informazioa biltegiratzeko fidagarritasun txikia konprimitutako datuen egiturarekin lotuta dago. Artxibo horretako informazioak ez du iturri-testua jasotzen, hiztegiko sarrera-kopuruak bertan gordetzen dira eta hiztegia bera dinamikoki aldatzen da uneko testu konprimituaren arabera. Artxibo-zati bat galdu edo hondatzen bada, ondorengo artxiboko sarrera guztiak ezin dira identifikatu ez edukiaren arabera ez hiztegiko sarreraren luzeraren arabera, ez baitago argi zein den hiztegiko sarrera-zenbakia.
Ezinezkoa da halako artxibo "hautsi" batetik informazioa berreskuratzea.
RTT algoritmoa konprimitutako datuak gordetzeko metodo fidagarriago batean oinarritzen da. Zatiak errepikatzeko indize metodoa erabiltzen du. Konpresioaren ikuspegi honek biltegiratze euskarrian informazioaren distortsioaren ondorioak minimizatzeko aukera ematen du, eta kasu askotan informazioa biltegiratzean sortutako distortsioak automatikoki zuzentzen ditu.
Hau da, indizearen konpresioaren kasuan artxibo-fitxategiak bi eremu dituelako:
- iturburu-testu eremu bat bertatik errepikatutako atalak kenduta;
- indize eremua.
Informazioa berreskuratzeko funtsezkoa den indize-eremua ez da tamaina handikoa eta bikoiztu egin daiteke datu fidagarriak gordetzeko. Beraz, iturburu-testuaren edo indize-matrizearen zati bat galdu arren, gainerako informazio guztia arazorik gabe berreskuratuko da, irudian bezala biltegiratze euskarri "analogiko" batekin.
Algoritmoaren desabantailak
Ez dago abantailarik desabantailarik gabe. Indizearen konpresioaren metodoak ez ditu errepikatzen diren sekuentzia laburrak konprimitzen. Hau indize metodoaren mugen ondorioz gertatzen da. Indizeek gutxienez 3 byteko tamaina dute eta 12 byteko tamaina izan dezakete. Errepikapen bat deskribatzen duen indizea baino tamaina txikiagoarekin aurkitzen bada, ez da kontuan hartuko, fitxategi konprimituan halako errepikapenak zenbateraino detektatzen diren ere.
Hiztegien konpresio metodo tradizionalak luzera motzeko errepikapen anitz konprimitzen ditu eta, beraz, indizearen konpresioa baino konpresio-erlazio handiagoa lortzen du. Egia da, hau prozesadore zentraleko karga handia dela eta lortzen da; hiztegi-metodoa indize-metodoa baino modu eraginkorragoan datuak konprimitzen hasteko, datuak prozesatzeko abiadura segundoko 10-20 megabyte-ra murriztu behar du errealean. CPU karga osoa duten informatika-instalazioak.
Abiadura baxu horiek onartezinak dira datuak biltegiratzeko sistema modernoentzat eta interes “akademikoagoa” dute praktikoa baino.
Informazioaren konpresio-maila nabarmen handituko da RTT algoritmoaren hurrengo aldaketan (RTT-Max), zeina dagoeneko garatzen ari den.
Beraz, beti bezala, jarraitzeko...
Iturria: www.habr.com