To debug the concurrency errors we need a mechanism for tracing the complex
operations with low overhead. See the article in DDJ April 23, 2007,
Multi-threaded Debugging Techniques by Shameem Akhter and Jason Roberts.
This is an excerpt from the book Multi-Core Programming by the same authors.

Create a background thread for the deadlock detector.

This is a symptom - the real issue is that if there is a catastrophic
failure, then SimpleDBM should immediately shutdown. At present, a
catastrophic failure in one component does not trigger a full shutdown.

The BTree Manager is easily the most complex of the SimpleDBM modules. If
things go wrong it is very hard to pinpoint where the problem lies. 

Already several measures are present:

Trace messages have been added recently.
Node level validations are done if appropriate flag is set at run time.
Simple checks are performed when inserting new entries in a page - also
when a flag is set.
Number of assertions have been increasing.

But these measures are all ad-hoc. We need a more systematic approach so
that we get the maximum benefit at minimum overhead. For instance, it only
makes sense to validate stuff if things have changed.

During logical undos, a transactional module may generate new log records. 
As a result, during transaction aborts or rollbacks, it is possible to 
make an attempt to recursively acquire the shared latch for the 
transaction manager. However, the ReadWriteUpdateLatch implementation does 
not support recursive shared latch access because it does not maintain 
information about owners of shared latch. 

Using an ArrayList is now possible as the locklist is no longer consulted
when locks are released, acquired or searched for. The only use is to 
support the need to release all or some locks during rollbacks.

The offset within the arraylist can be used as lock position.

When a search is executed on a key which is present in the right sibling 
of a leaf page (indirect child), the search fails with null pointer 
exception.

Seems like it is an integer truncation problem in the compareTo method.

Each transaction should allow lock timeout to be set as this is useful as 
a deadlock detector when testing.

At present a single LRU chain is used to determine which pages to evict. Every 
fix request must 
modify the LRU chain by locking it, and every time a page is evicted, the LRU 
chain must be locked 
exclusively.

Concurrency can impoved by implementing multiple LRU chains.

When more than one thread is concurrently attempting to insert a tuple, a
latch deadlock occurs due to the order of locking:

a) First thread obtains exclusive locks on space map page and then data page.
b) The second thread obtains exclusive lock on data page followed by space
map page.

The deadlock can be avoided by ensuring that latches are always acquired in
the same order.

Encountered a failure in testCase4() - assertion failure. 

In the NOT FOUND case, the lock on next key should be for instant duration
only. However, at present, the scan does not detect the NOT FOUND scenario,
and therefore cannot release the lock immediately. Only the calling client
can determine whether the key was found or not.

Affects database API 1.0.8

One of the test cases for reproducing a defect uses code that is copied
from the BTree page merge function. Fix the test case to use the actual
doMerge() operation.

The deadlock detector must ensure that it has exclusive access to the Lock 
Manager data structures. To enable this, a global latch was introduced. 
All regular operations acquire the latch in shared mode, but the deadlock 
detector acquires the latch in exclusive mode.

It is however possible that the interaction between the deadlock detector 
and other threads to lead to a deadlock within the Lock Manager. This is 
because a request for shared latch is blocked if there is a pending 
request for exclusive access. 

To avoid the deadlock the deadlock detectory should use tryExclusiveLock() 
rather than exclusiveLock(). 

Except for lock exceptions, most other exceptions should be unchecked 
exceptions. This will not only simply the interfaces and the exception 
handling code, but also make it easier to pass on lock exceptions to the 
client.

Add varbinary type to the typesystem

A new Dumpable interface will be added to support dumping object contents to a 
StringBuilder. 
Eventualy toString() will just be a call to a method in Dumpable interface.

If an PageId or Lockable object returns negative hash code, there will be 
an array out of bounds exception.

If all buffer pages are dirty and two threads are simultaneously trying to
fix a page, one of the threads may be starved and fail after 10 retries.
This appears to happen on single CPU machines. It seems that when the
buffer writer calls notifyAll() after a buffer write, it is possible for
one of threads to consistently fail to obtain the available buffer due to
the way the threads are awakened.

This would allow fine tuning of page sizes so that tables can have larger
page sizes if necessary for larger rows.

Produced during database stress test - owing to the exception thrown by the
loop detection logic.

java.lang.IllegalStateException: SIMPLEDBM-EM0007: Latch mode in
inconsistent state
        at
org.simpledbm.rss.impl.bm.BufferManagerImpl$BufferAccessBlockImpl.unlatch(Buffer
ManagerImpl.java:1488)
        at
org.simpledbm.rss.impl.bm.BufferManagerImpl.unfix(BufferManagerImpl.java:908)
        at
org.simpledbm.rss.impl.bm.BufferManagerImpl$BufferAccessBlockImpl.unfix(BufferMa
nagerImpl.java:1532)
        at
org.simpledbm.rss.impl.tuple.TupleManagerImpl$TupleInserterImpl.doCompleteInsert
(TupleManagerImpl.java:1249)
        at
org.simpledbm.rss.impl.tuple.TupleManagerImpl$TupleInserterImpl.completeInsert(T
upleManagerImpl.java:1346)
        at
org.simpledbm.rss.impl.tuple.TupleManagerImpl$TupleContainerImpl.doUpdate(TupleM
anagerImpl.java:1768)
        at
org.simpledbm.rss.impl.tuple.TupleManagerImpl$TupleContainerImpl.update(TupleMan
agerImpl.java:1776)
        at
org.simpledbm.database.impl.TableScanImpl.updateCurrentRow(TableScanImpl.java:14
3)
        at
org.simpledbm.database.TestDatabase$TesterThread.testUpdate(TestDatabase.java:63
4)
        at
org.simpledbm.database.TestDatabase$TesterThread.run(TestDatabase.java:857)
        at java.lang.Thread.run(Thread.java:619)

See Wiki page for specifications

When rolling back to a savepoint, the transaction manager releases locks 
acquired since the rollback. However, it does not reacquire locks that 
were released after the savepoint. Locks can be released in situations 
where cursors are executing in cursor stabilty mode and have move from the 
cursor position at the time of rollback. When the transacion rolls back to 
a savepoint, the cursors must be restored to their position as at the time 
of savepoint, and the locks reacquired. 

The efficient way to resolve this issue appears to be to restore cusror 
position and reaquire locks. 

The BTree split algorithm attempts to replace the high key in the left 
node before purging the items to the right of the high key. This is 
incorrect as the page may not have space for the high key if the new high 
key is larger than the old high key in size. The correct sequence is to 
purge the excess items first so that there is guaranteed space for the 
high key.

A related problem is that the slottedpage implementation does not report 
LOUDLY the failure to insert a slot due to lack of space. It reports the 
error condition by returning false - we need a more robust mechanism for 
reporting this; such as a runtime exception.

It seems that if there are page marked as having space, but which actually
contain uncommitted deletes, then the logic for allocating a page can go
into an endless loop.

Motivation is that it enables code completion in Eclipse when inserting
links in the javadoc comments.

Need to check whether it is possible to try to update the virtual EOF key that 
exists in every BTree. 
At present, there isn't any checks in the code for this - need to make sure 
that this is prevented.

Currently SimpleDBM needs to be embedded in the application. It would be
nice to have the ability to run a SimpleDBM server and connect to it over TCP.

At present during updates existing tuple segments are not resized even if
there is space available on the pages. This causes following inefficiency:
if a tuple grows beyond its original size, instead of resizing the tuple
segment, an additional tuple segment will be allocated (possibly on the
same page) and linked to the previous segment.

When searching for space map pages, a shared latch on the space map page
would be sufficient, as no changes are made to the space map page at this
point.

Creating many locks causes the lock hash table to grow. The lock requests 
start to fail when this happens with a NullPointerException.

org.simpledbm.rss.api.pm.PageException: SIMPLEDBM-EO0002: Cannot insert
item IndexItem(key=[[Blogg8072], [Joe8072]], isLeaf=false, isUnique=false,
Location=TupleId(ns=84, pageId=PageId(1,225), slot=1), ChildPage=207) of
size 58 into page at slot 137 due to lack of space: page contents = 
=========================================================================
PAGE DUMP : pageType=16, pageId=PageId(3,140), pageLsn=Lsn(3,2582669)
PageSize=8184
FIXED OVERHEAD=28
UsableSpace=8156
PageFlags=0
#Slots=139
#DeletedSlots=0
HighWaterMark=888
FreeSpace=54
SpaceMapPage=1
Slot#0=slot(offset=8136, length=20, flags=0)
Slot#1=slot(offset=8080, length=56, flags=0)
Slot#2=slot(offset=8024, length=56, flags=0)
Slot#3=slot(offset=7968, length=56, flags=0)
Slot#4=slot(offset=7912, length=56, flags=0)
...
Slot#137=slot(offset=888, length=48, flags=0)
Slot#138=slot(offset=936, length=16, flags=0)
Calculated PageSize=8184

        at
org.simpledbm.rss.impl.sp.SlottedPageImpl.insertAt(SlottedPageImpl.java:579)
        at
org.simpledbm.rss.impl.im.btree.BTreeIndexManagerImpl.redoLinkOperation(BTreeInd
exManagerImpl.java:491)
        at
org.simpledbm.rss.impl.im.btree.BTreeIndexManagerImpl.redo(BTreeIndexManagerImpl
.java:277)
        at
org.simpledbm.rss.impl.im.btree.BTreeIndexManagerImpl$BTreeImpl.doLink(BTreeInde
xManagerImpl.java:1461)
        at
org.simpledbm.rss.impl.im.btree.BTreeIndexManagerImpl$BTreeImpl.updateModeTraves
e(BTreeIndexManagerImpl.java:2270)
        at
org.simpledbm.rss.impl.im.btree.BTreeIndexManagerImpl$BTreeImpl.doInsertTraverse
(BTreeIndexManagerImpl.java:2357)
        at
org.simpledbm.rss.impl.im.btree.BTreeIndexManagerImpl$BTreeImpl.doInsert(BTreeIn
dexManagerImpl.java:2529)
        at
org.simpledbm.rss.impl.im.btree.BTreeIndexManagerImpl$BTreeImpl.insert(BTreeInde
xManagerImpl.java:2697)
        at org.simpledbm.database.impl.TableImpl.addRow(TableImpl.java:99)
        at
org.simpledbm.database.TestDatabase$TesterThread.testInsert(TestDatabase.java:52
5)
        at
org.simpledbm.database.TestDatabase$TesterThread.run(TestDatabase.java:814)
        at java.lang.Thread.run(Thread.java:613)

SimpleDBM RSS module offers a low-level API to the database engine. It has no 
support for type-
system or data dictionary. For most users the level of abstraction is too low 
level.

We need two additional modules:

a) A Typesystem that supports different data types and row types.
b) A higher level Database API that uses the typesystem and also adds a data 
dictionary.

There is an unnecessary overhead when scanning index nodes for child
pointers. Index items are fully de-serialized when only the child pointer
is needed. 

This will remove some pain in making copies of these types.

There is an issue with the timer logic in the LockManagerImpl. The shared
global lock is not released if the timer logic enters the loop. The lock
should be released during a lock wait so that the deadlock detector can be
activated.

This issue was found when running the stress test in the database API. 

When running the database stress test with 3 or more threads, the test can
go into a state where every request starts to deadlock. This happens when
data is being deleted.

Example of this deadlock:

2008-07-25 23:56:02,851 [DeadlockDetector] WARN
org.simpledbm.rss.impl.locking SIMPLEDBM-WC0011: Detected deadlock cycle:

R1 LockRequest(mode=EXCLUSIVE, convertMode=EXCLUSIVE, status=WAITING,
count=1, owner=Transaction(trxId=TrxId(109093),
isolationMode=READ_COMMITTED), thread=Thread[Thread-1,5,main],
duration=COMMIT_DURATION)
    (victim) waiting for
    R2 LockRequest(mode=EXCLUSIVE, convertMode=EXCLUSIVE, status=WAITING,
count=1, owner=Transaction(trxId=TrxId(109095),
isolationMode=READ_COMMITTED), thread=Thread[Thread-2,5,main],
duration=MANUAL_DURATION)

R1 LockItem(
   target=TupleId(ns=84, pageId=PageId(1,394), slot=39),
   grantedMode=EXCLUSIVE,
   waiting=true,
   queue=[
      LockRequest(mode=EXCLUSIVE, convertMode=UPDATE, status=GRANTED,
count=2, owner=Transaction(trxId=TrxId(109095),
isolationMode=READ_COMMITTED), thread=Thread[Thread-2,5,main],
duration=COMMIT_DURATION),
      LockRequest(mode=EXCLUSIVE, convertMode=EXCLUSIVE, status=WAITING,
count=1, owner=Transaction(trxId=TrxId(109093),
isolationMode=READ_COMMITTED), thread=Thread[Thread-1,5,main],
duration=COMMIT_DURATION)])

R2 LockItem(
   target=TupleId(ns=84, pageId=PageId(1,394), slot=35),
   grantedMode=EXCLUSIVE,
   waiting=true,
   queue=[
      LockRequest(mode=EXCLUSIVE, convertMode=EXCLUSIVE, status=GRANTED,
count=1, owner=Transaction(trxId=TrxId(109093),
isolationMode=READ_COMMITTED), thread=Thread[Thread-1,5,main],
duration=COMMIT_DURATION),
      LockRequest(mode=EXCLUSIVE, convertMode=EXCLUSIVE, status=WAITING,
count=1, owner=Transaction(trxId=TrxId(109094),
isolationMode=READ_COMMITTED), thread=Thread[Thread-3,5,main],
duration=COMMIT_DURATION),
      LockRequest(mode=EXCLUSIVE, convertMode=EXCLUSIVE, status=WAITING,
count=1, owner=Transaction(trxId=TrxId(109095),
isolationMode=READ_COMMITTED), thread=Thread[Thread-2,5,main],
duration=MANUAL_DURATION)])

2008-07-25 23:56:02,852 [DeadlockDetector] WARN
org.simpledbm.rss.impl.locking SIMPLEDBM-WC0011: Detected deadlock cycle:

R1 LockRequest(mode=EXCLUSIVE, convertMode=EXCLUSIVE, status=WAITING,
count=1, owner=Transaction(trxId=TrxId(109094),
isolationMode=READ_COMMITTED), thread=Thread[Thread-3,5,main],
duration=COMMIT_DURATION)
   (victim) waiting for
   R2 LockRequest(mode=EXCLUSIVE, convertMode=EXCLUSIVE, status=DENIED,
count=1, owner=Transaction(trxId=TrxId(109093),
isolationMode=READ_COMMITTED), thread=Thread[Thread-1,5,main],
duration=COMMIT_DURATION)

R1 LockItem(
   target=TupleId(ns=84, pageId=PageId(1,394), slot=35),
   grantedMode=EXCLUSIVE,
   waiting=true,
   queue=[
       LockRequest(mode=EXCLUSIVE, convertMode=EXCLUSIVE, status=GRANTED,
count=1, owner=Transaction(trxId=TrxId(109093),
isolationMode=READ_COMMITTED), thread=Thread[Thread-1,5,main],
duration=COMMIT_DURATION),
       LockRequest(mode=EXCLUSIVE, convertMode=EXCLUSIVE, status=WAITING,
count=1, owner=Transaction(trxId=TrxId(109094),
isolationMode=READ_COMMITTED), thread=Thread[Thread-3,5,main],
duration=COMMIT_DURATION),
       LockRequest(mode=EXCLUSIVE, convertMode=EXCLUSIVE, status=WAITING,
count=1, owner=Transaction(trxId=TrxId(109095),
isolationMode=READ_COMMITTED), thread=Thread[Thread-2,5,main],
duration=MANUAL_DURATION)])

R2 LockItem(
   target=TupleId(ns=84, pageId=PageId(1,394), slot=39),
   grantedMode=EXCLUSIVE,
   waiting=true,
   queue=[
       LockRequest(mode=EXCLUSIVE, convertMode=UPDATE, status=GRANTED,
count=2, owner=Transaction(trxId=TrxId(109095),
isolationMode=READ_COMMITTED), thread=Thread[Thread-2,5,main],
duration=COMMIT_DURATION),
       LockRequest(mode=EXCLUSIVE, convertMode=EXCLUSIVE, status=DENIED,
count=1, owner=Transaction(trxId=TrxId(109093),
isolationMode=READ_COMMITTED), thread=Thread[Thread-1,5,main],
duration=COMMIT_DURATION)])


It seems that this may be due to the COMMIT_DURATION request being
victimised instead of the MANUAL_DURATION request. 

It seems that pages are being latched in exclusive mode when reading tuples.

The Log Manager is becoming a bottleneck for btree tests. When running
test cases, we need to be able to say that we do not care about flushing
the log to disk so that we can get the tests to complete quickly.

Code is monolithic and contains duplication of the same code in multiple
places. Needs to be refactored so that methods are smaller in size, code is
more maintainable.

Some newly exposed properties include:

log.disableFlushRequests - if true, performs log flush less frequently
bufferpool.writerSleepInterval - changes the interval between write scans
transaction.ckpt.interval - changes the interval between checkpoints
lock.deadlock.detection.interval - changes the interval between deadlock checks
storage.flushMode - changes the way data is flushed to disk (noforce)

The current log messages are hard to read.

Some additional properties worth exposing are:

log.disableFlushRequests - if true, performs log flush less frequently
bufferpool.writerSleepInterval - changes the interval between write scans
transaction.ckpt.interval - changes the interval between checkpoints
lock.deadlock.detection.interval - changes the interval between deadlock checks

At present the ReadWriteLatch implementation uses Java's 
ReentrantReadWriteLock. It throws NotSupportedException if any of the 
methods that support update mode lock are invoked. Instead of throwing an 
exception, treat update locks as exclusive ones. 

This improvement will allow the use of these latches where the 
ReadWriteUpdateLatch is used - this is good for testing.

Seems like an oversight.

SlottedPage should test that the page latch is held exclusively when an 
attempt is made to modify the page. This is useful for catching bugs.

After the parent is split, the BTreeNode must be refreshed before it is
accessed - as the parent may have moved (could be the right sibling).