NASA-IVV-96-011 NASMWVU Software IV & V Facility WVU-SRL-96-01 I +,?_!U-SCS-TR-96-20 Software Research Laboratory CERC-TR-TM-96-01 i Technical Report Series J J Design and _.-m.p.._._e,-.___,_unof Repncated Oba,..,.. er b+,Sv.,dJ,+Jrig.oka _ .:- + .. i""_¸ mmmmmmmmm_ .National .Aeronautics and Space Administration /l_Lllw West Virginia University T According to the terms of Cooperative Agreement #NCCW-0040, the following approval is granted for distribution of this technical report outside the NASA/WVU Software Research Laboratory (54'o_K-_abol_sh .... bate John R. Callahan Date Man.r, Software Engineering WVU Principal Investigator Design and Implementation of Replicated Object Layer THESIS Submitted to the Eberly CoSlege of Arts and Sciences of West Virginia University in Partial Fulfillment of the Requirements for The Degree of Master of Science by Sudhir Koka Morgantown West Virginia May1996 ...... /, ¸.i.¸i¸_ .!_ i_._¸? i?,__ H Table Of Contents Table of Contents L_ of Tables iv L_ of Figures v Ac_owledgments vi Abstract vii 1 Introduction 1 1.1 Preview of Chapters 3 2 Related Work 4 2.1 IP Multicasting 4 2.2 Group Communication Concepts 5 _!ii:ii_: 2.3 Reliable Multicast Protocol (RMP) 7 2.3.1 RMP Entities 7 2.3.2 Interaction Model 8 2.3.3 Message Delivery and Fault Tolerance Features 2.4 Replicated Data 10 2.5 Replication Approaches I0 2.5.1 Primary - Backup Replication 10 2.5.2 Active Replication 11 2.6 Distributed Transactions 11 2.6.1 Two Phase Locking I2 2..6.2 Atomic Commit Protocol 13 2.6.2.1 Two Phase Commit Protocol 13 2.6.2.2 Quorum based Three Phase Commit 15 3 Design of ROL 17 3.1 Overview of ROL 17 3.2 _ Guarantees and Features 21 3.2.1 RMP Majority 22 3.2.2 ROLO option 22 3.3 RMP Coromut Protocol 23 3.3.1 Data Structures for RMP Co_t Protocol 25 3.3.2 Consistency of RMPCommit Protocol 27 3.3.3 Performance of RMPCo_t Protocol 28 3.4 ROL State S_ifications 30 3.4.1 Normal Operation of ROL 32 3.4.2 Reformation Extension of ROL 37 4 Implementation of Replica_ Object Layer 42 ........ ......... : _ i:•:i.....: :i:ii!ii!:i:,:::iI TableOfContents 4.1 ROL Class Structure 43 4.1.1 Type Registration 43 4.1.1.1 Type Class 43 4.1.1.2 Field Class 44 4.1.2 Dismbuted Transactions 44 4.1.2.1 Lock Class 44 4.1.2.2 Update Class 45 4.1.2.3 Commo_g and Log Classes 45 4.1.2.4 Transaction Class 45 4.1.3 Application Progran_-ning Interface 46 i_ili_i_ii_ 4.1.3.1 Object Cl_s 46 4.1.3.2 Objectlx_l Class 46 4.1.3.3 Chent Class 47 4.1.3.4 ROLEvent Class 47 4.2 An Example" A Simple Replicated Database Application 48 5 Ve_cation of ROL 52 5.1 SPIN Tool 52 5.2 SPIN Model for ROL 53 6 Conclusions and Furore Work 56 6.! Conclusions 56 6.2 Future Work 57 BibHo_phy 58 APPENDIX The RepHcat_ Object Layer Application Programming Interface 60 iii _t ofTables List of Tables TABLE 1 Performance of RMP Commit Protocol without pipelining 29 < TABLE 2 Performance of RMP Commit Protocol with pipelining 29 TABLE 3 Description of Events 31 TABLE 4 Token Site State 32 TABLE 5 Not Token Site State 34 • !i TABLE 6 Not in Group State 35 TABLE 7 Joining Group 36 TABLE 8 Leaving Group 37 TABLE 9 All Normal Operation States 38 TABLE 11 Reform State 38 TABLE 12 Synch Commfts State 40 iv L_t of Figures List of Figures Figure 1State Diagram for Two Phase Commit Protocol 14 Figure 2 State Diagram of Three Phase Commit Protocol 16 Fibre 3 RMP Architecture 17 Fi_e 4 Replicated Object Pool 18 Figure 5 Active replication using totally ordered messages 19 i Figure 6 ROL Server procedure 50 Figure 7 ROL Client Procedure 51 Figure 8 SPLN model for ROL 54 H i AcknowLutgments Acknowledgments I would _e to thank my advisor Dr. Jack Calla_hart for directing my research and helping me throughout my work here. I would _ like to thank Dr. James D. Mooney and Dr. V. Jagann_an for agreeing to be on my Examining Committee. An immeasurable amount of appreciation and gratitude go m Brian Whetten of USC Ber- keley and Todd Montogomery for providing enormous expense, knowledge and support throughout this work. I would like to thank people in NASA/WVU Research Lab and Con- _i!ii_ !i! i!ii_i current Engineering Research Center for their support and cooperation. Lastly, but most importantly, I would like to thank my parents and brother for unquestion- able su_rt, love and encouragement. Wi_out them this would not have been possible. vi Abstract Abstract One of the widely used techniques for construction of fault tolerant applications is the rep- lication of resources so that if one copy fails sufficient copies may still remain operational to allow the application to continue to function. This thesis involves tlx design and imple- mentation of an object orien_d framework for replicating data on multiple sites and across different platforms. Oar approach, called the Replicated Object Layer (ROL) provides a mechanism for consistent replication of data over dynamic networks. ROL uses the Reliable Multicast Protocol (RAMP) as a communication protocol that pro- vides for reliable delivery, serialization and fault tolerance. Besides providing type regis- tration, this layer facilitates distributed atomic transactions on replicated data. A novel al- gorithm called the RMP Commit Protocol, which commi_ transactio_ efficiently in reli- able multicast environment is presented. ROL provides recovery proc_es to ensure that site and communication failures donot corrupt persistent data, and m_e the system fault tolerant to network p_tio_. ROL will facilitate building distributed fault tolerant appli- cations by performing the Nardensome details of replica consistency owrations, and mak- ing it completely transparent to the application.Replicated databases are a major class of applications which coNd be built on top of ROL. vii ...... , i::¸ : _:,: , : ,_.... _.... : _ Introduction Introduction C_hapter 1 There has been a significant increase in the use of distributed systems over the last few years due to increasing availability of cheaper and faster computers, and new networkAn, g capabilities like multicasting. Reliability and availability of loosely-coupled distributed systems is a major requirement for distributed fault tolerant applications. One of the _- ods of making a distributed application tolerant to site failures and communication link fail- ures is replication of resources, but a replica consistency protocol is required to main_ the consistency between the replicated data at different sites. Distributed fault tolerant plications need an approach that provides a mechanism for consistent replication of over dyn_c ne_orks. , Replicated Object Layer (ROL) is one such approach, that provides an object-ofie.n_ framework for replicating data at multiple sites and across different platforms. ROL We- vides type registration fac_ty to give smmmre to replicated data. Sun's External Data R_ resentation [Sun87] is used to provide ship the data across different platforms. ROL vides support for perfo_g distributed atomic transactions on replicated data. A novel aI- gorithm called the RMP Commit Protocol, wNch commits transactions efficiently in reliable multicast environment is presented_ ROL provides recovery procedures to ensm,'e that site and communication failures _not corrupt persistent data, and make the system .... • _i¸•