Kini nga artikulo mao na ang ikaduha sa hilisgutan sa high-speed data compression. Gihulagway sa unang artikulo ang usa ka compressor nga naglihok sa gikusgon nga 10 GB/sec. matag processor core (minimum compression, RTT-Min).
Kini nga compressor gipatuman na sa mga ekipo sa forensic duplicators alang sa high-speed compression sa storage media dumps ug pagpausbaw sa kalig-on sa cryptography; mahimo usab kini gamiton sa pag-compress sa mga imahe sa mga virtual machine ug RAM swap files kung i-save kini sa high-speed. SSD drive.
Gipahibalo usab sa una nga artikulo ang pag-uswag sa usa ka algorithm sa compression alang sa pag-compress sa mga backup nga kopya sa HDD ug SSD disk drive (medium compression, RTT-Mid) nga adunay labi ka maayo nga mga parameter sa compression sa data. Sa pagkakaron, kini nga compressor hingpit nga andam ug kini nga artikulo mahitungod niini.
Ang usa ka compressor nga nagpatuman sa RTT-Mid algorithm naghatag ug compression ratio nga ikatandi sa standard archiver sama sa WinRar, 7-Zip, nga naglihok sa high-speed mode. Sa parehas nga oras, ang katulin sa pagpaandar niini labing menos usa ka han-ay sa kadako nga mas taas.
Ang katulin sa data packing/unpacking usa ka kritikal nga parameter nga nagtino sa sakup sa paggamit sa mga teknolohiya sa compression. Dili tingali nga adunay maghunahuna sa pag-compress sa usa ka terabyte nga datos sa katulin nga 10-15 MegaBytes matag segundo (kini mao gyud ang katulin sa mga archiver sa standard nga compression mode), tungod kay hapit kawhaan ka oras nga adunay bug-os nga load sa processor. .
Sa laing bahin, ang samang terabyte mahimong makopya sa gikusgon sa han-ay nga 2-3Gigabytes kada segundo sulod sa mga napulo ka minuto.
Busa, ang pag-compress sa dako nga gidaghanon nga impormasyon importante kung kini gihimo sa gikusgon nga dili ubos sa gikusgon sa tinuod nga input/output. Alang sa modernong mga sistema kini labing menos 100 Megabytes matag segundo.
Ang mga modernong compressor makahimo sa ingon nga mga katulin lamang sa "paspas" nga mode. Anaa sa karon nga mode nga atong itandi ang RTT-Mid algorithm sa tradisyonal nga mga compressor.
Comparative testing sa usa ka bag-ong compression algorithm
Ang RTT-Mid compressor nagtrabaho isip bahin sa programa sa pagsulay. Sa usa ka tinuod nga "nagtrabaho" nga aplikasyon kini molihok nga mas paspas, kini naggamit sa multithreading nga maalamon ug naggamit sa usa ka "normal" nga compiler, dili C #.
Tungod kay ang mga compressor nga gigamit sa comparative test gitukod sa lain-laing mga prinsipyo ug lain-laing mga matang sa data compress lainlain, alang sa objectivity sa pagsulay, ang pamaagi sa pagsukod sa "average nga temperatura sa ospital" gigamit ...
Usa ka sektor-sa-sektor nga dump file sa usa ka lohikal nga disk nga adunay Windows 10 operating system ang gibuhat; kini ang labing natural nga pagsagol sa lainlaing mga istruktura sa datos nga magamit gyud sa matag kompyuter. Ang pag-compress niini nga file magtugot kanimo nga itandi ang katulin ug ang-ang sa compression sa bag-ong algorithm sa labing abante nga mga compressor nga gigamit sa modernong mga archiver.
Ania ang dump file:
Ang dump file gi-compress gamit ang PTT-Mid, 7-zip, ug WinRar compressors. Ang WinRar ug 7-zip compressor gitakda sa maximum speed.
Nagdagan ang compressor 7-zip:
Nag-load kini sa processor sa 100%, samtang ang kasagaran nga katulin sa pagbasa sa orihinal nga dump mga 60 MegaBytes / sec.
Nagdagan ang compressor Winrar:
Ang sitwasyon susama, ang processor load hapit 100%, ang average nga dump reading speed maoy mga 125 Megabytes/sec.
Sama sa miaging kaso, ang katulin sa archiver limitado sa mga kapabilidad sa processor.
Ang programa sa pagsulay sa compressor karon nagdagan RTT-Mid:
Gipakita sa screenshot nga ang processor gikarga sa 50% ug wala’y trabaho sa nahabilin nga oras, tungod kay wala’y lugar nga ma-upload ang gi-compress nga datos. Ang data upload disk (Disk 0) halos bug-os nga gikarga. Ang katulin sa pagbasa sa datos (Disk 1) lainlain kaayo, apan sa aberids labaw sa 200 MegaBytes/sec.
Ang katulin sa compressor limitado sa kini nga kaso pinaagi sa abilidad sa pagsulat sa compressed data sa Disk 0.
Karon ang compression ratio sa mga resulta nga mga archive:
Makita nga ang RTT-Mid compressor ang naghimo sa pinakamaayo nga trabaho sa compression; ang archive nga gihimo niini mao ang 1,3 GigaBytes nga mas gamay kaysa sa WinRar archive ug 2,1 GigaBytes nga mas gamay sa 7z archive.
Panahon nga gigugol sa paghimo sa archive:
- 7-zip - 26 minutos 10 segundos;
- WinRar - 17 minuto 40 segundos;
- RTT-Mid – 7 minutos 30 segundos.
Sa ingon, bisan ang usa ka pagsulay, dili-optimized nga programa, gamit ang RTT-Mid algorithm, nakahimo sa paghimo sa usa ka archive labaw pa sa duha ug tunga ka beses nga mas paspas, samtang ang archive nahimo nga labi ka gamay kaysa sa mga kakompetensya niini ...
Kadtong dili motuo sa mga screenshot makasusi sa ilang pagkatinuod sa ilang kaugalingon. Ang programa sa pagsulay anaa sa , download ug check.
Apan sa mga processor lamang nga adunay suporta sa AVX-2, kung wala’y suporta alang sa kini nga mga panudlo ang compressor dili molihok, ug ayaw pagsulay sa algorithm sa mga tigulang nga mga processor sa AMD, hinay sila sa mga termino sa pagpatuman sa mga panudlo sa AVX...
Ang pamaagi sa compression gigamit
Ang algorithm naggamit ug paagi para sa pag-indeks sa gibalikbalik nga mga tipik sa teksto sa byte granularity. Kini nga pamaagi sa compression nahibal-an na sa dugay nga panahon, apan wala gigamit tungod kay ang pagpares nga operasyon mahal kaayo sa mga termino sa kinahanglan nga mga kapanguhaan ug nanginahanglan daghang oras kaysa paghimo usa ka diksyonaryo. Mao nga ang RTT-Mid algorithm usa ka klasiko nga pananglitan sa pagbalhin "balik sa umaabot" ...
Ang PTT compressor naggamit sa usa ka talagsaon nga high-speed match search scanner, nga nagtugot kanato sa pagpadali sa proseso sa compression. Usa ka hinimo sa kaugalingon nga scanner, kini mao ang "akong kaanyag ...", "kini medyo mahal, tungod kay kini hingpit nga hinimo sa kamot" (gisulat sa assembler).
Ang match search scanner gihimo sumala sa duha ka lebel nga probabilistic scheme: una, ang presensya sa usa ka "sign" sa usa ka posporo gi-scan, ug pagkahuman lamang sa "sign" mailhan sa niini nga dapit, ang pamaagi sa pag-ila sa usa ka tinuod nga tugma nagsugod na.
Ang bintana sa pagpangita sa posporo adunay dili matag-an nga gidak-on, depende sa lebel sa entropy sa giproseso nga bloke sa datos. Alang sa hingpit nga random (incompressible) nga datos kini adunay gidak-on nga megabytes, alang sa datos nga adunay mga pagsubli kini kanunay nga mas dako kaysa usa ka megabyte.
Apan daghang modernong mga format sa datos ang dili ma-compress ug ang pagpadagan sa usa ka resource-intensive nga scanner pinaagi niini walay kapuslanan ug usik, mao nga ang scanner naggamit sa duha ka operating mode. Una, gipangita ang mga seksyon sa gigikanan nga teksto nga adunay posible nga mga pagbalik-balik; kini nga operasyon gihimo usab gamit ang usa ka probabilistic nga pamaagi ug dali nga gihimo (sa tulin nga 4-6 GigaBytes / sec). Ang mga lugar nga adunay posible nga mga posporo unya giproseso sa panguna nga scanner.
Ang index compression dili kaayo episyente, kinahanglan nimong ilisan ang mga duplicate nga mga tipik sa mga indeks, ug ang han-ay sa indeks makapakunhod sa ratio sa compression.
Aron madugangan ang ratio sa compression, dili lamang kompleto nga mga tugma sa byte nga mga kuwerdas ang gi-index, kondili mga partial usab, kung ang kuwerdas adunay mga tugma ug dili managsama nga mga byte. Aron mahimo kini, ang index format naglakip sa usa ka match mask field nga nagpaila sa matching bytes sa duha ka block. Para sa mas dako nga compression, ang pag-indeks gigamit sa pagpatong sa pipila ka partially matching blocks ngadto sa kasamtangang block.
Kining tanan nagpaposible sa pagkuha sa PTT-Mid compressor sa usa ka compression ratio nga ikatandi sa mga compressor nga gihimo gamit ang diksyonaryo nga pamaagi, apan mas paspas ang pagtrabaho.
Ang katulin sa bag-ong algorithm sa compression
Kung ang compressor naglihok nga adunay eksklusibo nga paggamit sa memorya sa cache (4 Megabytes ang gikinahanglan matag thread), nan ang operating speed gikan sa 700-2000 Megabytes / sec. matag processor core, depende sa matang sa data nga gi-compress ug nagdepende gamay sa operating frequency sa processor.
Uban sa usa ka multi-threaded nga pagpatuman sa compressor, ang epektibo nga scalability gitino sa gidak-on sa ikatulo nga lebel nga cache. Pananglitan, nga adunay 9 MegaBytes sa cache nga panumduman "nakasakay", walay punto sa paglansad labaw pa sa duha ka mga hilo sa compression; ang katulin dili motaas gikan niini. Apan sa usa ka cache nga 20 Megabytes, mahimo ka na nga modagan sa lima ka compression thread.
Usab, ang latency sa RAM nahimong usa ka importante nga parameter nga nagtino sa katulin sa compressor. Ang algorithm naggamit sa random nga pag-access sa OP, nga ang pipila niini dili makasulod sa cache nga panumduman (mga 10%) ug kini kinahanglan nga mag-idle, naghulat sa datos gikan sa OP, nga makapamenos sa gikusgon sa operasyon.
Mahinungdanon nga makaapekto sa katulin sa compressor ug sa operasyon sa data input / output nga sistema. Ang mga hangyo sa OP gikan sa I/O block mga hangyo alang sa datos gikan sa CPU, nga makapamenos usab sa gikusgon sa compression. Kini nga problema hinungdanon alang sa mga laptop ug desktop; alang sa mga server dili kaayo hinungdanon tungod sa usa ka labi ka abante nga yunit sa kontrol sa pag-access sa bus ug multi-channel nga RAM.
Sa tibuuk nga teksto sa artikulo naghisgot kami bahin sa compression; ang decompression nagpabilin sa gawas sa sulud sa kini nga artikulo tungod kay "ang tanan gitabonan sa tsokolate". Ang decompression mas paspas ug limitado sa I/O speed. Ang usa ka pisikal nga kinauyokan sa usa ka hilo dali nga naghatag katulin sa pag-unpack nga 3-4 GB/sec.
Kini tungod sa pagkawala sa usa ka operasyon sa pagpangita sa posporo sa panahon sa proseso sa decompression, nga "nagkaon" sa mga nag-unang kapanguhaan sa processor ug memorya sa cache sa panahon sa compression.
Kasaligan sa compressed data storage
Sama sa gisugyot sa ngalan sa tibuok klase sa software nga naggamit sa data compression (archivers), kini gidisenyo alang sa dugay nga pagtipig sa impormasyon, dili sa mga tuig, kondili sa mga siglo ug milenyo...
Atol sa pagtipig, ang storage media mawad-an sa pipila ka mga datos, ania ang usa ka pananglitan:
Kini nga "analog" nga tigdala sa kasayuran usa ka libo ka tuig ang edad, pipila ka mga tipik nawala, apan sa kinatibuk-an ang kasayuran "mabasa" ...
Walay usa sa mga responsable nga tiggama sa modernong digital data storage system ug digital media alang kanila ang naghatag ug garantiya sa kompletong data safety sulod sa kapin sa 75 ka tuig.
Ug kini usa ka problema, apan usa ka na-postpone nga problema, ang atong mga kaliwatan ang makasulbad niini ...
Ang mga sistema sa pagtipig sa digital nga datos mahimong mawad-an sa datos dili lamang human sa 75 ka tuig, ang mga kasaypanan sa datos mahimong makita sa bisan unsang oras, bisan sa panahon sa ilang pagrekord, sila naningkamot sa pagpamenos niini nga mga pagtuis pinaagi sa paggamit sa redundancy ug pagtul-id kanila sa mga sistema sa pagtul-id sa sayop. Ang mga redundancy ug correction system dili kanunay makapahiuli sa nawala nga impormasyon, ug kung buhaton nila, walay garantiya nga ang operasyon sa pagpahiuli nahuman sa husto.
Ug kini usa usab ka dako nga problema, apan dili usa nga gilangan, apan usa ka karon.
Ang mga modernong compressor nga gigamit alang sa pag-archive sa digital nga datos gitukod sa lainlaing mga pagbag-o sa pamaagi sa diksyonaryo, ug alang sa ingon nga mga archive ang pagkawala sa usa ka piraso sa kasayuran mahimong usa ka makamatay nga panghitabo; adunay bisan usa ka natukod nga termino alang sa ingon nga kahimtang - usa ka "nabuak" nga archive ...
Ang ubos nga kasaligan sa pagtipig sa impormasyon sa mga archive nga adunay compression sa diksyonaryo nalangkit sa istruktura sa compressed data. Ang kasayuran sa ingon nga archive wala maglangkob sa gigikanan nga teksto, ang mga numero sa mga entri sa diksyonaryo gitipigan didto, ug ang diksyonaryo mismo dinamikong gibag-o sa karon nga na-compress nga teksto. Kung nawala o nadaot ang usa ka tipik sa archive, ang tanan nga nagsunod nga mga entry sa archive dili mailhan pinaagi sa sulud o sa gitas-on sa entry sa diksyonaryo, tungod kay dili klaro kung unsa ang katumbas sa numero sa entry sa diksyonaryo.
Imposible nga ibalik ang kasayuran gikan sa ingon nga "nabuak" nga archive.
Ang RTT algorithm gibase sa mas kasaligan nga paagi sa pagtipig sa compressed data. Gigamit niini ang indeks nga pamaagi sa pag-asoy alang sa balik-balik nga mga tipik. Kini nga pamaagi sa compression nagtugot kanimo nga maminusan ang mga sangputanan sa pagtuis sa kasayuran sa medium nga pagtipig, ug sa daghang mga kaso awtomatiko nga matul-id ang mga pagtuis nga mitumaw sa pagtipig sa kasayuran.
Kini tungod sa kamatuoran nga ang archive file sa kaso sa index compression adunay duha ka field:
- usa ka natad sa gigikanan nga teksto nga adunay gibalikbalik nga mga seksyon nga gikuha gikan niini;
- index field.
Ang natad sa indeks, nga hinungdanon alang sa pagbawi sa kasayuran, dili dako ang gidak-on ug mahimong madoble alang sa kasaligan nga pagtipig sa datos. Busa, bisan kung nawala ang usa ka tipik sa gigikanan nga teksto o han-ay sa indeks, ang tanan nga ubang kasayuran ibalik nga wala’y mga problema, sama sa litrato nga adunay medium nga pagtipig nga "analog".
Mga disbentaha sa algorithm
Walay mga bentaha nga walay mga disbentaha. Ang index compression nga pamaagi wala mag-compress sa mubu nga pagbalik-balik nga mga han-ay. Kini tungod sa mga limitasyon sa pamaagi sa indeks. Ang mga indeks labing menos 3 ka byte ang gidak-on ug mahimong hangtod sa 12 byte ang gidak-on. Kung ang usa ka pagbalik-balik makit-an nga adunay usa ka gamay nga gidak-on kaysa sa indeks nga naghulagway niini, nan wala kini gikonsiderar, bisan kung unsa ka sagad ang ingon nga mga pagsubli nakit-an sa compressed file.
Ang tradisyonal nga paagi sa kompresiyon sa diksyonaryo epektibo nga nag-compress sa daghang mga pagsubli sa mubo nga gitas-on ug busa nakab-ot ang usa ka mas taas nga ratio sa compression kaysa compression sa indeks. Tinuod, nakab-ot kini tungod sa taas nga pagkarga sa sentral nga processor; aron ang pamaagi sa diksyonaryo magsugod sa pag-compress sa datos nga labi ka episyente kaysa sa pamaagi sa indeks, kinahanglan nga pakunhuran ang katulin sa pagproseso sa datos sa 10-20 megabytes matag segundo sa tinuud. pag-compute sa mga instalasyon nga adunay bug-os nga load sa CPU.
Ang ingon nga ubos nga katulin dili madawat alang sa modernong mga sistema sa pagtipig sa datos ug labi ka "akademiko" nga interes kaysa praktikal.
Ang lebel sa kompresiyon sa impormasyon madugangan pag-ayo sa sunod nga pagbag-o sa RTT algorithm (RTT-Max), nga anaa na sa pag-uswag.
Mao nga, sama sa kanunay, magpadayon ...
Source: www.habr.com