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

ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών

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

Ζωγραφούλας Ιωάννας Νεαμονιτάκη

με θέμα

Ποσοστημόρια σε Ροές Δεδομένων με Σχετικό Σφάλμα στο Apache Flink

Relative Error Streaming Quantiles in Apache Flink

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

Καθηγητής Αντώνιος Δεληγιαννάκης (Σχολή ΗΜΜΥ, Επιβλέπων)
Καθηγητής Μίνως Γαροφαλάκης (Σχολή ΗΜΜΥ)
Αναπληρωτής Καθηγητής ΒασίλειοςΣαμολαδάς (Σχολή ΗΜΜΥ)

Περίληψη

Οι σύγχρονες εφαρμογές παράγουν έναν συνεχώς αυξανόμενο όγκο δεδομένων, επιβαρύνοντας τα υπάρχοντα υπολογιστικά συστήματα όταν απαιτείται η εκτέλεση στατιστικής ανάλυσης και επεξεργασίας δεδομένων σε ροές δεδομένων μεγάλης κλίμακας. Μία αποτελεσματική λύση σε αυτό το πρόβλημα είναι η χρήση δομών δεδομένων σύνοψης (synopsis data structures), οι οποίες επιτρέπουν τη μείωση των απαιτήσεων σε μνήμη και υπολογιστική ισχύ, ιδιαίτερα σε κατανεμημένα περιβάλλοντα και περιβάλλοντα επεξεργασίας ροών δεδομένων. Η παρούσα διπλωματική εργασία επικεντρώνεται στην υλοποίηση του Relative Error Quantile Sketch (ReqSketch), ενός τυχαιοποιημένου sketch που παρέχει εγγυήσεις πολλαπλασιαστικού σφάλματος για την εκτίμηση rank και quantile (rank and quantile estimations), καθώς και στην ενσωμάτωσή του στο Apache Flink. Σε αντίθεση με αλγορίθμους sketch που είχαν υλοποιηθεί προηγουμένως και παρέχουν εγγυήσεις αθροιστικού σφάλματος στην εκτίμηση του rank, το ReqSketch παρέχει μεγαλύτερη ακρίβεια για ranks τα οποία βρίσκονται κοντά στα άκρα της κατανομής των δεδομένων. Το ReqSketch δεν προϋποθέτει εκ των προτέρων γνώση του συνολικού μεγέθους της ροής δεδομένων και είναι πλήρως συγχωνεύσιμο (fully mergeable), γεγονός που επιτρέπει την εύκολη ενσωμάτωσή του σε παράλληλα και κατανεμημένα υπολογιστικά περιβάλλοντα. Το ReqSketch ενσωματώνεται στο Synopses Data Engine (SDE), με κύριο σκοπό τη χρήση του σε ένα κατανεμημένο περιβάλλον επεξεργασίας ροών δεδομένων. Η ενσωμάτωση αυτή υποστηρίζει τη δημιουργία, τη συντήρηση και την υποβολή ερωτημάτων σε συνόψεις ReqSketch σε πολλαπλές υπολογιστικές μονάδες. Η προκύπτουσα υλοποίηση του ReqSketch αξιολογείται ως προς τον ρυθμό εισαγωγής δεδομένων (data ingestion throughput) και τον ρυθμό εκτίμησης ερωτημάτων (query estimation throughput), τόσο για ερωτήματα rank όσο και για ερωτήματα ποσοστημορίων (quantiles), υπό συνθήκες παράλληλης εκτέλεσης.

Abstract

Modern applications generate a continuous and ever-increasing volume of data, stressing existing systems, if statistical analysis and data processing is to be performed on large-scale data streams. One effective solution to this problem is the use of synopsis data structures, allowing for memory and computational power requirement reduction, particularly in distributed and streaming environments. The focus of this thesis is the implementation of the Relative Error Quantile Sketch (ReqSketch), a randomized sketch that provides multiplicative-error guarantees for rank and quantile estimations and its integration into Apache Flink. In contrast to previously implemented sketch algorithms that provide additive rank-error guarantees, ReqSketch provides higher accuracy for ranks near the tails of the data distribution. ReqSketch assumes no prior knowledge of the stream length and is fully mergeable, enabling it to be easily integrated into parallel and distributed computing environments. ReqSketch is integrated into the Synopses Data Engine (SDE), with the express purpose of using it within a distributed stream-processing environment. The integration supports the creation, maintenance, and querying of ReqSketch synopses, across multiple computing units. The resulting ReqSketch algorithm is tested in terms of data ingestion throughput and query estimation throughput for both rank and quantile queries under parallel execution.