jackrabbit-oak-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Michael Dürig <mdue...@apache.org>
Subject Re: Avoiding conflicts (OAK-1717)
Date Tue, 29 Apr 2014 13:27:59 GMT
Hi Davide,

Sounds like an interesting idea. In fact, Tom and me discussed
something very similar during lunch.

In case of a "conflict" there would be multiple :next-xxx properties.
When the index is used and those are traversed, the "right" :next-xxx
property would need to be followed. At the same time the index could
be marked as "dirty" so an async process could pick it up for cleaning
at its convenience. We need to make sure this works for all types of
conflicts. I.e. traversal in the face of multiple :next pointers
doesn't accidentally drop a node. I don't think I have the full
picture here yet.

An alternative would be to change the linked list / skip list approach
and use an ordered tree instead. This should also be free of conflicts
and would also allow for skipping during traversal. As such trees
might become unbalanced we'd also need some background process, which
rebalances these trees. Rebalancing could occur on an as need basis:
whenever an unbalanced tree is discovered when using an index, a
balance operation would be scheduled.

Michael

On 29 April 2014 14:53, Davide Giannella <giannella.davide@gmail.com> wrote:
> Thank you all for the support and feedbacks.
>
> In the aim of find a structure that avoid conflicts I was thinking is to
> generate a "cluster-node-unique" :next
> property. Something like
>
>     :next-System.nanoTime()-new Random(System.nanoTime()).nextLong()
>
> by the fact that we're going to generate this one once in a while it
> should not affect the performance too much by the usage of nanoTime.
>
> So we should have in the end a list that looks something like
>
> n0: {
>     :next = ,
>     :next-34567-4567 =,
>     :next-76543-6543 =,
>     :next-...
> }
>
> this should definitely avoid any concurrency.
>
> But it definitely has to be merged. So it comes an async process that
> runs on a single node (like the async index) in charge of touching the
> :next and in the future generate all the lanes of the skip list.
>
> What I would like to happen is something like: hey node A don't use any
> longer the unique "4568-789" as I'm going to merge it for you. Then node
> A generate a new ID and keep going. Once merged the async process will
> delete the no longer used unique-id.
>
> Other than the overall complexity of the algorithm I'm not sure on how
> to achieve this message.
>
> Any hints, ideas?
>
> Thank you
> Davide
>
>

Mime
View raw message