- From: Sandro Hawke <sandro@w3.org>
- Date: Sat, 07 Sep 2013 22:55:38 -0400
- To: public-ldp-patch@w3.org
I think there are two different ways to think about patching, related to concurrency. Here's my proposed terminology and some thoughts about them. This stuff is mostly orthogonal to all the Patch proposals I've seen, which are mostly about syntax, although it does argue for increased expressivity. This is not researched -- it's possible the distributed database literature sorted this out in 80s. My proposed work-around may be the same as Optimistic Concurrency Control; I haven't had the time to think that through, and it seems like I should send this now, rather than wait. A "rigid" patch is constructed knowing the exact triples in the resource that is being patched. If applied to a different set of triples, then incorrect results might be obtained. Therefore, rigid patches MUST use the HTTP "if-match" header, which tells the server to reject the patch if the triples have changed since the given etag. On getting an if-match error, clients may be able to create a new rigid patch and attempt to use it. However, if the triples keep changing, the client may keep getting if-match errors, and may never be able to patch the resource. For example, if client A is modifying the resource every 100ms and client B has an RTT of 110ms, client B will never be able to apply a rigid patch, even if the particular triples A and B are modifying/attempting-to-modify are different. If this hasn't been named already, we might call this the whack-a-mole failure mode. (you'll never hit the mole if it moves faster than human reaction time.) In contrast, a "blind" patch is constructed not knowing the exact triples in the resource being patched. It is designed so that for any valid state, applying the patch will produce its intended result. For example, if the resource state is { <a> <b> 37 } and a client wants to increment that value, it could use a rigid patch, assuming it changed infrequently enough. It could only use a blind patch if the patch language were sufficiently expressive, as in SPARQL Update: PREFIX test:<http://example.com/> DELETE { test:test01 test:count ?count } INSERT { test:test01 test:count ?newcount } WHERE { test:test01 test:count ?count . BIND ((?count + 1) AS ?newcount) } (Example thanks to Barry Norton, at http://answers.semanticweb.com/questions/17344/atomic-increment-with-sparql-update) A possible work-around: In order to help deal with the RTT problem on rigid patches, it may be useful to provide a mechanism similar to if-match, but with slightly relaxed semantics. Call it perhaps "if-non-conflicting". The semantics would be that the patch is to be done if and only if the resulting graph would be identical to the graph produced had the patch been applied at the given etag state and then all intervening changes done afterwards. For example, client B does a GET and sees { <a> <b> 1. <c> <d> 2. } with etag 0001. Then client A sends a patch: DELETE { <a> <b> 1 } INSERT { <a> <b> 2 }. Now B tries to send a patch: DELETE { <c> <d> 2 } INSERT { <c> <d> 3 }. If B sends that patch with "if-match: 0001" it will have to be rejected, since the resource state is different. But intuitively the patch ought to be acceptable, since A changed a different part of the graph. So we could have B send a header "if-non-conflicting: 0001", which makes the server do something like: (1) apply the patch and save the result as G1; (2) apply the patch to resource state 0001, then apply all the other patches that have been received since 0001 and save the results as G2. If G1 = G2, then accept the patch; if not, reject it. -- Sandro
Received on Sunday, 8 September 2013 02:55:46 UTC