2 .\" The Regents of the University of California. All rights reserved.
4 .\" This document is derived from software contributed to Berkeley by
5 .\" Rick Macklem at The University of Guelph.
7 .\" Redistribution and use in source and binary forms, with or without
8 .\" modification, are permitted provided that the following conditions
10 .\" 1. Redistributions of source code must retain the above copyright
11 .\" notice, this list of conditions and the following disclaimer.
12 .\" 2. Redistributions in binary form must reproduce the above copyright
13 .\" notice, this list of conditions and the following disclaimer in the
14 .\" documentation and/or other materials provided with the distribution.
15 .\" 3. Neither the name of the University nor the names of its contributors
16 .\" may be used to endorse or promote products derived from this software
17 .\" without specific prior written permission.
19 .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
20 .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 .\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
23 .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25 .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 .\" @(#)2.t 8.1 (Berkeley) 6/8/93
33 .sh 1 "Not Quite NFS, Crash Tolerant Cache Consistency for NFS"
35 Not Quite NFS (NQNFS) is an NFS like protocol designed to maintain full cache
36 consistency between clients in a crash tolerant manner.
37 It is an adaptation of the NFS protocol such that the server supports both NFS
38 and NQNFS clients while maintaining full consistency between the server and
40 This section borrows heavily from work done on Spritely-NFS [Srinivasan89],
41 but uses Leases [Gray89] to avoid the need to recover server state information
43 The reader is strongly encouraged to read these references before
44 trying to grasp the material presented here.
47 The protocol maintains cache consistency by using a somewhat
48 Sprite [Nelson88] like protocol,
49 but is based on short term leases\** instead of hard state information
52 \** A lease is a ticket permitting an activity that is
53 valid until some expiry time.
55 The basic principal is that the protocol will disable client caching of a
56 file whenever that file is write shared\**.
58 \** Write sharing occurs when at least one client is modifying a file while
59 other client(s) are reading the file.
61 Whenever a client wishes to cache data for a file it must hold a valid lease.
62 There are three types of leases: read caching, write caching and non-caching.
63 The latter type requires that all file operations be done synchronously with
65 A read caching lease allows for client data caching, but no file modifications
67 A write caching lease allows for client caching of writes,
68 but requires that all writes be pushed to the server when the lease expires.
69 If a client has dirty buffers\**
71 \** Cached write data is not yet pushed (written) to the server.
73 when a write cache lease has almost expired, it will attempt to
74 extend the lease but is required to push the dirty buffers if extension fails.
75 A client gets leases by either doing a \fBGetLease RPC\fR or by piggybacking
76 a \fBGetLease Request\fR onto another RPC. Piggybacking is supported for the
77 frequent RPCs Getattr, Setattr, Lookup, Readlink, Read, Write and Readdir
78 in an effort to minimize the number of \fBGetLease RPCs\fR required.
79 All leases are at the granularity of a file, since all NFS RPCs operate on
80 individual files and NFS has no intrinsic notion of a file hierarchy.
81 Directories, symbolic links and file attributes may be read cached but
83 The exception here is the attribute file_size, which is updated during cached
84 writing on the client to reflect a growing file.
86 It is the server's responsibility to ensure that consistency is maintained
87 among the NQNFS clients by disabling client caching whenever a server file
88 operation would cause inconsistencies.
89 The possibility of inconsistencies occurs whenever a client has
90 a write caching lease and any other client,
91 or local operations on the server,
92 tries to access the file or when
93 a modify operation is attempted on a file being read cached by client(s).
94 At this time, the server sends an \fBeviction notice\fR to all clients holding
95 the lease and then waits for lease termination.
96 Lease termination occurs when a \fBvacated the premises\fR message has been
97 received from all the clients that have signed the lease or when the lease
99 The message pair \fBeviction notice\fR and \fBvacated the premises\fR roughly
100 correspond to a Sprite server\(->client callback, but are not implemented as an
101 actual RPC, to avoid the server waiting indefinitely for a reply from a dead
104 Server consistency checking can be viewed as issuing intrinsic leases for a
105 file operation for the duration of the operation only. For example, the
106 \fBCreate RPC\fR will get an intrinsic write lease on the directory in which
107 the file is being created, disabling client read caches for that directory.
109 By relegating this responsibility to the server, consistency between the
110 server and NQNFS clients is maintained when NFS clients are modifying the
111 file system as well.\**
113 \** The NFS clients will continue to be \fIapproximately\fR consistent with
117 The leases are issued as time intervals to avoid the requirement of time of day
118 clock synchronization. There are three important time constants known to
119 the server. The \fBmaximum_lease_term\fR sets an upper bound on lease duration.
120 The \fBclock_skew\fR is added to all lease terms on the server to correct for
121 differing clock speeds between the client and server and \fBwrite_slack\fR is
122 the number of seconds the server is willing to wait for a client with
123 an expired write caching lease to push dirty writes.
125 The server maintains a \fBmodify_revision\fR number for each file. It is
126 defined as a unsigned quadword integer that is never zero and that must
127 increase whenever the corresponding file is modified on the server.
129 by the client to determine whether or not cached data for the file is
131 Generating this value is easier said than done. The current implementation
132 uses the following technique, which is believed to be adequate.
133 The high order longword is stored in the ufs inode and is initialized to one
134 when an inode is first allocated.
135 The low order longword is stored in main memory only and is initialized to
136 zero when an inode is read in from disk.
137 When the file is modified for the first time within a given second of
138 wall clock time, the high order longword is incremented by one and
139 the low order longword reset to zero.
140 For subsequent modifications within the same second of wall clock
141 time, the low order longword is incremented. If the low order longword wraps
142 around to zero, the high order longword is incremented again.
143 Since the high order longword only increments once per second and the inode
144 is pushed to disk frequently during file modification, this implies
145 0 \(<= Current\(miDisk \(<= 5.
146 When the inode is read in from disk, 10
147 is added to the high order longword, which ensures that the quadword
148 is greater than any value it could have had before a crash.
149 This introduces apparent modifications every time the inode falls out of
150 the LRU inode cache, but this should only reduce the client caching performance
151 by a (hopefully) small margin.
152 .sh 2 "Crash Recovery and other Failure Scenarios"
154 The server must maintain the state of all the current leases held by clients.
155 The nice thing about short term leases is that maximum_lease_term seconds
156 after the server stops issuing leases, there are no current leases left.
157 As such, server crash recovery does not require any state recovery. After
158 rebooting, the server refuses to service any RPCs except for writes until
159 write_slack seconds after the last lease would have expired\**.
161 \** The last lease expiry time may be safely estimated as
162 "boottime+maximum_lease_term+clock_skew" for machines that cannot store
163 it in nonvolatile RAM.
165 By then, the server would not have any outstanding leases to recover the
166 state of and the clients have had at least write_slack seconds to push dirty
167 writes to the server and get the server sync'd up to date. After this, the
168 server simply services requests in a manner similar to NFS.
169 In an effort to minimize the effect of "recovery storms" [Baker91],
170 the server replies \fBtry_again_later\fR to the RPCs it is not
171 yet ready to service.
173 After a client crashes, the server may have to wait for a lease to timeout
174 before servicing a request if write sharing of a file with a cachable lease
175 on the client is about to occur.
176 As for the client, it simply starts up getting any leases it now needs. Any
177 outstanding leases for that client on the server prior to the crash will either be renewed or expire
180 Certain network partitioning failures are more problematic. If a client to
181 server network connection is severed just before a write caching lease expires,
182 the client cannot push the dirty writes to the server. After the lease expires
183 on the server, the server permits other clients to access the file with the
184 potential of getting stale data. Unfortunately I believe this failure scenario
185 is intrinsic in any delay write caching scheme unless the server is required to
186 wait \fBforever\fR for a client to regain contact\**.
188 \** Gray and Cheriton avoid this problem by using a \fBwrite through\fR policy.
190 Since the write caching lease has expired on the client,
191 it will sync up with the
192 server as soon as the network connection has been re-established.
194 There is another failure condition that can occur when the server is congested.
195 The worst case scenario would have the client pushing dirty writes to the server
196 but a large request queue on the server delays these writes for more than
197 \fBwrite_slack\fR seconds. It is hoped that a congestion control scheme using
198 the \fBtry_again_later\fR RPC reply after booting combined with
199 the following lease termination rule for write caching leases
200 can minimize the risk of this occurrence.
201 A write caching lease is only terminated on the server when there are have
202 been no writes to the file and the server has not been overloaded during
203 the previous write_slack seconds. The server has not been overloaded
204 is approximated by a test for sleeping nfsd(s) at the end of the write_slack
206 .sh 2 "Server Disk Full"
208 There is a serious unresolved problem for delayed write caching with respect to
209 server disk space allocation.
210 When the disk on the file server is full, delayed write RPCs can fail
211 due to "out of space".
212 For NFS, this occurrence results in an error return from the close system
213 call on the file, since the dirty blocks are pushed on close.
214 Processes writing important files can check for this error return
215 to ensure that the file was written successfully.
216 For NQNFS, the dirty blocks are not pushed on close and as such the client
217 may not attempt the write RPC until after the process has done the close
218 which implies no error return from the close.
219 For the current prototype,
220 the only solution is to modify programs writing important
221 file(s) to call fsync and check for an error return from it instead of close.
222 .sh 2 "Protocol Details"
224 The protocol specification is identical to that of NFS [Sun89] except for
225 the following changes.
229 Program Number 300105
233 Readdir_and_Lookup RPC
235 struct readdirlookargs {
247 nqnfs_fattr entry_attrib;
254 union readdirlookres switch (stat status) {
265 NQNFSPROC_READDIRLOOK(readdirlookargs) = 18;
267 Reads entries in a directory in a manner analogous to the NFSPROC_READDIR RPC
268 in NFS, but returns the file handle and attributes of each entry as well.
269 This allows the attribute and lookup caches to be primed.
273 struct getleaseargs {
279 union getleaseres switch (stat status) {
284 nqnfs_fattr attributes;
290 NQNFSPROC_GETLEASE(getleaseargs) = 19;
292 Gets a lease for "file" valid for "duration" seconds from when the lease
293 was issued on the server\**.
295 \** To be safe, the client may only assume that the lease is valid
296 for ``duration'' seconds from when the RPC request was sent to the server.
298 The lease permits client caching if "cachable" is true.
299 The modify revision level and attributes for the file are also returned.
304 NQNFSPROC_EVICTED (fhandle) = 21;
306 This message is sent from the server to the client. When the client receives
307 the message, it should flush data associated with the file represented by
308 "fhandle" from its caches and then send the \fBVacated Message\fR back to
309 the server. Flushing includes pushing any dirty writes via. write RPCs.
314 NQNFSPROC_VACATED (fhandle) = 20;
316 This message is sent from the client to the server in response to the
317 \fBEviction Message\fR. See above.
329 NQNFSPROC_ACCESS(accessargs) = 22;
331 The access RPC does permission checking on the server for the given type
332 of access required by the client for the file.
333 Use of this RPC avoids accessibility problems caused by client->server uid
336 Piggybacked Get Lease Request
338 The piggybacked get lease request is functionally equivalent to the Get Lease
339 RPC except that is attached to one of the other NQNFS RPC requests as follows.
340 A getleaserequest is prepended to all of the request arguments for NQNFS
341 and a getleaserequestres is inserted in all NFS result structures just after
342 the "stat" field only if "stat == NFS_OK".
344 union getleaserequest switch (cachetype type) {
352 union getleaserequestres switch (cachetype type) {
362 The get lease request applies to the file that the attached RPC operates on
363 and the file attributes remain in the same location as for the NFS RPC reply
366 Three additional "stat" values
368 Three additional values have been added to the enumerated type "stat".
374 The "expired" value indicates that a lease has expired.
376 value is returned by the server when it wishes the client to retry the
377 RPC request after a short delay. It is used during crash recovery (Section 2)
378 and may also be useful for server congestion control.
379 The "authetication error" value is returned for kerberized mount points to
380 indicate that there is no cached authentication mapping and a Kerberos ticket
381 for the principal is required.
392 Type of lease requested. NQLNONE is used to indicate no piggybacked lease
397 typedef unsigned hyper modifyrev;
399 The "modifyrev" is a unsigned quadword integer value that is never zero
400 and increases every time the corresponding file is modified on the server.
406 unsigned nano_seconds;
409 For NQNFS times are handled at nano second resolution instead of micro second
423 unsigned hyper bytes;
434 The nqnfs_fattr structure is modified from the NFS fattr so that it stores
435 the file size as a 64bit quantity and the storage occupied as a 64bit number
436 of bytes. It also has fields added for the 4.4BSD va_flags and va_gen fields
437 as well as the file's modify rev level.
452 The nqnfs_sattr structure is modified from the NFS sattr structure in the
453 same manner as fattr.
455 The arguments to several of the NFS RPCs have been modified as well. Mostly,
456 these are minor changes to use 64bit file offsets or similar. The modified
457 argument structures follow.
461 struct lookup_diropargs {
467 union lookup_diropres switch (stat status) {
470 union getleaserequestres lookup_lease;
472 nqnfs_fattr attributes;
479 The additional "duration" argument tells the server to get a lease for the
480 name being looked up if it is non-zero and the lease is specified
485 struct nqnfs_readargs {
487 unsigned hyper offset;
494 struct nqnfs_writeargs {
496 unsigned hyper offset;
501 The "append" argument is true for apeend only write operations.
503 Get Filesystem Attributes RPC
505 union nqnfs_statfsres (stat status) {
520 The "files" field is the number of files in the file system and the "files_free"
521 is the number of additional files that can be created.
524 The configuration and tuning of an NFS environment tends to be a bit of a
525 mystic art, but hopefully this paper along with the man pages and other
526 reading will be helpful. Good Luck.