[concurrency-interest] Multi-level locks

Bryan Thompson bryan at systap.com
Tue Mar 16 09:16:37 EDT 2010


Many databases have moved away from pessimistic locking.  Are you sure that you need this in your architecture rather than an optimistic concurrency strategy with validation during the commit protocol?  This often leads to higher throughput and can have the advantage that readers never block when coupled with a MVCC.



From: concurrency-interest-bounces at cs.oswego.edu [mailto:concurrency-interest-bounces at cs.oswego.edu] On Behalf Of Khilan Gudka
Sent: Monday, March 15, 2010 11:19 AM
To: concurrency-interest at cs.oswego.edu
Subject: [concurrency-interest] Multi-level locks

Dear all,

I'm looking to produce a high-performant implementation of multi-granularity (a.k.a multi-level) locks. I'm basing my implementation on the paper "Granularity of Locks in a Shared Data Base" by Gray et al. There are five modes: Shared (S), Exclusive (X), Intention Shared (IS), Intention Exclusive (IX) and Shared Intention Exclusive (SIX - this last mode can be represented implicitly by non-zero counts for both S and IX).

I currently have an implementation whereby I use a long to represent state. There is a global state for the lock that gives the status of the lock with respect to all threads as well as per-thread state for a thread's count of each of the above modes (minus the implicitly  represented mode SIX). Determining whether a request from a thread can proceed is achieved by subtracting the two (giving a so-called "group mode" of the other threads) and then doing a bit-wise AND to determine compatibility of the request with the group mode). I keep two queues (ConcurrentLinkedQueue) for upgrades and new requests respectively. To keep the implementation simple, the lock and unlock methods are synchronized. However, this doesn't perform very well. For instance, 8 threads incrementing a counter 100000 times takes 10 seconds compared with 0.2 seconds when using j.u.c.ReentrantReadWriteLock.

I've been looking at AbstractQueuedLongSynchronizer and noticed in the javadoc comments that it's designed for this sort of thing. However, from what I've seen it only supports the two modes S and X. Furthermore, it doesn't seem trivial to extend the internal wait queue given that the Node class is final? or is it?

If somebody could please give me some advice as to how to proceed, I would be ever so grateful.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20100316/b16afccd/attachment.html>

More information about the Concurrency-interest mailing list