List:Falcon Storage Engine« Previous MessageNext Message »
From:Jim Starkey Date:December 9 2008 4:34pm
Subject:Re: [Fwd: Real-World Concurrency]
View as plain text  
> On Mon, Dec 8, 2008 at 3:08 PM, Jim Starkey <jstarkey@stripped> 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 

   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

Re: [Fwd: Real-World Concurrency]Jim Starkey9 Dec
  • Re: [Fwd: Real-World Concurrency]MARK CALLAGHAN9 Dec
    • Re: [Fwd: Real-World Concurrency]Jim Starkey9 Dec
    • Re: [Fwd: Real-World Concurrency]Jim Starkey9 Dec