Subject: [nfsv4] Notes regarding discussion of directory scalabiliy issues

From: David Noveck <[email-masked]>
Date: Fri, 26 Jun 2020 13:54:20 -0400

*Introduction*

On 6/22, Chuck and I held a discussion to try to resolve some issues that
arose in our discussion of scalability issues for directory operations.
 After our original presentations on this topic at the
post-IETF107 virtual interim, it was anticipated that we would discuss
those on the wg mailing list.   Since that didn't work out, Chuck and I
decided to clarify and possibly resolve our differences of approach in a
short meeting that worked well in the form of a phone call.

We were able to clarify but not resolve two issues.  We hope to be able to
resolve these eventually, but not necessarily during the July 9th meeting.

   - We did agree that we will need to better understand, and try to
   resolve issues regarding the compatibility of directory notifications and
   client handling of directory cookies and their caching. See *Directory
   Delegation Issues* for details.

   - We also explored issues raised by the possible addition of ops to aid
   recursive directory traversals, building on Chuck's suggestion, at the
   earlier meeting, of possible protocol aid for "rm -r". See  *Ops to Add
   Aiding Recursive Directory Traversal *for details

*Directory Delegation Issues*

Implementations of directory delegations are quite limited, making it not
worth investing in server-side implementations.   Useful client-side
implementation would require the ability to efficiently cache large slowly
changing directories.   Unfortunately, that is not currently possible, at
least for the Linux client, since the creation or removal of a file from a
directory requires that the entire directory (which can be very large) be
refetched.  This now occurs for directory changes that the client makes
itself but would presumably also apply in the case of directory
notifications, making them not very useful in the important case of large
slowly-changing directories.

As Chuck related to me, this requirement for directory refetching is
predicated on the possibility that any change to a directory (e.g. remove,
create, rename) could potentially invalidate directory entry cookies for
all the cached directory.entries.   While this is unlikely to happen in
practice, I can see that clients might be unwilling to rely on filsystems
not changing these. The thing I don't understand, and Chuck was unable to
clarify for me, is why such entries need to be cached at all, and
essentially treated as if they were attributes.  While the directory
notification feature has the ability to propagate attribute changes to
clients with delegations, there is no such ability in the case of cookie
changes.  It appears that the feature was designed assuming these would not
be necessary.

As a result, it appeared that one if the following would have to be done:

   1. Clients might be modified so as not to depend on a supposed fixity of
   such cookies. That's clearly my favorite as I believe the client returning
   a cached directory could synthesize its own cookies to allow users to fetch
   directory information across multiple requests.  However, I'm not sure
   client implementers would agree and this is a matter on which consensus is
   important.
   2. Provide a way in which the server could  communicate that the
   theoretical possibility that a remove, create, or rename could cause a
   revision of cookies for uninvolved directory entries does not occur for  a
   given fs. This could be done by adding a new fs-scope attribute providing
   information about an fs's directory entry cookie management.  The downside
   is that this would be v4.2-only and would be require an additional RFC to
   make a v4.1 feature effectively usable 😞
   3. Provide another way to exclude the possibility of the client being
   blind-sided by a server-side fs prone to directory cookie reassignment.
   For example, any change to a directory entry cookie not being removed or
   renamed could require delegation recall.  Unfortunately, this is a big
   change to an existing feature😖

As Chuck and I finished the discussion we anticipated a long-term process
aimed at securing a consensus about which of these choices the working
group would adopt to make directory delegations useful.  This could start
at the 7/9 meeting but the need to make sure we had the
active participation of client implementers meant it wasn't a sure thing
for initial discussion at the 7/9 meeting.

Lately, I've been looking at directory notifications in more detail and
come to the conclusion that the way the notifications use cookies to update
cached directories is really predicated on the expectation that cookies for
directory entries not involved in the specific update will not change.  For
example, insert and rename notifications include the cookie of the entry
before the insertion point, which is not really useful if the server-side
fs  is free to change cookies for entries not involved in the directory
operation.

I now believe that it is possible to rework the description of this feature
so that the server by supporting directory notifications is providing
assurance that the server, by supporting such notifications, is effectively
providing an assurance that the wholesale revision of cookies as a result
of directory modification operations, about which clients are concerned,
cannot happen.   This could not be done as a consequence of an errata
report, but it is the sort of clarification/revision that I feel could be
done as a part of rfc5661bis, assuming that we can reach a working group
consensus on the matter.  We intend to do change sof this scale for some
REJECTED errata reports.I will take about 5-10 minutes for a presentation
of this issue at the 7/9 meeting, hoping to stimulate later discussion of
this issue and future directory delegation/notification
implementation possibilities on the mailing list.

*Ops to Add Aiding Recursive Directory Traversal*

In Chuck's presentation he alluded to the possibility of the protocol
giving "rm -r" more help and there are a number of useful extensions that
could be defined.  As I considered other applications in which recursive
directory traversal there appeared to be a number of possible READDIR
extensions that could be sensibly proposed and would be useful in software
build workloads.

The problem with such extensions is that they are unlikely to be used
unless complementary work is done to provide useful API's to provide access
to any helpful protocol extensions.  Although such work is out-of-scope for
the working group, the working group has to avoid investing in protocol
extensions which, realistically, will never be used.  As a result I will
not present regarding possible extensions at the 7/9 meeting but may dp
this later if there is interest in compatible API's for important clients.

*Miscellaneous Items.*

We also had occasion to discuss some other issues regarding the agenda of
the  forthcoming meeting:

   - Chuck reminded me of my previously mentioned intention to use github
   for the handling of the writing and review of wg documents associated with
   rfc5661bis (i.e. draft-ietf-nfsv4-internationalization,
   draft-ietf-nfsv4-security-needs, draft-ietf-nfsv4-security,
   draft-ietf-nfsv4-rfc5661bis, and possibly others).   Chuck wasn't clear
   what exactly I might need from him to help the process and it turned out,
   I wasn't sure either.  We agreed that I would mention the issues in my
   general slides on the rfc5661bis process and that I'd give Chuck an early
   opportunity to respond to those.
   - Chuck pointed out the issue of the length of rfc5661 nd the need to
   address concerns about that.  I was concerned that previous suggestions in
   this regard (with regard to pNFS file) might result in multiple documents
   that don't fit together all that well.   I agreed to look at other
   approaches to the issue and present those to the working group at the 7/9
   meeting.

---

From: Trond Myklebust <[email-masked]>
Date: Mon, 29 Jun 2020 18:42:58 +0000

Like it or not, the readdir cookie is an attribute of the directory.

If I want to support the POSIX telldir() and seekdir() operations ( https://pubs.opengroup.org/onlinepubs/9699919799/functions/seekdir.html ), then I need to ensure that when the application calls seekdir(), I return to the exact same cursor location in the stream that I was at when I called telldir().

Without a server side cookie on which to anchor my telldir() cookies, then all I have is a list of filenames that can and will change every time a file is created, deleted or renamed. Both the length and ordering of that list may change whenever the directory is modified, meaning that a naive implementation of synthetic cookies as an offset is not compatible with the telldir()/seekdir() requirements.
To make matters worse, the list size is for all intents and purposes unbounded, because there is no hard limit on the size of a directory. That makes it also impossible to create a cached mapping between a synthetic cookie and a filename; such a mapping would be unbounded both in size and in duration (since we don't know a priori how long the application will keep the directory open, or for that matter, which exact set of cookies it may have cached). So in order to make this work the client would basically have to create its own B-tree and persist it in storage somewhere. Remind me why we needed that NFS server?

On Fri, 2020-06-26 at 13:54 -0400, David Noveck wrote:
Introduction

On 6/22, Chuck and I held a discussion to try to resolve some issues that arose in our discussion of scalability issues for directory operations.   After our original presentations on this topic at the post-IETF107 virtual interim, it was anticipated that we would discuss those on the wg mailing list.   Since that didn't work out, Chuck and I decided to clarify and possibly resolve our differences of approach in a short meeting that worked well in the form of a phone call.

We were able to clarify but not resolve two issues.  We hope to be able to resolve these eventually, but not necessarily during the July 9th meeting.

  *   We did agree that we will need to better understand, and try to resolve issues regarding the compatibility of directory notifications and client handling of directory cookies and their caching. See Directory Delegation Issues for details.

  *   We also explored issues raised by the possible addition of ops to aid recursive directory traversals, building on Chuck's suggestion, at the earlier meeting, of possible protocol aid for "rm -r". See  Ops to Add Aiding Recursive Directory Traversal for details

Directory Delegation Issues

Implementations of directory delegations are quite limited, making it not worth investing in server-side implementations.   Useful client-side implementation would require the ability to efficiently cache large slowly changing directories.   Unfortunately, that is not currently possible, at least for the Linux client, since the creation or removal of a file from a directory requires that the entire directory (which can be very large) be refetched.  This now occurs for directory changes that the client makes itself but would presumably also apply in the case of directory notifications, making them not very useful in the important case of large slowly-changing directories.

As Chuck related to me, this requirement for directory refetching is predicated on the possibility that any change to a directory (e.g. remove, create, rename) could potentially invalidate directory entry cookies for all the cached directory.entries.   While this is unlikely to happen in practice, I can see that clients might be unwilling to rely on filsystems not changing these. The thing I don't understand, and Chuck was unable to clarify for me, is why such entries need to be cached at all, and essentially treated as if they were attributes.  While the directory notification feature has the ability to propagate attribute changes to clients with delegations, there is no such ability in the case of cookie changes..  It appears that the feature was designed assuming these would not be necessary.

  1.  Clients might be modified so as not to depend on a supposed fixity of such cookies. That's clearly my favorite as I believe the client returning a cached directory could synthesize its own cookies to allow users to fetch directory information across multiple requests.  However, I'm not sure client implementers would agree and this is a matter on which consensus is important.
  2.  Provide a way in which the server could  communicate that the theoretical possibility that a remove, create, or rename could cause a revision of cookies for uninvolved directory entries does not occur for  a given fs. This could be done by adding a new fs-scope attribute providing information about an fs's directory entry cookie management.  The downside is that this would be v4.2-only and would be require an additional RFC to make a v4.1 feature effectively usable 😞
  3.  Provide another way to exclude the possibility of the client being blind-sided by a server-side fs prone to directory cookie reassignment.  For example, any change to a directory entry cookie not being removed or renamed could require delegation recall.  Unfortunately, this is a big change to an existing feature😖

As Chuck and I finished the discussion we anticipated a long-term process aimed at securing a consensus about which of these choices the working group would adopt to make directory delegations useful.  This could start at the 7/9 meeting but the need to make sure we had the active participation of client implementers meant it wasn't a sure thing for initial discussion at the 7/9 meeting.

Lately, I've been looking at directory notifications in more detail and come to the conclusion that the way the notifications use cookies to update cached directories is really predicated on the expectation that cookies for directory entries not involved in the specific update will not change.  For example, insert and rename notifications include the cookie of the entry before the insertion point, which is not really useful if the server-side fs  is free to change cookies for entries not involved in the directory operation.

I now believe that it is possible to rework the description of this feature so that the server by supporting directory notifications is providing assurance that the server, by supporting such notifications, is effectively providing an assurance that the wholesale revision of cookies as a result of directory modification operations, about which clients are concerned, cannot happen.   This could not be done as a consequence of an errata report, but it is the sort of clarification/revision that I feel could be done as a part of rfc5661bis, assuming that we can reach a working group consensus on the matter.  We intend to do change sof this scale for some REJECTED errata reports.I will take about 5-10 minutes for a presentation of this issue at the 7/9 meeting, hoping to stimulate later discussion of this issue and future directory delegation/notification implementation possibilities on the mailing list.

Ops to Add Aiding Recursive Directory Traversal

In Chuck's presentation he alluded to the possibility of the protocol giving "rm -r" more help and there are a number of useful extensions that could be defined.  As I considered other applications in which recursive directory traversal there appeared to be a number of possible READDIR extensions that could be sensibly proposed and would be useful in software build workloads.

The problem with such extensions is that they are unlikely to be used unless complementary work is done to provide useful API's to provide access to any helpful protocol extensions.  Although such work is out-of-scope for the working group, the working group has to avoid investing in protocol extensions which, realistically, will never be used.  As a result I will not present regarding possible extensions at the 7/9 meeting but may dp this later if there is interest in compatible API's for important clients.

Miscellaneous Items.

We also had occasion to discuss some other issues regarding the agenda of the  forthcoming meeting:

  *   Chuck reminded me of my previously mentioned intention to use github for the handling of the writing and review of wg documents associated with rfc5661bis (i.e. draft-ietf-nfsv4-internationalization, draft-ietf-nfsv4-security-needs, draft-ietf-nfsv4-security, draft-ietf-nfsv4-rfc5661bis, and possibly others).   Chuck wasn't clear what exactly I might need from him to help the process and it turned out, I wasn't sure either.  We agreed that I would mention the issues in my general slides on the rfc5661bis process and that I'd give Chuck an early opportunity to respond to those.
  *   Chuck pointed out the issue of the length of rfc5661 nd the need to address concerns about that.  I was concerned that previous suggestions in this regard (with regard to pNFS file) might result in multiple documents that don't fit together all that well.   I agreed to look at other approaches to the issue and present those to the working group at the 7/9 meeting.

_______________________________________________

nfsv4 mailing list

<mailto:[email-masked]>

[email-masked]

<https://www.ietf.org/mailman/listinfo/nfsv4>

https://www.ietf.org/mailman/listinfo/nfsv4

--

Trond Myklebust
Linux NFS client maintainer, Hammerspace
[email-masked]<mailto:[email-masked]>

---

From: David Noveck <[email-masked]>
Date: Tue, 30 Jun 2020 08:40:21 -0400

Thanks for your helpful comments.

On Mon, Jun 29, 2020 at 2:43 PM Trond Myklebust <[email-masked]>
wrote:

> Like it or not, the readdir cookie *is* an attribute of the directory.
>

If the protocol treated them as such, then the attribute notifications
feature could provide updates to the client.   Given that it doesn't, we
could add a cookie update feature to directory notification feaure as a
v4.2 extension to the protocol.  However, I'm reluctant to start work on
the necessary protocol additions until we are sure they are needed to
provide better directory cacheability.

Actually, they are attributes of directory *streams.   *The difference is
not all that important given that client implementations are unlikely to be
aware of the specific steam associated with any particular request.
However, there are a few cases in which the difference is important in
determining whether various approaches to client handling of cookies might
or might not work, and will be important in the discussion below:

   - Two requests made on different clients necessarily are made on
   distinct streams.
   - Two requests made on different instances of the same client (with an
   intervening restart/reboot) also have to arise on different streams.

> If I want to support the POSIX telldir() and seekdir() operations (
> https://pubs.opengroup.org/onlinepubs/9699919799/functions/seekdir.html ),
> then I need to ensure that when the application calls seekdir(), I return
> to the exact same cursor location in the stream that I was at when I called
> telldir().
>

Agreed.

Without a server side cookie on which to anchor my telldir() cookies,

Every client has these available but it is not clear to me useful such
anchoring is.   I think the flexibility that each client has to
assign cookies to streams it is responsible for is valuable and could be
compromised if anchoring to the server cookies is made the focus of the
implementation.

then all I have is a list of filenames that can and will change every time
> a file is created, deleted or renamed.
>

Clearly it will change.  However, the directory notifications feature makes
some assumptions, currently implicit about how the list will change.   Once
these are made explicit, the wg could decide that server/fs pairs incapable
of staying within these reasonable restrictions (if they are, in fact,
reasonable), cannot support the directory notifications feature.

Both the length and ordering of that list may change whenever the directory
> is modified,

Clearly the length will change, but the reasonable expectation is that
creating a file will increase the length by one and deleting one will
decrease it by one.   I don't see the value of supporting directory
notifications on server fs that do something else.

With regard ro ordering,  suppose the spec allows an fs to shuffle the
directory order every time a change is made, but I'm unaware of any actual
file systems that do this.   Do we need to support directory notifications
for such fs's?

> meaning that a naive implementation
>

OK.   I'll plead guilty to one *misdemeanor *count of directory naivety.

> of synthetic cookies as an offset is not compatible with the
> telldir()/seekdir() requirements.
>

It's not clear to me how this incompatibility would manifest itself.  I
think I need to understand what would break.

> To make matters worse, the list size is for all intents and purposes
> unbounded, because there is no hard limit on the size of a directory. That
> makes it also impossible to create a cached mapping between a synthetic
> cookie and a filename; such a mapping would be unbounded both in size and
> in duration (since we don't know a priori how long the application will
> keep the directory open, or for that matter, which exact set of cookies it
> may have cached).
>

Such a mapping would, in essence, be part of the cached directory.   So, if
it is too big to keep in client memory,then it is too big to cache and you
might as well decide not to cache it.

I expect there is an issue that is a worry in the case in which a
reasonably sized directory  grows over time to be too big to cache while an
open directory stream retains some directory cookies which might be
incompatible with the client dropping  caching of directories and switching
to server-based cookies.😖
I feel it is reasonable to treat this situation as one might a
cookie-verifier failure, particularly if this is the only worrisome failure
mode.   However, this possibility means that I would not ask clients to
implement such local cookies. To enable that, we would have to make
explicit the same sort of reasonableness requirement for cookie changes
that we have already discussed for ordering changes.  RFC7530 already
alludes to the need to avoid spurious cookie invalidations although not in
as explicit or strict way as we would need to support
directory notifications:

   As there is no way for the client to indicate that a cookie value,
   once received, will not be subsequently used, server implementations
   should avoid schemes that allocate memory corresponding to a returned
   cookie.  Such allocation can be avoided if the server bases cookie
   values on a value such as the offset within the directory where the
   scan is to be resumed.

   Cookies generated by such techniques should be designed to remain
   valid despite modification of the associated directory.  If a server
   were to invalidate a cookie because of a directory modification,
   READDIRs of large directories might never finish.

> So in order to make this work the client would basically have to create
> its own B-tree and persist it in storage somewhere.
>

I don't see the need to make this persistent.  If the client restarts, all
directory streams have ceased to exist and we know  *a posteriori  *that
there are no outstanding directory cookies to which the client would have
to respond.

> <[email-masked]>
> [email-masked] <[email-masked]>
>
>
>

---

From: Trond Myklebust <[email-masked]>
Date: Tue, 30 Jun 2020 13:32:27 +0000

On Tue, 2020-06-30 at 08:40 -0400, David Noveck wrote:
Thanks for your helpful comments.

On Mon, Jun 29, 2020 at 2:43 PM Trond Myklebust <[email-masked]<mailto:[email-masked]>> wrote:
Like it or not, the readdir cookie is an attribute of the directory.

If the protocol treated them as such, then the attribute notifications feature could provide updates to the client.   Given that it doesn't, we could add a cookie update feature to directory notification feaure as a v4.2 extension to the protocol.  However, I'm reluctant to start work on the necessary protocol additions until we are sure they are needed to provide better directory cacheability.

Actually, they are attributes of directory streams.   The difference is not all that important given that client implementations are unlikely to be aware of the specific steam associated with any particular request.  However, there are a few cases in which the difference is important in determining whether various approaches to client handling of cookies might or might not work, and will be important in the discussion below:

  *   Two requests made on different clients necessarily are made on distinct streams.
  *   Two requests made on different instances of the same client (with an intervening restart/reboot) also have to arise on different streams.

Agreed.

Every client has these available but it is not clear to me useful such anchoring is.   I think the flexibility that each client has to assign cookies to streams it is responsible for is valuable and could be compromised if anchoring to the server cookies is made the focus of the implementation.

then all I have is a list of filenames that can and will change every time a file is created, deleted or renamed.

Clearly it will change.  However, the directory notifications feature makes some assumptions, currently implicit about how the list will change.   Once these are made explicit, the wg could decide that server/fs pairs incapable of staying within these reasonable restrictions (if they are, in fact, reasonable), cannot support the directory notifications feature.

Both the length and ordering of that list may change whenever the directory is modified,

Clearly the length will change, but the reasonable expectation is that creating a file will increase the length by one and deleting one will decrease it by one.   I don't see the value of supporting directory notifications on server fs that do something else.

With regard ro ordering,  suppose the spec allows an fs to shuffle the directory order every time a change is made, but I'm unaware of any actual file systems that do this.   Do we need to support directory notifications for such fs's?

touch foo; touch bar; ln foo baz; rm foo; mv baz foo

There... Most filesystems will end up reordering 'foo' and 'bar' in the directory stream given the above sequence of commands. How does the client figure out what happened if the above sequence of commands is performed on the server?
Now let's say that is a directory of a million files, and something like the above is made to happen regularly. How do I maintain a stable list of synthetic cookies on the client?

OK.   I'll plead guilty to one misdemeanor count of directory naivety.

of synthetic cookies as an offset is not compatible with the telldir()/seekdir() requirements.

It's not clear to me how this incompatibility would manifest itself.  I think I need to understand what would break.

To make matters worse, the list size is for all intents and purposes unbounded, because there is no hard limit on the size of a directory. That makes it also impossible to create a cached mapping between a synthetic cookie and a filename; such a mapping would be unbounded both in size and in duration (since we don't know a priori how long the application will keep the directory open, or for that matter, which exact set of cookies it may have cached).

Such a mapping would, in essence, be part of the cached directory.   So, if it is too big to keep in client memory,then it is too big to cache and you might as well decide not to cache it.

I expect there is an issue that is a worry in the case in which a reasonably sized directory  grows over time to be too big to cache while an open directory stream retains some directory cookies which might be incompatible with the client dropping  caching of directories and switching to server-based cookies.😖
I feel it is reasonable to treat this situation as one might a cookie-verifier failure, particularly if this is the only worrisome failure mode.   However, this possibility means that I would not ask clients to implement such local cookies. To enable that, we would have to make explicit the same sort of reasonableness requirement for cookie changes that we have already discussed for ordering changes.  RFC7530 already alludes to the need to avoid spurious cookie invalidations although not in as explicit or strict way as we would need to support directory notifications:

   scan is to be resumed.

So in order to make this work the client would basically have to create its own B-tree and persist it in storage somewhere.

I don't see the need to make this persistent.  If the client restarts, all directory streams have ceased to exist and we know  a posteriori  that there are no outstanding directory cookies to which the client would have to respond.
<mailto:[email-masked]>

--

--

Trond Myklebust