Энэ нийтлэл нь өндөр хурдны өгөгдлийг шахах сэдвийн хоёр дахь нийтлэл юм. Эхний нийтлэлд 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 үйлдлийн систем бүхий логик дискний салбар тус бүрээр дамп файлыг үүсгэсэн бөгөөд энэ нь компьютер бүрт байдаг төрөл бүрийн өгөгдлийн бүтцийн хамгийн байгалийн хольц юм. Энэ файлыг шахах нь шинэ алгоритмын шахалтын хурд, зэргийг орчин үеийн архивчид ашигладаг хамгийн дэвшилтэт компрессоруудтай харьцуулах боломжийг олгоно.
Энд dump файл байна:
Дамп файлыг 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 компрессор нь өвөрмөц өндөр хурдтай тохирох хайлтын сканнер ашигладаг бөгөөд энэ нь шахалтын процессыг хурдасгах боломжийг бидэнд олгодог. Өөрөө хийсэн сканнер, энэ бол "миний сэтгэл татам ...", "энэ нь маш үнэтэй, учир нь энэ нь бүрэн гараар хийгдсэн" (ассемблер дээр бичсэн).
Тоглолтын хайлтын сканнер нь хоёр түвшний магадлалын схемийн дагуу хийгддэг: нэгдүгээрт, тоглолтын "тэмдэг" байгаа эсэхийг сканнердаж, зөвхөн энэ газарт "тэмдэг" тодорхойлогдсоны дараа жинхэнэ таарч байгааг илрүүлэх процедурыг хийдэг. эхэлж байна.
Тоглолтын хайлтын цонх нь боловсруулсан өгөгдлийн блок дахь энтропийн зэргээс хамаарч урьдчилан тааварлах боломжгүй хэмжээтэй байдаг. Бүрэн санамсаргүй (шахагдах боломжгүй) өгөгдлийн хувьд энэ нь мегабайт хэмжээтэй, давталттай өгөгдлийн хувьд үргэлж мегабайтаас их байдаг.
Гэвч орчин үеийн олон өгөгдлийн форматууд нь шахагдах боломжгүй бөгөөд тэдгээрээр дамжуулан нөөц ихтэй сканнер ажиллуулах нь ашиггүй бөгөөд үрэлгэн байдаг тул сканнер нь хоёр үйлдлийн горимыг ашигладаг. Эхлээд эх текстийн боломжит давталт бүхий хэсгүүдийг хайж олох бөгөөд энэ үйлдлийг магадлалын аргыг ашиглан гүйцэтгэдэг бөгөөд маш хурдан (4-6 Гигабайт / сек хурдтай) гүйцэтгэдэг. Дараа нь таарч болох хэсгүүдийг үндсэн сканнер боловсруулдаг.
Индекс шахах нь тийм ч үр дүнтэй биш тул давхардсан хэсгүүдийг индексээр солих шаардлагатай бөгөөд индексийн массив нь шахалтын харьцааг эрс бууруулдаг.
Шахалтын харьцааг нэмэгдүүлэхийн тулд зөвхөн байт мөрүүдийн бүрэн тохирчуудыг индексжүүлээд зогсохгүй мөр нь таарсан ба тохирохгүй байт агуулж байгаа тохиолдолд хэсэгчилсэн мөрүүдийг индексжүүлдэг. Үүнийг хийхийн тулд индексийн формат нь хоёр блокийн тохирох байтыг харуулсан тохирох маск талбарыг агуулна. Илүү их шахалт хийхийн тулд индексжүүлэлтийг одоогийн блок дээр хэсэгчлэн тохирох хэд хэдэн блокуудыг давхарлахын тулд ашигладаг.
Энэ бүхэн нь PTT-Mid компрессорыг толь бичгийн аргаар хийсэн компрессортой харьцуулахуйц шахалтын харьцааг олж авах боломжийг олгосон боловч илүү хурдан ажилладаг.
Шинэ шахалтын алгоритмын хурд
Хэрэв компрессор нь кэш санах ойг онцгойлон ашигладаг бол (нэг урсгалд 4 мегабайт шаардлагатай) ажиллах хурд нь 700-2000 мегабайт / сек хооронд хэлбэлздэг. процессорын цөм тус бүр нь шахагдаж буй өгөгдлийн төрлөөс хамаарч процессорын ажиллах давтамжаас бага зэрэг хамаардаг.
Компрессорыг олон урсгалтай хэрэгжүүлснээр үр дүнтэй өргөтгөх чадварыг гурав дахь түвшний кэшийн хэмжээгээр тодорхойлдог. Жишээлбэл, "самбар дээр" 9 мегабайт кэш санах ойтой бол хоёроос илүү шахалтын урсгалыг эхлүүлэх нь утгагүй бөгөөд үүнээс хурд нэмэгдэхгүй. Гэхдээ 20 мегабайтын кэштэй бол та аль хэдийн таван шахалтын урсгалыг ажиллуулж болно.
Мөн RAM-ийн хоцрогдол нь компрессорын хурдыг тодорхойлдог чухал параметр болдог. Алгоритм нь OP-д санамсаргүй хандалтыг ашигладаг бөгөөд тэдгээрийн зарим нь кэш санах ойд ордоггүй (ойролцоогоор 10%), OP-ээс өгөгдлийг хүлээж, ажиллахгүй байх ёстой бөгөөд энэ нь үйлдлийн хурдыг бууруулдаг.
Компрессорын хурд болон өгөгдөл оруулах/гаралтын системийн ажиллагаанд ихээхэн нөлөөлдөг. Оролт гаралтын блокоос OP-д хийх хүсэлтүүд нь CPU-ээс өгөгдөл авах хүсэлтүүд бөгөөд энэ нь шахалтын хурдыг бууруулдаг. Энэ асуудал зөөврийн компьютер болон ширээний компьютерт чухал ач холбогдолтой бол серверийн хувьд илүү дэвшилтэт системийн автобусны хандалтын хяналтын нэгж болон олон сувгийн RAM-тай холбоотойгоор ач холбогдол багатай.
Өгүүллийн текстийн туршид бид шахалтын тухай ярьдаг; "бүх зүйл шоколадаар бүрхэгдсэн" тул шахалт нь энэ өгүүллийн хамрах хүрээнээс гадуур хэвээр байна. Декомпресс нь илүү хурдан бөгөөд оролт гаралтын хурдаар хязгаарлагддаг. Нэг утас дахь нэг физик цөм нь 3-4 ГБ/сек хурдыг задлах хурдыг хялбархан хангадаг.
Энэ нь шахалтын явцад процессор болон кэш санах ойн үндсэн нөөцийг "иддэг" шахалтыг задлах явцад тохирох хайлтын ажиллагаа байхгүйтэй холбоотой юм.
Шахсан өгөгдөл хадгалах найдвартай байдал
Өгөгдлийн шахалтыг (архивлагч) ашигладаг бүхэл бүтэн ангиллын программ хангамжийн нэрнээс харахад тэдгээр нь олон жилийн турш биш, харин олон зуун, мянган жилийн турш мэдээллийг урт хугацаанд хадгалах зориулалттай...
Хадгалах явцад хадгалах хэрэгсэл зарим өгөгдлийг алддаг, жишээ нь:
Энэхүү “аналог” мэдээлэл зөөгч нь мянган жилийн настай, зарим хэлтэрхий нь алдагдсан ч ерөнхийдөө мэдээлэл нь “унших боломжтой”...
Орчин үеийн дижитал өгөгдөл хадгалах систем, дижитал зөөвөрлөгчийг хариуцлагатай үйлдвэрлэгчдийн аль нь ч 75 гаруй жилийн турш мэдээллийн бүрэн аюулгүй байдлын баталгааг өгдөггүй.
Тэгээд энэ асуудал ч хойшлогдсон асуудал, үр удам маань шийднэ дээ...
Дижитал өгөгдөл хадгалах систем нь зөвхөн 75 жилийн дараа өгөгдөл алддаггүй, өгөгдөлд ямар ч үед алдаа гардаг, тэр ч байтугай бичлэг хийх явцад ч эдгээр гажуудлыг багасгахын тулд илүүдлийг ашиглах, алдаа засах системээр засахыг хичээдэг. Илүүдэл болон залруулгын систем нь алдагдсан мэдээллийг үргэлж сэргээж чаддаггүй бөгөөд хэрэв сэргээсэн бол сэргээх ажиллагаа зөв хийгдсэн гэсэн баталгаа байхгүй.
Энэ бол бас том асуудал, гэхдээ хойшлогдсон асуудал биш, харин одоо байгаа асуудал юм.
Дижитал өгөгдлийг архивлахад ашигладаг орчин үеийн компрессорууд нь толь бичгийн аргын янз бүрийн өөрчлөлтүүд дээр бүтээгдсэн бөгөөд ийм архивын хувьд нэг хэсэг мэдээлэл алдах нь үхэлд хүргэх болно; ийм нөхцөл байдлын хувьд тогтоосон нэр томъёо байдаг - "эвдэрсэн" архив ...
Толь бичгийн шахалтаар архивт мэдээллийг хадгалах найдвартай байдал бага байгаа нь шахсан өгөгдлийн бүтэцтэй холбоотой юм. Ийм архивын мэдээлэл нь эх бичвэрийг агуулаагүй, толь бичгийн оруулгуудын тоо тэнд хадгалагддаг бөгөөд толь бичиг өөрөө одоогийн шахсан текстээр динамикаар өөрчлөгддөг. Архивын фрагмент алдагдсан эсвэл гэмтсэн тохиолдолд толь бичгийн дугаар нь юутай тохирч байгаа нь тодорхойгүй тул архивын дараагийн бүх оруулгуудыг толь бичгийн агуулга, уртаар нь тодорхойлох боломжгүй.
Ийм "эвдэрсэн" архивын мэдээллийг сэргээх боломжгүй юм.
RTT алгоритм нь шахсан өгөгдлийг хадгалах илүү найдвартай арга дээр суурилдаг. Энэ нь давтагдах хэсгүүдийг бүртгэх индексийн аргыг ашигладаг. Шахалтын энэхүү арга нь хадгалах орчин дахь мэдээллийн гажуудлын үр дагаврыг багасгах боломжийг олгодог бөгөөд ихэнх тохиолдолд мэдээллийг хадгалах явцад үүссэн гажуудлыг автоматаар засах боломжийг олгодог.
Энэ нь индексийг шахах тохиолдолд архивын файл нь хоёр талбар агуулж байгаатай холбоотой юм.
- үүнээс хасагдсан давтагдах хэсгүүдтэй эх текстийн талбар;
- индекс талбар.
Мэдээллийг сэргээхэд чухал үүрэг гүйцэтгэдэг индексийн талбар нь том хэмжээтэй биш бөгөөд өгөгдлийг найдвартай хадгалах үүднээс хуулбарлах боломжтой. Тиймээс, эх текст эсвэл индексийн массивын хэсэг алдагдсан ч бусад бүх мэдээлэл "аналог" хадгалах хэрэгсэлтэй зураг дээрх шиг асуудалгүйгээр сэргээгдэх болно.
Алгоритмын сул тал
Сул талгүй давуу тал гэж байхгүй. Индекс шахах арга нь богино давтагдах дарааллыг шахдаггүй. Энэ нь индексийн аргын хязгаарлалттай холбоотой юм. Индекс нь дор хаяж 3 байт хэмжээтэй байх ба 12 байт хүртэл хэмжээтэй байж болно. Хэрэв давталтыг тодорхойлсон индексээс бага хэмжээтэй давталттай тулгарвал шахсан файлд ийм давталтыг хэр олон удаа илрүүлж байгаагаас үл хамааран үүнийг тооцохгүй.
Уламжлалт толь бичгийн шахалтын арга нь богино урттай олон давталтыг үр дүнтэй шахдаг тул индексийн шахалтаас илүү шахалтын харьцаатай байдаг. Үнэн бол энэ нь төв процессорын ачаалал ихтэй байдаг тул толь бичгийн аргыг индексийн аргаас илүү үр дүнтэй шахаж эхлэхийн тулд өгөгдөл боловсруулах хурдыг секундэд 10-20 мегабайт хүртэл бууруулах шаардлагатай болдог. CPU-ийн бүрэн ачаалалтай тооцоолох суурилуулалт.
Ийм бага хурд нь орчин үеийн өгөгдөл хадгалах системд хүлээн зөвшөөрөгдөхгүй бөгөөд практик гэхээсээ илүү "эрдмийн" сонирхолтой байдаг.
Мэдээллийн шахалтын түвшинг аль хэдийн боловсруулж байгаа RTT алгоритмын (RTT-Max) дараагийн өөрчлөлтөд мэдэгдэхүйц нэмэгдүүлэх болно.
Үргэлж үргэлжилсэн шигээ...
Эх сурвалж: www.habr.com