I'm having an urge to write an implementation of this... NOW

using something like Redis VM and Redis Cluster would be pretty scaleable and fault tolerant for graph databases

or even something like flockdb, which is Twitter's distributed graph db built on top of MySQL