Concurrent query analytics on distributed graph systems

Abstract

Large-scale graph problems, such as shortest path finding or social media graph evaluations, are an important area in computer science. In recent years, important graph applications such as PowerGraph or PowerLyra lead to a shift of paradigms of distributed graph processing systems towards processing of multiple parallel queries rather than a single global graph algorithm. Queries usually have locality in graphs, i.e. involve only a subset of the graphs vertices. Suitable partitioning and query synchronization approaches can minimize communication overhead and query latency by exploiting this locality. Additionally, partitioning algorithms must be dynamic as the number and locality of queries can change over time. Existing graph processing systems are not optimized to exploit query locality or to adapt graph partitioning at runtime. In this thesis we present Q-Graph, an open source, multitenant graph analytics system with dynamic graph repartitioning. Q-Graph's query-aware partitioning algorithm Q-Cut performs adaptive graph partitioning at runtime. Compared to static partitioning strategies, Q-Cut can exploit runtime knowledge about query locality and workload to improve partitioning dynamically. Furthermore a case study with an implementation for the shortest path problem and point search queries is presented. We present evaluations showing the performance of Q-Graph and the effectiveness of Q-Cut. Measurements show that Q-Cut improves query processing performance by up to 60% and automatically adapts partitioning on changing query workload and locality, outperforming partitioning methods using domain knowledge.

Large-scale Graph Probleme, wie beispielsweise Kürzeste-Wege Suchen oder Social Media Evaluationen, sind ein wichtiger Bereich in der Informatik. In den letzten Jahren zeigen Graph Anwendungen wie PowerGraph oder PowerLyra einen Paradigmenwechsel von verteilten Graph Systemen hin zu parallelen Anfragen, statt der Verarbeitung einzelner, globaler Anfragen. Solche Anfragen besitzen üblicherweise eine Lokalität in der Graph Datenstruktur, d.h. sie betreffen nur einen Teilbereich der Knoten eines Graphs. Geeignete Ansätze zur Partitionierung können dies nutzen um den Kommunikationsaufwand zu reduzieren und die Anfragenlatenz zu minimieren. Außerdem müssen Partitionierungs Algorithmen dynamisch sein, da sich die Anzahl und Lokalität von Anfragen über die Zeit ändern kann. Existierende Graph Systeme sind nicht optimiert um Anfragen Lokalität zu berücksichtigen oder die Graph Partitionierung zur Laufzeit anzupassen. In dieser Arbeit stellen wir Q-Graph vor, ein Open Source Graph System zur Verarbeitung nebenläufiger Anfragen und dynamischer Graph Partitionierung. Q-Graphs anfragenbasierter Partitionierungs Algorithmus Q-Cut kann die Partitionierung zur Laufzeit anpassen. Im Vergleich zu statischen Partitionierungen können hierbei Laufzeitinformationen über Anfragen Lokalität und Arbeitslast einbezogen werden. Außerdem wird eine Implementierung für das Kürzeste-Wege Problem vorgestellt. Evaluationen zeigen die Leistungsfähigkeit von Q-Graph und die Effektivität von Q-Cut. Messungen zeigen, dass Q-Cut die Ausführungszeit von Anfragen um bis zu 60% verbessern kannund in der Lage ist, die Partitionierung an sich verändernde Anfragen Lokalität und Arbeitslast anzupassen. Q-Cut übertrifft dabei Methoden welche Domänenwissen zur Partitioninerung verwenden.