A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases ROBERT H. THOMAS Bolt Beranek and Newman, Inc. A “majority consensus” algorithm which represents a new solution to the update synchronization problem for multiple copy databases is presented. The algorithm embodies distributed control and can function effectively in the presence of communication and database site outages. The correctness of the algorithm is demonstrated and the cost of using it is analyzed. Several examples that illustrate aspects of the algorithm operation are included in the Appendix. Key Words and Phrases: distributed databases, distributed computation, distributed control, computer networks, update synchronization, concurrency control, clock synchronization, multiprocess systems CR Categories: 4.3, 4.32,4.33,4.39, 5.29 I. INTRODUCTION In a computer network environment it is often desirable to store copies of the same database at a number of different network sites. A number of advantages can result from maintaining such duplicate databases. Among these advantages are: increased data accessibility-the data may be accessed even when some of the sites where it is stored have failed, as long as at least one of the sites is operational; more responsive data access- database queries initiated at sites where the data are stored can be satisfied directly without incurring network transmission delays and those initiated from sites “near” the database sites can be satisfied with less delay than those “farther” from the database sites; load sharing-the computational load of responding to queries can be distributed among a number of database sites rather than centralized at a single site. These and other benefits of replicating data must be balanced against the additional cost and complexities introduced in doing so. There is, of course, the cost of the extra storage required for the redundant copies. This paper considers the problem of maintaining synchronization of multiple copy databases in the presence of update activity and presents a solution to that problem. Other problems (e.g. determining for a given application the number of copies to Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. This research was supported by the Advanced Research Projects Agency of the Department of Defense under Contract NOO14-75-0773. Author’s address: Bolt Beranek and Newman, Inc., 50 Moulton St., Cambridge, MA 02136. 0 1979 ACM 036%5915/79/06CO-0160 $00.75 ACM Transactions on Database Systems, Vol. 4, No. 2, June 1979, Pages 180-209.A Majority Consensus Approach to Concurrency Control 181 maintain and the sites at which to maintain them; selecting a database site or sites to satisfy a query request when it is initiated) are not considered in this paper. The inherent communication delay between sites that maintain copies of a database makes it impossible to ensure that all copies remain identical at all times when update requests are being processed. The principal goal of an update mechanism is to guarantee that updates get applied to the database copies in a way that preserves the mutual consistency of the collection of database copies as well as the internal consistency of each database copy. By mutual consistency we mean that all copies converge to the same state and would be identical should update activity cease. The notion of internal consistency is somewhat more difficult to define precisely. It concerns the preservation of invariant relations that exist among items within a database. As such, internal consistency is related to the interpretation or semantics of items in the database. Therefore, most of the responsibility for the internal consistency of a database must rest with the application processes which update it. The update mechanism should incorporate little, if any, knowledge of the database semantics. It should, however, operate in a manner that does not destroy internal data relationships if the application processes updating the database act in a way that preserves them. An example should serve to clarify the distinction between the two types of consistencies. Consider a simple database duplicated at sites A and B that includes data items x, y, and z, which all initially have the value 1 in both copies. Further assume that the relation x+y+z=3 must be preserved for the database. Consider two updates Rl and R2: Rl: x := -1, y := 3 R2: y := -1, .z := 3 each of which, based on the initial database state, preserves the relation. If Rl and R2 are both applied, regardless of the order of application, the internal consistency of the database (the relation x + y + z = 3) will be destroyed. Hence (at least) one of the requests must be rejected in order to preserve the internal consistency of the database. Stated somewhat differently, the update request that gets rejected must be refused because it is based on information made obsolete (the initial values of X, y, and z) by the request that gets accepted. Concurrency control mechanisms designed to maintain internal consistency for single copy databases typically use some sort of mutual exclusion scheme (lock or semaphore discipline) to guarantee that updates applied are based on current information. The mutual consistency of the database would be destroyed, while its internal consistency would be preserved, if update Rl was accepted at site A and update R2 was accepted at site B. Maintenance of mutual
View Full Document
Unlocking...