You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@subversion.apache.org by Greg Hudson <gh...@MIT.EDU> on 2002/06/08 19:34:29 UTC
Atomicity under Windows
I'm working on the design of a Subversion filesystem back end which
maps directly to the underlying filesystem, instead of going through a
key/value or SQL database. (I don't want to actually discuss the
design here until after Subversion 1.0 is close to finished, to avoid
taking time away from people working on more important stuff. Also,
it might take me a while to complete the design, or I might lose
steam.) It would be nice if the back end could work and be robust
under Windows as well as Unix. I need some information about
atomicity under Windows to inform the design in this respect.
On Unix, you have some basic tools available for local filesystems:
* fsync() provides the basics of failure atomicity by guaranteeing
that a file's contents have been flushed to disk. (With some
fileystems, you may also have to fsync() directories in order to
make sure that directory entries are flushed to disk; with others,
fsync()ing a file guarantees that all paths referencing the file
have been flushed.)
* rename() is both failure-atomic and concurrency-atomic; either the
rename has happened or it hasn't. There is no in-between state
where the target doesn't exist. (You can't get this for
directories, incidentally.)
* open() with the O_CREAT|O_EXCL flags will fail if the file already
exists; you can use this to create unique files or do rudimentary
locking.
* fcntl() can create advisory locks on files, when the above two
approaches aren't sufficient for concurrency atomicity. fcntl()
locks are convenient because they are automatically cleaned up if
the locking process dies or the machine reboots. You can also use
it to do locking over subranges of a file.
(Some of these guarantees degrade or disappear for remote filesystems,
particularly some vintages of NFS. I don't know all the details
there.)
My question is: which of these tools have equivalents or analogs under
Windows, and which don't? And are there fundamentally different tools
you have to use instead?
Thanks.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Atomicity under Windows
Posted by "Stephen C. Tweedie" <sc...@redhat.com>.
Hi,
On Sun, Jun 09, 2002 at 05:22:10PM -0400, Greg Hudson wrote:
> I didn't mean to imply that rename() was asynchronous when I said it was
> failure-atomic. But apparently the claim was still a bit too strong.
> > Also, some of the more async Unix filesystems don't even guarantee
> > that relaxed form of failure atomicity
>
> You mean that a failure could leave the target directory entry
> nonexistent? I'm curious which filesystems have this property. (I
> assume you're not counting things like FFS with the async flag set; such
> combinations are documented with big red flags as being unsafe.)
That's exactly the situation (and likewise, on Linux, ext2 in async
mode). Sync IO is *really* expensive. Fantastically expensive. It
slows down many common fs operations by a factor of between ten and
fifty.
Fortunately, these days most Unixen have either journaled filesystems,
or something like soft updates, so we have the performance of async
writeback with the safety guarantees of sync IO.
However, this is *still* a red herring. The rename safety is largely
irrelevant. There's no benefit from renaming a file synchronously if
the file contents themselves are not safe on disk! You simply must
have some application control on IO syncing or you are not safe. And
with journaled or soft-update filesystems, the renames are safe, but
there are no guarantees when they will happen, so the syncing has to
apply to directories as well as to files.
> > but you can always simulate
> > that by using a combination of link(2) and fsync(2).
>
> If I'm not mistaken, fsync()ing a directory is a very Linux-specific
> concept. So if there are any non-Linux filesystems which don't provide
> the flaxed failure atomicity guarantee, I'm not sure how one would
> simulate it.
BSD soft updates is async but safe, and you'll still need some form of
fsync to make that safe.
> (Also, link() fails when the target exists. How would you use it to
> emulate relaxed-failure-atomic rename?)
It depends on exactly what end results you are wanting. If you are
going to be using link() and unlink() to get the end results, you'll
often choose a series of ops which does not precisely match any
sequence of renames.
> > > (Some of these guarantees degrade or disappear for remote filesystems,
> > > particularly some vintages of NFS. I don't know all the details
> > > there.)
>
> > I can help on the details if you want.
>
> Is rename() any less concurrency-atomic or failure-atomic than with
> local filesystems?
Hah. NFS is a nightmare.
The fundamental problem on NFS is that if the server power-cycles
after completing an op but before sending the ack, then the client
will resend the request and the server may try to do it twice.
This can result in (for example) deletes succeeding but returning
ENOENT, or renames being applied twice. The types of failure modes
you get when the typical production mix of buggy clients and servers
get together is even more painful!
> > Most NFS systems will offer
> > decent fcntl() locking these days, for example, and there are already
> > libraries in existance (used for things like mailbox locking) to
> > emulate NFS locking via atomic creation of temporary lock files on
> > those systems where fcntl() does not work.
> I'm still not sure how to create a lock in older NFS implementations, if
> it's even possible. fcntl() locking will work in some implementations
> but not others. open() with O_EXCL won't work in NFSv2. (Lots of lore
> on the net to corroborate this.) A google search yields suggests:
NFS does not specify locking, but there are complementary protocols
which exist alongside NFS for locking and which are pretty universally
implemented these days.
> * Create a temporary file with a unique name.
> * link() it to the lock file name.
> * Check to make sure your temporary file has a link count of 2.
>
> I'm not sure why this would work any better than open() with O_EXCL,
Because O_EXCL only helps you if you try to apply it to the shared
lock file. The point of the above recipe is to give you the added
protection of a unique temporary name (chosen randomly) so that you
don't have collisions on the initial create at all.
> unless link() is atomic (in which case why bother with the third
> step?).
The third step tells you if the link succeeded, even if the link
request reported failure due to the NFS repeated-application scenario
above. Link is still atomic.
Cheers,
Stephen
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Atomicity under Windows
Posted by Greg Hudson <gh...@MIT.EDU>.
Apologies for the diversion into obscure Unix and NFS semantics. It's
important for my back-end design. Nothing specific to Subversion here,
though, so busy developers can ignore us.
On Sat, 2002-06-08 at 17:46, Stephen C. Tweedie wrote:
> > * rename() is both failure-atomic and concurrency-atomic; either the
> > rename has happened or it hasn't.
I didn't mean to imply that rename() was asynchronous when I said it was
failure-atomic. But apparently the claim was still a bit too strong.
> BSD-style Unixen do guarantee that a crash will never leave the inode
> in a deleted state --- ie. a crash at an inopportune moment may leave
> both the old and the new directory entry present, but the disk will
> never see the old entry deleted before the new one is created.
This is what I really meant; the case where both the old and new
directory entries exist isn't usually all that important.
> Also, some of the more async Unix filesystems don't even guarantee
> that relaxed form of failure atomicity
You mean that a failure could leave the target directory entry
nonexistent? I'm curious which filesystems have this property. (I
assume you're not counting things like FFS with the async flag set; such
combinations are documented with big red flags as being unsafe.)
> but you can always simulate
> that by using a combination of link(2) and fsync(2).
If I'm not mistaken, fsync()ing a directory is a very Linux-specific
concept. So if there are any non-Linux filesystems which don't provide
the flaxed failure atomicity guarantee, I'm not sure how one would
simulate it.
(Also, link() fails when the target exists. How would you use it to
emulate relaxed-failure-atomic rename?)
> > (Some of these guarantees degrade or disappear for remote filesystems,
> > particularly some vintages of NFS. I don't know all the details
> > there.)
> I can help on the details if you want.
Is rename() any less concurrency-atomic or failure-atomic than with
local filesystems?
> Most NFS systems will offer
> decent fcntl() locking these days, for example, and there are already
> libraries in existance (used for things like mailbox locking) to
> emulate NFS locking via atomic creation of temporary lock files on
> those systems where fcntl() does not work.
I'm still not sure how to create a lock in older NFS implementations, if
it's even possible. fcntl() locking will work in some implementations
but not others. open() with O_EXCL won't work in NFSv2. (Lots of lore
on the net to corroborate this.) A google search yields suggests:
* Create a temporary file with a unique name.
* link() it to the lock file name.
* Check to make sure your temporary file has a link count of 2.
I'm not sure why this would work any better than open() with O_EXCL,
unless link() is atomic (in which case why bother with the third
step?). The following sequence seems like it would make the above
algorithm fail:
Client 1: Create temporary file
Client 2: Create temporary file
Client 1: Link to lock file
Client 1: Check link count
Client 2: Link to lock file and succeed due to non-atomic link()
Client 2: Check link count
Perhaps there's something else going on here; perhaps a non-atomic
link() success can't happen when there's been an intervening request (in
this case, client 1's checking of the link count).
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Atomicity under Windows
Posted by "Stephen C. Tweedie" <sc...@redhat.com>.
Hi,
On Sat, Jun 08, 2002 at 03:34:29PM -0400, Greg Hudson wrote:
> On Unix, you have some basic tools available for local filesystems:
> * rename() is both failure-atomic and concurrency-atomic; either the
> rename has happened or it hasn't. There is no in-between state
> where the target doesn't exist. (You can't get this for
> directories, incidentally.)
Unix does not guarantee this failure atomicity. Concurrency-atomicity
is guaranteed, though.
BSD-style Unixen do guarantee that a crash will never leave the inode
in a deleted state --- ie. a crash at an inopportune moment may leave
both the old and the new directory entry present, but the disk will
never see the old entry deleted before the new one is created.
Further, only on older Unix systems is the rename synchronous; you
can't rely on that these days.
ext3 does happen to guarantee that renames are 100% atomic, and they
can be made synchronous using either a sync attribute on the directory
or fsymc, but that's a special case and you can't rely on completely
atomic renames on Unix in general. You have to be able to cope with
both the old and new dirents existing after a crash.
Also, some of the more async Unix filesystems don't even guarantee
that relaxed form of failure atomicity, but you can always simulate
that by using a combination of link(2) and fsync(2).
> * fcntl() can create advisory locks on files, when the above two
> approaches aren't sufficient for concurrency atomicity. fcntl()
> locks are convenient because they are automatically cleaned up if
> the locking process dies or the machine reboots. You can also use
> it to do locking over subranges of a file.
> (Some of these guarantees degrade or disappear for remote filesystems,
> particularly some vintages of NFS. I don't know all the details
> there.)
I can help on the details if you want. Most NFS systems will offer
decent fcntl() locking these days, for example, and there are already
libraries in existance (used for things like mailbox locking) to
emulate NFS locking via atomic creation of temporary lock files on
those systems where fcntl() does not work.
Cheers,
Stephen
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Atomicity under Windows
Posted by "Stephen C. Tweedie" <sc...@redhat.com>.
Hi,
On Sun, Jun 09, 2002 at 04:32:03PM -0400, Greg Hudson wrote:
> Failure atomicity looks harder. There's no APR interface to the
> FILE_FLAG_WRITE_THROUGH create flag; even if this were corrected (and
> I'm not sure if it can be, since there's no Unix analog)
O_SYNC is a Unix write-through facility. It is used at open time, not
create time, but it still gives you write-through.
However, that's usually not what you want --- you often care more
about the file contents on close than on every single chunk you write
to the file, so fsync() is more appropriate.
--Stephen
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Atomicity under Windows
Posted by "Stephen C. Tweedie" <sc...@redhat.com>.
Hi,
On Sun, Jun 09, 2002 at 10:54:57PM +0200, Branko ?ibej wrote:
> I'm not sure about directory operations. You can't open a directory on
> Windows like you'd do on Unix (well, you can, but only for
> backup/restore purposes, and with the proper privileges enabled). I
> think that in the end it depends on what filesystem you're using. With
> NTFS, they should be atomic.
Right, but atomic != synchronous. A journaling filesystem can still
perform asynchronous writeback when doing a rename. You have a
guarantee that either the old or the new name will be visible after a
crash, but the atomicity guarantee alone is not enough to tell you
_when_ the new name is hard on disk. That's what you need the
additional fsync-style call for (unless the filesystem guarantees
synchronous updates as well as atomic updates.)
--Stephen
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Atomicity under Windows
Posted by Branko Čibej <br...@xbc.nu>.
Greg Hudson wrote:
>Okay, so it looks like one can get portable concurrency atomicity using
>apr_file_lock() (which uses LockFile() on Windows) or with
>apr_file_open() with the APR_EXCL flag (which calls CreateFile() with
>the CREATE_NEW flag on Windows). That's definitely good to know.
>
>Failure atomicity looks harder. There's no APR interface to the
>FILE_FLAG_WRITE_THROUGH create flag; even if this were corrected (and
>I'm not sure if it can be, since there's no Unix analog), I'm not sure
>how much of a gurantee it gives for file operations. And there would
>still be directory operations to worry about.
>
The analogue to fsync is FlushFileBuffers, not FILE_FLAG_WRITE_THROUGH.
The latter makes _all_ writes go straight to the disk, the former just
flushes ditry pages from the file buffers.
I'm not sure about directory operations. You can't open a directory on
Windows like you'd do on Unix (well, you can, but only for
backup/restore purposes, and with the proper privileges enabled). I
think that in the end it depends on what filesystem you're using. With
NTFS, they should be atomic. Using FAT or FAT32 is nonsense, anyway.
--
Brane Čibej <br...@xbc.nu> http://www.xbc.nu/brane/
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Atomicity under Windows
Posted by Greg Hudson <gh...@MIT.EDU>.
Okay, so it looks like one can get portable concurrency atomicity using
apr_file_lock() (which uses LockFile() on Windows) or with
apr_file_open() with the APR_EXCL flag (which calls CreateFile() with
the CREATE_NEW flag on Windows). That's definitely good to know.
Failure atomicity looks harder. There's no APR interface to the
FILE_FLAG_WRITE_THROUGH create flag; even if this were corrected (and
I'm not sure if it can be, since there's no Unix analog), I'm not sure
how much of a gurantee it gives for file operations. And there would
still be directory operations to worry about.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Atomicity under Windows
Posted by Paul Marculescu <pa...@p16.pub.ro>.
Greg Hudson wrote:
>
> On Unix, you have some basic tools available for local filesystems:
>
> * fsync() provides the basics of failure atomicity by guaranteeing
> that a file's contents have been flushed to disk. (With some
> fileystems, you may also have to fsync() directories in order to
> make sure that directory entries are flushed to disk; with others,
> fsync()ing a file guarantees that all paths referencing the file
> have been flushed.)
The dwFlagsAndAttributes parameter in CreateFile() can have a value of
FILE_FLAG_WRITE_THROUGH which urges the system to go directly to disk.
Note that CreateFile() does much more things than _creating_ files. :)
HANDLE CreateFile(
LPCTSTR lpFileName, // file name
DWORD dwDesiredAccess, // access mode
DWORD dwShareMode, // share mode
LPSECURITY_ATTRIBUTES lpSecurityAttributes, // SD
DWORD dwCreationDisposition, // how to create
DWORD dwFlagsAndAttributes, // file attributes
HANDLE hTemplateFile // handle to template file
);
>
> * rename() is both failure-atomic and concurrency-atomic; either the
> rename has happened or it hasn't. There is no in-between state
> where the target doesn't exist. (You can't get this for
> directories, incidentally.)
BOOL MoveFileEx(
LPCTSTR lpExistingFileName, // file name
LPCTSTR lpNewFileName, // new file name
DWORD dwFlags // move options
);
If you specify MOVEFILE_REPLACE_EXISTING in the flags, this function
will act like the UNIX rename().
MOVEFILE_WRITE_THROUGH - the function will return only after the file
has actually been moved on the disk.
However there is a rename() function under Windows too, but I couldn't
find anything about its atomicity in MSDN.
>
> * open() with the O_CREAT|O_EXCL flags will fail if the file already
> exists; you can use this to create unique files or do rudimentary
> locking.
CreateFile has a tone of options and flags and dwCreationDisposition can
have the following values:
CREATE_NEW
CREATE_ALWAYS
OPEN_EXISTING
OPEN_ALWAYS
TRUNCATE_EXISTING.
>
> * fcntl() can create advisory locks on files, when the above two
> approaches aren't sufficient for concurrency atomicity. fcntl()
> locks are convenient because they are automatically cleaned up if
> the locking process dies or the machine reboots. You can also use
> it to do locking over subranges of a file.