Disconnected Operation In A Distributed File System
Disconnected Operation in aDistributed File SystemJames Jay KistlerMay 1993CMU-CS-93-156School of Computer ScienceCarnegie Mellon UniversityPittsburgh, PA 15213Submitted in partial fulfillment of the requirementsfor the degree of Doctor of Philosophy.Thesis Committee:Mahadev Satyanarayanan, ChairEric CooperRichard RashidMichael Schroeder, Digital Systems Research CenterCopyright c 1993 James Jay KistlerThis research was supported in part by an IBM Graduate Fellowship, in part by the National Science Foundationunder Grant No. CCR-8657907, and in part by the Avionics Laboratory, Wright Research and Development Center,Aeronautical Systems Division (AFSC), U.S. Air Force, Wright-Patterson AFB, OH 45433-6543 under ContractF33615-90-C-1465, Arpa Order No. 7597.The views and conclusions contained in this document are those of the author and should not be interpreted asrepresenting the official policies, either expressed or implied, of the IBM Corporation or the U.S. Government.
Keywords: Disconnected operation, distributed file systems, high availability, mobile computers, caching, transparency, optimistic replication, hoarding, server emulation, reintegration,Coda.
For Chris
AbstractDisconnected operation refers to the ability of a distributed system client to operate despiteserver inaccessibility by emulating services locally. The capability to operate disconnected isalready valuable in many systems, and its importance is growing with two major trends: theincreasing scale of distributed systems, and the proliferation of powerful mobile computers.The former makes clients vulnerable to more frequent and less controllable system failures,and the latter introduces an important class of clients which are disconnected frequently andfor long durations—often as a matter of choice.This dissertation shows that it is practical to support disconnected operation for a fundamental system service: general purpose file management. It describes the architecture,implementation, and evaluation of disconnected file service in the Coda file system. The architecture is centered on the idea that the disconnected service agent should be one and thesame with the client cache manager. The Coda cache manager prepares for disconnection bypre-fetching and hoarding copies of critical files; while disconnected it logs all update activityand otherwise emulates server behavior; upon reconnection it reintegrates by sending its log tothe server for replay. This design achieves the goal of high data availability—users can accessmany of their files while disconnected, but it does not sacrifice the other positive properties ofcontemporary distributed file systems: scalability, performance, security, and transparency.The system has been seriously used by more than twenty people over the course of two years.Both stationary and mobile workstations have been employed as clients, and disconnectionshave ranged up to about ten days in length. Usage experience has been extremely positive.The hoarding strategy has sufficed to avoid most disconnected cache misses, and partitioneddata sharing has been rare enough to cause very few reintegration failures. Measurements andsimulation results indicate that disconnected operation in Coda should be equally transparentand successful at much larger scale.The main contributions of the thesis work and this dissertation are the following: a new,client-based approach to data availability that exploits existing system structure and has specialsignificance for mobile computers; an implementation of the approach of sufficient robustnessthat it has been put to real use; and analysis which sheds further light on the scope andapplicability of the approach.
AcknowledgmentsPerforming the thesis research and writing this dissertation turned out to be a larger undertakingthan I ever imagined. I could not have completed it without the care and support of manywonderful people, and I’m delighted to be able to acknowledge them here.First, I would like to thank my advisor, Satya. I couldn’t have had a better mentor. Healways made time to see me, no matter how busy his schedule. He was a constant sourceof good ideas and an infallible detector of bad ones. He challenged me when I needed tobe challenged and boosted my confidence when it needed to be boosted. He taught me theimportance of critical thinking and of validating one’s ideas through experimentation. Morethan anything, though, he has been a true and steady friend.The other members of my committee have been helpful throughout my career at CMU.Early on, Rick Rashid and Eric Cooper co-advised me and made me feel comfortable as I wasfinding my way. Later, they gave sound advice on my topic and on research in general. MikeSchroeder helped to expose and formulate the problem that my work addresses, and his carefulreading and critiquing of the dissertation made it a much better document. I thank all three ofthem for their efforts.I warmly thank my colleagues in the Coda group: Maria Ebling, Puneet Kumar, Qi Lu,Hank Mashburn, Lily Mummert, Brian Noble, Josh Raiff, Ellen Siegel, and David Steere. Theyare all very talented individuals and it has been a pleasure to work with them. Their help inthe design, implementation, and usage phases of my work was invaluable. Many of them alsoread the dissertation and gave useful feedback on it, and I thank them for that extra effort.Special thanks go to Puneet, who never failed to help with a problem or to put a happy face ona discouraging development. I have never known anyone as cheerful or as generous as he.I thank all of the people who used my software, who persevered through the rough stages ofdevelopment and who gave me their feedback on what was good and what was bad. My usersincluded all of the members of the Coda group, plus these other folks: Anurag Acharya, AdamBeguelin, Avrim Blum, David Eckhardt, Garth Gibson, Tammy Green, Tom Mitchell, HugoPatterson, Henry Rowley, Karen Shay, Peter Stout, Manuela Veloso, and Matt Zekauskus.A number of people on the CMU facilities staff helped me in setting up the Coda testbedenvironment, in collecting measurements, and in troubleshooting various problems. Special
thanks go to Mike Accetta, Paul Parker, Mark Puskar, and Dimitris Varotsis. Bob Baron, MikeJones, and Mary Thompson of the Mach group also assisted in these respects, and I thank themas well.A large and wonderful circle of friends has made my family’s stay in Pittsburgh very special.In addition to the people mentioned already, I’d like to thank Robert and Edie, Harry, Linda andPhil, Claire and Craig, Rhoda and Julian, Geli and Bernd, Dave and Gretchen, Dave and Ann,Deborah, Wendy and Craig, Brian and Debbie, and Wayne and the rest of the “brew crew” fortheir friendship and for all of the good times.My parents, Jim and Rita, instilled in me the desire to learn and the value of hard work.Without that grounding and their love I never could have come this far. Thank you, Mom andDad. My pal, Rigsby, took me on countless rejuvenating trips to the park and returned myaffection manyfold. Thanks go to you too, Rigs.My daughter, Hannah, was born part way through my thesis research, and she gave meadded incentive to finish. More importantly, she made me realize that, although I couldn’t writethe perfect dissertation, I couldn’t be such a bad guy because I’d helped to bring her into theworld. Thank you, Hannah. I will always be proud to be your father.Finally, my wife, Chris, deserves greater thanks than I can possibly give. For more than tenyears she has stayed with me, patiently allowing me to pursue my dream. She didn’t complainwhen I asked her to move from Berkeley to England to continue my studies. Unbelievably, shedidn’t object when I asked her to leave London for Pittsburgh so that I could enter graduateschool. In the course of almost seven years here she never once complained that I was takingtoo long. During the really grim periods of dissertation writing, when I doubted everythingI’d done and believed I could do no more, she comforted me and gave me the strength to keepgoing. Without her there for me I surely would have quit. I know that I can never adequatelyrepay her for these things, but I will spend the rest of my life trying. Thank you, dear. I loveyou.James Jay KistlerPittsburgh, PennsylvaniaMay 1993
Contents1Introduction1.1Distributed Computing1.2Distributed File Systems1.3Disconnected Clients :: : : : : : : : : : : : : : : : : : : : : : : : : : : : :2: : : : : : : : : : : : : : : : : : : : : : : : : : : : :41.3.1Impact of Large Scale1.3.2Impact of Mobile Computers: : : : : : : : : : : : : : : : : : : : : : : : :6: : : : : : : : : : : : : : : : : : : : : : : : : : : :7: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :81.5The Thesis: : : : : : : : : : : : : :9: : : : : : : : : : : : : : : : : : : : : : : :10: : : : : : : : : : : : : : : : : : : : : : : :101.5.1Requirements for Masking Disconnection1.5.2Establishing the ThesisOrganization of this Document :Design Rationale2.22.3AFS Heritage13: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :2.1.1Vice/Virtue2.1.2Client Caching2.1.3VolumesCoda Charter: : : : : : : : : : : : : : : : : : : : : : : : : : : : : :1313: : : : : : : : : : : : : : : : : : : : : : : : : : : :16: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :19: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :202.2.1High Availability in an AFS-Like Environment2.2.2First- versus Second-Class ReplicationPartitioned Replica Control2.3.16: : : : : : : : : : : : : : : : : : : : :Disconnected Operation2.11: : : : : : : : : : : : : : : : : : : : : : : : : : : :1.41.621: : : : : : : : : : : :20: : : : : : : : : : : : : : : :21: : : : : : : : : : : : : : : : : : : : : : : : : :22Transaction Model of Computationix: : : : : : : : : : : : : : : : : :24
CONTENTSx3System-Inferred Transactions2.3.3High Availability Transaction Specification2.3.4Optimistic Enforcement of Correctness2.3.5Replica Control Summary: : : : : : : : : : : : : : : : : : : : :34: : : : : : : : : : : : : : : :44: : : : : : : : : : : : : : : : : : : : : : :51533.1The View from Venus3.2Decoupling from Server Replication3.3Masking Disconnection3.5: : : : : : : : : : : : : : : : : : : : : : : : : : : : :4.254: : : : : : : : : : : : : : : : : : : : : :55: : : : : : : : : : : : : : : : : : : : : : : : : : : :56: : : : : : : : : : : : : : : : : : : : : : : :56: : : : : : : : : : : : : : : : : : : : : : : : : : : :56: : : : : : : : : : : : : : : : : : : : : : : : : : :57: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :57: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :573.3.1Cache Miss Avoidance :3.3.2Replica Control3.3.3Update Buffering3.3.4Persistence3.3.5SecurityComputation Correctness: : : : : : : : : : : : : : : : : : : : : : : : : : :3.4.1Intra-Partition Transaction Processing3.4.2Merging58: : : : : : : : : : : : : : : : :59: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :60Detailed Design and Implementation: : : : : : : : : : : : : : : : : : : : :Coda Internals4.130: : : : : : : : : : : : : :Architecture3.442.3.26263Client Organization: : : : : : : : : : : : : : : : : : : : : : : : : : : : : :63: : : : : : : : : : : : : : : : : : : : : : : : : : : :65: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :69: : : : : : : : : : : : : : : : : : : : : : : : : : : : : :72: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :724.1.1Cache Manager4.1.2MiniCacheServer Organization4.2.1File Server4.2.2Authentication Server: : : : : : : : : : : : : : : : : : : : : : : : :774.2.3Update Client/Server: : : : : : : : : : : : : : : : : : : : : : : : :78
CONTENTSxi579Hoarding5.1Idealized Cache Management: : : : : : : : : : : : : : : : : : : : : : : : :795.2Practical Cache Management: : : : : : : : : : : : : : : : : : : : : : : : :805.365.2.1Use of Explicit Reference Information :5.2.2Combining Implicit and Explicit Information5.2.3Use of Naming Information5.2.4Whole-Object Caching: : : : : : : : : : : : : : : :: : : : : : : : : : : : :82: : : : : : : : : : : : : : : : : : : : : :83: : : : : : : : : : : : : : : : : : : : : : : :84: : : : : : : : : : : : : : : : : : : : :85: : : : : : : : : : : : : : : : : : : : : : : : : : : :86Detailed Design and Implementation5.3.1Hoard Database5.3.2Object Priorities, Resource Allocation, and Naming Effects5.3.3Cache Equilibrium: : : : : :96: : : : : : : : : : : : : : : : : : : : : : : : : :99Server Emulation6.16.26.36.46.581119Disconnected Processing: : : : : : : : : : : : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : : : : :120: : : : : : : : : : : : : : : : : : : : : : : : : : : :121: : : : : : : : : : : : : : : : : : : : : : : : : : : : :1226.1.1User Transaction Processing6.1.2Hoard Walking :Transaction Logging119: : : : : : : : : : : : : : : : :122Cancellation Optimizations: : : : : : : : : : : : : : : : : : : : : :123Store-Record Optimization: : : : : : : : : : : : : : : : : : : : : :134: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :1366.2.1Log Organization and Record Format6.2.26.2.3Data Persistence: : : : : : : : : : : :137: : : : : : : : : : : : : : : : : : : : : :139: : : : : : : : : : : : : : : : : : : : : : : :148: : : : : : : : : : : : : : : : : : : : : : : : : : :149: : : : : : : : : : : : : : : : : : : : : : : : : : : : :1526.3.1Leveraging Off of the Local Unix File System6.3.2Using RVM for Meta-DataOther Masking Responsibilities6.4.1Access Checking6.4.2Fid Generation: : : : : : : : : : : : : : : : : : : : : : : : :152: : : : : : : : : : : : : : : : : : : : : : : : : : : : :153Mitigating Emulation Failures6.5.1Cache Misses6.5.2Resource Exhaustion: : : : : : : : : : : : : : : : : : : : : : : : :154
CONTENTSxii7Reintegration7.17.27.38157: : : : : : : : : : : : : : : : : : : : : : : : : :157: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :157Overview of the Algorithm7.1.1Prelude7.1.2Interlude: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :1607.1.3Postlude: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :163Non-Certification Issues: : : : : : : : : : : : : : : : : : : : : : : : : : : :7.2.1Volume-Log Ownership: : : : : : : : : : : : : : : : : : : : : : : :1647.2.2Transaction Validation: : : : : : : : : : : : : : : : : : : : : : : :1657.2.3Back-Fetching: : : : : : : : : : : : : : : : : : : : : : : : : : : :1657.2.4Atomicity of Reintegration7.2.5ClosuresCertification: : : : : : : : : : : : : : : : : : : : : :167: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :168: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :1697.3.1Version Certification7.3.2: : : : : : : : : : : : : : : : : : : : : : : : :170Value Certification: : : : : : : : : : : : : : : : : : : : : : : : : :1717.3.3Hybrid Certification: : : : : : : : : : : : : : : : : : : : : : : : : :1727.3.4Other Certification Issues7.3.5Summary: : : : : : : : : : : : : : : : : : : : : : :178: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :182Evaluation187: : : : : : : : : : : : : : :187: : : : : : : : : : : : : : : : : : : : : : : : : : : : :190: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :1908.1Implementation Status and Testbed Environment8.2Qualitative Evaluation8.31648.2.1Hoarding :8.2.2Server Emulation8.2.3Reintegration8.2.4General ObservationsQuantitative Evaluation: : : : : : : : : : : : : : : : : : : : : : : : : : :197: : : : : : : : : : : : : : : : : : : : : : : : : : : : :199: : : : : : : : : : : : : : : : : : : : : : : : :202: : : : : : : : : : : : : : : : : : : : : : : : : : : :2048.3.1Client Storage Requirements8.3.2Task Latency8.3.3Reintegration Latency8.3.4Cross-Client Write-Sharing: : : : : : : : : : : : : : : : : : : : :204: : : : : : : : : : : : : : : : : : : : : : : : : : : : :212: : : : : : : : : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : : : : : :215221
CONTENTSxiii9227Related Work9.19.2Systems: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :9.1.1FACE9.1.2AFS and Cedar9.1.3Tait and Duchamp9.1.4FicusMechanisms: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : : : : : : : : : : : :227229: : : : : : : : : : : : : : : : : : : : : : : : : : :229: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :231: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :2339.2.1Replica Control9.2.2Pre-Fetching and Hoarding9.2.3Log Optimizations9.2.4Recovery in Physical File Systems: : : : : : : : : : : : : : : : : : : : : : : : : : : :233: : : : : : : : : : : : : : : : : : : : : :234: : : : : : : : : : : : : : : : : : : : : : : : : : :236: : : : : : : : : : : : : : : : : :10 Conclusions236239: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :239: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :24110.1 Contributions10.2 Future Work22710.3 Final Remarks: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :243
xivCONTENTS
List of Figures1.1Effect of Caching on Service Structure: : : : : : : : : : : : : : : : : : : :42.1Vice and Virtue: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :142.2File System View at a Virtue Workstation2.3Integration of Server Replication and Disconnected Operation2.4A Non-1UE Execution Resulting from Partitioned Read/Write Conflict2.5Partitioned Transaction Example where 1SR-ness is Data-Dependent2.6: : : : : : : : : : : : : : : : : : :: : : : : : : :1523: : : :26: : : : :27A 1VSR Partitioned History with Read/Write Conflicts: : : : : : : : : : : :282.7Multi-Item Queries Violating One-Copy Serializability: : : : : : : : : : : :292.8Coda Data Item Description: : : : : : : : : : : : : : : : : : : : : : : : : :362.9Composition of the 1VSR’ History Class: : : : : : : : : : : : : : : : : : :2.10 A Non-1VSR’ History without Write/Write Conflicts42: : : : : : : : : : : : :44: : : : : : : : : : : : : : : : : : : : : : : : : :543.1Venus States and Transitions4.1Organization of a Coda Client4.2Typical Organization of Coda Servers5.1Format of a Venus File System Object (fsobj)5.2Format of a Hoard Database Entry5.3Sample HDB Entry Expansion5.4Sample Meta-Expansion5.5Name-Context States and Transitions5.6Reference Priority Recomputation5.7Status Walk: : : : : : : : : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : : : : : : : :6473: : : : : : : : : : : : : : : : :86: : : : : : : : : : : : : : : : : : : : : : :87: : : : : : : : : : : : : : : : : : : : : : : : :90: : : : : : : : : : : : : : : : : : : : : : : : : : : :92: : : : : : : : : : : : : : : : : : : : :105: : : : : : : : : : : : : : : : : : : : : : :115: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :115xv
LIST OF FIGURESxvi5.8CheckExpansion Routine Invoked During Status Walk5.9MetaExpand Routine Invoked During Status Walk5.10 Data Walk: : : : : : : : : : : :116: : : : : : : : : : : : : :117: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :1181236.1Format of a link Log Record6.2A 1SR History whose Log is Reintegrateable only after Optimization6.3Organization of Venus’ Address Space :7.1Stages of Reintegration, Major Sub-Tasks, and RPC Traffic7.2Atomic Sub-Tasks of Reintegration7.3A History that is Value but not Version Certifiable7.4A History that would Fail Version Certification due to Version Granularity7.5A History that would Fail Certification if Counter Operations were Certified7.6A History that is Partially Reintegrateable7.7Canonical Twin Transaction Example7.8Set CR: The Coda Reintegrateable Histories7.9Histories Illustrating the Availability Contribution of each Reintegration Feature 185: : : : : : : : : : : : : : : : : : : : : : : : :: : : : :125: : : : : : : : : : : : : : : : : : : :143: : : : : : : : : :158: : : : : : : : : : : : : : : : : : : : : :168: : : : : : : : : : : : : : :: :171172:178: : : : : : : : : : : :
Disconnected operation refers to the ability of a distributed system client to operate despite server inaccessibility by emulating services locally. The capability to operate disconnected is already valuable in many systems,
percent of disconnected young men and 43 percent of disconnected young women. Wald and Martinez further conclude that the South has more disconnected young adults than the Northeast and West combined, with nearly 61 percent of the nation’s disconnected African-American males living in the r
Disconnected Operation in the Coda File System JAMES J. KISTLER and M. SATYANARAYANAN Carnegie Mellon University Disconnected operation is amode of operation that enables client to continue accessing critical data during temporary failures of a shared data repository.
Nov 20, 2020 · C-10. Disconnected Impervious Surface . Design Objective Disconnected Impervious Surface (DIS) is the practice of directing stormwater runoff from built-upon areas to properly sized, sloped and vegetated pervious surfaces. Both roofs and paved areas can be disconnected with slightly di
Considerations for a disconnected device security policy This section will describe some of the high level considerations and tactics that can be used when defining a disconnected device security policy. The first thing that should be considered is how updates impact security when delivering them to disconnected devices.
Distributed Database Design Distributed Directory/Catalogue Mgmt Distributed Query Processing and Optimization Distributed Transaction Mgmt -Distributed Concurreny Control -Distributed Deadlock Mgmt -Distributed Recovery Mgmt influences query processing directory management distributed DB design reliability (log) concurrency control (lock)
―disconnected‖ families in reference to being disconnected from the labor market and public assistance programs. Given the potential for hardship for these families with children without earnings or means-tested cash benefits, policy makers
what needs to be done to re-engage disconnected students? Engaging students is a constant motivational c onsideration; re-engaging disconnected students is a major motivational problem. Prior to sc hools closing, students w ho were disengaged from instruction were a constant worr
transactions: (i) the exchange of the APX share for EPEX spot shares, which were then contributed by the Issuer to HGRT; (ii) the sale of 6.2% stake in HGRT to RTE and (iii) the sale of 1% to APG. The final result is that the Issuer has a participation in HGRT of 19%. For information regarding transactions (i) and (ii) please refer to the press release dated 28 August 2015 (in the note 4 pp .
