Fine grained locking and Linked Lists

The Buffer Manager in SimpleDBM uses a number of different locks in order to obtain fine-grained locking. The assumption is that with fine-grained locking, concurrency will be higher and the system will scale better with larger volumes and greater number of CPUs. However, whether this is actually achieved depends largely on the efficiency of the locks. It would be interesting to create a different version of the Buffer Manager that uses coarse locking, and then compare the performance of the two. I suspect that the benefits of fine-grained locking will only show when the buffer pool is large.

Fine grained locking does have couple of issues. It makes your code more complicated and difficult to maintain and debug. It also increases memory usage. To give you an example, in the Buffer Manager, we have following locks.

1. A ReentrantReadWriteLock to protect access to LRU chain.
2. A ReentrantReadWriteLock for each cached page.
3. A ReentrantLock for each Buffer Control Block.
4. A ReentrantReadWriteLock for each bucket in the Hash Table.

If we have a buffer pool of 500 pages, and a hash table of 193 buckets, then the total number of lock objects would be:

1 + 500 + 193 = 694 ReentrantReadWriteLocks
plus 500 ReentrantLocks.

I hope that the java.util.concurrent.lock package is upto this type of usage.

One problem in the Buffer Manager implementation is the single global LRU lock. It would be a good idea to split the global LRU list to multiple lists, each protected by its own lock.

Linked Lists

Linked Lists are used heavily in the Buffer Manager. The LRU list is a linked list. Each of the hash buckets has its own linked list.

The problem with the standard linked lists is that the remove operation requires a search within the list. This did not strike me until recently, when I was considering how to implement LRU placement hints. The larger the list grows, the longer it will take to search for the item to be removed. Since hash chains are expected to be small, maybe it is not an issue there. The LRU chain, however, is expected to be long. A possible solution (ugly) would be to implement some custom linked list code for the LRU list. Sigh.