RE: Lockless Refs? (Was [PATCH] refs: do not use cached refs in repack_without_ref)

["Pyeron, Jason J CTR (US)" <jason.j.pyeron.ctr@mail.mil>]

[-- Attachment #1: Type: text/plain, Size: 7382 bytes --]

> From: Martin Fick
> Sent: Thursday, January 03, 2013 6:53 PM
> 
> Any thoughts on this idea?  Is it flawed?  I am trying to
> write it up in a more formal generalized manner and was
> hoping to get at least one "it seems sane" before I do.

If you are assuming that atomic renames, etc. are available, then you should identify a test case and a degrade operation path when it is not available.

> 
> Thanks,
> 
> -Martin
> 
> On Monday, December 31, 2012 03:30:53 am Martin Fick wrote:
> > On Thursday, December 27, 2012 04:11:51 pm Martin Fick
> wrote:
> > > It concerns me that git uses any locking at all, even
> > > for refs since it has the potential to leave around
> > > stale locks.
> > > ...
> > > [a previous not so great attempt to fix this]
> > > ...
> >
> > I may have finally figured out a working loose ref update
> > mechanism which I think can avoid stale locks.
> > Unfortunately it requires atomic directory renames and
> > universally unique identifiers (uuids).  These may be
> > no-go criteria?  But I figure it is worth at least
> > exploring this idea because of the potential benefits?
> >
> > The general approach is to setup a transaction and either
> > commit or abort it.  A transaction can be setup by
> > renaming an appropriately setup directory to the
> > "ref.lock" name.  If the rename succeeds, the transaction
> > is begun.  Any actor can abort the transaction (up until
> > it is committed) by simply deleting the "ref.lock"
> > directory, so it is not at risk of going stale.  However,
> > once the actor who sets up the transaction commits it,
> > deleting the "ref.lock" directory simply aids in cleaning
> > it up for the next transaction (instead of aborting it).
> >
> > One important piece of the transaction is the use of
> > uuids. The uuids provide a mechanism to tie the atomic
> > commit pieces to the transactions and thus to prevent
> > long sleeping process from inadvertently performing
> > actions which could be out of date when they wake finally
> > up.  In each case, the atomic commit piece is the
> > renaming of a file.   For the create and update pieces, a
> > file is renamed from the "ref.lock" dir to the "ref" file
> > resulting in an update to the sha for the ref. However,
> > in the delete case, the "ref" file is instead renamed to
> > end up in the "ref.lock" directory resulting in a delete
> > of the ref.  This scheme does not affect the way refs are
> > read today,
> >
> > To prepare for a transaction, an actor first generates a
> > uuid (an exercise I will delay for now).  Next, a tmp
> > directory named after the uuid is generated in the parent
> > directory for the ref to be updated, perhaps something
> > like:  ".lock_uuid". In this directory is places either a
> > file or a directory named after the uuid, something like:
> > ".lock_uuid/,uuid".  In the case of a create or an
> > update, the new sha is written to this file.  In the case
> > of a delete, it is a directory.
> >
> > Once the tmp directory is setup, the initiating actor
> > attempts to start the transaction by renaming the tmp
> > directory to "ref.lock".  If the rename fails, the update
> > fails. If the rename succeeds, the actor can then attempt
> > to commit the transaction (before another actor aborts
> > it).
> >
> > In the case of a create, the actor verifies that "ref"
> > does not currently exist, and then renames the now named
> > "ref.lock/uuid" file to "ref". On success, the ref was
> > created.
> >
> > In the case of an update, the actor verifies that "ref"
> > currently contains the old sha, and then also renames the
> > now named "ref.lock/uuid" file to "ref". On success, the
> > ref was updated.
> >
> > In the case of a delete, the actor may verify that "ref"
> > currently contains the sha to "prune" if it needs to, and
> > then renames the "ref" file to "ref.lock/uuid/delete". On
> > success, the ref was deleted.
> >
> > Whether successful or not, the actor may now simply delete
> > the "ref.lock" directory, clearing the way for a new
> > transaction.  Any other actor may delete this directory at
> > any time also, likely either on conflict (if they are
> > attempting to initiate a transaction), or after a grace
> > period just to cleanup the FS.  Any actor may also safely
> > cleanup the tmp directories, preferably also after a grace
> > period.
> >
> > One neat part about this scheme is that I believe it would
> > be backwards compatible with the current locking
> > mechanism since the transaction directory will simply
> > appear to be a lock to older clients.  And the old lock
> > file should continue to lock out these newer
> > transactions.
> >
> > Due to this backwards compatibility, I believe that this
> > could be incrementally employed today without affecting
> > very much.  It could be deployed in place of any updates
> > which only hold ref.locks to update the loose ref.  So
> > for example I think it could replace step 4a below from
> > Michael Haggerty's description of today's loose ref
> > pruning during
> >
> > ref packing:
> > > * Pack references:
> > ...
> >
> > > 4. prune_refs(): for each ref in the ref_to_prune list,
> > >
> > > call  prune_ref():
> > >     a. Lock the reference using lock_ref_sha1(),
> > >     verifying that the recorded SHA1 is still valid.  If
> > >     it is, unlink the loose reference file then free
> > >     the lock; otherwise leave the loose reference file
> > >     untouched.
> >
> > I think it would also therefore be able to replace the
> > loose ref locking in Michael's new ref-packing scheme as
> > well as the locking in Michael's new ref deletion scheme
> > (again steps
> >
> > 4):
> > > * Delete reference foo:
> > ...
> >
> > >   4. Delete loose ref for "foo":
> > >      a. Acquire the lock $GIT_DIR/refs/heads/foo.lock
> > >
> > >      b. Unlink $GIT_DIR/refs/heads/foo if it is
> > >      unchanged.
> > >
> > >  If it is changed, leave it untouched.  If it is
> > >  deleted,
> > >
> > > that is OK too.
> > >
> > >      c. Release lock $GIT_DIR/refs/heads/foo.lock
> >
> > ...
> >
> > > * Pack references:
> > ...
> >
> > >   4. prune_refs(): for each ref in the ref_to_prune
> > >   list,
> > >
> > > call prune_ref():
> > >      a. Lock the loose reference using lock_ref_sha1(),
> > >
> > > verifying that the recorded SHA1 is still valid
> > >
> > >      b. If it is, unlink the loose reference file
> > >
> > > (otherwise, leave it untouched)
> > >
> > >      c. Release the lock on the loose reference
> >
> > To be honest, I suspect I missed something obvious because
> > this seems almost too simple to work.  I am ashamed that
> > it took me so long to come up with (of course, I will be
> > even more ashamed :( when it is shown to be flawed!)
> > This scheme also feels extensible. if there are no
> > obvious flaws in it, I will try to post solutions for ref
> > packing and for multiple repository/ref transactions also
> > soon.
> >
> > I welcome any comments/criticisms,
> >
> > -Martin
> > --
> > To unsubscribe from this list: send the line "unsubscribe
> > git" in the body of a message to
> > majordomo@vger.kernel.org More majordomo info at
> > http://vger.kernel.org/majordomo-info.html
> --
> To unsubscribe from this list: send the line "unsubscribe git" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

[-- Attachment #2: smime.p7s --]
[-- Type: application/x-pkcs7-signature, Size: 5615 bytes --]