Consistency

S2Graph provide eventual consistency over multiple edges. Many graph database provide transaction to client and let client deal with contention. Instead of providing transaction, S2Graph handle contention internally.

Actually, currently S2Graph is providing ACD(from ACID), but eventual consistency(not strong).

Currently there is open discussion whether provide strong consistency by implementing own transaction manager(or using tephra)

following section will describe how S2Graph update edge to meet eventual consistency.

If there are multiple requests that need to mutate same snapshotEdge(from, to, label) concurrently, then S2Graph need to make sure consistency on related edges on these requests.

below figure explain when contention on edge level happen.

Why not use transaction all the time?

Titan and Tinkerpop provide transaction so users are responsible resolving contentions.

S2Graph is designed for resolving contentions behind the scene just like other eventual consistency storage system such as cassandra.

Following is our reason not to use transaction.

1. Contention is rare.

We found that the probability for contention is very low. Especially when graph is immutable, then there is no contention actually. Only concurrent modification on same edge, referenced by (from, to, label, direction), will be our problem.

take one more read request is too much cost, since our production requests consists of 95% of read, and 5% write.

even if resolving contention become costly, it was better to resolving contention on write request since contention rate on write request was below 0.1%.

2. Asyncronous

Transaction is great but if contention occur, it is user thread to block and resolve this. This reduced performance on application server since one thread is blocked until transaction finished.

S2Graph process request asyncronously on event-based manner. there is no user thread block on all mutation/retry logics that will be explained. they are completely asynchronous so S2Graph require less resource to provide consistent data than other blocking graph database such as Titan.