Google File System, HDFS, BigTable PDF

Google File System, HDFS, BigTable και Hbase Συστήματα Διαχείρισης Μεγάλου Όγκου Δεδομένων Πανεπιστήμιο Θεσσαλίας Τμήμα Πληροφορικής και Τηλεπικοινωνιών Ιωάννης Κωνσταντίνου [email protected] Περιεχόμενα Εισαγωγή GFS HDFS BigTable Cassandra [email protected]...

Google File System, HDFS, BigTable και Hbase Συστήματα Διαχείρισης Μεγάλου Όγκου Δεδομένων Πανεπιστήμιο Θεσσαλίας Τμήμα Πληροφορικής και Τηλεπικοινωνιών Ιωάννης Κωνσταντίνου [email protected] Περιεχόμενα Εισαγωγή GFS HDFS BigTable Cassandra [email protected] 2 Γενικά Λειτουργίες ενός κατανεμημένου συστήματος: – Ονομασία – Διαμοιρασμός – Προσωρινή αποταμίευση – Αντίγραφα αρχείων Επιπλέον πρέπει να παρέχει στους χρήστες του: – Συνέπεια – Αξιοπιστία – Διαθεσιμότητα – Κλιμακωσιμότητα – Ασφάλεια – Διαφάνεια [email protected] 3 Γενικά Σε ένα Cloud – Απαιτείται δυνατότητα αποθήκευσης και διαχείρισης μεγάλου συνόλου δεδομένων. – Τα δεδομένα αξιοποιούνται και παράγονται σε διαφορετικές τοποθεσίες. – Οι βλάβες του υλικού είναι πολύ συχνές. – Τα αρχεία έχουν πολύ μεγάλο μέγεθος. [email protected] 4 GFS: Google File System Ένα κλιμακώσιμο κατανεμημένο σύστημα αρχείων προσανατολισμένο προς κατανεμημένες εφαρμογές διαχείρισης μεγάλου όγκου δεδομένων. Προσφέρει ανοχή σε σφάλματα, παρότι εκτελείται σε υπολογιστές μεσαίας ισχύος, και παράλληλα διαθέτει την ικανότητα να εξυπηρετεί ένα μεγάλο σύνολο από πελάτες. [email protected] 5 Παραδοχές Υψηλή συχνότητα βλαβών. Τα αρχεία σε τέτοιου είδους συστήματα είναι μεγάλα datasets σε GB 2 ειδών reads: μεγάλα σειριακά reads ή μικρά random reads Τα περισσότερα αρχεία τροποποιούνται µε προσάρτηση(append). Ειδικός χειρισμός για παράλληλο append. Ταιριάζουν για data analytics – Συνήθως µεγάλα αρχεία. – Το υψηλό bandwidth προτιµάται από το χαµηλό latency. [email protected] 6 Διεπαφή συστήµατος αρχείων create/delete open/close read/write Snapshot record append [email protected] 7 Αρχιτεκτονική Ένας master. Πολλαπλοί chunkserver. Πολλάπλοί clients. Τα αρχεία χωρίζονται σε chunks σταθερού µεγέθους. Δεν πραγματοποιείται caching. [email protected] 8 Αρχιτεκτονική Client Master Chunkserver Chunkserver Chunkserver [email protected] 9 Αρχιτεκτονική [email protected] 10 Αρχιτεκτονική Πολύ σημαντικό : η ροή δεδομένων αποσυνδέεται από τη ροή ελέγχου – Οι πελάτες αλληλεπιδρούν με τον master για τις λειτουργίες μεταδεδομένων – Οι πελάτες αλληλεπιδρούν άμεσα με τους chunkservers για όλες τις λειτουργίες των αρχείων – Αυτό σημαίνει ότι η απόδοση μπορεί να βελτιωθεί προγραμματίζοντας την ακριβή ροή δεδομένωνμε βάση την τοπολογία του δικτύου Ούτε οι υπολογιστές-πελάτες ούτε οι διακομιστές chunkservers αποθηκεύουν δεδομένα αρχείου cache – Οι ομάδες εργασίας είναι συνήθως πολύ μεγάλες για να αποθηκευτούν προσωρινά, οι chunkservers μπορούν να χρησιμοποιήσουν το Linuxbuffer cache [email protected] 11  Μέγεθος chunk 64 ΜΒ Μειωμένη ανάγκη επικοινώνίας client και master. Μειωμένος φόρτος δικτύου. Μικρότερο μέγεθος δομών δεδομένων στον master. Chunks από μικρά αρχεία μπορεί να αποτελέσουν hotspots. [email protected] 12 Master Ο master διατηρεί: – Το namespace. – Την αντιστοιχία από αρχεία σε chunks. – Τις θέσεις των chunks. Όλα τα μεταδεδομένα βρίσκονται στη μνήμη του master. (ταχύτητα, garbage collection, περιορισμένη μνήμη) Ο master εντοπίζει τα chunks μέσω heartbeat μηνυμάτων Σημαντικές αλλαγές στο GFS διατηρούνται στο operation log. Checkpoints. [email protected] 13 Συνέπεια Ένα αρχείο µπορεί να βρίσκεται σε µία από τις παρακάτω καταστάσεις: – Consistent – Defined – Inconsistent [email protected] 14 Συνέπεια Ορολογία: – συνεπής : όλοι οι πελάτες θα βλέπουν πάντοτε τα ίδια δεδομένα, ανεξάρτητα από το ποια αντίγραφα διαβάζουν – Ορισμένη: ίδια με την συνεπή και, επιπλέον, οι πελάτες θα δουν σε ποια είναι η τροποποίηση στο σύνολο της Εγγυήσεις: [email protected] 15 Lease, mutation και ροή δεδοµένων Mutation είναι κάθε αλλαγή στα δεδομένα ενός αρχείου και εφαρμόζεται σε όλα τα αντίγραφα του. Όταν σε ένα αντίγραφο του αποδοθεί ένα lease τότε θεωρείται το primary και διαχειρίζεται τα mutation στα υπόλοιπα αντίγραφα. Η ρόή δεδομένων διαχωρίζεται από τη ροή ελέγχου. Τα δεδομένα διαδίδονται σειριακά από ένα chunkserver στον κοντινότερο με pipelining. [email protected] 16 Τροποποιήσεις δεδομένων στο GFS Μετά από μια σειρά τροποποιήσεων, εάν είναι επιτυχής, τότε η περιοχή τροποποιημένου αρχείου εγγυάται την defined κατάσταση και περιέχει δεδομένα που έχουν γραφτεί από την τελευταία τροποποίηση Το GFS εφαρμόζει την τροποποίηση σε ένα κομμάτι με την ίδια σειρά σε όλα τα αντίγραφα του Ένα τεμάχιο χάνεται μη αναστρέψιμα αν και μόνο εάν χάνονται όλα τα αντίγραφα του πριν ο κύριος κόμβος μπορεί να αντιδράσει, συνήθως μέσα σε λίγα λεπτά – ακόμα και στην περίπτωση αυτή, τα δεδομένα χάνονται, δεν αλλοιώνονται [email protected] 17 Προσάρτηση Εγγραφών Μια λειτουργία τροποποίησης που εγγυάται ότι τα δεδομένα (η "εγγραφή") θα προσαρτηθούν ατομικά τουλάχιστον μία φορά - αλλά στο offset της επιλογής του GFS – Το offset που επιλέγεται από το GFS επιστρέφεται στον πελάτη έτσι ώστε να γνωρίζει η εφαρμογή Το GFS μπορεί να εισάγει “padded” αντίγραφα ή να καταγράφει διπλότυπα μεταξύ διαφορετικών λειτουργιών προσάρτησης εγγραφών Είναι προτιμόμενο οι εφαρμογές να χρησιμοποιούν αυτό αντί για write – Οι εφαρμογές θα πρέπει επίσης να γράφουν εγγραφές αυτο-επικύρωσης (π.χ. checksumming) με μοναδικά αναγνωριστικά για να χειρίζονται τα padding / duplicates [email protected] 18  Αλληλεπιδράσεις συστημάτος Εάν ο master λάβε μια λειτουργία τροποποίησης για ένα συγκεκριμένο τεμάχιο: – Ο master βρίσκει τους chunkservers που έχουν το κομμάτι και χορηγεί μια μίσθωση κομματιού (chunk lease) σε ένα από αυτά – Αυτός ο διακομιστής ονομάζεται πρωτεύων, οι άλλοι διακομιστές ονομάζονται δευτερεύοντες – Ο πρωτεύων προσδιορίζει τη σειρά σειριοποίησης για όλες τις τροποποιήσεις του τμήματος και τα δευτερεύοντα ακολουθούν αυτή τη σειρά – Μετά τη λήξη της μίσθωσης (~ 60 δευτερόλεπτα), ο πρωτεύων μπορεί να παραχωρήσει την πρωτεύουσα κατάσταση σε διαφορετικό διακομιστή για το συγκεκριμένο τμήμα – Ο master μπορεί, κατά καιρούς, να ανακαλέσει μια μίσθωση (π.χ. να απενεργοποιήσει τις τροποποιήσεις όταν το αρχείο μετονομάζεται) – Όσο τροποποιείται το κομμάτι, ο πρωτεύον μπορεί να ζητήσει μια επέκταση επ 'αόριστον – Εάν ο master χάνει την επαφή με τον πρωτεύων, είναι OK: απλώς χορηγείται μια νέα μίσθωση μετά την λήξη της παλαιάς [email protected] 19  Αλληλεπιδράσεις συστημάτος 1. Ο πελάτης καλεί τον πρωτεύοντα για όλους τους chunkservers (συμπεριλαμβανομένων όλων των δευτερευόντων) 2. Ο master χορηγεί μια νέα μίσθωση σε ένα τεμάχιο, αυξάνει τον αριθμό της έκδοσης του τμήματος, λέει σε όλα τα αντίγραφα να κάνουν το ίδιο. Απαντάει στον πελάτη. Ο πελάτης δεν χρειάζεται πλέον να μιλάει με τον master 3. Ο πελάτης σπρώχνει δεδομένα σε όλους τους διακομιστές, όχι κατ 'ανάγκη στον πρωταρχικό 4. Μόλις επικυρωθούν τα δεδομένα, ο πελάτης στέλνει αίτημα εγγραφής στον πρωτεύον. Ο πρωτεύων αποφασίζει την σειριοποίηση για όλες τις εισερχόμενες τροποποιήσεις και τις εφαρμόζει στο κομμάτι [email protected] 20  Αλληλεπιδράσεις συστημάτος 5. Μετά την ολοκλήρωση της τροποποίησης, ο πρωτεύων προωθεί το πρωταρχικό αίτημα εγγραφής προς τα εμπρός και την σειρά σειριοποίησης στους δευτερεύοντες, ώστε να μπορούν να εφαρμόζουν τροποποιήσεις με την ίδια σειρά. (Εάν ο πρωτεύων αποτύχει, αυτό το βήμα δεν εκτελείται ποτέ.) 6. Όλοι οι δευτερεύοντες απαντούν στον πρωτεύοντα μόλις ολοκληρώσουν τις τροποποιήσεις 7. Ο πρωτεύων απαντάει στον πελάτη, είτε με επιτυχία είτε με σφάλμα – Εάν η εγγραφή επιτύχει στον πρωτεύων αλλά αποτύχει σε οποιαδήποτε από τους δευτερεύοντες, τότε έχουμε μη-συνεπή κατάσταση → επιστρέφει σφάλμα στον πελάτη – Ο πελάτης μπορεί να επαναλάβει τα βήματα (3) έως (7) Σημείωση : Εάν η εγγραφή περιβάλλει το όριο του τμήματος (chunk), το GFS χωρίζει αυτό σε πολλαπλές εγγραφές [email protected] 21  Αλληλεπιδράσεις συστήματος για την εγγραφή προσαρτήσεων Όπως και πριν, αλλά με τα ακόλουθα επιπλέον βήματα: – Στο βήμα (4), ο πρωτεύων ελέγχει για να διαπιστωθεί αν η προσάρτηση εγγραφής στο τρέχον κομμάτι υπερβαίνει το μέγιστο μέγεθος (64 MB) – Αν ναι, κόβει το κομμάτι, ειδοποιεί τους δευτερεύοντες να κάνουν το ίδιο και λέει στον πελάτη να ξαναδοκιμάσει το αίτημα στο επόμενο κομμάτι – Η εγγραφή της προσθήκης περιορίζεται στο ¼ τέταρτο μέγεθος του chunk → το πολύ, το padding θα είναι 16 MB Εάν η προσθήκη εγγραφής αποτύχει σε οποιοδήποτε από τα αντίγραφα, ο πελάτης πρέπει να προσπαθήσει ξανά – Αυτό σημαίνει ότι αντίγραφα του ίδιου τμήματος ενδέχεται να περιέχουν αντίγραφα Μία επιτυχημένη εγγραφή; Αυτό σημαίνει ότι τα δεδομένα πρέπει να έχουν γραφτεί με το ίδιο offset σε όλα τα αντίγραφα του κομματιού – Ως εκ τούτου, το GFS εγγυάται ότι η προσάρτηση εγγραφών θα οριστεί διαδοχικά με ασυνεπή [email protected] 22  Current lease holder? Write request 3a. data identity of primary location of replicas (cached by client) Operation completed Operation completed or Error report 3b. data Primary assign s/n to mutations Applies it Forward write request 3c. data Operation completed [email protected] 23 Lease, mutation και ροή δεδοµένων (Αποθήκευση) Client Master Chunkserv Chunkserv Chunkserv er er er [email protected] 24 Lease, mutation και ροή δεδοµένων (Ανάγνωση) Client Master Chunkserv Chunkserv Chunkserv er er er [email protected] 25 Διαχείριση namespace και locking Υπάρχει αντιστοίχηση μεταξύ ενός αρχείου και του πλήρους pathname του. Read lock. Write lock. Παράλληλες αλλαγές στο ίδιο directory. [email protected] 26 Τοποθέτηση αντιγράφων Μεγιστοποίηση αξιοπιστίας και διαθεσιµότητας δεδοµένων. Μεγιστοποίηση χρήσης bandwidth. Ο χρήστης μπορεί να επιλέξει τον αριθμό των επιπλέον αντιγράφων (replicas). [email protected] 27 Ισορροπία δεσµευµένων πόρων Νέα αντίγραφα τοποθετούνται σε κόµβους µε σχετικά ελαφρύ φορτίο. ΄Ισος καταµερισµός δηµιουργιών αρχείων ανά chunkserver. Καταµερισµός αντιγράφων. Ο master δίνει προτεραιότητες στην αντιγραφή. [email protected] 28 Garbage collection Μετονοµασία αρχείου προς διαγραφή. Περιοδικός έλεγχος για τη διαγραφή τους. [email protected] 29 Stale replica detection Chunk version number. Αυξάνεται µε κάθε µίσθωση. Παλιά αντίγραφα αφαιρούνται από το µηχανισµό garbage collection [email protected] 30 Υψηλή διαθεσιµότητα Γρήγορη ανάρρωση από σφάλματα. Πολλαπλά αντίγραφα. Αντιγραφή της κατάστασης του master. [email protected] 31 Ακεραιότητα δεδοµένων Δεν είναι σωστό και πρακτικό να γίνεται έλεγχος μεταξύ των chunks. Χρήση checksums. Έλεγχος δεδοµένων πριν µεταφερθούν. Περιοδική εξέταση για corrupted chunks. [email protected] 32  Hadoop HDFS Hadoop Distributed File System (HDFS) είναι το πρωτεύον αποθηκευτικό σύστημα που χρησιμοποιείται από όλες τις εφαρμογές Hadoop. Το HDFS διασπάει το δεδομένα σε blocks και δημιουργεί αντίγραφα τους σε διαφορετικούς υπολογιστικούς κόμβους για να επιτύχει αξιόπιστους και υπερβολικά γρήγορους υπολογισμούς. Φροντίζει για τα αντίγραφα και την τοπικότητα των δεδομένων Ξεκίνησε σαν open source υλοποίηση του GFS [email protected] 33 Πλεονεκτήματα του Hadoop HDFS Κατανεμημένο αποθηκευτικό σύστημα πολύ μεγάλου μεγέθους. – 10.000 κόμβοι. – 100.000.000 αρχεία. – 10PB αποθηκευτικός χώρος. Βασίζεται σε φθηνό Hardware. – Κρατούνται αντίγραφα ασφαλείας των αρχείων ώστε να αντιμετωπίζονται οι βλάβες. – Ανίχνευση βλαβών και ανάκτηση. Είναι βελτιστοποιημένο για Batch processing – Οι τοποθεσίες των δεδομένων είναι διακριτές έτσι ώστε οι υπολογισμοί να μεταφέρονται εκεί που βρίσκονται τα δεδομένα – Παρέχει πολύ υψηλό συνολικό εύρος ζώνης Ο χώρος αποθήκευσης μπορεί να βρίσκεται σε ετερογενή λειτουργικά συστήματα. [email protected] 34 Βασικές αρχές του HDFS Ο χώρος των αρχείων είναι ενιαίος για όλο το cluster Επιβλέπει την συνέπεια των δεδομένων – Βασίζεται στο μοντέλο Write-once-read-many – Υποστηρίζεται στα αρχεία μόνο η διαδικασία append Τα αρχεία διασπόνται σε blocks – Τυπικό μέγεθος block 128 MB. – Κάθε block αντιγράφεται σε πολλαπλούς κόμβους δεδομένων (DataNodes). – Τα δεδοµένα δεν γράφονται απευθείας στο δίσκο. Πρώτα αποθηκεύονται σε buffer. Βασίζεται σε έξυπνους πελάτες (Clients). – Οι Clients μπορούν να βρουν την τοποθεσία των blocks – Οι Client προσπελαύνουν τα δεδομένα απευθείας στους DataNodes [email protected] 35  Η αρχιτεκτονική του HDFS Cluster Membership NameNode Secondary NameNode Client Cluster Membership NameNode : Maps a file to a file-id and list of MapNodes DataNode : Maps a block-id to a physical location on disk DataNode SecondaryNameNode: Periodic merge of Transaction log s [email protected] 36  NameNode - DataNode NameNode DataNode Metadata στην μνήμη Εξυπηρετητής Block – Όλα τα μεταδεδομένα φυλάσσονται στην – Τα δεδομένα αποθηκεύονται στο τοπικό κύρια μνήμη RAM σύστημα αρχείων (π.χ. ext3) – Δεν χρησιμοποιείται paging στα μεταδεδομένα – Αποθηκεύονται μεταδιδόμενα του κάθε block (π.χ. CRC) Είδη μεταδεδομένων – Μεταφέρει δεδομένα και μεταδεδομένα στους Clients. – Η λίστα των αρχείων – Η λίστα των Blocks για κάθε αρχείο Αναφορά Block – Η λίστα των DataNodes που περιέχουν το κάθε – Περιοδικά στέλνει μια αναφορά με όλα τα block υπάρχοντα blocks στον NameNode – Ιδιότητες αρχείων, πχ ώρα δημιουργίας, αριθμός αντιγράφων κλπ Διευκολύνει το Pipelining των δεδομένων – Προωθεί δεδομένα σε άλλους κόμβους Καταγραφή συμβάντων – Καταγράφονται δημιουργίες αρχείων, διαγραφές αρχείων κλπ [email protected] 37  Εγγραφή – Ανάγνωση στο HDFS [email protected] 38  Write Data Pipelining Ο Client λαμβάνει μια λίστα από DataNodes στους οποίους θα δημιουργηθούν τα αντίγραφα του block Ο Client γράφει το block στον πρώτο DataNode Ο Πρώτος DataNode προωθεί τα δεδομένα στον επόμενο DataNode του Pipeline Όταν όλα τα δεδομένα έχουν γραφτεί ο Client συνεχίζει την εγγραφή του επόμενου block του αρχείου [email protected] 39  NameΝode αντίγραφα Blocks Η στρατηγική που ακολουθείται – Ένα αντίγραφο στον τοπικό κόμβο. – Δεύτερο αντίγραφο στο ίδιο rack – Τρίτο αντίγραφο σε απομακρυσμένο rack – Επιπλέον αντίγραφα τοποθετούνται σε τυχαίους κόμβους Οι Clients διαβάζουν από τον πλησιέστερο αντίγραφο [email protected] 40 Replication Datanodes 1 2 1 1 2 2 4 5 3 4 3 3 5 5 4 Rack 1 Rack 2 [email protected] 41  Η ορθότητα των δεδομένων Η χρήση Checksums για την επικύρωση δεδομένων – χρήση CRC32 Κατά την δημιουργία αρχείων – ο Client υπολογίζει το checksum κάθε 512 bytes – οι DataNodes αποθηκεύουν τα checksums Κατά την πρόσβαση των αρχείων – ο Client λαμβάνει τα δεδομένα και το checksum από τον DataNode – εάν η επικύρωση αποτύχει τότε ο Client δοκιμάζει άλλο κόμβο [email protected] 42  Βλάβη στον NameNode A single point of failure Η καταγραφή των συναλλαγών αποθηκεύεται σε πολλαπλούς καταλόγους – Έναν κατάλογο στο τοπικό σύστημα αρχείων – Έναν κατάλογο σε απομακρυσμένο σύστημα αρχείων Υπάρχει η ανάγκη να ανατηχθεί μια λύση υψηλής διαθεσιμότητας (HA solution) [email protected] 43  Rebalancer Σε περίπτωση που κάποιος datanode βρεθεί µε πλεόνασµα αντιγράφων τότε το φορτίο µοιράζεται αυτόµατα. Σκοπός: όλοι οι δίσκοι των DataNodes να έχουν το ίδιο ποσοστό δεδομένων – Συνήθως τρέχει όταν νέοι DataNodes προστίθενται στο σύστημα. – ο Cluster παραμένει λειτουργικός όταν εκτελείται ο Rebalancer. – ο Rebalancer τίθεται σε αναμονή όταν υπάρχει μεγάλη κίνηση στο δίκτυο. – Είναι ένα εργαλείο Command line. [email protected] 44  Τι δεν κάνει το HDFS Transactional data? (e.g. concurrent reads and writes to the same data) – Εδώ το HDFS θα χρειαστεί να αποθηκεύει τα δεδομένα ένα file κάθε εγγραφή. Structured data? (e.g. record oriented views, columns) – Τα metadata είναι μόνο σε μορφή καταλόγων και ονομάτων αρχείων Relational data? (e.g. indexes) – Δεν υποστηρίζει αναζητήσεις. Ότι δεν κάνει το HDFS το κάνει ηHBase (BigTable)... [email protected] 45  BigTable ⚫ Το Bigtable αποτελεί ένα κατανεμημένο σύστημα αποθήκευσης για τη διαχείριση μεγάλης ποσότητας ημι-δομημένων δεδομένων και προσανατολισμένο στην κλιμακωσιμότητα (scalability) ⚫ Χρησιμοποιείται από την Google ⚫ Analytics, Google Earth, web indexing, κλπ ⚫ Κλειστού κώδικα ⚫ OSDI’06 [email protected] 46  Χαρακτηριστικά ⚫ Μεγάλο εύρος εφαρμογών ⚫ Batch processing εφαρμογές ⚫ Εφαμογές χαμηλής καθυστέρησης για χρήστες ⚫ Κλιμακωσιμότητα ⚫ Υψηλή απόδοση ⚫ Υψηλή διαθεσιμότητα ⚫ Δυνατότητα χρήσης σε συνδυασμό με MapReduce ⚫ Εκτελείται σε μέσου κόστους υλικό [email protected] 47  Μοντέλο δεδομένων ⚫ Είναι ένας αραιός, κατανεμημένος, πολυδιάστατος πίνακας ⚫ Διευθυνσιοδοτείται από: ⚫ Κλειδί γραμμής ⚫ Κλειδί στήλης ⚫ Χρονοσφραγίδα ⚫ Κάτι σαν συντεταγμένες ⚫ Κάθε κελί περιέχει ένα σύνολο bytes (row,colum Valu n,time) e [email protected] 48  Γραμμές (rows) ⚫ Το κλειδί απότελείται από ένα αλφαριθμητικό ⚫ Οι ενεργειες πάνω σε μία γραμμή είναι ατομικές ⚫ Λεξικογραφική ταξινόμηση με βάση τα κλειδιά ⚫ Όλος ο πίνακας αποτελείται από (δισ/τρισ/κλπ)εκατομμύρια λεξικογραφικά ταξινομημένες γραμμές. ⚫ Προσοχή: το row key είναι το μόνο πεδίο που γίνεται indexed στον BigTable ⚫ Αναζήτηση σε όλα τα άλλα πεδία γίνεται με full table scan [email protected] 49  Στήλες (columns) ⚫ Ομαδοποίηση σε column families. Σπάσιμο σε column families ανάλογα το application ⚫ Μικρός αριθμός από column families (πχ ~100) ⚫ Άπειρος αριθμός από columns ⚫ Μορφή family:qualifier ⚫ Ο έλεγχος πρόσβασης γίνεται με βάση τα column families [email protected] 50  Χρονοσφραγίδες (timestamps) ⚫ Πολλαπλές εκδόσεις των ίδιων δεδομένων ⚫ Πραγματικός χρόνος ή ⚫ Καθορισμένος από το χρήστη ⚫ Οι πιο πρόσφατες εκδόσεις είναι ευκολότερο προσβάσιμες ⚫ Ρύθμιση για την διατήρηση των ⚫ Τελευταίων Χ εκδόσεων ή ⚫ Όλες τις εκδόσεις των τελευταίων Χ εβδομάδων [email protected] 51  Παράδειγμα ⚫ rowkey: URL ⚫ Γιατί είναι ανάποδα γραμμένο? ⚫ Column families ⚫ Contents: Χωρίς column id. Το value είναι τα html contents (πολλές εκδόσεις) ⚫ Anchor: Έχει column id το url του link. Value είναι το κείμενο του link. ⚫ Ερώτηση: πως μπορώ να βρω όλες τις στήλες των οποίων το όνομα είναι cnnsi.com? [email protected] 52  API 1/2 ⚫ βασικές λειτουργίες βάσεων Δεδομένων: ⚫ Put(row_key, column_key,timestamp,value): βάλε μια τιμή σε ένα κελί. ⚫ Get(row_key) : επέστρεψε όλα τα κελιά για μια γραμμή ⚫ Get(row_key, column_key, timestamp): επέστρεψε ένα συγκεκριμένο κελί ⚫ Scan(start_row_key, end_row_key): επέστρεψε όλα τα κλειδιά μεταξύ start_key και end_key [email protected] 53  API 2/2 ⚫ Δεν υποστηρίζει joins!!! (κάντο με MapReduce εάν θες) ⚫ Δεν υποστηρίζει get(column_key) σκέτο: θα πρέπει να ξέρεις το row_key ⚫ No multi-row transactions ⚫ Atomic single-row writes ⚫ Optional atomic single-row reads ⚫ Δυνατότητα εκτέλεσης server-side script (sawzal) [email protected] 54  Αρχιτεκτονική ⚫ Αποτελείται από: ⚫ Την βιβλιοθήκη ⚫ Ένα master server ⚫ Πολλούς tablet servers ⚫ Στηρίζεται πάνω στα: ⚫ Google filesystem ⚫ SSTable ⚫ Chubby [email protected] 55  Tablets ⚫ Το ευρος των τιμών χωρίζεται σε tablets ⚫ Tablet: Ένα «ορθογώνιο κομμάτι» του πίνακα που περιέχει όλες τις γραμμές και στήλες μεταξύ δυο τιμών start και end. ⚫ Αποτελείται από πολλά SSTables SSTable: Tablet: [email protected] 56 Αρχιτεκτονική Client Έλεγχος Master Δεδομένα Chubby library library SSTable SSTable GFS GFS Tablet Tablet server server [email protected] 57  Master ⚫ Ανάθεση tablet σε κάποιον tablet server ⚫ Εντοπισμός νέων ή “ληγμένων” tablet servers ⚫ Εξισσόροπηση φόρτου ⚫ Συλλογή σκουπιδιών από το GFS ⚫ Διαχείριση schema ⚫ Δεν περνάνε δεδομένα από αυτόν ⚫ Τρέχει μαζί με τον Master του GFS. [email protected] 58  Tablet server ⚫ Διαχείριση ενός συνόλου tablets ⚫ Από δεκάδες μέχρι μερικές χιλιάδες ⚫ Εξυπηρέτηση αιτήσεων ανάγνωσης και εγγραφής ⚫ Διαίρεση των tablets που έχουν μεγαλώσει υπερβολικά (διαδικασία compaction) ⚫ Αρχικά υπάρχει ένα μόνο tablet ανά πίνακα το οποίο διαιρείται όταν γίνει περίπου 100-200 MB ⚫ Μπορούν να προστεθούν/αφαιρεθούν δυναμικά [email protected] 59  SSTable ⚫ Format αρχείου της Google ⚫ Μέγεθος τάξης MB (πχ 128MB) ⚫ Μπορεί να είναι και όλο στην RAM ⚫ Ταξινομημένα δεδομένα ⚫ Αντιστοιχεί κλειδιά σε τιμές ⚫ Αποτελείται από blocks τάξης KB (πχ 64ΚΒ) ⚫ Ένα «ειδικό» block περιέχει index για γρήγορη αναζήτηση ⚫ Σε περίπτωση που το SSTable είναι στον δίσκο, με το index block σε μια αναζήτηση βρίσκεται το block με 2 disk accesses. [email protected] 60  Chubby ⚫ Κατανεμημένο ⚫ Quorum από περιττό αριθμό servers ⚫ Paxos - like Algorithm (επίλυση διαφωνιών) ⚫ Υψηλή διαθεσιμότητα ⚫ Χρησιμοποιείται για: ⚫ υπηρεσίες lock (atomic transactions) ⚫ Εξασφάλιση λειτουργίας master ⚫ Αποθήκευση σημαντικών πληροφοριών(π.χ. schema) ⚫ Ανακάλυψη νέων tablet servers ⚫ Πληροφορίες ελέγχου πρόσβασης [email protected] 61  Οργάνωση των tablets ⚫ Ιεραρχία τριών επιπέδων για την αποθήκευση της πληροφορίας ⚫ Ένα αρχείο στο chubby περιέχει την τοποθεσία του root tablet ⚫ Το root tablet περιέχει πληροφορίες για το που βρίσκονται τα tablets ενός ειδικού πίνακα METADATA (1st METADATA) και δεν διαρείται ποτέ ⚫ Ο METADATA πίνακας περιέχει τις πληροφορίες για όλα τα υπόλοιπα tablets που περιέχουν τα δεδομένα του πίνακα [email protected] 62  Οργάνωση των tablets Table METADATA ROOT A a row Chubby ⚫ Με 128MB tablet μέγεθος και ένας ROOT που δεν σπάει ποτέ, υποστηρίζεται η διευθυνσιοδότηση 234 128MB tablets ή 261 bytes ⚫ Οι clients κάνουν cache το location. Στην χειρότερη (λάθος cache), με 6 network msgs βρίσκουν το location. [email protected] 63  Ανάθεση των tablets ⚫ Κάθε tablet ανατίθεται σε ένα tablet server ⚫ Ο master είναι υπεύθυνος για την ανάθεση τους ⚫ Ελεγχει την κατάσταση κάθε server περιοδικά ⚫ Το Chubby χρησιμοποιείται για την παρακολούθηση των tablet servers ⚫ Κατά την έναρξη ενός Master ⚫ Lock στο Chubby, ls στο dir, επικοινωνία με κάθε live server για να βρει ποια tablets είναι ήδη assigned, διάβασμα του METADATA για τα unassigned για να δοθούν σε νέους servers. [email protected] 64 Ξεκίνημα Master [email protected] 65  Μοίρασμα των tablets ⚫ Χρησιμοποιείται το GFS για την μόνιμη αποθήκευση των δεδομένων ενός tablet ⚫ Ένα commit log χρησιμοποιείται για τις ενημερώσεις ⚫ Οι πιο πρόσφατες διατηρούνται σε ένα memtable στη μνήμη RAM ⚫ Όταν ένα tablet ανακτάται τότε οι πληροφορίες του συγχωνεύονται με αυτές του memTable ⚫ Κάνει recovery από το log (WAL) [email protected] 66  Εξυπηρέτηση αιτήσεων [email protected] 67  Εγγραφή δεδομένων ⚫ Έλεγχος του είδους της εγγραφής και των δικαιωμάτων του χρήστη ⚫ Οι αλλαγές καταγράφονται στο commit log ⚫ Για να εξασφαλίσει ACID ⚫ Το memtable ενημερώνεται όταν ολοκληρωθεί η εγγραφή [email protected] 68  Εγγραφή δεδομένων write memtable Commit Log SSTa SSTa SSTa ble ble ble [email protected] 69  Συμπύκνωση (compaction) ⚫ Όταν το memtable μεγαλώσει αρκετά: ⚫ Minor compaction ⚫ Σταματάει να χρησιμοποιείται ⚫ Δημιουργείται ένα νέο ⚫ Το αρχικό εγγράφεται ως SSTable στο GFS ⚫ Major compaction: περιοδικά τα SSTables συγχωνευονται ⚫ Αποφεύγεται η δημιουργία πολλών αρχείων από πολλά minor compactions [email protected] 70  Συμπύκνωση write memtable Major Minor Compaction Compaction Commit Log SSTa SSTaSSTaSSTa SSTa ble ble ble ble ble [email protected] 71  Ανάγνωση δεδομένων ⚫ Έλεγχος του είδους της ανάγνωσης και των δικαιωμάτων του χρήστη ⚫ Η ανάγνωση πραγματοποιείται σε συνδιασμένα δεδομένα από το SSTable και του memtable [email protected] 72  Ανάγνωση δεδομένων read memtable Commit Log SSTa SSTa SSTa ble ble ble [email protected] 73  Βελτιώσεις ⚫ Locality groups ⚫ Με χρήση τους ομαδοποιούνται τα column families ⚫ Ένα ξεχωριστό SSTable δημιουργειται για καθένα ⚫ Διευκολύνουν την διαχείριση των πινάκων [email protected] 74  Βελτιώσεις ⚫ Συμπίεση ⚫ Ο χρήστης μπορεί να καθορίσει το επίπεδο της ⚫ Εφαρμόζεται σε κάθε SSTable block ξεχωριστά ⚫ Ταχύτητα εναντίον μεγάλης συμπίεσης (φτηνοί δίσκοι) ⚫ Δεν απαιτείται αποσυμπίεση ολοκληρου του αρχείου ⚫ Λόγοι 10/1 σε σχέση με τυπικό zip 3/1 επειδή τα δεδομένα που είναι «κοντά» μοιάζουν μεταξύ τους. ⚫ Snappy, data block encoding [email protected] 75  Βελτιώσεις ⚫ Caching ⚫ Πραγματοποιείται σε δύο επίπεδα ⚫ Η Scan Cache διατηρεί τα ζευγη key-value(υψηλό επίπεδο) ⚫ Η Block Cache διατηρεί ολόκληρα blocks από το SSTable(χαμηλό επίπεδο) [email protected] 76  Βελτιώσεις ⚫ Bloom filters ⚫ Ο χρήστης καθορίζει αν θα χρησιμοποιηθούν ⚫ Χρησιμοποιείται για να καθοριστεί αν κάποιο SSTable περιέχει δεδομένα από συγκεκριμένο row χωρίς να το ανακτήσουμε ⚫ Με λίγο αποθηκευτικό χώρο παραπάνω μπορούμε να αποκλείουμε αμέσως μεγάλο αριθμό sstables. ⚫ Πιθανά false positives: Σε αυτή την περίπτωση απλά δεν θα βρει κάτι στο sstable. ⚫ Ποτέ false negatives: ότι δεν βρίσκει, σίγουρα δεν υπάρχει. ⚫ Δημιουργούνται βάση locality group [email protected] 77 Παράδειγμα Bloom Filter [email protected] 78  Παράδειγμα Bloom Filter [email protected] 79  Βελτιώσεις ⚫ Υλοποιήση του commit log ⚫ Υπάρχει μόνο ένα ανά tablet server (και όχι ανά tablet) ⚫ Αλλιώς θέλαμε πολλά ταυτόχρονα ανοιχτά αρχεία ανά server ⚫ Βελτιώνει την απόδοση, αλλά προκαλεί προβλήματα σε περίπτωση σφάλματος ⚫ Tablets γίνονται re-assign σε πολλούς νέους servers ⚫ Χρειάζονται όλοι να σκανάρουν όλο το log για να βρουν τα tablets που τους ενδιαφέρουν (για REDO/UNDO) ⚫ Ταξινόμηση βάσει του key ⚫ Σπάσιμο του commit log σε 64ΜΒ chunks για παραλληλοποίηση του sorting ⚫ Όλες οι αλλαγές ενός tablet βρίσκονται κοντά: μόνο ένα disk seek και seq. read για recovery ενός tablet [email protected] 80 HBase Κλώνος του Bigtable Ανοιχτού κώδικα Apache project «Συνοδεύει» το Hadoop – HDFS αντί GFS – Μπορεί να χρησιμοποιηθεί από το Hadoop MapReduce Java [email protected] 81  Αντιστοιχίες BigTable HBase Master HMaster TabletServer Region Server SSTable Hfile (περίπου) Tablet TableRegion Chubby Zookeeper GFS HDFS [email protected] 82  Ερωτήσεις? [email protected] 83