Carnegie Mellon University

Carnegie Mellon UniversityCARNEGIE INSTITUTE OF TECHNOLOGYTHESISSUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTSFOR THE DEGREE OFTITLEDoctor of PhilosophyImproving the Dependability of Distributed Systemsthrough AIR Software UpgradesPRESENTED BYTudor A. Dumitra!ACCEPTED BY THE DEPARTMENT OFElectrical & Computer EngineeringADVISOR, MAJOR PROFESSORDEPARTMENT HEADDATEDATEAPPROVED BY THE COLLEGE COUNCILDEANDATE

Improving the Dependability of Distributed Systemsthrough AIR Software UpgradesSubmitted in partial fulfillment of the requirements forthe degree ofDoctor of PhilosophyinElectrical & Computer EngineeringTudor A. Dumitra!B.S., Computer Science, “Politehnica” University, Bucharest, RomaniaDiplôme d’Ingénieur, Ecole Polytechnique, Paris, FranceM.S., Electrical & Computer Engineering, Carnegie Mellon UniversityCarnegie Mellon UniversityPittsburgh, PADecember, 2010

To my parents and my teachers, who showed me the way. To my friends,who gave me a place to stand on. Pentru Tanti Lola.

AbstractTraditional fault-tolerance mechanisms concentrate almost entirely on responding to,avoiding, or tolerating unexpected faults or security violations. However, scheduled events,such as software upgrades, account for most of the system unavailability and often introducedata corruption or latent errors. Through two empirical studies, this dissertation identifiesthe leading causes of upgrade failure breaking hidden dependencies and of planned downtime complex data conversions in distributed enterprise systems. These findings represent the foundation of a new benchmark for software-upgrade dependability.This dissertation further introduces the AIR properties Atomicity, Isolation andRuntime-testing required for improving the dependability of distributed systems thatundergo major software upgrades. The AIR properties are realized in Imago, a system designed to reduce both planned and unplanned downtime by upgrading distributed systemsend-to-end. Imago builds upon the idea of isolating the production system from the upgrade operations, in order to avoid breaking hidden dependencies and to decouple the dataconversions from the normal system operation. Imago includes novel mechanisms, suchas providing a parallel universe for the new version, performing data conversions opportunistically, intercepting the live workload at the ingress and egress points or executing anatomic switchover to the new version, which allow it to deliver the AIR properties.Imago harnesses opportunities provided by the emerging cloud-computing technologies, by trading resource overhead (needed by the parallel universe) for an improved dependability of the software upgrades. This approach separates the functional aspects of theupgrade from the mechanisms for online upgrade, enabling an upgrade-as-a-service model.This dissertation also describes techniques for assessing the impact of software upgrades,in order to reason about the implications of relaxing the AIR guarantees.iv

This is for the one that I ate, 32 years ago.AcknowledgmentsSince I started to learn about Computer Science, I have been fascinated by our ability towrite computer programs that can protect themselves from various adverse conditions intheir environments. I equally enjoy building dependable systems firsthand and studyingempirically the behavior of systems large and small. This is the result of my interactionswith a few great mentors, who helped me discover the secrets of Computer Science andwho showed me the ways of scientific research.At age 13, I received a great gift from my uncle, Florin Covaciu. It was an HC-85 computer, a Romanian replica of the Sinclair ZX Spectrum (one of the world’s first personalcomputers). I learned to program on this machine, and, since then, I was not able to stayaway from programming for too long. This path took me to the Computer-Science HighSchool in Bucharest (Liceul de Informatică, now Colegiul Nat, ional Tudor Vianu), where teachers Mihai Budiu and Raluca Vasilescu opened my eyes to many computing concepts and totheir power to transform human society. These teachers shared their great knowledge andpassion for computing, and this inspired me to continue my studies in this field. I was nottoo surprised when I met Mihai and Raluca again, years later, in the graduate program atCarnegie Mellon University.Among my professors at the “Politehnica” University in Bucharest were Mircea Petrescu, who had supervised my father’s Honors thesis (diploma de licent, ă) twenty-five yearspreviously, Adrian Petrescu and Francisc Iacob, the creators of the HC-85, and NicolaeT, ăpus, , who supervised my own Honors thesis on Argo, a search engine with a distributedWeb crawler. Most of all, I am grateful to Zoea Racovit, ă for encouraging me to continuemy graduate studies and to apply to the Ph.D. program at Carnegie Mellon University.My education at the Ecole Polytechnique in Paris taught me to be responsible, confident, determined and to keep my commitments. I have to thank Jean-Marc Steyaert forguiding me through those years. Atom, a final-year project supervised by Sam Toueg, fov

ACKNOWLEDGMENTSvicused on implementing a practical group-communication system based on unreliable failure detectors (an exclusively theoretical technique, at the time) and seeded my curiosityabout distributed systems.When I arrived at Carnegie Mellon, Radu Mărculescu taught me the paramount importance of originality in all academic endeavors and the value of anticipating future technology trends for systems-oriented research. Our first paper together, which identified theneed for system-level fault tolerance in the emerging networks-on-chip (NoC) and reevaluated fundamental trade-offs made by classical networking protocols, remains my mostcited publication. Phil Koopman taught me everything I know about dependability, andhe always gave me good advice throughout my graduate studies.Many people contributed to the approach described in this dissertation. The membersof my thesis committee, Greg Ganger, Bruce Maggs and Asit Dan, encouraged me to pursuethe topic of online software upgrades and provided invaluable feedback in all the stages ofthis research. Dan Siewiorek taught me how to create a rigorous taxonomy. Jiaqi Tan andZhengheng Gho helped me design some of the core algorithms of Imago. At my request,Lorenzo Keller wrote a user manual for ConfErr, his fault-injection tool for mutating configuration files. A dinner-time discussion with Eli Tilevich turned into a publication aboutthe risks of software upgrades across multiple administrative domains. Douglas Schmidtshowed me how to present my research in an effective way. Jean-Charles Fabre has alwaysbeen a great mentor and a true friend. Je n’oublierai jamais que je dois mon premier emploi à tonsoutien sans réserve, Jean-Charles.Daniela Ros, u, Bich Le and Alan Downing my internship supervisors at IBM Research,VMware and Oracle, respectively provided me with a wealth of information about thepractical challenges of performing software upgrades. My approach also incorporates extensive feedback from the industry members of the Parallel Data Lab consortium. Duringmy dissertation research, I received financial support from the NSF CAREER Award CCR0238381, the DARPA PCES contract F33615-03-C-4110, as well as Carnegie Mellon’s CyLaband Parallel Data Lab.While not directly involved in this research, my collaborators Danny Dig and IulianNeamtiu helped me establish the series of workshops on Hot Topics in Software Upgrades(HotSWUp). The first two editions of the workshop provided a venue for insightful discussions about how upgrades are performed at various levels in the front-end of cloud com-

ACKNOWLEDGMENTSviiputing infrastructures, in EJB-based enterprise applications, in databases, in long-runningservers, in middleware frameworks or in satellites orbiting the Earth. Most importantly,HotSWUp emphasized that the challenge of upgrading distributed systems end-to-endcalls for an inter-disciplinary approach, combining ideas and techniques from several areasof Computer Science.Above all, I would like to thank my dissertation advisor, Prof. Priya Narasimhan, for allher guidance. She taught me the secrets of fault-tolerant middleware, and she showed mehow to enhance legacy applications with replication and recovery mechanisms by transparently intercepting the application’s system calls. She shared with me her great gift for writing and presenting technical material, she taught me the scientific method and she showedme how to ask the questions that matter. She passed down the teachings of Gottfried Wilhelm Leibniz, our academic ancestor, about how to turn an abundance of experimentaldata into rigorous scientific findings. She also passed down her aversion of adjectives andhyperbolae. She transformed a student into a researcher.Outside of Computer Science, my good friends too many to list here have always beena source of inspiration and vitality. My aunt, S, tefania Dumitras, , taught me about the practical things in life, and she also taught me French. My cousin, Ioana Căprar, has been closeas a sister. My parents, Dan Dumitras, and Monica Dumitras, , are my ultimate role models.Working at the Institute of Atomic Physics (where the first Romanian computer, CIFA, wasbuilt in 1955), their group of friends consisted of many other researchers, recognized internationally. I grew up among idealistic and passionate people, who were pushing the limitsof science and engineering, and this has influenced who I am today. I am grateful for all theintellectual gifts you gave me. I also thank Corina, with all my heart, for her support andencouragement during the final stages of my dissertation writing. Es, ti un pes, tis, or de aur.This dissertation is the fruit of your labor, as much as mine’s. For my part, this experience helped me to grow up, professionally, and to understand the difference between goodresearch and great research. I continue to marvel at the beauty of Computer Science and atall the things that are out there, for us to discover.

Contents12345Introduction11.1The dependability of software upgrades . . . . . . . . . . . . . . . . . . . . .31.2The next step forward . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .91.3AIR software upgrades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .91.4Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12Related Work172.1Causes of upgrade-induced downtime . . . . . . . . . . . . . . . . . . . . . .172.2Properties of software upgrades . . . . . . . . . . . . . . . . . . . . . . . . . .192.3Approaches for dependable upgrade . . . . . . . . . . . . . . . . . . . . . . .202.4Dependability benchmarking for software upgrades . . . . . . . . . . . . . .292.5Impact assessment for online upgrades . . . . . . . . . . . . . . . . . . . . .30Why Do Software Upgrades Fail?323.1Classification method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .353.2Upgrade-centric fault model . . . . . . . . . . . . . . . . . . . . . . . . . . . .403.3Tolerating upgrade faults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .473.4Summary of findings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .49Why Do Upgrades Need Planned Downtime?504.1Experimental method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .524.2Leading causes of planned downtime . . . . . . . . . . . . . . . . . . . . . .574.3Existing techniques for avoiding planned downtime . . . . . . . . . . . . . .614.4Summary of findings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .63The AIR Properties65viii