From: Jim Starkey Date: December 9 2008 4:34pm Subject: Re: [Fwd: Real-World Concurrency] List-Archive: http://lists.mysql.com/falcon/282 Message-Id: <493E9E31.5070402@nimbusdb.com> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit MARK CALLAGHAN wrote: > On Mon, Dec 8, 2008 at 3:08 PM, Jim Starkey wrote: > >> I think you guys are missing something important by not exploring cycle >> locking. It's a very powerful tool. I'm using it in Nimbus with great >> success. The water's warm, come on in. >> > > What is cycle locking? > > Cycle locking is a scheme to manage object lifetime and pointer validity without the overhead frequent locks and/or reference counting. The basic idea is to use a single high level lock (the cycle lock) to manage pointer validity in a shared, complex data structure. Clients take a shared lock on the cycle lock when initiating a high level operation and release it at the end. Objects that would otherwise be deleted during the cycle are moved, instead, to an object purgatory. A cycle manager periodically: 1. Starts a new cycle by creating (or recyling) a lock for the new cycle 2. Cleans up, if necessary, any dangling pointers to logically deleted objects 3. Wait for an exclusive lock on the prior cycle lock 4. Delete objects in purgatory (or take other appropriate action) The crux of the idea is that after step 3, there can be no dangling pointers to objects in purgatory. Let me give a example from Falcon. In Falcon, record versions are chained newest to oldest. A transaction finds an appropriate record version by traversing the record chain until it finds a record that either it created or was created by a transaction that was committed when it began. Assume a transaction modifies a single record over and over, each in a distinct savepoint. After commit, the record chain would look like: B => Bn => ... => B1 => A where B was the final update, Bn to B1 where intermediate updates in the same transaction as B, and A is the version of the record before transaction started. Records Bn to B1 are complete junk. They need to be retained during the transaction to allow a savepoint to be rolled back, but otherwise just waste memory. The problem is how to delete them without invalidating the pointers in the chain. There is no problem changing the chain to: B => A The problem is deleting versions Bn through B1 without crashing another thread traversing the chain. Originally, Falcon made no attempt to reclaim intermediate versions; it now uses a relatively expensive traversal lock to prevent traversal while intermediate versions are removed. This is both expensive and tragic because it almost never happens in a well structured application. With cycle locking, intermediate versions can be removed and moved to record purgatory. Since the record version pointers remain intact, a thread traversing the chain can safely dereference stale pointers. After the cycle as ended, however, there can be no remaining stale pointers, and the records in purgatory can be safely (and, possibly, cheaply) deleted. The beauty of cycle locking is that it is completely non-blocking (except for the cycle manager itself, which is of no consequence). Furthermore, it cost to client threads is a single shared lock Another application of cycle locking is inter-object references in a Java Virtual Machines. To allow objects to migrate, most JVMs identify objects by an object id which is dereferenced through a central data structure. With cycle locking, a Java object could cache a hard pointers to another object for the duration of the cycle, reducing the cost of object references. At the end of the cycle, the cached pointers would be zeroed as part of garbage collection. Cycle locking isn't a panacea, but it is a neat trick. -- Jim Starkey President, NimbusDB, Inc. 978 526-1376