Technologies for main memory data analysis

Abstract

The digital data has become a key resource for solving scienƟfic and business problems and achieving compeƟƟve advantage. With this purpose the scienƟfic and business communiƟes worldwide are trying to extract knowledge from data available to them. The Ɵmely use of data significantly affects scienƟfic progress, quality of life, and economic acƟvity.In the digital age the efficient processing and effecƟve data analysis are important challenges.The processing of data in main memory can boost processing efficiency especially if it is combinedwith new soŌware system architectures. At the same Ɵme useful and usable tools are required foranalysing main memory data to saƟsfy important use cases not met by database and programminglanguage technologies.The unified management of the memory hierarchy can improve the processing of data in mainmemory. In this architecture the communicaƟon between the different parts of the memory hierarchy is transparent to the applicaƟons and opƟmizaƟon techniques are applied holisƟcally. The data flow in the memory hierarchy so that the ones that will be processed shortly are closest to the Öçs and programming languages treat temporary and permanent data of any type uniformly. As a result, new data analysis systems can be developed that take advantage of faster main memory data structures over disk-based ones for processing the data leaving the memory hierarchy to care for the availability of data.The absence of suitable analyƟcal tools hinders knowledge extracƟon in cases of soŌware applicaƟons that do not need the support of a database system. Some examples are applicaƟons whose data have a complex structure and are oŌen stored in files, eg scienƟfic applicaƟons in areas such as biology, and applicaƟons that do not maintain permanent data, such as data visualizaƟon applicaƟons and diagnosƟc tools. Databases offer widely used and recognized query interfaces, but applicaƟons that do not need the services of a database should not resort to this soluƟon only to saƟsfy the need to analyze their data.Programming languages on the other hand rarely provide expressive and usable query interfaces.These can be used internally in an applicaƟon, but usually they do not offer interacƟve ad-hoc queries at runƟme. Therefore the data analysis scenarios they can support are standard and any addiƟons or modificaƟons to the queries entail recompiling and rerunning the applicaƟon.In addiƟon to solving problems modeled by soŌware applicaƟons, data analysis techniques areuseful for solving problems that occur in the applicaƟons themselves. This is possible by analyzing the metadata that applicaƟons keep in main memory during their operaƟon. This pracƟce can be applied to any kind of system soŌware, such as an operaƟng system.This thesis studies the methods and technologies for supporƟng queries on main memory dataand how the widespread architecture of soŌware systems currently affects technologies. Based onthe findings from the literature we develop a method and a technology to perform interacƟve queries on data that reside in main memory. Our approach is based on the criteria of usefulness and usability.AŌer an overview of the programming languages that fit the data analysis we choose Ýؽ, the standard data manipulaƟon language for decades.The method we develop represents programming data structures in relaƟonal terms as requires Ýؽ. Our method replaces the associaƟons between structures with relaƟonships between relaƟonal representaƟons. The result is a virtual relaƟonal schema of the programming data model, which we call relaƟonal representaƟon.The method’s implementaƟon took place on the and ++ programming languages because oftheir wide use for the development of systems and applicaƟons. An addiƟonal reason why ++ waschosen is the availability of a large number of algorithms and data structures that it offers. The implementaƟon includes a domain specific language for describing relaƟonal representaƟons, a compiler that generates the source code of the relaƟonal interface to the programming data structures given a relaƟonal specificaƟon, and the implementaƟon of Ýؽite’s virtual table Ö®. Ýؽite is a relaƟonal database system that offers the query engine and the ability to run queries to non-relaƟonal data through its virtual table Ö®.The implementaƟon expands to the development of two diagnosƟc tools for idenƟfying problemsin soŌware systems through queries to main memory metadata related to their state. as theimplementaƟon language of many soŌware systems is ideal for the applicaƟon of this idea. For thispurpose we incorporate our implementaƟon in the Linux kernel. Important implementaƟon aspectsthat we address is synchronized access to data and the integrity of query results. We also apply ourapproach to expand the diagnosƟc capabiliƟes of Valgrind, a system that controls the way that soŌware applicaƟons use memory.The overall evaluaƟon of our approach involves its integraƟon in three ++ soŌware applicaƟons,in the Linux kernel, and in Valgrind, where we also perform a user study with students. For the study we combine qualitaƟve analysis through quesƟonnaire and quanƟtaƟve analysis using code measurements.In the context of the ++ applicaƟons the performance measurements between Öi Ê Ø½queries and the corresponding queries expressed in ++ show that Ýؽ combined with our relaƟonal representaƟon provides greater expressiveness. The same happens when we compare our approach with Ýؽ aŌer imporƟng the data into a MyÝؽ relaƟonal database system. The efficiency of our approach is worse than ++ and beƩer than MyÝؽ. The queries with our approaches need twice as long Ɵme to run compared with ++ regardless of the problem’s size. The Ýؽ queries in MyÝؽ require double, triple, or more Ɵme to execute compared to our approach.In the context of the Linux kernel where our relaƟonal interface funcƟons as a diagnosƟc tool wefind real problems by execuƟng queries against the kernel’s data structures. Access to files without the required privileges, unauthorized execuƟon of processes, the idenƟficaƟon of binaries that are used in loading processes but are not used by any, and the direct execuƟon of system calls by processors belonging to a virtual machine are the security problems we idenƟfy. In addiƟon we show queries that combine metrics from different subsystems, such as pages in memory, disk files, processor acƟvity, and network data transfers, which can help idenƟfy performance problems. The measurement of query processing Ɵme and the added overhead to the system encourage the use of our tool.The diagnosƟc tool we developed for Valgrind detects problems, addiƟonal to those found byValgrind, through the use of quesƟons in the collected metadata of the applicaƟon being tested. The bzip2 tool for instance wastes nine hundred » where all the memory cells are consecuƟve in a single pool. This size is equivalent to twelve percent of the total memory that the applicaƟon needs to operate. Through queries on the dynamic funcƟon call graph formed during an applicaƟon’s execuƟonwe find a code path that is performance criƟcal. It is located in the glibc library and is widely used by the sort and uniq Unix tools. This opƟmizaƟon was implemented by glibc’s development team and was included in the next version without our contribuƟon.Finally, in the user study the one group expresses analysis tasks with Ýؽ queries and the otherwith Python code. The results show that the Ɵme required for the expression of an analysis job issmaller when Ýؽis used. On the contrary no staƟsƟcally significant differences are observed between the two approaches in terms of usefulness, efficiency, and expressiveness, although our approach has a higher raƟng. For the dimension of usability the evaluaƟons demonstrated no clear winner, but both approaches achieved very good evaluaƟon. The evaluaƟon of the Ýؽ group code’s performance shows that the Ýؽ group had more correct replies achieved with less Ɵme of programming. We consider this metric indicaƟve of our approach’s usefulness vis a vis Python, which is also widely used for data analysis. We also consider the Ɵme required for the expression of an analysis task as a usability factor.The challenges to the processing of data conƟnue to emerge at an unabated pace. In this environment soŌware applicaƟons require soluƟons for the analysis of user data, but also to solve problems relaƟng to their operaƟon. The processing of data in main memory can bring important benefits in combinaƟon with other innovaƟons. In this direcƟon new architectures that benefit the efficient processing of data can play an important role. We hope that this thesis will aid the efficient processing and effecƟve data analysis expected by users.

Τα ψηφιακά δεδομένα έχουν αναδειχθεί σε καθοριστικό πόρο για την επίλυση επιστημονικών και επιχειρηματικών προβλημάτων και για την επίτευξη ανταγωνιστικού πλεονεκτήματος. Με αυτό το σκοπό οι επιστημονικές και επιχειρηματικές κοινότητες διεθνώς προσπαθούν να εξάγουν γνώση από τα δεδομένα που έχουν στη διάθεσή τους. Η έγκαιρη αξιοποίηση των δεδομένων επηρεάζει σημαντικά την επιστημονική πρόοδο, την ποιότητα ζωής, και την οικονομική δραστηριότητα.Στην ψηφιακή εποχή η αποδοτική επεξεργασία και η αποτελεσματική ανάλυση των δεδομένων αποτελούν σημαντικές προκλήσεις. Η επεξεργασία των δεδομένων στην κύρια μνήμη μπορεί να προάγει την αποδοτικότητά της ειδικά αν συνδυαστεί με νέες αρχιτεκτονικές συστημάτων λογισμικού.Ταυτόχρονα όμως απαιτούνται χρήσιμα και χρηστικά εργαλεία ανάλυσης δεδομένων της κύριας μνήμης για να ικανοποιήσουν σημαντικές περιπτώσεις χρήσεις που δεν πληρούνται από τεχνολογίες βάσεων δεδομένων και γλωσσών προγραμματισμού.Η ενιαία διαχείριση της ιεραρχίας της μνήμης μπορεί να βελτιώσει την επεξεργασία των δεδομένων στην κύρια μνήμη. Σε αυτή την αρχιτεκτονική η επικοινωνία ανάμεσα στα διάφορα τμήματα της ιεραρχίας της μνήμης είναι διαφανής ως προς τις εφαρμογές ενώ οι τεχνικές βελτιστοποίησης εφαρμόζονται ολιστικά. Τα δεδομένα ρέουν στην ιεραρχία της μνήμης ούτως ώστε αυτά που πρόκειται να επεξεργαστούν να βρίσκονται όσο το δυνατόν πλησιέστερα στις κεντρικές μονάδες επεξεργασίας ενώ οι γλώσσες προγραμματισμού αντιμετωπίζουν ομοιόμορφα τα προσωρινά και τα μόνιμα δεδομένα κάθε τύπου. Ως αποτέλεσμα, νέα συστήματα ανάλυσης δεδομένων μπορούν να αναπτυχθούν που εκμεταλλεύονται τις ταχύτερες δομές δεδομένων της κύριας μνήμης έναντι αυτών του δίσκου για την επεξεργασία των δεδομένων αφήνοντας την ιεραρχία της μνήμης να φροντίσει για τη διαθεσιμότητα των δεδομένων.Η απουσία κατάλληλων εργαλείων ανάλυσης δυσχεραίνει την εξαγωγή γνώσης σε περιπτώσεις εφαρμογών λογισμικού που δε χρειάζονται την υποστήριξη μιας βάσης δεδομένων. Μερικά παραδείγματα είναι εφαρμογές των οποίων τα δεδομένα έχουν σύνθετη δομή και συχνά αποθηκεύονται σε αρχεία, π.χ. επιστημονικές εφαρμογές σε τομείς όπως η βιολογία, και εφαρμογές που δε διατηρούν μόνιμα δεδομένα, όπως εφαρμογές οπτικοποίησης δεδομένων και διαγνωστικά εργαλεία. Οι βάσεις δεδομένων προσφέρουν ευρέως χρησιμοποιούμενες και αναγνωρισμένες διεπαφές ερωτημάτων, όμως οι εφαρμογές που δεν έχουν ανάγκη τις υπηρεσίες μιας βάσης δεδομένων δεν πρέπει να καταφεύγουν σε αυτή τη λύση αποκλειστικά και μόνο για να ικανοποιήσουν την ανάγκη ανάλυσης των δεδομένων τους.Οι γλώσσες προγραμματισμού από την άλλη πλευρά σπάνια διαθέτουν εκφραστικές και εύκολες στη χρήση διεπαφές ερωτημάτων. Αυτές μπορούν να χρησιμοποιηθούν εσωτερικά σε μια εφαρμογή, αλλά συνήθως δεν προσφέρουν αλληλεπιδραστικά ερωτήματα σε χρόνο εκτέλεσης. Συνεπώς τα σενάρια ανάλυσης δεδομένων που μπορούν να υποστηρίξουν είναι τυποποιημένα και κάθε προσθήκη επιφέρει επαναμεταγλώττιση και επανεκτέλεση της εφαρμογής.Εκτός από την επίλυση προβλημάτων που μοντελοποιούνται από εφαρμογές λογισμικού, τεχνικές ανάλυσης δεδομένων είναι χρήσιμες και για την επίλυση προβλημάτων που παρουσιάζονται στις ίδιες τις εφαρμογές. Αυτό είναι εφικτό με την ανάλυση των μεταδεδομένων που φυλάσσουν οι εφαρμογές στην κύρια μνήμη κατά τη διάρκεια της λειτουργίας τους. Αυτή η πρακτική μπορεί να εφαρμοστεί σε κάθε είδους σύστημα λογισμικού όπως ένα λειτουργικό σύστημα.Η παρούσα διατριβή μελετά τις μεθόδους και τεχνολογίες για την υποστήριξη ερωτημάτων σε δεδομένα της κύριας μνήμης και πως η διαδομένη αρχιτεκτονική συστημάτων λογισμικού σήμερα επηρεάζει τις τεχνολογίες. Βάσει των ευρημάτων από τη βιβλιογραφία αναπτύσσουμε μια μέθοδο και μια τεχνολογία για την εκτέλεση αλληλεπιδραστικών ερωτημάτων σε δεδομένα της κύριας μνήμης.Η προσέγγισή μας βασίζεται στα κριτήρια της χρησιμότητας και της χρηστικότητας. Με τα από επισκόπηση των γλωσσών προγραμματισμού που ταιριάζουν στην ανάλυση δεδομένων επιλέγουμε την Ýؽ, την πρότυπη γλώσσα διαχείρισης δεδομένων εδώ και δεκαετίες.Η μέθοδος που αναπτύσσουμε αναπαριστά προγραμματιστικές δομές δεδομένων σε σχεσιακούς όρους όπως προϋποθέτει η Ýؽ. Η μέθοδος αντικαθιστά τις συσχετίσεις μεταξύ των δομών με σχέσεις μεταξύ των σχεσιακών αναπαραστάσεων. Το αποτέλεσμα είναι ένα ιδεατό σχεσιακό σχήμα του προγραμματιστικού μοντέλου δεδομένων το οποίο καλούμε σχεσιακή αναπαράσταση. H υλοποίηση της μεθόδου έγινε στις γλώσσες προγραμματισμού και ++ λόγω της ευρείας χρήσης τους για την ανάπτυξη συστημάτων και εφαρμογών. Ένας επιπλέον λόγος που επιλέχθηκε η ++είναι η διαθεσιμότητα μεγάλου αριθμού αλγορίθμων και δομών δεδομένων. H υλοποίηση περιλαμβάνει μια γλώσσα πεδίου για την περιγραφή σχεσιακών αναπράστασεων, έναν μεταγλωττιστή που παράγει τον πηγαίο κώδικα της σχεσιακής διεπαφής προς τις προγραμματιστικές δομές δεδομένων από μια σχεσιακή περιγραφή, και την υλοποίηση της προγραμματιστικής διεπαφής ιδεατών πινάκων της σχεσιακής βάσης δεδομένων Ýؽite. Η τελευταία προσφέρει τη μηχανή ερωτημάτων, η οποία δίνει τη δυνατότητα εκτέλεσης ερωτημάτων προς μη σχεσιακά δεδομένα μέσω της διεπαφής ιδεατών πινάκων.Η υλοποίηση επεκτείνεται για την ανάπτυξη δύο διαγνωστικών εργαλείων που εντοπίζουν προβλήματα σε συστήματα λογισμικού μέσω ερωτημάτων προς τα μεταδεδομένα που τα συστήματα φυλάσσουν στην κύρια μνήμη αναφορικά με τη λειτουργία τους. Η ως γλώσσα υλοποίησης πολλών συστημάτων λογισμικού είναι ιδανική για την εφαρμογή αυτής της ιδέας. Γι’ αυτό το σκοπό ενσωματώνουμε την υλοποίησή μας στον πυρήνα του Linux όπου εστιάζουμε στη συγχρονισμένη πρόσβαση στα δεδομένα και στην ακεραιότητα των αποτελεσμάτων των ερωτημάτων. Επίσης εφαρμόζουμε την προσέγγισή μας για να επεκτείνουμε τις διαγνωστικές ικανότητες του Valgrind, ένα σύστημα το οποίο ελέγχει τον τρόπο που εφαρμογές λογισμικού χρησιμοποιούν τη μνήμη.Η αξιολόγηση της προσέγγισής μας συνολικά περιλαμβάνει την ενσωμάτωση σε τρεις εφαρμογές λογισμικού της ++, στον πυρήνα του Linux, και στο Valgrind, όπου διενεργούμε και μια μελέτη αξιολόγησης χρηστών με φοιτητές. Για τη μελέτη συνδυάζουμε ποιοτική ανάλυση μέσω ερωτηματολογίου και ποσοτική ανάλυση μέσω μετρήσεων κώδικα. Οι μετρήσεις στις ++ εφαρμογές ανάμεσα σε Ýؽ ερωτήματα και αντίστοιχα ερωτήματα εκφρασμένα στη ++ δείχνουν ότι η Ýؽ σε συνδυασμό με τη σχεσιακή μας αναπαράσταση παρέχει ανώτερη εκφραστικότητα. Το ίδιο συμβαίνει όταν συγκρίνουμε την προσέγγισή μας με την ίδια την Ýؽ έχοντας εισάγει τα δεδομένα στη σχεσιακή βάση δεδομένων MyÝؽ. Η αποδοτικότητα της προσέγγισής μας είναι χειρότερη αυτής των ερωτημάτων ++ και καλύτερη αυτής των ερωτημάτων Ýؽ εκτελεσμένων στη MyÝؽ. Τα ερωτήματα με την προσέγγισή μας χρειάζονται το διπλάσιο χρόνο για να εκτελεστούν σε σύγκριση με τη ++ ανεξάρτητα από το μεγέθος του προβλήματος. Τα ερωτήματα Ýؽ στη MyÝؽ απαιτούν διπλάσιο, τριπλάσιο, ή και παραπάνω χρόνο για την εκτέλεσή τους σε σχέση με τη δική μας προσέγγιση.Στο πλαίσιο του πυρήνα του Linux όπου η σχεσιακή μας διεπαφή λειτουργεί ως διαγνωστικό εργαλείο βρίσκουμε αληθινά προβλήματα εκτελώντας Ýؽ ερωτήματα προς τις δομές δεδομένων του συστήματος. Η πρόσβαση σε αρχεία χωρίς τα κατάλληλα δικαιώματα, η μη εξουσιοδοτημένη εκτέλεση διεργασιών, ο εντοπισμός δυαδικών αρχείων που χρησιμεύουν στη φόρτωση διεργασιών αλλά δε χρησιμοποιούνται από καμία, και η εκτέλεση κλήσεων συστήματος από επεξεργαστές που ανήκουν σε ένα ιδεατό μηχάνημα είναι τα προβλήματα ασφάλειας που εντοπίζουμε. Επίσης δείχνουμε ερωτήματα που συνδυάζουν μετρικές από διαφορετικά υποσυστήματα, όπως σελίδες στη μνήμη, αρχεία στο δίσκο, δραστηριότητα επεξεργαστή, και δικτυακές μεταφορές δεδομένων, τα οποία μπορούν να βοηθήσουν στον εντοπισμό προβλημάτων απόδοσης. Η μέτρηση του χρόνου επεξεργασίας των ερωτημάτων και το βάρος που προσθέτουν στο σύστημα ενθαρρύνουν τη χρήση του εργαλείου μας.Το διαγνωστικό εργαλείο που αναπτύξαμε πάνω στο Valgrind εντοπίζει προβλήματα, επιπρόσθετα αυτών που βρίσκει το Valgrind, μέσω της χρήσης Ýؽ ερωτημάτων στα συλλεγμένα μεταδεδομένα της εφαρμογής που ελέγχεται. Το bzip2 για παράδειγμα σπαταλά 900» μνήμης όπου όλα τα κελιά είναι συνεχόμενα στην ίδια περιοχή. Αυτό το μέγεθος ισοδυναμεί με το 12% της συνολικής μνήμης που χρειάζεται η εφαρμογή για να λειτουργήσει. Επίσης από ερωτήματα πάνω στο γράφο δυναμικών κλήσεων συναρτήσεων που σχηματίζεται κατά την εκτέλεση μιας εφαρμογής διαπιστώνουμε την ύπαρξη κρίσιμου από πλευράς απόδοσης κώδικα που βρίσκεται στη βιβλιοθήκη glibc και χρησιμοποιείται ευρέως από τα εργαλεία Unix sort και uniq. Η εν λόγω βελτιστοποίηση υλοποιήθηκε από την ομάδα ανάπτυξης της βιβλιοθήκης σε επόμενη έκδοση χωρίς δική μας παρέμβαση. Τέλος, στο πείραμα με τους φοιτητές η μια ομάδα εκφράζει εργασίες ανάλυσης με ερωτήματαÝؽ και η άλλη με κώδικα Python. Τα αποτελέσματα δείχνουν ότι ο χρόνος που απαιτείται για την έκφραση μιας εργασίας ανάλυσης είναι μικρότερος όταν χρησιμοποιείται Ýؽ. Αντίθετα δε σημειώνονται στατιστικά σημαντικές διαφορές στη χρησιμότητα, απόδοση, και εκφραστικότητα ανάμεσα στις δύο προσεγγίσεις παρόλο που η προσέγγισή μας έχει υψηλότερη αξιολόγηση. Στη διάσταση της χρηστικότητας οι αξιολογήσεις δεν κατέδειξαν ξεκάθαρο νικητή, όμως και οι δύο προσεγγίσεις πέτυχαν πολύ καλή αξιολόγηση. Η αξιολόγηση της απόδοσης του κώδικα που έγραψαν οι φοιτητές για τα ερωτήματα δείχνει ότι η ομάδα φοιτητών που χρησιμοποίησε Ýؽ είχε περισσότερες σωστές απαντήσεις σε μικρότερο χρόνο. Θεωρούμε αυτή τη μετρική ενδεικτική της χρησιμότητας της προσέγγισής μας έναντι της Python, η οποία επίσης χρησιμοποιείται ευρέως σε εργασίες ανάλυσης δεδομένων.Επίσης θεωρούμε το χρόνο που απαιτείται για τη έκφραση μιας εργασίας ανάλυσης παράμετρο χρηστικότητας.Οι προκλήσεις στην επεξεργασία των δεδομένων συνεχίζουν να αναδύονται με αμείωτο ρυθμό.Σε αυτό το περιβάλλον οι εφαρμογές λογισμικού απαιτούν λύσεις για την ανάλυση των δεδομένων των χρηστών αλλά και για την επίλυση προβλημάτων που αφορούν τις ίδιες. Η επεξεργασία των δεδομένων στην κύρια μνήμη μπορεί να φέρει σημαντικά οφέλη σε συνδυασμό με άλλες καινοτομίες. Σε αυτή την κατεύθυνση νέες αρχιτεκτονικές που οφελούν την αποδοτική επεξεργασία των δεδομένων μπορούν να παίξουν σημαντικό ρόλο. Ελπίζουμε ότι αυτή η διατριβή θα βοηθήσει στην αποδοτικότερη επεξεργασία και αποτελεσματικότερη ανάλυση των δεδομένων που προσδοκούν οι χρήστες.