DGraph : A Graph Database

Guide : Prof. Krishna Sivalingam

17 May 2016

Acknowledgements

• Manish Rai Jain : Author of DGraph, Founder of DGraph Labs, ex-Google and ex-Quora Engineer

What is DGraph

• Open-source, Native, Low latency, High throughput Graph Database
• Distributed and scalable from v0.2
• Written in Go-lang

- Highly Concurrent (go-routines, channels)
- Performance similar to C++
- Compiled and does not require specific environments to run on

Motivation

• Usage of graph databases has grown significantly in a world where Big Data is now a common term.
• Applications in

- Social networks
- User behaviour analysis
- E-commerce recommendations
- Internet of things
- Medical and DNA research
- Search engines

Problem Statement

• Making an existing open-source graph database project DGraph to support distributed operation

- Support distributed data loading
- Support communication among the servers 
- Minimise the network calls made to process a query

Overview

• Graph data structures store objects and the relationships between them

• Relational databases : Large number of table joins to find the relationships. Compute time required increases as the number of results increases
• Graph databases store the relationships as first class citizens. Accessing connections is an efficient, constant-time operation

Background

• Flatbuffer
• RDF
• Sharding
• GraphQL

Flatbuffer

• Efficient cross-platform serialisation library created by Google for performance critical applications
• DGraph uses Flatbuffer for all the communication, storage and internal representation.
• Characteristics of Flatbuffer which make it very useful are:

- Access to serialised data without processing or unpacking
- Memory efficiency and speed
- Strongly typed

RDF

• Resource Description Framework
• DGraph's input is in RDF format
• Effective format to represent Subject-Predicate-Object relationships
• A sample RDF line

<Alice>    <friendof>    <Bob>    .

• A real world dataset would have millions if not billions of such lines which represent the connections

Sharding

• Partitioning of a dataset into multiple data chunks based on some mathematical function
• Some Types of sharding
• Range-based sharding : where the different ranges of the dataset are mapped to different shards
• Modulo sharding : where the key name is passed to a hash function to get an integer and this integer’s Modulo with the number of shards gives the shard number

GraphQL

• Query language and execution engine developed at Facebook
• Limited support. Lexing and parsing done by DGraph to convert into internal query representation
• By v1.0, most features of GraphQL would be supported
• Example : Query for genre of all the movies directed by Steven Spielberg

{
  me(_xid_: m.06pj8) {
    type.object.name.en
    film.director.film  {
      film.film.genre {
        type.object.name.en
      }
    }
  }
}

Centralised Version

Making it Distributed

• Split loader into 2 phases : UID Assigner and Loader

- UID Assigner: Allots a unique uint64 ID to each node
- Loader: Converts RDF file to Posting lists by using the UID map generated

• Enable communication among servers through RPC using TCP connection pools
• Batch writes which reduce the run-time of Loader

Example sharding

         Shard 1                            Shard 2
 <alice> <enemy> <bob6> .         <alice> <follows> <bob7> .
 <alice> <enemy> <bob1> .         <alice> <follows> <bob2> .
 <alice> <enemy> <bob3> .         <alice> <follows> <bob0> .
 <alice> <enemy> <bob4> .         <alice> <follows> <bob5> .
 
 
 -----------------------Posting List-------------------------
PS1
[enemy:alice] -> (bob1, bob3, bob4, bob6)

PS2
[follows:alice] -> (bob0, bob2, bob5, bob7)

Distributed Version

Query processing

• GraphQL query received. Parsed into internal query representation
• Make network calls to process the query (linearly proportional to number of predicates/attributes)

type SubGraph struct {
  Attr     string
  Children []*SubGraph
  query  []byte
  result []byte
}

Query processing

Subgraph format

SubGraph [result uid = "0xbb0de646eaf32b74"]
  |
Children
  |
  --> SubGraph [Attr = "type.object.name.en"]
  --> SubGraph [Attr = "film.director.film"]
         |
       Children
         |
         --> SubGraph [Attr = "film.film.genre"]
               |
             Children
               |
               --> SubGraph [Attr = "type.object.name.en"]

Demo

DGraph

Freebase Film Dataset

• Freebase is an online collection of structured data
• Includes information about 478,936 actors, 98,063 directors, films produced worldwide, genres, ratings
• Some examples of the predicates in Freebase film data are :

- type.object.name.en : Connects the object to its English name
- film.actor.film : Connects an actor to the film objects he has acted in

• Some examples of entries in the dataset are :

- <m.0102j2vq> <film.actor.film> <m.011kyqsq> .
- <m.050llt> <type.object.name> "Aishwarya Rai Bachchan"@hr .
- <m.0bxtg> <type.object.name> "Tom Hanks"@es .

Performance Analysis

• Were done on GCE (Google Compute Engine) instances

• Metrics

- Throughput
- Latency [mean, 50 and 95 percentile]

• Parameters

- Number of nodes in a cluster
- Number of parallel connections
- Number of cores in an instance

Queries

• The queries used to test the performance were about 478,936 Actors and 98,063 Directors
• For each request, a query and an entity are randomly chosen

The query about an actor obtains the list of all the movies that the actor has acted in
and looks like this:

{
    me ( _ x i d _ : XID ) {
        t y p e . o b j e c t . name . en
        film . actor . film {
            film . performance . film {
                t y p e . o b j e c t . name . en
            }
        }
    }
}

Queries

The query about a director obtains the genre of all the movies directed by that person
and looks like this:

{
    me ( _ x i d _ : XID ) {
        t y p e . o b j e c t . name . en
        film . director . film {
            film . film . genre {
                t y p e . o b j e c t . name . en
            }
        }
    }
}

Throughput Comparison

Throughput Comparison

Latency Comparison

Latency Comparison

Latency Comparison

Latency Comparison

Latency Comparison

Latency Comparison

Fine Grained Locks

• Locks are obtained over individual posting lists and not over the entire database
• Concurrent access to different posting lists could be made which increases the throughput
• When the queries are varied, the performance gets better

Results

• As the cumulative computational power that is available increases, the performance of the database is better
• The recommendation for running DGraph would be:

• Use as many cores as possible
• Have the servers geographically close-by so that network latency is reduced
• Larger sized RAMs are not a necessity in server but are important in case of
loader
• Distribute the data among servers and query them in a round-robin fashion for
greater throughput

Conclusions

• Performance of Distributed version is better under higher loads [A couple hundred parallel connections]
• A single machine can only handle so much
• Hence, horizontal scalability is important in modern databases and is supported through sharding

Further Work

• Moving shards across machines
• Fault tolerance
• Replication
• Supporting more GraphQL features

Thank you