VERNE : a vertex-centric SPARQL engine

Technologies such as RDF and SPARQL allow interacting with schema-less data modeled as a graph, where nodes represent entities and edges represent relationships between entities. These so formed datasets – often referred to as knowledge graphs – can become huge, posing challenges to their efficient processing. The scale of real-world RDF graphs can easily reach billions of vertices and trillions of edges, making them very demanding in terms of memory requirements. For this reason, centralized systems are not enough to efficiently support operations on RDF datasets. In recent years, Google has proposed a novel approach to distributed graph processing called Pregel. Pregel forces the developer to think like a vertex, i.e., to express a computation in terms of the operations that each vertex has to perform. This abstraction allows writing parallel algorithms that are naturally scalable and free of deadlocks. In this work, we present VERNE, a distributed SPARQL query engine built around the computational model offered by Pregel. The vertex- centric design of VERNE allows it to be scalable while focusing on performance and without sacrificing simplicity.

Tecnologie come RDF e SPARQL permettono di interagire agevol- mente con dati schema-less (senza uno schema rigido), modellati come un grafo in cui i vertici rappresentano entità e gli archi rappresentano relazioni tra entità. I dataset così formati – spesso chiamati knowledge graphs, grafi della conoscenza – possono facilmente diventare immensi, e rendere quindi la loro elaborazione molto onerosa in termini di risorse. La dimensione di alcuni dataset RDF attualmente esistenti può facilmente raggiungere e superare i milioni di vertici e miliardi di archi, rendendoli molto esigenti in termini di memoria richiesta. Per questo motivo, i sistemi centralizzati non sono in grado di supportare efficientemente le tipiche operazioni sui dataset RDF più grandi. Recentemente, Google ha presentato un nuovo approccio all’elaborazione distribuita sui grafi, a cui ha dato il nome di Pregel. Pregel obbliga lo sviluppatore a pensare come un vertice, cioè ad es- primere un algoritmo in termini di operazioni che ogni vertice deve compiere. Questa astrazione permette di scrivere algoritmi che sono intrinsecamente scalabili e che non presentano deadlock. Il modello vertex-centric introdotto da Pregel era già stato utilizzato per implementare risolutori di query SPARQL. Tuttavia, la maggior parte dei tentativi utilizzano GraphX, un componente per Apache Spark che implementa una variazione delle API di Pregel. Essendo Apache Spark un sistema complesso e general-purpose costruito per l’ecosistema basato sulla JVM, è naturale che non riesca ad offrire prestazioni ottimali per un carico di lavoro specifico. In questa tesi viene presentato VERNE, un risolutore di query SPARQL distribuito, costruito sul modello computazionale offerto da Pregel. Il design vertex-centric di VERNE e la sua implementazione personalizzata gli permettono di essere scalabile mantenendo alte le performance senza sacrificare la semplicità.