Å is raksts ir jau otrais Ätrgaitas datu kompresijas tÄmÄ. PirmajÄ rakstÄ bija aprakstÄ«ts kompresors, kas darbojas ar Ätrumu 10 GB/sek. uz vienu procesora kodolu (minimÄlÄ kompresija, RTT-Min).
Å is kompresors jau ir ieviests kriminÄlistikas pavairotÄju iekÄrtÄs datu nesÄju izgÄztuvju ÄtrdarbÄ«gai saspieÅ”anai un kriptogrÄfijas stiprÄ«bas uzlaboÅ”anai; to var izmantot arÄ« virtuÄlo maŔīnu attÄlu un RAM mijmaiÅas failu saspieÅ”anai, saglabÄjot tos ÄtrdarbÄ«bÄ. SSD diskdziÅi.
PirmajÄ rakstÄ tika paziÅots arÄ« par saspieÅ”anas algoritma izstrÄdi HDD un SSD disku disku rezerves kopiju saspieÅ”anai (vidÄja kompresija, RTT-Mid) ar ievÄrojami uzlabotiem datu saspieÅ”anas parametriem. Å obrÄ«d Å”is kompresors ir pilnÄ«bÄ gatavs, un Å”is raksts ir par to.
Kompresors, kas ievieÅ” RTT-Mid algoritmu, nodroÅ”ina saspieÅ”anas pakÄpi, kas ir salÄ«dzinÄma ar standarta arhivatoriem, piemÄram, WinRar, 7-Zip, kas darbojas Ätrgaitas režīmÄ. TajÄ paÅ”Ä laikÄ tÄ darbÄ«bas Ätrums ir vismaz par vienu pakÄpi lielÄks.
Datu iepakoÅ”anas/izpakoÅ”anas Ätrums ir kritisks parametrs, kas nosaka saspieÅ”anas tehnoloÄ£iju pielietojuma apjomu. Diez vai kÄdam ienÄks prÄtÄ saspiest terabaitu datu ar Ätrumu 10-15 megabaiti sekundÄ (tieÅ”i tÄds ir arhivÄtÄju Ätrums standarta saspieÅ”anas režīmÄ), jo ar pilnu procesora slodzi tas prasÄ«tu gandrÄ«z divdesmit stundas. .
No otras puses, vienu un to paÅ”u terabaitu var nokopÄt ar Ätrumu 2-3 gigabaiti sekundÄ apmÄram desmit minÅ«tÄs.
TÄpÄc liela apjoma informÄcijas saspieÅ”ana ir svarÄ«ga, ja tÄ tiek veikta ar Ätrumu, kas nav mazÄks par reÄlÄs ievades/izvades Ätrumu. MÅ«sdienu sistÄmÄm tas ir vismaz 100 megabaiti sekundÄ.
MÅ«sdienu kompresori var radÄ«t Å”Ädus Ätrumus tikai āÄtrÄā režīmÄ. Å ajÄ paÅ”reizÄjÄ režīmÄ mÄs salÄ«dzinÄsim RTT-Mid algoritmu ar tradicionÄlajiem kompresoriem.
Jauna kompresijas algoritma salÄ«dzinoÅ”Ä pÄrbaude
RTT-Mid kompresors darbojÄs kÄ daļa no testa programmas. ReÄlÄ ādarbaā lietojumprogrammÄ tÄ darbojas daudz ÄtrÄk, tÄ saprÄtÄ«gi izmanto daudzpavedienu veidoÅ”anu un izmanto āparastuā kompilatoru, nevis C#.
TÄ kÄ salÄ«dzinoÅ”ajÄ testÄ izmantotie kompresori ir veidoti pÄc dažÄdiem principiem un dažÄda veida dati saspiež atŔķirÄ«gi, testa objektivitÄtei tika izmantota āvidÄjÄs temperatÅ«ras slimnÄ«cÄā mÄrÄ«Å”anas metode...
Tika izveidots loÄ£iskÄ diska ar operÄtÄjsistÄmu Windows 10 izgÄztuves fails pa sektoru, tas ir visdabiskÄkais dažÄdu datu struktÅ«ru sajaukums, kas faktiski pieejams katrÄ datorÄ. Å Ä« faila saspieÅ”ana ļaus salÄ«dzinÄt jaunÄ algoritma saspieÅ”anas Ätrumu un pakÄpi ar vismodernÄkajiem kompresoriem, ko izmanto mÅ«sdienu arhivÄjos.
Å eit ir izgÄztuves fails:
Izdrukas fails tika saspiests, izmantojot PTT-Mid, 7-zip un WinRar kompresorus. WinRar un 7-zip kompresors tika iestatÄ«ts uz maksimÄlo Ätrumu.
Kompresors darbojas 7-zip:
Tas noslogo procesoru par 100%, savukÄrt vidÄjais sÄkotnÄjÄs izgÄztuves nolasÄ«Å”anas Ätrums ir aptuveni 60 megabaiti/sek.
Kompresors darbojas WinRAR:
SituÄcija ir lÄ«dzÄ«ga, procesora noslodze ir gandrÄ«z 100%, vidÄjais dump lasÄ«Å”anas Ätrums ir aptuveni 125 Megabaiti/sek.
TÄpat kÄ iepriekÅ”ÄjÄ gadÄ«jumÄ, arhivÄÅ”anas Ätrumu ierobežo procesora iespÄjas.
Tagad darbojas kompresora pÄrbaudes programma RTT-vid:
EkrÄnuzÅÄmumÄ redzams, ka procesors ir noslogots uz 50% un pÄrÄjo laiku ir dÄ«kstÄvÄ, jo nav kur augÅ”upielÄdÄt saspiestos datus. Datu augÅ”upielÄdes disks (Disk 0) ir gandrÄ«z pilnÄ«bÄ ielÄdÄts. Datu lasÄ«Å”anas Ätrums (1. disks) ir ļoti atŔķirÄ«gs, bet vidÄji vairÄk nekÄ 200 megabaiti/sek.
Kompresora Ätrumu Å”ajÄ gadÄ«jumÄ ierobežo iespÄja ierakstÄ«t saspiestus datus diskÄ 0.
Tagad iegÅ«to arhÄ«vu saspieÅ”anas pakÄpe:
Var redzÄt, ka RTT-Mid kompresors veica vislabÄko saspieÅ”anas darbu; tÄ izveidotais arhÄ«vs bija par 1,3 gigabaitiem mazÄks nekÄ WinRar arhÄ«vs un par 2,1 gigabaitu mazÄks nekÄ 7z arhÄ«vs.
Laiks, kas pavadīts arhīva izveidei:
- 7-zip ā 26 minÅ«tes 10 sekundes;
- WinRar ā 17 minÅ«tes 40 sekundes;
- RTT-Mid ā 7 minÅ«tes 30 sekundes.
TÄdÄjÄdi pat testa, neoptimizÄta programma, izmantojot RTT-Mid algoritmu, spÄja izveidot arhÄ«vu vairÄk nekÄ divarpus reizes ÄtrÄk, savukÄrt arhÄ«vs izrÄdÄ«jÄs ievÄrojami mazÄks nekÄ konkurentiem...
Tie, kas netic ekrÄnuzÅÄmumiem, var paÅ”i pÄrbaudÄ«t to autentiskumu. Testa programma pieejama plkst , lejupielÄdÄjiet un pÄrbaudiet.
Bet tikai procesoros ar AVX-2 atbalstu, bez Å”o instrukciju atbalsta kompresors nedarbojas un netestÄ algoritmu uz vecÄkiem AMD procesoriem, tie ir lÄni AVX instrukciju izpildes ziÅÄ...
IzmantotÄ saspieÅ”anas metode
Algoritms izmanto metodi atkÄrtotu teksta fragmentu indeksÄÅ”anai baitu precizitÄtÄ. Å Ä« saspieÅ”anas metode bija zinÄma jau sen, bet netika izmantota, jo saskaÅoÅ”anas darbÄ«ba bija ļoti dÄrga nepiecieÅ”amo resursu ziÅÄ un prasÄ«ja daudz vairÄk laika nekÄ vÄrdnÄ«cas veidoÅ”ana. TÄtad RTT-Mid algoritms ir klasisks piemÄrs, kÄ pÄrvietoties "atpakaļ uz nÄkotni"...
PTT kompresorÄ tiek izmantots unikÄls Ätrgaitas atbilstÄ«bas meklÄÅ”anas skeneris, kas ļauj mums paÄtrinÄt saspieÅ”anas procesu. PaÅ”taisÄ«ts skeneris, tas ir āmans Å”arms...ā, ātas ir diezgan dÄrgs, jo ir pilnÄ«bÄ roku darbsā (rakstÄ«ts montÄtÄjÄ).
AtbilstÄ«bas meklÄÅ”anas skeneris tiek veikts pÄc divu lÄ«meÅu varbÅ«tÄ«bas shÄmas: vispirms tiek skenÄta atbilstÄ«bas āzÄ«mesā klÄtbÅ«tne, un tikai pÄc tam, kad Å”ajÄ vietÄ ir identificÄta āzÄ«meā, tiek veikta reÄlas atbilstÄ«bas noteikÅ”anas procedÅ«ra. ir uzsÄkta.
AtbilstÄ«bas meklÄÅ”anas logam ir neparedzams izmÄrs atkarÄ«bÄ no apstrÄdÄtÄ datu bloka entropijas pakÄpes. PilnÄ«gi nejauÅ”iem (nesaspiežamiem) datiem tÄ izmÄrs ir megabaiti, datiem ar atkÄrtojumiem tas vienmÄr ir lielÄks par megabaitu.
TaÄu daudzi mÅ«sdienu datu formÄti ir nesaspiežami, un resursietilpÄ«ga skenera darbinÄÅ”ana caur tiem ir bezjÄdzÄ«ga un izŔķÄrdÄ«ga, tÄpÄc skeneris izmanto divus darbÄ«bas režīmus. PirmkÄrt, tiek meklÄtas avota teksta sadaļas ar iespÄjamiem atkÄrtojumiem, Ŕī darbÄ«ba tiek veikta arÄ« ar varbÅ«tÄ«bas metodi un tiek veikta ļoti Ätri (ar Ätrumu 4-6 Gigabaiti/sek). PÄc tam apgabalus ar iespÄjamÄm atbilstÄ«bÄm apstrÄdÄ galvenais skeneris.
Indeksa saspieÅ”ana nav Ä«paÅ”i efektÄ«va, jums ir jÄaizstÄj dublikÄti fragmenti ar indeksiem, un indeksu masÄ«vs ievÄrojami samazina saspieÅ”anas pakÄpi.
Lai palielinÄtu saspieÅ”anas pakÄpi, tiek indeksÄtas ne tikai pilnÄ«gas baitu virkÅu atbilstÄ«bas, bet arÄ« daļÄjas, kad virknÄ ir saskaÅoti un nesaskaÅoti baiti. Lai to izdarÄ«tu, indeksa formÄtÄ ir iekļauts atbilstÄ«bas maskas lauks, kas norÄda divu bloku atbilstoÅ”os baitus. VÄl lielÄkai saspieÅ”anai tiek izmantota indeksÄÅ”ana, lai paÅ”reizÄjam blokam uzliktu vairÄkus daļÄji atbilstoÅ”us blokus.
Tas viss ļÄva PTT-Mid kompresorÄ iegÅ«t kompresijas pakÄpi, kas ir salÄ«dzinÄma ar kompresoriem, kas izgatavoti, izmantojot vÄrdnÄ«cas metodi, bet darbojas daudz ÄtrÄk.
JaunÄ saspieÅ”anas algoritma Ätrums
Ja kompresors darbojas ar ekskluzÄ«vu keÅ”atmiÅas izmantoÅ”anu (katram pavedienam ir nepiecieÅ”ami 4 megabaiti), tad darbÄ«bas Ätrums svÄrstÄs no 700-2000 megabaitiem/sek. uz vienu procesora kodolu, atkarÄ«bÄ no saspiežamo datu veida un maz ir atkarÄ«gs no procesora darbÄ«bas frekvences.
Izmantojot kompresora vairÄkpavedienu ievieÅ”anu, efektÄ«vo mÄrogojamÄ«bu nosaka treÅ”Ä lÄ«meÅa keÅ”atmiÅas lielums. PiemÄram, ja ir 9 megabaitu keÅ”atmiÅa, nav jÄgas palaist vairÄk par diviem kompresijas pavedieniem; Ätrums no tÄ nepalielinÄsies. Bet ar 20 megabaitu keÅ”atmiÅu jÅ«s jau varat palaist piecus kompresijas pavedienus.
ArÄ« RAM latentums kļūst par svarÄ«gu parametru, kas nosaka kompresora Ätrumu. Algoritms izmanto nejauÅ”u piekļuvi OP, daļa no kurÄm nenokļūst keÅ”atmiÅÄ (apmÄram 10%) un tai ir jÄdarbojas dÄ«kstÄvÄ, gaidot datus no OP, kas samazina darbÄ«bas Ätrumu.
BÅ«tiski ietekmÄ kompresora Ätrumu un datu ievades/izvades sistÄmas darbÄ«bu. PieprasÄ«jumi OP no I/O bloÄ·Ä datu pieprasÄ«jumus no CPU, kas arÄ« samazina saspieÅ”anas Ätrumu. Å Ä« problÄma ir nozÄ«mÄ«ga klÄpjdatoriem un galddatoriem; serveriem tÄ ir mazÄk nozÄ«mÄ«ga uzlabotas sistÄmas kopnes piekļuves vadÄ«bas bloka un daudzkanÄlu RAM dÄļ.
VisÄ raksta tekstÄ mÄs runÄjam par saspieÅ”anu; dekompresija paliek Ärpus Ŕī raksta darbÄ«bas jomas, jo "viss ir pÄrklÄts ar Å”okolÄdi". Dekompresija ir daudz ÄtrÄka, un to ierobežo I/O Ätrums. Viens fiziskais kodols vienÄ pavedienÄ viegli nodroÅ”ina izpakoÅ”anas Ätrumu 3-4 GB/s.
Tas ir saistÄ«ts ar to, ka dekompresijas procesa laikÄ netiek veikta atbilstÄ«bas meklÄÅ”anas darbÄ«ba, kas saspieÅ”anas laikÄ āapÄdā procesora galvenos resursus un keÅ”atmiÅu.
Saspiestu datu uzglabÄÅ”anas uzticamÄ«ba
KÄ liecina visas programmatÅ«ras klases nosaukums, kas izmanto datu saspieÅ”anu (arhiverus), tie ir paredzÄti ilgstoÅ”ai informÄcijas glabÄÅ”anai, nevis gadiem, bet gan gadsimtiem un tÅ«kstoÅ”iem...
GlabÄÅ”anas laikÄ datu nesÄji zaudÄ dažus datus. Å eit ir piemÄrs:
Å is āanalogaisā informÄcijas nesÄjs ir tÅ«kstoÅ” gadus vecs, daži fragmenti pazuduÅ”i, bet kopumÄ informÄcija ir ālasÄmaā...
Neviens no atbildÄ«gajiem mÅ«sdienu digitÄlo datu uzglabÄÅ”anas sistÄmu un tiem paredzÄto digitÄlo mediju ražotÄjiem nesniedz garantijas par pilnÄ«gu datu droŔību vairÄk nekÄ 75 gadu garumÄ.
Un tÄ ir problÄma, bet atlikta problÄma, to atrisinÄs mÅ«su pÄcteÄi...
DigitÄlÄs datu glabÄÅ”anas sistÄmas var zaudÄt datus ne tikai pÄc 75 gadiem, kļūdas datos var parÄdÄ«ties jebkurÄ brÄ«dÄ«, arÄ« to ierakstÄ«Å”anas laikÄ, tÄs cenÅ”as minimizÄt Å”os kropļojumus, izmantojot redundances un labojot tos ar kļūdu laboÅ”anas sistÄmÄm. Redundances un korekcijas sistÄmas ne vienmÄr var atjaunot zaudÄto informÄciju, un, ja tÄ notiek, nav garantijas, ka atjaunoÅ”anas darbÄ«ba tika pabeigta pareizi.
Un arÄ« Ŕī ir liela problÄma, bet ne jau atlikta, bet gan aktuÄla.
MÅ«sdienu kompresori, ko izmanto digitÄlo datu arhivÄÅ”anai, ir veidoti uz dažÄdÄm vÄrdnÄ«cas metodes modifikÄcijÄm, un Å”Ädiem arhÄ«viem informÄcijas daļas nozaudÄÅ”ana bÅ«s liktenÄ«gs notikums, Å”Ädai situÄcijai ir pat noteikts termins - āsalauztsā arhÄ«vs. ...
ZemÄ uzticamÄ«ba informÄcijas glabÄÅ”anai arhÄ«vos ar vÄrdnÄ«cas saspieÅ”anu ir saistÄ«ta ar saspiesto datu struktÅ«ru. Å ÄdÄ arhÄ«vÄ esoÅ”Ä informÄcija nesatur avota tekstu, tajÄ tiek glabÄti vÄrdnÄ«cas ierakstu numuri, un paÅ”u vÄrdnÄ«cu dinamiski modificÄ paÅ”reizÄjais saspiestais teksts. Ja kÄds arhÄ«va fragments tiek pazaudÄts vai bojÄts, visus turpmÄkos arhÄ«va ierakstus nevar identificÄt ne pÄc satura, ne pÄc ieraksta garuma vÄrdnÄ«cÄ, jo nav skaidrs, kam atbilst vÄrdnÄ«cas ieraksta numurs.
Nav iespÄjams atjaunot informÄciju no tik āsalauztaā arhÄ«va.
RTT algoritms ir balstÄ«ts uz uzticamÄku saspiestu datu glabÄÅ”anas metodi. TÄ izmanto indeksa metodi atkÄrtotu fragmentu uzskaitei. Å Ä« pieeja saspieÅ”anai ļauj samazinÄt informÄcijas izkropļojumu sekas datu nesÄjÄ un daudzos gadÄ«jumos automÄtiski koriÄ£Ät izkropļojumus, kas rodas informÄcijas glabÄÅ”anas laikÄ.
Tas ir saistÄ«ts ar faktu, ka indeksa saspieÅ”anas gadÄ«jumÄ arhÄ«va failÄ ir divi lauki:
- avota teksta lauks, no kura noÅemtas atkÄrtotas sadaļas;
- indeksa lauks.
Indeksa lauks, kas ir bÅ«tisks informÄcijas atkopÅ”anai, nav liels, un to var dublÄt, lai nodroÅ”inÄtu uzticamu datu glabÄÅ”anu. TÄpÄc, pat ja tiek pazaudÄts avota teksta vai indeksu masÄ«va fragments, visa pÄrÄjÄ informÄcija tiks atjaunota bez problÄmÄm, kÄ attÄlÄ ar āanaloguā datu nesÄju.
Algoritma trūkumi
Nav priekÅ”rocÄ«bu bez trÅ«kumiem. Indeksa saspieÅ”anas metode nesaspiež Ä«sas atkÄrtotas secÄ«bas. Tas ir saistÄ«ts ar indeksu metodes ierobežojumiem. Indeksu lielums ir vismaz 3 baiti un var bÅ«t lÄ«dz 12 baitiem. Ja tiek konstatÄts atkÄrtojums ar mazÄku izmÄru nekÄ to aprakstoÅ”ais indekss, tas netiek Åemts vÄrÄ neatkarÄ«gi no tÄ, cik bieži Å”Ädi atkÄrtojumi tiek konstatÄti saspiestajÄ failÄ.
TradicionÄlÄ vÄrdnÄ«cas saspieÅ”anas metode efektÄ«vi saspiež vairÄkus Ä«sa garuma atkÄrtojumus un tÄdÄjÄdi sasniedz augstÄku saspieÅ”anas pakÄpi nekÄ indeksa saspieÅ”ana. Tiesa, tas tiek panÄkts lielÄs centrÄlÄ procesora slodzes dÄļ; lai vÄrdnÄ«cas metode sÄktu saspiest datus efektÄ«vÄk nekÄ indeksa metode, tai jÄsamazina datu apstrÄdes Ätrums lÄ«dz 10-20 megabaitiem sekundÄ reÄlajÄ skaitļoÅ”anas instalÄcijas ar pilnu CPU slodzi.
MÅ«sdienu datu uzglabÄÅ”anas sistÄmÄm tik mazs Ätrums ir nepieÅemams, un tas ir vairÄk āakadÄmisksā nekÄ praktisks.
InformÄcijas saspieÅ”anas pakÄpe tiks ievÄrojami palielinÄta nÄkamajÄ RTT algoritma modifikÄcijÄ (RTT-Max), kas jau ir izstrÄdes stadijÄ.
TÄtad, kÄ vienmÄr, turpinÄs...
Avots: www.habr.com