Oracle FAQ Your Portal to the Oracle Knowledge Grid

Home -> Community -> Usenet -> comp.databases.theory -> Re: Lock-free databases

Re: Lock-free databases

From: vc <>
Date: 9 Nov 2005 08:45:21 -0800
Message-ID: <>

Joe Seigh wrote:
> 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.

  1. How does your being familiar with some lock-free algorithms and having implemented others let you *know* what specific lock-free algorithms ANTs uses (unless you familiar with the patents in question in which case there is a contradiction with your other statement that they "haven't provided any facts significant to anyone familiar with lock-free programming techniques") ?
  2. For my own education, while I am aware that IBM/370 had the compare and swap instruction (as well as 'test and set') , what specific lock-free algorithms, other than multiprocessing support, were implemented in the mainframe kernel 20-30 years ago ?

> >
> >>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 (
> >>> ) 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
> 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.

Fair enough. Until they quantify the lock-free data structures performance impact, it's hard to say.

> 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.

No argument about that either.

> --
> Joe Seigh
> When you get lemons, you make lemonade.
> When you get hardware, you make software.
Received on Wed Nov 09 2005 - 10:45:21 CST

Original text of this message