Subject: RE: leases revisited was RE: Some issues with stateid's

From: "Noveck, Dave" <[email-masked]>
Date: Wed, 17 Nov 1999 08:14:23 -0800

> 
> > I was assuming that OPEN and CLOSE are considered locking 
> > requests because share reservations are locks, etc.  OPEN
> > does have a seqid4 which I assumed was for that purpose.
> > On the other hand, I've just looked at CLOSE and it doesn't
> > have a sequence number so I don't know what to think (Other
> > than things need to be clarified).
> > 
> > If we decide that OPEN and CLOSE do not need to take part
> > in the sequence logic (and that might depend on how we
> > resolve the issue of whether there can be multiple open
> > for the same file and lockowner at the same time), then
> > I still have concerns about whether sequencing can be
> > reset when a lockowner has no locks.
> > 
> > I guess it depends on what the sequence logic is intended
> > to prevent.  It is intended only to deal with at-most-one
> > semantics for retries, then this resetting might work.
> > The problem is that in other cases (changng stateid's
> > for example) we have used something I'll call the 
> > Byzantine Router Test.  We assume that a nasty router 
> > has held onto a request for a long time (re-ordering
> > across a very large span of messages) and send the
> > delayed request just at the wrong time.  If we want
> > to be safe against this, then you can come up with
> > scenarios that violate at-most-once semantics.
> > 
> >     OPEN a file.
> > 
> >     Do a lock with sequence zero (Router holds onto some
> >     instance of that at is successfully retried).
> > 
> >     Do an unlock with sequence one.
> > 
> >     Do a CLOSE
> > 
> >     Do an open of the same file.
> > 
> >     Router disgorges saved LOCK request which is erroneously
> >     acted on.
> > 
> > Maybe this isn't an issue but we have made (and accepted)
> > arguments of this form in the past.  The logic that requires
> > stateid's to change so that a delayed WRITE is not erroneously
> > acted on past an unlock that invalidates it is exactly of
> > this form.
> 
> Dealing with the Byzantine Router is a very hard problem.  
> The only way
> to deal with it is to maintain state forever.  Consider the case where
> it is the initial OPEN on the initial contact to a server, the server
> has no state so it must accept the request.  If the BR 
> retransmits this
> request in the future it may be hard to defend it, probably can. Then
> consider a server reboot with the same BR, it needs to defend against
> all possible requests that ever got from that client which is an
> unsolveable problem (run out of storage and seqid space).

If we need to solve this problem, I think we could not
automatically accept things with seqid zero just because
we didn't know about the lockowner.  I think all sequence
streams that were transient would have to be created
and destroyed explicitly and named by something stateid-like
(an ownerid).  All such creation and deletion requests
would have to be sequenced using a global (permanent)
sequence stream.  To deal with reboots, you'd have to 
add additional verifiers to anything in the global 
sequence stream.

I don't think this is unsolvable but it probably is unsolvable
in the time we have.

> 
> I think we have to accept the possibility of rogue requests 
> and recommend
> that servers do their best to defend against them, however there will
> be an upper bound similar to defending against duplicate XIDs.

In most cases, TCP will be used and that will be adequate 
protection.

Maybe we should say: If you use Byzantine (tm) routers, you
MUST use TCP as a transport. :-)

So we're coming to a resolution that says that the sequence
id is to be reset when a given lockowner has no locks
(including opens as a species of locks).  This would
provide non-BR at-most-once semantics.  

The only isses that I still have with this have to do with
the final request in a sequence, the one that unlocks the
last lock or does the last close (and is cause the server
to forget all about the lockowner).

I would simply avoid the first case and say you have to
get rid of the record locks before you do the CLOSE.
I think the spec now says the the server may give you
an error if you do a CLOSE while you still have locks.
I would change this to having required to give you an
error and require the client to do the unlocks first.
This means that a LOCKU cannot be the final request
in a sequence stream so it is ok as far as (non-BR)
at-most-once semantics.

This leaves CLOSE.  It doesn't have a seqid currently
and if it did, the fact that the server would throw
the information away would be a problem.  As it stands,
a retransmitted CLOSE would be rejected with a bad
stateid.  Most servers will have a reply cache so the
question is whether we need an additional level of 
protection against retransmission issues.  I'm inclined
to say "no".

> I am starting to believe that multiple OPENs with the same lockowner
> is going to be more trouble than it is worth.  If instead we allow
> an OPEN to upgrade/downgrade an existing OPEN with a single CLOSE
> terminating the state it pushes the multiplexing back to the client
> where it is more easily handled. The seqid can be used to guarentee
> ordering but with the above caveat, the server can timeout and saved
> lockowner within some reasonable amount of time (N * lease interval?).

I think multiplexing is reasonable as long as we have some
way to do upgrade/downgrade.

In thinking about OPEN and how multiple OPEN's are handled,
let's think about a couple of cases.

Suppose a process opens A/B for read, and then suppose it
opens A/C for write.  The two opens may or may not be of
the same file (because of hard links or an intervening
rename), so what happens if they turn out to be opens 
of the same file.  The normal expectation would
be that the write access overwrites the read access 
(thsi would allow upgrade and downgrade to be easily
specified) but in't what you want in this case.  You'd
like the server to merge in the write access bit and now 
have a read-write open but how can the desired behavior
be clearly defined?  Note that the client isn't yet 
aware that this is an upgrade.  How does he find 
out?  He could look at the filehandle and compare.  
There are issues with multiple filehandles for 
the same file which I'll discuss below.  If the
filehandle compare works, then the client can figure 
our that his two opens are joined and that when a
close is done he really has to do an OPEN(!) to
adjust the access for the file.  If A/B is closed
then he has to downgrade from read-write to write
and if A/C is closed then he has to downgrade
from read-write to read.  The problem is OPEN
makes him specify a filename which may not be
valid because of a subsequent rename.  I think
downgrade should probably be a separate operation
which takes a filehandle rather than a name.
Upgrade makes sense being included with OPEN
because the client may not know it's an upgrade
until after the request completes.

If we change the above, so that A/B and A/C are
both opened for read, then the open of A/C won't
be an upgrade; it will be a no-op.  I think that
the same multiplexing logic can deal with it.
The client sees that the filehandle matches (after
doing the OPEN) and thus he has to increment 
a count of opens for that acess type-lockowner-file 
triple. When the close is done, that count is 
decremented and since it is non-zero, no OPEN,
CLOSE, upgrade or downgrade need be done.

Now if the process does two opens of A/B, what
happens on the second one.  I believe that in
the absence of delegation, the second open has
to go to the server because we don't know that
A/B is the same file we have open.

I think multiplexing can work but the client isn't
going to know that he is multiplexing on the OPEN
side until after he has done the OPEN.

There is an issue with servers that designate the
same file by multiple handles.  The client does not
have a guaranteed way to determine whether two
handles designate the same file.  I think the spec
should say that if a server does this, it may not 
treat an OPEN done on one file handle as an 
upgrade of an open done on another filehandle,
even though they may designate the same object.
If it has multiple handles for the same object 
than it has to maintan separate open status for
each.

> 
> > >From the Unix point of view, it has the file open and it
> > is entitled to do the locking.  If the client file system
> > has to do an OPEN to effect this, this would be OK, except
> > that the OPEN can fail (file could have been renamed).
> 
> The client is responsible for recreating the OPEN, typically this
> would be hid from the application.  If a failure occurs then that
> may happen and the child gets and error.  The alternative is to have
> the server try and handle multiple threads and handle one app doing
> a CLOSE, or grabbing new locks (should it use the old or new 
> lockowner,
> how does it distinguish requests if it is the same...?) This 
> just seems
> too hard for a server to deal with and easier for the client.

This is really more an issue for those on the client side that
are going to have to deal with applications that run into
this.  

What we would be saying is that if you are the child in 
a fork() you can't get record locks if the name of the 
file has changed (unless the client can figure out what 
is has changed to).  Is this too weird to worry about?  
This works on a local file systems OK and I'm guessing 
that people will run into this.  Murphy's Law says it
will be an absolutely critical application, that for 
tons of reasons can't be chnged to work some other
way.

I think this can be dealt with by a new operation that
clones an already existing open from one owner to
another.  It would take a filehandle and two lockowners
and produce a stateid.  The problem that this would
solve is not that big but I don't see that this
is big thing to implement either.
 
> > OK.  But when you start running out of bits, just remember, you
> > had the chance to expand this.
> 
> I'll open this question up to the rest of the WG, is an additional
> 32 bits a concern to anyone? I am really neutral on this.

Here's my reasoning:

     If you think a fixed limit is probably OK, then it won't
     be OK.

     If you are absolutely, positively sure that a fixed limit
     is OK, it may be OK.

     I think a limit of 64 bits is probably OK, therefore it 
     won't be OK :-)

---

From: Neil Brown <[email-masked]>
Date: Thu, 18 Nov 1999 11:17:49 +1100 (EST)

> > unsolveable problem (run out of storage and seqid space).
..
> I don't think this is unsolvable but it probably is unsolvable

I've been thinking about the Byzantine Router (BR) problem (I like that
name) a lot lately, and there are some interesting issues, some of
which I will save for later emails.

However I think that maintaining reliable state agreements is quite
solvable.  As Mike suggested, TCP already does it, though the
connection only occurred to me in hind sight.

Firstly, I would like to invent a new word.  I find it very helpful to
have words for important concepts as it helps to understand them and
to talk about them.  I think the word I want is "agreement".
Currently, we have a "stateid" which changes with every lock/locku etc
request for a particular file/lockowner.  So there is a sequence of
states, each with a stateid. I want a word that means a sequence of
states.  I choose the word "agreement".

So an agreement is created in response to an OPEN, and it lapses
.. sometime.  Possibly when the agreement reaches an empty state,
possibly on a CLOSE.
There is another sort of agreement, which is represented by a clientid.
It is, you might say, a container agreement in that it just sets the
stage on which other agreements can be made.
I will call this a 'client agreement' to differentiate it from the
'file agreement'.  They are agreements about different things, but
they are similar in that they have a 'state' represented by a stateid
or clientid.

As I have suggested before (in different words) if we change the state
of the client agreement everytime a subordinate file agreement lapses
then we have a guarantee against the BR creating unintented file
agreements (as a new OPEN request will either present an old state of
the client agreement or will conflict with a current file agreement).

However, that doesn't protect against a BR creating an unintended
client agreement by resending a delayed SETCLIENTID after a server has
restarted.

This is where the TCP analogy comes in.  TCP has a "three way
handshake" to establish sequence numbers.  The important part of this
is that the server give the client a sequence number which the client uses to
verify its sequence number to the server (that may be a bit vague, but
I think it is close enough).

So we need one more super-agreement which is a server agreement. This is
represented by a sequence of serverids which are unique over time for
a given server.
The process of getting a client id becomes two operations:
    GETSERVERID: - -> serverid
    SETCLIENTID: clientidentifier clientverifier serverid -> clientid

The SETCLIENTID only succeeds if the serverid is still valid as well
as current rules for SETCLIENTID about changing verifier and
same credential.

The server guarantees to change its serverid if a client agreement
ever expires, which means atleast at restart, and possibly other times
when client agreements become void (can the server ever forget a
clientid in the current protocol?).

This requires the server storing a very small datum to stable storage
occasionally, essentially the same as /var/statmon/state.

This gives you a hierarchy of agreements.
      server / client / file
with the file agreement changing state when real work happens like
files being locked etc, and the upper level agreements changing state
whenever a lower level agreement lapses.

Whether this is all too much to worry about I'm not sure but if we
admit that out-of-order deliver is possibly, then we must either deal
with all of it, or make it clear exactly how much can be dealt with
(e.g. deal with delivery delays of 30 seconds, no more - this would
simplify things a lot).
The alternative is to require a transport that assures there will be
no out-of-order delivery.  This would make state handling much simpler
(by pushing the problems down) but might hurt concurrency(?) and might
be politically incorrect(?).

Then there is the lockowner agreement.  I still have a big problem
with lock owners, but everybody else seems to like them, so I guess I
go with the flow.  It  fits between client and file agreements.
Dave Noveck's {CREATE,DESTROY}_OWNER idea relates to this.  Taking the
same names, but modifying their meaning somewhat, the way I would do
{CREATE,DESTROY}_OWNER would be to see the agreement hierarchy as
      server / client / lockowner / file 
You need a serverid to create a client agreement,
 a clientid to create a lockowner agreement (CREATE_OWNER) and
 a lockownerid (instead of clientid) to create a file agreement.

Each agreement (except server which is special) can be terminated by a
TERMINATE-AGREEMENT operation (== CLOSE or DESTROY_OWNER or
destroy_client?) which terminates all subordinate agreements (and
releases all locks) and as a side effect terminates any aborted
locking requests.
All this without depending on sequenceids (if you will allow that a
failed lock request returns a new stateid. Would you allow that?).

Dave Noveck has worried about the need for single-threading the
TERMINATE-AGREEMENT operation (or equivalents) with respect to
CREATE-AGREEMENT operations (OPEN in particular).

If this is a real issue, then the server can be a bit more generous
about what agreementid it allows in a create-agreement style operation.
It can keep a list of the last few (dozen?) agreementids for each
active agreement, together with the entity name
(client/lockowner/file) of the entity that had its agreement
terminated with that state change.
Then an OPEN (etc) succeeds if it is accompanied by a current
lockownerid, or a recent lockownerid where the server knows that no
CLOSE has been performed on that file since the recent lockownerid was
current.
(I hope I made sense there)

Actually, given that presentation of lockowners, I am beginning to
like them a bit.  A delegation agreement would be like a file
agreement, but would be subordinate to a client agreement instead of a
lockowner agreement.  I could draw of a picture of that, which makes
me a lot more comfortable.

NeilBrown

>      I think a limit of 64 bits is probably OK, therefore it 

16 bits to differentiate between server restarts.
24 bits to differentiate between concurrently open files.
24 bits to differentiate between consecutive states of an open file,
   and conseutive uses of an open-file slot by different files.

I would be happy with that (but happier with statehandles that were a
subtype of filehandles:-)

NeilBrown