On Fri, Oct 16, 2015 at 1:04 AM, Yakov Zhdanov <[email protected]> wrote:
> Agree with Sam here - we also reduce network calls since we don't need to > notify for each failed tryLock, but only for cases when tx will definitely > loose. > I also like this approach. Deadlock-free transactions is a HUGE feature and I can't wait to blog about it. On top of that, it looks like it will be the fastest transactional mode as well. I think we should spend some time documenting the algorithm in detail, so users will have precise understanding on how it works. > > Thanks! > -- > Yakov Zhdanov, Director R&D > *GridGain Systems* > www.gridgain.com > > 2015-10-16 10:22 GMT+03:00 Semyon Boikov <[email protected]>: > > > > > > > The success ratio with ordered approach is naturally going to be > better. > > > However, I think the performance will suffer, because queues are > > generally > > > expensive. Have you tried comparing performance of the queue-based > > approach > > > vs. the try-lock one? > > > > > > I did not add any new queues and just use existing per-entry list of mvcc > > candidates, so ordered approach will definitely perform better than > > try-lock. > > > > On Fri, Oct 16, 2015 at 4:10 AM, Dmitriy Setrakyan < > [email protected]> > > wrote: > > > > > On Thu, Oct 15, 2015 at 12:00 AM, Semyon Boikov <[email protected]> > > > wrote: > > > > > > It seems there is better approach to resolve these conflicts to do not > > fail > > > > all conflicting transactions: > > > > - we should order all transactions by some attribute (e.g. all > > > transactions > > > > already have unique version) > > > > - transaction with greater order should always 'win' transaction with > > > lower > > > > order > > > > - per-entry queue with waiting transactions should be sorted by this > > > order > > > > - when transaction tries to acquire entry lock it is added in waiting > > > queue > > > > if queue is empty or last waiting transaction have lower order, > > otherwise > > > > transaction fails > > > > > > > > With this approach transaction lock assignment is ordered and > > > transactions > > > > with lower order never wait for transactions with greater order, so > > this > > > > algorithm should not cause deadlocks. > > > > > > > > I also created unit test simulating this algorithm and it did not > > reveal > > > > any issues. Also in this unit tests I measured percent of rollbacks > > when > > > > concurrent updates have lots of conflicts: with 'try-lock' approach > > > percent > > > > of rollbacks is ~80%, with new algorithm is ~1% (but of course with > > > > real-life test results can be different). > > > > > > > > > > The success ratio with ordered approach is naturally going to be > better. > > > However, I think the performance will suffer, because queues are > > generally > > > expensive. Have you tried comparing performance of the queue-based > > approach > > > vs. the try-lock one? > > > > > >
