[PATCH 6/8] knfsd: repcache: use client IP address in hash

[PATCH 6/8] knfsd: repcache: use client IP address in hash

[Greg Banks]

knfsd: Use the client's IP address in the duplicate request cache
hash function, instead of just the XID.  This avoids contention
on hash buckets when the workload has many clients whose XIDs are
nearly in lockstep, a property seen on compute clusters using NFS
for shared storage.

Signed-off-by: Greg Banks <gnb@melbourne.sgi.com>
---

 fs/nfsd/nfscache.c |   11 ++++++++---
 1 files changed, 8 insertions(+), 3 deletions(-)

Index: linux-git-20061009/fs/nfsd/nfscache.c
===================================================================
--- linux-git-20061009.orig/fs/nfsd/nfscache.c	2006-10-10 16:41:07.121363949 +1000
+++ linux-git-20061009/fs/nfsd/nfscache.c	2006-10-10 16:41:49.107949488 +1000
@@ -93,13 +93,18 @@ static int			cache_disabled = 1;
  * Calculate the hash index from an XID.  Note, some clients increment
  * their XIDs in host order, which can result in all the variation being
  * in the top bits we see here.  So we fold those bits down.
+ *
+ * Experiment shows that using the Jenkins hash improves the spectral
+ * properties of this hash, but the CPU cost of calculating it outweighs
+ * the advantages.
  */
 static inline u32
-request_hash(u32 xid)
+request_hash(u32 xid, const struct sockaddr_in *sin)
 {
 	u32 h = xid;
 	h ^= (xid >> 24);
 	h ^= ((xid & 0xff0000) >> 8);
+	h ^= sin->sin_addr.s_addr;
 	return h;
 }
 
@@ -248,7 +253,7 @@ nfsd_cache_lookup(struct svc_rqst *rqstp
 	int			safe = 0;
 	int			expand = 0;
 
-	h = request_hash(xid);
+	h = request_hash(xid, &rqstp->rq_addr);
 	b = bucket_for_hash(h);
 	h = (h / CACHE_NUM_BUCKETS) & (HASHSIZE-1);
 
@@ -399,7 +404,7 @@ nfsd_cache_update(struct svc_rqst *rqstp
 	if (!(rp = rqstp->rq_cacherep) || cache_disabled)
 		return;
 
-	b = bucket_for_hash(request_hash(rp->c_xid));
+	b = bucket_for_hash(request_hash(rp->c_xid, &rp->c_addr));
 
 	len = resv->iov_len - ((char*)statp - (char*)resv->iov_base);
 	len >>= 2;

Greg.
-- 
Greg Banks, R&D Software Engineer, SGI Australian Software Group.
I don't speak for SGI.



-------------------------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security?
Get stuff done quickly with pre-integrated technology to make your job easier
Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
_______________________________________________
NFS maillist  -  NFS@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nfs

Re: [PATCH 6/8] knfsd: repcache: use client IP address in hash

[Trond Myklebust]

On Wed, 2006-10-11 at 21:28 +1000, Greg Banks wrote:
> knfsd: Use the client's IP address in the duplicate request cache
> hash function, instead of just the XID.  This avoids contention
> on hash buckets when the workload has many clients whose XIDs are
> nearly in lockstep, a property seen on compute clusters using NFS
> for shared storage.

Note that some platforms (in particular the *BSDs) use an MD5 checksum
of the first couple of 100 bytes of the RPC header+message instead of
relying on the XID. That is a good deal safer w.r.t. port reuse by other
clients etc.

Cheers,
  Trond


-------------------------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security?
Get stuff done quickly with pre-integrated technology to make your job easier
Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
_______________________________________________
NFS maillist  -  NFS@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nfs

Re: [PATCH 6/8] knfsd: repcache: use client IP address in hash

[Greg Banks]

On Wed, Oct 11, 2006 at 07:30:00PM -0700, Trond Myklebust wrote:
> On Wed, 2006-10-11 at 21:28 +1000, Greg Banks wrote:
> > knfsd: Use the client's IP address in the duplicate request cache
> > hash function, instead of just the XID.  This avoids contention
> > on hash buckets when the workload has many clients whose XIDs are
> > nearly in lockstep, a property seen on compute clusters using NFS
> > for shared storage.
> 
> Note that some platforms (in particular the *BSDs) use an MD5 checksum
> of the first couple of 100 bytes of the RPC header+message instead of
> relying on the XID. That is a good deal safer w.r.t. port reuse by other
> clients etc.
> 

I hear that there was a Cthon presentation on this subject.  It sounds
very interesting, does anyone have a URL?

I presume the approach involves masking out the IPID and TCP sequence
number?  Otherwise retries would never hash to the same value as the
original requests, thus defeating the repcache entirely.

Also, I'm not entirely convinced that a hash function which distributes
repcache entries more evenly across the hash table (which is what
I would expect an MD5 to do) is necessarily the best approach.
For one thing, that maximises the number of times that cachelines
need to be retrieved from remote nodes.  A better approach might be
to construct the hash function so that certain cachelines naturally
stay on certain CPUs.  I thought I'd done something like this, but
looking at the patch I sent it's dumber than that.


Greg.
-- 
Greg Banks, R&D Software Engineer, SGI Australian Software Group.
I don't speak for SGI.

-------------------------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security?
Get stuff done quickly with pre-integrated technology to make your job easier
Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
_______________________________________________
NFS maillist  -  NFS@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nfs

Re: [PATCH 6/8] knfsd: repcache: use client IP address in hash

[Chuck Lever]

On 10/12/06, Greg Banks <gnb@sgi.com> wrote:
> On Wed, Oct 11, 2006 at 07:30:00PM -0700, Trond Myklebust wrote:
> > On Wed, 2006-10-11 at 21:28 +1000, Greg Banks wrote:
> > > knfsd: Use the client's IP address in the duplicate request cache
> > > hash function, instead of just the XID.  This avoids contention
> > > on hash buckets when the workload has many clients whose XIDs are
> > > nearly in lockstep, a property seen on compute clusters using NFS
> > > for shared storage.
> >
> > Note that some platforms (in particular the *BSDs) use an MD5 checksum
> > of the first couple of 100 bytes of the RPC header+message instead of
> > relying on the XID. That is a good deal safer w.r.t. port reuse by other
> > clients etc.
> >
>
> I hear that there was a Cthon presentation on this subject.  It sounds
> very interesting, does anyone have a URL?
>
> I presume the approach involves masking out the IPID and TCP sequence
> number?  Otherwise retries would never hash to the same value as the
> original requests, thus defeating the repcache entirely.

The hash starts at the beginning of the RPC header, so the IP and
TCP/UDP headers are skipped.

-- 
"We who cut mere stones must always be envisioning cathedrals"
   -- Quarry worker's creed

-------------------------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security?
Get stuff done quickly with pre-integrated technology to make your job easier
Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
_______________________________________________
NFS maillist  -  NFS@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nfs

Re: [PATCH 6/8] knfsd: repcache: use client IP address in hash

[J. Bruce Fields]

On Thu, Oct 12, 2006 at 06:21:26PM +1000, Greg Banks wrote:
> On Wed, Oct 11, 2006 at 07:30:00PM -0700, Trond Myklebust wrote:
> > On Wed, 2006-10-11 at 21:28 +1000, Greg Banks wrote:
> > > knfsd: Use the client's IP address in the duplicate request cache
> > > hash function, instead of just the XID.  This avoids contention
> > > on hash buckets when the workload has many clients whose XIDs are
> > > nearly in lockstep, a property seen on compute clusters using NFS
> > > for shared storage.
> > 
> > Note that some platforms (in particular the *BSDs) use an MD5 checksum
> > of the first couple of 100 bytes of the RPC header+message instead of
> > relying on the XID. That is a good deal safer w.r.t. port reuse by other
> > clients etc.
> > 
> 
> I hear that there was a Cthon presentation on this subject.  It sounds
> very interesting, does anyone have a URL?

My possibly muddled notes from Rick's presentation:

Rick suggests:
        LRU cache per TCP connection:
                evicts from each cache on TCP ack from reply
        keep individual caches around forever, even after disconnect--
                since longterm network partition e.g. may be typical case.
                (OK, maybe not forever).
        (Note lookups are *global*--he doesn't look up on TCP connection (or
                even IP address)--he wants reconnects to get hits.)
        He uses XID and checksum on first 100 bytes of decrypted RPC body
                as key into cache.
                He assumes any hit on an in-progress rpc is a false positive.
                He also will *never* drop based on a hit on anything with
                a sequenceid-mutating op in it.


He also has more detailed notes at
ftp://ftp.cis.uoguelph.ca:/pub/nfsv4/server-cache.algorithm
and code in newnfs/nfsd/nfsd_srvcache.c in any of the nfsv4-fullkern* tarballs
on the same site.

--b.

-------------------------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security?
Get stuff done quickly with pre-integrated technology to make your job easier
Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
_______________________________________________
NFS maillist  -  NFS@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nfs

Re: [PATCH 6/8] knfsd: repcache: use client IP address in hash

[Neil Brown]

On Wednesday October 11, trond.myklebust@fys.uio.no wrote:
> On Wed, 2006-10-11 at 21:28 +1000, Greg Banks wrote:
> > knfsd: Use the client's IP address in the duplicate request cache
> > hash function, instead of just the XID.  This avoids contention
> > on hash buckets when the workload has many clients whose XIDs are
> > nearly in lockstep, a property seen on compute clusters using NFS
> > for shared storage.
> 
> Note that some platforms (in particular the *BSDs) use an MD5 checksum
> of the first couple of 100 bytes of the RPC header+message instead of
> relying on the XID. That is a good deal safer w.r.t. port reuse by other
> clients etc.

I'm amused at the juxtaposition here.
We have the possibility of using an MD5 hash over 100 bytes in a
comment on patch containing the comment

+ * Experiment shows that using the Jenkins hash improves the spectral
+ * properties of this hash, but the CPU cost of calculating it outweighs
+ * the advantages.

If a Jenkins hash is too expensive, I suspect MD5 would be even more
so...

I'm not suggesting either approach is right or wrong - just that it is
thought provoking.

Greg: did you have measurements to suggest that a Jenkins hash was too
expensive?   Did it just increase CPU load a bit, or did it affect
throughput?

Thanks,
NeilBrown

-------------------------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security?
Get stuff done quickly with pre-integrated technology to make your job easier
Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
_______________________________________________
NFS maillist  -  NFS@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nfs

Re: [PATCH 6/8] knfsd: repcache: use client IP address in hash

[Greg Banks]

On Mon, Oct 16, 2006 at 12:27:32PM +1000, Neil Brown wrote:
> On Wednesday October 11, trond.myklebust@fys.uio.no wrote:
> > On Wed, 2006-10-11 at 21:28 +1000, Greg Banks wrote:
> > > knfsd: Use the client's IP address in the duplicate request cache
> > > hash function, instead of just the XID.  This avoids contention
> > > on hash buckets when the workload has many clients whose XIDs are
> > > nearly in lockstep, a property seen on compute clusters using NFS
> > > for shared storage.
> > 
> > Note that some platforms (in particular the *BSDs) use an MD5 checksum
> > of the first couple of 100 bytes of the RPC header+message instead of
> > relying on the XID. That is a good deal safer w.r.t. port reuse by other
> > clients etc.
> 
> I'm amused at the juxtaposition here.
> We have the possibility of using an MD5 hash over 100 bytes in a
> comment on patch containing the comment
> 
> + * Experiment shows that using the Jenkins hash improves the spectral
> + * properties of this hash, but the CPU cost of calculating it outweighs
> + * the advantages.
> 
> If a Jenkins hash is too expensive, I suspect MD5 would be even more
> so...

;-)

> I'm not suggesting either approach is right or wrong - just that it is
> thought provoking.
> 
> Greg: did you have measurements to suggest that a Jenkins hash was too
> expensive?   Did it just increase CPU load a bit, or did it affect
> throughput?

Fmeh.  Reading my notes again, I had the following observations.

With the original hash function, testing with a fixed call rate showed
the probe rate graph had an interesting periodic behaviour, sawtooth
IIRC, with a significant variation of number of probes per call.
This lead me to conclude that the spectral properties of the hash
function were poor (I didn't actually dump the hash table to confirm).

Then I tried changing the hash function to a Jenkins hash of the XID
and the client IP address.  This significantly reduced the CPU time
spent in nfsd_cache_lookup in the single-node case, and the graph
of probe rate became flat indicating better spectral properties,
which is all very wonderful.  However in the 2-node test all the CPU
usage came back, and the saturation call rate dropped from about 80
Kcalls/sec to about 77 Kcalls/sec.

So I think what was happening was that the improved spectral properties
of the hash function helped make the chains a more consistent length
but did nothing to reduce the cacheline bouncing due to CPUs from
multiple nodes writing to the same cacheline in the hash index.

In light of this I can't explain what I was smoking when I wrote the
comment about "CPU cost of calculating it".  Sorry.

Nevertheless, I think an MD5 would have the same behaviour as I
observed with the Jenkins hash.

In retrospect, there are a couple of other approaches I might
have tried if I'd had the time:

 *  Use multiple hashes, keyed on XID only and attached to the
    struct ip_map (might suffer from potential lifetime problems
    without another data structure to manage the hashes).

 *  Change the algorithm to avoid writing to two hash index
    cachelines on every lookup in the steady-state case (not
    even sure if this is possible).

Greg.
-- 
Greg Banks, R&D Software Engineer, SGI Australian Software Group.
I don't speak for SGI.

-------------------------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security?
Get stuff done quickly with pre-integrated technology to make your job easier
Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
_______________________________________________
NFS maillist  -  NFS@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nfs

Re: [PATCH 6/8] knfsd: repcache: use client IP address in hash

[Trond Myklebust]

On Mon, 2006-10-16 at 12:27 +1000, Neil Brown wrote:
> On Wednesday October 11, trond.myklebust@fys.uio.no wrote:
> > On Wed, 2006-10-11 at 21:28 +1000, Greg Banks wrote:
> > > knfsd: Use the client's IP address in the duplicate request cache
> > > hash function, instead of just the XID.  This avoids contention
> > > on hash buckets when the workload has many clients whose XIDs are
> > > nearly in lockstep, a property seen on compute clusters using NFS
> > > for shared storage.
> > 
> > Note that some platforms (in particular the *BSDs) use an MD5 checksum
> > of the first couple of 100 bytes of the RPC header+message instead of
> > relying on the XID. That is a good deal safer w.r.t. port reuse by other
> > clients etc.
> 
> I'm amused at the juxtaposition here.
> We have the possibility of using an MD5 hash over 100 bytes in a
> comment on patch containing the comment
> 
> + * Experiment shows that using the Jenkins hash improves the spectral
> + * properties of this hash, but the CPU cost of calculating it outweighs
> + * the advantages.
> 
> If a Jenkins hash is too expensive, I suspect MD5 would be even more
> so...

The point of using the checksum is to avoid having to save the incoming
RPC message itself in the replay cache. i.e. the goal is data
compression. That is indeed likely to require a tradeoff in the form of
more CPU.

In a mainly TCP world, the point of the replay cache is almost always to
deal with the scenario where a network partition causes the connection
to be lost so that the client has to wait for the partition to heal,
then reconnect before finally replaying the request. Sod's law implies
that this is most likely to happen while the other clients are hammering
at the server at full blast.
That means you have to design the cache to hold large amounts of data
for long periods of time in order to be useful (hence compression).

BTW: It also means that a LRU algorithm for cache evictions is the wrong
thing to do. In fact the least recently used entry is likely to be the
most significant when you have a failure scenario like the above.

Cheers,
  Trond


-------------------------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security?
Get stuff done quickly with pre-integrated technology to make your job easier
Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
_______________________________________________
NFS maillist  -  NFS@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nfs

Re: [PATCH 6/8] knfsd: repcache: use client IP address in hash

[Neil Brown]

On Monday October 16, trond.myklebust@fys.uio.no wrote:
> On Mon, 2006-10-16 at 12:27 +1000, Neil Brown wrote:
> > On Wednesday October 11, trond.myklebust@fys.uio.no wrote:
> > > On Wed, 2006-10-11 at 21:28 +1000, Greg Banks wrote:
> > > > knfsd: Use the client's IP address in the duplicate request cache
> > > > hash function, instead of just the XID.  This avoids contention
> > > > on hash buckets when the workload has many clients whose XIDs are
> > > > nearly in lockstep, a property seen on compute clusters using NFS
> > > > for shared storage.
> > > 
> > > Note that some platforms (in particular the *BSDs) use an MD5 checksum
> > > of the first couple of 100 bytes of the RPC header+message instead of
> > > relying on the XID. That is a good deal safer w.r.t. port reuse by other
> > > clients etc.
> > 
> > I'm amused at the juxtaposition here.
> > We have the possibility of using an MD5 hash over 100 bytes in a
> > comment on patch containing the comment
> > 
> > + * Experiment shows that using the Jenkins hash improves the spectral
> > + * properties of this hash, but the CPU cost of calculating it outweighs
> > + * the advantages.
> > 
> > If a Jenkins hash is too expensive, I suspect MD5 would be even more
> > so...
> 
> The point of using the checksum is to avoid having to save the incoming
> RPC message itself in the replay cache. i.e. the goal is data
> compression. That is indeed likely to require a tradeoff in the form of
> more CPU.

Yeah... that makes sense.
Rejecting a write request based on a hash collision that didn't cover
the whole write request makes me a bit queezy, but it is probably not
going to be a problem in practice.

> 
> In a mainly TCP world, the point of the replay cache is almost always to
> deal with the scenario where a network partition causes the connection
> to be lost so that the client has to wait for the partition to heal,
> then reconnect before finally replaying the request. Sod's law implies
> that this is most likely to happen while the other clients are hammering
> at the server at full blast.
> That means you have to design the cache to hold large amounts of data
> for long periods of time in order to be useful (hence compression).
> 
> BTW: It also means that a LRU algorithm for cache evictions is the wrong
> thing to do. In fact the least recently used entry is likely to be the
> most significant when you have a failure scenario like the above.
> 

I can see your point, but I cannot think of a better cache eviction
algorithm ... other than "discard when we get a TCP-ACK for the
reply".  I really like that idea.  Might be fiddly to implement
though.

For UDP I guess we are stuck with LRU and crossing fingers.

It probably makes sense to have quite separate caches for UDP and
TCP. with very different disciplines.

Thanks for the thoughts.

NeilBrown

-------------------------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security?
Get stuff done quickly with pre-integrated technology to make your job easier
Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
_______________________________________________
NFS maillist  -  NFS@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nfs

Re: [PATCH 6/8] knfsd: repcache: use client IP address in hash

[J. Bruce Fields]

On Wed, Oct 11, 2006 at 09:28:50PM +1000, Greg Banks wrote:
> knfsd: Use the client's IP address in the duplicate request cache
> hash function, instead of just the XID.

By the way, do we ever match the credential used on the replayed request
with the credential used on the original request?  From a quick check of
the code, I can't see any place where we do.

It strikes me as something as an attacker might be able to have some fun
with.  (Poison the cache with requests matching xid's you expect to be
used in the future?  "Replay" somebody else's request just to see a
response that you wouldn't otherwise have been able to?)

--b.

-------------------------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security?
Get stuff done quickly with pre-integrated technology to make your job easier
Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
_______________________________________________
NFS maillist  -  NFS@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nfs