DGraph – Scalable, Distributed, Low-Latency, High-Throughput Graph Database
dgraph.io
dgraph.io
Notably, there are quite a few omissions. DGraph and Cayley [1] being two of those. Interestingly, both are developed by Googlers. Cayley is used by Kythe.io [2], a Google project that kind of competes with srclib [3] by SourceGraph.
Cayley has native JavaScript interface, which makes it an interesting choice for Node JS based apps.
At work, we settled on TitanDB, primarily because it supports DynamoDB/Cassandra for storage and ElasticSearch. Most of the graph DBs rely on some storage engine or the other underneath-- Cayley supports LevelDB, for instance; whereas TitanDB supports BerkeleyDB apart from aforementioned DyanmoDB and Cassandra.
[0] https://docs.google.com/a/wikimedia.org/spreadsheets/d/1MXik...
[1] https://github.com/google/cayley
[2] https://kythe.io
DGraph, OTOH, is a native graph database. We do use RocksDB, but the data distribution and maintenance is done by us. It's optimized for decreasing the number of network calls, to keep them linear to the complexity of the query, not the number of results. This is of incredible value when you're running real time queries, serving results directly to end user. The query latency hence, isn't too affected by high fan out of intermediate results and should remain low; while providing high throughput.
In fact, the entire HN traffic is being served by one GCE n1-standard-4 instance right now, using all 4 cores really well :-).
I have questions, I'd be glad if you could answer them:
1. DGraph v0.2 isn't production ready?
2. DGraph API doc is missing?
3a. Does DGraph support bulk loading of RDFs only? No support for graphSON?
3b. Does DGraph support incremental loading of a Graph? Or just bulk loads?
4. Is 'distribution' achieved by maintaining a copy of entire Graph data across all instances? Or is data distributed too?
5. What's with the UID generation? Is to establish a partioning scheme?
3a. Yes, with the 2 phase loader. Only RDFs are supported right now, nothing else. https://github.com/dgraph-io/dgraph#distributed-bulk-data-lo...
3b. Yes, with mutations. https://github.com/dgraph-io/dgraph#queries-and-mutations
4. It's truly distributed. The data is actually sharded, with each shard containing part of the data and served by a separate instance. The bulk loader instructions generate 3 instances.
5. To keep the queries, data storage and data transfer efficient, we assign a uint64 ID to all entities. UID assignment is that operation.
A few Qs abt the storage layer:
DGraph supports replication too, in case a node fails...?
Given your description, I take that you've implemented a custom data distribution protocol on top of rocksdb? Do you have plans to extract this 'distributed rocksdb' out to its own implementation? How would something like this compare to actordb.com and/or rqlite?
Thx again.
DGraph would support high availability, which means all our shards would be replicated 3x across servers, so in case one server fails, the shards would still be available for querying and mutations. In addition, shard movements to other servers would happen so the replication factor remains the same. We aim to achieve this using (Etcd's) RAFT protocol, by version 0.4.
RocksDB is just a medium for us to have something between the database and disk. All the data arrangement, handling, movement etc. happens above RocksDB. So, no there's no "distributed rocksdb" here.
Also, the choice of BlazeGraph whiffed of politics. Wikidata (or at least one of the primary developers) seems to have been courted by the BlazeGraph people, to the point where Wikidata prematurely abandoned their research spreadsheet. This was at a time when there was hardly any public info/documentation about BlazeGraph, and its pedigree seemed completely unknown/untested.
I agree with your point about the Wikidata decision process. Some links about this if anyone is interested: https://news.ycombinator.com/item?id=11201943
BlazeGraph seems like a reasonable product (now). But I don't like seeing this "Wikidata evaluated products and chose Blazegraph" thing - they started an evaluation process.
Quickly looking at this project suggests it's on the OLTP side, not OLAP, so apples/oranges. Claiming more performance than a GPU compute engine would need some real benchmarking ;-)
This is definitely incorrect. Wikidata uses it exclusively for read/write queries.
The (GPU accelerated) graph processing in BlazeGraph is new, and it's pretty unclear to me if it actually does the (GraphX) style processing. The examples[1] are all query-based.
It does look interesting though!
That said, I'd be skeptical of a GPU system for being great at writes, and I'd be skeptical of a non-GPU one computing better than one on GPUs.
Some questions because I need something like this:
What does "distributed" mean in this context? Can the graph size be larger than the storage on a single node? If so, how is it partitioned (I think Titan was randomly partitioned)?
Has any thought been given to in-graph processing (PageRank etc)?
A typical RDF data is (subject, predicate, object). We shard the data based on predicates. So, all the RDFs corresponding to one predicate are on one server. This allows us to find, say lists of friends of X really quickly; with a single lookup.
I think PageRank should be relatively straightforward for DGraph, provided we have edges in the right direction. We don't automatically generate a reverse edge, it has to be provided, if needed for queries.
Wait, then you don't actually have relationships as first class citizens? Does every "thing" know what is connected to it? I mean, where do you draw the line between graph databases and an object database with one way links?
DGraph uses type schema to understand the relationships an entity can have. So, you can have an entity of type A, where A has relationships R1, R2, and R3. So, you can then deduce that A has relationships R1, R2, and R3. Of course, each entity can be of multiple types (for e.g. Tom Hanks is an actor and a director).
This approach is very scalable, because it avoids unnecessary scans over the distributed database to find all the relationships an entity can have. Rather, utilizing a schema to deduce such information; and then hitting the right servers to get the data.
This isn't unusual - it's somewhat analogous to the derived (inferred) relationship thing in RDF-style graph databases (eg, Sydney is-in Australia, Australia is-in Oceania, therefor Sydney is-in Oceania).
This sounds like a great idea, but in practice doesn't always work so well. You end up with an explosion of relations, some of which are completely useless.
I'm not opposed to this decision being a choice.
Not a huge fan of SPQRQL, but OTOH I don't know GraphQL at all so I can't comment sensibly on a comparison.
Are they a good choice for turn-by-turn navigation, and answering questions (given a traffic dataset) like: "What has been the quickest route between A and P, departing at 8am on a Monday morning?"
Finding the shortest route between A and B is on the roadmap. This would mean adding a weight to the edge. Navigation adds yet another interesting factor, which means we need to store multiple weights per edge, depending upon time of the day, day of the week, or day of the year etc. This would be an interesting challenge to solve; probably by v1.0.
Also if you are sharing on predicate you will end up in big trouble. Predicates in most RDF datasets are not at all evenly distributed, tending more towards extreme value distributions. e.g. in UniProt the most common predicate has 2,419,000,171 occurrences, the least 1!
Also if you are going to benchmark can I suggest the rather good LDBC ones[1]. Even if for marketing reasons you don't want them public they are good to show where you can improve.
It's hard to "prove" on a landing page, without going into design details, that you truly are those things. We do have a demo, with 21 million RDFs from real world data from Freebase, so you could play with the database, and get a feel for it.
We'll look into LDBC. Thanks for the pointer.
https://github.com/dgraph-io/dgraph/issues/1
In general Graph DBs are great when you have many "kinds" of things, which would require many many tables in traditional databases, and lots of interlinking. Those scenarios are ideal for Graphs, because many different kinds of things can be interrelated to each other easily, and be queried seamlessly. In other words, the schema for graphs is very fluid.
[1]: http://assimilationsystems.com/
[2]: http://linux-ha.org/source-doc/assimilation/html/index.html
It gets fun for us when we help visualize a full enterprise (hundreds of thousands of users, devices, apps..), and even more so when event data enters the picture. We do the former with our GPU tech, and push the latter to generic big data systems like Spark or Splunk that should already be in place before this becomes worthwhile.
You should try it out :)
Are you planning to add filtering, supported by indexes? Seems a bit useless for production use if you can't filter a query by predicate, or even sort/limit. You could layer something like Elasticsearch on top of it, but then you lose all the graph support.
Any thoughts on enforcing schemas?
We do filter by predicates, and have plans to do sort and limit, including count. DGraph is designed to accommodate all these use cases really well.
The idea is that you shouldn't need much on top of DGraph, because the query latency should be low; maybe Memcached. But, in the graph world, a single edge change can affect many queries, and so we've designed DGraph to provide low latency for arbitrarily complex queries.
The schemas would be enforced via GraphQL, i.e. the query language, not via the storage mechanism. This allows you to change the definition of types of entities, without changing the corresponding data. This is incredible for both backwards compatibility, and quick iterations.
Does DGraph use indexes to back the predicates? If so, do indexes have to be pre-declared? To explain, we layer ElasticSearch on top of our current document store because we don't want to manage an "index schema" manually; we have tons of different apps on top of the same document store, and they have all sorts of ad-hoc queries where it would simply be easier to (like ES does) index everything rather than require the app to declare a schema.
Not sure I understand your schema explanation. We're talking about schemas for validating document data, yes?
So, DGraph supports arbitrary complexity, so we try to not optimize for any particular query. Hence, you don't need to specify indices. We automatically generate posting lists, which store all the objects for a given (subject, predicate). For e.g., all the friends of X is stored in a single value, which is a sorted list of UIDs (uint64).
When we do sorting, we'll provide a way to specify which predicates to sort by. That'd be something that the user would have to provide; that we can't automatically deduce. For e.g., movie sorting by year of release etc.
Re: schema, have a look at GraphQL type system: https://facebook.github.io/graphql/#sec-Type-System This explains how types can be specified, and enforced while inputting data; and retrieving data.
Without value indexes, how would your data model optimize for queries like (year >= 1975) or (title like "%thing%)?
If I understand you correctly, the client would pass a schema along with each mutation? It's something we considered and quickly discarded for our own data layer, because it's not a good data model. Every client now has to know how to express its current schema, which puts too much of a burden on the client.
For example, we have a lot of microservices that all share the same data and schema, and to avoid boilerplate we'd have to build client glue (in 3 different languages) to let them share a schema.
The clients don't need to pass the schema on every mutation. DGraph could be provided the "schema" part of GraphQL when run, so all the servers have a common knowledge of what's the schema -- and the clients can assume that knowledge, without having to be repetitive.
So, no your clients in different languages wouldn't have to share any schema.