Dit artikel is al het tweede op het gebied van snelle datacompressie. In het eerste artikel werd een compressor beschreven die werkte met een snelheid van 10 GB/sec. per processorkern (minimale compressie, RTT-Min).
Deze compressor is al geïmplementeerd in de uitrusting van forensische duplicators voor snelle compressie van opslagmediadumps en het verbeteren van de kracht van cryptografie; hij kan ook worden gebruikt om afbeeldingen van virtuele machines en RAM-wisselbestanden te comprimeren wanneer deze op hoge snelheid worden opgeslagen. SSD-schijven.
In het eerste artikel werd ook de ontwikkeling aangekondigd van een compressie-algoritme voor het comprimeren van back-upkopieën van HDD- en SSD-schijfstations (medium compressie, RTT-Mid) met aanzienlijk verbeterde datacompressieparameters. Inmiddels is deze compressor helemaal klaar en gaat dit artikel erover.
Een compressor die het RTT-Mid-algoritme implementeert, biedt een compressieverhouding die vergelijkbaar is met die van standaard archiveringsprogramma's zoals WinRar en 7-Zip, die in hogesnelheidsmodus werken. Tegelijkertijd is de werksnelheid minstens een orde van grootte hoger.
De snelheid van het in- en uitpakken van gegevens is een kritische parameter die het toepassingsgebied van compressietechnologieën bepaalt. Het is onwaarschijnlijk dat iemand eraan denkt om een terabyte aan gegevens te comprimeren met een snelheid van 10-15 MegaBytes per seconde (dit is precies de snelheid van archiveringsprogramma's in de standaard compressiemodus), omdat het bijna twintig uur zou duren bij een volledige processorbelasting. .
Aan de andere kant kan dezelfde terabyte in ongeveer tien minuten worden gekopieerd met snelheden in de orde van 2-3 gigabytes per seconde.
Daarom is compressie van grote hoeveelheden informatie belangrijk als deze wordt uitgevoerd met een snelheid die niet lager is dan de snelheid van de werkelijke invoer/uitvoer. Voor moderne systemen is dit minimaal 100 Megabytes per seconde.
Moderne compressoren kunnen dergelijke snelheden alleen in de “snelle” modus produceren. Het is in deze huidige modus dat we het RTT-Mid-algoritme zullen vergelijken met traditionele compressoren.
Vergelijkende testen van een nieuw compressie-algoritme
De RTT-Mid-compressor werkte als onderdeel van het testprogramma. In een echte “werkende” applicatie werkt het veel sneller, het maakt verstandig gebruik van multithreading en gebruikt een “normale” compiler, niet C#.
Omdat de compressoren die in de vergelijkende test worden gebruikt op verschillende principes zijn gebouwd en verschillende soorten gegevens verschillend worden gecomprimeerd, werd voor de objectiviteit van de test de methode voor het meten van de “gemiddelde temperatuur in het ziekenhuis” gebruikt...
Er is een sector-voor-sector dumpbestand gemaakt van een logische schijf met het Windows 10-besturingssysteem; dit is de meest natuurlijke mix van verschillende datastructuren die daadwerkelijk op elke computer beschikbaar zijn. Door dit bestand te comprimeren, kunt u de snelheid en mate van compressie van het nieuwe algoritme vergelijken met de meest geavanceerde compressoren die in moderne archiveringsprogramma's worden gebruikt.
Hier is het dumpbestand:
Het dumpbestand is gecomprimeerd met behulp van PTT-Mid-, 7-zip- en WinRar-compressoren. De WinRar- en 7-zip-compressor stonden op maximale snelheid.
Compressor draait 7-zip:
Het laadt de processor met 100%, terwijl de gemiddelde leessnelheid van de originele dump ongeveer 60 MegaBytes/sec bedraagt.
Compressor draait WinRAR:
De situatie is vergelijkbaar: de processorbelasting is bijna 100%, de gemiddelde leessnelheid van de dump is ongeveer 125 Megabytes/sec.
Net als in het vorige geval wordt de snelheid van het archiveringshulpmiddel beperkt door de mogelijkheden van de processor.
Het compressortestprogramma loopt nu RTT-Mid:
De schermafbeelding laat zien dat de processor voor 50% is geladen en de rest van de tijd inactief is, omdat er geen plek is om de gecomprimeerde gegevens te uploaden. De gegevensuploadschijf (schijf 0) is bijna volledig geladen. De dataleessnelheid (Schijf 1) varieert sterk, maar bedraagt gemiddeld meer dan 200 MegaBytes/sec.
De snelheid van de compressor wordt in dit geval beperkt door de mogelijkheid om gecomprimeerde gegevens naar schijf 0 te schrijven.
Nu de compressieverhouding van de resulterende archieven:
Het is duidelijk dat de RTT-Mid-compressor het beste compressiewerk deed; het archief dat het creëerde was 1,3 GigaBytes kleiner dan het WinRar-archief en 2,1 GigaBytes kleiner dan het 7z-archief.
Tijd besteed aan het maken van het archief:
- 7-zip – 26 minuten 10 seconden;
- WinRar – 17 minuten en 40 seconden;
- RTT-Mid – 7 minuten en 30 seconden.
Zo kon zelfs een niet-geoptimaliseerd testprogramma, dat gebruik maakte van het RTT-Mid-algoritme, een archief ruim tweeënhalf keer sneller creëren, terwijl het archief aanzienlijk kleiner bleek te zijn dan dat van zijn concurrenten...
Wie de screenshots niet gelooft, kan zelf de authenticiteit ervan controleren. Het testprogramma is beschikbaar op , downloaden en controleren.
Maar alleen op processors met AVX-2-ondersteuning, zonder ondersteuning voor deze instructies werkt de compressor niet, en test het algoritme niet op oudere AMD-processors, deze zijn traag in het uitvoeren van AVX-instructies...
Compressiemethode gebruikt
Het algoritme maakt gebruik van een methode voor het indexeren van herhaalde tekstfragmenten in bytegranulariteit. Deze compressiemethode is al lang bekend, maar werd niet gebruikt omdat de matchingoperatie erg duur was in termen van de benodigde middelen en veel meer tijd vergde dan het bouwen van een woordenboek. Het RTT-Mid-algoritme is dus een klassiek voorbeeld van “terug naar de toekomst” gaan...
De PTT-compressor maakt gebruik van een unieke snelle matchzoekscanner, waardoor we het compressieproces kunnen versnellen. Een zelfgemaakte scanner, dit is “mijn charme...”, “het is vrij duur, want het is volledig handgemaakt” (geschreven in assembler).
De matchzoekscanner is gemaakt volgens een probabilistisch schema op twee niveaus: eerst wordt de aanwezigheid van een “teken” van een match gescand, en pas nadat het “teken” op deze plaats is geïdentificeerd, wordt de procedure voor het detecteren van een echte match gevolgd. is begonnen.
Het matchzoekvenster heeft een onvoorspelbare grootte, afhankelijk van de mate van entropie in het verwerkte datablok. Voor volledig willekeurige (onsamendrukbare) gegevens heeft deze een grootte van megabytes, voor gegevens met herhalingen is deze altijd groter dan een megabyte.
Maar veel moderne dataformaten zijn onsamendrukbaar en het is nutteloos en verspillend om er een scanner die veel middelen nodig heeft, te laten werken. Daarom gebruikt de scanner twee werkingsmodi. Eerst worden gedeelten van de brontekst met mogelijke herhalingen doorzocht; ook deze handeling gebeurt probabilistisch en zeer snel (met een snelheid van 4-6 GigaBytes/sec). De gebieden met mogelijke overeenkomsten worden vervolgens door de hoofdscanner verwerkt.
Indexcompressie is niet erg efficiënt, je moet dubbele fragmenten vervangen door indices, en de indexarray vermindert de compressieverhouding aanzienlijk.
Om de compressieverhouding te vergroten, worden niet alleen volledige overeenkomsten van bytereeksen geïndexeerd, maar ook gedeeltelijke overeenkomsten, wanneer de reeks overeenkomende en niet-overeenkomende bytes bevat. Om dit te doen, bevat het indexformaat een matchmaskerveld dat de overeenkomende bytes van twee blokken aangeeft. Voor een nog grotere compressie wordt indexering gebruikt om verschillende gedeeltelijk overeenkomende blokken op het huidige blok te plaatsen.
Dit alles maakte het mogelijk om in de PTT-Mid-compressor een compressieverhouding te verkrijgen die vergelijkbaar is met die van compressoren gemaakt met behulp van de woordenboekmethode, maar die veel sneller werkten.
Snelheid van het nieuwe compressie-algoritme
Als de compressor werkt met exclusief gebruik van cachegeheugen (4 Megabytes zijn vereist per thread), varieert de bedrijfssnelheid van 700-2000 Megabytes/sec. per processorkern, afhankelijk van het type gegevens dat wordt gecomprimeerd en weinig afhankelijk van de werkfrequentie van de processor.
Met een multi-threaded implementatie van de compressor wordt de effectieve schaalbaarheid bepaald door de grootte van de cache op het derde niveau. Als u bijvoorbeeld 9 MegaBytes cachegeheugen "aan boord" heeft, heeft het geen zin om meer dan twee compressiethreads te starten; de snelheid zal hierdoor niet toenemen. Maar met een cache van 20 Megabytes kun je al vijf compressiethreads draaien.
Ook wordt de latentie van het RAM een belangrijke parameter die de snelheid van de compressor bepaalt. Het algoritme maakt gebruik van willekeurige toegang tot de OP, waarvan een deel niet in het cachegeheugen terechtkomt (ongeveer 10%) en moet inactief zijn, wachtend op gegevens van de OP, wat de werkingssnelheid vermindert.
Heeft een aanzienlijke invloed op de snelheid van de compressor en de werking van het gegevensinvoer-/uitvoersysteem. Verzoeken aan de OP vanuit I/O blokkeren verzoeken om gegevens van de CPU, waardoor ook de compressiesnelheid wordt verlaagd. Dit probleem is aanzienlijk voor laptops en desktops; voor servers is het minder groot vanwege een geavanceerdere systeembustoegangscontrole-eenheid en meerkanaals RAM.
In de hele tekst van het artikel praten we over compressie; decompressie valt buiten het bestek van dit artikel omdat “alles bedekt is met chocolade”. Decompressie is veel sneller en wordt beperkt door de I/O-snelheid. Eén fysieke kern in één thread zorgt met gemak voor uitpaksnelheden van 3-4 GB/sec.
Dit komt door het ontbreken van een zoekactie naar overeenkomsten tijdens het decompressieproces, die tijdens de compressie de belangrijkste bronnen van de processor en het cachegeheugen "opeet".
Betrouwbaarheid van gecomprimeerde gegevensopslag
Zoals de naam van de hele klasse van software die gebruik maakt van datacompressie (archivers) suggereert, zijn ze ontworpen voor langdurige opslag van informatie, niet voor jaren, maar voor eeuwen en millennia...
Tijdens opslag verliezen opslagmedia enkele gegevens, hier is een voorbeeld:
Deze “analoge” informatiedrager is duizend jaar oud, enkele fragmenten zijn verloren gegaan, maar over het algemeen is de informatie “leesbaar”...
Geen van de verantwoordelijke fabrikanten van moderne digitale gegevensopslagsystemen en digitale media daarvoor biedt al meer dan 75 jaar garanties voor volledige gegevensveiligheid.
En dit is een probleem, maar een uitgesteld probleem, onze nakomelingen zullen het oplossen...
Digitale gegevensopslagsystemen kunnen niet alleen na 75 jaar gegevens verliezen; fouten in gegevens kunnen op elk moment optreden, zelfs tijdens de opname. Ze proberen deze vervormingen te minimaliseren door middel van redundantie en deze te corrigeren met foutcorrectiesystemen. Redundantie- en correctiesystemen kunnen verloren informatie niet altijd herstellen, en als ze dat wel doen, is er geen garantie dat de hersteloperatie correct is voltooid.
En dit is ook een groot probleem, maar niet een uitgesteld probleem, maar een actueel probleem.
Moderne compressoren die worden gebruikt voor het archiveren van digitale gegevens zijn gebouwd op verschillende aanpassingen van de woordenboekmethode, en voor dergelijke archieven zal het verlies van een stukje informatie een fatale gebeurtenis zijn; er is zelfs een gevestigde term voor een dergelijke situatie: een ‘kapot’ archief ...
De lage betrouwbaarheid van het opslaan van informatie in archieven met woordenboekcompressie hangt samen met de structuur van de gecomprimeerde gegevens. De informatie in zo'n archief bevat niet de brontekst, het aantal vermeldingen in het woordenboek wordt daar opgeslagen en het woordenboek zelf wordt dynamisch aangepast door de huidige gecomprimeerde tekst. Als een archieffragment verloren gaat of beschadigd raakt, kunnen alle daaropvolgende archiefvermeldingen niet worden geïdentificeerd aan de hand van de inhoud of de lengte van de vermelding in het woordenboek, omdat niet duidelijk is waarmee het woordenboekvermeldingsnummer correspondeert.
Het is onmogelijk om informatie uit zo’n ‘kapot’ archief te herstellen.
Het RTT-algoritme is gebaseerd op een betrouwbaardere methode voor het opslaan van gecomprimeerde gegevens. Het maakt gebruik van de indexmethode om rekening te houden met herhalende fragmenten. Met deze compressiebenadering kunt u de gevolgen van vervorming van informatie op het opslagmedium minimaliseren en in veel gevallen automatisch vervormingen corrigeren die zijn ontstaan tijdens de opslag van informatie.
Dit komt doordat het archiefbestand bij indexcompressie twee velden bevat:
- een brontekstveld waaruit herhaalde secties zijn verwijderd;
- indexveld.
Het indexveld, dat cruciaal is voor informatieherstel, is niet groot van formaat en kan worden gedupliceerd voor betrouwbare gegevensopslag. Daarom zal, zelfs als een fragment van de brontekst of indexarray verloren gaat, alle andere informatie zonder problemen worden hersteld, zoals in de afbeelding met een “analoog” opslagmedium.
Nadelen van het algoritme
Er zijn geen voordelen zonder nadelen. De indexcompressiemethode comprimeert geen korte herhalende reeksen. Dit komt door de beperkingen van de indexmethode. Indexen zijn minimaal 3 bytes groot en kunnen maximaal 12 bytes groot zijn. Als er een herhaling wordt aangetroffen met een kleinere omvang dan de index die deze beschrijft, wordt er geen rekening mee gehouden, ongeacht hoe vaak dergelijke herhalingen in het gecomprimeerde bestand worden gedetecteerd.
De traditionele woordenboekcompressiemethode comprimeert effectief meerdere herhalingen van korte lengte en bereikt daardoor een hogere compressieverhouding dan indexcompressie. Toegegeven, dit wordt bereikt vanwege de hoge belasting van de centrale processor; om ervoor te zorgen dat de woordenboekmethode gegevens efficiënter gaat comprimeren dan de indexmethode, moet deze de gegevensverwerkingssnelheid verlagen tot 10-20 megabytes per seconde in reële omstandigheden. computerinstallaties met een volledige CPU-belasting.
Dergelijke lage snelheden zijn onaanvaardbaar voor moderne gegevensopslagsystemen en zijn eerder van ‘academisch’ belang dan van praktisch belang.
De mate van informatiecompressie zal aanzienlijk worden verhoogd bij de volgende wijziging van het RTT-algoritme (RTT-Max), die al in ontwikkeling is.
Dus, zoals altijd, wordt vervolgd...
Bron: www.habr.com