SIEVE: Επαναστατικός αλγόριθμος «εκτοξεύει» την ταχύτητα περιήγησης στο διαδίκτυο – Πώς λειτουργεί

Ίντερνετ Διαδίκτυο

Ένας νέος αλγόριθμος θα μπορούσε να επιταχύνει σημαντικά την περιήγηση στον ιστό, καθιστώντας την προσωρινή αποθήκευση δεδομένων πιο αποτελεσματική.

Το πρόγραμμα ανοικτού κώδικα, που ονομάζεται “SIEVE”, εισάγει έναν νέο τρόπο χειρισμού της προσωρινής αποθήκευσης στο διαδίκτυο – τη διαδικασία αποθήκευσης και ανάκτησης αντικειμένων από τη μακροπρόθεσμη αποθήκευση ενός υπολογιστή καθώς τα συναντάτε κατά την πλοήγηση στο διαδίκτυο.

Αυτά τα αντικείμενα – μικροσκοπικά αρχεία που αποθηκεύονται στον σκληρό σας δίσκο – περιλαμβάνουν εικόνες, λογότυπα ή ολόκληρα αντίγραφα ιστοσελίδων. Όταν συναντάτε αυτά τα στοιχεία για πρώτη φορά, τα ανακτάτε από τον διακομιστή, αλλά αποθηκεύονται στον σκληρό σας δίσκο για επαναχρησιμοποίηση. Τη δεύτερη φορά που θα συναντήσετε αυτά τα αντικείμενα, το πρόγραμμα περιήγησής σας μπορεί να τα ανακτήσει από τη μνήμη του υπολογιστή σας και όχι από τον διακομιστή, γεγονός που εξοικονομεί χρόνο και καταναλώνει λιγότερη ενέργεια.

Επειδή όμως ο τοπικός αποθηκευτικός χώρος είναι περιορισμένος, οι αλγόριθμοι απομάκρυνσης από την κρυφή μνήμη δουλεύουν για να αποφασίσουν για πόσο καιρό θα αποθηκεύσουν τα αντικείμενα και πότε θα αντικαταστήσουν τα παλαιότερα αντικείμενα, στα οποία ο χρήστης έχει λιγότερο συχνή πρόσβαση, με νεότερα ή πιο δημοφιλή.

Αν και υπάρχουν πολλοί τέτοιοι αλγόριθμοι, ο SIEVE είναι μια πολύ πιο απλή και αποτελεσματική επιλογή που μπορεί να επιταχύνει δραματικά την περιήγηση στον ιστό, αν εφαρμοστεί σε όλο το διαδίκτυο, ανέφεραν οι επιστήμονες σε εργασία τους, που δημοσιεύθηκε στις 17 Δεκεμβρίου 2023. Σκοπεύουν να την παρουσιάσουν στο 21ο Συμπόσιο USENIX για τη σχεδίαση και υλοποίηση δικτυακών συστημάτων τον Απρίλιο.

«Ένας βασικός λόγος για τον οποίο οι υπολογιστές και το διαδίκτυο είναι γρήγοροι είναι η κρυφή μνήμη. Πιστεύουμε ότι οι κρυφές μνήμες λογισμικού είναι αυτός ο πανταχού παρών και συνάμα υποτιμημένος πυλώνας που επιτρέπει τη λειτουργία του σύγχρονου διαδικτύου και έτσι η εργασία πάνω σε αυτές μπορεί να έχει τεράστιο αντίκτυπο», δήλωσε στο Live Science ένας από τους κύριους συγγραφείς της εργασίας, ο Yazhuo Zhang, που είναι διδακτορικός φοιτητής στο Πανεπιστήμιο Emory στην Ατλάντα.

O SIEVE και η νέα προσέγγιση για την προσωρινή αποθήκευση στο διαδίκτυο

Οι αλγόριθμοι First-in, first-out (FIFO) λειτουργούν προσθέτοντας νέα αντικείμενα με τη σειρά σε έναν “ιμάντα μεταφοράς” προς τη λήθη. Όταν τα αντικείμενα φτάσουν στο τέλος της γραμμής, αφαιρούνται. Το «LRU (Less recently used)» είναι μια άλλη μέθοδος κατά την οποία τα αντικείμενα κινούνται κατά μήκος του ιμάντα μεταφοράς -όπως και στον FIFO-, αλλά αν ένα αντικείμενο ζητηθεί ξανά, μεταπηδά πίσω στο μπροστινό μέρος.

«Υπάρχουν πιο περίπλοκες παραλλαγές, αλλά όσο πιο πολύπλοκες είναι, τόσο περισσότερα σφάλματα έχουν» δήλωσε ο Zhang και πρόσθεσε: «Το SIEVE, αντίθετα, υλοποιήθηκε με λιγότερες από 20 γραμμές κώδικα».

Πώς λειτουργεί o SIEVE

Το SIEVE χρησιμοποιεί τον ίδιο μηχανισμό «ιμάντα μεταφοράς», αλλά τα αντικείμενα έχουν αρχικά την ένδειξη «μηδέν». Όταν ένα αντικείμενο ζητηθεί ξανά, η κατάστασή του αλλάζει σε «ένα» και εντάσσεται στο μπροστινό μέρος της γραμμής. Τα αντικείμενα εκδιώκονται κανονικά όταν φτάσουν στο τέλος. Αυτό είναι γνωστό ως «τεμπέλικη προώθηση».

Εν τω μεταξύ, ένα «κινούμενο χέρι» που σαρώνει το μήκος του ιμάντα και γυρίζει πίσω στην αρχή, είναι προγραμματισμένο να απομακρύνει κάθε αντικείμενο με ετικέτα «μηδέν». Αυτή η λειτουργία που μοιάζει με κόσκινο ονομάζεται «γρήγορος υποβιβασμός». Οι επιστήμονες δήλωσαν ότι ο SIEVE είναι ο απλούστερος αλγόριθμος που επιτυγχάνει τόσο την τεμπέλικη προώθηση όσο και το γρήγορο υποβιβασμό.

SIEVE

Διεξήγαγαν 1.500 ξεχωριστές δοκιμές έναντι εννέα σύγχρονων αλγορίθμων χρησιμοποιώντας πραγματικά ιστορικά προσωρινής αποθήκευσης που βασίζονται σε εντοπισμένα ίχνη προσωρινής αποθήκευσης ιστού από τις Meta, Wikimedia, X και τέσσερις άλλες πηγές. Ένα ίχνος, για παράδειγμα, αποτελούνταν από 2,8 δισεκατομμύρια αιτήσεις ιστού που έγιναν για πρόσβαση σε μέσα ενημέρωσης στη Wikipedia το 2019. Συνολικά, τα 1.500 ίχνη περιλάμβαναν 247 δισεκατομμύρια αιτήσεις σε σχεδόν 15 δισεκατομμύρια αντικείμενα.

Έψαχναν για ένα χαμηλό «ποσοστό αστοχίας» ή το κλάσμα των αντικειμένων που ανακτήθηκαν από τον ιστό σε σχέση με την αποθήκευση, όπου ως “αστοχία” θεωρείται η ανάκτηση ενός αντικειμένου από τον ιστό – όσο μικρότερο, τόσο το καλύτερο.

«Κανένας αλγόριθμος δεν αναμένεται να έχει τη χαμηλότερη αναλογία αστοχίας σε κάθε δοκιμή, αλλά ο SIEVE είχε τις καλύτερες επιδόσεις στο 45% των δοκιμών. Ο αμέσως επόμενος καλύτερος αλγόριθμος, αντίθετα, είχε την καλύτερη επίδοση μόλις στο 15%» δήλωσε ο Zhang στο Live Science.

Ο SIEVE έχει ήδη εφαρμοστεί σε περισσότερες από 10 δημοφιλείς βιβλιοθήκες που τροφοδοτούν σύγχρονες εφαρμογές και ιστότοπους. Πολλοί ιστότοποι ενδέχεται σύντομα να αναβαθμιστούν στο SIEVE «χωρίς μεγάλη προσπάθεια», δήλωσε ο Zhang. Πρόσθεσε ότι η Meta πρόκειται να αξιολογήσει το SIEVE στην παραγωγή, ενώ η Google έχει επίσης εκδηλώσει ενδιαφέρον για την υιοθέτηση του SIEVE μαζί με άλλες εταιρείες του διαδικτύου.

«Πρόκειται για αξιοσημείωτη και ασυνήθιστη έλξη», δήλωσε ο Zhang. «Κανένας αλγόριθμος κρυφής μνήμης τα τελευταία 20 χρόνια δεν έχει δει ευρεία αποδοχή σε πολλαπλά συστήματα παραγωγής».

Scroll to Top