Re: Lock-free databases

From: vc <boston103_at_hotmail.com>
Date: 9 Nov 2005 12:29:42 -0800
Message-ID: <1131568182.611244.149710_at_g49g2000cwa.googlegroups.com>


Joe Seigh wrote:
> vc wrote:

[...]

> > Could you elaborate a bit on the techniques they used ? Also, where
> > can I find a description of those techniques ?
>
> 6,760,726 appears to be a patent on LIFO queues with a version count
> to avoid the ABA problem. Slightly different than IBM's version in
> that they increment the version count on the pop operation rather than
> push operation. In theory it's more optimal than IBM's version in
> that you could use a single word CAS for the push operation rather
> than a double word CAS. I don't know if they do that but in practice
> it doesn't matter. It's more of an esthetic thing. There's at least
> one other patent on this, 6,178,473, so it's a popular thing to patent.
>
> You can use this to queue requests for service or for object recycling
> queues. If queue contention was a major problem then this would help.
> But I suspect processing the requests takes the bulk of the processing
> time, not the queue/dequeueing of requests.
>
> 6,763,447 is, AFAICT, some kind of lock-free FIFO queue. There's
> some circular producer/consumer queue logic. This is a popular
> area to mess around in with lock-free due to compsci profs using
> a circular producer/cosumer queue as an example when teaching
> threaded programming. It's easy to get into all kinds of interesting
> and painful race conditions, especially if you're inexperienced.
> I generally don't waste a lot of time looking at this kind of stuff
> unless they can articulate they know what the problems are and that
> they have a novel solution of the problems.
>
> If you want a working multi-reader, multi-writer FIFO queue, use
> Maged Michael and Michael Scott's non-blocking concurrent queue
> algorithm.
>
> At any rate, lock-free FIFO queues is similar to LIFO in application.
> They're not what I would expect to be useful for a database implentation
> which is a large shared data struction. You want lock-free reader/writer
> solutions like RCU, not lock-free producer/consumer solutions like
> lock-free LIFO's and FIFO's.

Thank you, much appreciated. Their techniques do not seem to be paticularly original despite the patents and all.

>
> You can look at the patents here http://www.uspto.gov/ but be warned,
> patents are notoriously difficult to read.

I know ;)

[...]

> > Did not know about this one, thought it was a Linux thingie. Thanks.
>
> I thought it was just a VM thingie until a couple of years ago. I thought
> all operating systems except VM were normally preemptive.
>
> But you can implement RCU in user space outside the kernel. Just depends
> on what you use for quiescent states. I used to have an RCU implementation
> here, http://atomic-ptr-plus.sourceforge.net/ but have since shelved it
> in favor of RCU+SMR which has better granularity so when a thread gets
> involuntarily preempted or blocked, it doesn't tie up as many resources
> waiting to be deleted and recycled.

I'll take a look.

I researched ANTs' claims a bit, and what I found does not look as interesting as I originally thought it might be. Also, I was put off a bit by their advertizing style (claims about 15 fold performance improvements).

Thank you for your contribution to the discussion.

>
> --
> Joe Seigh
>
> When you get lemons, you make lemonade.
> When you get hardware, you make software.
Received on Wed Nov 09 2005 - 21:29:42 CET

Original text of this message