Den hÀr artikeln Àr den andra i serien om snabb datakompression. I den första artikeln beskrevs en kompressor som arbetar med en hastighet av 10 GB/s per processor kÀrna (minimalt komprimering, RTT-Min).
Denna kompressor har redan implementerats i utrustning för kriminaltekniska dubbletter för snabb komprimering av dumpningar av informationsbÀrare och för att öka motstÄndskraften hos kryptografi. Den kan Àven anvÀndas för komprimering av bilder av virtuella maskiner och svappfiler i RAM-minnet nÀr de lagras pÄ högpresterande SSD-enheter.
I den första artikeln tillkÀnnagavs ocksÄ utvecklingen av en komprimeringsalgoritm för att komprimera sÀkerhetskopior av HDD- och SSD-enheter (medelkomprimering, RTT-Mid) med avsevÀrt förbÀttrade komprimeringsparametrar. För nÀrvarande Àr denna kompressor helt fÀrdig och denna artikel handlar just om den.
Kompressorn som implementerar algoritmen RTT-Mid ger en komprimeringsgrad som Àr jÀmförbar med standardarkivator som WinRar och 7-Zip, som arbetar i snabbhetslÀge. Samtidigt Àr dess arbets hastighet minst en ordning högre.
Hastigheten för packning/uppackning av data Àr en kritisk parameter som avgör anvÀndningsomrÄdet för kompressionsteknologier. Det Àr osannolikt att nÄgon skulle komma pÄ tanken att komprimera en terabyte data med en hastighet av 10-15 Megabyte per sekund (det Àr just denna hastighet hos arkivator i standard komprimeringslÀge), eftersom det skulle ta nÀstan tjugo timmar med full processorladdning...
à andra sidan kan samma terabyte kopieras med hastigheter pÄ cirka 2-3 Gigabyte per sekund pÄ tio minuter.
DÀrför Àr komprimering av stora volymer information relevant om det utförs med en hastighet som inte Àr lÀgre Àn den verkliga in- och utmatningshastigheten. För moderna system Àr detta inte mindre Àn 100 Megabyte per sekund.
SÄdana hastigheter kan moderna kompressorer endast nÄ i "fast"-lÀge. Det Àr i detta aktuella lÀge vi kommer att göra en jÀmförelse av algoritmen RTT-Mid med traditionella kompressorer.
JÀmförande testning av den nya komprimeringsalgoritmen
Kompressorn RTT-Mid fungerade som en del av ett testprogram. I en verklig "arbets"-applikation arbetar den betydligt snabbare, dÀr anvÀnds multithreading effektivt och en "normal" kompilator, inte C#.
Eftersom de kompressorer som anvĂ€ndes i det jĂ€mförande testet baseras pĂ„ olika principer och olika typer av data komprimeras pĂ„ olika sĂ€tt, anvĂ€ndes metoden att mĂ€ta 'den genomsnittliga temperaturen pĂ„ sjukhuset' för att sĂ€kerstĂ€lla objektivitet i testetâŠ
En fil med sektordump av den logiska disken med operativsystemet Windows 10 skapades, vilket utgör en naturlig blandning av olika datastrukturer som faktiskt finns pÄ varje dator. Komprimering av denna fil möjliggör en jÀmförelse av hastighet och kompressionsgrad för den nya algoritmen med de mest avancerade kompressorerna som anvÀnds i moderna arkiverare.
HÀr Àr dumpfilen:
Dumpfilen komprimerades av kompressorerna RTT-Mid, 7-zip, WinRar. Kompressorerna WinRar och 7-zip stÀlldes in pÄ maximal arbetskapacitet.
Kompressorn arbetar 7-zip:
Den belastar processorn till 100%, med en genomsnittlig lÀshastighet av den ursprungliga dumpen pÄ cirka 60 Megabyte/s.
Kompressorn arbetar WinRar:
Situationen Àr liknande, processorbelastningen Àr nÀstan 100%, med en genomsnittlig lÀshastighet av dumpen pÄ cirka 125 Megabyte/s.
Som i det föregÄende fallet begrÀnsas arkiverarens hastighet av processorens kapacitet.
Nu körs testprogrammet för kompressorn RTT-Mid:
SkÀrmdumpen visar att processorn Àr belastad till 50% och Àr inaktiv resten av tiden, eftersom det inte finns nÄgot stÀlle att skriva ut de komprimerade data. Utdataklusteret (Disk 0) Àr nÀstan helt fullt. Hastigheten för datalÀsning (Disk 1) fluktuerar kraftigt, men ligger i genomsnitt över 200 Megabyte/s.
I det hÀr fallet begrÀnsas kompressorens hastighet av möjligheten att skriva de komprimerade data pÄ Disk 0.
Nu ser vi graden av komprimering av de resulterande arkiven:
Det Àr tydligt att kompressorn RTT-Mid var bÀst pÄ komprimering; arkivet skapat av den Àr 1,3 Gigabyte mindre Àn arkivet frÄn WinRar och 2,1 Gigabyte mindre Àn arkivet frÄn 7z.
Tiden som lagts ned pÄ att skapa arkivet:
- 7-zip â 26 minuter 10 sekunder;
- WinRar â 17 minuter 40 sekunder;
- RTT-Mid â 7 minuter 30 sekunder.
DĂ€rmed lyckades Ă€ven det testprogram som inte var optimerat, med hjĂ€lp av algoritmen RTT-Mid, att skapa ett arkiv mer Ă€n tvĂ„ och en halv gĂ„ng snabbare och arkivet blev betydligt mindre Ă€n konkurrenternasâŠ
De som inte tror pÄ skÀrmdumparna kan sjÀlva kontrollera deras Àkthet. Testprogrammet finns tillgÀngligt pÄ , ladda ner och kontrollera.
Men endast pÄ processorer som stöder AVX-2. Utan stöd för dessa instruktioner fungerar kompressorn inte, och testa inte algoritmen pÄ gamla AMD-processorer, de Àr lÄngsamma nÀr det gÀller att utföra AVX-kommandon...
Den anvÀnda komprimeringsmetoden
Algoritmen anvÀnder en metod för indexering av upprepande textfragment i bytesgranulering. Denna komprimeringsmetod Àr gammal, men har inte anvÀnts eftersom sökoperationen efter matchningar var mycket resurskrÀvande och tog betydligt lÀngre tid Àn att bygga en ordbok. SÄ algoritmen RTT-Mid Àr ett klassiskt exempel pÄ en "tillbakagÄng till framtiden"...
I RTT-kompressorn anvÀnds en unik snabb sökscanner för matchningar, det Àr just den som har möjliggjort att komprimeringsprocessen kan pÄskyndas. Scannern Àr egentillverkad, "det Àr min dyrgrip ...", "den kostar en hel del, eftersom den Àr helt handgjord" (skriven i assembler).
Matchningssökaren Àr genomförd med en tvÄnivÄ sannolikhetsschema; först scannas nÀrvaron av en "indikator" för matchning, och endast efter att "indikatorn" har identifierats i denna plats aktiveras proceduren för att upptÀcka den verkliga matchningen.
Fönstret för matchningssökning har en oförutsÀgbar storlek, beroende av graden av entropi i den bearbetade datablocket. För helt slumpmÀssiga (inte komprimerbara) data Àr storleken megabyte, medan data med upprepningar alltid har en storlek över en megabyte.
Men mÄnga moderna dataformat Àr inte komprimerbara, och att "köra" en resurskrÀvande scanner pÄ dem Àr meningslöst och slöseri, dÀrför finns det tvÄ arbetslÀgen i scannern. Först letas delar av den ursprungliga texten med möjliga upprepningar, denna operation utförs ocksÄ med en sannolikhetsmetod och utförs mycket snabbt (i hastighet av 4-6 Gigabyte/s). Sedan behandlas de delar med möjliga matchningar av den huvudsakliga scannern.
Indexkompression Àr inte sÀrskilt effektivt, man mÄste ersÀtta upprepande fragment med index, och indexmatrisen sÀnker kraftigt kompressionsförhÄllandet.
För att öka komprimeringsgraden indexeras inte bara fullstÀndiga matchningar av byte-strÀngar, utan ocksÄ partiella, nÀr strÀngen innehÄller matchande och icke-matchande byte. För detta inkluderar indexformatet ett fÀlt för matchningsmask som anger de matchande byte för tvÄ block. För Ànnu större komprimering anvÀnds indexering med överlappande flera delvis matchande block pÄ det nuvarande blocket.
Allt detta har gjort det möjligt att i kompressorn RTT-Mid uppnÄ en komprimeringsgrad som kan jÀmföras med kompressorer som anvÀnder den ordbaserade metoden, men som arbetar mycket snabbare.
Hastigheten pÄ den nya komprimeringsalgoritmen
Om kompressorn arbetar med monopoliserad anvÀndning av cache-minnet (4 Megabyte krÀvs för en trÄd), varierar hastigheten mellan 700-2000 Megabyte/sekund per processor-kÀrna beroende pÄ typen av komprimerade data och pÄverkas lite av processor-frekvensen.
Vid flertrÄdad implementering av kompressorn bestÀms den effektiva skalbarheten av mÀngden tredje nivÄns cache-minne. Till exempel, med 9 Megabyte cache-minne Àr det meningslöst att starta mer Àn tvÄ komprimeringsströmmar eftersom hastigheten inte kommer att öka. Men med 20 Megabyte cache kan man redan starta fem komprimeringsströmmar.
En annan betydande parameter som bestÀmmer kompressorns hastighet Àr latensen i det operativa minnet. Algoritmen anvÀnder slumpvisa Ätkomster till RAM, varav en del inte nÄr cache-minnet (ungefÀr 10%), och den mÄste vÀnta pÄ data frÄn RAM, vilket sÀnker hastigheten.
Systemarbetet med in- och utdata pÄverkar ocksÄ avsevÀrt hastigheten pÄ kompressorn. FrÄgor till RAM frÄn in- och utdata blockerar Ätkomsten till data frÄn CPU, vilket ocksÄ sÀnker komprimeringshastigheten. Detta problem Àr betydande för bÀrbara datorer och stationÀra datorer, för servrar det Àr mindre betydande tack vare en mer avancerad kontrollstruktur för Ätkomst till systembussen och flerkanaligt RAM.
Ăverallt i texten i artikeln talas det om komprimering, medan dekompression ligger utanför denna artikel eftersom "allt Ă€r i sin ordning". Dekompression utförs betydligt snabbare och begrĂ€nsas av in- och utdatahastigheten. Ett fysiskt kĂ€rna i en enda trĂ„d kan enkelt uppnĂ„ upplösningshastigheter pĂ„ 3-4 Gigabyte/s.
Detta beror pÄ avsaknaden av matchningssökning i dekompressionsprocessen, som "Àter upp" huvuddelen av CPU- och cache-minnesresurserna vid komprimering.
Tillförlitlighet i lagring av komprimerade data
Som titeln pÄ hela klassen av programvaror som anvÀnder datakomprimering (arkivverktyg) antyder, Àr de avsedda för lÄngsiktig lagring av information, inte för Är utan för Ärhundraden och Ärtusenden...
Under lagringstiden förlorar lagringsmedia en del av informationen, hÀr Àr ett exempel:
Detta "analoga" lagringsmedium Àr tusen Är gammalt, vissa fragment har gÄtt förlorade, men i stort sett Àr informationen "lÀsbar"...
Ingen av de ansvarsfulla tillverkarna av moderna digitala lagringssystem och digitala medier erbjuder garantier för fullstÀndig informationsbevarande i mer Àn 75 Är.
Och det Àr ett problem, men ett uppskjutet problem, som vÄra efterkommande kommer att behöva lösa...
Digitala datalagringssystem kan förlora data inte bara efter 75 Är; databasfel kan intrÀffa nÀr som helst, Àven under deras inspelning. Dessa förvrÀngningar försöker man minimera genom att anvÀnda redundans och korrigera med felkorrigeringssystem. Redundans och felkorrigeringssystem kan sÀllan ÄterstÀlla förlorad information, och om de gör det, finns det inga garantier för att ÄterstÀllningsoperationen var korrekt.
Och detta Àr ocksÄ ett stort problem, men inte uppskjutet, utan ett aktuellt.
Moderna kompressorer som anvĂ€nds för arkivering av digitala data Ă€r baserade pĂ„ olika modifieringar av ordningsmetoden, och för sĂ„dana arkiv Ă€r förlust av information ett katastrofalt hĂ€ndelse; det finns till och med en etablerad term för en sĂ„dan situation â "korrupt" arkiv...
Den lÄga tillförlitligheten vid lagring av information i arkiv med ordbaserad kompression beror pÄ strukturen hos de komprimerade uppgifterna. Informationen i ett sÄdant arkiv innehÄller inte den ursprungliga texten, utan istÀllet lagras poster med referenser i en ordbok som dynamiskt modifieras av den aktuella text som komprimeras. Vid förlust eller förvanskning av en del av arkivet blir det omöjligt att identifiera alla följande poster varken efter innehÄll eller lÀngd pÄ referensen i ordboken, eftersom det inte gÄr att förstÄ vad referensen motsvarar.
Det Àr omöjligt att ÄterstÀlla information frÄn ett sÄdant "kaputt" arkiv.
RTT-algoritmen bygger pÄ en mer tillförlitlig metod för lagring av komprimerade data. Den anvÀnder en indexmetod för att hantera upprepade fragment. Denna metod för kompression minimerar effekterna av information som förvanskas pÄ lagringsmedium och korrigerar automatiskt förvanskningar som uppstÄr vid lagring av information i mÄnga fall.
Detta beror pÄ att den arkiverade filen vid indexkompression innehÄller tvÄ fÀlt:
- ett fÀlt för ursprunglig text med borttagna upprepningar;
- ett indexfÀlt.
IndexfÀltet, som Àr avgörande för att ÄterstÀlla informationen, Àr inte stort till storleken och kan dupliceras för att sÀkerstÀlla tillförlitligheten i datalagringen. DÀrför, Àven om en del av den ursprungliga texten eller indexmatrisen förloras, kan all annan information ÄterstÀllas utan problem, precis som pÄ en bild med ett "analogt" informationslagringsmedium.
Nackdelar med algoritmen
Det finns inget utan nackdelar. Indexmetoden för kompression komprimerar inte upprepande sekvenser av liten lÀngd. Detta beror pÄ begrÀnsningarna hos indexmetoden. Indexen Àr minst 3 byte lÄnga och kan vara upp till 12 byte. Om det finns upprepningar med en storlek mindre Àn den som beskrivs av dess index, beaktas de inte, oavsett hur ofta sÄdana upprepningar förekommer i den komprimerade filen.
Den traditionella ordboksmetoden för komprimering komprimerar effektivt flera korta upprepningar och nÄr dÀrför en högre komprimeringsgrad Àn indexkomprimering. Detta uppnÄs dock pÄ bekostnad av en hög belastning pÄ CPU:n, vilket innebÀr att ordboksmetoden mÄste sÀnka databehandlingshastigheten till 10-20 megabyte per sekund pÄ verkliga berÀkningsinstallationer vid full CPU-belastning för att effektivt kunna komprimera data jÀmfört med indexmetoden.
SÄdana lÄga hastigheter Àr oacceptabla för moderna datalagringssystem och utgör mer av ett 'akademiskt' intresse Àn ett praktiskt.
Graden av informationskomprimering kommer att öka avsevÀrt i nÀsta modifiering av RTT-algoritmen (RTT-Max), som redan Àr under utveckling.
SĂ„ som alltid, fortsĂ€ttning följerâŠ
KĂ€lla: habr.com
