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 <[email protected]> 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 > >
