Why Google needed to build a graph serving system

Hi all, author of Dgraph and the article here.

Glad to see this post trending on HN. I'm around if you want to ask any questions, and will share whatever I can about my experience with graphs and the decisions at Google.

Since leaving Google, I've built Dgraph [1]. It is open source, designed for horizontal scalability, ACID transactions and provides incredible performance for both reads and writes. And of course, it solves the join-depth problem as explained in the post. So, do check it out!

And do remember to give us a star on GitHub [1]. Your love helps other open source users give Dgraph a real shot in their companies with similar leadership struggles as I experienced at Google.

[1]: https://github.com/dgraph-io/dgraph

Thanks for writing this up! I worked with the Knowledge Graph as a contractor at Google in 2013. My manager had a neat idea for adding our own Schema and triples (actually quads) for a specific application.

It surprises me how many large companies do not have a ‘knowledge graph strategy’ while everyone is on board with machine learning (which is what I currently do, managing a machine learning team). I would argue that a high capacity, low query latency Knowledge Graph should be core infrastructure for most large companies and knowledge graphs and machine learning are complementary.

OOT, but the illustrations on their home page ( https://dgraph.io/ ) is veeery cute, you should check it out.

I've been using DGraph for quite a while now in a side project of mine.

I looked at a number of other graph dbs, and landed on dgraph for a few reasons.

a) I like the query language. It felt natural to me. That's just my opinion though. Other languages felt cumbersome, and I didn't feel like I was operating on a graph.

b) I needed write performance. I'd talked to colleagues about their experiences (I have some friends at graphy companies) and every time I asked "what about X graphdb? could it handle this write load?" the answer was "no, definitely not".

I chose dgraph and it's been working like champ. Support via slack has been solid, they're focusing on the right things (performance, correctness), and I have a lot of confidence in the future of the project.

This a really neat historical perspective, although I do find one detail odd:

>If you are sneering at the memory requirement, note that this was back in 2010. Most Google servers were maxed at 32GB.

As I recall, Nehalem EP (launched 2008 or 2009?) could handle in excess of 100GB per socket? Not cheap necessarily, but definitely still counted as "commodity hardware" for that era. I say this recalling that even my mid-tier workstation from then could handle 48GB (in that wonky era of triple-channel RAM), though I only had it loaded with 12GB. Then again I could see, if said servers in 2010 were at the end of a purchasing cycle from 2007 or so, that they were "maxed" at 32GB?

Anyway, my from-memory nitpick doesn't detract from the article's ultimate point, though: distribution was an obvious need that would only become more pressing.

Insightful article / ad. Maybe the problem with the idea is that in practice not many users want to do joins at arbitrary depths levels, e.g. "sort all the children of US presidents by height" is probably not a very common query needing a massively distributed architecture?

This reminded me of SQL.

> Say, you want to know [people in SF who eat sushi]....If an application external to a database was executing this, it would do one query to execute the first step. Then execute multiple queries (one query for each result), to figure out what each person eats, picking only those who eat sushi.

A query like that in SQL could also suffer from "a fan-out problem" and could get slow. It's often faster to put subqueries in the From clause than the Select. It's certainly faster than an app taking the rows of one query and sending new queries for each row, as many developers do. For example:

  select
      p.name,
      (
          select max(visit_date)
          from visits v
          where v.person = p.id
      ) as last_visit
  from people p
  where p.born < '1960-01-01'

can be slower than:

  select p.name, v.last_visit
  from people p
      join (
          select person, max(visit_date) as last_visit
          from visits
          group by person
      ) v on p.id = v.person
  where p.born < '1960-01-01' 

In the second example, you first form a new table through a subquery of the original. This is not what a new programmer would first try. The first example, with the subquery in the Select clause, is closer to the train of thought. Also you would guess that getting the last visit dates of each person is more efficient after you know who to look for (like, only the people born before 1960). But in my experience, it often hasn't been.

Therefore likewise with this San Francisco sushi query, I was thinking that if it were SQL then I would (1) get all people in San Francisco, (2) get all people who like sushi, and then (3) join them, to find their intersection. Lo and behold, I then read that it is the same solution in this humongous graph database:

> The concepts involved in Dgraph design were novel and solved the join-depth problem.... The first call would find all people who live in SF. The second call would send this list of people and intersect with all the people who eat sushi.

For the scalability side of graph, we've just started using Amazon Neptune RDF, and have been amazed that we can easily and very quickly run sparql queries on 2.6 billion triples on their smallest 2 core 15 gig machine. Incredible capacity.

I've been looking for an open source graph nosql style database that makes it easy to do gather-scatter on a GPU. It's been tough.

Plug: some people are working to fork/restart Blazegraph development, which is the database Amazon took to make Neptune. Its GPU features are missing, as they were originally kept proprietary. If you have any interest and know how, this could be an exciting project to contribute to!

https://github.com/blazegraph/database/issues/86

There is also Janusgraph which Google contributes to http://janusgraph.org

Slightly off topic, but while we're on the subject of graph databases: could anyone point me at some useful introductions to the subject? Thank you.

How does Dgraph compare in performance, features to something like Neo4j?

This was a great article, and I'm a competitor! :) Learned a lot about the history.

My one nit-pick is they say distributed joins are hard though. But they don't really justify it other than the assumption other engineers have come from a traditional DB background. It is not a hard problem if you try to solve it on your own though: You do the join on the client, incrementally (or debounced if necessary) as the data is streamed. This works very well at scale in production (TB/day) for our system.

We are using AWS Neptune in building our marketing analytics product. What I have realized is that it has best of both worlds, the querying power of SQL databases and schemaless functionality like nosql databases.