Lock-free tdb lookups

[Joe Seigh]

David Collier-Brown wrote:
> Joe Seigh wrote:
> 
>> I took a look at the tdb source.  It would be pretty straightforward
>> to make it read lock-free except for the transactional stuff.
>> Transactions have to be atomic w.r.t. other operations.  I can't see
>> any way of making things lock-free without infringing, in part at least,
>> on patent application 20050198030 "Efficient support of consistent cyclic
>> search with read-copy-update" by Paul McKenney, file in March 2004,
>> and probably on anything else filed on software transactional memory.
>>
>> So "Closed on account of patents" I guess.
> 
> 
> If this is strictly lookups, are there uses of the tdb that
> do not require consistency, merely atomicity?

It's the atomicity of transactions that is the problem.  You
couldn't have a simple look up see part of a transaction
followed by another simple look up see pre-transaction data.
It's not likely that code doing the simple look ups cares
about that but you don't have any choice in implementing
the transaction semantics.  If atomicity didn't matter, why
have transactions?

> 
> If not, a former colleague used to recommend an algorithm
> from many moons ago which did not guarantee consistency,
> but allowed the reader to detect it was trying to read
> while the data was inconsistent and return EAGAIN or ESTART.
> 
> That one was easy: there was a transaction-number field at
> the beginning and the end of the updated location,
> and the writer guaranteed to write the transaction
> counter into the first number field, change the data
> in between and then write the transaction number into
> the last one.  ICL used this in disks, so you could
> detect a half-complete write on power failure (;-))
> 
> This last might be an patent-free approach, or perhaps
> prior art.
> 

That would work if you wanted to have read-only transactions,
i.e. a group reads considered as an atomic entity.


--
Joe Seigh