  Graph databases have become an increasingly common infrastructure component.
Yet existing systems either operate on offline snapshots, provide weak
consistency guarantees, or use expensive concurrency control techniques that
limit performance. In this paper, we introduce a new distributed graph
database, called Weaver, which enables efficient, transactional graph analyses
as well as strictly serializable ACID transactions on dynamic graphs. The key
insight that allows Weaver to combine strict serializability with horizontal
scalability and high performance is a novel request ordering mechanism called
refinable timestamps. This technique couples coarse-grained vector timestamps
with a fine-grained timeline oracle to pay the overhead of strong consistency
only when needed. Experiments show that Weaver enables a Bitcoin blockchain
explorer that is 8x faster than Blockchain.info, and achieves 12x higher
throughput than the Titan graph database on social network workloads and 4x
lower latency than GraphLab on offline graph traversal workloads.
