Бул макала жогорку ылдамдыктагы маалыматтарды кысуу темасында экинчи болуп саналат. Биринчи макалада 10 ГБ/сек ылдамдыкта иштеген компрессор сүрөттөлгөн. процессордун өзөгү үчүн (минималдуу кысуу, RTT-Min).
Бул компрессор криминалистикалык дупликаторлордун жабдууларында сактагычтын таштандыларын жогорку ылдамдыкта кысуу жана криптографиянын күчүн жогорулатуу үчүн киргизилген; 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-индекс:
Ал процессорду 100% жүктөйт, ал эми баштапкы таштандыны окуунун орточо ылдамдыгы болжол менен 60 Мегабайт/сек.
Компрессор иштеп жатат Winrar:
Кырдаал окшош, процессордун жүктөмү дээрлик 100%, демптин орточо окуу ылдамдыгы болжол менен 125 Мегабайт/сек.
Мурунку окуядагыдай эле, архиватордун ылдамдыгы процессордун мүмкүнчүлүктөрү менен чектелет.
Компрессорду сыноо программасы азыр иштеп жатат RTT-Орто:
Скриншот процессордун 50% жүктөлгөнүн жана калган убакта бош турганын көрсөтүп турат, анткени кысылган маалыматтарды жүктөө үчүн эч жер жок. Маалыматтарды жүктөө диски (Диск 0) дээрлик толугу менен жүктөлгөн. Маалыматтарды окуу ылдамдыгы (1-диск) абдан өзгөрүп турат, бирок орто эсеп менен 200 мегабайт/сек.
Компрессордун ылдамдыгы бул учурда дискке 0 кысылган маалыматтарды жазуу мүмкүнчүлүгү менен чектелген.
Эми алынган архивдердин кысуу катышы:
Көрүнүп тургандай, RTT-Mid компрессору эң жакшы кысуу ишин аткарган; ал түзгөн архив WinRar архивинен 1,3 Гигабайтка жана 2,1z архивинен 7 Гигабайтка аз болгон.
Архивди түзүүгө кеткен убакыт:
- 7-zip – 26 мүнөт 10 секунд;
- WinRar – 17 мүнөт 40 секунд;
- RTT-Орто – 7 мүнөт 30 секунд.
Ошентип, RTT-Mid алгоритмин колдонуп, тестирлөөчү, оптималдаштырылбаган программа дагы эки жарым эсе тезирээк архив түзө алды, ал эми архив атаандаштарына караганда бир топ кичине болуп чыкты...
Скриншотторго ишенбегендер алардын аныктыгын өздөрү текшерсе болот. Сыноо программасы дареги боюнча жеткиликтүү , жүктөп алуу жана текшерүү.
Бирок AVX-2 колдоосу бар процессорлордо гана, бул нускамаларды колдоосуз компрессор иштебейт жана эски AMD процессорлорунда алгоритмди сынабайт, алар AVX нускамаларын аткаруу жагынан жай...
Кысуу ыкмасы колдонулат
Алгоритм кайталануучу текст фрагменттерин байт гранулдуулугунда индекстөө ыкмасын колдонот. Бул кысуу ыкмасы көптөн бери белгилүү, бирок колдонулган эмес, анткени дал келүү операциясы керектүү ресурстар жагынан абдан кымбат жана сөздүк түзүүгө караганда алда канча көп убакытты талап кылган. Ошентип, RTT-Mid алгоритми "келечекке кайтып келүүнүн" классикалык мисалы болуп саналат ...
PTT компрессору уникалдуу жогорку ылдамдыктагы дал келүүчү издөө сканерин колдонот, ал бизге кысуу процессин тездетүүгө мүмкүндүк берет. Өз алдынча жасалган сканер, бул "менин сүйкүм...", "бул абдан кымбат, анткени ал толугу менен колго жасалган" (ассемблерде жазылган).
Дал келүүнү издөө сканери эки деңгээлдүү ыктымалдык схема боюнча жүргүзүлөт: биринчиден, дал келүүнүн "белгисинин" болушу сканерден өткөрүлөт жана бул жерде "белги" аныкталгандан кийин гана чыныгы дал келүүнү аныктоо процедурасы башталат.
Дал келүүнү издөө терезеси иштелип чыккан маалымат блогундагы энтропиянын даражасына жараша күтүүсүз чоңдукка ээ. Толук кокустук (кысылбаган) маалыматтар үчүн ал мегабайттын өлчөмүнө ээ, кайталануучу маалыматтар үчүн ал ар дайым мегабайттан чоңураак.
Бирок көптөгөн заманбап маалымат форматтары кысылбайт жана алар аркылуу ресурсту көп талап кылган сканерди иштетүү пайдасыз жана ысырапкор, ошондуктан сканер эки иштөө режимин колдонот. Биринчиден, мүмкүн болгон кайталануулар менен баштапкы тексттин бөлүмдөрү изделет; Мүмкүн болгон дал келген аймактар андан кийин негизги сканер тарабынан иштетилет.
Индекс кысуу өтө эффективдүү эмес, кайталануучу фрагменттерди индекстер менен алмаштырууга туура келет, ал эми индекс массиви кысуу катышын кыйла азайтат.
Кысуу катышын жогорулатуу үчүн байт саптарынын толук дал келүүлөрү гана индекстелбестен, сап дал келген жана дал келбеген байттарды камтыган жарым-жартылайы да индекстелет. Бул үчүн, индекс форматы эки блоктун дал келген байттарын көрсөткөн дал келүүчү маска талаасын камтыйт. Андан да көбүрөөк кысуу үчүн, индекстөө бир нече жарым-жартылай дал келген блокторду учурдагы блоктун үстүнө коюу үчүн колдонулат.
Мунун баары PTT-Mid компрессорунда сөздүк ыкмасы менен жасалган компрессорлор менен салыштырылуучу, бирок бир топ ылдамыраак иштеген кысуу катышын алууга мүмкүндүк берди.
Жаңы кысуу алгоритминин ылдамдыгы
Эгерде компрессор кэш эстутумун эксклюзивдүү пайдалануу менен иштесе (бир жипке 4 мегабайт талап кылынат), анда иштөө ылдамдыгы 700-2000 Мегабайт/сек. ар бир процессордун өзөгү, кысылып жаткан маалыматтардын түрүнө жараша жана процессордун иштөө жыштыгына бир аз көз каранды.
Компрессордун көп жиптүү ишке ашырылышы менен эффективдүү масштабдоо үчүнчү деңгээлдеги кэштин өлчөмү менен аныкталат. Мисалы, "бортто" 9 мегабайт кэш эстутумуна ээ болуу, экиден ашык кысуу жиптерин ишке киргизүүнүн мааниси жок; Бирок 20 мегабайт кэш менен сиз беш кысуу жиптерин иштете аласыз.
Ошондой эле, оперативдүү эс тутумдун күтүү убактысы компрессордун ылдамдыгын аныктоочу маанилүү параметр болуп калат. Алгоритм ОПга туш келди кирүүнү колдонот, алардын айрымдары кэш эстутумуна түшпөйт (болжол менен 10%) жана ал ОПдан маалыматтарды күтүп, иштөө ылдамдыгын азайтат.
Киргизүү/чыгаруу системасы компрессордун ылдамдыгына олуттуу таасир этет. Оперативдик эс тутумга киргизүү/чыгаруу сурамдары CPU'нун маалымат сурамдарын бөгөттөйт, бул да кысуу ылдамдыгын төмөндөтөт. Бул көйгөй ноутбуктар жана рабочий компьютерлер үчүн маанилүү. серверлер Ал өнүккөн системалык шина кирүүнү башкаруу блогу жана көп каналдуу RAMдан улам анчалык маанилүү эмес.
Макаладагы текст боюнча биз компрессия жөнүндө сөз кылабыз, анткени "баары шоколад менен капталган". Декомпрессия бир топ ылдамыраак жана киргизүү/чыгаруу ылдамдыгы менен чектелет. Бир жиптеги бир физикалык өзөк 3-4 ГБ/сек ачуу ылдамдыгын оңой камсыз кылат.
Бул декомпрессия процессинде матчты издөө операциясынын жоктугу менен шартталган, ал кысуу учурунда процессордун жана кэш эстутумдун негизги ресурстарын "жеп салат".
Кысылган маалыматтарды сактоонун ишенимдүүлүгү
Маалыматтарды кысууну (архивчилер) колдонгон программалык камсыздоонун бүткүл классынын аталышы айтып тургандай, алар маалыматты узак мөөнөттүү сактоо үчүн жылдар бою эмес, кылымдар жана миң жылдыктар үчүн иштелип чыккан...
Сактоо учурунда, сактагыч медиа кээ бир маалыматтарды жоготот, бул жерде бир мисал:
Бул “аналогдук” маалымат алып жүрүүчүнүн жашы миң жыл, кээ бир фрагменттери жоголгон, бирок жалпысынан маалымат “окууга болот”...
Заманбап санариптик маалыматтарды сактоо тутумдарын жана алар үчүн санариптик медианы жооптуу өндүрүүчүлөрдүн бири дагы 75 жылдан ашык убакыт бою маалыматтардын толук коопсуздугуна кепилдик бербейт.
А бул маселе, бирок кийинкиге калтырылган маселе, аны биздин урпактар чечет...
Санарип маалыматтарды сактоо тутумдары маалыматтарды 75 жылдан кийин гана жоготуп коюшу мүмкүн, маалыматтардагы каталар каалаган убакта пайда болушу мүмкүн, жада калса аларды жазуу учурунда, алар ашыкча колдонуу жана каталарды оңдоо системалары менен оңдоо аркылуу бул бурмалоолорду минималдаштырууга аракет кылышат. Кыскартуу жана оңдоо системалары ар дайым жоголгон маалыматты калыбына келтире албайт жана алар калыбына келтирсе, калыбына келтирүү операциясы туура аяктаганына кепилдик жок.
Бул дагы чоң көйгөй, бирок кийинкиге калтырылган эмес, азыркы учур.
Санариптик маалыматтарды архивдөө үчүн колдонулган заманбап компрессорлор сөздүк ыкмасынын ар кандай модификацияларына негизделген жана мындай архивдер үчүн маалыматтын бир бөлүгүн жоготуу өлүмгө дуушар болот, ал тургай, мындай кырдаал үчүн белгиленген термин бар - "сынган" архив; ...
Сөздүк кысуу менен архивде маалыматты сактоонун ишенимдүүлүгүнүн төмөндүгү кысылган маалыматтардын түзүлүшү менен байланыштуу. Мындай архивдеги маалымат баштапкы текстти камтыбайт, сөздүктөгү жазуулардын номерлери ошол жерде сакталат жана сөздүктүн өзү учурдагы кысылган текст тарабынан динамикалык түрдө өзгөртүлгөн. Эгерде архив фрагменти жоголсо же бузулса, бардык кийинки архивдик жазууларды сөздүктөгү жазуунун мазмуну же узундугу боюнча аныктоо мүмкүн эмес, анткени сөздүктүн номери эмнеге дал келери түшүнүксүз.
Мындай “бузулган” архивден маалыматты калыбына келтирүү мүмкүн эмес.
RTT алгоритми кысылган маалыматтарды сактоонун ишенимдүү ыкмасына негизделген. Ал кайталануучу фрагменттерди эсепке алуунун индекстик ыкмасын колдонот. Кысууга мындай мамиле сактоочу чөйрөдөгү маалыматтын бурмаланышынын кесепеттерин минималдаштырууга жана көп учурларда маалыматты сактоо учурунда пайда болгон бурмалоолорду автоматтык түрдө оңдоого мүмкүндүк берет.
Бул индекс кысуу учурунда архивдик файл эки талааны камтыганына байланыштуу:
- андан алынып кайталануучу бөлүмдөр менен баштапкы текст талаасы;
- индекс талаасы.
Маалыматты калыбына келтирүү үчүн өтө маанилүү болгон индекс талаасынын көлөмү чоң эмес жана маалыматтарды ишенимдүү сактоо үчүн кайталанышы мүмкүн. Демек, баштапкы тексттин же индекс массивинин фрагменти жоголсо да, башка бардык маалымат "аналогдук" сактоочу чөйрө менен сүрөттөгүдөй көйгөйсүз калыбына келтирилет.
Алгоритмдин кемчиликтери
Кемчиликсиз артыкчылыгы жок. Индекс кысуу ыкмасы кыска кайталануучу тизмектерди кыспайт. Бул индекс ыкмасынын чектөөлөр менен шартталган. Индекстердин көлөмү кеминде 3 байт жана өлчөмү 12 байтка чейин болушу мүмкүн. Эгерде кайталоо аны сыпаттаган индекстен кичирээк өлчөм менен кездешсе, кысылган файлда мындай кайталануулар канчалык көп аныкталганына карабастан, ал эсепке алынбайт.
Салттуу сөздүк кысуу ыкмасы кыска узундуктагы бир нече кайталоону эффективдүү кысып, ошондуктан индекстин кысуусуна караганда жогорку кысуу катышына жетишет. Ырас, бул сөздүк методу индекстик ыкмага караганда маалыматтарды эффективдүү кысуу үчүн борбордук процессорго жогорку жүктөмдүн эсебинен жетишилет, ал маалыматтарды иштетүү ылдамдыгын секундасына 10-20 мегабайтка чейин төмөндөтүшү керек; толук CPU жүгү менен эсептөө орнотуулары.
Мындай төмөн ылдамдык заманбап маалыматтарды сактоо системалары үчүн кабыл алынгыс жана практикалык караганда көбүрөөк "академиялык" кызыкчылык туудурат.
Маалыматты кысуу даражасы иштелип жаткан RTT алгоритминин (RTT-Max) кийинки модификациясында кыйла жогорулайт.
Ошентип, адаттагыдай эле, улантуу керек ...
Source: www.habr.com
