Original Post

Πλήρες Κείμενο:

Πώς καταφέρνει το Gmail να σε ενημερώνει ακαριαία ότι το όνομα χρήστη που επέλεξες είναι ήδη κατειλημμένο, ανάμεσα σε δισεκατομμύρια λογαριασμούς; Οι περισσότεροι πιστεύουν ότι το σύστημα εκτελεί απλώς μια γρήγορη αναζήτηση σε κάποια κλασική βάση δεδομένων.

Η πραγματικότητα, όμως, είναι πολύ πιο ενδιαφέρουσα. Η Google χρησιμοποιεί μια δομή δεδομένων που ονομάζεται Φίλτρο Μπλουμ (Bloom Filter). Πώς λειτουργεί ο μηχανισμός Φανταστείτε έναν τεράστιο πίνακα από bits (δισεκατομμύρια 0 και 1) που βρίσκεται εξολοκλήρου αποθηκευμένος στη μνήμη RAM για μέγιστη ταχύτητα.

Όταν ένας χρήστης κατοχυρώνει, για παράδειγμα, το john@gmail.com, το σύστημα περνάει αυτό το string από μερικές συναρτήσεις κατακερματισμού (hash functions). Κάθε συνάρτηση επιστρέφει μια συγκεκριμένη θέση στον πίνακα, και το bit της θέσης αυτής γίνεται 1. Όταν πληκτρολογείς εσύ ένα υποψήφιο username, επαναλαμβάνεται ακριβώς η ίδια διαδικασία.

Οι συναρτήσεις υπολογίζουν τις αντίστοιχες θέσεις στον πίνακα των bits: Αν έστω και μία από αυτές τις θέσεις έχει την τιμή 0, το όνομα χρήστη είναι σίγουρα ελεύθερο.

Αν όλες οι θέσεις έχουν την τιμή 1, το όνομα είναι πιθανότατα κατειλημμένο (υπάρχει μια ελάχιστη πιθανότητα σφάλματος, γι' αυτό και ακολουθεί ένας τελικός έλεγχος επιβεβαίωσης). Χωρίς χρονοβόρες σαρώσεις.

Χωρίς αναζητήσεις σε δίσκους.

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

Το εντυπωσιακό είναι ότι ολόκληρο αυτό το σύστημα για ένα δισεκατομμύριο χρήστες καταλαμβάνει μόλις 1,2 GB μνήμης RAM.

Πέρα από την τεχνολογία, όμως, βρισκόμαστε αντιμέτωποι με ένα πολύ μεγαλύτερο, δομικό πρόβλημα.

Δοκιμάστε να καταχωρίσετε οποιοδήποτε κοινό όνομα στο Gmail σήμερα: john, maria, kostas... Όλα είναι πιασμένα.

Η δική μας γενιά έχει εξαντλήσει κάθε προφανή συνδυασμό.

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

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

Η επιλογή των posts/links γίνεται με ένα στατιστικό μοντέλο και μπορεί να μην απεικονίζει επακριβώς τη σειρά δημοτικότητάς τους