Fri 18:00 Sat 00:00 Sat 06:00 Sat 12:00 Sat 18:00 Sun 00:00 Sun 06:00 Sun12:00 Sun 18:00 Mon 00:00 Mon 06:00 Mon 12:00 Mon 18:00 Tue 00:00 Tue 06:00Tue 12:00 Tue 18:00 Wed 00:00 Wed 06:00 Wed 12:00 Wed 18:00100020003000400050006000Reads/Writes per hourWritesReads (all)Figure 1 - Read and Write Traffic Over Time5.2. File SharingOne property observed in the DEC-SRC trace is the tendency of files that areused by multiple workstations to make up a significant proportion of readtraffic but a very small proportion of write traffic. This has importantimplications for a caching strategy, since, when it is true, files that arecached at many places very rarely need to be invalidated. Although thePrinceton computing facility does not have a single workstation per user, asimilar metric is the degree to which files read by more than one user areread and written. In this respect, the Princeton trace is very similar tothe DEC-SRC trace. Files read by more than one user make up more than 60% ofread traffic, but less than 2% of write traffic. Files shared by more thanten users make up less than .2% of write traffic but still more than 30% ofread traffic. Figure 3 plots the number of users who have previously readeach file against the number of reads and writes.5.3. File "Entropy"Files in the DEC-SRC trace demonstrated a strong tendency to "become"read-only as they were read more and more often. That is, the probabilitythat the next operation on a given file will overwrite the file drops offshar ply in proportion to the number of times it has been read in the past.Like the sharing property, this has implications for a caching strategy,since the probability that cached data is valid influences the choice of avalidation scheme. Again, we find this property to be very strong in thePrinceton trace. For any file access in the trace, the probability that itis a write is about 27%. If the file has already been read at least oncesince it was last written to, the write probability drops to 10%. Once thefile has been read at least five times, the write probability drops below1%. Fig ure 4 plots the observed write probability against the number ofreads since the last write.Thu 00:00  Thu 06:00  Thu 12:00  Thu 18:00  Fri 00:00  Fri 06:00  Fri 12:00Fri 18:00 Sat 00:00 Sat 06:00 Sat 12:00 Sat 18:00 Sun 00:00 Sun 06:00 Sun12:00 Sun 18:00 Mon 00:00 Mon 06:00 Mon 12:00 Mon 18:00 Tue 00:00 Tue 06:00Tue 12:00 Tue 18:00 Wed 00:00 Wed 06:00 Wed 12:00 Wed 18:0010002000300040005000Total reads per hourCache Hits (estimated)Cache Misses (actual)Figure 2 - Cache Hits and Misses Over Time6. ConclusionsAlthough filesystem traces are a useful tool for the analysis of current andproposed systems, the difficulty of collecting meaningful trace data makessuch traces difficult to obtain. The performance degradation introduced bythe trace software and the volume of raw data generated makes traces overlong time periods and outside of comput ing research facilities particularlyhard to conduct.Although not as accurate as direct, kernel-based tracing, a passive networkmonitor such as the one described in this paper can permit tracing ofdistributed systems relatively easily. The ability to limit the datacollected to a high-level log of only the data required can make itpractical to conduct traces over several months. Such a long term trace ispresently being conducted at Princeton as part of the author's research onfilesystem caching. The non-intrusive nature of the data collection makestraces possible at facilities where kernel modification is impracti cal orunacceptable.It is the author's hope that other sites (particularly those not doingcomputing research) will make use of this toolkit and will make the tracesavailable to filesystem researchers.7. AvailabilityThe toolkit, consisting of rpcspy, nfstrace, and several support scripts,currently runs under several BSD-derived platforms, including ULTRIX 4.x,SunOS 4.x, and IBM-RT/AOS. It is available for anonymous ftp over theInternet from samadams.princeton.edu, in the compressed tar filenfstrace/nfstrace.tar.Z.Thu 00:00  Thu 06:00  Thu 12:00  Thu 18:00  Fri 00:00  Fri 06:00  Fri 12:00Fri 18:00 Sat 00:00 Sat 06:00 Sat 12:00 Sat 18:00 Sun 00:00 Sun 06:00 Sun12:00 Sun 18:00 Mon 00:00 Mon 06:00 Mon 12:00 Mon 18:00 Tue 00:00 Tue 06:00Tue 12:00 Tue 18:00 Wed 00:00 Wed 06:00 Wed 12:00 Wed 18:00 0100200300Reads per hourCache Hits (estimated)Cache Misses (actual)Figure 3 - Cache Hits and Misses Over Time - Private Workstation0 5 10 15 20n (readers)020406080100% of Reads and Writes used by > n usersReadsWritesFigure 4 - Degree of Sharing for Reads and Writes0 5 10 15 20Reads Since Last Write0.00.10.2P(next operation is write)Figure 5 - Probability of Write Given >= n Previous Reads8. AcknowledgmentsThe author would like to gratefully acknowledge Jim Roberts and Steve Beckfor their help in getting the trace machine up and running, Rafael Alonsofor his helpful comments and direction, and the members of the pro gramcommittee for their valuable suggestions. Jim Plank deserves special thanksfor writing jgraph, the software which produced the figures in this paper.9. References[1] Sandberg, R., Goldberg, D., Kleiman, S., Walsh, D., & Lyon, B. "Designand Implementation of the Sun Net work File System." Proc. USENIX, Summer,1985.[2] Mogul, J., Rashid, R., & Accetta, M. "The Packet Filter: An EfficientMechanism for User-Level Network Code." Proc. 11th ACM Symp. on OperatingSystems Principles, 1987.[3] Ousterhout J., et al. "A Trace-Driven Analysis of the Unix 4.2 BSD FileSystem." Proc. 10th ACM Symp. on Operating Systems Principles, 1985.[4] Floyd, R. "Short-Term File Reference Patterns in a UNIX Environment,"TR-177 Dept. Comp. Sci, U. of Rochester, 1986.[5] Baker, M. et al. "Measurements of a Distributed File System," Proc. 13thACM Symp. on Operating Systems Principles, 1991.[6] Metcalfe, R. & Boggs, D. "Ethernet: Distributed Packet Switching forLocal Computer Networks," CACM July, 1976.[7] "Etherfind(8) Manual Page," SunOS Reference Manual, Sun Microsystems,1988.[8] Gusella, R. "Analysis of Diskless Workstation Traffic on an Ethernet,"TR-UCB/CSD-87/379, University Of California, Berkeley, 1987.[9] "NIT(4) Manual Page," SunOS Reference Manual, Sun Microsystems, 1988.[10] "XDR Protocol Specification," Networking on the Sun Workstation, SunMicrosystems, 1986.[11] "RPC Protocol Specification," Networking on the Sun Workstation, SunMicrosystems, 1986.[12] "NFS Protocol Specification," Networking on the Sun Workstation, SunMicrosystems, 1986.[13] Postel, J. "User Datagram Protocol," RFC 768, Network InformationCenter, 1980.[14] Blaze, M., and Alonso, R., "Long-Term Caching Strategies for Very LargeDistributed File Systems," Proc. Summer 1991 USENIX, 1991.Matt Blaze is a Ph.D. candidate in Computer Science at Princeton University,where he expects to receive his degree in the Spring of 1992. His researchinterests include distributed systems, operating systems, databases, andprogramming environments. His current research focuses on caching in verylarge distributed filesys tems. In 1988 he received an M.S. in ComputerScience from Columbia University and in 1986 a B.S. from Hunter College. Hecan be reached via email at mab@cs.princeton.edu or via US mail at Dept. ofComputer Science, Princeton University, 35 Olden Street, Princeton NJ08544.