From: Alex B. <boi...@in...> - 2006-01-20 15:37:06
|
Kevin, I think your algorithm would work but it would not account for changes that have ripple effects, such as rebalancing a BTree, or updating an object with a larger size. Both of those cases would ultimately 'lock' bytes beyond the original 'row' and therefore you would still end up with non-deterministic case of conflicts between transactions. I am more in favor of splitting the physical record and logical object management such that transactions operate at the logical level until their commit point (to avoid conflicts) and migrate objects to physical pages after the commit point. In DBCache parlance, the safe and cache would contain objects (not physical records) and objects would be reallocated (and hopefully clustered) when moved to the database. Makes sense? alex Kevin Day wrote: > Hi folks - I've done some noodling on things, and I think I finally > "get" the BFIM strategy for long transactions. I've also started > coming up with some thoughts on how to make this actually work for > jdbm, including fine grained locking semantics. > > Here's what I'm thinking (much of this is similar to DB Cache, but > with the addition of lower-than-page locking): > > > First, we have to throw out a few of the posits of the DB Cache > system. Namely, the concept that there are only two versions of a > given page in cache. If multiple txs are going to operate > concurrently, then each transaction must have a copy of a given page > that contains only the changes that tx has made since it's inception. > > I am going to suggest that what we really need is a 'current' version > of each page in cache, plus transaction specific versions of that page > for all active transactions. > > Next, we need a way of determing low level locking regions to ensure > compatible updates. To that end, we need to have what I'm calling a > delta mask for each version of each page. The 'current' version of a > page will have a master delta mask that tracks the updated bytes of > all active transactions. Each transaction version of a page will have > a tx delta mask that tracks the updated bytes of other transactions > that have worked on the page since the inception of the tx under > consideration (this is a little tricky, but I think it works). > > > I am putting together some transaction usage cases in Excel that will > be very helpful for explaining what I'm talking about - are you both > able to open and view XLS files? If so, I'll put something together > with the full strategy and get it out for your review. > > The long and short is that I'm pretty sure I have an algorithm that > will allow byte level locking, with high performance for small > transactions and support for long transactions (using a modified BFIM > strategy). > > If this works the way I think it should, that will give us the low > level tools for supporting multiple transactions with high > concurrency, all while avoiding the non-deterministic locking problems > that arise with doing full page locking. > > Let's make sure that you don't see any issues with the algorithm I > describe (tomorrow - too darned tired now), then we can start a > discussion about what data structures need to be in place in the > translation page and free row lists to support high concurrency. > > Cheerio! > > - K > > Kevin Day > Trumpet, Inc. > www.trumpetinc.com <http://www.trumpetinc.com> > ke...@tr... <mailto:ke...@tr...> > 602-438-7030 > > ------------------------------------------------------- This SF.net > email is sponsored by: Splunk Inc. Do you grep through log files for > problems? Stop! Download the new AJAX search engine that makes > searching your log files as easy as surfing the web. DOWNLOAD SPLUNK! > http://sel.as-us.falkag.net/sel?cmd=lnk&kid=103432&bid=230486&dat=121642 > _______________________________________________ Jdbm-developer mailing > list Jdb...@li... > https://lists.sourceforge.net/lists/listinfo/jdbm-developer |