Artikel ini sudah menjadi yang kedua dalam topik kompresi data berkecepatan tinggi. Artikel pertama menjelaskan kompresor beroperasi pada kecepatan 10GB / s. per inti prosesor (kompresi minimum, RTT-Min).
Kompresor ini, yang sudah diimplementasikan dalam peralatan duplikator forensik untuk kompresi kecepatan tinggi dari tempat penyimpanan media dan meningkatkan kekuatan kriptografi, juga dapat digunakan untuk mengompresi gambar mesin virtual dan file swap RAM sambil menyimpannya pada drive SSD berkecepatan tinggi.
Artikel pertama juga mengumumkan pengembangan algoritma kompresi untuk mengompresi cadangan HDD dan drive disk SSD (kompresi menengah, RTT-Mid) dengan parameter kompresi data yang ditingkatkan secara signifikan. Sampai saat ini, kompresor ini benar-benar siap dan artikel ini tentang dia.
Kompresor yang mengimplementasikan algoritma RTT-Mid menyediakan rasio kompresi yang sebanding dengan pengarsip standar seperti WinRar, 7-Zip, yang beroperasi dalam mode kecepatan tinggi. Apalagi kecepatannya setidaknya merupakan urutan besarnya lebih tinggi.
Kecepatan pengemasan / pembongkaran data merupakan parameter penting yang menentukan ruang lingkup teknologi kompresi. Tidak mungkin ada orang yang berpikir untuk mengompresi data terabyte pada kecepatan 10-15 megabyte per detik (ini adalah kecepatan pengarsip dalam mode kompresi standar), karena akan memakan waktu hampir dua puluh jam untuk memuat prosesor sepenuhnya ...
Di sisi lain, terabyte yang sama dapat disalin dengan kecepatan urutan 2-3 Gigabytes per detik selama sekitar sepuluh menit.
Oleh karena itu, kompresi informasi pada volume yang besar relevan jika dilakukan pada kecepatan yang tidak lebih rendah dari kecepatan input / output nyata. Untuk sistem modern, ini setidaknya 100 megabyte per detik.
Kompresor modern hanya dapat menghasilkan kecepatan seperti itu dalam mode "cepat". Dalam mode saat ini kita akan membandingkan algoritma RTT-Mid dengan kompresor tradisional.
Pengujian komparatif dari algoritma kompresi baru
Kompresor RTT-Mid bekerja sebagai bagian dari program pengujian. Dalam aplikasi "bekerja" yang sebenarnya, ia bekerja lebih cepat, multithreading digunakan dengan benar di sana, dan kompiler "normal" digunakan, bukan C #.
Karena kompresor yang digunakan dalam uji komparatif dibangun berdasarkan prinsip yang berbeda dan tipe data yang berbeda dikompresi secara berbeda, untuk obyektivitas tes kami menggunakan metode pengukuran "suhu rata-rata di rumah sakit" ...
File dump sektor per sektor dari drive logis dengan sistem operasi Windows 10 telah dibuat, ini adalah campuran paling alami dari berbagai struktur data yang sebenarnya tersedia di setiap komputer. Kompresi file ini akan memungkinkan Anda untuk membandingkan kecepatan dan tingkat kompresi algoritma baru dengan kompresor paling canggih yang digunakan dalam pengarsipan modern.
Ini file dumpnya:
File dump dikompresi oleh PTT-Mid, 7-zip, kompresor WinRar. Kompresor WinRar dan 7-zip diatur ke kecepatan maksimum.
Kompresor
7-zip bekerja:
Ini memuat prosesor 100%, sementara kecepatan baca rata-rata dump asli adalah sekitar 60 megabyte / detik.
WinRar compressor bekerja:
Situasinya mirip, beban prosesor hampir 100%, kecepatan baca rata-rata dump adalah sekitar 125 Megabita / detik.
Seperti pada kasus sebelumnya, kecepatan pengarsip dibatasi oleh kemampuan prosesor.
Program uji kompresor
RTT-Mid sekarang berfungsi:
Tangkapan layar menunjukkan bahwa prosesor dimuat 50% dan tidak digunakan selama sisa waktu, karena tidak ada tempat untuk mengunduh data yang dikompresi. Disk unggah data (Disk 0) dimuat hampir sepenuhnya. Kecepatan membaca data (Disk 1) banyak, tetapi rata-rata lebih dari 200 megabita / detik.
Kecepatan kompresor dibatasi dalam hal ini oleh kemampuan untuk menulis data terkompresi ke Disk 0.
Sekarang rasio kompresi arsip yang dihasilkan:
Dapat dilihat bahwa kompresor RTT-Mid menangani kompresi lebih baik daripada siapa pun, arsip yang dibuatnya adalah 1,3 Gigabytes lebih kecil dari arsip WinRar dan 2,1 Gigabytes lebih kecil dari arsip 7z.
Waktu yang dihabiskan untuk membuat arsip:
- 7-zip - 26 menit 10 detik;
- WinRar - 17 menit 40 detik;
- RTT-Mid - 7 menit 30 detik.
Dengan demikian, bahkan sebuah tes, bukan program yang dioptimalkan, menggunakan algoritma RTT-Mid, mampu membuat arsip lebih dari dua setengah kali lebih cepat, sedangkan arsip ternyata jauh lebih kecil daripada pesaing ...
Mereka yang tidak percaya tangkapan layar dapat memverifikasi akurasinya sendiri. Program pengujian tersedia di
sini , unduh dan periksa.
Tetapi hanya pada prosesor dengan dukungan untuk AVX-2, tanpa dukungan instruksi ini, kompresor tidak bekerja, dan tidak menguji algoritma pada prosesor AMD yang lebih lama, mereka lambat dalam hal menjalankan perintah AVX ...
Metode Kompresi Digunakan
Algoritme menggunakan metode pengindeksan fragmen teks berulang dalam granulasi byte. Metode kompresi ini telah dikenal sejak lama, tetapi belum pernah digunakan, karena operasi pencarian kecocokan sangat mahal dalam hal sumber daya yang diperlukan dan membutuhkan lebih banyak waktu daripada membangun kamus. Jadi algoritma RTT-Mid adalah contoh klasik dari gerakan "kembali ke masa depan" ...
Kompresor PTT menggunakan pemindai berkecepatan tinggi yang unik untuk menemukan kecocokan, dialah yang memungkinkan untuk mempercepat proses kompresi. Pemindai buatan sendiri, ini adalah "pesonaku ...", "harganya mahal, karena sepenuhnya buatan tangan" (ditulis secara assembler).
Pemindai pencarian pertandingan didasarkan pada skema probabilistik dua tingkat, keberadaan "tanda" pertandingan pertama kali dipindai, dan hanya setelah "tanda" terdeteksi di tempat ini, prosedur untuk mendeteksi pertandingan yang sebenarnya dimulai.
Jendela pencarian kecocokan memiliki ukuran yang tidak dapat diprediksi, tergantung pada tingkat entropi dalam blok data yang sedang diproses. Untuk data yang benar-benar acak (tidak dapat dimampatkan), ia memiliki ukuran megabita, untuk data yang memiliki pengulangan selalu memiliki ukuran lebih dari satu megabita.
Tetapi banyak format data modern tidak dapat dimampatkan dan "mendorong" pemindai intensif sumber daya pada mereka tidak berguna dan boros, oleh karena itu pemindai menggunakan dua mode operasi. Pertama, bagian teks sumber dengan kemungkinan pengulangan dicari, operasi ini juga dilakukan dengan metode probabilistik dan dilakukan dengan sangat cepat (pada kecepatan 4-6 Gigabytes / detik). Kemudian area dengan kemungkinan kecocokan diproses oleh pemindai utama.
Kompresi indeks tidak terlalu efisien, Anda harus mengganti fragmen berulang dengan indeks, dan array indeks secara signifikan mengurangi rasio kompresi.
Untuk meningkatkan rasio kompresi, tidak hanya kecocokan penuh string byte yang diindeks, tetapi juga sebagian ketika ada yang cocok dan tidak cocok dengan byte dalam string. Untuk melakukan ini, bidang topeng indeks termasuk dalam format indeks, yang menunjukkan byte kebetulan dua blok. Untuk kompresi yang lebih besar lagi, pengindeksan digunakan dengan tumpang tindih beberapa blok pencocokan sebagian pada blok saat ini.
Semua ini memungkinkan untuk mendapatkan rasio kompresi dalam kompresor PTT-Mid, sebanding dengan kompresor yang dibuat sesuai dengan metode kamus, tetapi bekerja lebih cepat.
Kecepatan algoritma kompresi baru
Jika kompresor bekerja dengan penggunaan cache memori yang eksklusif (diperlukan 4 megabita per aliran), maka kecepatan bervariasi dari 700-2000 megabita / detik. per inti prosesor, tergantung pada jenis data yang dikompresi dan sedikit tergantung pada frekuensi operasi prosesor.
Dengan implementasi multi-threaded kompresor, skalabilitas yang efektif ditentukan oleh volume memori cache tingkat ketiga. Misalnya, memiliki "on board" 9 Megabytes memori cache, tidak masuk akal untuk menjalankan lebih dari dua stream kompresi, kecepatan tidak akan bertambah dari ini. Tetapi dengan cache 20 megabita, Anda sudah dapat menjalankan lima aliran kompresi.
Selain itu, latensi RAM menjadi parameter penting yang menentukan kecepatan kompresor. Algoritma ini menggunakan akses acak ke OP, beberapa di antaranya tidak masuk ke memori cache (sekitar 10%) dan harus diam, menunggu data dari OP, yang mengurangi kecepatan kerja.
Secara signifikan mempengaruhi kecepatan kompresor dan pengoperasian sistem input / output data. Permintaan ke OP dari I / O memblokir permintaan data dari CPU, yang juga mengurangi tingkat kompresi. Masalah ini signifikan untuk laptop dan desktop, untuk server kurang signifikan karena unit kontrol akses yang lebih maju untuk bus sistem dan RAM multi-channel.
Di mana-mana dalam teks, artikel mengacu pada kompresi, dekompresi berada di luar cakupan artikel ini karena semuanya ada dalam cokelat. Dekompresi jauh lebih cepat dan dibatasi oleh kecepatan I / O. Satu inti fisik dalam satu utas dengan tenang memberikan kecepatan dekompresi pada tingkat 3-4 Gigabytes / detik.
Hal ini disebabkan tidak adanya operasi pencarian-cocok selama proses pembongkaran, yang “memakan” prosesor utama dan sumber daya cache selama kompresi.
Penyimpanan data terkompresi yang andal
Seperti yang disiratkan oleh nama seluruh kelas perangkat lunak menggunakan kompresi data (pengarsipan), mereka dirancang untuk penyimpanan informasi jangka panjang, bukan selama bertahun-tahun, tetapi selama berabad-abad dan ribuan ...
Selama penyimpanan, media penyimpanan kehilangan beberapa data, berikut adalah contohnya:
Media penyimpanan "analog" ini berusia seribu tahun, beberapa fragmen telah hilang, tetapi secara umum informasinya "dapat dibaca" ...
Tidak ada produsen yang bertanggung jawab atas sistem penyimpanan digital modern dan media digital untuk mereka yang memberikan jaminan keamanan data lengkap selama lebih dari 75 tahun.
Dan ini adalah masalah, tetapi masalahnya ditunda, keturunan kita akan menyelesaikannya ...
Sistem penyimpanan data digital dapat kehilangan data tidak hanya setelah 75 tahun, kesalahan data dapat muncul kapan saja, bahkan selama perekaman, mereka mencoba meminimalkan distorsi ini dengan menggunakan redundansi dan memperbaiki sistem koreksi kesalahan. Sistem redundansi dan koreksi tidak selalu dapat mengembalikan informasi yang hilang, dan jika dipulihkan, tidak ada jaminan bahwa operasi pemulihan itu benar.
Dan ini juga masalah besar, tapi bukan yang tertunda, tapi yang sekarang.
Kompresor modern yang digunakan untuk pengarsipan data digital dibangun di atas berbagai modifikasi dari metode kamus, dan untuk arsip seperti itu hilangnya informasi akan menjadi peristiwa yang fatal, bahkan ada istilah yang ditetapkan untuk situasi seperti itu - arsip "rusak" ...
Rendahnya keandalan penyimpanan informasi dalam arsip dengan kompresi kamus dikaitkan dengan struktur data terkompresi. Informasi dalam arsip semacam itu tidak mengandung teks sumber, jumlah entri dalam kamus disimpan di sana, kamus itu sendiri secara dinamis diubah oleh teks yang dapat dikompresi saat ini. Jika sebuah fragmen arsip hilang atau terdistorsi, semua entri arsip selanjutnya tidak dapat diidentifikasi baik oleh konten atau oleh panjangnya entri dalam kamus, karena tidak jelas apa yang terkait dengan jumlah entri kamus.
Tidak mungkin memulihkan informasi dari arsip yang "rusak".
Algoritma RTT didasarkan pada metode yang lebih dapat diandalkan untuk menyimpan data terkompresi. Ini menggunakan metode indeks akuntansi untuk mengulangi fragmen. Pendekatan kompresi seperti itu memungkinkan meminimalkan konsekuensi dari distorsi informasi pada media, dan dalam banyak kasus, secara otomatis memperbaiki distorsi yang timbul selama penyimpanan informasi.
Ini disebabkan oleh fakta bahwa file arsip dalam kasus kompresi indeks berisi dua bidang:
- bidang teks sumber dengan bagian berulang dihapus dari itu;
- bidang indeks.
Bidang indeks yang kritis untuk pemulihan data tidak berukuran besar dan dapat diduplikasi untuk penyimpanan data yang andal. Oleh karena itu, bahkan jika sebuah fragmen teks sumber atau array indeks hilang, maka semua informasi lainnya akan dipulihkan tanpa masalah, seperti pada gambar dengan pembawa informasi "analog".
Kekurangan algoritma
Keuntungan tidak ada tanpa kerugian. Metode kompresi indeks tidak memampatkan urutan pendek berulang. Ini karena keterbatasan metode indeks. Indeks setidaknya berukuran 3 byte dan dapat berukuran hingga 12 byte. Jika pengulangan terjadi dengan ukuran lebih kecil dari indeks yang menggambarkannya, maka itu tidak diperhitungkan, namun seringkali pengulangan seperti itu terdeteksi dalam file kompresibel.
Metode kompresi kosa kata tradisional secara efektif memampatkan beberapa pengulangan pendek dan karenanya mencapai rasio kompresi yang lebih tinggi daripada kompresi indeks. Benar, ini dicapai karena tingginya beban kerja prosesor sentral, sehingga metode kosakata mulai mengompres data lebih efisien daripada metode indeks, itu harus mengurangi kecepatan pemrosesan data hingga 10-20 megabyte per detik pada instalasi komputasi nyata dengan pemanfaatan CPU penuh.
Kecepatan rendah seperti itu tidak dapat diterima untuk sistem penyimpanan data modern dan lebih menarik "akademik" daripada praktis.
Tingkat kompresi informasi akan meningkat secara signifikan dalam modifikasi berikutnya dari algoritma PTT (RTT-Max), itu sudah dalam pengembangan.
Jadi, seperti biasa, untuk dilanjutkan ...