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

[Martin Fick <mfick@codeaurora.org>]

On Saturday, December 29, 2012 03:18:49 pm Martin Fick wrote:
> Jeff King <peff@peff.net> wrote:
> >On Thu, Dec 27, 2012 at 04:11:51PM -0700, Martin Fick 
wrote:
> >> My idea is based on using filenames to store sha1s
> >> instead of file contents.  To do this, the sha1 one of
> >> a ref would be stored in a file in a directory named
> >> after the loose ref.  I believe this would then make
> >> it possible to have lockless atomic ref updates by
> >> renaming the file.
> >> 
> >> To more fully illustrate the idea, imagine that any
> >> file (except for the null file) in the directory will
> >> represent the value of the ref with its name, then the
> >> following transitions can represent atomic state
> >> changes to a refs
> >
> >> value and existence:
> >Hmm. So basically you are relying on atomic rename() to
> >move the value around within a directory, rather than
> >using write to move it around within a file. Atomic
> >rename is usually something we have on local filesystems
> >(and I think we rely on it elsewhere). Though I would
> >not be
> >surprised if it is not atomic on all networked
> >filesystems (though it is
> >on NFS, at least).
> 
> Yes.  I assume this is OK because doesn't git already rely
> on atomic renames?  For example to rename the new
> packed-refs file to unlock it?
> 
> ...
> 
> >> 3) To create a ref, it must be renamed from the null
> >> file (sha 0000...) to the new value just as if it were
> >> being updated from any other value, but there is one
> >> extra condition: before renaming the null file, a full
> >> directory scan must be done to ensure that the null
> >> file is the only file in the directory (this condition
> >> exists because creating the directory and null file
> >> cannot be atomic unless the filesystem supports atomic
> >> directory renames, an expectation git does not
> >> currently make).  I am not sure how this compares to
> >> today's approach, but including the setup costs
> >> (described below), I suspect it is slower.
> >
> >Hmm. mkdir is atomic. So wouldn't it be sufficient to
> >just mkdir and create the correct sha1 file?
> 
> But then a process could mkdir and die leaving a stale
> empty dir with no reliable recovery mechanism.
> 
> 
> Unfortunately, I think I see another flaw though! :( I
> should have known that I cannot separate an important
> check from its state transitioning action.  The following
> could happen:
> 
>  A does mkdir
>  A creates null file
>  A checks dir -> no other files
>  B checks dir -> no other files
>  A renames null file to abcd
>  C creates second null file
>  B renames second null file to defg
> 
> One way to fix this is to rely on directory renames, but I
> believe this is something git does not want to require of
> every FS? If we did, we could Change #3 to be:
> 
> 3) To create a ref, it must be renamed from the null file
> (sha 0000...) to the new value just as if it were being
> updated from any other value. (No more scan)
> 
> Then, with reliable directory renames, a process could do
> what you suggested to a temporary directory, mkdir +
> create null file, then rename the temporary dir to
> refname.  This would prevent duplicate null files.  With
> a grace period, the temporary dirs could be cleaned up in
> case a process dies before the rename.  This is your
> approach with reliable recovery.

The whole null file can go away if we use directory renames.  
Make #3:

3) To create a ref, create a temporary directory containing a 
file named after the sha1 of the ref to be created and rename 
the directory to the name of the ref to create.  If the 
rename fails, the create fails.  If the rename succeeds, the 
create succeeds.

With a grace period, the temporary dirs could be cleaned up 
in case a process dies before the rename,

-Martin