This paper introduces MELOGRAPH, a new system that exposes in the front-end a domain speci c language(DSL) for graph processing tasks and in the back-end identi es, ranks and generates source code for the top-N ranked engines. This approach lets the specialized MELOGRAPH be part of a more general multi-engine work ow optimizer. The candidate execution engines are chosen from the contemporaneous Big Data ecosystem: graph databases (e.g. Neo4j, TitanDB, OrientDB, Sparksee/DEX) and robust graph processing frameworks with Java API or packaged libraries of algorithms (e.g. Giraph, Okapi, Flink Gelly, Hama, Gremlin). As MELOGRAPH is work in progress, our current paper stresses upon the state of the art in this eld, provides a general architecture and some early implementation insights. Big Data ecosystem; multi-engine work ow; graph processing tasks
The multitude of frameworks and datastores in the Big Data ecosystem, with their di erent data models, libraries of implemented algorithms, available connectors and performance pro les, make it challenging to select the right tools when building a Big Data storage and processing architecture. Instead, one can bene t from the open-source licenses and community editions to set up a polyvalent architecture, with polyglot persistence and multiple processing engines.
On the data management side, with the emergence of
NoSQL datastores that usually complement relational
databases in the enterprise data architecture, there has been a
continuous interest for polyglot persistence (also referred to
as "multiparadigm data storage" [
This research topic remained an open challenge and few
robust solutions have been provided to this date. From
the industry, we cite Oracle Big Data SQL [
Perhaps even more challenging than with storing and
querying Big Data, developing complex analytics work ows needs
choosing among the plethora of candidate frameworks.
Several Big Data architecture patterns were promoted (e.g. [
A more mature approach to tackle the complexity of the
problem is to enhance a work ow manager with some
"intelligence", with the ability to decide between several
frameworks and to generate all necessary ETLs between the
chosen execution engines. Therefore nowadays an increasing
focus is put on designing multi-engine work ows [
A couple of publications present prototypes of systems
that address all these dimensions: QoX [
Except from these studies, few practical results of
integrating graph analytics in larger work ows are reported (e.g.
graph processing and NLP [
Finally, let us highlight some di erences between MELOGRAPH and the aforementioned systems. Compared to Aster's SQL-GR, MELOGRAPH not only aims to support a variety of data sources as input, but also to support various execution engines for each task; however MELOGRAPH's DSL doesn't make it embeddable in SQL queries. Compared to the other systems we innovate in the following aspects: 1) MELOGRAPH addresses speci c graph processing tasks, the suitability of storing data in a graph database prior to processing, possible optimizations in cascaded graph tasks; 2) MELOGRAPH generates Java source code on-the- y and does not treat operators as black boxes; 3) MELOGRAPH does not need any syntax validation since this is already enforced by the MPS editor (based on the DSL structure).
Before diving in the discussion about MELOGRAPH, let us rst depict some examples of work ows containing graph processing tasks. In a rst example, from the citations network in Computer Science we rstly retain a subgraph having in nodes only publications cited at least k times, then among them nd communities based on papers' co-citation and lastly evaluate how close is each community to a clique structure. In this case we have a sequence of three graph processing tasks in the work ow: a k-core graph processing task, a label propagation (or other epidemics-based identi cation of network structure) and nally aggregations to compute local clustering coe cients.
Secondly, a use case from the entertainment industry, where one can use YouTube Data API to extract the network of videos (retaining video's unique identi er, metadata about its channel/user, video title, description) and their relatedto relationships (a search for relatedToVideoId). Once the graph is obtained, two processing tasks are launched sequentially: a pattern matching query over the graph and a text semantic analysis over the resulting subgraphs video's description in order to extract entities (entity recognition task).
We end by presenting an example from [
The main components that build up the MELOGRAPH internals are: the DSL kneaded in a language workbench, the Candidate Solutions Assembler, the Ranker and the Solution Packager. Now let us present some details for each component.
Our domain speci c language, MELOGRAPHy, is designed and built to facilitate the de nition of graph processing tasks in a manner agnostic to the execution engine. In a rst stage, MELOGRAPHy supports functionality only based on the inventory of algorithms and queries available in the engines. However, in a second stage we want to extend the language to allow custom vertex-centric iterations using the Bulk Synchronous Parallel Model. We give some insights into our DSL in section 4 of the paper.
Based on the inventory of engines and on a set of patterns, the Candidate Solutions Assembler (CSA) builds the possible pipelines for solving the graph processing task. The CSA is concerned with the feasibility of the solution, not with its optimality, therefore some of the candidate solutions it produces may exhibit weak performance at runtime.
It is the role of the Ranker component to reward or to
penalize candidate solutions based on a set of heuristics.
Ideally, a cost-based model should be employed by the Ranker
to build its nal ranking of the candidate solutions; we'll
address this aspect in a future study. From the cost
perspective, for the moment we can anticipate adopting the
approach to treat execution engines as black boxes; this idea
already won consensus among both Big data management
researchers (e.g. " A 'black box' approach makes a lot more
sense when coping with disparate underlying engines" [
Finally, the Solution Packager prepares all the necessary shell scripts to launch in execution the various tools found in each of the top-N ranked candidate solutions. Therefore, the nal result of MELOGRAPH consists in a number of N folders in the local le system, each folder storing: the le containing the code source generated by the language workbench at compilation time; additional ETL scripts/programs to convert inputs to required format or to load data in a graph database; a driver script that orchestrates all the tools in that solution.
The next section presents how MELOGRAPH works, from receiving the input task to packaging a set of alternative solutions.
Before presenting the processing work ow of MELOGRAPH, in current version, let us rst provide some insights into basic MELOGRAPHy domain speci c language.
Regarding the DSL development environment we opted
for the JetBrains MPS metaprogramming system[
The root concept in MELOGRAPHy's structure is the T ask. For this concept, Figure 1 presents the three aforementioned concerns. Let us brie y make some comments.
Firstly, we highlight our choice to use the GraphAlgorithm concept to abstract both queries (e.g. pattern matching) and graph analytics (e.g. PageRank).
Secondly, in terms of data sources, the minimal information needed to build and to analyze the graph is its structure, which is given by the edges together with their incident vertices identi ers. This is why dataSourceEdgeInf o is mandatory, whereas dataSourceV ertexInf o is optional. We realize that this approach misses out the isolated nodes, but the user still has the option to load both the edges and the vertices data sets and hence include isolated vertices too. Besides eliminating unnecessary data loads, our approach has a more subtle bene t: it easily accommodates polyglot persistence, where vertex information is stored in a separate datastore than the information from which we build edges. One nal comment is that we take into consideration adding one more child to the T ask's aforementioned structure, with the scope of empowering the user to suggest his/her preferred execution engine.
Figure 2 depicts the structure of concepts that extend EdgeDataSourceT ype and V ertexDataSourceT ype for the speci c case of table data source (e.g. in Hive; but also in a relational database in Oracle or MySQL). In a brief parenthesis we comment that given a relational database table as data source, MELOGRAPH will automatically include Sqoop in all candidate solutions pipelines and thus the actual input to the graph algorithm will be the HDFS le obtained after loading the data. Thus, in the source code generation templates we use le input directly in such cases.
Let us also remark that except from the case of graph databases (where this information is native), for the rest of the data sources it is mandatory to specify the means of accessing edges' endpoints. In the illustrated case of a table data source locators are column names, similarly in the case of a CSV le locators are eld indices and in the case of HBase locators are fully quali ed columns names from some column family.
We advance now to the MELOGRAPH work ow. As shown in Figure 1, the use of mapping con gurations makes it possible to generate code for multiple engines at the same time according to a set of Java code templates developed by us. Details of this architecture are given in Figure 3.
Along with engines-speci c code, we generate the class M ELOGRAP Hclass that uses the functionality of all MELOGRAPH components discussed in the overview section of this paper. However, the ranking of the solutions can be obtained only when this Java program is run, consequently some of the heuristics need to be implemented in the modelto-model transformers, too.
With the data sources and the algorithm speci ed, MELOGRAPH's Candidate Solutions Assembler will emit all feasible pipelines to accomplish the task. This involves assembling tools based on prede ned patterns. Except from the data movement scripts that MELOGRAPH will eventually generate, we need to embed these patterns in the modelto-model transformer for each individual engine too. This approach is required by the fact that all source les are generated at once and need to be consistent among them. MELOGRAPH's Ranker will then rank the solutions and output a list of the top-N solutions.
The current state of the art in multi-engine processing work ows on Big Data displays increasing interest in tackling the practical challenges raised by the contemporaneous Big Data ecosystem. We join this emerging research movement and present in this paper the rst bricks that we've put in developing MELOGRAPH.
MELOGRAPH is specialized in graph processing tasks which are generally part of ampler work ows; however, the whole work ow needs to be developed in JetBrains MPS, too. In the design of MELOGRAPH we address heterogeneity at all levels, from the data sources, execution engines and runtime computing environment (through the heuristics used in ranking candidate solutions).