Sounds nice!


The resource queue class (Queue) requires a transaction object.  The signature is:


lock(Object tx, short mode)
          Request a lock for the tx in the specified mode and block until the lock is granted.


The deadlock support class (TxDag) has similar requirements:


addEdge(Object blocked, Object running)
          Add an edge to the DAG.


Where blocked and running are “transaction” objects.  I have not placed any constraint on the interfaces implemented by a “transaction” object, so this could be anything at all.  Let me know if this would create any problems.  My goal was a 2PL module without dependencies on other API – ideally something that can be reused easily.


I am definitely interested in looking at optimistic strategies – overall I think that they are really the best way to go.  I have thought about how I would use optimistic CC in the GOM framework over jdbm, where I like the approach that some classes are able to achieve consistency without locking – much like you have suggested for btrees.  Overall, there is nothing about the 2PL system that would make it impossible to use an optimistic concurrency control strategy, you just need to make sure that you validate if you do not obtain a lock.




From: [] On Behalf Of Kevin Day
Sent: Thursday, March 23, 2006 4:46 PM
To: JDBM Developer listserv
Subject: re[2]: [Jdbm-developer] Preliminary work on version manager is ready to commit...




I think I'll wait for Alex to weigh in and decide how best to proceed on where to check this stuff in to.  Everything I've done up to now is from scratch, so licensing is not restricted.


The use (or non-use) of dbCache should be completely orthoganol to the transaction management in this design.  When I talk about "writing to the store", I mean writing to any type of persistent storage.  From the perspective of the proof of concept, whether the data winds up on the safe or in the actual db doesn't matter at all.  For simplicity, I'm currently using a non page-based storage layer (basically, an array of typed variable length byte arrays).


Basically, dbCache (or the existing jdbm logging system) is used to ensure atomicity of groups of pages only.  As long a you can guarantee that a given set of pages will either commit in their entirety or not at all, the multi-version algorithm takes care of transaction level isolation, atomicity and consistency.  This does *not* require that all pages involved in a given transaction be written at the same time, though.  There are certain groups of pages that do have to be written at the same time, so the smallest atomic write operation may involve 3 or 4 pages (a data page, a version page, a couple of translation pages).  That same transaction may wind up making thousands of page writes over it's entire life, but they don't all have to be written at the same time.


Once that guarantee is in place, the version control system takes care of ensuring isolation, atomicity and consistency at the transaction level.


Durability is achieved by ensuring that all data involved in a given transaction has been written to the safe at the time of commit - but it's perfectly acceptable to have some of the data structures that are involved in multiple transactions.  It's even possible for two active transactions to maintain changes to the same record at the same time - the concurrency management layer comes in at this point to determine whether a commit is allowed or not.


I have *not* written any thread synchronization or locking into the system at this point, so I'm relying on serial sequences of transaction operations for my unit testing.  My goal here was more to prove that the concept would work, and provide a test bed so we could come up with transaction sequences that we thought might give us problems.


I'm pretty sure that we can implement 2PL on the logical records of the versioning system (it seems to me that concurrency control is really involved in the logical state of the database, not the physical state).  I'm not sure where the appropriate place to actually look for deadlocks is, but I'm sure that will fall out as we start looking at the overall architecture.  Does the 2PL system require that a transaction identifier (or transaction object itself) be passed in to the lock request?


Dring the development of the 2PL system, did you come across any ways of abstracting the design to easily support both 2PL and optimistic locking?




- K




Sounds interesting.  I just fixed the deadlock detection code and integrated it into the 2PL locking support[1].  This does not support intention locks (you can not describe a hierarchy of resources), but it should support basic 2PL.  I am working on an optimization to the deadlock detection code and I hope to release a beta by Monday.
I take it that you mean that the notion of consistency for the design that you have does not use any notion of transactions within a page manager layer such as DBCache.  Is that of necessity or just how you developed it?  The DBCache [2]implementation will let you force a page to the db at any time, but that is probably not what you are looking for.  In any case, I am sure that we will get a chance to discuss the relationship between the version/transaction manager and page caching :-)
I am not sure how best to proceed with respect to a jdbm2.x code base.  Anything that is derived from jdbm1.x is of course under the existing license terms, but new modules can be under a different license as long as they do not share code or have explicit copyright grants from all authors.  
[2] /index.html

From: [] On Behalf Of Kevin Day
Sent: Thursday, March 23, 2006 10:16 AM
To: JDBM Developer listserv
Subject: [Jdbm-developer] Preliminary work on version manager is ready to commit...



OK - finally had time to finish up work on the proof of concept for the version and transaction manager for jdbm2.  This is just proof of concept, but I'd like to ask you guys to take a look at the unit test and let me know if you see anything that you think should be tested for that isn't, etc...


The current implementation has been tested for transaction isolation for overlapping transactions, properly purging of unneeded data, etc...


The algorithm has been designed with aborts and roll-back in mind, but I have not put unit tests in place for that yet (tomorrow maybe), and the code for properly purging aborted tx from the transaction manager still needs to be put in place (Basically, aborted tx can't be removed from the master transaction list until the garbage collector has run one full iteration).


The algorithms are designed to allow writing to the data store at any point - regardless of whether a transaction is comitted or not.  A warning:  this is *very* different from the dbCache design, which relies on only writing comitted data to the data store (or jumping through hoops to allow for roll-back if uncomitted data is written to the store).


The current proof of concept system has no caching - all changes to the data are written directly to the store (which is in-memory right now - nothing to disk, etc...).  This means that there is absolutely no distinction between regular transactions and very long transactions - the algorithm treats them all the same (and works :-)  ).  This means that handling of VLR will become a caching policy implementation detail - not something that requires special handling in the transaction or version managers (this is a good thing, I think).



So - where should I commit the code to?  Alex - should I create a separate folder for jdbm2 exploratory stuff in the jdbm SF project?  Should we create a new SF project (for licensing reasons)?




- K



Kevin Day
Trumpet, Inc.



------------------------------------------------------- This SF.Net email is sponsored by xPML, a groundbreaking scripting language that extends applications into web and mobile media. Attend the live webcast and join the prime developer group breaking into this new coding territory! _______________________________________________ Jdbm-developer mailing list