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.

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.

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.

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.

Concurrency Control

Multi-version Concurrency Control (MVCC)

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

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.

Isolation Levels

Snapshot Isolation

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

Views

Not Supported

Query Compilation

Not Supported

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.

Data Model

Graph

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

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 Postings in memory without fetching things from disk.

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.

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.

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.

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.

Query Execution

Tuple-at-a-Time Model

Query Interface

GraphQL

Dgraph uses a variation of 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.