Patch Issue: Rigid vs Blind Patching

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