Re: Lockless Refs? (Was [PATCH] refs: do not use cached refs in repack_without_ref)
On Sat, Jan 5, 2013 at 11:12 AM, Jeff King p...@peff.net wrote: On Mon, Dec 31, 2012 at 03:30:53AM -0700, Martin Fick wrote: 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. Deleting a directory is not atomic, as you first have to remove the contents, putting it into a potentially inconsistent state. I'll assume you deal with that later... I know I'm a bit late to the dance here, but FWIW the apparent atomicy (odd conjugation there) of directory deletion depends largely upon the filesystem and VFS api in use. It is not unheard of that a delete operation actually consist of moving the reference to the item's own allocation marker into a trashcan to be cleaned up after later. In other words, I'd not advise planning on directory deletes always being atomic nor always not being atomic. -- -Drew Northup -- As opposed to vegetable or mineral error? -John Pescatore, SANS NewsBites Vol. 12 Num. 59 -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Lockless Refs? (Was [PATCH] refs: do not use cached refs in repack_without_ref)
On Mon, Dec 31, 2012 at 03:30:53AM -0700, Martin Fick wrote: 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. Deleting a directory is not atomic, as you first have to remove the contents, putting it into a potentially inconsistent state. I'll assume you deal with that later... 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. Has this been a problem for you in practice? Avoiding this is one of the reasons that git does not take out long locks; instead, it takes the lock only at the moment it is ready to write, and aborts if it has been updated since the longer-term operation began. This has its own problems (you might do a lot of work only to have your operation aborted), but I am not sure that your proposal improves on that. Your proposal does sound like it could potentially improve robustness when killing stale transactions (i.e., you know that the transaction originator will never wake up and think it still has the lock). But again, is that a problem in practice? Git typically holds ref locks for a few syscalls. If you are conservative about leaving potentially stale locks in place (e.g., give them a few minutes to complete before assuming they are now bogus), you will not run into that problem. The more conservative you are about treating a lock as stale, of course, the less performant you will be in the face of stale locks. But since they're the exception, that isn't a big problem in practice (at least it has not been for me). 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. I think we've had problems with cross-directory renames on some filesystems, but I don't recall the details. I know that Coda does not like cross-directory links, but cross-directory renames are OK (and in fact we fall back to the latter when the former does not work). Ah, here we go: 5723fe7 (Avoid cross-directory renames and linking on object creation, 2008-06-14). Looks like NFS is the culprit. 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. Hmm. So what happens to the delete file when the ref.lock directory is being deleted? Presumably deleting the ref.lock directory means doing it recursively (which is non-atomic). But then why are we keeping the delete file at all, if we're just about to remove it? What happens if another process wants to cancel a transaction that is partially done? That is, the ref.lock directory is created, but it contains the uuid subdir? It sounds like it's OK to just delete from it, and the original process will then fail at its rename? 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. Yeah, I don't see anything that would prevent that. The current code only cares about open($ref.lock, O_EXCL). But that should be correct and atomic with respect to the renamed directories. You are depending on atomic directory renames. Those aren't used anywhere yet in git, as far as I know. So that may run into problems (but there's no reason this system couldn't be optional for filesystems that are more abled, and other systems could fall back to the straight-file locking). So in response to your question, no, I don't see any real showstoppers here. And unlike the all refs are files in a directory scheme, it's confined to writing, which solves the readdir() atomicity questions I had there. I still can't say I'm super excited about it, just because it seems like a solution in search of a problem that I have not experienced myself. But if it's solving a problem for you, I don't want to
RE: Lockless Refs? (Was [PATCH] refs: do not use cached refs in repack_without_ref)
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
Re: Lockless Refs? (Was [PATCH] refs: do not use cached refs in repack_without_ref)
On Friday, January 04, 2013 10:52:43 am Pyeron, Jason J CTR (US) wrote: 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, sound reasonable. Where you thinking a runtime test case that would be run before every transaction? I was anticipating a per repo config option called something like core.locks = recoverable that would be needed to turn them on? I was thinking that this was something that server sites could test in advance on their repos and then enable it for them. Maybe a git- lock tool with a --test-recoverable option? -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
Re: Lockless Refs?
Martin Fick mf...@codeaurora.org writes: 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. The general impression I have been getting was that this isn't even worth the effort and the resulting complexity of the code, given Peff's observations earlier in the thread that ref update conflicts and leftover locks are reasonably rare in practice. But perhaps I has been mis-reading the discussion. I also have this suspicion that if you really want to shoot for multi-repository transactions in an massively scaled repository hosting environment, you would rather want to not rely on hacks based on filesystem semantics, but instead want to RPC with a dedicated ref management service that knows the transaction semantics you want, but that could become a much larger change. I dunno. -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Lockless Refs? (Was [PATCH] refs: do not use cached refs in repack_without_ref)
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. 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
Re: Lockless Refs? (Was [PATCH] refs: do not use cached refs in repack_without_ref)
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.
Re: Lockless Refs? (Was [PATCH] refs: do not use cached refs in repack_without_ref)
On Saturday, December 29, 2012 03:18:49 pm Martin Fick wrote: Jeff King p...@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 ...) 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 ...) 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 -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Lockless Refs? (Was [PATCH] refs: do not use cached refs in repack_without_ref)
On Thu, Dec 27, 2012 at 04:11:51PM -0700, Martin Fick wrote:
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.
FWIW, I am involved in cleaning up stale locks for a very large git
hosting site. It actually happens surprisingly little. I think it is
mostly because git holds actual locks for a very short period of time
(just enough to check that the value is unchanged from when we started a
lengthy operation, and then atomically write the new value).
So I agree it would be cool (and maybe open up new realms of
scalability) for git to be lockless, but in my experience, this isn't
that pressing a problem (and any solutions are not going to be backwards
compatible, so there is going to be a high deployment cost).
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).
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!
OK. Makes sense.
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.
We do sometimes delete without knowing the value. In most cases we would
not want to do this, but for some force-type commands, we do. You
would actually have the same problem with updating above, as we
sometimes update with the intent to overwrite whatever is there.
3) To create a ref, it must be renamed from the null file (sha
...) 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? A simultaneous creator would fail on the
mkdir and abort. A simultaneous reader might see the directory, but it
would either see it as empty, or with the correct file. In the former
case, it would treat that the same as if the directory did not exist.
Speaking of which, you did not cover reading at all, but it would have
to be:
dh = opendir(ref);
if (!dh) {
if (errno == ENOENT)
return 0; /* no such ref */
else
return error(couldn't read ref);
}
while ((ent = readdir(dh)) {
if (ent-d_name[0] == '.')
/*
* skip . and .., and leave room for annotating
* refs via dot-files
Re: Lockless Refs? (Was [PATCH] refs: do not use cached refs in repack_without_ref)
On Fri, Dec 28, 2012 at 07:50:14AM -0700, Martin Fick wrote: Hmm, actually I believe that with a small modification to the semantics described here it would be possible to make multi repo/branch commits work. Simply allow the ref filename to be locked by a transaction by appending the transaction ID to the filename. So if transaction 123 wants to lock master which points currently to abcde, then it will move master/abcde to master/abcde_123. If transaction 123 is designed so that any process can commit/complete/abort it without requiring any locks which can go stale, then this ref lock will never go stale either (easy as long as it writes all its proposed updates somewhere upfront and has atomic semantics for starting, committing and aborting). On commit, the ref lock gets updated to its new value: master/newsha and on abort it gets unlocked: master/abcde. Hmm. I thought our goal was to avoid locks? Isn't this just locking by another name? I guess your point is to have no locks in the normal case, and have locked transactions as an optional add-on? -Peff -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Lockless Refs?
On Fri, Dec 28, 2012 at 09:15:52AM -0800, Junio C Hamano wrote: Martin Fick mf...@codeaurora.org writes: Hmm, actually I believe that with a small modification to the semantics described here it would be possible to make multi repo/branch commits work Shawn talked about adding multi repo/branch transaction semantics to jgit, this might be something that git wants to support also at some point? Shawn may have talked about it and you may have listened to it, but others wouldn't have any idea what kind of multi repo/branch transaction you are talking about. Is it about I want to push this ref to that repo and push this other ref to that other repo, in what situation will it be used/useful, what are the failure modes, what are failure tolerances by the expected use cases, ...? Care to explain? I cannot speak for Martin, but I am assuming the point is to atomically update 2 (or more) refs on the same repo. That is, if I have a branch refs/heads/foo and a ref pointing to meta-information (say, notes about commits in foo, in refs/notes/meta/foo), I would want to git push them, and only update them if _both_ will succeed, and otherwise fail and update nothing. I think Shawn mentioned this at the last GitTogether as a stumbling block for pushing more of Gerrit's meta-information as refs over the git protocol. But I might be mis-remembering. -Peff -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Lockless Refs?
Jeff King p...@peff.net wrote: On Fri, Dec 28, 2012 at 09:15:52AM -0800, Junio C Hamano wrote: Martin Fick mf...@codeaurora.org writes: Hmm, actually I believe that with a small modification to the semantics described here it would be possible to make multi repo/branch commits work Shawn talked about adding multi repo/branch transaction semantics to jgit, this might be something that git wants to support also at some point? Shawn may have talked about it and you may have listened to it, but others wouldn't have any idea what kind of multi repo/branch transaction you are talking about. Is it about I want to push this ref to that repo and push this other ref to that other repo, in what situation will it be used/useful, what are the failure modes, what are failure tolerances by the expected use cases, ...? Care to explain? I cannot speak for Martin, but I am assuming the point is to atomically update 2 (or more) refs on the same repo. That is, if I have a branch refs/heads/foo and a ref pointing to meta-information (say, notes about commits in foo, in refs/notes/meta/foo), I would want to git push them, and only update them if _both_ will succeed, and otherwise fail and update nothing. My use case was cross repo/branch dependencies in Gerrit (which do not yet exist). Users want to be able to define several changes (destined for different project/branches) which can only be merged together. If one change cannot be merged, the others should fail too. The solutions we can think of generally need to hold ref locks while acquiring more ref locks, this drastically increases the opportunities for stale locks over the simple lock, check, update, unlock mode which git locks are currently used for. I was perhaps making too big of a leap to assume that there would be other non Gerrit uses cases for this? I assumed that other git projects which are spread across several git repos would need this? But maybe this simply wouldn't be practical with other git server solutions? -Martin Employee of Qualcomm Innovation Center,Inc. which is a member of Code Aurora Forum -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Lockless Refs? (Was [PATCH] refs: do not use cached refs in repack_without_ref)
Jeff King p...@peff.net wrote: On Fri, Dec 28, 2012 at 07:50:14AM -0700, Martin Fick wrote: Hmm, actually I believe that with a small modification to the semantics described here it would be possible to make multi repo/branch commits work. Simply allow the ref filename to be locked by a transaction by appending the transaction ID to the filename. So if transaction 123 wants to lock master which points currently to abcde, then it will move master/abcde to master/abcde_123. If transaction 123 is designed so that any process can commit/complete/abort it without requiring any locks which can go stale, then this ref lock will never go stale either (easy as long as it writes all its proposed updates somewhere upfront and has atomic semantics for starting, committing and aborting). On commit, the ref lock gets updated to its new value: master/newsha and on abort it gets unlocked: master/abcde. Hmm. I thought our goal was to avoid locks? Isn't this just locking by another name? It is a lock, but it is a lock with an owner: the transaction. If the transaction has reliable recovery semantics, then the lock will be recoverable also. This is possible if we have lock ownership (the transaction) which does not exist today for the ref locks. With good lock ownership we gain the ability to reliably delete locks for a specific owner without the risk of deleting the lock when held by another owner (putting the owner in the filename is good, while putting the owner in the filecontents is not). Lastly, for reliable recovery of stale locks we need the ability to determine when an owner has abandoned a lock. I believe that the transaction semantics laid out below give this. I guess your point is to have no locks in the normal case, and have locked transactions as an optional add-on? Basically. If we design the transaction into the git semantics we could ensure that it is recoverable and we should not need to expose these reflocks outside of the transaction APIs. To illustrate a simple transaction approach (borrowing some of Shawn's ideas), we could designate a directory to hold transaction files *1. To prepare a transaction: write a list of repo:ref:oldvalue:newvalue to a file named id.new (in a stable sorted order based on repo:ref to prevent deadlocks). This is not a state change and thus this file could be deleted by any process at anytime (preferably after a long grace period). If file renames are atomic on the filesystem holding the transaction files then 1, 2, 3 below will be atomic state changes. It does not matter who performs state transitions 2 or 3. It does not matter who implements the work following any of the 3 transitions, many processes could attempt the work in parallel (so could a human). 1) To start the transaction, rename the id.new file to id. If the rename fails, start over if desired/still possible. On success, ref locks for each entry should be acquired in listed order (to prevent deadlocks), using transaction id and oldvalue. It is never legal to unlock a ref in this state (because a block could cause the unlock to be delayed until the commit phase). However, it is legal for any process to transition to abort at any time from this state, perhaps because of a failure to acquire a lock (held by another transaction), and definitely if a ref has changed (is no longer oldvalue). 2) To abort the transaction, rename the id file to id.abort. This should only ever fail if commit was achieved first. Once in this state, any process may/should unlock any ref locks belonging to this transaction id. Once all refs are unlocked, id.abort may be deleted (it could be deleted earlier, but then cleanup will take longer). 3) To commit the transaction, rename the file to id.commit. This should only ever fail if abort was achieved first. This transition should never be done until every listed ref is locked by the current transaction id. Once in this phase, all refs may/should be moved to their new values and unlocked by any process. Once all refs are unlocked, id.commit may be deleted. Since any process attempting any of the work in these transactions could block at any time for an indefinite amount of time, these processes may wake after the transaction is aborted or comitted and the transaction files are cleaned up. I believe that in these cases the only actions which could succeed by these waking processes is the ref locking action. All such abandoned ref locks may/should be unlocked by any process. This last rule means that no transaction ids should ever be reused, -Martin *1 We may want to adapt the simple model illustrated above to use git mechanisms such as refs to hold transaction info instead of files in a directory, and git submodule files to hold the list of refs to update. Employee of Qualcomm Innovation Center,Inc. which is a member of Code Aurora Forum -- To unsubscribe from this list: send
Re: Lockless Refs? (Was [PATCH] refs: do not use cached refs in repack_without_ref)
Jeff King p...@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 ...) 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 ...) 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. 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? I think you would need to bump core.repositoryformatversion, and just never let old versions of git access the repository directly. Not the end of the world, but it certainly increases deployment effort. If we were going to do that, it would probably make sense to think about solving the D/F conflict issues at the same time (i.e., start calling refs/heads/foo in the filesystem refs.d/heads.d/foo.ref so that it cannot conflict with refs.d/heads.d/foo.d/bar.ref). Wouldn't you want to use a non legal ref character instead of dot? And without locks, we free up more of the ref namespace too I think? (Refs could end in .lock) -Martin Employee of Qualcomm Innovation Center,Inc. which is a member of Code Aurora Forum -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Lockless Refs?
Martin Fick mf...@codeaurora.org writes: 3) To create a ref, it must be renamed from the null file (sha ...) 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... While you are scanning this directory to make sure it is empty, I am contemplating to create the same ref with a different value. You finished checking but haven't created the null. I have also scanned, created the null and renamed it to my value. Now you try to create the null, succeed, and then rename. We won't know which of the two non-null values are valid, but worse yet, I think one of them should have failed in the first place. Sounds like we would need some form of locking around here. Is your goal no locks, or less locks? I don't know how this new scheme could be made to work with the current scheme,... It is much more important to know if/why yours is better than the current scheme in the first place. Without an analysis on how the new scheme interacts with the packed refs and gives better behaviour, that is kinda difficult. I think transition plans can wait until that is done. If it is not even marginally better, we do not have to worry about transitioning at all. If it is only marginally better, the transition has to be designed to be no impact to the existing repositories. If it is vastly better, we might be able to afford a flag day. -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Lockless Refs?
Martin Fick mf...@codeaurora.org writes: Hmm, actually I believe that with a small modification to the semantics described here it would be possible to make multi repo/branch commits work Shawn talked about adding multi repo/branch transaction semantics to jgit, this might be something that git wants to support also at some point? Shawn may have talked about it and you may have listened to it, but others wouldn't have any idea what kind of multi repo/branch transaction you are talking about. Is it about I want to push this ref to that repo and push this other ref to that other repo, in what situation will it be used/useful, what are the failure modes, what are failure tolerances by the expected use cases, ...? Care to explain? -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Lockless Refs?
On Friday, December 28, 2012 09:58:36 am Junio C Hamano wrote: Martin Fick mf...@codeaurora.org writes: 3) To create a ref, it must be renamed from the null file (sha ...) 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... While you are scanning this directory to make sure it is empty, The objective is not to scan for an empty dir, but to scan for the existence of only the null file. I am contemplating to create the same ref with a different value. You finished checking but haven't created the null. The scan needs to happen after creating the null, not before, so I don't believe the rest of the scenario below is possible then? I have also scanned, created the null and renamed it to my value. Now you try to create the null, succeed, and then rename. We won't know which of the two non-null values are valid, but worse yet, I think one of them should have failed in the first place. Sounds like we would need some form of locking around here. Is your goal no locks, or less locks? (answered below) I don't know how this new scheme could be made to work with the current scheme,... It is much more important to know if/why yours is better than the current scheme in the first place. The goal is: no locks which do not have a clearly defined reliable recovery procedure. Stale locks without a reliable recovery procedure will lead to stolen locks. At this point it is only a matter of luck whether this leads to data loss or not. So I do hope to convince people first that the current scheme is bad, not that my scheme is better! My scheme was proposed to get people thinking that we may not have to use locks to get reliable updates. Without an analysis on how the new scheme interacts with the packed refs and gives better behaviour, that is kinda difficult. Fair enough. I will attempt this if the basic idea seems at least sane? I do hope that eventually the packed-refs piece and its locking will be reconsidered also; as Michael pointed out it has issues already. So, I am hoping to get people thinking more about lockless approaches to all the pieces. I think I have some solutions to some of the other pieces also, but I don't want to overwhelm the discussion all at once (especially if my first piece is shown to be flawed, or if no one has any interest in eliminating the current locks?) I think transition plans can wait until that is done. If it is not even marginally better, we do not have to worry about transitioning at all. If it is only marginally better, the transition has to be designed to be no impact to the existing repositories. If it is vastly better, we might be able to afford a flag day. OK, makes sense, I jumped the gun a bit, -Martin -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Lockless Refs? (Was [PATCH] refs: do not use cached refs in repack_without_ref)
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 ...) 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?
