Re: Lock-free databases

From: Joe Seigh <jseigh_01_at_xemaps.com>
Date: Wed, 09 Nov 2005 11:22:41 -0500
Message-ID: <EKSdnU7eErqBv-_enZ2dnUVZ_s-dnZ2d_at_comcast.com>


vc wrote:
> Joe Seigh wrote:
>

>>VC wrote:
>>
>>Lock-free techniques similar to the ones covered by their patents have
>>be used in operating system kernels for decades and those operating systems
>>weren't going around proclaiming they were lock-free.

>
>
> Since they "haven't provided any facts significant to anyone familiar
> with lock-free programming techniques", how can you claim that "
> Lock-free techniques similar to the ones covered by their patents have
> be used in operating system kernels for decades and those operating
> systems weren't going around proclaiming they were lock-free".
>
Because I used to be a mainframe kernel developer and implemented some of those lock-free algorithms. In fact I did an RCU implementation in the mid 80's.

>

>>In fact use of lock-free
>>techniques like RCU for significant performance benefits doesn't qualify
>>Linux as lock-free since it still has plenty of locks left over.

>
>
> So what ? Linux may have plenty of locks left over, but ANTS may not.
> You just do not know if ANTS has any locks, or if it has any left,
> whether the leftover is significant to make their claim false.

I never said their claims are false. I just expressed doubt since I have experience with lock-free algorithms. The burden of proof is on them as far as I'm concerned. If you want to believe their claims that's ok with me.

>

>>>
>>>>Unless
>>>>their bottlenecks are IPC related, I don't see how their lock-free
>>>>patented techniques would help performance.
>>>
>>>
>>>There is some evidence (
>>>http://www.cs.chalmers.se/~phs/TechnicalReports/SunT02_Noble.pdf ) that
>>>operations on lock-free data structures outperform similar lock-based
>>>implementations (without dragging IPC into the picture).
>>
>>Under certain conditions.  It helps if you have contention.  In non-contention
>>cases, regular locks are as fast or faster than lock-free based solutions.

>
>
> It may be true for RCU, but not true for other approaches to
> implementing lock-free data structures (you can easily find plenty of
> research results by googling for "performance" and "lock-free").
> Clearly, in some cases lock-based synchronization will outperform
> lock-free algorithms, no one claims otherwise.
>
>
>
>>Having stuff lock-free doesn't automatically make things run faster.

>
>
> Of course not. In fact, performance improvements with operations on
> lock-free structures is a recently new phenomenon. Implementating
> lock-free structures requires much more effort than the traditional
> locking approach. But the point is that, judging by many independent
> results, it's possible to achieve performance gain by using such
> structures. Taking into account those results, the ANTS claims that
> lock-free data structures improve performace have more credibility that
> your wholesale denial of their claims.

Well in that article cited earlier
http://www.it-director.com/article.php?articleid=12912 they claim to use a lot of techniques to get their performance, not just lock-free. They use in-memory, thread pooling, etc... That's a lot of variables and they haven't quantified how much benefit is gotten from each technique. They just compared their database against a conventional database, not another vendor's in-memory database. That's apples and oranges as far as I'm concerned and doesn't reallly tell me anything about how effective their lock-free techniques are. So when I ask how much benefit can be gotten from using lock-free techniques, saying ANTs claims to be lock-free doesn't provide me with any useful information.

When I test lock-free techniques, I test them against known lock based solutions and against other lock-free techniques. This isn't always done. It's easy to pick a worst case technique to compare your technique against and make it look good.

-- 
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software. 
Received on Wed Nov 09 2005 - 17:22:41 CET

Original text of this message