Idempotency

S2Graph is designed to yield same eventual state regardless of order of requests client issued. let me explain problem first.

Note that S2Graph buffered requests in short period of time, then flush them to persistent layer.

This property which comes from asynchbase client, is great for performance but it could yield not expected state on storage, since there is no guarantee which request will be applied on to storage.

Problem

consider following requests on same edge(from, labe, to, direction).

Request Id Timestamp operation properties
1 t1 insert {"is_hidden": false}
2 t2 delete {}
3 t3 insert {"is_hidden": false, "weight": 10}
4 t4 update {"time": 1, "weight": -10}
5 t5 update {"is_blocked": true}

so final expected state on storage would be

5, t5, update, {"is_hidden": false, "weight": -10, "time": 1, "is_blocked": true}

if every requests comes in sequential order, then it is easy to guarantee final state.

but remember that S2Graph buffer incoming requests on local buffer and flush them, so if request 1,2,3 goes to server1, and request 4,5 goes to server2, which is very likely happen with L4, then there is no guarantee that server2 flush later than server1.

so let`s see one possibility.

request 5,1,3 goes to server1, and request 2, 4 goes to server2, and server1 flush, then server2 flush. actual order of requests to apply on storage would be

5 -> 1 -> 3 -> 2 -> 4
Request Id Timestamp operation properties server #
5 t5 update {"is_blocked": true} server1
1 t1 insert {"is_hidden": false} server1
3 t3 insert {"is_hidden": false, "weight": 10} server1
2 t2 delete {} server2
4 t4 update {"time": 1, "weight": -10} server2

even though above case, S2Graph should yield same final state.

Let`s see the details.

results matching ""

    No results matching ""