Αυτό το άρθρο είναι ήδη το δεύτερο στο θέμα της συμπίεσης δεδομένων υψηλής ταχύτητας. Το πρώτο άρθρο περιγράφει έναν συμπιεστή που λειτουργεί με ταχύτητα 10 GB/sec. ανά πυρήνα επεξεργαστή (ελάχιστη συμπίεση, RTT-Min).
Αυτός ο συμπιεστής έχει ήδη εφαρμοστεί στον εξοπλισμό εγκληματολογικών αντιγραφέων για συμπίεση υψηλής ταχύτητας χωματερών μέσων αποθήκευσης και ενίσχυση της ισχύος της κρυπτογραφίας· μπορεί επίσης να χρησιμοποιηθεί για τη συμπίεση εικόνων εικονικών μηχανών και αρχείων ανταλλαγής RAM κατά την αποθήκευση τους σε υψηλή ταχύτητα Μονάδες SSD.
Το πρώτο άρθρο ανήγγειλε επίσης την ανάπτυξη ενός αλγορίθμου συμπίεσης για τη συμπίεση αντιγράφων αντιγράφων ασφαλείας των μονάδων δίσκου HDD και SSD (μέση συμπίεση, RTT-Mid) με σημαντικά βελτιωμένες παραμέτρους συμπίεσης δεδομένων. Μέχρι τώρα, αυτός ο συμπιεστής είναι εντελώς έτοιμος και αυτό το άρθρο είναι σχετικά.
Ένας συμπιεστής που υλοποιεί τον αλγόριθμο RTT-Mid παρέχει αναλογία συμπίεσης συγκρίσιμο με τυπικούς αρχειοθέτες όπως WinRar, 7-Zip, που λειτουργούν σε λειτουργία υψηλής ταχύτητας. Ταυτόχρονα, η ταχύτητα λειτουργίας του είναι τουλάχιστον μια τάξη μεγέθους υψηλότερη.
Η ταχύτητα συσκευασίας/αποσυσκευασίας δεδομένων είναι μια κρίσιμη παράμετρος που καθορίζει το πεδίο εφαρμογής των τεχνολογιών συμπίεσης. Είναι απίθανο κάποιος να σκεφτεί να συμπιέσει ένα terabyte δεδομένων με ταχύτητα 10-15 MegaByte ανά δευτερόλεπτο (αυτή είναι ακριβώς η ταχύτητα των αρχειοθέτητων σε τυπική λειτουργία συμπίεσης), επειδή θα χρειαζόταν σχεδόν είκοσι ώρες με πλήρες φορτίο επεξεργαστή. .
Από την άλλη, το ίδιο terabyte μπορεί να αντιγραφεί με ταχύτητες της τάξης των 2-3 Gigabyte ανά δευτερόλεπτο σε περίπου δέκα λεπτά.
Επομένως, η συμπίεση πληροφοριών μεγάλου όγκου είναι σημαντική εάν εκτελείται με ταχύτητα όχι χαμηλότερη από την ταχύτητα της πραγματικής εισόδου/εξόδου. Για τα σύγχρονα συστήματα αυτό είναι τουλάχιστον 100 Megabyte ανά δευτερόλεπτο.
Οι σύγχρονοι συμπιεστές μπορούν να παράγουν τέτοιες ταχύτητες μόνο σε «γρήγορη» λειτουργία. Σε αυτήν την τρέχουσα λειτουργία θα συγκρίνουμε τον αλγόριθμο RTT-Mid με τους παραδοσιακούς συμπιεστές.
Συγκριτική δοκιμή νέου αλγόριθμου συμπίεσης
Ο συμπιεστής RTT-Mid λειτούργησε ως μέρος του προγράμματος δοκιμής. Σε μια πραγματική "εργαζόμενη" εφαρμογή λειτουργεί πολύ πιο γρήγορα, χρησιμοποιεί σοφά το multithreading και χρησιμοποιεί έναν "κανονικό" μεταγλωττιστή, όχι C#.
Δεδομένου ότι οι συμπιεστές που χρησιμοποιούνται στη συγκριτική δοκιμή είναι κατασκευασμένοι σε διαφορετικές αρχές και διαφορετικοί τύποι δεδομένων συμπιέζονται διαφορετικά, για την αντικειμενικότητα της δοκιμής χρησιμοποιήθηκε η μέθοδος μέτρησης της «μέσης θερμοκρασίας στο νοσοκομείο»...
Δημιουργήθηκε ένα ενδεικτικό αρχείο ανά τομέα ενός λογικού δίσκου με το λειτουργικό σύστημα Windows 10· αυτό είναι το πιο φυσικό μείγμα από διάφορες δομές δεδομένων που είναι πραγματικά διαθέσιμες σε κάθε υπολογιστή. Η συμπίεση αυτού του αρχείου θα σας επιτρέψει να συγκρίνετε την ταχύτητα και τον βαθμό συμπίεσης του νέου αλγόριθμου με τους πιο προηγμένους συμπιεστές που χρησιμοποιούνται στα σύγχρονα αρχεία αρχειοθέτησης.
Εδώ είναι το αρχείο dump:
Το αρχείο ένδειξης σφαλμάτων συμπιέστηκε χρησιμοποιώντας συμπιεστές PTT-Mid, 7-zip και WinRar. Το WinRar και ο συμπιεστής 7-zip ρυθμίστηκαν στη μέγιστη ταχύτητα.
Συμπιεστής σε λειτουργία 7-zip:
Φορτώνει τον επεξεργαστή κατά 100%, ενώ η μέση ταχύτητα ανάγνωσης του αρχικού dump είναι περίπου 60 MegaBytes/sec.
Συμπιεστής σε λειτουργία WinRAR:
Η κατάσταση είναι παρόμοια, το φορτίο του επεξεργαστή είναι σχεδόν 100%, η μέση ταχύτητα ανάγνωσης dump είναι περίπου 125 Megabyte/sec.
Όπως και στην προηγούμενη περίπτωση, η ταχύτητα του αρχειοθέτη περιορίζεται από τις δυνατότητες του επεξεργαστή.
Το πρόγραμμα δοκιμής συμπιεστή εκτελείται τώρα RTT-Mid:
Το στιγμιότυπο οθόνης δείχνει ότι ο επεξεργαστής είναι φορτωμένος στο 50% και είναι αδρανής τον υπόλοιπο χρόνο, επειδή δεν υπάρχει πουθενά να ανεβάσετε τα συμπιεσμένα δεδομένα. Ο δίσκος μεταφόρτωσης δεδομένων (Δίσκος 0) είναι σχεδόν πλήρως φορτωμένος. Η ταχύτητα ανάγνωσης δεδομένων (Δίσκος 1) ποικίλλει πολύ, αλλά κατά μέσο όρο πάνω από 200 MegaByte/sec.
Η ταχύτητα του συμπιεστή περιορίζεται σε αυτήν την περίπτωση από τη δυνατότητα εγγραφής συμπιεσμένων δεδομένων στο δίσκο 0.
Τώρα ο λόγος συμπίεσης των αρχείων που προκύπτουν:
Μπορεί να φανεί ότι ο συμπιεστής RTT-Mid έκανε την καλύτερη δουλειά συμπίεσης· το αρχείο που δημιούργησε ήταν 1,3 GigaByte μικρότερο από το αρχείο WinRar και 2,1 GigaByte μικρότερο από το αρχείο 7z.
Χρόνος που αφιερώθηκε για τη δημιουργία του αρχείου:
- 7-zip – 26 λεπτά 10 δευτερόλεπτα.
- WinRar – 17 λεπτά 40 δευτερόλεπτα.
- RTT-Mid – 7 λεπτά 30 δευτερόλεπτα.
Έτσι, ακόμη και ένα δοκιμαστικό, μη βελτιστοποιημένο πρόγραμμα, χρησιμοποιώντας τον αλγόριθμο RTT-Mid, κατάφερε να δημιουργήσει ένα αρχείο πάνω από δυόμισι φορές πιο γρήγορα, ενώ το αρχείο αποδείχθηκε σημαντικά μικρότερο από αυτό των ανταγωνιστών του...
Όσοι δεν πιστεύουν τα στιγμιότυπα οθόνης μπορούν να ελέγξουν οι ίδιοι την αυθεντικότητά τους. Το πρόγραμμα δοκιμής είναι διαθέσιμο στη διεύθυνση , κατεβάστε και ελέγξτε.
Αλλά μόνο σε επεξεργαστές με υποστήριξη AVX-2, χωρίς υποστήριξη για αυτές τις οδηγίες ο συμπιεστής δεν λειτουργεί και μην δοκιμάζετε τον αλγόριθμο σε παλαιότερους επεξεργαστές AMD, είναι αργοί όσον αφορά την εκτέλεση εντολών AVX...
Χρησιμοποιείται μέθοδος συμπίεσης
Ο αλγόριθμος χρησιμοποιεί μια μέθοδο για την ευρετηρίαση επαναλαμβανόμενων τμημάτων κειμένου σε ευρετηρίαση byte. Αυτή η μέθοδος συμπίεσης ήταν γνωστή εδώ και πολύ καιρό, αλλά δεν χρησιμοποιήθηκε επειδή η λειτουργία αντιστοίχισης ήταν πολύ δαπανηρή όσον αφορά τους απαραίτητους πόρους και απαιτούσε πολύ περισσότερο χρόνο από την κατασκευή ενός λεξικού. Έτσι, ο αλγόριθμος RTT-Mid είναι ένα κλασικό παράδειγμα μετακίνησης «επιστροφής στο μέλλον»...
Ο συμπιεστής PTT χρησιμοποιεί έναν μοναδικό σαρωτή αναζήτησης αντιστοίχισης υψηλής ταχύτητας, ο οποίος μας επιτρέπει να επιταχύνουμε τη διαδικασία συμπίεσης. Ένας αυτοδημιούργητος σαρωτής, αυτό είναι "το γούρι μου...", "είναι αρκετά ακριβό, γιατί είναι εντελώς χειροποίητο" (γραμμένο στο assembler).
Ο σαρωτής αναζήτησης αντιστοιχίας κατασκευάζεται σύμφωνα με ένα πιθανό σχήμα δύο επιπέδων: πρώτα, σαρώνεται η παρουσία ενός "σημαδιού" ενός αγώνα και μόνο αφού εντοπιστεί το "σημάδι" σε αυτό το μέρος, η διαδικασία ανίχνευσης μιας πραγματικής αντιστοίχισης έχει ξεκινήσει.
Το παράθυρο αναζήτησης αντιστοίχισης έχει απρόβλεπτο μέγεθος, ανάλογα με τον βαθμό εντροπίας στο μπλοκ δεδομένων που έχει υποστεί επεξεργασία. Για εντελώς τυχαία (ασυμπίεστα) δεδομένα έχει μέγεθος megabyte, για δεδομένα με επαναλήψεις είναι πάντα μεγαλύτερο από ένα megabyte.
Ωστόσο, πολλές σύγχρονες μορφές δεδομένων είναι ασυμπίεστες και η εκτέλεση ενός σαρωτή με ένταση πόρων μέσω αυτών είναι άχρηστη και σπάταλη, επομένως ο σαρωτής χρησιμοποιεί δύο τρόπους λειτουργίας. Αρχικά, αναζητούνται τμήματα του κειμένου πηγής με πιθανές επαναλήψεις· αυτή η λειτουργία εκτελείται επίσης χρησιμοποιώντας μια πιθανολογική μέθοδο και εκτελείται πολύ γρήγορα (με ταχύτητα 4-6 GigaBytes/sec). Στη συνέχεια, οι περιοχές με πιθανές αντιστοιχίσεις επεξεργάζονται από τον κύριο σαρωτή.
Η συμπίεση ευρετηρίου δεν είναι πολύ αποτελεσματική, πρέπει να αντικαταστήσετε διπλά θραύσματα με δείκτες και η συστοιχία ευρετηρίου μειώνει σημαντικά την αναλογία συμπίεσης.
Για να αυξηθεί ο λόγος συμπίεσης, δεν ευρετηριάζονται μόνο πλήρεις αντιστοιχίσεις συμβολοσειρών byte, αλλά και μερικές, όταν η συμβολοσειρά περιέχει αντιστοιχισμένα και μη αντιστοιχισμένα byte. Για να γίνει αυτό, η μορφή ευρετηρίου περιλαμβάνει ένα πεδίο μάσκας αντιστοίχισης που υποδεικνύει τα byte που ταιριάζουν δύο μπλοκ. Για ακόμη μεγαλύτερη συμπίεση, η ευρετηρίαση χρησιμοποιείται για την υπέρθεση πολλών μερικώς ταιριασμένων μπλοκ στο τρέχον μπλοκ.
Όλα αυτά κατέστησαν δυνατή την απόκτηση στον συμπιεστή PTT-Mid μιας αναλογίας συμπίεσης συγκρίσιμη με τους συμπιεστές που κατασκευάζονται με τη μέθοδο του λεξικού, αλλά λειτουργεί πολύ πιο γρήγορα.
Ταχύτητα του νέου αλγόριθμου συμπίεσης
Εάν ο συμπιεστής λειτουργεί με αποκλειστική χρήση κρυφής μνήμης (απαιτούνται 4 Megabyte ανά νήμα), τότε η ταχύτητα λειτουργίας κυμαίνεται από 700-2000 Megabyte/sec. ανά πυρήνα επεξεργαστή, ανάλογα με τον τύπο των δεδομένων που συμπιέζονται και εξαρτάται ελάχιστα από τη συχνότητα λειτουργίας του επεξεργαστή.
Με μια εφαρμογή πολλαπλών νημάτων του συμπιεστή, η αποτελεσματική επεκτασιμότητα καθορίζεται από το μέγεθος της κρυφής μνήμης τρίτου επιπέδου. Για παράδειγμα, έχοντας 9 MegaByte μνήμης cache "στο σκάφος", δεν έχει νόημα να εκκινήσετε περισσότερα από δύο νήματα συμπίεσης· η ταχύτητα δεν θα αυξηθεί από αυτό. Αλλά με μια κρυφή μνήμη 20 Megabyte, μπορείτε ήδη να εκτελέσετε πέντε νήματα συμπίεσης.
Επίσης, η καθυστέρηση της μνήμης RAM γίνεται μια σημαντική παράμετρος που καθορίζει την ταχύτητα του συμπιεστή. Ο αλγόριθμος χρησιμοποιεί τυχαία πρόσβαση στο OP, μερικά από τα οποία δεν μπαίνουν στη μνήμη cache (περίπου 10%) και πρέπει να αδράνει, περιμένοντας δεδομένα από το OP, γεγονός που μειώνει την ταχύτητα λειτουργίας.
Επηρεάζει σημαντικά την ταχύτητα του συμπιεστή και τη λειτουργία του συστήματος εισαγωγής/εξόδου δεδομένων. Αιτήσεις προς το OP από I/O μπλοκ αιτήματα για δεδομένα από την CPU, γεγονός που μειώνει επίσης την ταχύτητα συμπίεσης. Αυτό το πρόβλημα είναι σημαντικό για φορητούς υπολογιστές και επιτραπέζιους υπολογιστές, ενώ για διακομιστές είναι λιγότερο σημαντικό λόγω μιας πιο προηγμένης μονάδας ελέγχου πρόσβασης διαύλου συστήματος και μνήμης RAM πολλαπλών καναλιών.
Σε όλο το κείμενο του άρθρου μιλάμε για συμπίεση· η αποσυμπίεση παραμένει εκτός του σκοπού αυτού του άρθρου αφού «όλα καλύπτονται με σοκολάτα». Η αποσυμπίεση είναι πολύ πιο γρήγορη και περιορίζεται από την ταχύτητα I/O. Ένας φυσικός πυρήνας σε ένα νήμα παρέχει εύκολα ταχύτητες αποσυσκευασίας 3-4 GB/sec.
Αυτό οφείλεται στην απουσία λειτουργίας αναζήτησης αντιστοίχισης κατά τη διάρκεια της διαδικασίας αποσυμπίεσης, η οποία «τρώει» τους κύριους πόρους του επεξεργαστή και τη μνήμη cache κατά τη συμπίεση.
Αξιοπιστία αποθήκευσης συμπιεσμένων δεδομένων
Όπως υποδηλώνει το όνομα ολόκληρης της κατηγορίας λογισμικού που χρησιμοποιεί συμπίεση δεδομένων (αρχειοθέτες), έχουν σχεδιαστεί για μακροπρόθεσμη αποθήκευση πληροφοριών, όχι για χρόνια, αλλά για αιώνες και χιλιετίες...
Κατά τη διάρκεια της αποθήκευσης, τα μέσα αποθήκευσης χάνουν ορισμένα δεδομένα, εδώ είναι ένα παράδειγμα:
Αυτός ο «αναλογικός» φορέας πληροφοριών είναι χιλίων ετών, κάποια κομμάτια έχουν χαθεί, αλλά γενικά οι πληροφορίες είναι «αναγνώσιμες»...
Κανένας από τους υπεύθυνους κατασκευαστές σύγχρονων συστημάτων αποθήκευσης ψηφιακών δεδομένων και ψηφιακών μέσων για αυτά δεν παρέχει εγγυήσεις πλήρους ασφάλειας δεδομένων για περισσότερα από 75 χρόνια.
Και αυτό είναι πρόβλημα, αλλά πρόβλημα αναβληθέν, θα το λύσουν οι απόγονοί μας...
Τα συστήματα αποθήκευσης ψηφιακών δεδομένων μπορούν να χάσουν δεδομένα όχι μόνο μετά από 75 χρόνια, σφάλματα στα δεδομένα μπορούν να εμφανιστούν ανά πάσα στιγμή, ακόμη και κατά την καταγραφή τους, προσπαθούν να ελαχιστοποιήσουν αυτές τις παραμορφώσεις χρησιμοποιώντας πλεονασμό και διορθώνοντάς τα με συστήματα διόρθωσης σφαλμάτων. Τα συστήματα πλεονασμού και διόρθωσης δεν μπορούν πάντα να αποκαταστήσουν τις χαμένες πληροφορίες και, αν το κάνουν, δεν υπάρχει εγγύηση ότι η λειτουργία αποκατάστασης ολοκληρώθηκε σωστά.
Και αυτό είναι επίσης ένα μεγάλο πρόβλημα, αλλά όχι αναβαλλόμενο, αλλά τρέχον.
Οι σύγχρονοι συμπιεστές που χρησιμοποιούνται για την αρχειοθέτηση ψηφιακών δεδομένων βασίζονται σε διάφορες τροποποιήσεις της μεθόδου του λεξικού και για τέτοια αρχεία η απώλεια μιας πληροφορίας θα είναι ένα θανατηφόρο γεγονός· υπάρχει ακόμη και ένας καθιερωμένος όρος για μια τέτοια κατάσταση - ένα "σπασμένο" αρχείο ...
Η χαμηλή αξιοπιστία της αποθήκευσης πληροφοριών σε αρχεία με συμπίεση λεξικού σχετίζεται με τη δομή των συμπιεσμένων δεδομένων. Οι πληροφορίες σε ένα τέτοιο αρχείο δεν περιέχουν το κείμενο προέλευσης, οι αριθμοί των καταχωρήσεων στο λεξικό αποθηκεύονται εκεί και το ίδιο το λεξικό τροποποιείται δυναμικά από το τρέχον συμπιεσμένο κείμενο. Εάν ένα τμήμα αρχείου χαθεί ή καταστραφεί, όλες οι επόμενες εγγραφές αρχείου δεν μπορούν να αναγνωριστούν ούτε από το περιεχόμενο ούτε από το μήκος της καταχώρισης στο λεξικό, καθώς δεν είναι σαφές σε τι αντιστοιχεί ο αριθμός καταχώρισης του λεξικού.
Είναι αδύνατο να επαναφέρετε πληροφορίες από ένα τέτοιο "σπασμένο" αρχείο.
Ο αλγόριθμος RTT βασίζεται σε μια πιο αξιόπιστη μέθοδο αποθήκευσης συμπιεσμένων δεδομένων. Χρησιμοποιεί τη μέθοδο ευρετηρίου λογιστικής για την επανάληψη των τμημάτων. Αυτή η προσέγγιση στη συμπίεση σάς επιτρέπει να ελαχιστοποιήσετε τις συνέπειες της παραμόρφωσης των πληροφοριών στο μέσο αποθήκευσης και σε πολλές περιπτώσεις να διορθώσετε αυτόματα τις παραμορφώσεις που προέκυψαν κατά την αποθήκευση πληροφοριών.
Αυτό οφείλεται στο γεγονός ότι το αρχείο αρχειοθέτησης στην περίπτωση συμπίεσης ευρετηρίου περιέχει δύο πεδία:
- ένα πεδίο κειμένου πηγής με τμήματα επανάληψης που έχουν αφαιρεθεί από αυτό.
- πεδίο ευρετηρίου.
Το πεδίο ευρετηρίου, το οποίο είναι κρίσιμο για την ανάκτηση πληροφοριών, δεν είναι μεγάλο σε μέγεθος και μπορεί να αντιγραφεί για αξιόπιστη αποθήκευση δεδομένων. Επομένως, ακόμα κι αν χαθεί ένα τμήμα του κειμένου προέλευσης ή του πίνακα ευρετηρίου, όλες οι άλλες πληροφορίες θα αποκατασταθούν χωρίς προβλήματα, όπως στην εικόνα με ένα "αναλογικό" μέσο αποθήκευσης.
Μειονεκτήματα του αλγορίθμου
Δεν υπάρχουν πλεονεκτήματα χωρίς μειονεκτήματα. Η μέθοδος συμπίεσης δείκτη δεν συμπιέζει σύντομες επαναλαμβανόμενες ακολουθίες. Αυτό οφείλεται στους περιορισμούς της μεθόδου του δείκτη. Τα ευρετήρια έχουν μέγεθος τουλάχιστον 3 byte και μπορούν να είναι έως 12 byte. Εάν μια επανάληψη συναντηθεί με μέγεθος μικρότερο από το ευρετήριο που την περιγράφει, τότε δεν λαμβάνεται υπόψη, όσο συχνά κι αν ανιχνεύονται τέτοιες επαναλήψεις στο συμπιεσμένο αρχείο.
Η παραδοσιακή μέθοδος συμπίεσης λεξικού συμπιέζει αποτελεσματικά πολλαπλές επαναλήψεις μικρού μήκους και επομένως επιτυγχάνει υψηλότερο λόγο συμπίεσης από τη συμπίεση δείκτη. Είναι αλήθεια ότι αυτό επιτυγχάνεται λόγω του υψηλού φορτίου στον κεντρικό επεξεργαστή· για να αρχίσει η μέθοδος λεξικού να συμπιέζει δεδομένα πιο αποτελεσματικά από τη μέθοδο ευρετηρίου, πρέπει να μειώσει την ταχύτητα επεξεργασίας δεδομένων στα 10-20 megabyte ανά δευτερόλεπτο σε πραγματικό υπολογιστικές εγκαταστάσεις με πλήρες φορτίο CPU.
Τέτοιες χαμηλές ταχύτητες είναι απαράδεκτες για τα σύγχρονα συστήματα αποθήκευσης δεδομένων και παρουσιάζουν περισσότερο «ακαδημαϊκό» ενδιαφέρον παρά πρακτικό.
Ο βαθμός συμπίεσης της πληροφορίας θα αυξηθεί σημαντικά στην επόμενη τροποποίηση του αλγορίθμου RTT (RTT-Max), που βρίσκεται ήδη σε εξέλιξη.
Όπως πάντα, συνέχεια...
Πηγή: www.habr.com