Re: how to build a database from scratch

On 2006-12-08, NENASHI, Tegiri wrote:

>> 2PL does make life easy, but you can't use it unless you know precisely
>> what data is going to be touched by a transaction when it begins.
>
> It is very strange what you say. Microsoft SQL Server utilizes 2PL
> and I think DB2 also.

I meant to say "ordered 2PL" or "2PL like that". The point was that 2PL alone does not guarantee deadlock-freeness. If you use it, at the very least you'll need to implement deadlock avoidance or recovery, and of course an efficient rollback mechanism. If locks are allocated in a global order and the requestor immediately backs off when it cannot allocate all of the needed locks, then deadlocks cannot occur, but on the other hand now you need to know in advance which locks are required and you still don't get guaranteed progress. This happens because rollbacks caused by lock acquisition failures carry overhead which can grow rather stern when the locking granularity is as coarse as a whole tree: a number of other tasks can be expected to compete for access to the tree and suddenly all of your time might be wasted on rollbacks caused by lock acquisition failure. It's not difficult to show that the problem gets worse real fast with increasing concurrency.

In some environments such considerations can be assumed away, which of course considerably simplifies your DBMS. But in general you can't neglect this sort of thing. This is also a typical example of why you need more complicated concurrency control mechanisms like multigranularity locking. Then, as I already said, reengineering your B-trees starts seeming like a good idea because suddenly having a lock on the tree no longer guarantees that the overarching topology of the tree stays the same. This complicates the tree maintenance code quite a lot and causes the bottleneck to shift into the tree maintenance code.

-- 
Sampo Syreeni, aka decoy - mailto:decoy_at_iki.fi, tel:+358-50-5756111
student/math+cs/helsinki university, http://www.iki.fi/~decoy/front
openpgp: 050985C2/025E D175 ABE5 027C 9494 EEB0 E090 8BA9 0509 85C2