1Outline for Today’s LectureAdministrative:– Assignment 5 – start NOW. Read the newsgroup. Justin will be out of town this weekend.– Handout – Nachos guide formatted!Objective: – Disk dilemmasRotational MediaSectorTrackCylinderHeadPlatterArmAccess time = seek time + rotational delay + transfer timeseek time= 5-15 milliseconds to move the disk arm and settle on a cylinderrotational delay= 8 milliseconds for full rotation at 7200 RPM: average delay = 4 mstransfer time= 1 millisecond for an 8KB block at 8 MB/sBandwidth utilization is less than 50% for any noncontiguous access at a block grain.Rotational MediaSectorTrackCylinderHeadPlatterArmAccess time = seek time + rotational delay + transfer time + spinup timeseek time= 5-15 milliseconds to move the disk arm and settle on a cylinderrotational delay= 8 milliseconds for full rotation at 7200 RPM: average delay = 4 mstransfer time= 1 millisecond for an 8KB block at 8 MB/sSpinup/spindown time= ~1 secondBandwidth utilization is less than 50% for any noncontiguous access at a block grain.What to do about Disks?• Avoid them altogether! Caching• Disk scheduling– Idea is to reorder outstanding requests to minimize seeks.• Layout on disk– Placement to minimize disk overhead• Build a better disk (or substitute)– Example: RAID2File Buffer Cache• Avoid the disk for as many file operations as possible.• Cache acts as a filter for the requests seen by the disk− reads served best.• Delayed writebackwill avoid going to disk at all for temp files.MemoryFilecacheProcHandling Updates in the File Cache1. Blocks may be modified in memory once they have been brought into the cache.Modified blocks are dirty and must (eventually) be written back.2. Once a block is modified in memory, the write back to disk may not be immediate (synchronous).Delayed writes absorb many small updates with one disk write.How long should the system hold dirty data in memory?Asynchronous writes allow overlapping of computation and disk update activity (write-behind).Do the write call for block n+1while transfer of block n is in progress.Distributed File Systemsü Naming– Location transparency/ independence• Caching– Consistency• Replication– Availability and updatesservernetworkserverclientclientclientCaching was “The Answer”• Avoid the disk for as many file operations as possible.• Cache acts as a filter for the requests seen by the disk− reads served best.• Delayed writebackwill avoid going to disk at all for temp files.MemoryFilecacheProc3Caching in Distributed F.S.• Location of cache on client - disk or memory• Update policy– write through– delayed writeback– write-on-close• Consistency– Client does validity check, contacting server– Server call-backsservernetworkserverclientclientclientFile Cache ConsistencyCaching is a key technique in distributed systems.The cache consistency problem: cached data may become staleif cached data is updated elsewhere in the network.Solutions:Timestamp invalidation (NFS).Timestamp each cache entry, and periodically query the server: “has this file changed since time t?”; invalidate cache if stale.Callback invalidation (AFS).Request notification (callback) from the server if the file changes; invalidate cache on callback.Leases (NQ-NFS) [Gray&Cheriton89]45Sun NFS Cache Consistency• Server is stateless• Requests are self-contained.• Blocks are transferred and cached in memory.• Timestamp of last known mod kept with cached file, compared with “true” timestamp at server on Open. (Good for an interval)• Updates delayed but flushed before Close ends.servernetworkserverclientclientclienttitjopenti== tj?write/closeFile HandlesQuestion: how does the client tell the server which file or directory the operation applies to?– Similarly, how does the server return the result of a lookup?• More generally, how to pass a pointer or an object reference as an argument/result of an RPC call?In NFS, the reference is a file handle or fhandle, a 32-byte token/ticket whose value is determined by the server.– Includes all information needed to identify the file/object on the server, and get a pointer to it quickly.volume ID inode# generation #4NFS: From Concept to Implementation– How do we make it fast?• Answer: caching, read-ahead, and write-behind.– How do we make it reliable? What if a message is dropped? What if the server crashes?• Answer: client retransmits request until it receives a response.– How do we preserve file system semantics in the presence of failures and/or sharing by multiple clients?• Answer: well, we don’t, at least not completely.– What about security and access control?NQ-NFS LeasesIn NQ-NFS, a client obtains a leaseon the file that permits the client’s desired read/write activity.“A lease is a ticket permitting an activity; the lease is valid until some expiration time.”– A read-caching lease allows the client to cache clean data.Guarantee: no other client is modifying the file.– A write-caching lease allows the client to buffer modified data for the file.Guarantee: no other client has the file cached.Leases may be revoked by the server if another client requests aconflicting operation (server sends eviction notice).Since leases expire, losing “state” of leases at server is OK.50Cache Consistency for the Web• Time-to-Live (TTL) fields - HTTP “expires” header• Client polling -HTTP “if-modified-since” request headers– polling frequency? possibly adaptive (e.g. based on age of object and assumed stability)networkWebserverproxycachelanclientclient51AFS Cache Consistency• Server keeps state of all clients holding copies (copy set)• Callbacks when cached data are about to become stale• Large units (whole files or 64K portions)• Updates propagated upon close• Cache on local disk & memoryservernetworkserverc0c1c2{c0, c1}closecallback• If client crashes, revalidation on recovery (lost callback possibility)5Coda – Using Caching to Handle Disconnected Access • Single location-transparent UNIX FS.• Scalability - coarse granularity (whole-file caching, volume management)• First class (server) replication and client caching (second class replication)• Optimistic replication & consistency maintenance.→ Designed for disconnected operation for mobile computing clientsExplicit First-class Replication• File name maps to set of replicas, one of which will be used to satisfy request– Goal: