Artikel ini sudah pun menjadi yang kedua dalam topik pemampatan data berkelajuan tinggi. Artikel pertama menerangkan pemampat yang beroperasi pada kelajuan 10 GB/saat. setiap teras pemproses (mampatan minimum, RTT-Min).
Pemampat ini telah pun dilaksanakan dalam peralatan pendua forensik untuk pemampatan berkelajuan tinggi bagi pembuangan media storan dan meningkatkan kekuatan kriptografi; ia juga boleh digunakan untuk memampatkan imej mesin maya dan fail swap RAM apabila menyimpannya pada kelajuan tinggi pemacu SSD.
Artikel pertama juga mengumumkan pembangunan algoritma pemampatan untuk memampatkan salinan sandaran pemacu cakera HDD dan SSD (mampatan sederhana, RTT-Mid) dengan parameter pemampatan data yang dipertingkatkan dengan ketara. Sekarang, pemampat ini sudah siap sepenuhnya dan artikel ini adalah mengenainya.
Pemampat yang melaksanakan algoritma RTT-Mid menyediakan nisbah mampatan yang setanding dengan pengarkib standard seperti WinRar, 7-Zip, beroperasi dalam mod kelajuan tinggi. Pada masa yang sama, kelajuan operasinya sekurang-kurangnya satu susunan magnitud yang lebih tinggi.
Kelajuan pembungkusan/pembongkaran data ialah parameter kritikal yang menentukan skop penggunaan teknologi pemampatan. Tidak mungkin sesiapa akan berfikir untuk memampatkan terabait data pada kelajuan 10-15 Megabait sesaat (ini betul-betul kelajuan pengarkib dalam mod mampatan standard), kerana ia akan mengambil masa hampir dua puluh jam dengan beban pemproses penuh. .
Sebaliknya, terabait yang sama boleh disalin pada kelajuan tertib 2-3Gigabait sesaat dalam masa kira-kira sepuluh minit.
Oleh itu, pemampatan maklumat volum besar adalah penting jika ia dilakukan pada kelajuan tidak lebih rendah daripada kelajuan input/output sebenar. Untuk sistem moden ini sekurang-kurangnya 100 Megabait sesaat.
Pemampat moden boleh menghasilkan kelajuan sedemikian hanya dalam mod "cepat". Dalam mod semasa inilah kami akan membandingkan algoritma RTT-Mid dengan pemampat tradisional.
Ujian perbandingan algoritma pemampatan baharu
Pemampat RTT-Mid berfungsi sebagai sebahagian daripada program ujian. Dalam aplikasi "berfungsi" sebenar ia berfungsi dengan lebih pantas, ia menggunakan multithreading dengan bijak dan menggunakan pengkompil "biasa", bukan C#.
Memandangkan pemampat yang digunakan dalam ujian perbandingan dibina berdasarkan prinsip yang berbeza dan jenis pemampatan data yang berbeza secara berbeza, untuk objektiviti ujian, kaedah mengukur "suhu purata di hospital" telah digunakan...
Fail pembuangan sektor demi sektor bagi cakera logik dengan sistem pengendalian Windows 10 telah dicipta; ini adalah campuran paling semula jadi dari pelbagai struktur data yang sebenarnya tersedia pada setiap komputer. Memampatkan fail ini akan membolehkan anda membandingkan kelajuan dan tahap pemampatan algoritma baharu dengan pemampat paling canggih yang digunakan dalam pengarkib moden.
Berikut ialah fail dump:
Fail dump telah dimampatkan menggunakan pemampat PTT-Mid, 7-zip dan WinRar. Pemampat WinRar dan 7-zip ditetapkan pada kelajuan maksimum.
Pemampat berjalan 7-Zip:
Ia memuatkan pemproses sebanyak 100%, manakala kelajuan purata membaca pembuangan asal ialah kira-kira 60 MegaBytes/saat.
Pemampat berjalan WinRAR:
Keadaannya adalah sama, beban pemproses hampir 100%, kelajuan bacaan dump purata adalah kira-kira 125 Megabait/saat.
Seperti dalam kes sebelumnya, kelajuan pengarkib dihadkan oleh keupayaan pemproses.
Program ujian pemampat kini sedang berjalan RTT-Pertengahan:
Tangkapan skrin menunjukkan bahawa pemproses dimuatkan pada 50% dan melahu sepanjang masa, kerana tiada tempat untuk memuat naik data yang dimampatkan. Cakera muat naik data (Disk 0) hampir dimuatkan sepenuhnya. Kelajuan membaca data (Disk 1) sangat berbeza, tetapi secara purata lebih daripada 200 MegaBytes/saat.
Kelajuan pemampat dihadkan dalam kes ini dengan keupayaan untuk menulis data termampat ke Cakera 0.
Sekarang nisbah mampatan arkib yang terhasil:
Dapat dilihat bahawa pemampat RTT-Mid melakukan kerja pemampatan yang terbaik; arkib yang dicipta adalah 1,3 GigaBytes lebih kecil daripada arkib WinRar dan 2,1 GigaBytes lebih kecil daripada arkib 7z.
Masa yang dihabiskan untuk membuat arkib:
- 7-zip - 26 minit 10 saat;
- WinRar - 17 minit 40 saat;
- RTT-Mid β 7 minit 30 saat.
Oleh itu, walaupun ujian, program yang tidak dioptimumkan, menggunakan algoritma RTT-Mid, dapat mencipta arkib lebih daripada dua setengah kali lebih pantas, manakala arkib ternyata jauh lebih kecil daripada pesaingnya...
Mereka yang tidak percaya tangkapan skrin boleh menyemak sendiri kesahihannya. Program ujian boleh didapati di , muat turun dan semak.
Tetapi hanya pada pemproses dengan sokongan AVX-2, tanpa sokongan untuk arahan ini pemampat tidak berfungsi, dan tidak menguji algoritma pada pemproses AMD yang lebih lama, mereka lambat dari segi melaksanakan arahan AVX...
Kaedah mampatan digunakan
Algoritma menggunakan kaedah untuk mengindeks serpihan teks berulang dalam butiran bait. Kaedah pemampatan ini telah lama diketahui, tetapi tidak digunakan kerana operasi pemadanan adalah sangat mahal dari segi sumber yang diperlukan dan memerlukan lebih banyak masa daripada membina kamus. Jadi algoritma RTT-Mid ialah contoh klasik untuk bergerak "kembali ke masa hadapan"...
Pemampat PTT menggunakan pengimbas carian padanan berkelajuan tinggi yang unik, yang membolehkan kami mempercepatkan proses pemampatan. Pengimbas buatan sendiri, ini adalah "pesona saya...", "ia agak mahal, kerana ia buatan tangan sepenuhnya" (ditulis dalam penghimpun).
Pengimbas carian padanan dibuat mengikut skema kebarangkalian dua peringkat: pertama, kehadiran "tanda" padanan diimbas, dan hanya selepas "tanda" dikenal pasti di tempat ini, prosedur untuk mengesan padanan sebenar dimulakan.
Tetingkap carian padanan mempunyai saiz yang tidak dapat diramalkan, bergantung pada tahap entropi dalam blok data yang diproses. Untuk data rawak sepenuhnya (tidak boleh mampat) ia mempunyai saiz megabait, untuk data dengan ulangan ia sentiasa lebih besar daripada megabait.
Tetapi banyak format data moden tidak boleh dimampatkan dan menjalankan pengimbas intensif sumber melaluinya adalah sia-sia dan membazir, jadi pengimbas menggunakan dua mod operasi. Pertama, bahagian teks sumber dengan kemungkinan pengulangan dicari; operasi ini juga dijalankan menggunakan kaedah kebarangkalian dan dilakukan dengan sangat cepat (pada kelajuan 4-6 GigaBytes/saat). Kawasan yang mempunyai kemungkinan padanan kemudiannya diproses oleh pengimbas utama.
Mampatan indeks tidak begitu cekap, anda perlu menggantikan serpihan pendua dengan indeks, dan tatasusunan indeks mengurangkan nisbah mampatan dengan ketara.
Untuk meningkatkan nisbah mampatan, bukan sahaja padanan lengkap rentetan bait diindeks, tetapi juga separa, apabila rentetan tersebut mengandungi bait yang sepadan dan tidak sepadan. Untuk melakukan ini, format indeks termasuk medan topeng padanan yang menunjukkan bait padanan dua blok. Untuk pemampatan yang lebih besar, pengindeksan digunakan untuk menindih beberapa blok padanan separa pada blok semasa.
Semua ini memungkinkan untuk mendapatkan dalam pemampat PTT-Mid nisbah mampatan yang setanding dengan pemampat yang dibuat menggunakan kaedah kamus, tetapi berfungsi dengan lebih pantas.
Kelajuan algoritma pemampatan baharu
Jika pemampat beroperasi dengan penggunaan memori cache secara eksklusif (4 Megabait diperlukan setiap utas), maka kelajuan operasi berjulat dari 700-2000 Megabait/saat. setiap teras pemproses, bergantung pada jenis data yang dimampatkan dan bergantung sedikit pada kekerapan operasi pemproses.
Dengan pelaksanaan berbilang benang pemampat, kebolehskalaan yang berkesan ditentukan oleh saiz cache tahap ketiga. Sebagai contoh, mempunyai 9 MegaByte memori cache "di atas kapal", tidak ada gunanya melancarkan lebih daripada dua benang mampatan; kelajuan tidak akan meningkat daripada ini. Tetapi dengan cache 20 Megabait, anda sudah boleh menjalankan lima utas mampatan.
Juga, kependaman RAM menjadi parameter penting yang menentukan kelajuan pemampat. Algoritma menggunakan akses rawak kepada OP, sebahagian daripadanya tidak masuk ke dalam memori cache (kira-kira 10%) dan ia perlu melahu, menunggu data daripada OP, yang mengurangkan kelajuan operasi.
Secara ketara mempengaruhi kelajuan pemampat dan operasi sistem input/output data. Permintaan kepada OP daripada blok I/O meminta data daripada CPU, yang juga mengurangkan kelajuan mampatan. Masalah ini penting untuk komputer riba dan desktop; untuk pelayan ia kurang penting kerana unit kawalan akses bas sistem yang lebih maju dan RAM berbilang saluran.
Sepanjang teks dalam artikel kita bercakap tentang pemampatan; penyahmampatan kekal di luar skop artikel ini kerana "semuanya diliputi dalam coklat". Penyahmampatan adalah lebih pantas dan dihadkan oleh kelajuan I/O. Satu teras fizikal dalam satu utas dengan mudah memberikan kelajuan pembongkaran 3-4 GB/saat.
Ini disebabkan oleh ketiadaan operasi carian padanan semasa proses penyahmampatan, yang "memakan" sumber utama pemproses dan memori cache semasa pemampatan.
Kebolehpercayaan storan data termampat
Seperti yang dicadangkan oleh nama seluruh kelas perisian yang menggunakan pemampatan data (pengarkib), ia direka untuk penyimpanan maklumat jangka panjang, bukan selama bertahun-tahun, tetapi selama berabad-abad dan beribu tahun...
Semasa penyimpanan, media storan kehilangan beberapa data, berikut ialah contoh:
Pembawa maklumat "analog" ini berusia seribu tahun, beberapa serpihan telah hilang, tetapi secara umum maklumat itu "boleh dibaca"...
Tiada pengeluar yang bertanggungjawab bagi sistem penyimpanan data digital moden dan media digital untuk mereka memberikan jaminan keselamatan data yang lengkap selama lebih daripada 75 tahun.
Dan ini adalah masalah, tetapi masalah yang ditangguhkan, keturunan kita akan menyelesaikannya...
Sistem penyimpanan data digital boleh kehilangan data bukan sahaja selepas 75 tahun, ralat dalam data boleh muncul pada bila-bila masa, malah semasa rakamannya, mereka cuba meminimumkan herotan ini dengan menggunakan redundansi dan membetulkannya dengan sistem pembetulan ralat. Sistem redundansi dan pembetulan tidak boleh sentiasa memulihkan maklumat yang hilang, dan jika ia berlaku, tiada jaminan bahawa operasi pemulihan telah selesai dengan betul.
Dan ini juga masalah besar, tetapi bukan masalah tertunda, tetapi masalah semasa.
Pemampat moden yang digunakan untuk mengarkibkan data digital dibina berdasarkan pelbagai pengubahsuaian kaedah kamus, dan untuk arkib sedemikian kehilangan sekeping maklumat akan menjadi peristiwa yang membawa maut; malah terdapat istilah yang ditetapkan untuk situasi sedemikian - arkib "pecah" ...
Kebolehpercayaan yang rendah untuk menyimpan maklumat dalam arkib dengan pemampatan kamus dikaitkan dengan struktur data yang dimampatkan. Maklumat dalam arkib sedemikian tidak mengandungi teks sumber, bilangan entri dalam kamus disimpan di sana, dan kamus itu sendiri diubah suai secara dinamik oleh teks termampat semasa. Jika serpihan arkib hilang atau rosak, semua entri arkib berikutnya tidak boleh dikenal pasti sama ada mengikut kandungan atau dengan panjang entri dalam kamus, kerana tidak jelas dengan nombor entri kamus yang sepadan.
Adalah mustahil untuk memulihkan maklumat daripada arkib "pecah" sedemikian.
Algoritma RTT adalah berdasarkan kaedah yang lebih dipercayai untuk menyimpan data termampat. Ia menggunakan kaedah indeks perakaunan untuk serpihan berulang. Pendekatan pemampatan ini membolehkan anda meminimumkan akibat herotan maklumat pada medium storan, dan dalam banyak kes, herotan yang timbul semasa penyimpanan maklumat secara automatik diperbetulkan.
Ini disebabkan oleh fakta bahawa fail arkib dalam kes pemampatan indeks mengandungi dua medan:
- medan teks sumber dengan bahagian ulangan dialih keluar daripadanya;
- medan indeks.
Medan indeks, yang penting untuk pemulihan maklumat, tidak bersaiz besar dan boleh diduplikasi untuk penyimpanan data yang boleh dipercayai. Oleh itu, walaupun serpihan teks sumber atau tatasusunan indeks hilang, semua maklumat lain akan dipulihkan tanpa masalah, seperti dalam gambar dengan medium storan "analog".
Kelemahan algoritma
Tiada kelebihan tanpa kekurangan. Kaedah mampatan indeks tidak memampatkan urutan berulang pendek. Ini disebabkan oleh batasan kaedah indeks. Indeks bersaiz sekurang-kurangnya 3 bait dan boleh bersaiz sehingga 12 bait. Jika pengulangan ditemui dengan saiz yang lebih kecil daripada indeks yang menerangkannya, maka ia tidak diambil kira, tidak kira berapa kerap pengulangan tersebut dikesan dalam fail yang dimampatkan.
Kaedah pemampatan kamus tradisional secara berkesan memampatkan berbilang ulangan panjang pendek dan oleh itu mencapai nisbah mampatan yang lebih tinggi daripada mampatan indeks. Benar, ini dicapai kerana beban tinggi pada pemproses pusat; agar kaedah kamus mula memampatkan data dengan lebih cekap daripada kaedah indeks, ia perlu mengurangkan kelajuan pemprosesan data kepada 10-20 megabait sesaat pada sebenar. pemasangan pengkomputeran dengan beban CPU penuh.
Kelajuan rendah sedemikian tidak boleh diterima untuk sistem penyimpanan data moden dan lebih "akademik" minat daripada praktikal.
Tahap pemampatan maklumat akan meningkat dengan ketara dalam pengubahsuaian seterusnya bagi algoritma RTT (RTT-Max), yang sudah dalam pembangunan.
Jadi, seperti biasa, akan diteruskan...
Sumber: www.habr.com