Denne artikel er allerede den anden i emnet højhastighedsdatakomprimering. Den første artikel beskrev en kompressor, der arbejder med en hastighed på 10 Gbytes/sek. pr. processorkerne (minimum komprimering, RTT-Min).
Denne kompressor er allerede blevet implementeret i retsmedicinske duplikatorer til højhastighedskomprimering af lagermediedumps og styrkelse af kryptografisk styrke. Det kan også bruges til at komprimere virtuelle maskine-billeder og RAM-swap-filer, når du gemmer dem på højhastigheds SSD-drev.
Den første artikel annoncerede også udviklingen af en komprimeringsalgoritme til at komprimere sikkerhedskopier af HDD- og SSD-diskdrev (medium komprimering, RTT-Mid) med væsentligt forbedrede datakomprimeringsparametre. Denne kompressor er nu helt klar, og denne artikel handler om det.
Kompressoren, der implementerer RTT-Mid-algoritmen, giver et komprimeringsniveau, der kan sammenlignes med standardarkivere som WinRar, 7-Zip, der arbejder i højhastighedstilstand. Samtidig er dens driftshastighed mindst en størrelsesorden højere.
Hastigheden af datapakning/udpakning er en kritisk parameter, der bestemmer anvendelsesområdet for kompressionsteknologier. Det er usandsynligt, at nogen ville finde på at komprimere en terabyte data med en hastighed på 10-15 megabyte i sekundet (dette er hastigheden for arkivere i standardkomprimeringstilstand), fordi dette ville kræve næsten tyve timer med en fuld processorbelastning...
På den anden side kan den samme terabyte kopieres med hastigheder på omkring 2-3 Gigabyte i sekundet på omkring ti minutter.
Derfor er komprimering af store mængder information relevant, hvis den udføres med en hastighed, der ikke er lavere end hastigheden af faktisk input/output. For moderne systemer er dette mindst 100 megabyte pr. sekund.
Moderne kompressorer kan kun producere sådanne hastigheder i "hurtig" tilstand. Det er i denne nuværende tilstand, at vi vil sammenligne RTT-Mid-algoritmen med traditionelle kompressorer.
Sammenlignende test af den nye kompressionsalgoritme
RTT-Mid kompressoren blev brugt som en del af et testprogram. I et rigtigt "fungerende" program virker det meget hurtigere, det bruger multithreading korrekt og bruger en "normal" compiler, ikke C#.
Da kompressorerne brugt i den sammenlignende test er bygget på forskellige principper og komprimerer forskellige typer data forskelligt, blev målemetoden "gennemsnitstemperatur på hospitalet" brugt for at sikre objektiviteten af testen...
En sektor-for-sektor dumpfil af en logisk disk med Windows 10-operativsystemet blev oprettet, dette er den mest naturlige blanding af forskellige datastrukturer, der faktisk findes på hver computer. Komprimering af denne fil vil give os mulighed for at sammenligne hastigheden og kompressionsforholdet for den nye algoritme med de mest avancerede kompressorer, der bruges i moderne arkivere.
Her er dump-filen:
Dumpfilen blev komprimeret ved hjælp af kompressorerne RTT-Mid, 7-zip, WinRar. WinRar og 7-zip kompressorer blev indstillet til maksimal hastighed.
Kompressoren virker 7-zip:
Den belaster processoren med 100 %, mens den gennemsnitlige hastighed for at læse den originale dump er omkring 60 MegaBytes/sek.
Kompressoren virker WinRAR:
Situationen er den samme, processorbelastningen er næsten 100%, den gennemsnitlige dump-læsehastighed er omkring 125 megabyte/sek.
Som i det foregående tilfælde er arkiveringshastigheden begrænset af processorens muligheder.
Kompressortestprogrammet kører nu. RTT-Mid:
Skærmbilledet viser, at processoren er indlæst med 50% og er inaktiv resten af tiden, fordi der ikke er nogen steder at aflæse de komprimerede data. Datadump-disken (Disk 0) er næsten fuldstændig indlæst. Datalæsehastigheden (Disk 1) svinger meget, men i gennemsnit er den mere end 200 Megabyte/sek.
Kompressorens driftshastighed er i dette tilfælde begrænset af evnen til at skrive komprimerede data til Disk 0.
Nu er komprimeringsforholdet for de resulterende arkiver:
Det er klart, at RTT-Mid-kompressoren klarede sig bedst i kompression; arkivet, det oprettede, var 1,3 Gigabyte mindre end WinRar-arkivet og 2,1 Gigabyte mindre end 7z-arkivet.
Tid brugt på at oprette arkivet:
- 7-zip – 26 minutter 10 sekunder;
- WinRar – 17 minutter 40 sekunder;
- RTT-Mid – 7 minutter 30 sekunder.
Således var selv et test, ikke-optimeret program, ved hjælp af RTT-Mid-algoritmen, i stand til at oprette et arkiv mere end to en halv gange hurtigere, mens arkivet viste sig at være væsentligt mindre end konkurrenternes...
De, der ikke tror på skærmbillederne, kan selv tjekke deres ægthed. Testprogrammet findes på , download og tjek.
Men kun på processorer med AVX-2 support, uden understøttelse af disse instruktioner virker kompressoren ikke, og test ikke algoritmen på gamle AMD processorer, de er langsomme til at udføre AVX instruktioner...
Den anvendte kompressionsmetode
Algoritmen bruger en metode til at indeksere gentagne tekstfragmenter i bytegranularitet. Denne komprimeringsmetode har været kendt i lang tid, men blev ikke brugt, fordi matchningsoperationen var meget ressourcekrævende og krævede meget mere tid end at bygge en ordbog. Så RTT-Mid-algoritmen er et klassisk eksempel på "tilbage til fremtiden"-bevægelse...
RTT-kompressoren bruger en unik high-speed match-scanner, som gør det muligt at accelerere kompressionsprocessen. En selvfremstillet scanner, dette er "min skat...", "det er ikke billigt, fordi det er fuldstændig håndlavet" (skrevet i assembler).
Matchsøgningsscanneren implementeres ved hjælp af et to-niveaus sandsynlighedsskema: Først scannes tilstedeværelsen af et match "tegn", og først efter at "tegnet" er opdaget på dette sted, lanceres proceduren til at detektere et rigtigt match.
Søgevinduet for matches har en uforudsigelig størrelse, afhængig af graden af entropi i den datablok, der behandles. For helt tilfældige (ukomprimerbare) data har den en størrelse på megabyte, for data med gentagelser har den altid en størrelse større end en megabyte.
Men mange moderne dataformater er ukomprimerbare, og at køre en ressourcekrævende scanner gennem dem er ubrugelig og spild, så scanneren bruger to driftstilstande. Først søges der efter afsnit af kildeteksten med mulige gentagelser; denne operation udføres også ved hjælp af en probabilistisk metode og udføres meget hurtigt (med en hastighed på 4-6 Gigabyte/sek.). Områder med mulige matchninger behandles derefter af hovedscanneren.
Indekskomprimering er ikke særlig effektiv, det er nødvendigt at erstatte gentagne fragmenter med indekser, og indeksarrayet reducerer komprimeringsforholdet betydeligt.
For at øge graden af komprimering indekseres ikke kun komplette matches af byte-strenge, men også delvise, når strengen indeholder matchede og umatchede bytes. Til dette formål inkluderer indeksformatet et matchmaskefelt, der angiver de matchende bytes af to blokke. For endnu større komprimering bruges indeksering med overlejring af flere delvist matchende blokke på den aktuelle blok.
Alt dette gjorde det muligt i RTT-Mid-kompressoren at opnå et kompressionsforhold, der kan sammenlignes med kompressorer fremstillet ved hjælp af ordbogsmetoden, men som arbejder meget hurtigere.
Hastigheden af den nye kompressionsalgoritme
Hvis kompressoren kører med eksklusiv brug af cache-hukommelse (4 megabyte kræves pr. stream), så svinger driftshastigheden i området 700-2000 megabyte/sek. processorkerne afhængig af typen af data, der komprimeres, og afhænger kun lidt af processorens driftsfrekvens.
Når du implementerer en multithreaded-kompressor, bestemmes den effektive skalerbarhed af størrelsen på tredje-niveau-cachen. For eksempel med 9 megabytes cache-hukommelse "ombord" er det ingen mening i at køre mere end to komprimeringsstrømme; hastigheden vil ikke stige herfra. Men med en cache på 20 megabyte kan du allerede køre fem komprimeringsstreams.
Også latensen af RAM bliver en vigtig parameter, der bestemmer kompressorens hastighed. Algoritmen bruger tilfældig adgang til RAM'en, hvoraf nogle ikke kommer ind i cachehukommelsen (ca. 10%), og den skal stå inaktiv og vente på data fra RAM'en, hvilket reducerer driftshastigheden.
I/O-systemet påvirker også kompressorhastigheden betydeligt. I/O-anmodninger til RAM-blokering af CPU-dataanmodninger, hvilket også reducerer kompressionshastigheden. Dette problem er betydeligt for bærbare og stationære computere. servere Det er mindre betydningsfuldt på grund af en mere avanceret systembusadgangskontrolenhed og flerkanals RAM.
Gennem hele artiklens tekst diskuteres komprimering; dekompression forbliver uden for denne artikels omfang, da alt er "i chokolade" der. Dekompression udføres meget hurtigere og er begrænset af input/output-hastigheden. Én fysisk kerne i én tråd giver let dekompressionshastigheder på niveauet 3-4 Gigabyte/sek.
Dette skyldes fraværet af en matchsøgningsoperation under udpakningsprocessen, som "spiser" de vigtigste ressourcer i processoren og cachehukommelsen under komprimering.
Pålidelighed af lagring af komprimerede data
Som det følger af navnet på hele klassen af softwareværktøjer, der bruger datakomprimering (arkivere), er de designet til langtidslagring af information, ikke i årevis, men i århundreder og årtusinder...
Under lagring mister lagringsmedier nogle af deres data, her er et eksempel:
Denne "analoge" informationsbærer er tusind år gammel, nogle fragmenter går tabt, men generelt er informationen "læselig"...
Ingen af de ansvarlige producenter af moderne digitale datalagringssystemer og digitale medier til dem giver garantier for fuldstændig datasikkerhed i mere end 75 år.
Og dette er et problem, men et udskudt problem, vores efterkommere vil løse det...
Digitale datalagringssystemer kan miste data ikke kun efter 75 år, datafejl kan opstå når som helst, selv mens de bliver optaget, og disse forvrængninger forsøges minimeret ved at bruge redundans og korrektion af fejlkorrektionssystemer. Redundans- og korrektionssystemer kan ikke altid gendanne tabte informationer, og selvom de gør det, er der ingen garanti for, at gendannelsesoperationen blev udført korrekt.
Og dette er også et stort problem, men ikke et udskudt, men et aktuelt.
Moderne kompressorer, der bruges til at arkivere digitale data, er bygget på forskellige modifikationer af ordbogsmetoden, og for sådanne arkiver ville tabet af et fragment af information være en fatal begivenhed; der er endda en etableret betegnelse for en sådan situation - et "brudt" arkiv...
Lav pålidelighed af lagring af information i arkiver med ordbogskomprimering er forbundet med strukturen af komprimerede data. Oplysningerne i et sådant arkiv indeholder ikke den originale tekst; den gemmer antallet af poster i ordbogen, og selve ordbogen modificeres dynamisk af den aktuelle komprimerede tekst. Hvis et fragment af et arkiv går tabt eller forvansket, kan alle efterfølgende optegnelser af arkivet ikke identificeres hverken efter indhold eller længden af posten i ordbogen, da det er uklart, hvad ordbogsoptegnelsens nummer svarer til.
Det er umuligt at gendanne information fra et sådant "brudt" arkiv.
RTT-algoritmen er bygget på en mere pålidelig metode til lagring af komprimerede data. Den bruger en indeksmetode til at tage højde for gentagne fragmenter. Denne tilgang til komprimering giver os mulighed for at minimere konsekvenserne af informationsforvrængning på lagringsmediet, og i mange tilfælde automatisk korrigere forvrængninger, der opstår under informationslagring.
Dette skyldes, at arkivfilen i tilfælde af indekskomprimering indeholder to felter:
- kildetekstfeltet med gentagelsessektionerne fjernet fra det;
- indeksfelt.
Indeksfeltet, som er kritisk for datagendannelse, er ikke stort i størrelse og kan duplikeres for pålidelig datalagring. Derfor, selvom et fragment af den originale tekst eller indeks-array går tabt, vil al anden information blive gendannet uden problemer, som på billedet med et "analogt" lagringsmedium.
Ulemper ved algoritmen
Der er ingen fordele uden ulemper. Indekskomprimeringsmetoden komprimerer ikke gentagne sekvenser med kort længde. Dette skyldes indeksmetodens begrænsninger. Indekser er mindst 3 bytes store og kan være op til 12 bytes store. Hvis der stødes på en gentagelse, der er mindre i størrelse end indekset, der beskriver den, tages der ikke højde for det, uanset hvor ofte sådanne gentagelser detekteres i den komprimerede fil.
Den traditionelle ordbogskomprimeringsmetode komprimerer effektivt flere kortlængde gentagelser og opnår derfor et højere kompressionsforhold end indekskomprimering. Sandt nok opnås dette på bekostning af høj CPU-belastning; For at ordbogsmetoden skal begynde at komprimere data mere effektivt end indeksmetoden, skal den reducere databehandlingshastigheden til 10-20 megabyte i sekundet på rigtige computerinstallationer med fuld CPU-belastning.
Sådanne lave hastigheder er uacceptable for moderne datalagringssystemer og er af mere "akademisk" interesse end praktisk.
Graden af informationskomprimering vil blive væsentligt øget i den næste ændring af RTT-algoritmen (RTT-Max), den er allerede under udvikling.
Så som altid fortsættes...
Kilde: www.habr.com
