MARK CALLAGHAN wrote:
> 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
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
