Titan on the other hand is a transactional database system to handle large, multi-relational (labeled) graphs with heterogeneous properties. A Titan graph is constantly evolving (as in the posted benchmark). For graphs (unlike geo-spatial domains), applying space decomposition techniques first requires a metric space embedding which is a non-trivial and computationally expensive process. For changing graphs, this embedding will change as well making this very difficult to use in practice. The best approaches I know of for achieving locality therefore use adaptive graph partitioning techniques instead. However, for the types of OLTP workloads that Titan is optimized for, this would be overkill in the sense that the time spend on partitioning will likely exceed the time saved at runtime. At very large scale, it is most important for OLTP systems to focus on access path optimization based on the ACTUAL query load experienced by the system and not some perceived sense of locality based on connectedness. I published a paper a while ago suggesting one approach to do so: http://www.knowledgefrominformation.com/2010/08/01/cosi-clou... The Graph500 benchmark explicitly prohibits this optimization ("The first kernel constructs an undirected graph in a format usable by all subsequent kernels. No subsequent modifications are permitted to benefit specific kernels").
I was using Graph500 as a decently documented public example more than the only example. There are other problems based on real-world data in the trillion edge range that serve as "hello world" models for testing massively parallel graph algorithms. Directed and undirected, cyclic, and acyclic, properties and property-free. Semantic databases and entity analytics are popular test cases.
In the specific case of Graph500, the graph is significantly cyclic which creates coordination issues if you simply denormalize the data (e.g. replicating edges around a graph cut). Being able to do a massively parallel BFS from any vertex in the graph and producing the globally correct result without replicating edges means that you cannot know how to optimize the organization ahead of time. This was an intentional part of the benchmark design. The Graph 500 does not lend itself to optimizing for a particular set of adaptive graph cuts in any conventional sense; the algorithms used need to be general over the 64 randomized runs and that benchmark was designed to favor non-replicated edges when using massively parallel systems (the coordination costs of edge replicas will kill your performance). However, obviously the massively parallel systems are partitioning up the graph in some sense.
In the specific case of the work I did a couple years ago, the systems can ingest tens of millions of new edges per second concurrent with parallel queries (not serializable multi-statement transactions, obviously). The ingest structure can be identical to the structure against which ad hoc queries are run without any kind of query optimization. The fact that ingest rates that high are sustained effectively precludes dynamically reorganizing the data to satisfy particular queries more optimally. In truth, it could be made more optimal for batch-y type workloads (maybe 2-3x faster versus the dynamic version?) but the point was to be able to throw massive amounts of hardware at arbitrary graph data models rather than optimizing it for a specific query.
BTW, metric space embedding is non-trivial algorithmically but can also be computationally inexpensive. The Macbook Air I am using now can do tens of millions of those embedding operations per second on a single core for moderately complex spaces and data models. Maybe an order of magnitude or two slower if dealing with complex, non-Euclidean geometries. However, I also spent a couple years of computer science R&D developing the algorithms to make that fast. :-) I have been working in this particular area for a bit over half a decade now so my perspective takes some things for granted I think. There isn't just one problem you have to solve, there are actually several if you are starting from scratch.
Like I said, I didn't want to take anything away from Titan and true OLTP-oriented systems have their own complex problems, not the least of which is that they don't scale too far beyond a couple hundred compute nodes for the current state-of-the-art. Not my specialty. I work in a world of more basic consistency guarantees.
Cheers!
Are there any open source graph databases that are scalable in your opinion? Which one would you recommend?
I've done work in other algorithm areas where the situation is similar. It often costs millions of dollars to develop major computer science advances but the best way to recover that investment is to leverage it without publishing it. Reverse engineering a thoroughly obfuscated technology takes a lot longer than when someone publishes the blueprints.
I will add that a lot of these algorithms are not at all obvious until you understand how they work. While knowing something is possible helps, it still requires a fair amount of theoretical computer science cleverness.
Space decomposition structures take a metric space and decompose it using an invariant space partitioning function. The partition points are fixed regardless of data distribution, the only decision process is when to apply the partitioning function.
The two well-known examples in literature are quad-trees and distributed hash tables. These are both very simple, narrow examples of space decomposition structures in a universe of possible metric spaces and possible partitioning functions. Many parallel data problems can't be made to fit into the simple space decomposition structures computer scientists are familiar with.
When massively parallel machinery is the foundational assumption, every computational structure must be represented in terms of space decomposition primitives. Right now, most computer scientists treat space decomposition structures as dumb data buckets and are largely oblivious to their expressiveness. Most published parallel algorithm computer science is based on computational structures that will only sort of parallelize on sufficiently small systems.
This is very interesting. Is there an example of the expressiveness of spatial decomposition you could share?
For graph queries, linearity can be definitely achieved on parallel systems with tens of thousands of compute nodes using the state-of-the-art algorithms. However, Titan does not use any of those algorithms and will be very lucky to exhibit linearity at a couple dozen nodes. Not to take away from the implementation but people looking for a scalable graph database will not be satisfied with Titan.
As an aside, the best algorithms and data structures for doing massively parallel graph operations are not published but obviously exist. The fastest system in the Graph500 benchmark uses a half million cores on a trillion edge graph. That is a several order of magnitude gap between what the best open source systems can do and what systems developed by closed research organizations can do as published in public benchmarks.
(Disclosure: I invented one of the aforementioned families of massively parallel graph processing algorithms in 2009, and not the first. The published literature has not even caught up with the first generation of such algorithms. A significant portion of advanced computer science research is no longer published.)