My first thought is that this is working around an improper use of optimistic locking. If I have many concurrent writes to the child list of a node its not a read-mostly situation.

If the root and children map to a Order and OrderItems collection and a tx updates the Order.sum, its possible that sum written is inconsistent with the OrderItems and this would not be detected because the Order version has not updated beween initial read and the time the sum is written.

Yes it would, so a question that arises is what is being optimistically locked? Whether or not you want the tree to be treated as a consistently versioned object vs hierarchical data where each node should be versioned independently depends on what is being stored and how its being used.

Take the case of the cache being used as a second level cache for an entity that is mapped onto the cache using aop. How is a change to a leaf node going to be reflected in terms of the overall object dirty state? Such a graph certainly cannot have two txs write to different leaf nodes with two writes of the object to a db that results in a last commit wins mode to the db. If just the changed columns were written this actually would not be a conflicting concurrent writes, but if the full state was written back to the db it would be.

See below for email conversation with Manik by email on this topic

> Hi manik,
> Yes I agree and in an optimistic sense that is really to do with the
> validation stage. There are a few strategies that you can apply
> (principally forward and backward validation with merging to make
> things
> more flexible).
>
> So, one approach (which is to say these two threads both changed the
> parent - therefore one is rolledback).
>
> However, in validation we can take a slightly more permissive approach
> and say - is this particular node incompatible with the other
> transaction (with incompatible being defined in the code) - so if two
> children are put in under different keys perhaps this is not
> incompatible (although it can become very difficult to cover all bases
> here).
>
> The real problem I think is that because the structure is a tree
> and if
> there is a lot of nodes put in under the root node then this is a
> problem (lots of contention) - if the same contention was happening
> on a
> node much further down the branches then we might say that this is
> fine
> as the optimistic stuff is guaranteeing that the second change is
> rolled
> back as it has optimistically failed (the point of the optimistic
> stuff)
>
> We can look at some slightly more permissive strategies if you want (I
> even mention this in my roadmap docs that I sent along with the
> original
> code)
>
> Let me know what you think
>
> steve
>
>
> -----Original Message-----
> From: Manik Surtani
> To: Steve Woodcock
> Subject: Re: Opt locking - node versioning and merging
>
> Yes, the versioning and dirty marking does take place on the
> workspace node only, but on commit (after successful validation) this
> version is written back to the underlying node so that concurrent
> threads will be able to validate their workspace nodes when they
> commit.
>
> The problem is that parent nodes (which have no changes except that
> they have gained/lost child nodes) are being marked as dirty as well,
> and their version sget incremented on commit time. This only causes
> a problem if a parent has many children (imagine a tree 1-level deep,
> where all nodes are directly under the root). Completely beats the
> purpose of opt locking if every tx will need to roll back because the
> parent (root) is marked as modified just because a new node is added!
>
> Cheers,
> --

>
>
> On 19 Oct 2005, at 14:16, Steve Woodcock wrote:
>
>
>> Manik,
>> I am pretty sure that the versioning and the dirty marking all take
>> place in the workspace (on a wrapper of the real node - not the real
>> node)- the root node's version and state is only updated on commit
>> after
>> the validation has been run (at least that is how I remember it
>> working
>> ) - so I do not think the rollback is an issue as it only affects the
>> copies - not the real node
>>
>> So I am not sure the description is entirely accurate

I think that the versioning is actually a node level issue - not an overall tree level one.

It just happens to be a tree in this case but could easily be anything else - such as a Map or we could even (at a stretch) imagine a set of leaves under a parent to be roughly analogous to a table. In these cases the optimistic versions tend to apply at a row level rather than a table level.

I think an issue here is that we want the optimistic strategy (which is currently based on the traditional backward validation approach) to somehow work out the compatible operations on the same parent node (in a sense the locking method is not really relevant - the aim is that the operations should produce consistent results as if the operations were run in a serialized manner).

Therefore the addition of two nodes in a parent under different keys could be seen to be compatible (as would adding two rows to a table) - but something like the first tx removing a node which is later updated by a second tx would not be.

There is some existing research on this sort of conflict resolution and it bears some relation to the algorithms used in version control systems to provide merge and conflict detection functionality.

I suppose it depends on how far down this path (in a complexity sense) you want to go.

It makes sense when the nodes do correlate with rows. The disconnect is when the nodes correlate with columns as could be the case when mapping an entity using aop. In such a case couldn't we just say that a write to any subtree node should require an optimistic lock on the root? The problem would be how to identify such a subtree to the cache.

hmmm..... I am not sure I quite understand the analogy to columns. By columns are you suggesting that the same property of many objects are changed?
Surely an optimisitic version increase of the root node with any other node change assumes that the root node is always the root of all objects - which I assume not the case in the majority of cases (If I am mistaken as I am not as familiar with the AOP stuff - please correct me).

I think what we need to identify in the AOP case is the parent of the root of the object - not necessarily the whole tree (which may be what you are actually getting at) - in which case the issue of merging still becomes the same problem - i.e do we allow the changes to different properties of one object to be merged - as we are effectively treating it as a collection of properties - or do we say this subtree has to be changed as a whole - in which case the AOP code would require a mechanism to update all nodes that make up the object -

"steview" wrote:

I think what we need to identify in the AOP case is the parent of the root of the object - not necessarily the whole tree (which may be what you are actually getting at) - in which case the issue of merging still becomes the same problem - i.e do we allow the changes to different properties of one object to be merged - as we are effectively treating it as a collection of properties - or do we say this subtree has to be changed as a whole - in which case the AOP code would require a mechanism to update all nodes that make up the object

Or instead of maintaining the version on every node in the subtree, all nodes point to the root of the subtree and this is the only node used for the optimistic lock check.