From: Martin Fick <mfick@codeaurora.org>
To: Michael Haggerty <mhagger@alum.mit.edu>
Cc: Jeff King <peff@peff.net>,
git@vger.kernel.org, Junio C Hamano <gitster@pobox.com>
Subject: Lockless Refs? (Was [PATCH] refs: do not use cached refs in repack_without_ref)
Date: Thu, 27 Dec 2012 16:11:51 -0700 [thread overview]
Message-ID: <201212271611.52203.mfick@codeaurora.org> (raw)
In-Reply-To: <50DAB447.8000101@alum.mit.edu>
On Wednesday, December 26, 2012 01:24:39 am Michael Haggerty
wrote:
> ... lots of discussion about ref locking...
It concerns me that git uses any locking at all, even for
refs since it has the potential to leave around stale locks.
For a single user repo this is not a big deal, the lock can
always be cleaned up manually (and it is a rare occurrence).
However, in a multi user server environment, possibly even
from multiple hosts over a shared filesystem such as NFS,
stale locks could lead to serious downtime and risky recovery
(since it is currently hard to figure out if a lock really is
stale). Even though stale locks are probably rare even today
in the larger shared repo case, as git scales to even larger
shared repositories, this will eventually become more of a
problem *1. Naturally, this has me thinking that git should
possibly consider moving towards a lockless design for refs
in the long term.
I realize this is hard and that git needs to support many
different filesystems with different semantics. I had an idea I
think may be close to a functional lockless design for loose
refs (one piece at a time) that I thought I should propose,
just to get the ball rolling, even if it is just going to be
found to be flawed (I realize that history suggests that such
schemes usually are). I hope that it does not make use of
any semantics which are not currently expected from git of
filesystems. I think it relies only on the ability to rename
a file atomically, and the ability to scan the contents of a
directory reliably to detect the "ordered" existence of files.
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:
1) To update the value from a known value to a new value
atomically, simply rename the file to the new value. This
operation should only succeed if the file exists and is still
named old value before the rename. This should even be
faster than today's approach, especially on remote filesystems
since it would require only 1 round trip in the success case
instead of 3!
2) To delete the ref, simply delete the filename representing
the current value of the ref. This ensures that you are
deleting the ref from a specific value. I am not sure if git
needs to be able to delete refs without knowing their values?
If so, this would require reading the value and looping until
the delete succeeds, this may be a bit slow for a constantly
updated ref, but likely a rare situation (and not likely
worse than trying to acquire the ref-lock today). Overall,
this again would likely be faster than today's approach.
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.
While this outlines the state changes, some additional
operations may be needed to setup some starting conditions
and to clean things up. But these operations could/should be
performed by any process/thread and would not cause any state
changes to the ref existence or value. For example, when
creating a ref, the ref directory would need to be created
and the null file needs to be created. Whenever a null file is
detected in the directory at the same time as another file, it
should be deleted. Whenever the directory is empty, it may
be deleted (perhaps after a grace period to reduce retries
during ref creation unless the process just deleted the ref).
I don't know how this new scheme could be made to work with
the current scheme, it seems like perhaps new git releases
could be made to understand both the old and the new, and a
config option could be used to tell it which method to write
new refs with. Since in this new scheme ref directory names
would conflict with old ref filenames, this would likely
prevent both schemes from erroneously being used
simultaneously (so they shouldn't corrupt each other), except
for the fact that refs can be nested in directories which
confuses things a bit. I am not sure what a good solution to
this is?
What did I miss, where are my flaws? Does anyone else share
my concern for stale locks? How could we similarly eliminate
locks for the packed-refs file?
-Martin
*1 We have been concerned with stale locks in the Gerrit
community when trying to design atomic cross repository
updates. Of course, while a lockless solution eliminates
stale locks, it might make it impossible to do atomic cross
repository updates since all of our solutions so far need
locks. :(
next prev parent reply other threads:[~2012-12-27 23:12 UTC|newest]
Thread overview: 23+ messages / expand[flat|nested] mbox.gz Atom feed top
2012-12-21 8:04 [PATCH] refs: do not use cached refs in repack_without_ref Jeff King
2012-12-26 8:24 ` Michael Haggerty
2012-12-27 23:11 ` Martin Fick [this message]
2012-12-28 14:50 ` Lockless Refs? (Was [PATCH] refs: do not use cached refs in repack_without_ref) Martin Fick
2012-12-28 17:15 ` Lockless Refs? Junio C Hamano
2012-12-29 8:16 ` Jeff King
2012-12-29 21:15 ` Martin Fick
2012-12-29 8:12 ` Lockless Refs? (Was [PATCH] refs: do not use cached refs in repack_without_ref) Jeff King
2012-12-29 21:29 ` Martin Fick
2012-12-28 16:58 ` Lockless Refs? Junio C Hamano
2012-12-29 1:07 ` Martin Fick
2012-12-29 8:10 ` Lockless Refs? (Was [PATCH] refs: do not use cached refs in repack_without_ref) Jeff King
2012-12-29 22:18 ` Martin Fick
2012-12-30 17:03 ` Martin Fick
2012-12-31 10:30 ` Martin Fick
2013-01-03 23:52 ` Martin Fick
2013-01-04 17:52 ` Pyeron, Jason J CTR (US)
2013-01-04 18:01 ` Martin Fick
2013-01-04 21:28 ` Lockless Refs? Junio C Hamano
2013-01-05 16:12 ` Lockless Refs? (Was [PATCH] refs: do not use cached refs in repack_without_ref) Jeff King
2013-01-22 4:31 ` Drew Northup
2012-12-29 7:16 ` [PATCH] refs: do not use cached refs in repack_without_ref Jeff King
[not found] ` <201301071109.12086.mfick@codeaurora.org>
2013-01-07 18:14 ` Martin Fick
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=201212271611.52203.mfick@codeaurora.org \
--to=mfick@codeaurora.org \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
--cc=mhagger@alum.mit.edu \
--cc=peff@peff.net \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).