Conflict handling causes spurious observation events

[Michael Dürig <md...@apache.org>]

Hi,

Chetan discovered that in some cases spurious observation events would 
be created when to sessions save concurrently. In a nutshell the problem 
occurs since the current implementation of observation [1] expects a 
linear sequence of revisions (per cluster node). However on Root.commit 
there is a small race between rebasing and merging a branch: when 
another session saves inside this time frame, its branch will have the 
same base revision like that of the former session. In this case the 
sequence of revisions is effectively non linear.

This problem was acknowledged and discusses earlier already in the 
context of the commit hooks, which also might run against "the wrong" 
base revision, and which might cause validation of global constraints. 
The SegmentMk solves this by rebasing internally [2]. For the MongoMk 
this was so far not deemed a problem [3].

Non of these approaches solves the problem for observation however. For 
this case I currently see the following options:

1) Live with the spurious events
2) Tighten the contract of NodeStoreBranch.merge() to throw if a branch 
is not rebased so the caller can rebase again and retry [4]
3) Tighten the contract of NodeStoreBranch.merge() such that for the non 
trivial merge case it is obliged to do a merge commit first and commit 
the rest of the changes on top of that. The return value should then 
also include the merge conflict.

Michael

[1] 
https://issues.apache.org/jira/browse/OAK-775?focusedCommentId=13641416&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-13641416
[2] http://markmail.org/message/rdd5bljutuoendzl
[3] http://markmail.org/message/5vh6bk7ei32jgtbg
[4] 
http://wiki.apache.org/jackrabbit/Conflict%20handling%20through%20rebasing%20branches

Re: Conflict handling causes spurious observation events

[Michael Dürig <md...@apache.org>]

On 23.7.13 12:26, Chetan Mehrotra wrote:
> In discussion referred to in OAK-775 it was mentioned that the event
> processing would be pluggable. Is that still the case? If we make the
> merge method synchronized then it cannot be avoided through a
> different PostCommitHook implementation

No, not pluggable yet. Our priority is to get the most common use case 
covered first. If it turns out that we need different implementations, 
we need to make it pluggable then.

In relation to the synchronisation issue, the commit hooks are also 
affected by the implementation that might merge against "the wrong" base 
revision. See my initial mail of this thread. The current fix also 
covers this. If it turns out that synchronising this ways is to costly, 
we should try optimistic locking in the way SegmentMK does it.

Michael

Re: Conflict handling causes spurious observation events

[Chetan Mehrotra <ch...@gmail.com>]

> https://issues.apache.org/jira/browse/OAK-775). The compromise we came
> up with in OAK-775 is to maintain such information for local events
> (i.e. b1->h1 for node A and b1->h2 for node B), but not for events
> originating from the rest of the cluster (i.e. h1->h3 and h2->h3).

Okie now I understand. Missed reading that discussion as I was on
leave. So for external event we do not have to provide the user and
date information.

In discussion referred to in OAK-775 it was mentioned that the event
processing would be pluggable. Is that still the case? If we make the
merge method synchronized then it cannot be avoided through a
different PostCommitHook implementation

We can possibly persist only the metadata associated with tuple
(baseRevision,headRevision) and refer to that for providing
information regarding the metadata. This would avoid duplicating the
complete content. And with use of Mongo capped collections [1] can be
easily implemented

[1] http://docs.mongodb.org/manual/core/capped-collections/

Chetan Mehrotra


On Tue, Jul 23, 2013 at 3:30 PM, Jukka Zitting <ju...@gmail.com> wrote:
> Hi,
>
> On Tue, Jul 23, 2013 at 12:47 PM, Chetan Mehrotra
> <ch...@gmail.com> wrote:
>>> The end result in either case is a sequence of events from b1 to h3.
>>
>> If this is fine (and something which cannot be avoided) then cannot we
>
> In general that can't be avoided in a fully distributed case.
>
>> just make the NodeState comparable and avoid synchronizing the merge?
>> As that still allows us to see an ordered flow of changes.
>
> The problem why we can't just do as you suggest is that there's no way
> to (scalably) attach accurate user information (who committed this
> change) to merges like h3, which leads to backwards compatibility
> issues for observation (see
> https://issues.apache.org/jira/browse/OAK-775). The compromise we came
> up with in OAK-775 is to maintain such information for local events
> (i.e. b1->h1 for node A and b1->h2 for node B), but not for events
> originating from the rest of the cluster (i.e. h1->h3 and h2->h3).
>
> BR,
>
> Jukka Zitting

Re: Conflict handling causes spurious observation events

[Jukka Zitting <ju...@gmail.com>]

Hi,

On Tue, Jul 23, 2013 at 12:47 PM, Chetan Mehrotra
<ch...@gmail.com> wrote:
>> The end result in either case is a sequence of events from b1 to h3.
>
> If this is fine (and something which cannot be avoided) then cannot we

In general that can't be avoided in a fully distributed case.

> just make the NodeState comparable and avoid synchronizing the merge?
> As that still allows us to see an ordered flow of changes.

The problem why we can't just do as you suggest is that there's no way
to (scalably) attach accurate user information (who committed this
change) to merges like h3, which leads to backwards compatibility
issues for observation (see
https://issues.apache.org/jira/browse/OAK-775). The compromise we came
up with in OAK-775 is to maintain such information for local events
(i.e. b1->h1 for node A and b1->h2 for node B), but not for events
originating from the rest of the cluster (i.e. h1->h3 and h2->h3).

BR,

Jukka Zitting

Re: Conflict handling causes spurious observation events

[Chetan Mehrotra <ch...@gmail.com>]

> The end result in either case is a sequence of events from b1 to h3.

If this is fine (and something which cannot be avoided) then cannot we
just make the NodeState comparable and avoid synchronizing the merge?
As that still allows us to see an ordered flow of changes.

Chetan Mehrotra


On Tue, Jul 23, 2013 at 2:48 PM, Jukka Zitting <ju...@gmail.com> wrote:
> Hi,
>
> On Tue, Jul 23, 2013 at 11:57 AM, Chetan Mehrotra
> <ch...@gmail.com> wrote:
>> How this would work in a cluster mode. If two nodes in a cluster
>> perform commit with (base revision, head revision) [b1,h1] and [b1,h2]
>> then how would observation work?.
>
> Assuming h3 is the result of merging h1 and h2, then:
>
> * Node A would see local events b1->h1, followed by external events h1->h3.
> * Node B would see local events b1->h2, followed by external events h2->h3.
>
> The end result in either case is a sequence of events from b1 to h3.
>
> BR,
>
> Jukka Zitting

Re: Conflict handling causes spurious observation events

[Jukka Zitting <ju...@gmail.com>]

Hi,

On Tue, Jul 23, 2013 at 11:57 AM, Chetan Mehrotra
<ch...@gmail.com> wrote:
> How this would work in a cluster mode. If two nodes in a cluster
> perform commit with (base revision, head revision) [b1,h1] and [b1,h2]
> then how would observation work?.

Assuming h3 is the result of merging h1 and h2, then:

* Node A would see local events b1->h1, followed by external events h1->h3.
* Node B would see local events b1->h2, followed by external events h2->h3.

The end result in either case is a sequence of events from b1 to h3.

BR,

Jukka Zitting

Re: Conflict handling causes spurious observation events

[Michael Dürig <md...@apache.org>]

On 23.7.13 10:57, Chetan Mehrotra wrote:
> Its possible that for a series of changes like [b1,h1] ->[ b1,h2] ->
> [h1,h3] the observation logic miss out seeing in between state
> transition. But it would effectively see all the changes. Only changes
> which get negated between missed transition would not be observed. But
> I do not see a way that such losses can be avoided without going for a
> linear journal or serializing the complete commit sequences.

See my recent mail for how I think we can achieve serialisation by 
rebasing in NodeStoreBranch.merge(). This has said impact on session 
concurrency. As a further optimisation we can later try to do something 
similar like the SegmentMK, which tries optimistic locking first and 
falls back to optimistic locking if this fails. But let's go one step at 
a time.

Michael

Re: Conflict handling causes spurious observation events

[Chetan Mehrotra <ch...@gmail.com>]

>> The limitation would be on the set of concurrent
>> sessions for which we want to keep track of local commit information
>> for observation.

How this would work in a cluster mode. If two nodes in a cluster
perform commit with (base revision, head revision) [b1,h1] and [b1,h2]
then how would observation work?.

What if we make NodeState implement comparable and then while changing
the ChangeDispatcher.previousRoot do the change only if the new state
is *newer* than previous. Then we would not be seeing duplicate
events. We can do this for Segment and MongoMK as both refer to
linearly increasing recordId/revisionId. H2 MK is anyway single node
and it serializes the writes so it has to be managed through some
mechanism.

Its possible that for a series of changes like [b1,h1] ->[ b1,h2] ->
[h1,h3] the observation logic miss out seeing in between state
transition. But it would effectively see all the changes. Only changes
which get negated between missed transition would not be observed. But
I do not see a way that such losses can be avoided without going for a
linear journal or serializing the complete commit sequences.

regards
Chetan


On Mon, Jul 22, 2013 at 4:45 PM, Michael Dürig <mi...@gmail.com> wrote:
> On 22.7.13 12:48, Jukka Zitting wrote:
>> Hi,
>>
>> On Mon, Jul 22, 2013 at 1:35 PM, Michael Dürig <md...@apache.org> wrote:
>>> For other NodeStore implementations I currently don't see how to reuse the
>>> code from SegmentMK without changing the contract of the Microkernel.merge
>>> method. As long as that method does its own merge magic we need to prevent
>>> concurrent merges in order to avoid the race condition. This means we'd need
>>> to synchronise on the NodeStore instance as you mention. But AFAIR we
>>> explicitly wanted to avoid this for scalability reasons.
>>
>> Note that the extra synchronization here would only hurt single-node
>> concurrency, not horizontal scalability across cluster nodes. I.e. it
>> would still be possible for two cluster nodes (even two
>> repository/KernelNodeStore instances in the same JVM) to commit
>> concurrently. The limitation would be on the set of concurrent
>> sessions for which we want to keep track of local commit information
>> for observation.
>
> Right and for the latter case there is also the option of using
> SegmentMK, which doesn't suffer from this. For the Microkernel based
> implementation we can reconsider further optimisations if it turns out
> we need to improve per cluster node session concurrency.
>
> Going forward I will therefore:
> - move the post commit hook to NodeStoreBranch.merge,
> - leverage its rebasing capability in the case of SegementMK,
> - explicitly synchronise in the case of the MircorKernel based
> implementations.
>
> Michael
>
>>
>> BR,
>>
>> Jukka Zitting
>>

Re: Conflict handling causes spurious observation events

[Michael Dürig <mi...@gmail.com>]

On 22.7.13 12:48, Jukka Zitting wrote:
> Hi,
>
> On Mon, Jul 22, 2013 at 1:35 PM, Michael Dürig <md...@apache.org> wrote:
>> For other NodeStore implementations I currently don't see how to reuse the
>> code from SegmentMK without changing the contract of the Microkernel.merge
>> method. As long as that method does its own merge magic we need to prevent
>> concurrent merges in order to avoid the race condition. This means we'd need
>> to synchronise on the NodeStore instance as you mention. But AFAIR we
>> explicitly wanted to avoid this for scalability reasons.
>
> Note that the extra synchronization here would only hurt single-node
> concurrency, not horizontal scalability across cluster nodes. I.e. it
> would still be possible for two cluster nodes (even two
> repository/KernelNodeStore instances in the same JVM) to commit
> concurrently. The limitation would be on the set of concurrent
> sessions for which we want to keep track of local commit information
> for observation.

Right and for the latter case there is also the option of using
SegmentMK, which doesn't suffer from this. For the Microkernel based
implementation we can reconsider further optimisations if it turns out
we need to improve per cluster node session concurrency.

Going forward I will therefore:
- move the post commit hook to NodeStoreBranch.merge,
- leverage its rebasing capability in the case of SegementMK,
- explicitly synchronise in the case of the MircorKernel based
implementations.

Michael

>
> BR,
>
> Jukka Zitting
>

Re: Conflict handling causes spurious observation events

[Chetan Mehrotra <ch...@gmail.com>]

Hi Michael,

On Tue, Jul 23, 2013 at 2:59 PM, Michael Dürig <md...@apache.org> wrote:
> It is still possible to have two not branches merging against the same base
> revision. I.e. two branches that are not rebased on top of the current trunk
> and "merge internally". IFAICS it is also necessary for
> NodeStoreBranch.merge() to rebase the branch. I'll give this a try.

I am not sure it would work without going for a cluster level locking.
As the MK does not have any indication that other node is also
committing when it starts the merge it would still merge the changes
internally. So unless MongoMK does not perform a cluster level lock
such a situation cannot be avoided. We can probably make it do that
under some sort of "serialized" transaction mode which can be enabled
as per user requirements.

Chetan Mehrotra

Re: Conflict handling causes spurious observation events

[Michael Dürig <md...@apache.org>]

On 22.7.13 13:14, Michael Dürig wrote:
> - explicitly synchronise in the case of the MircorKernel based
> implementations.

As Chetan mentions in the other mail, synchronisation alone does not 
help here. It is still possible to have two not branches merging against 
the same base revision. I.e. two branches that are not rebased on top of 
the current trunk and "merge internally". IFAICS it is also necessary 
for NodeStoreBranch.merge() to rebase the branch. I'll give this a try.

Michael

Re: Conflict handling causes spurious observation events

[Michael Dürig <mi...@gmail.com>]

On 22.7.13 12:48, Jukka Zitting wrote:
> Hi,
>
> On Mon, Jul 22, 2013 at 1:35 PM, Michael Dürig <md...@apache.org> wrote:
>> For other NodeStore implementations I currently don't see how to reuse the
>> code from SegmentMK without changing the contract of the Microkernel.merge
>> method. As long as that method does its own merge magic we need to prevent
>> concurrent merges in order to avoid the race condition. This means we'd need
>> to synchronise on the NodeStore instance as you mention. But AFAIR we
>> explicitly wanted to avoid this for scalability reasons.
>
> Note that the extra synchronization here would only hurt single-node
> concurrency, not horizontal scalability across cluster nodes. I.e. it
> would still be possible for two cluster nodes (even two
> repository/KernelNodeStore instances in the same JVM) to commit
> concurrently. The limitation would be on the set of concurrent
> sessions for which we want to keep track of local commit information
> for observation.

Right and for the latter case there is also the option of using 
SegmentMK, which doesn't suffer from this. For the Microkernel based 
implementation we can reconsider further optimisations if it turns out 
we need to improve per cluster node session concurrency.

Going forward I will therefore:
- move the post commit hook to NodeStoreBranch.merge,
- leverage its rebasing capability in the case of SegementMK,
- explicitly synchronise in the case of the MircorKernel based 
implementations.

Michael

>
> BR,
>
> Jukka Zitting
>

Re: Conflict handling causes spurious observation events

[Jukka Zitting <ju...@gmail.com>]

Hi,

On Mon, Jul 22, 2013 at 1:35 PM, Michael Dürig <md...@apache.org> wrote:
> For other NodeStore implementations I currently don't see how to reuse the
> code from SegmentMK without changing the contract of the Microkernel.merge
> method. As long as that method does its own merge magic we need to prevent
> concurrent merges in order to avoid the race condition. This means we'd need
> to synchronise on the NodeStore instance as you mention. But AFAIR we
> explicitly wanted to avoid this for scalability reasons.

Note that the extra synchronization here would only hurt single-node
concurrency, not horizontal scalability across cluster nodes. I.e. it
would still be possible for two cluster nodes (even two
repository/KernelNodeStore instances in the same JVM) to commit
concurrently. The limitation would be on the set of concurrent
sessions for which we want to keep track of local commit information
for observation.

BR,

Jukka Zitting

Re: Conflict handling causes spurious observation events

[Michael Dürig <md...@apache.org>]

On 22.7.13 12:05, Jukka Zitting wrote:
> Hi,
>
> On Fri, Jul 19, 2013 at 7:00 PM, Michael Dürig <md...@apache.org> wrote:
>> Chetan discovered that in some cases spurious observation events would be
>> created when to sessions save concurrently. In a nutshell the problem occurs
>> since the current implementation of observation [1] expects a linear
>> sequence of revisions (per cluster node). However on Root.commit there is a
>> small race between rebasing and merging a branch: when another session saves
>> inside this time frame, its branch will have the same base revision like
>> that of the former session. In this case the sequence of revisions is
>> effectively non linear.
>
> If we move the logic from Root.commit() to NodeStoreBranch.merge(), we
> should be able to prevent concurrent updates either by leveraging the
> internal rebase logic in SegmentMK or by synchronizing on the
> associated NodeStore instance.

Yes I was thinking of something similar. For this to work we need to 
pass the post commit hook to NSB.merge().

I noticed that the SegmentMK handles this situation correctly. That is, 
it rebases before running the hooks and re-runs the hooks in case of a 
failure. It even incorporate some logic to fall back to pessimistic 
locking when optimistic locking fails.

So moving the post commit hook to NSB.merge() should solve the problem 
when using the SegmentMK.

For other NodeStore implementations I currently don't see how to reuse 
the code from SegmentMK without changing the contract of the 
Microkernel.merge method. As long as that method does its own merge 
magic we need to prevent concurrent merges in order to avoid the race 
condition. This means we'd need to synchronise on the NodeStore instance 
as you mention. But AFAIR we explicitly wanted to avoid this for 
scalability reasons.

Michael

>
> BR,
>
> Jukka Zitting
>

Re: Conflict handling causes spurious observation events

[Jukka Zitting <ju...@gmail.com>]

Hi,

On Fri, Jul 19, 2013 at 7:00 PM, Michael Dürig <md...@apache.org> wrote:
> Chetan discovered that in some cases spurious observation events would be
> created when to sessions save concurrently. In a nutshell the problem occurs
> since the current implementation of observation [1] expects a linear
> sequence of revisions (per cluster node). However on Root.commit there is a
> small race between rebasing and merging a branch: when another session saves
> inside this time frame, its branch will have the same base revision like
> that of the former session. In this case the sequence of revisions is
> effectively non linear.

If we move the logic from Root.commit() to NodeStoreBranch.merge(), we
should be able to prevent concurrent updates either by leveraging the
internal rebase logic in SegmentMK or by synchronizing on the
associated NodeStore instance.

BR,

Jukka Zitting