Subject: RE: idea - atomic append for NFS writes

From: Mike Eisler <[email-masked]>
Date: Fri, 16 Mar 2001 10:09:12 -0800 (PST)

>From: "Noveck, Dave" <[email-masked]>

>> As Peter points out, atomic appends are probably (I say probably,
>> because it hasn't been proven they can't be done, its just that every
>> proposal has been found to have holes) impossible, although if the
>> server has delegated write capability to the client, as long as the
>> delegation is in force, appends come for free.
>
>In that case, they are essentially local writes.
>
>I'm not sure that I'm prepared to give up on append writes yet.

Ah, new blood on the problem! I wish you luck.

>> The use of a COMPOUND with VERIFY (file size) followed by WRITE comes
>> close, but because there's no atomicity guarantee between operations,
>> it comes up short. Still, it might be a good idea for NFS client's
>> simulating append to use VERIFY to reduce corruption during
>> write sharing. But it's early (for me) this morning, and I'm
>> probably missing something.
>
>I may not be understanding exactly the form of COMPOUND you are
>anticipating using, but it seems that COMPOUND with VERIFY is subject
>to exactly the same issue that you identified with Mark's proposal:
>duplicate records even in the absence of sharing.  If I do a GETATTR
>of the file size and then do a VERIFY-WRITE compound, then if the
>verify fails I am going to loop back and do another GETATTR followed 
>by a VERIFY-WRITE assuming that somebody else got his record in before 
>me.  But in the presence of retries, it may have been that the WRITE 
>that got in was an earlier instance of *my* VERIFY-WRITE which succeeded, 
>so the second retry (actually the first retry after the initial try)
>fails in the VERIFY and I go off to write my record  again.  Since, 
>in this mode of operation I'm doing twice as many requests as in 
>Mark's proposal, I'm going to hit the problem even earlier.

Like I said, I was probably missing something. APPEND is simply hard.

>I know I'm being heretical here, but I'm beginning to think that NFS
>may be at the point of exhausting the universe of things that can be
>done effectively with at-least-once semantics.  Unless we are prepared
>to keep giving people things (like append writes) that work most of
>the time and tell them to stop complaining, we may have to bite the

I'm not sure I've ever had a customer complaint about appends not
working. 

>bullet and solve the general problem.
>
>     Exactly-once Semantics -- Accept No Substitutes

Maybe The Open Group and IBM will open the DCE/DFS protocol
specifications and source code. :-)

	-mre

---

From: Neil Brown <[email-masked]>
Date: Tue, 20 Mar 2001 15:08:29 +1100 (EST)

> Ah, new blood on the problem! I wish you luck.

Can I try please????

A lot of what I am going to say has been mentioned here and there
through the discussion, but I will try to tie it together.

What we need to do reliable append writes is atmost-once semantics.
There are two ways that atmost-once is currently achieved in the
protocol and it is worth looking at those to see what can be learnt.

The first is exclusive create.
The basic mechanism for exclusive create is:

   client provide a unique cookie with the request.
   Server stores the cookie with the result of the request at least
     until the client indicates that is knows that the request
     has completed.
     If a request arrives that has a cookie the same as the stored
     cookie, the server responds as though the request has succeeded,
     but without doing anything.

For exclusive create, the cookie is stored in the inode and the client
indicates knowledge of completion by sending a SETATTR request.

The analogue for write-append would be for there to be a WRITE_APPEND
command which included a cookie.  The server would need to remember a
number of cookies for each file that was being appended to.
As Dave Noveck suggested, a seqid could be part of this cookie. 
The client could indicate knowledge of completion by using the next
seqid in some request.
This would work fine as long as the server didn't restart.
To cope with restart, the server would need to record all the cookies
to stable storage, and this would probably be prohibitive.

Still, server restarts aren't very common, and the worst case scenario
in that face of restart would be that a few entries would be appended
multiple times. So

  WRITE_APPEND: (cfd) count, stateid, seqid, data -> count

could be part of an answer, though it has problems which have been
discussed (like forcing synchronous writes even when there isn't any
sharing).

The second mechanism for atmost once semantics in the current protocol
is the maintaining of client state on the server, and stateids and
seqids and all that.  This mechanism has a facility for surviving
server restarts without storing excessive state to stable storage, and
so could be superior than the first mechanism in that sense.

It has been suggested that locking could be used to ensure proper
append writes, but I don't think that this is the case because locking
is only advisory, so it is quite possible to write without the lock,
and in particular, a process on the server could append to the file,
assuming atomic append semantics, but not getting involved in locking
at all.

The other use of client-state, delegation, has been mentioned, and I
think they hold the answer.

If a server can implement write delegations, then it must have some
way to stop local processes from appending while the delegation is in
force, and so delegations can be used to implement atomic writes.

Ofcourse, a server doesn't have to support delegation, nor does it
have to grant them in any particular cirumstance, so there needs to be
a fall back.  That would be the WRITE_APPEND op.

So this is how I see atomic append working.

When a process on the client writes to an O_APPEND file, the data is
cached locally, and the record boundry is kept.  The client does not
necessarily have to flush the data to the server instantly, though it
may.
It must flush to the server:
  1/ on fsync or close (or sync ...)
  2/ before any read on the file that might go past the currently
     known end-of-file
  3/ before any non-append write request on the file.
  4/ befor any truncate.
  5/ possibly other similar situations.

When the client decides that it will write some data to the file, it
first use a request:
    OPEN append
    GETATTR size

The "append" flag gets squeezed into OPEN somehow, it isn't important
how.  As the client will already have the file open, this will, in
effect, upgrade the open to also have the "append" flag.
In this situation, the server is "strongly encouraged" to grant a
write delegation, though it may set the "recall" flag in the response
to say the the client should return the delegation as soon as
possible.

If the client gets a delegation, it issues normal write requests.
If it got the "recall" flag, then in the last write request, it
includes a DELEGRETURN and maybe an OPEN_DOWNGRADE to remove the
"append" bit. 

If the client doesn't get a delegation, then it sends WRITE_APPEND
requests as described above, making sure to honour the record boundry
is multiple write-append requests have been cached-behind.

If the server restarts while the delegation is in force, then the
normal recovery process makes sure the append is effectively atomic.
If the server restarts after completing the WRITE_APPEND, but without
the reply getting to the client, then there will be a small amount of
duplication in the log (so complain to the server vendor and ask for
delegations). 

Ofcourse, the client could respond to lack-of-delegation, by just
acting as current NFS does and hoping that it doesn't matter.  Maybe
that could a client configuration option.

If there is only one client appending to a particular file, it will
hopefully get a non-recalled write delegation and can write-behind to
it's hearts content.

Each append would require two round-trips if a standing delegation
could not be granted.  This is slower than normal writes, but you
would expect there to be some cost.

NeilBrown