11 ms·
Why Google needed to build a graph serving system
- sandGorgon 8y agoThere is also Janusgraph which Google contributes to http://janusgraph.org http://janusgraph.org
- ddorian43 8y agoIf you don't do datastructures right, then it will suck on performance. Imagine doing a search-engine in a rdbms without special datastructures.
- sandGorgon 8y agojanusgraph is usually used with Cassandra. This is the schema - https://docs.janusgraph.org/latest/schema.html https://docs.janusgraph.org/latest/schema.html
- ddorian43 8y agoSee mrjn replies. You need native graph db.
- chao- 8y agoThis 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.
- orestes910 8y agoMy first guess would be that power consumption drove those decisions.
- shereadsthenews 8y agoThe hardware replacement cycle is much longer than you’ve implied. Servers I am building today will still be TCO-positive for 15 years. In 2010 Google data centers would still have been full of their first generation dual-socket Opteron machine.
- chao- 8y agoI will happily stand corrected, because I was only implying based on very limited awareness. I am only directly familiar with workstations, where I've seen replacements occur on the order of 4-7 years, not servers or entire datacenters. However, everything I read seemed reinforce an idea that servers follow a similar pattern. Maybe I was just wildly misinterpreting? With the relative stagnation in per-core performance since about 2010 I could easily see something built then expecting to last to 2025, power consumption improvements nonwithstanding.
- wiradikusuma 8y agoOOT, but the illustrations on their home page ( https://dgraph.io/ https://dgraph.io/ ) is veeery cute, you should check it out.
- saagarjha 8y agoIs that a skunk? Kind of an interesting choice…
- pletnes 8y agoBadger.
- mrjn 8y agoWe recently made this image, inspired by my favorite movie. It's licensed under CC-by-ND. https://twitter.com/dgraphlabs/status/1088516069852012544 https://twitter.com/dgraphlabs/status/1088516069852012544 Feel free to use it! :-)
- pvg 8y agoIt makes you wonder how the product handles mushroom and more importantly, snake.
- mrjn 8y agoBadger don't care! https://www.youtube.com/watch?v=4r7wHMg5Yjg https://www.youtube.com/watch?v=4r7wHMg5Yjg
- marknadal 8y agoThis 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.
- politician 8y agoThere are a variety of distributed join scheduling models to consider depending on the latency of the network and the size of the data sets. Techniques like Bloom filters used to accelerate joins by minimizing the data transmitted are novel to many developers. Layer in HA and transactions, and it becomes hard.
- geuszb 8y agoInsightful 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?
- yorwba 8y agoI suspect that although any given query that needs a join is rare, there is a long tail of many different such queries. Just having more than one predicate is enough, e.g. "weather in <city> during <event>" or any of the queries in footnote 2 of the article.
- mrjn 8y agoConsider [sort all comedy movies by rating]. Such queries happen on a daily basis on movie sites like IMDB or Rotten Tomatoes. The only way to avoid joins is when you specialize your data to a particular vertical. Therefore, your flat tables are then built to serve say movie data, and can avoid some joins. But, if you're building something spanning multiple verticals, like Knowledge Graph is, which houses movie data, celebrity data, music data, events, weather, flights, etc. Then building flat tables specific to each vertical's properties is almost impossible.
- geuszb 8y agoYes, you're right about the need for many flat tables specific to each vertical. However, if other aspects of these verticals need to be specific to the vertical anyway (for example, UI: weather for the week is presented differently than a list of movies and their ratings; or: data quality), then there's still a significant amount of eng work per vertical, so that data flattening step may not be the bottleneck in growing the number of verticals served...
- mrjn 8y agoThat was the exact issue Google found itself in. Every OneBox had their own backend, which meant many different teams were involved in running and maintaining them. Now, with the graph serving system in place, all they need to do is to slap a new UI for the vertical, while the backend remains the same. Of course, there's real effort involved in building a new UI for the vertical, but it's a lot smaller compared to building a whole stack for each vertical. Not to mention, just the movie vertical itself has many "types" of data. Movies, Actors, Directors, Producers, Cinematographers, etc. -- all of these have different properties. By the time one is done flattening all of these into relational tables, they've built a custom graph solution -- which is what happens repeatedly in companies.
- mark_l_watson 8y agoThanks 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.
- taherchhabra 8y agoSounds like a good Enterprise saas product idea
- pklee 8y agoThe beauty of RDF is it can support schema promiscuity i.e. you can have many schemas for your same data. You can do that with OWL. In typical graph databases you are fixed on nodes, properties and edges, but in RDF you can choose what should be node and properties arbitrarily. My issue with RDF has been performance works great for categorical, relationship heavy data, but not so much for numerical data.
- mark_l_watson 8y agoI am also a fan of RDF and OWL. My two ‘practical semantic web’ books (one in Common Lisp and one for Jave/Clojure/Scala) are now 8 years old, but you can get free PDFs from my web site. Those books badly need second editions, the material is interesting but outdated.
- gibsonf1 8y agoMark, are you up for helping with solid security for cl-solid? (The library now works with both Neptune and Allegrograph) https://github.com/gibsonf1/cl-solid https://github.com/gibsonf1/cl-solid - live use of cl-solid library here https://graphmetrix.net https://graphmetrix.net , sometimes very lively discussion of Solid here: https://gitter.im/solid/chat https://gitter.im/solid/chat (including Tim BL)
- Tharkun 8y agoSlightly 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.
- amirouche 8y agoLook at my Python graph database 0.8.1 is the last release with the vanilla graphdb API, after that it only expose a triple store https://github.com/amirouche/hoply/tree/fa77d31757c835688098f6138e1cda3ea40aa4c7 https://github.com/amirouche/hoply/tree/fa77d31757c835688098...
- mrjn 8y agoI'd suggest starting with https://docs.dgraph.io/get-started/ https://docs.dgraph.io/get-started/, and then going to https://tour.dgraph.io https://tour.dgraph.io. It gives you all you need to understand the query language (based on GraphQL) and get you up to speed building your first app on a graph DB.
- staticassertion 8y agoI'll echo this - I learned about graph databases using DGraph.
- agumonkey 8y agohttps://archive.fo/IsWTe https://archive.fo/IsWTe
- bufferoverflow 8y agoThank you. That page freezes Chrome, ironically.
- gibsonf1 8y agoFor 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.
- macawfish 8y agoFYI, Neptune is based on Blazegraph. Amazon's acquisition of Blazegraph halted the database's open development. I'm sure they would welcome interested contributors: https://github.com/blazegraph/database/issues/86 https://github.com/blazegraph/database/issues/86
- gibsonf1 8y agoI actually found out about Neptune through finding out about Blazegraph. Do you know what's happening with the Blazegraph project now? Just followed your link and saw this comment from one of the original authors in Jan: https://github.com/blazegraph/database/issues/86#issuecomment-454854244 https://github.com/blazegraph/database/issues/86#issuecommen... Since Amazon is effectively selling machine time to run Neptune with no cost for the db, wouldn't it be excellent if the original author and team continued to contribute to Blazegraph. I'm not sure if the linked note is a potential nod in that direction or not. (We have customers that also want to have on-prem deployments, which you obviously can't do with Neptune)
- mrjn 8y agoAs others mention, Neptune is based on Blazegraph. It is a layer on top of Amazon Aurora and has the typical graph layer issues I mention my blog post (in particular the join depth problem). When Neptune was launched, I wrote another article critiquing its design. Worth a read: https://blog.dgraph.io/post/neptune/ https://blog.dgraph.io/post/neptune/
- pbowyer 8y agoI'd missed the announcement of Neptune, so thanks for alerting me. Have you reviewed the Microsoft Azure Cosmos DB, with its graph access layer?
- taherchhabra 8y agoWe 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.
- macawfish 8y agoWhenever I read mention of Neptune, I feel obligated to mention Blazegraph, which Amazon based Neptune on. As I've shamelessly advertised elsewhere in these comments, Blazegraph is in the early stages of a fork and/or reboot, as Amazon's acquisition severely hampered progress on the open source project. https://github.com/blazegraph/database/issues/86 https://github.com/blazegraph/database/issues/86
- mrjn 8y agoConsider Dgraph :-). https://blog.dgraph.io/post/neptune/ https://blog.dgraph.io/post/neptune/
- sexmachinebot 8y agoUnsubstantiated comment just to take OPs project down. Cmon, tell us why it's "the best" and what exactly it offers over Dgraph which makes it best.
- macawfish 8y agoI'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 https://github.com/blazegraph/database/issues/86
- mrjn 8y agoHi 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 https://github.com/dgraph-io/dgraph
- Game_Ender 8y agoI have some experience with Bazel, the open source version of Blaze, and I noticed that it's build graph implementation appears to be very memory hungry as well. Such that a few million lines of code already use 10-30GB of memory. Like you mentioned it requires the entire build graph to fit in memory on one machine. Do you know what sort of graph solution Blaze uses to handle 2 orders of magnitude more code, ie. manage 100's of millions of lines of code? I always assumed it was a distributed graph database, but your article seems to indicate something else.
- mrjn 8y agoGoogle's graph serving system is not generally available to be used by other teams, because its custom-built just for one purpose: to serve knowledge as part of web search infra. I think if Blaze is using some graph solution, it must be custom built.
- Xorlev 8y agoThat and the availability of machines with enough RAM to waste.
- shereadsthenews 8y agoThere are some crumbs that leak out, for example there are mentions of blaze’s “skygraph” feature in the bazel sources.
- deleted 8y ago[deleted]
- combatentropy 8y agoThis 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.
- staticassertion 8y agoI'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.
- mrjn 8y agoNot just you, a lot of Dgraph users appreciate the intuitive model of GraphQL+- (modification on GraphQL), and how it fits naturally with JSON and apps. When I started in 2015, I didn't imagine that our decision to use GraphQL would become such a major "feature." GraphQL has taken off like a wildfire, which was hard to imagine back in 2015 when it just launched in July 2015. In fact this year, we plan to align GraphQL+- even more with the official GraphQL spec. Stay tuned! re: write perf, it just got a whole lot better with 3 changes I made recently, and there're still a lot of room for optimization: https://github.com/dgraph-io/dgraph/commit/b7189935e6ec93aec04762321252b70f98466985 https://github.com/dgraph-io/dgraph/commit/b7189935e6ec93aec...
- staticassertion 8y agoLike I said, a big part of feeling confident in my choice to use DGraph is the direction - the improvements to the QL and performance, as well as the Jepsen tests, are exactly the work I want to see as a consumer. And that is one hell of an improvement. Nice work.
- subsaharancoder 8y agoHow does Dgraph compare in performance, features to something like Neo4j?
- mrjn 8y agoSlightly old post, but we did some benchmarks couple of years ago: https://blog.dgraph.io/post/benchmark-neo4j/ https://blog.dgraph.io/post/benchmark-neo4j/ We also get to hear benchmark conclusions from users who tried out Neo4j, Janus, Datastax DSE Graph, etc. They typically find Dgraph to be the best performing one. There's a comparison chart here: https://github.com/dgraph-io/dgraph#dgraph-compared-to-other-graph-dbs https://github.com/dgraph-io/dgraph#dgraph-compared-to-other...
- subsaharancoder 8y agoThank you for the comparisons. I think the approach you've taken with the documentation and the support out of the box for libraries in Go, Python etc is excellent, the playground is definitely a winner!!