DGraph

Dgraph is a distributed graph database that supports GraphQL. It emphasizes concurrency in distributed environment by minimizing network calls.

History

In July 2015, Manish Rai Jain created Dgraph based on his previous experience at Google -- there he led a project to unite all data structures for serving web search with a backend graph system. The first version v0.1 was released in December 2015, with the goal offering an open source, native, and distributed graph database never changes since then. In 2020, Dgraph launched hosted Dgraph with Dgraph Cloud. The only native GraphQL graph database available on AWS, GCP, and Azure, Dgraph Cloud has three tiers. The free tier lets users get started and try out the service. The shared and dedicated tiers are ideal for app developers or companies. Thanks to the scalability of Dgraph, enterprises are using it with terabytes of data in production.

Query Interface

GraphQL

Dgraph uses a variation of [GraphQL](https://facebook.github.io/graphql/) (created by Facebook) called **DQL** as its query language because of GraphQL's graph-like query syntax, schema validation and subgraph shaped response. The difference is that **DQL** supports graph operations and has removed some inappropriate features considering graph database's special structure.

Concurrency Control

Multi-version Concurrency Control (MVCC)

Dgraph supports MVCC, Read Snapshots, and Distributed ACID transactions.

Logging

Logical Logging

Dgraph's logging scheme is close to logical logging. Every mutation is logged and then synced to disk via append-only log. Additionally, two layers of mutation responsible for replacing and addition/deletion respectively can log mutations in memory, allowing periodical garbage collection for dirty posting list via BadgerDB. This reduces the need for recreating the posting lists.

Joins

Hash Join

Dgraph's `PostingList` structure stores all `DirectedEdges` corresponding to an `Attribute` in the format of `Attribute: Entity -> sorted list of ValueId`, which already consists of all data needed for a join. Therefore, each RPC call to the cluster would result in only one join rather than multiple joins. Join operation is reduced to lookup rather than application layer.

Storage Model

Custom

Dgraph utilizes BadgerDB (an application library rather than a database) to help with key-value storage of posting lists on disk. However, all data handling still happens at Dgraph level rather than BadgerDB. BadgerDB functions as an interface of disk for Dgraph.

Isolation Levels

Snapshot Isolation

Transactions are based on Snapshot Isolation (not Serializable Snapshot Isolation), because conflicts are determined by writes (not reads).

Stored Procedures

Supported

Dgraph supports Persistent Queries. When a client uses persistent queries, the client only sends the hash of a query to the server. The server has a list of known hashes and uses the associated query accordingly.

Indexes

Inverted Index (Full Text) Log-Structured Merge Tree

Today we use Badger, an efficient and persistent key-value database we built that’s written in Go. Our blog covers our rationale for choosing Badger in “Why we choose Badger over RocksDB in Dgraph”. Today, Badger is used in Dgraph as well as many other projects.

Storage Architecture

Hybrid

BadgerDB library would decide how data are served out of memory, SSD or disk. In order to proceed processing, updates to posting lists can be stored in memory as an overlay over immutable `Posting list`. Two separate update layers are provided for replacing and addition/deletion respectively, which allows iteration over `Posting`s in memory without fetching things from disk.

Checkpoints

Non-Blocking Consistent

Every mutation upon hitting the database doesn’t immediately make it on disk via BadgerDB. We avoid re-generating the posting list too often, because all the postings need to be kept sorted, and it’s expensive. Instead, every mutation gets logged and synced to disk via append only log files called write-ahead logs. So, any acknowledged writes would always be on disk. This allows us to recover from a system crash, by replaying all the mutations since the last write to Posting List.

Foreign Keys

Supported

In contrast to foreign key in relational database, nodes in graph database don't possess properties. Foreign relationships are represented by *edges* and should not exist implicitly. In Dgraph, creating relationships on top of data is the only way to model the data.

Data Model

Graph

Dgraph is a horizontally scalable and distributed GraphQL database with a graph backend.

System Architecture

Shared-Nothing

Dgraph uses RAFT consensus algorithm for communication between servers. During each **term** (election cycle), voting is conducted to decide a single leader. Then there is unidirectional RPC communication from leader to followers, but they don't share disk naturally. Each server exposes a GRPC interface, which can then be called by the query processor to retrieve data. Clients must locate the cluster to interact with it. A client can randomly pick up any server in the cluster. If not picking a leader, the request should be rejected, and the leader information is passed along. The client can then re-route it's query to the leader.

Query Compilation

Not Supported

Compression

Delta Encoding Bitmap Encoding

Dgraph Alpha lets you configure the compression of data on disk using the --badger superflag’s compression option. You can choose between the Snappy and Zstandard compression algorithms, or choose not to compress data on disk.

Storage Organization

Log-structured

We have built an efficient and persistent log structured merge (LSM) tree based key-value store, purely in Go language. It is based upon WiscKey paper included in USENIX FAST 2016. This design is highly SSD-optimized and separates keys from values to minimize I/O amplification; leveraging both the sequential and the random performance of SSDs.

DGraph Logo
Website

https://dgraph.io/

Source Code

https://github.com/dgraph-io/dgraph

Developer

DGraph Labs, Inc

Country of Origin

US

Start Year

2015

Project Type

Commercial, Open Source

Written in

Go

Supported languages

Go

Derived From

BadgerDB

Operating Systems

Linux, OS X

Licenses

Apache v2