Request State Diagram

Basic CRUD request goes through following state. Request have following 4 status.

Note that if label`s consistencyLevel is weak, then S2Graph skip following complex process.

1. Trying(Status Code 0): Initial state.
2. Locked(Status Code 1): Current request succeed to acquire lock on snapshot Edge.
3. Updated(Status Code 2): All mutations(Delete old + Insert new + update degree) on IndexEdges succeed.
4. Done(Status Code 3): releasing lock(update snapshot edge as current edge applied) succeed, yeh.

Trying_to_Locked(0 -> 1)

There should two possible state with status code 0.

1. SnapshotEdge is not locked by any thread.
2. SnapshotEdge is locked by another thread.

If SnapshotEdge is not locked, then fine. The current thread can proceed. But when SnapshotEdge is locked, current thread need to retry after back off time, since another thread is changing same SnapshotEdge.

First thing to do with status code 0 is fetching old state of current request edge`s corresponding snapshot edge.

S2Graph store two extra information on snapshot edge to make sure only one thread mutate same snapshot edge at the same time.

1. Pending Edge: Note which request is mutating corresponding snapshot edge. This is owner of lock on SnapshotEdge.
2. LockedAt: Note when this pending mutation started.

Pending Edge on SnapshotEdge always set with lockedAt.

For short period time window(MaxBackOff time x Max Retry Number), only pending Edge can mutate this snapshot Edge.

After this time window, other request see this lock(pending edge + lockedAt) has been expired so they can process.

above figure describe contention.

The initial rating from Jone to McDonald's was 1.0.

Now 2 update requests on this rating between Jone and McDonald's to 3.0(Thread 0) and 5.0(Thread 1) are racing each other.

Both of Thread 0 and Thread 1 will fetch initial SnapshotEdge, which has rating 1.0.

Note that only one thread can success on acquire lock, since we are using compareAndSet operation from HBase.

This means each thread try to set their expected SnapshotEdge, which has each thread's request as PendingEdge and current timestamp as lockTs, using fetched SnapshotEdge as expected value.

Note that since compareAndSet guarantee atomicity, it is guaranteed that only one thread can success.

Now thread 0's status code becomes 1 from 0, while thread 1's status code remains as 0.

Thread 0 proceed, but Thread 1 will retry after back off time and start from fetch SnapshotEdge all over again.

Locked_to_Updated(1 -> 2)

Once current thread succeed to lock SnapshotEdge after compareAndSet, then following things need to be applied on index edges.

for index in label's indices:
    Delete old index edges on this index.
    Insert new index edges on this index.
    Update degree value on this index.

This is block of Transaction of S2Graph, which can be abstract into EdgeMutate class.

Based on fetched SnapshotEdge and current thread's request edges on same SnapshotEdge, S2Graph build all mutations based on EdgeMutate explained above.

It is very rare but possible that HBase RPC fail. Current thread can proceed from status code 1 to 2 only if all RPCs sent to HBase comes with success.

If any partial failure occur, then retry logic will trigger retry with status code 1.

With status code 1, we are guaranteed that only current thread can update this SnapshotEdge, so only firing RPCs to storage is retried, without fetching SnapshotEdge again. With same EdgeMutate class instance, RPCs to storage always be same so it is safe to re-send RPCs multiple times.

Note that multiple retry can fire same RPCs on same HBase cell, so it is important not to mess up state even if we fire same RPCs over and over on same HBase cell.

If all RPCs succeed, then this thread is done with updating phase, so move status code from 1 to 2, otherwise retry after back off time.

Updated_to_Done(2 -> 3)

Once all mutations are succeed, then current thread will try followings.

1. update SnapshotEdge by newSnapshotEdge.
2. remove PendingEdge.
3. remove LockedAt.

This newSnapshotEdge is built by merging current thread's request edge with fetched SnapshotEdge.

Let's say current thread's request edge is

{"rating": (3.0, t1)}

Fetched SnapshotEdge is

{"rating": (1.0, t0)}

Then merged newSnapshotEdge would be

{"rating": (3.0, t1)}

merge means build expected value with latest timestamp.

Thread that succeed up until status code 2, will fire RPC to overwrite SnapshotEdge by newSnapshotEdge without PendingEdge and LockedAt.

Now Thread 0 successfully updated it's IndexEdges and SnapshotEdge.

Note that at this point, query can see rating 3.0 as valid data, while request to update rating to 5.0 is retrying. This is why S2Graph consistency is eventual, not strong.

User can think IndexEdge is actual data layer and SnapshotEdge is our index(just like B-tree index on RDBMS).

Now since SnapshotEdge is now not locked by Thread 0, Thread 1 now can proceed from start.

Note that Thread 1 now sees correct rating value 3.0 that is updated by Thread 0, and decide what to do with it's request edge, which try to update rating value to 5.0.

If Thread 1's request has smaller version(timestamp on request edge), then S2Graph will drop smaller version and we are done.

Otherwise, Thread 1 will fetch SnapshotEdge and start from status code 0 and go same states as Thread 0.