Concurent state file manipulation with multiple pr

Question

The question below may sound a bit long and complex, but actually it's a quite simple, generic and common problem of three processes working on a same file. In a text below I'm trying to decompose the problem into set of particular requirements with some illustrative examples.

Task preamble

There is a text file, called index, which contains some metadata.

There is an application (APP), which understands the file format and perform meaningful changes on it.

The file is stored under version control system (VCS), which is a source of changes performed on the same file by other users.

We need to design an application (APP), that will work with the file in a reasonable file, preferable without interring much with VCS, as it's assumed that VCS is used to keep a large project with the index file being just a small part of it, and user may want to update the VCS at any point without considering any ongoing operations within APP. In that case APP should gracefully handle the situation in a way preventing any possible loss of data.

Preable remarks

Please note that VCS is unspecified, it could be perforce, git, svn, tarballs, flash drives or your favourite WWII Morse-based radio and a text editor.

Text file could be binary, that doesn't change things much. But with VCS storage in mind, it's prone to be merged and therefore text/human-readable format is most adequate.

Possible examples for such things are: complex configurations (AI behaviour trees, game object descriptions), resource listings, other things that are not meant to be edited by hand, related to a project at hand, but which history matters.

Note that, unless you are keen to implement your own version control system, "outsourcing" most of the configuration into some external, client-server based solution does not solve the problem - you still have to keep a reference file within version control system with a reference to a matching version of configuration in question in the database. Which means, that you still have the same problem, but at a bit smaller scale - a single text line in a file instead of a dozen.

The task itself

A generic APP in vacuum may the index in three phases: read, modify, write. The read phase - read and de-serialize the file, modify - change an in-memory state, write - serialize the state and write to the file.

There are three kind of generic workflows for such an application:

1. read -> <present an information>
2. read -> <present an information and await user's input> -> modify -> write
3. read -> modify -> write

The first workflow is for read-only "users", like a game client, which reads data once and forgets about the file.

The second workflow is for editing application. With external updates being rather rare occurrence and being improbable that user will edit the same file in few editing applications at the same time, it's only reasonable to assume, that a generic editing application will want to read the state only once (especially if it's a resource-consuming operation) and re-read only in case of external updates.

The third workflow is for an automated cli usage - build servers, scripts and such.

With that in mind, it's reasonable to threat read and modify + write separately. Let's call an operation that makes only read phase and prepares some information a read operation. And a write operation would be an operation that modifies a state from a read operation and writes it to the disk.

As workflows one and two may be running at the same time by different application instances, it's also reasonable to allow multiple read operations running at the same time. Some read operations, like reads for editing applications, may want to wait until any existing write operations are finished to read the most recent and up-to-date state. Other read operations, like this in a game client may want to read the current state, whatever it is, without being blocked at all.

On other hand, it's only reasonable for write operations to detect any other write operations running and abort. Write operations should also detect any external changes made to the index file and abort. Rationale - there is no point to perform (and wait for) any work, that would be thrown away due to the fact that they've been made basing on a possible out-of-date state.

For a robust application, a possibility for a critical failure of a galaxy scale should be assumed at every single point of an application. Under no circumstances such a failure should left the index file inconsistent.

Requirements

1. file reads are consistent - under no circumstances should we read a half of a file before it have been changed or an another half after.
2. write operations are exclusive - no other write operations are allowed at the same time with the same file.
3. write operations are robustly waitable - we should be able to wait for a write operation to complete or fail.
4. write operations are transactional - under no circumstances should the file be left in partially changed or otherwise inconsistent state or based on an out-of-date state. Any change to the index file prior or during the operation should be detected and operation should be aborted as soon as possible.

Answer 1

In Linux, you can also use mandatory file locking.

See "Semantics" section:

If a process has locked a region of a file with a mandatory read lock, then other processes are permitted to read from that region. If any of these processes attempts to write to the region it will block until the lock is released, unless the process has opened the file with the O_NONBLOCK flag in which case the system call will return immediately with the error status EAGAIN.

and:

If a process has locked a region of a file with a mandatory write lock, all attempts to read or write to that region block until the lock is released, unless a process has opened the file with the O_NONBLOCK flag in which case the system call will return immediately with the error status EAGAIN.

With this approach, the APP may set read or write lock on file, and VCS will be blocked until lock is released.

---

Note that neither mandatory locks, nor file leases will work good if VCS can unlink() index file or replace it using rename():

• If you use mandatory locks, VCS won't be blocked.
• If you use file leases, APP won't get notification.

You also can't establish locks or leases on a directory. What you can do in this case:

• After read operation, APP can manually check that file still exist and has the same i-node.

• But it's not enough for write operations. Since APP can't atomically check file i-node and modify file, it can accidentally overwrite changes made by VCS without being able to detect it. You probably can detect this situation using inotify(7).

Answer 2

Linux

A read operation:

1. Obtain a shared lock, if requested - open(2) (O_CREAT | O_RDONLY) and flock(2) (LOCK_SH) the "lock" file.
2. open(2) (O_RDONLY) the index file.
3. Create contents snapshot and parse it.
4. close(2) the index file.
5. Unlock - flock(2) (LOCK_UN) and close(2) the "lock" file

A write operation:

1. Obtain an exclusive lock - open(2) (O_CREAT | O_RDONLY) and flock(2) (LOCK_EX) the "lock" file.
2. open(2) (O_RDONLY) the index file.
3. fcntl(2) (F_SETLEASE, F_RDLCK) the index file. - we are only interested in writes, those RDLCK lease.
4. Check if the state is up-to-date, do things, change the state, write it to a temporary file nearby.
5. rename(2) the temporary file to the index - it's atomic, and if we haven't got a lease break so far, we won't at all - this will be a different file, not the one we've got the lease on.
6. fcntl(2) (*F_SETLEASE, F_UNLCK) the index file.
7. close(2) the index file (the "old" one, with no reference in the filesystem left)
8. Unlock - close(2) the "lock" file

If a signal from the lease is received - abort and cleanup, no rename. rename(2) has no mention that it might be interrupted and POSIX requires it to be atomic, so once we've got to it - we've made it.

I know there are shared-memory mutexes and named semaphores (instead of an advisory locking for cooperation between application instances), but I think we all agree, that they are needlessly complex for the task at hand and have their own problems.

Windows

A read operation:

1. Obtain a shared lock, if requested - CreateFile (OPEN_ALWAYS, GENERIC_READ, FILE_SHARE_READ) and LockFileEx (1 byte) the "lock" file
2. CreateFile (OPEN_EXISTING, GENERIC_READ, FILE_SHARE_READ) the index file
3. Read file contents
4. CloseHandle the index
5. Unlock - CloseHandle the "lock" file

A write operation:

1. Obtain an exclusive lock - CreateFile (OPEN_ALWAYS, GENERIC_READ, FILE_SHARE_READ) and LockFileEx (LOCKFILE_EXCLUSIVE_LOCK, 1 byte) the "lock" file
2. CreateFile (OPEN_EXISTING, GENERIC_READ, FILE_SHARE_READ | FILE_SHARE_WRITE ) the index file
3. ReadDirectoryChanges (FALSE, FILE_NOTIFY_CHANGE_LAST_WRITE) on the index file directory, with OVERLAPPED structure and an event
4. Check the state is up-to-date. Modify the state. Write it a temporary file
5. Replace the index file with a temporary
6. CloseHandle the index
7. Unlock - CloseHandle the "lock" file

During the modification part check for the event from the OVERLAPPED structure with WaitForSingleObject (zero timeout). If there are events for the index - abort the operation. Otherwise - fire the watch again, check if we are still up-to-date and if so - continue.

Remarks

1. Windows version use locking instead of Linux version's notification mechanism, which may interfere with outside processes making writes, but there is seemingly no other way in Windows.