Re: Lock-free databases

vc wrote:
> Joe Seigh wrote:
>

>>vc wrote:
>>
>>>Joe Seigh wrote:
>>>
>>>
>>>>vc wrote:
>>>>
>>>>>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")  ?
>>
>>They haven't quantified the performance contribution of the patents
>>and knowing the techniques in question, they'd have to have some
>>very specific performance bottlenecks to get a significant benefit.

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.

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

>>>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 ?
>>>
>>
>>Lock-free LIFO queues and lock-free enqueuing onto FIFO queues.
>>Some fast pathed things like WAIT/POST bypass.  Examples of those
>>were in appendix A for the 370/390/z-Arch Principles of Operation.

>>And an RCU like mechanism in the VM operating system.

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.

-- 
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.