I worked on implementing a backend for google cayley, the issue is the iterators abstract how a backend actually works so it becomes harder to optimise without introducing tighter coupling, also imho effort is better spent on more important things like high availability etc. I haven't touched it in a while so i can't speak re. its performance today.

I've never worked with Neo4j but it's a stable and matured product with numerous large scale deployments, enough said. :)

Could you elaborate? I was under the impression that Cayley supported MongoDB and LevelDB as backends:

http://google-opensource.blogspot.com/2014/06/cayley-graphs-...

yeah cayley supports numerous backends that do have replication such as mongodb and postgres or cockroach db. The issue being that a complex query consists of multiple stages like 'friends of friends of friends'. So if you're using a remote backend iterating over the result of a query then recursively making new queries results in performance that is at best poor.