Getting performance out of a graph often depends on being able to express your query effectively. The last thing you want to do is plunk down a cursor on a node and have your client start wandering around the graph, following edges. All that back-and-forth chattiness is a non-starter network-wise and it gives the database engine essentially no chance to optimize the query. I've been favoring scripts that let me use free variables--like Prolog logic variables--to describe shapes in a graph and then let the database server find bindings that match. Like 'print a.name, b.name for a, b, x, y where a is_friend_of b and a is_friend_of x and b is friend_of y and not x is_friend_of y and x.city == y.city'
Maybe so. Orly has a somewhat leveldb-like component called a Repo which might slot in well. A Repo is a log-structured merge storage system that also provides indexing, access to previous values, and, most importantly, consistent reads and writes, even across multiple Repos. It also makes good use of resources (RAM, SSD, HDD) to optimize performance and cost. (Also working on letting it run on GPUs, for insanely high performance for people with the power and air conditioning budgets.)
A graph can do what a table can do and a lot more, but that's usually not the whole issue. In practice you need to consider things like speed, volume, scale, consistency, redundancy, computation, ad-hoc vs. planned operations, use of resources (disk, memory, CPU, GPU), etc. And as most NoSQL systems just aren't as mature as their table-based counterparts, you'll also have to factor in your tolerance for issues and general system crankiness. All that being said, some applications just cry out for graphs, particularly apps that involve items linked in pairs. Social apps (people linked by friendships), travel (places linked by flights), communications (people linked by messages), all of these can play hell with an SQL database but are naturals for graph databases.
I have. I'm on the team that's been developing it for the past four years. It's nice to see graph databases getting some popular traction at last. (I was into them before they were cool, of course.) I've only just started looking at Cayley but it looks like there are some significant differences between the projects. Orly is designed for high-speed, high-volume applications that need large-scale storage and consistent transactions. We're more OLTP than OLAP, which seems to be the way Cayley leans. Most graph systems tend toward analytic applications.