Subject: Re: Stateid and seqid

From: Neil Brown <[email-masked]>
Date: Mon, 5 Feb 2001 11:53:56 +1100 (EST)

On Tuesday January 30, [email-masked] wrote:
> > 
> > I have a very clear idea in my head as to how it could be done.  I
> > tried to present in on the list a while ago (over a year a think) but
> > I didn't get much (or any) response.  I'm happy to try again if anyone
> > is interested.
> 
> Go ahead and run it by us again.  With some implementation experience
> behind us, we may view your proposal differently.  Though I recommend you
> preface your proposal with the reasons why the current state model
> is flawed.
> 
> 	Brent

Hmmm... you don't make it easy :-)  It is much harder to show why a
model is flawed than just to assert that it is, but it is certainly a
fair question and I will do my best.

What I will try to do is:
 1/ present a model for how state-maintenance can/should/does work.
    This model will be motivated by the current spec, but kept as
    minimal as possible.
 2/ describe how the current protocol maps to the model.  This should
    both aid in the understanding of the protocol, and show the
    problems that I see in the protocol.
 3/ Present an alternate protocol for state management that is a
    better fit for the model.

I should say from the outset that I'm not asserting that the protocol
is flawed in the sense that it cannot communicate the information that
needs to be communicated.  I am fairly sure that the protocol atleast
comes extremely close to being able to communicate successful.
My problem with the protocol is that I find it very hard to go that
extra step from from "extremely close" to "definately there", and I
believe this is due to lack of a clear abstract model to use when
reasoning about the protocol.

It could be that providing a clear model and a clear description of
how the protocol fits that model will be enough to make the protocol
easy to work with -  Dave Noveck suggests that possibility in a recent
Email.   I will leave it to the reader to judge on that issue.

Enough pre-amble - on to some real detail.

-------------- The Model -----------------------------

What is state:
 
   The area of the protocol that I dealing with here is state
   management.  The server maintains a certain amount of state on
   behalf of clients, and it is critical that the servers view of the
   state remain consistant with the clients view of the state despite
   an imperfect communication channel (Allowing loss, deuplication,
   and re-ordering).  The protocol needs to assure this consistancy.

   The basic elements of state are things like locks and share
   reservations.  I am not particularly interested here with what
   state can be recorded, or what state transitions are allowed, but
   only with how those state transitions are communicated and
   confirmed. 

   It is clear from the NFSv4 RFC that the basic unit of state
   maintenance known to the protocol is the "openfile" (my term).
   An "openfile" is a particular reference by some client to a
   particular file.  It is certainly the case that different clients
   may each reference the same file and maintain different state
   (different locks) on that file.  It may also be the case that one
   client could maintain multiple references to the one file, though
   this possibility would need to be justified (later).

   It is, I think, worth noting that the basic element of state could
   be chosen to be bigger or smaller.  We could, for example, treat
   all locks on all files held by a particular client to be a single
   unit of state. Alternately we could consider each byte of each file,
   which may be locked independantly, to have it's own element of
   state.  The "openfile" is the unit using in the current spec, and I
   believe it is a good one, so we will start there.

   There is some value in treating number of related elements of state
   as a single large state for certain purposes.  For example, the
   current spec considers all openfiles associated with a particular
   client to be a single object for the purposes for lease extension,
   and for discarding old state when it is confirmed that a client has
   failed.  Thus we have atleast two levels of state.

   The RFC indicates two other levels of state.  One that is not
   explicitly spelled out, but is there implicitly, is the "server"
   level.  The total state maintained on a server sometimes needs to be
   treated as a whole, such as to describe what is lost on server
   restart. The other level described in the RFC is the "lockowner"
   level. This level goes between the openfile and the client, in that
   each openfile is owned by a lockowner, and each lockowner is owned
   by a client.

   This is, I think, sufficient justification to treat state as
   hierarchical.  There is a clear hierarchy of state elements:
   server, client, lockowner, openfile where the state of an time at
   each level is wholely contained in the state of its parent at the
   preceeding level.

How is state managed:

   State is stored on the server.  While the client will keep it's own
   records of the current state, the state stored on the server is
   authoritative. 
   
   In general, state transitions happen as a direct result of a
   request by the client - e.g. "LOCK" or "OPEN".  It is possible,
   though comparatively rare, for state transitions to be effected
   independantly be the server.  This can happen, for example, in the
   case of lease expiry, or server admin intervention (section 8.7)

   The particular goal for the state management protocol is to ensure
   that the client and server both know when a state transition has
   occurred, and that the both know that the other knows.

   Considering only the client initiated transitions for now, the
   client is only uncertain of the server's state between when it sends
   a request, and when it receives a reply.  To provide the needed
   guarantees we require that the client either:
      1/ persist with any request state-changing until it gets a reply
        (as in section 8.6)
   or
      2/ accepts complete loss of state on the server - in the event
         of losing contact with the server.

   The server's period of uncertainty about the client's view of state
   is between sending a reply and getting some new request that in
   some way confirms that the client received the reply.  For the
   server to become certain about the clients view, there needs to be
   some way for the client to confirm reply.  The model presented in
   the RFC (which I believe is a good one) is to use a "cookie" (my
   term) to represent a particular state.  The architypal cookie in
   the spec is the stateid.

   The minimal detail required of this cookie is that
    1/ from the server's response, the client can deduce a new cookie.
    2/ in subsequent requests the client can show that it has the new
       cookie.

   Note that this does not require the literal cookie to appear in
   responses and requests, though that is certainly an obvious
   implementation.  An alternate implementation would be a universal
   sequence number. The client includes the sequence number in
   requests - satisfying 2, and the client increments it whenever it
   sees a new response from the server - satisfying 1.  This would
   work for the current purpose, but has other negative implication
   for the protocol (total serialisation).

   The "cookie" is shorthand for a particular state.  Whenever there
   is a new state, there must be a new cookie.

   For server-initiated state changes, the client can find out that
   something has happened by receiving a failure status for a request
   with a cookie that is no longer valid.  The spec isn't clear on
   exactly how the client informs the server that it has figured out
   the new state.  I think that the neatest approach is that the
   client should send unlock/close requests to release any state that
   is in question, and that in these requests, old cookies should be
   accepted. 

   Ok, it took a little while to get here, but we now have an
   hierarchical state and a cookie for state confirmation.

State transitions:

   There are three sorts of state transitions that we need to
   consider:
    1/ creating a new state
    2/ modifying a state
    3/ discarding an old state.

   For each of these, we need to understand:
    A/ what cookie must be presented by the client to convince the
       server that the client and server views of state are sufficiently
       consistant.
    B/ what cookies get changed or created and how are these returned.

   I will assert the answers to these questions and leave the
   justification to when I compare the model to the current protocol.

   When creating a new state, the cookie for the parent state must be
   presented, and a new cookie is created and returned for the new
   state.  The cookie for the parent state doesn't change.

   When modifying a state, the cookie for that state must be presented
   and a new cookie for the new state is returned.  Note that only the
   bottom level of state can be directly modified.  Higher levels are
   modified by creating/deleting a lower level state.

   When deleting a state, the cookie for the state and the parent
   state must be presented, and a new cookie for the parent state is
   returned.

   Each of the above assumes that the request succeeds and that the
   state transition happens.  Indeed, at this level of abstraction, we
   must assume that every request either:
    1/ will always result in failure (e.g. protocol violation) or
    2/ does cause a state transition.  It may not be the state
       transition that was requested, but there must be a new cookie,
       so that both the server and client can be sure that they agree
       on the result of the request.  
   As we shall see later, it is easy to include a light-weight
   component to each cookie to accomodate the trivial state change of
   "another request failed".

   Also, the above does not cope with describing the creation of a new
   server or the destruction of a new server.  These are not really
   relevant to the client, and hence to the protocol, except that the
   client needs to get a cookie for the server to use when creating or
   destroying a client.  For this, we simply need a way for the client
   to ask the server for a current cookie.

   So that is basically the model: hiearchical state, cookies, and
   rules for cookie handling on state transition.

---------------------- The current protocol  ----------------------------

  We will examine the current protocol by looking at the different
  objects at the different level in the hierarchy, and look at what
  sort of cookie they have and how it is communicated.

  The protocol defines four levels of state: server, client,
  lockowner, openfile.

  Server:
   Server creation and deletion is not part of the protocol.
   The "cookie" for the server state is  effectively the
   setclientid_confirm verifier that the SETCLIENTID operation
   returns.  More discussion of this below.

  Clients:

   A client is created by a SETCLIENTID operation followed by a
   SETCLIENTID_CONFIRM operation.
   This is very similar to the "get server cookie" followed by "create
   client given a server cookie" approach that the model suggests. 
   The setclientid_confirm value serves adequately as a server cookie.

   A client cannot be explicitly deleted in the protocol, except by
   creating a new client with the same cookie but a different verifier. 
   Rather the server is allowed to delete client state after it hasn't
   heard from the client for a while

   The clients "cookie" is, as a first approximation, the clientid
   returned by SETCLIENTID, though it should be clear that this
   doesn't quite meet the needs of a cookie, because a cookie must
   change when a child state is deleted, but a clientid never changes.
   We will address this issue at a lower level of the protocol.

  Lockowner:

   Object Creation:

    A lock-owner is created by the OPEN_CONFIRM operation which follows
    an OPEN operation which tried to use a non-existant lockowner (or
    possibly by an OPEN operation which is received before the server
    has discarded any lockowner state).

    In our model, a creation request must be accompanied by the cookie
    for the parent.  The OPEN request contains the clientid of the
    parent, but we argue above that this is not enough for a cookie.
    In OPEN_CONFIRM, an open_confirm verifier is also sent.  This is
    an opaque datum provided by the server and effectively serves as
    the remainder of the cookie.

    One way to look at this, is that the server maintains a client
    cookie which is the clientid plus something else.  When the client
    makes a request that requires the "something else", the server
    replies by saying "you also need this datum to confirm the
    request".  The client then confirms.

    So the "cookie" for the "client" is the clientid plus the
    open_confirm verifier.

  Object destruction:

    There is no way for the client to indicate to the server that a
    lockowner can be released.  It can only release all lower-level
    state (UNLOCK locks and CLOSE files) and then wait.
    The server is free to release the lockowner object if it is
    "empty" and has not been used for a while.

    The model requires that the cookie for the parent client must
    change.  This will manifest in the open_confirm verifier being
    different next time.

   Object cookie:

    The lockowner does not get a cookie created for it by the server.
    Rather the cookie is a combination of an nfs_lockowner4 (which is a
    clientid4 plus an opaque owner) and sequence id.  The sequence id
    (seqid) is negoatiated at lockowner creation time.

    This combination of nfs_lockowner4 and seqid is somewhat awkward
    as the seqid is also involved in preresenting state at a lower
    level.

 Openfiles:

  Object creation:
    An "openfile" object is created with the "OPEN" operation.  The
    client must present the "cookie" for the lockowner, being the
    nfs_lockowner4 structure and the seqid (and possibly must present
    a verifier with OPEN_CONFIRM, but that is to confirm the creation
    of the lockowner, not to confirm the creation of the openfile.

  Object creation failure:

    It is quite possible for openfile creation to fail in a way that a
    subsequent identical request could succeed.  One possibility is a
    request for exclusive create: the file could be removed between
    the initial request and the retransmit.  Another possibility is a
    conflicting share reservation.
    For this reason the "cookie" that is presented for the parent state -
    the lockowner -  must change when an OPEN fails for one of these
    reasons.
    The part of the "cookie" that changes is the seqid.
    The server doesn't explicitly return a new seqid, but implicitly
    indicates that it must change.
    For the protocol to work reliably, it must require that the 
    seqid change in an agreed way (increment) whenever the server
    fails an OPEN request for a reason which could be transient.

  Object deletion:

    openfiles can be explicitly closed using the CLOSE operation.
    The model requires that the parent cookie be presented for this
    operation and be changed by it.
    nfs_lockowner4 part of the cookie is deducable by the stateid, and
    the other part, the seqid, is explicitly given.  The seqid is
    implicit changed by the completion of the operation, thus changing
    the whole cookie.

  Object state change:
  
    The openfile is the only object that can undergo a state change
    without creating/deleting a child object.
    The state changes happen with LOCK and UNLOCK (and maybe
    OPEN_DOWNGRADE and possibly OPEN and maybe even others).
    
    Each such request passes a stateid plus seqid, and return an new
    stateid on success and implicitly update the state id on failure
    (and on success).

  Object cookie.

    The cookie for an openfile is the stateid returned by the OPEN
    operation, combined with the seqid.  The seqid component is needed
    to reflect failed LOCK attempts.  Here we see that the seqid is
    part of the cookie for both the openfile and the lockowner.

Summary of issues:

 - While there is a clear hierarchy of state, the way that state is
   indicated (the cookie) is very different at different levels.
 - It is unclear what the purpose of the lockowner level is.
   I am happy to detail my view of the lockowner level but this email
   is too long as it is, so I have cut it out and will send it
   separately if anyone is interested.
 - The one 'seqid' plays a similar, though independant, role for 
   the lockowner level and the openfile level.
   Also, the rules for incrementing it do not make clear it's function
   (and do not seem to be generally agreed on).

   My rules for incrementing the seqid value in the current protocol
   would be:
    1/ The spec MUST specify exactly which return status for which
        operations cause the seqid to be incremented:
    2/ These MUST include any status which indicates a condition which
       is transient such that a subsequent receipt of an identical
       operation could succeed.

------------------------- My proposed protocol -----------------------

You may have guessed much of my model by the foregoing treatment of
the current model, so I'll try not to be too verbose.
In this model I will completely leave out the lockowner level, because
I cannot convincingly argue for it's existance.  You might find it an
interesting exercise to see what it takes to add the lockowner level
back in.  Hopefully you will be pleasantly surprised.

Foundation:
  There is an hierarchy of state maintained on the server.  The levels
  of the hierarchy are:
      server
      client
      openfile

  The state of an object at each level is represented by a "stateid"
  and a "failurecount". These together form the cookie.  

  There is precisely one server level state on each server.  It is
  created by the server at start time and assigned a unique server stateid. 
  All other levels of state are created by a request from the client.
  Any request to create state for an object at a particular level
  requires that the client present
   -  a current stateid and failure count for a parent state level
      above the target level. 
   -  a "name" for the object for which state is being created.
      For a client, the "name" is an nfs_client_id4
      For an openfile, the "name" might be a filehandle or a
      filehandle plus a basename, and may include a uniquifier to
      allow one client to hold multiple openfiles on the one file.
      The details an implications of this are beyond the current 
      discussion.

  Thus to create state for client, the server stateid and failure
  count must be presented along with a nfs_client_id4.
 
  To create state for an openfile, a current client id and
  failurecount must be presented along with a filehandle and,
  possibly, a basename.

  In each case, other information relevant to the specific object may
  be required.  The state/failurecount/name is the minimum in common.

  If the requested state is successfully created then a new stateid is
  returned. 

  State for objects are deleted on explicit request from the client. 
  The request identifes the parent state with stateid and
  failurecount, and also the target state bby stateid.
  A successful response to state deletion includes a new stateid for
  the parent state.

  Whenever a new stateid is given to the client by the server, the
  associated failurecount is agreed to be zero.  Whenever the client
  presents a stateid+failurecount in an state-creation request to the
  server,  there are three possibilities wrt the handling of state:

    1/ The state change succeeds, a new stateid is created and
       returned to the client.  The failurecount is agreed to be zero.
       The server will remember the previous stateid/failurecount and
       the operation that suceeded at least until the new stateid is
       seen from the client.  This allows the server to reply
       consistantly in the event of retransmission.
    2/ The state change operation could fail for a reason that is
       potentially transient. e.g. there are conflicting locks
       current, or the server temporarily ran out of resourse. In this
       case the failurecount is implicitly incremented by client and
       server.  The server remembers the return status at least until
       it sees a request from the client with the same stateid and a
       new failurecount.  This allows it to reply consistantly in the
       event of retransmission.
    3/ The state change operation could fail for some reason that is
       permanent, such as EXPIRED or FHEXPIRED or several others.  In
       this case, no change of state is need as retransmission will
       result in the same (or sufficiently similar) reponse.

  The server stateid can be requested of the server at any time.

I apologise for the length of this email, appreciate your patience in
reading, and look forward to your comments.

NeilBrown

---

From: David Robinson <[email-masked]>
Date: Mon, 05 Feb 2001 12:35:43 -0800

Neil Brown wrote:

An excellent writeup that I think exposes the history of V4
adding state through the design, instead of knowing the state
needed and creating a design.

> back in.  Hopefully you will be pleasantly surprised.

I think the flaw in your reasoning is the fact that there is
a level between the client and the openfile that allows the
same file to be opened but with different state and privileges.  
Thus the need for a lock owner.

Consider the case where two separate entities on a client open the
same file with different permissions and each obtains a non-conflicting
lock. Having only a single "cookie" per openfile will require that
any state change cause all requests that are intransit to fail and
be recovered.  If in this example one of the entities UNLOCKs their
portion of the file that was read LOCKed, this changes the cookie
but it does not effect the ability of other entities to access the
file with their old cookies.  The addition of a lockowner allows an
intermediate state between the client and the openfile that prevents
every state changing operation from serializing all operations.

Although I did not get this from your writeup, your model could work
if every unique entity (i.e. process in Unix) is its own client. However
given that these clients will likely all fail and recover at the same
time I am not convinced the overhead is worth it.

	-David

---

From: Neil Brown <[email-masked]>
Date: Tue, 6 Feb 2001 11:45:27 +1100 (EST)

> needed and creating a design.

Thankyou.  As they say, hindsight gives 20/20 vision.

> every state changing operation from serializing all operations.

I'm not actually arguing against the lockowner level at this point,
just saying that I find it hard to argue for it.

However, there is no need for an extra level to provide separate
cookies for separate entities accessing the same file.
Hidden in "My proposed protocol" it says:

Note the "uniquifier to allow one client to hold multiple openfiles on
the one file".  Think of the uniquifier as an index into the client's
open file table.
This explicitly allows the client to hold two indpendant opens on the
same file, even within the same "process" on the client.

Given this, we could probably get rid of the open upgrade/downgrade
issue that seems to bother the WinNT server implementors, and could
clearly resolve the question:
  What happens if a client opens the one file using two different
  names, and getting two different filehandles? 
Currently, I think that the client needs to inspect the fileid to see
if they are the same open.  In my proposal that isn't necessary. The
client gives a different uniquifier and knows that it has a different
"open" (i.e. a different, independant, cookie-sequence).

NeilBrown