Re: [PATCH v9 23/27] NFS: Convert readdir page cache to use a cookie based index

[Trond Myklebust <trondmy@hammerspace.com>]

On Fri, 2022-03-11 at 11:14 -0500, Benjamin Coddington wrote:
> On 11 Mar 2022, at 9:02, Trond Myklebust wrote:
> 
> > On Fri, 2022-03-11 at 06:58 -0500, Benjamin Coddington wrote:
> > > On 10 Mar 2022, at 16:07, Trond Myklebust wrote:
> > > 
> > > > On Wed, 2022-03-09 at 15:01 -0500, Benjamin Coddington wrote:
> > > > > On 27 Feb 2022, at 18:12, trondmy@kernel.org wrote:
> > > > > 
> > > > > > From: Trond Myklebust <trond.myklebust@hammerspace.com>
> > > > > > 
> > > > > > Instead of using a linear index to address the pages, use
> > > > > > the
> > > > > > cookie of
> > > > > > the first entry, since that is what we use to match the
> > > > > > page
> > > > > > anyway.
> > > > > > 
> > > > > > This allows us to avoid re-reading the entire cache on a
> > > > > > seekdir()
> > > > > > type
> > > > > > of operation. The latter is very common when re-exporting
> > > > > > NFS,
> > > > > > and
> > > > > > is a
> > > > > > major performance drain.
> > > > > > 
> > > > > > The change does affect our duplicate cookie detection,
> > > > > > since we
> > > > > > can
> > > > > > no
> > > > > > longer rely on the page index as a linear offset for
> > > > > > detecting
> > > > > > whether
> > > > > > we looped backwards. However since we no longer do a linear
> > > > > > search
> > > > > > through all the pages on each call to nfs_readdir(), this
> > > > > > is
> > > > > > less
> > > > > > of a
> > > > > > concern than it was previously.
> > > > > > The other downside is that invalidate_mapping_pages() no
> > > > > > longer
> > > > > > can
> > > > > > use
> > > > > > the page index to avoid clearing pages that have been read.
> > > > > > A
> > > > > > subsequent
> > > > > > patch will restore the functionality this provides to the
> > > > > > 'ls -
> > > > > > l'
> > > > > > heuristic.
> > > > > 
> > > > > I didn't realize the approach was to also hash out the
> > > > > linearly-
> > > > > cached
> > > > > entries.  I thought we'd do something like flag the context
> > > > > for
> > > > > hashed page
> > > > > indexes after a seekdir event, and if there are collisions
> > > > > with
> > > > > the
> > > > > linear
> > > > > entries, they'll get fixed up when found.
> > > > 
> > > > Why? What's the point of using 2 models where 1 will do?
> > > 
> > > I don't think the hashed model is quite as simple and efficient
> > > overall, and
> > > may produce impacts to a system beyond NFS.
> > > 
> > > > > 
> > > > > Doesn't that mean that with this approach seekdir() only hits
> > > > > the
> > > > > same pages
> > > > > when the entry offset is page-aligned?  That's 1 in 127 odds.
> > > > 
> > > > The point is not to stomp all over the pages that contain
> > > > aligned
> > > > data
> > > > when the application does call seekdir().
> > > > 
> > > > IOW: we always optimise for the case where we do a linear read
> > > > of
> > > > the
> > > > directory, but we support random seekdir() + read too.
> > > 
> > > And that could be done just by bumping the seekdir users to some
> > > constant
> > > offset (index 262144 ?), or something else equally dead-nuts
> > > simple. 
> > > That
> > > keeps tightly clustered page indexes, so walking the cache is
> > > faster.  That
> > > reduces the "buckshot" effect the hashing has of eating up
> > > pagecache
> > > pages
> > > they'll never use again.  That doesn't cap our caching ability at
> > > 33
> > > million
> > > entries.
> > > 
> > 
> > What you say would make sense if readdir cookies truly were
> > offsets,
> > but in general they're not. Cookies are unstructured data, and
> > should
> > be treated as unstructured data.
> > 
> > Let's say I do cache more than 33 million entries and I have to
> > find a
> > cookie. I have to linearly read through at least 1GB of cached data
> > before I can give up and start a new readdir. Either that, or I
> > need to
> > have a heuristic that tells me when to stop searching, and then
> > another
> > heuristic that tells me where to store the data in a way that
> > doesn't
> > trash the page cache.
> > 
> > With the hashing, I seek to the page matching the hash, and I
> > either
> > immediately find what I need, or I immediately know to start a
> > readdir.
> > There is no need for any additional heuristic.
> 
> The scenario where we want to find a cookie while not doing a linear
> pass
> through the directory will be the seekdir() case.  In a linear walk,
> we have
> the cached page index to help.  So in the seekdir case, the chances
> of
> having someone already fill a page and also having the cookie be the
> 1 in
> 127 that are page-aligned (and so match an already cached page) are
> small, I
> think.  Unless your use-case will often hit the exact same offsets
> over and
> over.

For the use case where we are reexporting NFS, it can definitely
happen.
Firstly, the clients usually are reading the reexported directory
linearly, so they will tend to follow the same cookie request patterns.
Secondly, we're not going to replay the readdir from the duplicate
reply cache if the client resends the request. So even if you only have
one client, there can be a benefit.

> 
> So with the hashing and seekdir case, I think that the cache will be
> pretty
> heavily filled with the same duplicated data at various offsets and
> rarely
> useful.  That's why I wondered if you'd tested your use-case for it
> and found
> it to be advantageous.  I think what we've got is going to work fine,
> but I
> wonder if you've seen it to work well.
> 
> The major pain point most of our users complain about is not being
> able to
> perform a complete walk in linear time with respect to size with
> invalidations at play.  This series fixes that, and is a huge bonus. 
> Other
> smaller performance improvements are pale in comparison for us, and
> might
> just get us forever chasing one or two minor optimizations that have
> trade-offs.
> 
> There's a lot of variables at play.  For some client/server setups
> (like
> some low-latency RDMA), and very large directories and cache sizes,
> it might
> be more performant to just do the READDIR every time, walking local
> caches
> be damned.
> 

Sure, so a dedicated readdirplus() system call could help by providing
the same kind of guidance that statx() does today.

> > > Its weird to me that we're doing exactly what XArray says not to
> > > do,
> > > hash
> > > the index, when we don't have to.
> > > 
> > > > > It also means we're amplifying the pagecache's useage for
> > > > > slightly
> > > > > changing
> > > > > directories - rather than re-using the same pages we're
> > > > > scattering
> > > > > our usage
> > > > > across the index.  Eh, maybe not a big deal if we just expect
> > > > > the
> > > > > page
> > > > > cache's LRU to do the work.
> > > > > 
> > > > 
> > > > I don't understand your point about 'not reusing'. If the user
> > > > seeks to
> > > > the same cookie, we reuse the page. However I don't know how
> > > > you
> > > > would
> > > > go about setting up a schema that allows you to seek to an
> > > > arbitrary
> > > > cookie without doing a linear search.
> > > 
> > > So when I was taking about 'reusing' a page, that's about re-
> > > filling
> > > the
> > > same pages rather than constantly conjuring new ones, which
> > > requires
> > > less of
> > > the pagecache's resources in total.  Maybe the pagecache can
> > > handle
> > > that
> > > without it negatively impacting other users of the cache that
> > > /will/
> > > re-use
> > > their cached pages, but I worry it might be irresponsible of us
> > > to
> > > fill the
> > > pagecache with pages we know we're never going to find again.
> > > 
> > 
> > In the case where the processes are reading linearly through a
> > directory that is not changing (or at least where the beginning of
> > the
> > directory is not changing), we will reuse the cached data, because
> > just
> > like in the linearly indexed case, each process ends up reading the
> > exact same sequence of cookies, and looking up the exact same
> > sequence
> > of hashes.
> > 
> > The sequences start to diverge only if they hit a part of the
> > directory
> > that is being modified. At that point, we're going to be
> > invalidating
> > page cache entries anyway with the last reader being more likely to
> > be
> > following the new sequence of cookies.
> 
> I don't think we clean up behind ourselves anymore.  Now that we are
> going
> to validate each page before using it, we don't invalidate the whole
> cache
> at any point.  That means that a divergence duplicates the pagecache
> usage
> beyond the divergence.
> 

No. I reinstated the call to nfs_revalidate_mapping() in the linux-next
branch after Olga demonstrated that NFSv3 is still troubled with crappy
mtime/ctime resolutions on the server causing directory changes to not
be reflected in the readdir cache.

-- 
Trond Myklebust
Linux NFS client maintainer, Hammerspace
trond.myklebust@hammerspace.com