knfsd: repcache: use client IP address in hash
Subsystems (2)
PATCH 6/8 knfsd: repcache: use client IP address in hash
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.
---
fs/nfsd/nfscache.c | 11 ++++++++--- 1 files changed, 8 insertions(+), 3 deletions(-)
fs/nfsd/nfscache.c +8 -3
@@ -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 *rqstpint 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 *rqstpif (!(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.
Signature · 13 lines
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 - [email protected] https://lists.sourceforge.net/lists/listinfo/nfs
Quoted 5 lines · 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.
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 - [email protected]
https://lists.sourceforge.net/lists/listinfo/nfs
Quoted 7 lines · Trond Myklebust
Quoted 5 lines · 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.
Quoted 5 lines
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.
Signature · 11 lines
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 - [email protected] https://lists.sourceforge.net/lists/listinfo/nfs
Quoted 14 lines · Greg Banks
Quoted 7 lines · Trond Myklebust
Quoted 5 lines · 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.
Quoted 5 lines
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.
Quoted 6 lines
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.
Signature · 11 lines
"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 - [email protected] https://lists.sourceforge.net/lists/listinfo/nfs
Quoted 8 lines · Greg Banks
Quoted 7 lines · Trond Myklebust
Quoted 5 lines · 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.
Quoted 8 lines
Quoted 5 lines
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 - [email protected]
https://lists.sourceforge.net/lists/listinfo/nfs
Quoted 11 lines · On Wednesday October 11, [email protected] wrote:
Quoted 5 lines · 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.
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 - [email protected]
https://lists.sourceforge.net/lists/listinfo/nfs
Quoted 17 lines · Neil Brown
Quoted 11 lines · On Wednesday October 11, [email protected] wrote:
Quoted 5 lines · 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.
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
Quoted 6 lines
+ * 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...
;-)
Quoted 6 lines
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.
Signature · 11 lines
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 - [email protected] https://lists.sourceforge.net/lists/listinfo/nfs
Quoted 17 lines · Neil Brown
Quoted 11 lines · On Wednesday October 11, [email protected] wrote:
Quoted 5 lines · 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.
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
Quoted 6 lines
+ * 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 - [email protected]
https://lists.sourceforge.net/lists/listinfo/nfs
Quoted 22 lines · On Monday October 16, [email protected] wrote:
Quoted 21 lines · Neil Brown
Quoted 11 lines · On Wednesday October 11, [email protected] wrote:
Quoted 5 lines · 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.
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.
Quoted 7 lines
Quoted 2 lines
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.
Quoted 10 lines
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).
Quoted 4 lines
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 - [email protected]
https://lists.sourceforge.net/lists/listinfo/nfs
Quoted 2 lines · Greg Banks
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 - [email protected]
https://lists.sourceforge.net/lists/listinfo/nfs