mutation mechanism

For Strong consistencyLevel label, S2Graph use read-modify-write mechanism for every requests. Every request has timestamp field that is used as version internally, and S2Graph validate and build Mutations based on this version.

To process and store a request into Storage, S2Graph do following thing.

1. read old state for request edge.
2. merge old state with request edge and build Mutations.
3. actually apply Mutations into storage.

This read-modify-write require only one thread can write into storage and S2Graph use optimistic concurrency control which never acquire lock on read time, but resolving conflict on write time(on step 3).

S2Graph use CompareAndSet atomic operation that storage engine provide(Currently main storage engine is HBase).

Mutations is collection of data that need to be changed at storage if current request edge is applied into storage correctly. S2Graph use Mutations to backtrack into edges that are sorted by their index property values.

1. old edges to delete.
2. new edges to insert.
3. degree to increment/decrement.
4. new state on vertex pair.

Let's see how S2Graph build this Mutations.

Examples

Let`s say user created following edge already.

curl -XPOST localhost:9000/graphs/edges/insert -H 'Content-Type: Application/json' -d '
{
    "timestamp": 10,
    "from": "1",
    "to": "A",
    "label": "friend",
    "props": {
        "p1": 10,
        "p2": "x",
        "p4": -1
    }
}
'

now use want to update same edge with following request.

curl -XPOST localhost:9000/graphs/edges/update -H 'Content-Type: Application/json' -d '
{
    "timestamp": 11,
    "from": "1",
    "to": "A",
    "label": "friend",
    "props": {
        "p1": 20,
        "p2": "y",
        "p3": 100
    }
}
'

note that update request has large version(timestamp is 11 over 10).

after read SnapshotEdge following state is available.

now S2Graph merge old state with request's state and build new state.

Based on this old state, request state, and new state, S2Graph can decide which previous edges need to be deleted and which new edges need to be inserted. Also if it is update, then there is no need to increment degree so degree mutation would be empty. finally new state need to be stored into storage so next request can yield correct state based on it.

Since every request goes through read-modify-write process, S2Graph can decide what to drop or what to apply based on old state stored in SnapshotEdge.

Reverse order Example

in above example, update request may deliver into S2Graph before initial insert request.

natural event order
insert(t10) -> update(t11)

event delivered in reversed order
update(t11) -> insert(t10)

go back to our state table, then this time old is update and request is insert since update is delivered prior.

Note that most of old state wins over request's state since old version is larger than request's version.

If there is no changes on new state, then it means request can be safely dropped out and S2Graph decide which request drop or apply based on comparison between old state version and new state version.

Note that this time the final state is same with previous case.

Conculusion

above examples show that S2Graph can yield same state regardless of deliver order of event. It is guaranteed that by request same set of requests multiple time, the final state would be same.

Next part will explain what is SnapshotEdge and will explain how S2Graph provide eventual consistency between multiple indexes and fast update/delete performance.