The files:
nfsclient.c
nfsclient.h
makefile
api/makefile
api/nfsapi.c
api/nfsapi.h
api/instrument.c
myrpc/awake.c
myrpc/awake.h
myrpc/makefile
myrpc/mount.h
myrpc/mount_clnt.c
myrpc/mount_svc.c
myrpc/mount_xdr.c
myrpc/nfs_prot.h
myrpc/nfs_prot_clnt.c
myrpc/nfs_prot_svc.c
myrpc/nfs_prot_xdr.c

Effectiveness of an NFS cache

The purpose of this assignment was to implement a simple Least Recently Used cache for our NFS client. My design decisions on this cache were that it should be:


Experiments

First of all, I decided that the only metric I would measure would be response time from the application's point of view. Other important metrics include

The first factor we would like to vary is, naturally, the presence or absence of a cache. My hypothesis was that response time would be better with the cache.

I ran three different profiles of application with and without the cache. The profiles were: reading ten 16k files ten times, reading three files of 1 megabyte, 440 kilobytes, and 188 kilobytes ten times, and an interspersion between the two four times.

Here are some sample values for repeated runs of this test without the cache, with their means and variances. All values are in seconds.

  Several small Few large Interspersed
response
time
1.646652
1.429611
1.528120
1.905650
1.549155
1.542954
1.557152
1.409769
1.572472
2.028570
1.422529
1.675956
1.682209
1.663814
1.398795
1.574566
1.471017
1.475718
1.482658
1.825816
3.439753
3.439407
3.559233
3.897712
3.462158
3.374335
3.567981
3.506511
3.551039
3.657332
3.438312
3.793020
3.604678
3.405391
4.136171
4.336967
3.767816
3.715689
3.558361
3.589751
3.508682
3.602645
3.549313
3.942828
mean 1.59215915 3.55723275 3.7265243
variance 0.02857536 0.02441722 0.0771113

None of this is particularly surprising. As always, it is gratifying to see that the variance is small, as it suggests that a reasonable number of runs is enough to generate representative results.


For the runs with the cache, I used a cache large enough to hold all the files. This is the cache that will give us ideal performance; LRU, like any replacement policy, is a concession to the sad reality that we cannot keep everything in cache forever.

Note that the first value in each run is much higher than the others. This is the first time the file is loaded, an unavoidable startup miss. The file must be both fetched over RPC and written to disk. This overhead is amortized over all the times the file is read.

  Several small Few large Interspersed
Startup miss
Response time
2.461696
1.844097
1.982967
2.156388
1.814694
1.988630
1.881075
2.022450
1.842045
1.993219
1.869258
1.970206
1.915221
10.150296
5.743487
6.013501
6.001712
5.495977
5.664555
6.505875
6.254668
6.260654
5.771529
5.819221
5.579478
6.113525
10.570553
6.913707
8.478969
5.886286
5.736703
6.128009
8.419220
8.281347
6.922081
5.743408
7.216393
6.322908
5.730222
Average non-startup 1.94002080 5.93534850 6.81493775
Ratio of startup to non-startup 1.26890180 1.71014320 1.55108577
Ratio of non-startup to startup 0.78808300 0.58474630 0.64470967

We could use these numbers to calculate how many references to a file it would take to fully amortize the startup cost with respect to the non-cached version. Unfortunately, our cached version actually takes longer than the non-cached version!

The ratios of response time cached to response time uncached:

Several small 1.21848424093366
Few large 1.59273037530145
Interspersed 1.91579753953407
Average 1.57567071858973

Since our own NFSClient and the NFS daemon are running on the same machine (swift.cs.unc.edu), it seems reasonable to assume that loading these files from disk would take the same amount of time for either process. The obvious conclusion is that either we're doing a ridiculous amount of overhead, which I don't think we are, or the NFS daemon does a much better job of caching, probably in memory. Thus my hypothesis of improved response time was shown to be false.

If our only goal were to lessen response time, we would abandon this caching scheme here, as it is slower than a cacheless version. However, it should still reduce load on the server and network traffic.


Switching horses midstream

Clearly it's time for a new hypothesis. I submit that using a cache, even a slowish disk-based one, can drastically reduce load on the NFS server and traffic between the client and the NFS server.

I completely reinstrumented my system to test this. I kept a running tally of the number of socket connections opened and the bytes sent and received over them. I also kept a tally of the number of RPC calls made, which is a good approximation of the load on the RPC service, and the bytes sent in the arguments and return values of those.

Running the same six profiles as I did before, here were the results. Note that these are the same every time the profile is run, because unlike network latency, the code is completely deterministic.

  no cache perfect cache
several
small
rpccalls == 311
rpcbytes == 1444140
socketsends == 491
socketrecvs == 491
socketsendbytes == 1401541
socketrecvbytes == 5538
rpccalls == 40
rpcbytes == 145008
socketsends == 491
socketrecvs == 491
socketsendbytes == 1401541
socketrecvbytes == 5538
few
large
rpccalls == 962
rpcbytes == 7426310
socketsends == 1007
socketrecvs == 1007
socketsendbytes == 7292827
socketrecvbytes == 15367
rpccalls == 207
rpcbytes == 1658327
socketsends == 1007
socketrecvs == 1007
socketsendbytes == 7292827
socketrecvbytes == 15367
inter-
spersed
rpccalls == 975
rpcbytes == 7214708
socketsends == 1053
socketrecvs == 1053
socketsendbytes == 7080013
socketrecvbytes == 16102
rpccalls == 246
rpcbytes == 1803275
socketsends == 1053
socketrecvs == 1053
socketsendbytes == 7080013
socketrecvbytes == 16102

The difference in the number of RPC calls and the bytes sent over RPC is dramatic. This is due to the cacheless version having to read the entire large file every time it reads it; since each RPC call can only transfer 8K of data, each read is going to take a minimum of 125 calls! And of course, the file size has an even more direct relationship with the bytes transferred. With a perfect cache, every byte only needs to be transferred once; with no cache, every byte needs to be transferred as many times as the file is read.

So what effect does the cache size have on our new metrics of server load and RPC traffic? All other things being equal, here are the results for a geometric progression of cache sizes.

[eagle] 14> n /tmp/nfscache 5000
: rpccalls == 498
: rpcbytes == 3608374
: rpccalls/cachesize == 0.09960000
: rpcbytes/cachesize == 721.6748

[eagle] 14> n /tmp/nfscache 10000
: rpccalls == 498
: rpcbytes == 3608374
: rpccalls/cachesize == 0.04980000
: rpcbytes/cachesize == 360.8374

[eagle] 14> n /tmp/nfscache 20000
: rpccalls == 488
: rpcbytes == 3591386
: rpccalls/cachesize == 0.02440000
: rpcbytes/cachesize == 179.5693

[eagle] 14> n /tmp/nfscache 40000
: rpccalls == 485
: rpcbytes == 3575398
: rpccalls/cachesize == 0.01212500
: rpcbytes/cachesize == 89.3849

[eagle] 14> n /tmp/nfscache 80000
: rpccalls == 474
: rpcbytes == 3527138
: rpccalls/cachesize == 0.00592500
: rpcbytes/cachesize == 44.0892

[eagle] 14> n /tmp/nfscache 160000
: rpccalls == 462
: rpcbytes == 3463186
: rpccalls/cachesize == 0.00288750
: rpcbytes/cachesize == 21.6449

[eagle] 14> n /tmp/nfscache 320000
: rpccalls == 438
: rpcbytes == 3287141
: rpccalls/cachesize == 0.00136875
: rpcbytes/cachesize == 10.2723

[eagle] 14> n /tmp/nfscache 640000
: rpccalls == 403
: rpcbytes == 3029584
: rpccalls/cachesize == 0.00062969
: rpcbytes/cachesize == 4.7337

[eagle] 14> n /tmp/nfscache 1280000
: rpccalls == 343
: rpcbytes == 2523830
: rpccalls/cachesize == 0.00026797
: rpcbytes/cachesize == 1.9717

[eagle] 14> n /tmp/nfscache 2560000
: rpccalls == 246
: rpcbytes == 1803275
: rpccalls/cachesize == 0.00009609
: rpcbytes/cachesize == 0.7044

[eagle] 14> n /tmp/nfscache 5120000
: rpccalls == 246
: rpcbytes == 1803275
: rpccalls/cachesize == 0.00004805
: rpcbytes/cachesize == 0.3522

The ratios of calls to bytes don't tell us as much as we might have thought.

The differences disappear at the low ends and high ends, where nothing and everything can be cached. But notice the progression of differences in the middle:

calls: 11, 13, 24, 35, 60, 97
bytes: 5k, 7k, 18k, 26k, 49k, 72k

That's a pretty good approximation of a Fibonacci series. I hypothesize that this progression is a direct reflection of the size distribution of the file set. I submit that a more interesting file set would be one in which the sizes varied linearly, and the order in which files are loaded is randomized. However, this is a total of three independent variables, one of them random, so it is a bit outside the scope of this report.


Miscellaneous notes

The client now additionally incorporates a filehandle cache. Thus, if different applications open the same file (distinguished by its pathname, since only one server may be active) the client does not need to make additional lookup RPCs to the NFS server.

For evaluating which file was least recently used, I use a system of integer timestamps. Every time a file is read or opened, its last-used value gets the current timestamp, and the current timestamp is incremented. Thus, there are never any ties between files.

If multiple applications are accessing this client simultaneously, they all benefit from the prefetching of files. However, the risk is always run that too wide a variety of requests can cause the cache to be overwritten too quickly to be of much use.

I was not able to run multiple testing applications simultaneously, however. The fact that they use UNIX sockets to communicate means that the application must be on the same filesystem as the server, so it is difficult to separate the effects of multiple accesses from those of shared resources.

It is trivial to note that the degree of reuse and sharing of files is directly proportional to the effectiveness of caching. If you never use a file more than once, you are just wasting overhead by caching it. And if you use the same file over and over, you can essentially eliminate network connections (ignoring consistency if writes occur from elsewhere). Here is the client run with a cache big enough for exactly half of those ten 16k files. The first run reads each of the files in turn, a hundred times total; the second reads one file a hundred times.

[eagle] 14> n /tmp/nfscache/ 80000
: rpccalls == 31
: rpcbytes == 160100

[eagle] 14> n /tmp/nfscache/ 80000
: rpccalls == 4
: rpcbytes == 16064


Conclusions

Important metrics to consider when evaluating a cache include response time, server load, client resource usage, network traffic, and consistency semantics.

I conclude that adding a simple cache to our NFS client definitely reduces the load on the RPC service and network traffic between the client and the service.

It appears that a disk-based cache does not offer any improvement in response time over a cacheless system. This is presumably due to memory caching on the server side.

Distribution of file sizes can strongly affect the performance of a cache. If the designer of the cache has any information about how often different file sizes are accessed, he could use this information to create a better replacement scheme than LRU. If those weights are known precisely, the problem is equivalent to the knapsack problem. The smaller the average file size is compared to the cache size, the more closely it resembles the fractional knapsack problem, which can be solved with greedy methods. Implementing such a method would be an interesting direction for this project to take.