Ημερολόγιο Εκδηλώσεων

Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών

Πρόγραμμα Προπτυχιακών Σπουδών

ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ

ΓΚΟΥΤΖΙΟΥΛΗ ΔΗΜΗΤΡΑΣ

με θέμα

Συνόψεις σε Ροές Δεδομένων στο Apache Flink

Synopses over Streaming Data at Apache Flink

Δευτέρα 7 Οκτωβρίου 2019, 9 π.μ.

Αίθουσα 2041, Κτίριο Επιστημών, Πολυτεχνειούπολη

Εξεταστική Επιτροπή

Αναπληρωτής Καθηγητής  Δεληγιαννάκης Αντώνιος (επιβλέπων)

Καθηγητής Γαροφαλάκης Μίνως

Αναπληρωτής Καθηγητής Σαμολαδάς Βασίλειος

Περίληψη

́Ενας μεγάλος αριθμός εφαρμογών απαιτεί αλγορίθμους και δομές δεδομένων που επεξεργάζονται αποδοτικά σύνολα δεδομένων που απαρτίζονται από gigabytes σε terabytes μέχρι petabytes. Τεράστιες ποσότητες πληροφοριών που παράγονται συνεχώς από διάφορες πηγές ονομάζονται Μεγάλα Δεδομένα. Τα Μεγάλα Δεδομένα είναι δεδομένα που περιέχουν τεράστια ποικιλία, φθάνουν σε αυξανόμενες ποσότητες και με μεγάλη ταχύτητα. Σήμερα, πολλές εφαρμογές λαμβάνουν δεδομένα σε συνεχείς ροές δεδομένων οι οποίες πρέπει να επεξεργάζονται αμέσως κατά την άφιξή τους. Έτσι, η χρήση δομών δεδομένων που ονομάζονται Συνόψεις, είναι απαραίτητη για τη διαχείριση πληθώρας δεδομένων, καθώς δεν είναι αποτελεσματική η μαζική διαχείριση τους. Οι συνόψεις συνοψίζουν το σύνολο δεδομένων και παρέχουν προσεγγιστικές απαντήσεις σε επερωτήματα. Μια από τις κύριες οικογένειες των συνόψεων είναι τα σκίτσα. Ένα σκίτσο μιας μεγάλης ποσότητας δεδομένων είναι μια μικρή δομή δεδομένων που μπορεί να υπολογίσει ή να προσεγγίσει ορισμένα χαρακτηριστικά των αρχικών δεδομένων. Στην παρούσα διπλωματική εργασία εστιάζουμε στους διάφορους αλγορίθμους ροών σκίτσων όπως το Bloom Filter, το Count-Min, το Flajolet-Martin και το AMS σκίτσο. Προτείνουμε μια παράλληλη υλοποίηση της εγγραφής επερωτήσεων των παραπάνω σκίτσων τα οποία θα ενημερώνονται καθώς φτάνουν όλο και περισσότερα δεδομένα, θα εισάγονται δυναμικά νέα στιγμιότυπα των παραπάνω σκίτσων κατά την εκτέλεση σε πραγματικό χρόνο και θα υπολογίζονται διάφορες συναρτήσεις. Αυτές οι συναρτήσεις μπορούν να εκτιμήσουν το πλήθος των στοιχείων, την ποσότητα διακριτών στοιχείων ή να ενημερώσουν για την ύπαρξη ενός στοιχείου σε μία ροή. Για την υλοποίηση του παραπάνω εγχειρήματος, χρησιμοποιήσαμε την πλατφόρμα Apache Flink. Το Flink είναι ένας κατανεμημένος συνεχούς ροής μηχανισμός με υψηλό ρυθμό επεξεργασίας δεδομένων, χαμηλό χρόνο καθυστέρησης και αντοχή σε υπολογιστικά σφάλματα σε οριοθετημένες ή και μη ροές δεδομένων. Αρχικά, παρουσιάζουμε το θεωρητικό υπόβαθρο των εφαρμοζόμενων αλγορίθμων και της κατανεμημένης πλατφόρμας. Στη συνέχεια, εξηγούμε την υλοποίηση του κώδικα καθώς χρησιμοποιούμε ως πηγή δεδομένων το Apache Kafka, τους μετασχηματισμούς της διεπαφής Datastream του Flink και τελικά, το χαρακτηριστικό Queryable State του Flink. Μέσω αυτής της μεθόδου, οι χρήστες ζητούν να μάθουν τις πιο ενημερωμένες τιμές των σκίτσων και επιπλέον αυτή η πληροφορία μπορεί να χρησιμοποιηθεί ως πηγή σε άλλες πλατφόρμες.

​​​​​​​​​​​​​​Abstract

A  growing  number  of  applications  demand  algorithms  and  data  structures  that  enable  the efficient  processing  of  data  sets  with  gigabytes  to  terabytes  to  petabytes.   Massive amounts of information that are generated continuously from numerous types of sources are called Big Data.  Big Data is data that contains greater variety arriving in increasing volumes and with ever-higher velocity. Nowadays, many applications receive data in a streaming fashion way that must be processed on the fly as it arrives.  Thus, the use of data structures called Synopses, is essential for managing such massive data, as handling large data sets is not often efficient to work fully on them.  Synopses summarize the data set and provide approximate responses to queries. One of the main families of synopses are sketches.  A sketch of a large amount of data is a small data structure that is able to calculate or approximate certain characteristics of the original data.  In this diploma thesis we focus on various streaming algorithms of sketches such as Bloom Filter, Count-Min, Flajolet-Martin and AMS sketches. We  propose  a  parallel  implementation  of  query  registration  of  the  above  sketches  to  be updated as more data arrives, insert dynamically new instances of these sketches in real-time execution and compute several functions.  These functions may estimate the cardinality of the elements, the amount of distinct elements, or inform about the existence of an element in a stream.  In order to develop that, we used the Apache Flink framework. Flink is a distributed streaming engine with high-throughput, low-latency and fault-tolerant computations over un-bounded and bounded data streams. First of all, we expound the theoretical background of the implemented algorithms and the distributed framework. Then, we explicate the implementation of the code as we use a Kafka connector, the transformations of Datastream API and finally the Queryable State feature of Flink. Through  that  method,  users  query  the  most  up-to-date  values  of  the  sketches  while other platforms can use this information as source.