Dit artikel is al it twadde yn it ûnderwerp fan kompresje fan hege snelheid. It earste artikel beskreau in kompressor dy't wurket mei in snelheid fan 10 GB / sek. per prosessor kearn (minimum kompresje, RTT-Min).
Dizze kompressor is al ymplementearre yn 'e apparatuer fan forensyske duplikators foar kompresje mei hege snelheid fan opslachmediadumps en it ferbetterjen fan' e sterkte fan kryptografy; it kin ek brûkt wurde om ôfbyldings fan firtuele masines en RAM-swapbestannen te komprimearjen by it bewarjen fan se op hege snelheid SSD-skiven.
It earste artikel kundige ek de ûntwikkeling oan fan in kompresjealgoritme foar it komprimearjen fan reservekopyen fan HDD- en SSD-skiifdriuwen (medium kompresje, RTT-Mid) mei signifikant ferbettere parameters foar gegevenskompresje. Tsjintwurdich is dizze kompressor folslein klear en dit artikel giet deroer.
In kompressor dy't it RTT-Mid-algoritme ymplementearret, leveret in kompresjeferhâlding te fergelykjen mei standert archivers lykas WinRar, 7-Zip, dy't operearje yn hege snelheidsmodus. Tagelyk is syn wurksnelheid op syn minst in oarder fan grutte heger.
De snelheid fan it ynpakken / útpakke fan gegevens is in krityske parameter dy't it tapassingsgebiet fan kompresjetechnologyen bepaalt. It is net wierskynlik dat immen soe tinke oan it komprimearjen fan in terabyte oan gegevens mei in snelheid fan 10-15 MegaBytes per sekonde (dit is krekt de snelheid fan archivers yn standert kompresjemodus), om't it hast tweintich oeren soe nimme mei in folsleine prosessorlading. .
Oan 'e oare kant kin deselde terabyte kopieare wurde mei snelheden fan' e oarder fan 2-3Gigabytes per sekonde yn sawat tsien minuten.
Dêrom is kompresje fan ynformaasje mei grut folume wichtich as it wurdt útfierd mei in snelheid net leger as de snelheid fan echte ynfier / útfier. Foar moderne systemen is dit op syn minst 100 Megabytes per sekonde.
Moderne compressors kinne produsearje sokke snelheden allinnich yn "flugge" modus. It is yn dizze hjoeddeistige modus dat wy it RTT-Mid-algoritme sille fergelykje mei tradisjonele kompressors.
Fergelykjende testen fan in nij kompresjealgoritme
De RTT-Mid-kompressor wurke as ûnderdiel fan it testprogramma. Yn in echte "wurkjende" applikaasje wurket it folle flugger, it brûkt multithreading wiis en brûkt in "normale" kompilator, net C #.
Sûnt de kompressors dy't brûkt wurde yn 'e ferlykjende test binne boud op ferskate prinsipes en ferskillende soarten gegevens komprimearje oars, foar de objektiviteit fan' e test, waard de metoade foar it mjitten fan 'e "gemiddelde temperatuer yn it sikehûs" brûkt ...
In sektor-by-sektor dumptriem fan in logyske skiif mei it Windows 10 bestjoeringssysteem is makke; dit is it meast natuerlike mingsel fan ferskate gegevensstruktueren dy't eins beskikber binne op elke kompjûter. Troch dit bestân te komprimearjen kinne jo de snelheid en kompresjegraad fan it nije algoritme fergelykje mei de meast avansearre kompresjers dy't brûkt wurde yn moderne archivers.
Hjir is it dumpbestân:
It dumpbestân waard komprimearre mei PTT-Mid, 7-zip, en WinRar-kompressors. De WinRar en 7-zip compressor waarden ynsteld op maksimale snelheid.
Kompressor draait 7-zip:
It laadt de prosessor mei 100%, wylst de gemiddelde snelheid fan it lêzen fan 'e orizjinele dump sawat 60 MegaBytes / sek is.
Kompressor draait Winrar:
De situaasje is fergelykber, de prosessorlading is hast 100%, de gemiddelde dumplêssnelheid is sawat 125 Megabytes / sek.
Lykas yn it foarige gefal is de snelheid fan 'e archiver beheind troch de mooglikheden fan' e prosessor.
It kompressortestprogramma rint no RTT-Mid:
It skermôfbylding lit sjen dat de prosessor op 50% wurdt laden en de rest fan 'e tiid idle is, om't d'r nergens is om de komprimearre gegevens op te laden. De data upload skiif (skiif 0) is hast folslein laden. De gegevens lêzen snelheid (skiif 1) fariearret sterk, mar gemiddeld mear as 200 MegaBytes / sek.
De snelheid fan 'e kompressor wurdt yn dit gefal beheind troch de mooglikheid om komprimearre gegevens op Disk 0 te skriuwen.
No de kompresjeferhâlding fan 'e resultearjende argiven:
It kin sjoen wurde dat de RTT-Mid-kompressor it bêste wurk fan kompresje die; it argyf dat it makke wie 1,3 GigaBytes lytser dan it WinRar-argyf en 2,1 GigaBytes lytser dan it 7z-argyf.
Tiid bestege oan it meitsjen fan it argyf:
- 7-zip - 26 minuten 10 sekonden;
- WinRar - 17 minuten 40 sekonden;
- RTT-Mid - 7 minuten 30 sekonden.
Sa koe sels in test, net-optimisearre programma, mei it RTT-Mid-algoritme, in argyf mear as twa en in heal kear rapper meitsje, wylst it argyf signifikant lytser bliek te wêzen as dat fan syn konkurrinten ...
Dejingen dy't de skermôfbyldings net leauwe, kinne har autentisiteit sels kontrolearje. It testprogramma is beskikber by , download en kontrolearje.
Mar allinich op processors mei AVX-2-stipe, sûnder stipe foar dizze ynstruksjes wurket de kompressor net, en test it algoritme net op âldere AMD-processors, se binne traach yn termen fan it útfieren fan AVX-ynstruksjes ...
Kompresje metoade brûkt
It algoritme brûkt in metoade foar it yndeksearjen fan werhelle tekstfragminten yn bytegranulariteit. Dizze kompresjemetoade is al lang bekend, mar waard net brûkt om't de oerienkommende operaasje tige djoer wie yn termen fan de nedige middels en folle mear tiid frege as it bouwen fan in wurdboek. Dat it RTT-Mid-algoritme is in klassyk foarbyld fan ferpleatse "werom nei de takomst" ...
De PTT-kompressor brûkt in unike sykmasine mei hege snelheid, wêrtroch't wy it kompresjeproses kinne fersnelle. In selsmakke scanner, dit is "myn sjarme ...", "it is frij djoer, want it is folslein mei de hân makke" (skreaun yn assembler).
De wedstryd sykje scanner wurdt makke neffens in twa-nivo probabilistysk skema: earst wurdt de oanwêzigens fan in "teken" fan in wedstriid skansearre, en pas nei't it "teken" is identifisearre op dit plak, de proseduere foar it opspoaren fan in echte wedstriid is begûn.
It finster foar wedstriidsykjen hat in ûnfoarspelbere grutte, ôfhinklik fan de graad fan entropy yn it ferwurke gegevensblok. Foar folslein willekeurige (ynkompressibele) gegevens hat it in grutte fan megabytes, foar gegevens mei werhellingen is it altyd grutter as in megabyte.
Mar in protte moderne dataformaten binne ynkomprimerber en it útfieren fan in boarne-yntinsive scanner troch har is nutteloos en fergriemend, sadat de scanner twa bestjoeringsmodi brûkt. Earst wurde seksjes fan 'e boarnetekst socht mei mooglike werhellingen; dizze operaasje wurdt ek útfierd mei in probabilistyske metoade en wurdt tige fluch útfierd (mei in snelheid fan 4-6 GigaBytes / sek). De gebieten mei mooglike oerienkomsten wurde dan ferwurke troch de haadscanner.
Yndekskompresje is net heul effisjint, jo moatte dûbele fragminten ferfange mei yndeksen, en de yndeksarray fermindert de kompresjeferhâlding signifikant.
Om de kompresjeferhâlding te ferheegjen, wurde net allinich folsleine oerienkomsten fan byte-strings yndeksearre, mar ek foar in part, as de tekenrige oerienkommende en ongeëvenaarde bytes befettet. Om dit te dwaan, omfettet it yndeksformaat in wedstriidmaskerfjild dat de oerienkommende bytes fan twa blokken oanjout. Foar noch gruttere kompresje wurdt yndeksearring brûkt om ferskate foar in part oerienkommende blokken op it aktuele blok oer te setten.
Dit alles makke it mooglik om yn 'e PTT-Mid-kompressor in kompresjeferhâlding te krijen dy't fergelykber is mei kompressors makke mei de wurdboekmetoade, mar wurkje folle flugger.
Snelheid fan it nije kompresjealgoritme
As de compressor wurket mei eksklusyf gebrûk fan cache-ûnthâld (4 Megabytes binne fereaske per thread), dan rint de bestjoeringssnelheid fan 700-2000 Megabytes / sek. per prosessor kearn, ôfhinklik fan it type gegevens wurdt komprimearre en hinget net folle op 'e operaasje frekwinsje fan' e prosessor.
Mei in multi-threaded ymplemintaasje fan de compressor, effektive scalability wurdt bepaald troch de grutte fan it tredde nivo cache. Bygelyks, it hawwen fan 9 MegaBytes fan cache-ûnthâld "oan board", hat gjin punt om mear dan twa kompresje-threads te lansearjen; de snelheid sil hjirfan net tanimme. Mar mei in cache fan 20 Megabytes kinne jo al fiif kompresje-threads útfiere.
Ek wurdt de latency fan 'e RAM in wichtige parameter dy't de snelheid fan' e compressor bepaalt. It algoritme brûkt willekeurige tagong ta de OP, wêrfan guon net yn it cache-ûnthâld komme (sawat 10%) en it moat idle, wachtsje op gegevens fan 'e OP, wat de snelheid fan operaasje ferminderet.
Signifikant beynfloedet de compressor snelheid en de wurking fan de gegevens input / output systeem. Fersiken nei de OP fan I / O-blokoanfragen foar gegevens fan 'e CPU, dy't ek de kompresjesnelheid ferminderet. Dit probleem is wichtich foar laptops en buroblêden; foar servers is it minder wichtich troch in mear avansearre systeembus tagongskontrôle-ienheid en multi-kanaal RAM.
Yn 'e hiele tekst yn it artikel prate wy oer kompresje; dekompresje bliuwt bûten it berik fan dit artikel, om't "alles is bedekt mei sûkelade". Dekompresje is folle flugger en wurdt beheind troch I / O snelheid. Ien fysike kearn yn ien tried leveret maklik útpakkesnelheden fan 3-4 GB / sek.
Dit is te tankjen oan it ûntbrekken fan in wedstrydsykaksje tidens it dekompresjeproses, dy't de wichtichste boarnen fan 'e prosessor en cache-ûnthâld by kompresje "fet".
Betrouberens fan komprimearre gegevens opslach
Lykas de namme fan 'e hiele klasse fan software dy't gegevenskompresje (archivers) brûkt suggerearret, binne se ûntwurpen foar lange termyn opslach fan ynformaasje, net foar jierren, mar foar ieuwen en milennia ...
Tidens opslach ferlieze opslachmedia wat gegevens, hjir is in foarbyld:
Dizze "analoge" ynformaasjedrager is tûzen jier âld, guon fragminten binne ferlern gien, mar yn 't algemien is de ynformaasje "lêsber" ...
Gjin fan 'e ferantwurdlike fabrikanten fan moderne digitale gegevens opslach systemen en digitale media foar harren jout garânsjes fan folsleine gegevens feiligens foar mear as 75 jier.
En dit is in probleem, mar in útsteld probleem, ús neiteam sil it oplosse ...
Digitale gegevens opslachsystemen kinne gegevens ferlieze net allinich nei 75 jier, flaters yn gegevens kinne op elk momint ferskine, sels tidens har opname, se besykje dizze fersteuringen te minimalisearjen troch oerstalligens te brûken en se te korrigearjen mei flaterkorreksjesystemen. Redundancy- en korreksje systemen kinne net altyd weromsette ferlerne ynformaasje, en as se dogge, der is gjin garânsje dat de restauraasje operaasje waard klear korrekt.
En dit is ek in grut probleem, mar net in útstelde, mar in aktuele.
Moderne kompressors dy't brûkt wurde foar it argivearjen fan digitale gegevens binne boud op ferskate wizigingen fan 'e wurdboekmetoade, en foar sokke argiven sil it ferlies fan in stikje ynformaasje in fataal barren wêze; d'r is sels in fêststelde term foar sa'n situaasje - in "brutsen" argyf ...
De lege betrouberens fan it opslaan fan ynformaasje yn argiven mei wurdboekkompresje is ferbûn mei de struktuer fan 'e komprimearre gegevens. De ynformaasje yn sa'n argyf befettet de boarnetekst net, de nûmers fan yngongen yn it wurdboek wurde dêr opslein, en it wurdboek sels wurdt dynamysk oanpast troch de aktuele komprimearre tekst. As in argyffragmint ferlern giet of beskeadige is, kinne alle folgjende argyfyngongen noch net identifisearre wurde troch de ynhâld noch oan de lingte fan de yngong yn it wurdboek, om't net dúdlik is wêrmei it wurdboekyngongsnûmer oerienkomt.
It is ûnmooglik om ynformaasje te herstellen fan sa'n "brutsen" argyf.
It RTT-algoritme is basearre op in mear betroubere metoade foar it bewarjen fan komprimearre gegevens. It brûkt de yndeksmetoade om fragminten te werheljen. Dizze oanpak fan kompresje kinne jo minimalisearje de gefolgen fan ferfoarming fan ynformaasje op it opslach medium, en yn in protte gefallen automatysk korrigearje ferfoarming dy't ûntstienen tidens ynformaasje opslach.
Dit komt troch it feit dat it argyfbestân yn it gefal fan yndekskompresje twa fjilden befettet:
- in boarnetekstfjild mei werhelle seksjes derút fuorthelle;
- yndeks fjild.
It yndeksfjild, dat kritysk is foar ynformaasjeherstel, is net grut yn grutte en kin duplikearre wurde foar betroubere gegevensopslach. Dêrom, sels as in fragmint fan 'e boarne tekst of yndeks array is ferlern, alle oare ynformaasje wurdt weromset sûnder problemen, lykas yn 'e foto mei in "analoge" opslach medium.
Neidielen fan it algoritme
D'r binne gjin foardielen sûnder neidielen. De yndekskompresjemetoade komprimearret gjin koarte werheljende sekwinsjes. Dit komt troch de beheiningen fan 'e yndeksmetoade. Yndeksen binne op syn minst 3 bytes yn grutte en kinne oant 12 bytes grut wêze. As in werhelling tsjinkomt mei in lytsere grutte as de yndeks dy't it beskriuwt, dan wurdt der gjin rekken mei hâlden, hoe faak oft sokke werhellingen ek ûntdutsen wurde yn 'e komprimearre triem.
De tradisjonele wurdboekkompresjemetoade komprimearret effektyf meardere werhellingen fan koarte lingte en berikt dêrtroch in hegere kompresjeferhâlding dan yndekskompresje. Wier, dit wurdt berikt troch de hege lading op 'e sintrale prosessor; om de wurdboekmetoade te begjinnen om gegevens effisjinter te komprimearjen as de yndeksmetoade, moat it de gegevensferwurkingssnelheid ferminderje nei 10-20 megabytes per sekonde op echte komputerynstallaasjes mei in folsleine CPU-load.
Sokke lege snelheden binne net akseptabel foar moderne data-opslachsystemen en binne fan mear "akademysk" belang dan praktysk.
De mjitte fan ynformaasjekompresje sil signifikant ferhege wurde yn 'e folgjende wiziging fan it RTT-algoritme (RTT-Max), dat al yn ûntwikkeling is.
Dat, lykas altyd, wurdt ferfolge ...
Boarne: www.habr.com