Titan: A Highly Scalable, Distributed Graph Database

http://thinkaurelius.github.com/titan/

by d0ugal • 14 years ago

170 39 14 years ago

thinkaurelius.github.com

nchuhoai• 14 years ago

Interesting, does anyone know how this compares with the popular Neo4j Database?

norkakn2• 14 years ago

Each Neo4j node stores all of the data, and it doesn't scale write horizontally well.

OrientDB tries to scale writes (I'll be testing this in a few months), but still stores all of the data everywhere.

This looks like it shards the data automagically. If it works well, I might be able to bang on it a bit, but I'm guessing that it gives shit performance for complex graph questions.

okram5• 14 years ago

Titan exposes graph data over a machine cluster. It is an OLTP system that allows you to do local neighborhood graph traversals in sub-second time. For OLAP processing (e.g. global graph algorithms), Aurelius will be releasing two projects named Faunus and Fulgora in the coming months. These provide Hadoop connectivity and compressed in-memory representations of "graph slices." We will be publishing our talk slides tonight that discuss this eco-system of graph technologies. See http://titanbiggraphdata.eventbrite.com/

okram5• 14 years ago

Also, Aurelius will be posting a blog post in ~2 weeks where we will be simulating Twitter. We replay Twitter from day 1 to June 2009 and slam it with ~10,000 concurrent users writing/reading follows relationships, tweets, stream constructions -- ultimately growing (what we think will be) a 3 billion edge graph when the simulation is complete.

oacgnol• 14 years ago

Very interesting. Since it implements Blueprints, does it also have support for Furnace (graph algorithms)? If so, does this imply that graph processing is done on disk rather than in-memory? I am rather unfamiliar with Blueprints but I'm wondering how Titan implements that aspect.

joe_the_user• 14 years ago

Also,

What is interesting about a graph database relative to simple key-value database? Storing edges of a graph is trivial for a key-value store and so it seems like any key-value store could let store the basic graph structure?

Do graph databases support graphic-specific queries and indices?

netghost• 14 years ago

They seem to implement a variety of graph centric APIs. From a query standpoint, it's easier to use a graph database to do something like find all the people who share interests with someone (person <--> interest <--> person), or find all the grand children in a family tree.

Now whether or not Titan implements these performantly, I have no idea.

JPKab• 14 years ago

I can only answer for one advantage I specifically know of regarding graph DB's over key value: dynamic, mergeable schemas which enforce data integrity WITHIN the database rather than with code on top of it.

There are many, many people on HN who are much more knowledgeable than I am on graph DB's, and I sure as hell hope they answer on this question.

I'm curious if this supports the RDF, OWL, and SPARQL standards?

I'm a little tired of graph DB's that focus on scale, rather than speed and flexibility though. A good one to check out is Stardog. http://stardog.com/ I think it just went into 1.0.

philjohn2• 14 years ago

It looks like it's Gremlin only.

What triple stores have you looked at? 4store is performant, but doesn't support reasoning. There's also BigData and Virtuoso which support various levels of it, and Franz are apparently working on a clustered version of Allegrograph.

dkersten• 14 years ago

Sure you can easily store graphs in a KV store, but graph databases allow you to efficiently traverse the graph too. Look up how to traverse graph structures in hadoop for example - I was looking it up recently for something Im building and in the end I opted for using hadoop to filter, aggregate and format the raw data and then input the preprocessed data into graph databases (Im using orientdb at the moment) for traversal queries. I duplicate the data on multiple machines and use storm bolts to do geaph queries (so each storm bolt has its own local copy of the graph database). Seems to be working well so far and allows me to do realtime traversals (though inserts wait hadoop the next hadoop batch job). Seemed a lot easier than what Id have to do to efficiently process using hadoop.

mhluongo• 14 years ago

What's interesting about key-value databases? Storing keys and values in an RDBMS is trivial...

Graph databases are great for datasets where structure matters more than in a relational database and (way) more than in a K/V-store. When you're doing traversals of arbitrary depth, other technologies fall on their collective face.

pooriaazimi• 14 years ago

Read Neo4j's documentation [1](well, don't read; just gloss over it). You'll be blown away by how much it can do. I recommend looking at chapter 5. An example, with the actual query:

-----------

5.3.1. Co-Favorited Places - Users Who Like x Also Like y

Find places that people also like who favorite this place:

* Determine who has favorited place x.

* What else have they favorited that is not place x.

Query:

    START place=node:node_auto_index(name = "CoffeeShop1")
    MATCH place<-[:favorite]-person-[:favorite]->stuff
    RETURN stuff.name, count(*)
    ORDER BY count(*) DESC, stuff.name

-----------

[1]: PDF: http://docs.neo4j.org/pdf/neo4j-manual-milestone.pdf , online: http://docs.neo4j.org/chunked/milestone/

rjurney• 14 years ago

Storing graphs in a key/value store is trivial. Querying them is not. Gremlin is much more powerful than anything you can home bake.

petern• 14 years ago

Yes, all information models are basically isomorphic. However, Neo4j for instance maintains referential integrity along the relationships, making sure there will never be a relationships without start- or endnode. In a K/V store or document store, there are no guarantees that your IDs pointing to other objects are updated as you change, delete or move the target data. Also, the graph structure is maintained on dics, meaning you can direct pointers on the storage level even in non-cached scenarios, while in a K/V or Document store you need to recreate the graph in memory before being able to do anything with it.

As for special indexes and queries, look at things like http://docs.neo4j.org/chunked/snapshot/cypher-query-lang.htm... expressing patterns and walks in graphs.

You can combine index lookups in e.g. Redis, MongoDB or Lucene with the core graph engine.

See http://docs.neo4j.org/chunked/snapshot/index.html for docs.

/peter

PaulHoule• 14 years ago

Where's the SPARQL support?

okram5• 14 years ago

Titan currently does not have "edge indexing" and thus can not implement Blueprints' GraphSail interface [https://github.com/tinkerpop/blueprints/wiki/Sail-Ouplementa...]. If it did implement GraphSail, then SPARQL would be supported via the Sail SPARQL engine.

jandrewrogers4• 14 years ago

What makes this graph database "highly scalable, distributed"?

There are difficult theoretical computer science problems that effectively limit the parallelization/distribution of generalized graph operators. To achieve high scalability you have to solve these computer science problems first. If this design offers a novel solution to the longstanding computer science problem then kudos, but nothing at the site suggests this is the case.

Many graph databases have claimed high scalability and distributability but none of those claims have held up over time due to the aforementioned computer science problems. This may be a very nice graph database but I am skeptical of the claims of "highly scalable, distributed" unless there is evidence that it uses fundamentally new theoretical computer science to achieve that.

th0ma53• 14 years ago

You mean CAP theorem? http://en.wikipedia.org/wiki/CAP_theorem I imagine it is either the A or the P that gets to be the victim, but I'm not sure which in this case.

tptacek• 14 years ago

Worth a re-read: http://codahale.com/you-cant-sacrifice-partition-tolerance/

okram5• 14 years ago

See https://speakerdeck.com/u/okram/p/titan-the-rise-of-big-grap...

jandrewrogers4• 14 years ago

No, I am referring to the set of problems related to graph partitioning.

This is essentially the same underlying problem that is the source of why distributed NoSQL databases do not support join operations. In the case of NoSQL databases, they simply do not support joins because it is not a core operations. (Technically you can still do a join, it just has terrible scaling characteristics.)

The fundamental operation of graph databases are relational joins by another name, which means that graph databases have the same limitation on distribution that distributed NoSQL databases have on joins. However, unlike NoSQL databases it is their primary operation so they can't just not support it. Consequently, the only way to have a "graph database" that is massively distributable is to solve the same problem that prevents distributed databases from supporting joins.

cbsmith2• 14 years ago

You could have said the same thing about generalized distributed computing as well. Much like with MapReduce, the trick is to recognize that there is an 80% solution that works quite well (based around BSP):

http://kowshik.github.com/JPregel/pregel_paper.pdf

http://googleresearch.blogspot.com/2009/06/large-scale-graph...

The trick is not to build a generalized graph operator solution. It's to have a specialized graph operator solution, and then see how many solutions you can fit to the specialized graph operators. Turns out you can do a lot with a little.

jandrewrogers4• 14 years ago

Approaches like Pregel have been the canonical way of dealing with large graph problems for many years. Unfortunately, most interesting graph analytic problems do not fit into that model because the "graph-like" aspect is still limited to problem sizes that fit conventional algorithms.

For example, if you can reduce a trillion-edge graph analysis problem into a billion-edge graph plus some other stuff (usually materialized document structures) then you can fit that into something like Pregel. That is how almost all real-world graph analysis is done today.

But by doing so, you've lost the ability to do graph analysis on the other ~trillion edges for the sake of tractability in a narrow case. You can't do relationship analysis across the attached documents. There are many, many graph analytic problems that require a true graph that is orders of magnitude larger than what can be partitioned even after accounting for graph reduction techniques such as those used in Pregel.

The Holy Grail is still the ability to run ad hoc graph analytic queries against a massively distributed graph representation. There are no shortcuts around this for many interesting applications. Right now, we are limited to mere billions of edges for most practical purposes and all of the hacks and workarounds are designed to keep the number of true edges to around this number even when the data model is much larger.

bendemott• 14 years ago

Agreed, this is why our solution was to use Node.JS and achieve parallelism through eventually consistent independent data-stores separated on each physical web-server application instance, I'll gladly switch to a distributed centrally managed system when it becomes available.

okram5• 14 years ago

We are going to address alot of these questions in our presentation tonight. However, for the Hacker News crew that won't be there tonight, here is an early release of the Titan talk.

https://speakerdeck.com/u/okram/p/titan-the-rise-of-big-grap...

http://titanbiggraphdata.eventbrite.com/

Enjoy!, Marko.

hendler• 14 years ago

Great presentation.

benjaminRRR• 14 years ago

Also it appears like a great way to take speakerdeck down...

niho• 14 years ago

I don't want to spam this thread, but I feel I have to plug my personal pet project Related (https://github.com/sutajio/related), since it is, well.. yeah... "related" to the topic being discussed.

It can't do half of what Titan does and is a much, much simpler design. But it is fast, easy to use and works really well for 80% of the use cases you might have for a graph database on the web (social graphs, semantic web stuff, etc.)

moondowner2• 14 years ago

Anyone tried to use this with Spring?

moondowner2• 14 years ago

Why the downvote? Spring Data Neo4j [1] works excellent, it's pretty popular and I'm interested has anyone tried working with TITAN in a Spring project(probably using the Blueprints API).

[1] http://www.springsource.org/spring-data/neo4j

sravfeyn• 14 years ago

"Vertex-centric indices provide vertex-level querying to alleviate issues with the infamous super node problem"

Does that mean, for each vertex, is it's sub-graph indexed?!

Titan: A Highly Scalable, Distributed Graph Database

Related Stories