Բարձր արագությամբ անհաջող սեղմում (շարունակություն)

Այս հոդվածն արդեն երկրորդն է տվյալների գերարագ սեղմման թեմայում։ Առաջին հոդվածում նկարագրված էր 10 Գբ/վ արագությամբ աշխատող կոմպրեսոր: մեկ պրոցեսորի միջուկի համար (նվազագույն սեղմում, RTT-Min):

Այս կոմպրեսորն արդեն ներդրվել է դատաբժշկական կրկնօրինակիչների սարքավորումներում՝ պահեստավորման մեդիա աղբարկղերի արագ սեղմման և գաղտնագրության ուժը բարձրացնելու համար։ Այն կարող է օգտագործվել նաև վիրտուալ մեքենաների և RAM փոխանակման ֆայլերի պատկերները սեղմելու համար՝ դրանք բարձր արագությամբ պահպանելիս։ SSD կրիչներ.

Առաջին հոդվածը նաև հայտարարեց սեղմման ալգորիթմի մշակման մասին՝ HDD և SSD սկավառակների (միջին սեղմում, RTT-Mid) կրկնօրինակները սեղմելու համար՝ տվյալների սեղմման զգալիորեն բարելավված պարամետրերով: Մինչ այժմ այս կոմպրեսորը լիովին պատրաստ է, և այս հոդվածը դրա մասին է:

RTT-Mid ալգորիթմը ներդրող կոմպրեսորը ապահովում է սեղմման հարաբերակցություն, որը համեմատելի է ստանդարտ արխիվատորների հետ, ինչպիսիք են WinRar-ը, 7-Zip-ը, որոնք աշխատում են գերարագ ռեժիմում: Միևնույն ժամանակ, դրա գործառնական արագությունը առնվազն մի կարգով ավելի բարձր է:

Տվյալների փաթեթավորման/փաթեթավորման արագությունը կարևոր պարամետր է, որը որոշում է սեղմման տեխնոլոգիաների կիրառման շրջանակը: Դժվար թե որևէ մեկը մտածի մեկ տերաբայթ տվյալների սեղմման մասին 10-15 Մեգաբայթ/վայրկյան արագությամբ (սա հենց ստանդարտ սեղմման ռեժիմում արխիվատորների արագությունն է), քանի որ պրոցեսորի լրիվ ծանրաբեռնվածությամբ կպահանջվի գրեթե քսան ժամ: .

Մյուս կողմից, նույն տերաբայթը կարող է կրկնօրինակվել 2-3 Գիգաբայթ/վրկ արագությամբ մոտ տասը րոպեում:

Ուստի մեծածավալ տեղեկատվության սեղմումը կարևոր է, եթե այն իրականացվում է իրական մուտքի/ելքի արագությունից ոչ ցածր արագությամբ: Ժամանակակից համակարգերի համար սա առնվազն 100 Մեգաբայթ է վայրկյանում:

Ժամանակակից կոմպրեսորները կարող են նման արագություններ արտադրել միայն «արագ» ռեժիմով։ Հենց այս ընթացիկ ռեժիմում մենք կհամեմատենք RTT-Mid ալգորիթմը ավանդական կոմպրեսորների հետ:

Նոր սեղմման ալգորիթմի համեմատական ​​փորձարկում

RTT-Mid կոմպրեսորն աշխատել է որպես թեստային ծրագրի մի մաս: Իրական «աշխատանքային» հավելվածում այն ​​շատ ավելի արագ է աշխատում, այն խելամտորեն օգտագործում է բազմաթելեր և օգտագործում է «նորմալ» կոմպիլյատոր, ոչ թե C#:

Քանի որ համեմատական ​​թեստում օգտագործվող կոմպրեսորները կառուցված են տարբեր սկզբունքների վրա, և տվյալների տարբեր տեսակներ սեղմվում են տարբեր կերպ, թեստի օբյեկտիվության համար օգտագործվել է «հիվանդանոցում միջին ջերմաստիճանի» չափման մեթոդը...

Ստեղծվել է Windows 10 օպերացիոն համակարգով տրամաբանական սկավառակի հատված առ ոլորտ աղբանոց ֆայլ, սա տարբեր տվյալների կառուցվածքների ամենաբնական խառնուրդն է, որն իրականում առկա է յուրաքանչյուր համակարգչի վրա: Այս ֆայլի սեղմումը թույլ կտա համեմատել նոր ալգորիթմի սեղմման արագությունն ու աստիճանը ժամանակակից արխիվներում օգտագործվող ամենաառաջադեմ կոմպրեսորների հետ։

Ահա աղբանոց ֆայլը.

Աղբավայրի ֆայլը սեղմվել է PTT-Mid, 7-zip և WinRar կոմպրեսորների միջոցով: WinRar-ը և 7-zip կոմպրեսորը սահմանվել են առավելագույն արագության:

Կոմպրեսորը աշխատում է 7-zip:

Այն բեռնում է պրոցեսորը 100%-ով, մինչդեռ սկզբնական աղբանոցը կարդալու միջին արագությունը մոտ 60 Մեգաբայթ/վ է։

Կոմպրեսորը աշխատում է Winrar:

Իրավիճակը նման է, պրոցեսորի ծանրաբեռնվածությունը գրեթե 100% է, թափոնների ընթերցման միջին արագությունը մոտ 125 Մեգաբայթ/վ է։

Ինչպես նախորդ դեպքում, արխիվատորի արագությունը սահմանափակվում է պրոցեսորի հնարավորություններով։

Այժմ աշխատում է կոմպրեսորի փորձարկման ծրագիրը RTT-Միջ:

Սքրինշոթը ցույց է տալիս, որ պրոցեսորը բեռնված է 50%-ով և մնացած ժամանակ անգործուն է, քանի որ սեղմված տվյալները վերբեռնելու տեղ չկա։ Տվյալների վերբեռնման սկավառակը (Սկավառակ 0) գրեթե ամբողջությամբ բեռնված է: Տվյալների ընթերցման արագությունը (սկավառակ 1) մեծապես տարբերվում է, բայց միջինում ավելի քան 200 Մեգաբայթ/վրկ:

Կոմպրեսորի արագությունը այս դեպքում սահմանափակվում է սեղմված տվյալները Disk 0-ում գրելու ունակությամբ:

Այժմ ստացված արխիվների սեղմման հարաբերակցությունը.

Կարելի է տեսնել, որ RTT-Mid կոմպրեսորը սեղմման լավագույն աշխատանքն է արել. նրա ստեղծած արխիվը 1,3 Գիգաբայթով փոքր էր WinRar արխիվից և 2,1 Գիգաբայթով փոքր, քան 7z արխիվը:

Արխիվի ստեղծման համար ծախսված ժամանակը.

• 7-zip – 26 րոպե 10 վայրկյան;
• WinRar – 17 րոպե 40 վայրկյան;
• RTT-Mid – 7 րոպե 30 վայրկյան:

Այսպիսով, նույնիսկ թեստային, ոչ օպտիմիզացված ծրագիրը, օգտագործելով RTT-Mid ալգորիթմը, կարողացավ ավելի քան երկուսուկես անգամ ավելի արագ արխիվ ստեղծել, մինչդեռ արխիվը զգալիորեն փոքր էր իր մրցակիցներից...

Նրանք, ովքեր չեն հավատում սքրինշոթերին, կարող են իրենք ստուգել դրանց իսկությունը: Թեստային ծրագիրը հասանելի է ՈՒղեցույց, ներբեռնեք և ստուգեք։

Բայց միայն AVX-2 աջակցությամբ պրոցեսորների վրա, առանց այս հրահանգների աջակցության կոմպրեսորը չի աշխատում, և ալգորիթմը մի փորձարկեք հին AMD պրոցեսորների վրա, դրանք դանդաղ են AVX հրահանգների կատարման առումով...

Օգտագործված սեղմման մեթոդ

Ալգորիթմն օգտագործում է կրկնվող տեքստի բեկորների ինդեքսավորման մեթոդ բայթի հատիկությամբ: Սեղմման այս մեթոդը վաղուց հայտնի էր, բայց չէր օգտագործվում, քանի որ համապատասխանող գործողությունը շատ թանկ էր անհրաժեշտ ռեսուրսների առումով և պահանջում էր շատ ավելի շատ ժամանակ, քան բառարան կառուցելը։ Այսպիսով, RTT-Mid ալգորիթմը «վերադարձ դեպի ապագա» շարժվելու դասական օրինակ է...

PTT կոմպրեսորն օգտագործում է համընկնումների որոնման եզակի գերարագ սկաներ, որը թույլ է տալիս արագացնել սեղմման գործընթացը: Ինքնագործ սկաներ, սա «իմ հմայքը...», «բավականին թանկ է, քանի որ ամբողջովին ձեռագործ է» (գրված է assembler-ում):

Համընկնումների որոնման սկաները պատրաստված է երկու մակարդակի հավանականական սխեմայի համաձայն. նախ սկանավորվում է համընկնման «նշանի» առկայությունը, և միայն այս վայրում «նշանը» հայտնաբերելուց հետո, իրական համընկնումը հայտնաբերելու կարգը: սկսված է.

Համընկնումների որոնման պատուհանն ունի անկանխատեսելի չափ՝ կախված մշակված տվյալների բլոկում էնտրոպիայի աստիճանից: Ամբողջովին պատահական (անսեղմելի) տվյալների համար այն ունի մեգաբայթի չափ, կրկնվող տվյալների համար միշտ ավելի մեծ է, քան մեգաբայթը։

Սակայն տվյալների շատ ժամանակակից ձևաչափեր անսեղմելի են, և դրանց միջոցով ռեսուրսներով ինտենսիվ սկաների գործարկումն անօգուտ է և վատնման, ուստի սկաները օգտագործում է երկու աշխատանքային ռեժիմ: Նախ, որոնվում են սկզբնաղբյուր տեքստի հնարավոր կրկնություններով հատվածներ, այս գործողությունը նույնպես իրականացվում է հավանականական մեթոդով և կատարվում է շատ արագ (4-6 Գիգաբայթ/վրկ արագությամբ): Այնուհետև հնարավոր համընկնումներ ունեցող տարածքները մշակվում են հիմնական սկաների կողմից:

Ինդեքսի սեղմումն այնքան էլ արդյունավետ չէ, դուք պետք է կրկնօրինակ բեկորները փոխարինեք ինդեքսներով, իսկ ինդեքսային զանգվածը զգալիորեն նվազեցնում է սեղմման հարաբերակցությունը:

Սեղմման հարաբերակցությունը մեծացնելու համար ինդեքսավորվում են ոչ միայն բայթ տողերի ամբողջական համընկնումները, այլ նաև մասնակիները, երբ տողը պարունակում է համապատասխան և չհամընկնող բայթեր։ Դա անելու համար ինդեքսի ձևաչափը ներառում է համընկնման դիմակ դաշտ, որը ցույց է տալիս երկու բլոկների համապատասխան բայթերը: Նույնիսկ ավելի մեծ սեղմման համար ինդեքսավորումն օգտագործվում է մի քանի մասամբ համապատասխան բլոկներ ընթացիկ բլոկի վրա տեղադրելու համար:

Այս ամենը հնարավորություն տվեց PTT-Mid կոմպրեսորում ստանալ սեղմման հարաբերակցություն, որը համեմատելի է բառարանի մեթոդով պատրաստված կոմպրեսորների հետ, բայց շատ ավելի արագ է աշխատում:

Նոր սեղմման ալգորիթմի արագություն

Եթե ​​կոմպրեսորն աշխատում է քեշի հիշողության բացառիկ օգտագործմամբ (մեկ շղթայի համար պահանջվում է 4 մեգաբայթ), ապա աշխատանքային արագությունը տատանվում է 700-2000 Մեգաբայթ/վրկ: մեկ պրոցեսորի միջուկի համար՝ կախված սեղմվող տվյալների տեսակից և քիչ է կախված պրոցեսորի գործառնական հաճախականությունից:

Կոմպրեսորի բազմաշերտ ներդրման դեպքում արդյունավետ մասշտաբայնությունը որոշվում է երրորդ մակարդակի քեշի չափով: Օրինակ, ունենալով 9 Մեգաբայթ քեշ հիշողություն «նավում», իմաստ չկա գործարկել ավելի քան երկու սեղմման թելեր, արագությունը դրանից չի բարձրանա: Բայց 20 Մեգաբայթանոց քեշով դուք արդեն կարող եք գործարկել հինգ սեղմման թելեր:

Բացի այդ, RAM-ի հետաձգումը դառնում է կարևոր պարամետր, որը որոշում է կոմպրեսորի արագությունը: Ալգորիթմը օգտագործում է պատահական մուտք դեպի OP, որոնցից մի քանիսը չեն մտնում քեշի հիշողության մեջ (մոտ 10%) և այն պետք է անգործության մատնվի՝ սպասելով տվյալների OP-ից, ինչը նվազեցնում է գործողության արագությունը:

Զգալիորեն ազդում է կոմպրեսորի արագության և տվյալների մուտքագրման/ելքի համակարգի աշխատանքի վրա: OP-ին I/O բլոկի հարցումները պահանջում են տվյալներ պրոցեսորից, ինչը նաև նվազեցնում է սեղմման արագությունը: Այս խնդիրը նշանակալի է նոութբուքերի և աշխատասեղանների համար, իսկ սերվերների համար՝ ավելի առաջադեմ համակարգային ավտոբուսի մուտքի կառավարման միավորի և բազմալիքային RAM-ի պատճառով:

Հոդվածի ամբողջ տեքստի ընթացքում մենք խոսում ենք սեղմման մասին, ապակոմպրեսիան մնում է այս հոդվածի շրջանակից դուրս, քանի որ «ամեն ինչ պատված է շոկոլադով»: Decompression-ը շատ ավելի արագ է և սահմանափակվում է I/O արագությամբ: Մեկ ֆիզիկական միջուկը մեկ թելի մեջ հեշտությամբ ապահովում է 3-4 ԳԲ/վրկ ապափաթեթավորման արագություն:

Դա պայմանավորված է ապակոմպրեսիոն գործընթացում համընկնումների որոնման գործողության բացակայությամբ, որը սեղմման ընթացքում «խժռում» է պրոցեսորի հիմնական ռեսուրսները և քեշի հիշողությունը:

Սեղմված տվյալների պահպանման հուսալիությունը

Ինչպես հուշում է ծրագրային ապահովման ամբողջ դասի անվանումը, որն օգտագործում է տվյալների սեղմում (արխիվատորներ), դրանք նախատեսված են տեղեկատվության երկարաժամկետ պահպանման համար, ոչ թե տարիներով, այլ դարերով ու հազարամյակներով...

Պահպանման ընթացքում կրիչները կորցնում են որոշ տվյալներ, ահա մի օրինակ.

Այս «անալոգային» տեղեկատվական կրիչը հազար տարվա վաղեմություն ունի, որոշ բեկորներ կորել են, բայց ընդհանուր առմամբ ինֆորմացիան «ընթեռնելի» է...

Ժամանակակից թվային տվյալների պահպանման համակարգերի և նրանց համար թվային կրիչների պատասխանատու արտադրողներից ոչ մեկը չի ապահովում տվյալների ամբողջական անվտանգության երաշխիքներ ավելի քան 75 տարի:
Եվ սա խնդիր է, բայց հետաձգված խնդիր, մեր սերունդները կլուծեն...

Թվային տվյալների պահպանման համակարգերը կարող են կորցնել տվյալները ոչ միայն 75 տարի հետո, տվյալների սխալները կարող են հայտնվել ցանկացած պահի, նույնիսկ դրանց գրանցման ժամանակ, նրանք փորձում են նվազագույնի հասցնել այդ աղավաղումները՝ օգտագործելով ավելորդությունը և ուղղելով դրանք սխալների ուղղման համակարգերով: Ավելորդության և ուղղման համակարգերը չեն կարող միշտ վերականգնել կորցրած տեղեկատվությունը, և եթե դա վերականգնվի, երաշխիք չկա, որ վերականգնման գործողությունը ճիշտ է ավարտվել:

Եվ սա նույնպես մեծ խնդիր է, բայց ոչ հետաձգված, այլ ընթացիկ։

Թվային տվյալների արխիվացման համար օգտագործվող ժամանակակից կոմպրեսորները կառուցված են բառարանի մեթոդի տարբեր փոփոխություններով, և այդպիսի արխիվների համար տեղեկատվության կորուստը ճակատագրական իրադարձություն կլինի, նույնիսկ գոյություն ունի նման իրավիճակի համար սահմանված տերմին՝ «կոտրված» արխիվ։ ...

Բառարանների սեղմումով արխիվներում տեղեկատվության պահպանման ցածր հուսալիությունը կապված է սեղմված տվյալների կառուցվածքի հետ: Նման արխիվում տեղեկատվությունը չի պարունակում սկզբնաղբյուր տեքստը, բառարանի գրառումների թվերը պահվում են այնտեղ, իսկ բառարանն ինքնին դինամիկ ձևափոխվում է ընթացիկ սեղմված տեքստով: Եթե ​​արխիվի հատվածը կորել կամ վնասվել է, արխիվի բոլոր հաջորդ գրառումները չեն կարող նույնականացվել բառարանի մուտքի բովանդակությամբ կամ երկարությամբ, քանի որ պարզ չէ, թե բառարանի մուտքի համարը ինչին է համապատասխանում:

Նման «կոտրված» արխիվից տեղեկատվությունը հնարավոր չէ վերականգնել։

RTT ալգորիթմը հիմնված է սեղմված տվյալների պահպանման ավելի հուսալի մեթոդի վրա: Այն օգտագործում է հաշվառման ինդեքսային մեթոդը կրկնվող բեկորների համար: Սեղմման այս մոտեցումը թույլ է տալիս նվազագույնի հասցնել տեղեկատվության խեղաթյուրման հետևանքները պահեստավորման միջավայրում և շատ դեպքերում ինքնաբերաբար ուղղել տեղեկատվության պահպանման ընթացքում առաջացած աղավաղումները:
Դա պայմանավորված է նրանով, որ ինդեքսի սեղմման դեպքում արխիվային ֆայլը պարունակում է երկու դաշտ.

• սկզբնաղբյուր տեքստի դաշտ, որտեղից հեռացվել են կրկնվող բաժինները.
• ինդեքսային դաշտ:

Ինդեքսային դաշտը, որը կարևոր է տեղեկատվության վերականգնման համար, մեծ չափի չէ և կարող է կրկնօրինակվել տվյալների հուսալի պահպանման համար: Հետևաբար, եթե նույնիսկ սկզբնաղբյուր տեքստի կամ ինդեքսային զանգվածի մի հատված կորչի, մնացած բոլոր տեղեկությունները կվերականգնվեն առանց խնդիրների, ինչպես նկարում պատկերված է «անալոգային» պահեստավորման միջավայրով:

Ալգորիթմի թերությունները

Առանց թերությունների առավելություններ չկան։ Ցուցանիշի սեղմման մեթոդը չի սեղմում կարճ կրկնվող հաջորդականությունները: Դա պայմանավորված է ինդեքսային մեթոդի սահմանափակումներով: Ինդեքսները ունեն առնվազն 3 բայթ չափ և կարող են լինել մինչև 12 բայթ: Եթե ​​կրկնությունը հանդիպում է այն նկարագրող ինդեքսից ավելի փոքր չափերով, ապա այն հաշվի չի առնվում, անկախ նրանից, թե որքան հաճախ են նման կրկնությունները հայտնաբերվում սեղմված ֆայլում։

Ավանդական բառարանի սեղմման մեթոդը արդյունավետորեն սեղմում է կարճ երկարության բազմաթիվ կրկնությունները և, հետևաբար, հասնում է սեղմման ավելի բարձր հարաբերակցության, քան ինդեքսային սեղմումը: Ճիշտ է, դա ձեռք է բերվում կենտրոնական պրոցեսորի բարձր ծանրաբեռնվածության պատճառով, որպեսզի բառարանի մեթոդը սկսի ավելի արդյունավետ սեղմել տվյալները, քան ինդեքսային մեթոդը, այն պետք է նվազեցնի տվյալների մշակման արագությունը մինչև 10-20 մեգաբայթ/վրկ իրականում: հաշվողական տեղակայումներ՝ ամբողջ պրոցեսորի ծանրաբեռնվածությամբ:

Նման ցածր արագություններն անընդունելի են տվյալների պահպանման ժամանակակից համակարգերի համար և ավելի շատ «ակադեմիական» հետաքրքրություն են ներկայացնում, քան գործնական:

Տեղեկատվության սեղմման աստիճանը զգալիորեն կբարձրանա RTT ալգորիթմի (RTT-Max) հաջորդ փոփոխության մեջ, որն արդեն մշակման փուլում է։

Այսպիսով, ինչպես միշտ, շարունակելի...

Source: www.habr.com