Copyright by Conrad Tze Kong Chang, 2002 ADAPTIVE MULTI-GRANULARITY LOCKING PROTOCOL IN OBJECT-ORIENTED DATABASES BY CONRAD TZE KONG CHANG B.S., Illinois State University, 1990 M.S., Illinois State University, 1992 THESIS Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Computer Science in the Graduate College of the University of Illinois at Urbana-Champaign, 2002 Urbana, Illinois RED-BORDERED FORM ADAPTIVE MULTI-GRANULARITY LOCKING PROTOCOL IN OBJECT- ORIENTED DATABASES Conrad Tze Kong Chang Department of Computer Science University of Illinois at Urbana-Champaign Geneva G. Belford, Advisor Abstract Object-oriented databases can be very useful for applications containing complex data models that are not well served by conventional databases. Although much research has been done on developing concurrency control protocols for conventional databases like relational databases over the last 30 years in the concurrency control area, many of these protocols are not designed to be used in object-oriented database originally. Consequently, many opportunities presented in the rich data model of object-oriented databases are not fully utilized in the concurrency control protocols. My research presents a concurrency control protocol that will adaptively scale to the requirements of different transactions by utilizing different granularity units dynamically during each transaction. The concurrency control model proposed does not require any consistency relaxation. It uses the well-known serializability for guaranteeing consistency within the database. Concurrency control is critical as it plays a significant role in determining the performance of multi-user database systems. In this study, a self-adapting multiple granularity locking protocol is developed to improve the performance throughout and increase the degree of concurrency in object-oriented databases. This is accomplished by having a concurrency control protocol having the ability to undergo modifications in the number of locks required and the lockable granularity units according to changing transaction requirements without human input. However, it still conforms to the well-understood concept of consistency. Hence, the protocol is adaptive to the requirements of transactions. Two enhancements are proposed in this protocol. First, multiple logical granularity units are chosen with the knowledge of the data model. The protocol can freely choose the appropriate units for concurrency control. Second, escalation and de-escalation techniques are used to change the granularity units dynamically during the execution of a transaction. This is particularly important when the transaction is long lived, as is frequently the case in object-oriented databases. In this study, an adaptive multi-granularity protocol is developed and presented along with a series of simulation. iii ACKNOWLEDGEMENTS This project would not have been possible without the support of many people. Many thanks to my adviser, Geneva Belford, who read my numerous revisions and helped making some sense of the confusion. Also thanks to my committee members, Dr. Bruce Schatz, Dr. Marianne Winslett, and Dr. Duncan Lawrie, who offered guidance and support. Finally, thanks to my wife, parents, family members and friends who endured this long process with me, always offering support and love. iv TABLE OF CONTENTS Chapter 1 Introduction ............................................................................................................................................1 1.1 Dissertation Outline............................................................................................................2 Chapter 2 Motivating Examples...............................................................................................................................4 2.1 Software Development Environment .................................................................................5 Chapter 3 Background and Related Work..............................................................................................................9 3.1 Object-Oriented Database.................................................................................................10 3.2 Object-Oriented Database Definitions..............................................................................11 3.3 Concurrency Control in Traditional Databases ................................................................12 3.4 Concurrency Control in Object-Oriented Databases ........................................................16 3.5 Lock Escalation and De-escalation...................................................................................20 Chapter 4 System Model.........................................................................................................................................23 4.1 Data Model.......................................................................................................................23 4.2 Transaction Model............................................................................................................25 4.3 Basic Access Patterns .......................................................................................................26 4.4 Concurrency Control Model.............................................................................................27 Chapter 5 Adaptive Multi-Granularity Locking Protocol...................................................................................30 5.1 Lockable Granularity Units ..............................................................................................30 5.1.1 Class Inheritance Dimension............................................................................................34 5.1.2 Composite Object Dimension ...........................................................................................34 5.1.3 Class Instance Dimension ................................................................................................36 5.2 Soft Lock and Firm Lock..................................................................................................37 5.3 Explicit and Implicit Lock................................................................................................37 5.4 Lock Modes......................................................................................................................38 v 5.4.1 Instance Locks ..................................................................................................................39 5.4.2 Class Locks.......................................................................................................................39 5.4.3 Composite Object Hierarchy Locks..................................................................................40 5.4.4 Class Inheritance Hierarchy Locks ..................................................................................41 5.4.5 Class Definition Locks......................................................................................................42 5.5 Lock Compatibility Matrix...............................................................................................44 5.6 Rules for Requesting Locks..............................................................................................45 5.6.1 Class Locking Protocol ....................................................................................................46 5.6.1.1 Locking Classes...............................................................................................................................46 5.6.1.2 Locking Class Hierarchies...............................................................................................................47 5.6.1.3 Locking Class Definitions ...............................................................................................................48 5.6.2 Instance Locking Protocol................................................................................................49 5.6.2.1 Locking Instances ............................................................................................................................49 5.6.2.2 Locking Composite Objects.............................................................................................................49 5.7 Lock Granularity Graph....................................................................................................51 5.7.1 Formal Definition.............................................................................................................52 5.8 Equivalence Proof: Proposed Lock Modes to Basic Lock Modes....................................56 5.8.1 Basic Two-Mode Protocol................................................................................................56 5.8.2 Proof of Correctness of the Proposed Protocol................................................................56 5.9 Lock Escalation and De-escalation...................................................................................60 5.9.1 Lock Conversions .............................................................................................................61 5.9.1.1 Lock Mode Restriction ....................................................................................................................61 5.9.1.2 Lock Coverage Restriction ..............................................................................................................63 5.9.2 Lock Escalation and De-escalation Definitions ...............................................................64 5.9.3 Triggers for Escalation and De-escalation ......................................................................66 5.9.4 Optimistic Protocols for Requesting Locks ......................................................................66 5.9.4.1 Locking Instances ............................................................................................................................67 5.9.4.2 Locking Composite Objects.............................................................................................................67 5.9.4.3 Locking Classes...............................................................................................................................68 vi 5.9.4.4 Locking Class Hierarchies...............................................................................................................68 5.9.4.5 Locking Class definitions ................................................................................................................69 5.9.5 Examples ..........................................................................................................................69 Chapter 6 Simulation Overview .............................................................................................................................75 6.1 Simulation Model .............................................................................................................75 6.1.1 User Model .......................................................................................................................75 6.1.2 Database System Model ...................................................................................................76 6.1.3 Transaction Model............................................................................................................78 6.1.4 Summary of Simulation Parameters .................................................................................82 6.2 Criteria of Performance Evaluation..................................................................................83 6.2.1 Locking-related Metrics: ..................................................................................................83 6.2.2 Conflict-related Metrics: ..................................................................................................83 6.3 Simulation of the Concurrency Control Protocols............................................................84 6.3.1 Simulation Environment ...................................................................................................84 6.3.1.1 Programming Tool Kit.....................................................................................................................84 6.3.1.2 Smalltalk Classes.............................................................................................................................84 6.3.1.3 Sample Smalltalk Code....................................................................................................................87 Chapter 7 Experiments, Results and Analysis ....................................................................................................100 7.1 Locking Protocols...........................................................................................................100 7.1.1 Instance Granularity Locking.........................................................................................100 7.1.2 Class Granularity Locking .............................................................................................101 7.1.3 Multi-Granularity Locking .............................................................................................101 7.1.4 Adaptive Multi-Granularity Locking ..............................................................................102 7.2 Values of Simulation Parameters....................................................................................102 7.3 Experiments....................................................................................................................103 7.3.1 Description of Simulation Results ..................................................................................103 7.3.2 T1a: Object Access, Short Time, Small Workload..........................................................105 7.3.2.1 Description ....................................................................................................................................105 7.3.2.2 Result.............................................................................................................................................106 vii 7.3.3 T1b: Object Access, Short Time, Large Workload .........................................................107 7.3.3.1 Description ....................................................................................................................................108 7.3.3.2 Result.............................................................................................................................................108 7.3.4 T1c: Object Access, Long Time, Small Workload ..........................................................110 7.3.4.1 Description ....................................................................................................................................110 7.3.4.2 Result.............................................................................................................................................111 7.3.5 T1d: Object Access, Long Time, Large Workload..........................................................112 7.3.5.1 Description ....................................................................................................................................112 7.3.5.2 Result.............................................................................................................................................113 7.3.6 T2a: Class Access, Short Time, Small Workload............................................................115 7.3.6.1 Description ....................................................................................................................................115 7.3.6.2 Result.............................................................................................................................................116 7.3.7 T2b: Class Access, Short Time, Large Workload ...........................................................117 7.3.7.1 Description ....................................................................................................................................118 7.3.7.2 Result.............................................................................................................................................118 7.3.8 T2c: Class Access, Long Time, Small Workload ............................................................119 7.3.8.1 Description ....................................................................................................................................119 7.3.8.2 Result.............................................................................................................................................120 7.3.9 T2d: Class Access, Long Time, Large Workload............................................................121 7.3.9.1 Description ....................................................................................................................................122 7.3.9.2 Result.............................................................................................................................................122 7.3.10 T3a: Hierarchy Access, Short Time, Small Workload ....................................................124 7.3.10.1 Description ....................................................................................................................................124 7.3.10.2 Result.............................................................................................................................................125 7.3.11 T3b: Hierarchy Access, Short Time, Large Workload....................................................126 7.3.11.1 Description ....................................................................................................................................127 7.3.11.2 Result.............................................................................................................................................127 7.3.12 T3c: Hierarchy Access, Long Time, Small Workload.....................................................128 7.3.12.1 Description ....................................................................................................................................128 7.3.12.2 Result.............................................................................................................................................129 viii 7.3.13 T3d: Hierarchy Access, Long Time, Large Workload ....................................................130 7.3.13.1 Description ....................................................................................................................................130 7.3.13.2 Result.............................................................................................................................................131 7.3.14 T4a: Mixed Access, Short Time, Small Workload ..........................................................133 7.3.14.1 Description ....................................................................................................................................133 7.3.14.2 Result.............................................................................................................................................134 7.3.15 T4b: Mixed Access, Short Time, Large Workload ..........................................................136 7.3.15.1 Description ....................................................................................................................................136 7.3.15.2 Result.............................................................................................................................................137 7.3.16 T4c: Mixed Access, Long Time, Small Workload ...........................................................138 7.3.16.1 Description ....................................................................................................................................139 7.3.16.2 Result.............................................................................................................................................139 7.3.17 T4d: Mixed Access, Long Time, Large Workload ..........................................................140 7.3.17.1 Description ....................................................................................................................................140 7.3.17.2 Result.............................................................................................................................................141 7.4 Experiment Summary.....................................................................................................142 Chapter 8 Conclusion and Future Work.............................................................................................................144 8.1 Conclusion......................................................................................................................144 8.2 Future Work ...................................................................................................................147 References ........................................................................................................................................149 Vita ........................................................................................................................................152 ix LIST OF FIGURES FIGURE 2-1: ORGANIZATION OF AN EXAMPLE PROJECT..................................................................................................5 FIGURE 2-2: DIFFERENT GRANULARITY UNITS. ..............................................................................................................6 FIGURE 2-3: OPTIMAL SOLUTION FOR JOHN AND CONNIE. .............................................................................................7 FIGURE 5-1: LOCK HIERARCHY OF RESOURCES IN TRADITIONAL DATABASES ..............................................................30 FIGURE 5-2: EXAMPLE OF AN OBJECT-ORIENTED DATABASE........................................................................................32 FIGURE 5-3: LOCK HIERARCHY OF RESOURCES IN OBJECT-ORIENTED DATABASES.......................................................33 FIGURE 5-4: EXAMPLE OF A COMPOSITE OBJECT..........................................................................................................35 FIGURE 5-5: EXPLICIT AND IMPLICIT LOCKS ................................................................................................................37 FIGURE 5-6: LOCK GRANULARITY GRAPH ...................................................................................................................51 FIGURE 5-7: EXAMPLES OF NODES IN LG GRAPH........................................................................................................52 FIGURE 5-8: SAMPLE DATABASE..................................................................................................................................53 FIGURE 5-9: LG GRAPH OF THE SAMPLE DATABASE ....................................................................................................55 FIGURE 5-10: EXAMPLE: OBJECT LOCKING WITH ONE TRANSACTION...........................................................................70 FIGURE 5-11: EXAMPLE: OBJECT LOCKING WITH TWO TRANSACTIONS ........................................................................71 FIGURE 5-12: EXAMPLE: OBJECT LOCKING WITH TWO TRANSACTIONS CONTINUES.....................................................72 FIGURE 5-13: EXAMPLE: OBJECT LOCKING WITH FOUR TRANSACTIONS .......................................................................73 FIGURE 5-14: EXAMPLE: OBJECT LOCKING WITH FIVE TRANSACTIONS ........................................................................74 FIGURE 6-1: SIMULATION MODEL................................................................................................................................78 FIGURE 6-2: PHYSICAL RESOURCE USAGE MODEL......................................................................................................81 FIGURE 7-1: EXPERIMENT T1A, PART 1......................................................................................................................106 FIGURE 7-2: EXPERIMENT T1A, PART 2......................................................................................................................107 FIGURE 7-3: EXPERIMENT T1B, PART 1......................................................................................................................108 FIGURE 7-4: EXPERIMENT T1B, PART 2......................................................................................................................109 x FIGURE 7-5: EXPERIMENT T1C, PART 1......................................................................................................................111 FIGURE 7-6: EXPERIMENT T1C, PART 2......................................................................................................................112 FIGURE 7-7: EXPERIMENT T1D, PART 1......................................................................................................................113 FIGURE 7-8: EXPERIMENT T1D, PART 2......................................................................................................................114 FIGURE 7-9: EXPERIMENT T2A, PART 1......................................................................................................................116 FIGURE 7-10: EXPERIMENT T2A, PART 2....................................................................................................................117 FIGURE 7-11: EXPERIMENT T2B, PART 1....................................................................................................................118 FIGURE 7-12: EXPERIMENT T2B, PART 2....................................................................................................................119 FIGURE 7-13: EXPERIMENT T2C, PART 1....................................................................................................................120 FIGURE 7-14: EXPERIMENT T2C, PART 2....................................................................................................................121 FIGURE 7-15: EXPERIMENT T2D, PART 1....................................................................................................................122 FIGURE 7-16: EXPERIMENT T2D, PART 2....................................................................................................................123 FIGURE 7-17: EXPERIMENT T3A, PART 1....................................................................................................................125 FIGURE 7-18: EXPERIMENT T3A, PART 2....................................................................................................................126 FIGURE 7-19: EXPERIMENT T3B, PART 1....................................................................................................................127 FIGURE 7-20: EXPERIMENT T3B, PART 2....................................................................................................................128 FIGURE 7-21: EXPERIMENT T3C, PART 1....................................................................................................................129 FIGURE 7-22: EXPERIMENT T3C, PART 2....................................................................................................................130 FIGURE 7-23: EXPERIMENT T3D, PART 1....................................................................................................................131 FIGURE 7-24: EXPERIMENT T3D, PART 2....................................................................................................................132 FIGURE 7-25: EXPERIMENT T4A, PART 1....................................................................................................................134 FIGURE 7-26: EXPERIMENT T4A, PART 2....................................................................................................................135 FIGURE 7-27: EXPERIMENT T4B, PART 1....................................................................................................................137 FIGURE 7-28: EXPERIMENT T4B, PART 2....................................................................................................................138 FIGURE 7-29: EXPERIMENT T4C, PART 1....................................................................................................................139 FIGURE 7-30: EXPERIMENT T4C, PART 2....................................................................................................................140 FIGURE 7-31: EXPERIMENT T4D, PART 1....................................................................................................................141 FIGURE 7-32: EXPERIMENT T4D, PART 2....................................................................................................................142 xi LIST OF TABLES TABLE 4-1: SCHEMA CHANGES IN ORION SYSTEM .....................................................................................................27 TABLE 5-1: LOCK GRANULAR UNITS EXPLICITLY AND IMPLICITLY ACQUIRED...........................................................44 TABLE 5-2: LOCK COMPATIBILITY MATRIX.................................................................................................................45 TABLE 5-3: BASIC TWO-MODE LOCK COMPATIBILITY MATRIX ..................................................................................56 TABLE 6-1: SUMMARY OF DATABASE PARAMETERS....................................................................................................77 TABLE 6-2: SUMMARY OF SIMULATION PARAMETERS.................................................................................................82 TABLE 6-3: SMALLTALK CLASSES ...............................................................................................................................85 TABLE 7-1: DATABASE GENERATION PARAMETERS ..................................................................................................102 TABLE 7-2: SIMULATION PARAMETERS THAT ARE CONSTANT ...................................................................................103 TABLE 7-3: SIMULATION CHART LEGEND DESCRIPTION............................................................................................104 TABLE 7-4: T1A SIMULATION PARAMETERS..............................................................................................................105 TABLE 7-5: T1B SIMULATION PARAMETERS ..............................................................................................................107 TABLE 7-6: T1C SIMULATION PARAMETERS ..............................................................................................................110 TABLE 7-7: T1D SIMULATION PARAMETERS..............................................................................................................112 TABLE 7-8: T2A SIMULATION PARAMETERS..............................................................................................................115 TABLE 7-9: T2B SIMULATION PARAMETERS ..............................................................................................................117 TABLE 7-10: T2C SIMULATION PARAMETERS ............................................................................................................119 TABLE 7-11: T2D SIMULATION PARAMETERS............................................................................................................121 TABLE 7-12: T3A SIMULATION PARAMETERS............................................................................................................124 TABLE 7-13: T3B SIMULATION PARAMETERS ............................................................................................................126 TABLE 7-14: T3C SIMULATION PARAMETERS ............................................................................................................128 TABLE 7-15: T3D SIMULATION PARAMETERS............................................................................................................130 TABLE 7-16: T4A SIMULATION PARAMETERS............................................................................................................133 xii TABLE 7-17: T4B SIMULATION PARAMETERS ............................................................................................................136 TABLE 7-18: T4C SIMULATION PARAMETERS ............................................................................................................138 TABLE 7-19: T4D SIMULATION PARAMETERS............................................................................................................140 TABLE 7-20: BEST AND WORST OF EACH EXPERIMENT .............................................................................................143 xiii Chapter 1 Introduction It has been proposed that object-oriented databases are well suited for certain applications like CAD/CAM, complex scientific applications, complex business applications [1-3]. The data modeling power of object-oriented databases allows them to deal with these applications more efficiently while other types of database system might fail. Accordingly, object-oriented databases are starting to fill a void in fields where conventional database technology is deficient. Nevertheless, many of these applications pose very difficult requirements even to object- oriented database systems. They are usually long-duration and perform extensive computations on a large number of interrelated objects. They usually load all these objects into memory and then do the necessary computation on them. All these present a significant performance challenge to an object-oriented database system. Past researchers have looked mainly at the single-user performance issues but have not studied carefully the concurrency control issues in a multiple users and applications environment. However, as the use of object-oriented databases becomes more common, good performance in an environment with multiple users and/or multiple applications will become more significant. After all, performance is one of the most important factors for users in deciding to use an object-oriented database instead of a file-based system. The object-oriented database paradigm presents some unique challenges in concurrency control when multiple applications use the same object-oriented database. The problems of concurrency control in conventional databases, such as the lost update problem and the uncommitted dependency problem, remain in object-oriented database. Furthermore, due to the complexity of the object-oriented data model, the problems become more complex. Many concurrency control techniques have been studied for many years in the relational database field [4]. Some of these techniques were used in many object- oriented databases. However, many of these techniques have not been researched and modified to match the performance requirements of an object-oriented database [5, 6]. Depending on the implementation of the 1 concurrency control algorithms, there could be substantial performance differences among object-oriented database systems. Concurrency control is critical mainly because it is one of the deciding factors of performance in any database system. Hardware advances have led to several-fold improvements in performance over the years and it is likely that this trend will continue in the near future. Concurrency control algorithms will have to be much more efficient just to keep pace with hardware. Traditionally object-oriented databases are used in application areas where data contention is relatively small. However, if object-oriented databases were to be more widely used. The application areas must include areas where data contention is frequent, such as business data processing. Increasingly, data contention has become the single most critical factor of database performance in these areas. Furthermore, the concurrency control issue is not only important in dealing with performance issues, but also has a direct impact on the scalability of an object-oriented database. In addition to the common techniques that are used in relational databases, some granularity schemes proposed by researchers help reduce some of the problems, but all of them have various weaknesses. 1.1 Dissertation Outline The remainder of this thesis is organized as follows. Chapter 2 further explains the deficiencies of current concurrency control protocols in object-oriented databases. Several scenarios using an example in a software development environment are used to illustrate the problems encountered in database access conflicts. The goal is to provide the motivations for the development of the proposed concurrency control mechanisms in object-oriented databases. A literature review of related work in the field of database concurrency-control protocols is presented in chapter 3. Chapter 4 details the data model that is used as a reference for the target database system of the proposed protocol. A formal transaction and concurrency control model is also discussed. All these models serve as the basic reference points on which the proposed protocol can be used. All these models are intended to be very close to the models that are used by most commercial and research object-oriented database systems. 2 In chapter 5, the design and correctness of the protocol is discussed. The major components such as the granularity units, lock request protocols, lock compatibility matrix, lock escalation, and de-escalation are described in detail. Chapter 6 presents a detailed simulation of the proposed protocol in different environments. The simulation methodology and models are described in detail and the results of the experimental studies using different parameters are presented in chapter 7. Chapter 8 gives a summary of this thesis and the conclusions following from it. It summaries the contributions and presents some suggestions and directions for future research in this area. 3 Chapter 2 Motivating Examples The purpose of this chapter is to provide the motivation for the development of the proposed concurrency control mechanisms in object-oriented databases. In the following sections, examples are used to illustrate the type of problems these proposed concurrency control mechanisms are designed for and to show that they are not served well by the current set of concurrency control mechanisms. Many large, multi-user, advanced computer applications, such as software development, computer-aided design (CAD) and manufacturing (CAM), network management, financial forecast, medical informatics, information retrieval, knowledge discovery, office automation, and scientific engineering applications involve computation on large amount of data with rich semantic data models. In information retrieval, for instance, one of the basic problems is to get a concise set of results for a given query on a large set of information. Because of the low quality of results of precise term matching, researchers are turning towards more complex techniques like statistical indexing such as concept space computation [7] to augment traditional precise term matching. However, many of these indexing techniques have large data storage needs and involve computation of a large number of objects with complex data models. When these applications are coupled with database management systems, they present requirements to the database management systems that cannot be easily met. Because of these requirements, many of these applications elect to use object-oriented databases. Many of the current object-oriented databases employ concurrency-control techniques that are borrowed from traditional database systems. The requirements of these applications on the concurrency control mechanisms are quite different from the traditional database applications. Some of the essential characteristics of these applications are that they could involve a large number of objects and thus require significant overhead for the locks used for each object. Operations on these objects could also take a long time and may be interactive in nature and 4 thus the transactions involved are usually long-lived. Although such transactions occur in traditional applications as well, they are usually an order of magnitude longer in advanced applications. For instance, compiling code in a software development environment or building indexes on a knowledge base could take minutes or even hours. Holding locks for long periods is particularly problematic for object-oriented databases that use primarily navigation access methods. If the wrong granularity unit is locked, severe performance degradation can result. An example would be that locking a root object could significantly reduce the number of concurrent transactions, since it completely prevents any other transaction from accessing any part of the database. Finally, all these applications demand fast performance. 2.1 Software Development Environment We motivate the need for the development of an enhanced concurrency control mechanism by a simple example from the software development domain. A large amount of data is maintained in a typical software development environment. Data include programmers' source code, generated object code, intermediate compilation file, documentation, test suites, and others. Traditionally, all these different objects would be manipulated manually by programmers and project managers. System configuration tools like Make, RCS, CVS are Project Root X Y Z W C5 C2 C4 C3 C12 C1 C8 C6 C7 C9 C10 C11 Figure 2-1: Organization of an example project. used for management of these objects. Although these tools provide basic support for configuration management, they lack the flexibility that some people might desire, since they all depend on the underlying file system as the 5 shared storage space. Advanced functions like backup and restore, concurrent access control, error recovery are not used. For these reasons, many people started to use an object-oriented database for the management of these objects. The following example illustrates how a simple locking scheme could be undesirable for this kind of applications. Assume that two programmers, John and Connie, are working on the same software project. The software project consists of four major modules X, Y, Z, and W. Each of these modules also consists of several procedures and libraries, as illustrated in Figure 2-1. At the beginning, John is the only person working on the project. He wants to insert a change to procedures C1 through C8. The DBMS would go out and obtain a lock on each of these procedures. Eight locks are being obtained and they are kept until the transaction commits. Note that the overhead in this case is larger than needed. Since John is the only person working on the project, it would be more desirable if one lock can be used for locking Project Root Project Root X Y Z W X Y Z W C5 C2 C4 C3 C12 C1 C8 C6 C7 C9 C10C11 C5 C2 C4 C3 C12 C1 C8 C6 C7 C9 C10C11 Locks Figure 2-2: Different granularity units. the whole project. Although this would result in more objects being locked than what is needed by John, it would not create any concurrent access conflicts since no one else is using the database. However, the overhead is significantly reduced from eight locks to only one lock. This saving would be even more dramatic if John needs to work on hundreds of procedures instead of eight as stated in this example. Since locking the whole project would be best for John in this case, let's assume that the DBMS uses this approach. With this lock granted for the whole project, John proceeds to make the changes and test the modified code. 6 During the time when John is working on the code, Connie decides that she wants to make some changes to the procedure C11. She cannot do that although she is not concerned about procedures that John modified and would like to make changes to C11 only. Since John is locking the whole project, Connie would have to wait until John's transaction is completed before she can start working on her code. This situation, however, would not have happened if locks were granted at the lowest level. The best case for Connie would be to have John obtaining a lock for each procedure he modified and therefore allowing Connie to obtain a lock for C11. In the above example, if the traditional concurrency control scheme of two-phase locking were used, it would only result in a good solution for one of the transactions depending on which granularity unit was chosen by the DBMS. If the granularity unit were a project, it would have been best for John. If it were a procedure, it would have been best for Connie. The problem is somewhat remedied but not eliminated if multiple granularity units are Project Root X Y Z W C5 C2 C4 C3 C12 C1 C8 C6 C7 C9 C10 C11 John Connie Figure 2-3: Optimal solution for John and Connie. permitted. The problem still exists because the granularity units to be locked are determined at the beginning of a transaction and cannot be changed during the process. A wrong decision made at the start of a transaction by any transaction would result in the same sub-optimal solution. Let's see another example to see how this might be the case. Again, assume that John and Connie are working on the same software project, as illustrated in Figure 2-1. In this scenario, the DBMS can lock several different granularity units at the same time. The granularity units are 7 project, module, and procedure. Similar to the previous scenario, John wants to make another change to the same group of procedures C1 through C8. This time all these procedures are contained within modules X, Y, and Z. To save locking overhead, the DBMS locks modules X, Y, Z instead of procedure C1 through C8. This reduces the locking overhead from eight to three locks. The saving is not as great as last time. However, the number of objects that are locked unnecessarily is also reduced. In fact, the only object that is locked unnecessarily is C12 in module Y. Similar to the last scenario, Connie wants to make some changes to C11 during John's transaction. This time Connie can proceed because a lock can be obtained either for procedure C11 or for module W. On the other hand, if Connie wants to make changes to C12, there would be a problem. She would have to wait until John's transaction is finished before she can continue. The above scenario indicates that although the DBMS can lock multiple granularity locking units, unnecessary conflicts still exist. The optimal solution in this case, shown in Figure 2-3, would be for John's transaction to lock modules X and Z, and procedures C1 and C3. This would result in minimal locking overhead and maximum concurrency access. In general, it is impossible to pre-determine the optimal granularity units for locking by a given transaction T. This would require complete knowledge of objects being used by all transactions that started after T but before T is finished. In this scenario, the database system would not be able to come up with the optimal solution for John's transaction, since this would require knowing about what objects would be accessed by Connie in the future. What is needed to solve this problem is a flexible and dynamic concurrency control scheme that allows change of the granularity units to be locked during a transaction to accommodate requirements from other transactions. In this study, I will propose an adaptive multiple granularity-locking scheme that attempts to accomplish this objective. 8 Chapter 3 Background and Related Work "An object database management system is a database management system that integrates database capabilities with object-oriented programming language capabilities." ODMG2.0 "Concurrency control is the activity of coordinating the actions of processes that operate in parallel, access shared data, and therefore potentially interface with each other." Bernstein et al. [4] "A concurrency control mechanism allows multiple users to access and update the database so that overall correctness is maintained and performance is optimized." Olsen and Ram [6] This chapter presents a brief review of some of the basic concepts of object-oriented databases. A literature review of research on concurrency control issues in the field of relational databases and object-oriented databases is then discussed. Specifically, previous works on granularity locking and the idea of lock escalation and de-escalation are presented. Granularity locking, lock escalation and lock de-escalation have been used by some relational databases but are not well researched and seldom implemented in object-oriented databases with more complex data models. 9 3.1 Object-Oriented Database Researchers first developed object-oriented databases during the early 1980s when several shortcomings of conventional relational database systems [8-10] were becoming clear. Conventional database systems are not well suited for applications that require management of a complex data model, such as the complex nested data structures used in many CAD applications. They generally only support a limited set of atomic data types; general user-defined data types are not supported. This limitation makes them not suitable for many multimedia applications that require storage of image, audio and other objects. As object-oriented concepts flourished in the programming community, the impedance-mismatch problem between the conventional database language, such as SQL, and the application programming language became more significant. Slow performance of conventional database systems in various computation-intensive applications is also a problem area. The object-oriented database system was designed to overcome these deficiencies in conventional database systems, specifically relational databases. It is designed to have the ability to represent and manipulate arbitrarily complex objects of any size. An object-oriented database system also has a rich data model for complex data model requirements. It extends and incorporates the data model into the application programming model using the underlying application programming language, thereby reducing the impedance-mismatch problem. It also supports efficient storage and access methods of data objects used in the programming models. Unlike the relational database model, however, there is no strong underlying mathematical foundation or a well-defined and accepted set of concepts and tools. However, many have observed that some of the concepts in object-oriented databases are similar to the ones in semantic data modeling. Earlier object-oriented programming languages such as Smalltalk [11] introduced many basic concepts like classes and objects used in object-oriented databases. These concepts proved to be very useful as a programming model. Object-oriented database management systems, in many ways, can be seen as an attempt to combine these useful programming language concepts with concepts from the persistent database world. Various researchers have produced many research prototypes and commercial systems. These include ORION [2], O2 [12], GemStone, ObjectStore [13], Versant [14] and others. As the lead developer of one of the earliest commercial object-oriented database, Won Kim [2, 3, 15-17] has formally stated many basic concepts and theories in the field of object-oriented database. He defined an object- oriented database as "a database system which directly supports an object-oriented data model" [2]. His object- oriented data model consists of several concepts that are commonly used and understood by researchers nowadays. 10 It should be noted, however, that not all of these concepts are universally accepted and implemented in object- oriented database system. A list of definitions is in section 3.2. 3.2 Object-Oriented Database Definitions Object: Objects are simply real-world entities that are of some meaning. An object consists of a set of values for its attributes. These values can also be objects, thus forming relationships among objects. Each attribute can contain a single object or a set of objects. Object Identifiers: Each object is assigned a unique ID number. The ID number is theoretically never assigned to another object even if the original object is deleted from system [2, 3]. This identifier serves as the handle to the object and is a convenient way of locating a particular object. This is in many ways similar to the object pointer used in programming languages. Because of the extensive use of object identifiers for building relationships among objects, object-oriented databases tend to have a model that emphasizes direct navigational access using pointers and object identifiers. Nonetheless, there are also other methods of manipulating data in object-oriented databases, such as using declarative languages like Object SQL. Class: All objects that share the same set of attributes belong to the same class. A class is a logical grouping for a set of objects with the same defined set of attributes. An object belongs to a class and is an instance of that class. In addition to attributes being defined in a class, the behaviors of a class are also defined and are commonly referred to as methods. The concept directly captures the instance-of relationship between a class and its objects. No standard methodology exists for determining what classes should be modeled in a particular database. Typically, a database designer would have to use experience and heuristics to guide the design process. Class Inheritance: Inheritance corresponds to the semantic modeling concepts of generalization and specialization. A subclass is a specialized case of its superclass. A subclass inherits the methods and attributes of all of its superclasses. Together, the classes in a system form a hierarchy called a class hierarchy. A class usually inherits its attributes and methods from 11 one superclass. If this is the case, it is called single inheritance. If there may be more than one superclass, it is called multiple inheritance. Many object-oriented databases do not support multiple inheritance because of the added complexity. In a system that supports multiple inheritance, the classes form a rooted and connected directed acyclic graph (DAG). The class hierarchy directly captures the IS-A relationship between a class and its superclass. Encapsulation: It refers to the property that objects contain both methods and internal structure (attributes). There is no means to access an object's attributes except through the predefined methods. This is important for reusability, interoperability and modularization in many applications. Composite Object: A composite object is a set of objects that form a PART-OF relationship hierarchy. The component objects are existence dependent on container objects. If the container object were destroyed, its component objects would need to be deleted as well. Generally, it is desirable to be able to treat all the component objects of a composite object as a single unit for database operations. 3.3 Concurrency Control in Traditional Databases Conflicts among data accesses are avoidable when there are multiple agents accessing the data. Keeping the order and resolving the conflicts are the responsibility of concurrency control schemes. The field of concurrency control was first researched in the 1970s to ensure that consistency is maintained in a database when multiple transactions are updating simultaneously. A few basic approaches were proposed, and many variations of these approaches have been developed since then [4]. All of them use the concept of serializability for consistency guarantee. The basic theory behind this concept is that a schedule of transactions to execute is correct if the schedule is consistent. A schedule is consistent if the operations of the transactions within the schedule are executed in an order equivalent to a serial schedule. A serial schedule is one in which transactions are executed serially. A formal definition of serializability and further discussion is presented in section 4.4. These basic approaches can be classified into three categories in general. They are two-phase locking [18], optimistic protocols and timestamping. Two-phase locking is considered a pessimistic approach since it requires 12 locks to be obtained before data can be accessed. Timestamping and other optimistic protocols belong to the optimistic approach as data can be accessed before conflicts among operations are checked. The underlying assumption behind using an optimistic approach is that conflicts are infrequent. Therefore, obtaining locks for data could be a waste of resources since they may not conflict with any transactions. The assumption for using a pessimistic approach is the opposite. It assumes that conflicts appear frequently. Locks are the most common mechanism for maintaining consistency in database systems [8-10, 19-21]. Many protocols have been developed using locks. One commonly used protocol is called two-phase locking. A typical transaction using two-phase locking would obey the following rules [19]. "A transaction is defined as two-phase if all its LOCK actions precede all its UNLOCK actions. A two-phase transaction T has a growing phase, T[1], ..., T[j], during which it acquires locks, and a shrinking phase, T[j+1],...,T[n], during which it releases locks" Two-phase locking has two phases as its name implies. First, there is the growing phase where locks are accumulated. This is followed by the shrinking phase where locks are being released. This means that a lock release is never followed by a lock request. If this rule were violated at any time during the transaction, the transaction would have to abort. Because of these simple rules, a very desirable outcome is obtained in which global consistency is guaranteed among transactions. Optimistic locking is a variation of the field call methods [19, 22]. Field call is a concurrency control method that focuses on reducing the transactions' collision cross section. The collision cross section is defined as the time-space product of the amount of data the transaction locks and the lock duration. The basic idea of field call is very similar to predicate locks. Predicate locks are designed to lock a subset of the database instead of an individual object. The subset of the database is specified by a predicate, which is a condition that a record satisfies. For example, a predicate will select all records in Table E where the value of the field age equals to 20. Each field call consists of a predicate and a transform on a specific record. Either part can be omitted. A transform specifies the change in value to be applied to the record. A predicate specifies the condition in which the transform should be executed. A short duration shared mode lock is used to cover the test of the condition in the predicate against the content of the current record, and is released as soon as the test is done. If the predicate returns false, an error is returned. Otherwise, the transaction creates a REDO log record to be performed at commit time. After the creation of the log records, locks are released. The log record contains both the predicate and the transform. The 13 predicate is stored in the REDO log so that it can be used again at commit time to verify the predicate condition. During the commit phase, records that only appear in the predicates of the REDO log records are locked with read locks, since there is no need to change the value of the record. On the other hand, records that appear in the transforms of the REDO log records are locked with exclusive locks. The predicate of each record in the REDO log is then tested again during the commit phase. If the predicate is false, the transaction is rolled back with a predicate violation error. If the predicates are all still true, then each transform is applied and the locks are freed. In some applications, locking can be too constrictive to the level of concurrency that can be achieved. It can also add unnecessary overhead, especially when transactions do not overlap or conflicts among transactions are infrequent. Optimistic locking was invented after field calls by Kung and Robinson [23] to eliminate some of these problems. In optimistic locking, the predicate is {field = old-value} and the transform is {field = new-value}. In the paper by Kung and Papadimitriou [24], they use the optimistic locking scheme as their concurrency control method. They allow all transactions to proceed and then perform a validation phase for conflict resolution immediately prior to the commit phase. Any transaction that cannot be committed is aborted and restarted. In systems where transaction conflicts are rare, studies have shown that it performs quite well. However, optimistic locking starts to break down and performs quite poorly when conflicts between transactions are high. In many cases, its performance is worse than conventional two-phase locking. The timestamping technique was originally designed for distributed database systems. It is also used in many centralized database systems as a concurrency control mechanism [4]. One of the problems of locking mechanisms is the potential for deadlock. Deadlock happens when two or more transactions are waiting for each other's resources. Timestamping solves this problem by assigning each transaction a unique number, called a timestamp. The timestamp is chosen from a sequence of monotonically increasing numbers. All transactions are then processed in the order of the timestamp. This sequence can be any monotonic sequence of numbers, but is often a function of the time of day. Using timestamps, a concurrency control mechanism can totally order requests from transactions according to the transactions' timestamps. Three actions are possible when there are two conflicting transactions. First, the protocol could force a transaction T1 requesting to access a data item x that is being held by another transaction T2 to wait until T2 terminates. Second, it can also abort the transaction T1, and do a restart for that transaction if it cannot be granted access to the data item. Finally, transaction T1 can preempt transaction T2 14 with a more recent timestamp and get the data item. Timestamping can be considered as a special case of the optimistic locking scheme [19]. The protocols mentioned in the discussion so far operate on individual objects or data items only. In many cases, it is often useful to be able to access a set of objects or data items as a single unit. This allows fewer locks to be used and usually leads to improve performance. Gray et al. [25] presented a multiple granularity concurrency control protocol that aims to minimize the number of locks used while accessing sets of objects in a database. In Gray's model, data items are organized in a tree structure, where smaller data items are contained within larger ones. Each non-leaf item represents the data associated with all its descendants. As such, nodes closer to the top represent more data than the nodes at the bottom. The root of the tree represents the whole database. When a transaction locks nodes, descendants of these nodes are locked implicitly as well. Locks can be exclusive (X) or shared (S). An exclusive lock excludes any other transaction from accessing the node; a shared lock permits other transactions to read the same node concurrently but prevents any updating of the node. To grant a lock to a transaction on a particular node, the transaction manager needs to follow the path from the root to the node to find out if any other transaction has explicitly locked any of the ancestors of the node. This process is very inefficient in terms of time consumption. To make this process more efficient, Gray developed a third kind of lock mode called intention lock. It works as a lock for all ancestors of a node that is explicitly locked. All the ancestors of a node must be locked in intention mode before an explicit lock can be put on the node. Three additional lock modes were added. They are (1) Intention-Shared (IS) lock specifies that descendant nodes will be explicitly locked in shared mode; (2) intention- exclusive (IX) lock implies that explicit locking is being done at a lower level in exclusive mode; (3) shared and intention-exclusive (SIX) lock implies that the whole subtree rooted at the node is being locked in shared mode and that explicit locking will be done at a lower level with exclusive-mode locks. Gray also defined a compatibility matrix for resolving lock conflicts. The following multiple granularity protocol was developed based on the compatibility matrix: 1 A transaction Ti can lock a node in S or IS mode only if all ancestors of the node are locked in either IX or IS mode by Ti. 2 A transaction Ti can lock a node in X, SIX, or IX mode only if all the ancestors of the node are locked in either SIX or IX mode by Ti. 15 3 Locks should be released either at the end of the transaction (in any order) or in leaf-to-root order. In particular, if locks are not held to the end of the transaction, the transaction should not hold a lock on a node after releasing the locks on its ancestors. The multiple granularity protocol increases concurrency and decreases overhead. This is especially true when there is a combination of short transactions with a few accesses and long transactions that last for an extended period of time accessing a large number of objects. 3.4 Concurrency Control in Object-Oriented Databases Concurrency control problems associated with conventional databases still exist in object-oriented databases. The more complex object-oriented data model, however, does create new challenges and new opportunities that did not exist before. Hundreds of concurrency control algorithms exist in the traditional database field [4, 5]. However, very few of these address object-oriented databases and no comprehensive theory has been developed in the area of concurrency control for object-oriented databases. Lee and Liou [26] pointed out that there are three major types of access conflicts in object-oriented databases. There are instance-to-instance conflicts, instance-to-schema conflicts, and schema-to-schema conflicts. Many concurrency control algorithms used in object- oriented databases were adapted from existing algorithms in relational databases. Some were re-implementations of existing algorithms like two-phase locking and, timestamping described in the previous section. Others were modified and developed to better fit the need of object-oriented databases. These include semantic-based locking protocols, versioning [1-3] and some simple hierarchical locking schemes. Most of these hierarchical schemes are some variations of the multi-granularity locking scheme [25, 27] described earlier. Following is a brief summary of some of the research and developments in this field. One direction researchers took was the use of semantic-based locking protocols in object-oriented databases. This approach uses the semantics to ensure correct execution. Since object-oriented databases have richer semantics associated with them, the use of semantics for concurrency control could potentially increase concurrency among transactions. In general, semantic-based protocols can be classified into two classes depending on whether they depend on the semantics of transactions or the semantics of objects. Garcia-Molina [28] developed one of the earliest transactions-based concurrency control protocols for database systems. Gracia-Molina introduced the notion that some transactions must output only consistent data to the user, thus these transactions rely on the consistency of 16 the database being maintained. These transactions are called sensitive transactions. Although not all transactions are sensitive, transactions can produce inconsistent data in certain applications when the requirements do not demand consistent output. However, sensitive transactions are required to guarantee that the database will be maintained in a consistent state. A semantically consistent schedule is one that transforms the database from one semantically consistent state to another. It is found difficult to create a general concurrency control protocol that could recognize schedules that maintain semantic consistency. It is simply very difficult for the concurrency control protocol to determine a priori which schedules maintain semantic consistency. As such, the database system must run the schedules and check the resulting state of the database to see whether it satisfies the consistency requirements. To avoid rollback, the concurrency control protocols must be provided with information concerning about which transactions are compatible with each other. Two transactions are said to be compatible provided their operations can be interleaved at certain points without violating semantic consistency. This type of compatibility information has to be provided by the user. It requires the user to understand the details of applications and in most cases, this is not a feasible solution. Garcia-Molina presented a framework that explicitly defines the semantics of database operations generally. He defines the following four kinds of semantic information. First, he categorizes transactions into types depending on the nature of the operations in those transactions. Second, transactions are statically divided into atomic steps. These steps make up a transaction of that type. Third, a compatibility set is defined for each type of transaction. It specifies the allowable interleaving with respect to those steps of the same kind or other kinds of transactions. The compatibility set enables the protocol to maintain consistency over the state of the database. In Garcia-Molina's scheme, if transactions of type X are compatible with transactions of types Y and Z, any two transactions Ti of type Y and Tj of type Z can arbitrarily interleave their steps with a transaction Tk of type X. Hence, there is no distinction between interleaving with respect to Y and interleaving with respect to Z. Countersteps are then specified for what to do in case a step needs to be undone. These countersteps are used if rollback is necessary. Garcia-Molina defines an alternative concept to atomicity called semantic atomicity. A transaction is said to be semantically atomic if all its steps are executed or if any executed steps are eventually followed by their countersteps. All this information is used by a concurrency control protocol that uses two kinds of locks; local locks, which ensure the atomicity of transaction steps, and global locks, which guarantee that the interleaving between transactions does not violate semantic consistency. Thus depending on the compatibility sets of different types of 17 transactions, various levels of concurrency can be achieved. For instance, if the compatibility sets of all kinds of transaction are empty, the mechanism reverts to a traditional locking mechanism that enforces serializability. In the area of protocols based on object semantics, many researchers have focused on the use of the general notion of commutativity and the extension of it to abstract data types. Hadzilacos and Hadzilacos [29] introduced a transaction model for object databases following this direction. They simplify the nested transaction model [30] originally proposed by Moss [31] and apply it to transaction executions in object-oriented databases. The result is a nested two-phase locking protocol [29] that could be used in object-oriented databases. It is a generalization of the locking protocol for nested transactions proposed by Moss. In this protocol, locks are requested only for the leaves in the nested execution. When a transaction is finished, its parent inherits its locks. A lock is granted only if there are no other conflicting locks. Locks are discarded only when the top-level transaction terminates. This two-phase locking protocol is a generalization of the locking protocol for nested transactions. Muth et al. [32] develops another protocol based on commutativity. In this protocol, conflicts between lower-level operations or methods can be ignored due to the commutativity of the corresponding higher-level methods in the nested execution. When two lower-level operations conflict, if the ancestors of these operations commute, then locks are granted for these operations. One limitation of the protocol is that it cannot be used with object-oriented databases with shared objects. In addition, this protocol requires locks not only for the atomic operations but also for method executions. Therefore, the system designer has to derive a conflict or commutativity table not only for the atomic operations of each class but also for all the method executions of all the classes in the database. This results in significant burden for the application developers of the database system. Agrawal and El Abbadi [33] also develop a nonrestrictive concurrency control mechanism for object-oriented databases using nested two-phase locking with ordered sharing based partly on Moss's nested transaction model. Ordered sharing is similar to commutativity. For a given operation O1, the set of operations is divided into two groups ­ the set of operations that commute with O1, and the set of operations that do not commute with O1. If O1 commutes with some operation O2, then O1 and O2 are compatible and can share the same lock being granted. However, if O1 does not commute with O2, an extra step must be taken to ensure that the execution order is preserved. A set of commit rules is developed to ensure this. If a transaction Ti is granted a lock with an ordered shared relationship with respect to a lock held by Tj on an object, and Tj is a proper descendent of the parent of Ti, then Ti cannot commit unless Tj has committed or aborted. Like the nested transaction model in Moss, a transaction cannot commit or abort until all its children are terminated, and locks are 18 inherited by its parent when it commits. Although Agrawal and Abbadi increase concurrency among methods by adopting ordered sharing, they do not exploit semantics of methods. Because of this, the protocol can deal with objects that contain any user-defined methods. Conflicting operations may share locks on the same objects, if the order between the operations is preserved. This protocol is extended for synchronizing nested executions of transactions on objects. Another approach to concurrency control in object-oriented databases is versioning [1-3, 17]. Versioning allows many different versions of an object to be created and to exist without enforcing consistency requirements at creation time. Reconciling the value of an object to be consistent with the values in the public database must be done before the value can be made public. Versioning is more suitable in long-lived transactions but is not well suited for standard, short-lived database transactions due to the amount of time the reconciliation takes. Multi-granularity locking was originally developed by Gray [19] to reduce locking overhead in relational databases. Through organizing the database in the form of a hierarchy and obtaining a lock at a higher level, transactions implicitly lock entities at the lower levels. In a relational database, for instance, the hierarchy would be formed by database, relation and row with database as the root and row as the leaf. By applying the same principle to object-oriented databases, the designers of earlier object-oriented database systems such as ORION and O2 developed similar protocols [1-3, 12, 34] by replacing the database hierarchy with simple class and object hierarchy. These researchers chose to use strict two phase locking to implement their protocols. However, there are several drawbacks to their approaches. First, the rich semantics contained in object-oriented databases are not used. For example, the inheritance relationship between parent class and child class is not considered. Second, the degree of concurrency is low on locking a composite object. If one transaction updates any component objects of a composite object, the locking model locks the composite object in its entirety. Therefore, a large number of objects may be locked even if the transaction only accesses a small subset of them. No other transactions can directly access any component object of the composite object via the component classes. Third, the model does not support class schema locks. The model always locks class schemas and instances at the same time. This reduces the degree of concurrency in many situations when the class schema can be read independently of the instances for different requests. Concurrency can be increased if separate lock modes for the accessing class schema are used. Taniguchi et al. [35] examine three multi-granularity locking options for concurrency control in object- oriented databases. These options are non-class-hierarchy locking, class granularity locking, and class-hierarchy 19 locking protocols. The proposed locking protocols obey the two-phase locking rules to preserve serializability. In the class granularity locking protocol, two types of objects can be locked. The first type is the instance object. Each instance object requires a different lock. The second type of object that can be locked is the class object. Locking a class means implicit locks on all instances of the class. In the class-hierarchy protocol, in addition to instance objects and class objects, a class-hierarchy can also be a locking unit. Setting locks on a class means that there are implicit locks on all subclasses of that class. In non-class-hierarchy locking, locks must be set on every object to be accessed. In general, class granularity locking is appropriate for accessing classes near to the leaf level of a deep class hierarchy. Class-hierarchy locking is more suitable for accessing classes near the root of a class hierarchy. Non- class-hierarchy locking is better if a few objects are accessed. Their experiments show that the class granularity locking protocol may be the better approach among the three in most cases. However, this assumes that the option chosen cannot be changed within a transaction. Therefore, although the objects are dynamically locked, the type of object that can be locked is statically assigned before the beginning of a transaction. Olsen and Ram [6] propose a general framework for addressing concurrency control issues in object- oriented databases. They also develop a lock-based concurrency control mechanism named O2C2 that was built based on this framework. In the framework, they give a list of rules that are crucial to an object-oriented database concurrency control mechanism. These rules address issues like lock request and release order and lock modes related to one or more of the dimensions. The dimensions proposed are: (1) Hierarchical Dimension; (2) Data Type Dimension; (3) Composite or Complex Objects Dimension; (4) Transaction Type Dimension. Their objective was to provide a theoretical framework for issues involved in designing a concurrency control protocol. Hence, some of the issues are not fully investigated. 3.5 Lock Escalation and De-escalation Lock escalation is defined by Gray [19] as the process of trading fine-granularity locks for coarse ones. Lock de-escalation is the reverse process of trading coarse-granularity locks for fine ones. Lock escalations are used in many relational database systems. The locked objects are usually physical units such as physical pages. In 20 general, the database system keeps track of the number of locks at a specific level and then escalates when a threshold is passed. The escalation process happens along the hierarchy and goes up to the root in one direction only. Lehman et al. [36] proposed a two-level resource hierarchy for locking in relational databases. In their design, the granularity units consist of only relations and tuples. The protocol keeps track of the number of transactions waiting for locks on the relational level. This count is used later for lock de-escalations. Lock de-escalation happens when a threshold is exceeded, transactions holding locks at the relational level are given the needed tuple level locks instead. The threshold is exceeded when the transaction holding the relational locks significantly inhibits the progress of other transactions, and is primarily determined by the number of transactions waiting on the lock and the amount of time they have been waiting. On the other hand, lock escalations happen as soon as the tuple-level locks are no longer required. Since lock escalation or lock de-escalation can only happen in one direction within a single transaction in all these protocols, the impact of having multiple escalation and de-escalation within a single transaction has not been studied. In his work on the relational database system Rdb/VMS, Joshi [37] found that the number of locks requested by the transaction is independent of the actual number of conflicts that occur among concurrent transactions in a typical database management system. Hence, even if the concurrent transactions access non- intersecting sets of data, they will continue to incur the same overhead of locking for each transaction. The concurrency control manager of the DBMS is unable to detect the degree of conflict and adjust the number of locks requested by the transaction, without sacrificing correctness and the degree of concurrency in the system. To solve this problem, Joshi developed a dynamic locking strategy that allowed a higher level of concurrency than Lehman's method [36]. The locking algorithm was designed to respond to the contention level among concurrent users by adjusting the number of lock requests required by transactions. The protocol can detect situations of low contention and automatically reduce the number of lock requests per transaction. If contention increases, the number of locks automatically increases to the appropriate level required to maintain the correctness and consistency of the data. This is accomplished by organizing records within a table into an adjustable lock granularity tree. This tree organizes the records into varying levels of granularity starting with the root of the tree representing the entire table and the leaves being individual records. The number of levels in the granularity tree and the groupings of records in various levels are determined by users. In the simplest case, the tree has two levels. The root is the entire table and the leaf is each record. However, the tree can contain more levels. For example, the first level is the entire table. The second level 21 contains two nodes, each of which represents half of the table. The third level contains the records belonging to each of these half tables. The lock de-escalation protocol works by acquiring locks at the highest ancestor of the record in the tree. If it succeeds in getting the lock, all descendants are then implicitly locked. It should be noted that the actual records being accessed have to be recorded. If a conflicting lock request comes in from any other transaction, then the locks would be de-escalated into the locks of the actual records needed. The cost of remembering implicitly locked records is proportional to the number of records accessed. Many transactions in object-oriented databases are long-lived and tend to access a large number of objects; the use of lock escalation and de-escalation protocols could yield significant benefits. There are also more possible types of resources that can be used for locking. For example, each attribute or method of an object could also be treated as a granularity unit. In turn, this increases the routes for possible lock escalation and de-escalation significantly. Nevertheless, issues involving lock escalation and de-escalation in object-oriented databases have generally been neglected. 22 Chapter 4 System Model 4.1 Data Model A brief description of the data model for the proposed concurrency control protocol is presented in this section. The data model described here is very close to the basic model used in current object-oriented database definitions by researchers. There is no feature in this model that would be considered as uncommon in object- oriented databases. The goal is to define a model that would be basic enough that the concurrency control protocol being built on it would be applicable to any object-oriented database. The basic storage unit in the database is an object. An object represents any real-world entity. The properties of this entity are represented by one or more attributes of the object. The object also has one or more methods that represent the behavior of the entity. All objects of the same type share the same set of attributes and methods. This group of objects is named a class. The class is not only a set of objects, also named instances, but also contains information about its instances. There could be many classes in the model representing various types of objects. All these classes may relate to each other in a parent-child relationship and form a hierarchy or a directed acyclic graph (DAG), also called a class hierarchy. All attributes and methods defined for a class are inherited by all its subclasses recursively. This hierarchical structure provides additional information and allows new opportunities for improvement to concurrency control algorithms. Objects can also relate to one another in two different types of relationships, association and composition. Objects can associate with one another in many ways and association can represent different semantic meanings. Association is represented simply by one object containing a reference to another object. Composition is, on the other hand, very specific and has only one meaning. A composite object is an 23 object that contains a set of component objects. The existence of the component objects depends on the existence of the composite object as a whole. This relationship can also be defined recursively on each of the component objects. Like the class hierarchy, each composite object may also form a composite object hierarchy. Unlike the class hierarchy, each composite object hierarchy is a tree structure with a single root node. In addition, unlike the class hierarchy where there is usually single hierarchy for each database, there could be many composite object hierarchies in a single database with different root nodes. In this data model, it is assumed that composite objects are explicitly supported. Component objects can only be parts of a single composite object and the composition relationships can be explicitly declared in the model. It is therefore assumed that the closure of a composite object is well defined, bounded, and can be detected by the concurrency control mechanism. All other links not declared as composite links are considered associations. Associations, however, are not used for the consideration of granularity units. Using this description of the data model, the proposed concurrency control mechanism can control three basic types of resources, instance objects, class definition objects, and class objects. The class definition objects are the information repositories of its instances like interfaces, attributes, and methods. Class objects, however, are the containers for instances objects. There are other more advanced structures that the concurrency control mechanism can control. Examples include the class hierarchy and the composite object hierarchy. These structures are related to the resources described above as well as with each other. They are explained further in the following sections. It should be noted that the concurrency control mechanism is primarily concerned with determining what types of objects should be locked to facilitate transaction processing. Some of these objects controlled by the concurrency control mechanism correspond directly to objects that are defined in the data model. However, there could be other objects that may not be directly defined in the data model. For example, one would usually think of the class definition as part of the class object in an object-oriented data model. To the concurrency control mechanism, however, it would be more desirable to separate the class into a class object and a class definition object. This would allow increased concurrency, as some operations may need only to access the class definition but not the instances within the class. To make the distinction clear between objects included in the data model and objects controlled by the concurrency control mechanism, it will be more appropriate to consider these objects as resources controlled by the concurrency control mechanism. Some of the granularity units controlled by the concurrency control mechanism are similar to the resources managed by the concurrency control manager in relational databases. For instance, class 24 definition object in object databases is analogous to the relation schema in relation databases. Locking the class definition object prevents changes made to the structure and the properties of the data of a class, just like locking the relation schema prevents definition of the relation being changed. Class objects are comparable to relations. They both serve as containers for the underlying instances or tuples. Locking a class object locks all instances of that class, just like locking a relation locks all tuples of that relation. Locking an instance of a class corresponds to locking a tuple of a relation. 4.2 Transaction Model A transaction access data stored in a database by means of data access operations. Two types of data access operations exist, Read operation and Write operation. A Read operation simply returns a value associated with a datum, while a Write operation modifies the value of the datum. The transaction model assumes that a transaction T is well formed. Therefore, all data accesses are covered by locks. A transaction also consists of two phases, a reading phase and a writing phase. Together, the transaction consists of a set of Read operations and a set of Write operations. It is assumed that a transaction behaves in the following way: read the data, process it, and write the results into the database. I will use ri[x] and wi[x] to denote Read and Write operations on an object x in transaction Ti. A transaction Ti, is defined by Bernstein [4] as "a partial order with an ordering relation A. A node with no parent is a root; a node with no children is a leaf. A path is any sequence of two or more nodes , such that for each 1 Vehicles class hierarchy node Truck (A) class-instance dependency Car Truck Electric Car instances of Truck composite class node Electric Car Vehicles Truck Car Truck Car Electric Car (C) class hierarchy- composite object dependency Car Truck Electric Car object hierarchy node Electric Car (B) class hierarchy - subclass hierarchy dependency Figure 5-7: Examples of Nodes in LG Graph i < k, A. Node b is an ancestor of node c if b lies on some path from a root to node c. A LG Graph has a single root node. The root node represents the class inheritance tree rooted at the root class. In other words, it also represents the whole database since all instances are children of classes that can 52 eventually trace back to the root class as the super class. There are different types of nodes in the graph representing different lockable granular units. These are as follows: * Instance Node: a single instance of a class * Class Node: a single class * Object Hierarchy Node: a set of instances that forms a composite object hierarchy * Composite Class Node: a set of all classes of all instances that are parts of a composite object. * Class Hierarchy Node: a set of classes that forms a class hierarchy. This node also represents the class definitions of these classes. The set of arcs that exits in the LG graph is determined by the following rules: a) exists if p is a class node and c is an instance node where c represents an instance of p Object Car Engine Compact Truck Gas Electric (A) Class Hierarchy compact 1 gas2 gas1 (B) Composite Instance (C) Simple Instance Figure 5-8: Sample database 53 b) exists if p is a class hierarchy node and c is a class hierarchy node, where c is an immediate subtree of p in the class hierarchy tree. c) exists if p is a class hierarchy node and c is a class node, where c is the root class of p. d) exists if p is a class hierarchy node and c is a composite class node, where the set of classes in c is a subset of classes in p e) exists if p is a composite class node and c is a component hierarchy node where each instance in c belongs to a class in p f) exists if p is a object hierarchy node and c is a object hierarchy node where c is an immediate subtree of p in a composite object hierarchy. g) exists if p is a object hierarchy node and c is a instance node where c is the root object of p in the composite hierarchy. Each node in the LG graph represents a lockable granularity unit. In other words, each node can be hold with a lock as a resource. The arc between two nodes defines a parent-child, or a containment relationship. The child node is completely contained within a parent node. In another words, the granularity unit represented by the child node is completely contained within the granularity unit within the parent node. 54 object object engine engine car car compact, gas compact truck gas electric electric compact truck gas compact 1 gas2 comp gas1 act1 gas1 Class Hierarchy Node Object Hierarchy Node Composite Class Node Instance Node Class Node Figure 5-9: LG graph of the Sample database 55 To illustrate the LG graph more clearly, a sample database is shown in Figure 5-8. To make the illustration simpler, the database consists of only seven classes. These classes form a single class inheritance tree with the `object' class as the root class. In addition, there are three object instances in this database. `gas1' and `gas2' are object instances of the class `gas'. `compact1' is an object instance of the class `compact'. Finally, `compact1' and `gas1' also form a composite object instance. The corresponding LG graph is shown in Figure 5-9. 5.8 Equivalence Proof: Proposed Lock Modes to Basic Lock Modes 5.8.1 Basic Two-Mode Protocol The basic locking protocol locks each atomic resource with two lock modes, shared (S) and exclusive (X). The compatibility of these two locks can be determined by their semantics. A shared lock allows the resource to be S X S Y N X N N Table 5-3: Basic Two-Mode Lock Compatibility Matrix read but not modified. An exclusive lock allows the resource to be modified. An exclusive lock is incompatible with any other lock. A shared lock is only compatible with another shared lock, since no modification is done. The compatibility matrix is shown in Table 5-3. 5.8.2 Proof of Correctness of the Proposed Protocol We will now prove that the described lock protocol is compatible to the basic protocol, which uses only two modes: shared and exclusive locks, to lock only atomic resources or leaves of the resource tree. The leaves of the resource tree would be the object instances of an object-oriented database. In this proof, we will also add the null lock (NL) to the set of locks that are described in section 5.4. A null lock does not place any locking constraints on a 56 resource and is thus compatible with all other locks. The following proof is modeled on the proof Gray [25] used for proving correctness of his multi-granularity locking scheme. Let G = (N, A) be a finite directed graph where N is the set of nodes and A is the set of directed arcs representing relationships among these nodes. A node p is a parent of a node n, and n is a child of p if there is an arc from p to n. A node n is called a source if n has no parents. It is called a sink if it has no children. Let SN be the set of sinks of G; therefore SN contains the set of nodes that have no children. An ancestor of node n is any node (including n) in a path from a source to n. A node-slice NS of sink n is a collection of nodes such that each path from a source to n contains at least one of these nodes. Removing all elements from a node-slice NS of sink n will completely partition node n from the graph. We also assume that there is no non-null path leading from a node n to itself, therefore graph G has no cycle. Specifically, G represents the graph of lockable resources or the LG graph defined in section 5.7. Assume that we have the lock modes M = {NL, FS, FX, TS, TX, FSD, FXD, TSD, TXD, FSN, FXN, FSH, TXH, TSH, TXH, FSO, FXO, TSO, TXO} described in section 5.4 and the compatibility matrix C:M×M {Yes, No} described in Table 5-2. FS and FX locks are used for both class objects and instance objects. To make the distinction between the two types of locks clearer, we hereon use S and X to represent the FS and FX locks on instance objects. We use FS and FX to represent the FS and FX locks on class objects. Thus, M = = {NL, FS, FX, TS, TX, FSD, FXD, TSD, TXD, FSN, FXN, FSH, TXH, TSH, TXH, FSO, FXO, TSO, TXO, S, X}. Given the basic two-mode protocol in Table 5-3, m is the set of lock modes {NL, S, X}. Let c:m×m {Yes, No} be the restriction of C to m. A lock-graph is a mapping L: N M such that: (a) If L(n) {FS, TS, FSD, TSD, FSN, FSH, TSH, FSO, TSO, S} then either n is a source with no parents or there exists a parent p of n such that L(p) {FS, TS, FSD, TSD, FSN, FSH, TSH, FSO, TSO, FX, TX, FXD, TXD, FXN, FXH, TXH, FXO, TXO}. Even though there is one source node in the LG graph, namely the class inheritance tree rooted at the root class, the path from this source node to n can contain many nodes. The set of all possible locks held by these nodes is L(p). Assume that r is a parent of p, L1(p) {FS, TS, FSD, TSD, FSN, FSH, TSH, FSO, TSO} and L2(p) {FX, TX, FXD, TXD, FXN, FXH, TXH, FXO, TXO} where L1(p) U L2(p) = L(p). If the lock on p L1(p), then 57 L1(r) {FS, TS, FSD, TSD, FSN, FSH, TSH, FSO, TSO, FX, TX, FXD, TXD, FXN, FXH, TXH, FXO, TXO} using (a). If the lock on p L2(p), then L2(r) {TX, TXH, FXD, TXD, FXO, TXO} using (b). Notice that L(r) equals to the union of L1(r) and L2(r) which is {FS, TS, FSD, TSD, FSN, FSH, TSH, FSO, TSO, FX, TX, FXD, TXD, FXN, FXH, TXH, FXO, TXO}. By induction there exists a path P from a source to n such that if q is an ancestor of n, L(q) {FS, TS, FSD, TSD, FSN, FSH, TSH, FSO, TSO, FX, TX, FXD, TXD, FXN, FXH, TXH, FXO, TXO} on it. In other words, L(n), where n is in P, cannot be empty. Thus, all nodes on P are properly locked. (b) If L(n) {FX, TX, FXD, TXD, FXN, FXH, TXH, FXO, TXO, X} then either n is a source or for all parents p1...pk of n we have L(pi) {TX, TXH, FXD, TXD, FXO, TXO} where i = 1...k. By induction there exists a path from a source to n such that if q is an ancestor of n, L(q) {TX, TXH, FXD, TXD, FXO, TXO} on all the ancestors of n. The lock-graph L for a transaction shows the set of objects being locked and their corresponding lock modes for a particular transaction using the different lock modes described in Table 5-2 above. Although some of the locks on objects are implicitly acquired from their parents' locks, it is assumed, in this proof, that all of these implicitly acquired locks are explicitly represented in the lock graph. For example, if one locks a class inheritance tree with a FSH lock, all subtrees of the inheritance tree are implicitly locked with FSH locks also. These implicitly acquired locks are explicitly represented in the lock graph for the purpose of this proof. The projection of a lock-graph, on the other hand, shows the set of locks in the three-state locking protocol on atomic resources correspondingly acquired by a transaction through the explicit locks being held. The projection of a lock-graph L is the mapping l:SN m constructed as follows: (a) l(n) = X if there exist a node-slice {n1...ns} of n such that L(ni) {FX, FXN, FXH, FXO} where i = 1...ns. (b) l(n) = S if (a) is not satisfied and there exists an ancestor a of n such that L(a) {FS, FSN, FSH, FSO, FX, FXN, FXH, FXO}. (c) l(n) = NL if neither (a) nor (b) is satisfied. Two lock-graphs L1 and L2 are said to be compatible if C(L1(n), L2(n)) = YES for all n N. Similarly two projections l1 and l2 are compatible if c (l1 (n), l2 (n) ) = YES for all n SN. 58 We would like to show that when two lock-graphs from two transactions are compatible, their projections would also be compatible. In this case, the projection is the simple two-state locking protocol with the addition of the NL lock. Theorem 5-2: If two lock-graphs L1 and L2 are compatible with each other, then their projection l1 and l2 are also compatible. In other words, if the explicit locks set by two transactions are not conflicting, then also locks implicitly acquired by these transactions in the three-state locking protocol (simple two-state locking protocol with the addition of NL lock) are not conflicting. Proof: To prove the theorem, we need to show that the lock-graph L1 and L2 are incompatible when the projection l1 and l2 are incompatible. By definition of compatibility defined in Table 5-3, there must exist a sink n such that l1(n) = X and l2(n) {S, X} or vice versa for l1 and l2 to be incompatible. Otherwise, if both l1(n) and l2(n) {S}, they are compatible. Assume without the loss of generality that l1(n) = X and l2(n) {S, X}. By definition of projection there must exist a node-slice {n1...ns} of n such that L1(n1) ...L1(ns) {FX, FXN, FXH, FXO}. Also there must exist an ancestor n0 of n such that L2(n0) {FS, FSN, FSH, FSO, FX, FXN, FXH, FXO}. The path from a source to n in L2 must intercept the node-slice of n in L1. The intersection can occur either from the source to n0 or from n0 to n. From the definition of lock-graph there is a path P1 from a source to n0 on which L2 is not null. If P1 intersects the node-slice at ni then L1 and L2 are incompatible since L1(ni) {FX, FXN, FXH, FXO} which is incompatible with the non-null value of L2(ni). Alternatively, there is a path P2 from n0 to the sink n which intersects the node-slice at ni. From the definition of lock-graph, L1 takes a value in {TX, TXH, FXD, TXD, FXO, TXO} on all ancestors of ni. In particular L1(n0) {TX, TXH, FXD, TXD, FXO, TXO}. Since L2(n0) {FS, FSN, FSH, FSO, FX, FXN, FXH, FXO}, we have C(L1(n0), L2(n0)) = NO. Thus, the theorem is proofed. 59 5.9 Lock Escalation and De-escalation Locking using the lock modes defined in section 5.4 ensures that updates by various transactions in a database can be done correctly and consistently. However, the overhead of maintaining these locks could be high, depending on the number of objects being locked, the types of objects being locked, and the contention level. If the contention level among transactions is low, coarser granularity objects should be used for locking. This results in fewer objects being locked. This in turn results in fewer overheads. On the other hand, locking finer granularity objects is appropriate when the contention level among transactions is high. The optimal choice of locking granularity for different transactions can be different. It is also true that the optimal choice can be different even within a single transaction at a different time. Hence, decisions must be made dynamically at run-time to provide the optimal solution for each transaction. A static choice made uniformly for all transactions in a database would produce average results for most transactions. For instance, if we set the granularity level to be class-instance, meaning that we can lock a class and its instances as a unit or each instance as a unit, this would be a good fit for those transactions accessing instances from different classes. However, this would be a poor fit for those transactions that are accessing instances from the same class inheritance tree, where choosing a different granularity unit could reduce locking overhead. Most automatic locking systems do acquire locks for transactions on demand. Generally, they default to fine granularity locking unless there is other guidance. This allows the system to have the maximum degree of concurrency even if the system picks the wrong granularity units. However, once the granularity unit is acquired, it will not be changed even when there might be a better granularity unit to lock later in the transaction. Over time, these results in granularity units that are not the best choice being locked by a transaction. To correct this problem, lock escalation is used. For example, the system might use a fine granularity unit for locking when a coarse granularity unit would be more appropriate. Potentially, this could result in hundreds of unnecessary locks being maintained by the system. However, using lock escalation when the number of locks hits a certain number or threshold, the system would try to convert some of these smaller granularity units into larger granularity units. A different approach would be to lock the largest granularity unit at the beginning of a transaction even if most of the objects locked may not be needed at first. If there is any conflict from other transactions, lock de- escalation is performed. Each conflicting transaction would lock the next highest granularity unit that is not in conflict. 60 My proposed protocol combines both lock escalation and lock de-escalation into the multi-granularity protocol described in section 5.1. Both of these operations are performed dynamically during the transaction. The protocol is able to detect situations of low contention and automatically reduce the number of lock requests per transaction. If contention increases, the protocol then increases the number of lock requests (using finer granularity units) to the appropriate level. Therefore, the protocol adapts to the transaction requirements. The protocol first defaults to lock the highest granularity unit at the beginning of each transaction. However, it keeps track of the objects being accessed and the types of access. This information is needed when lock de-escalation is performed. When the number of locks exceeds an escalation threshold, lock escalation is performed. The lock escalation attempts to acquire the highest granularity unit that is not in conflict with other transactions. The process of lock escalation and de-escalation can be performed repeatedly during the lifetime of a transaction. 5.9.1 Lock Conversions Traditionally, lock conversions refer to the process of changing locks of an object from one mode to another mode. For example, a transaction may lock an object at the beginning for read access. Later it needs to write to the object. The shared lock it held would have to be converted into a more restricted exclusive lock mode. I will call this conversion lock mode conversion. Furthermore, lock mode conversion is not restricted to just converting from read access to exclusive access or vice versa. Any lock mode existing in the compatibility matrix can be converted to other lock modes following a defined rule. This rule is stated in Lock Mode Restriction Definition 5-2. With multi-granularity locking, another type of lock conversion also exists. I will refer to this type as the lock coverage conversion. This conversion deals with the set of objects that are covered by a lock. Some locks cover more objects than other locks because some locks may be locking a larger granular unit than others. With lock coverage conversions, locks can be upgraded or downgraded to cover more or fewer objects. 5.9.1.1 Lock Mode Restriction Lock mode restriction deals with the level of access rights of a lock. If lock X is compatible with more locks than lock Y on the same resource, we can say that lock Y has fewer access rights than lock X or it is more mode restrictive than lock Y. 61 Lock Mode Restriction Definition 5-2: Let L1, L2 be two lock modes. L1 is more mode restrictive than L2, L1 m L2 if and only if Lx in Table 5-2, if C(L1, Lx) Y, then C(L2, Lx) Y (1) where C(Lx, Ly) denotes the compatibility between Lx and Ly as indicated in Table 5-2. Lx and Ly are compatible if the intersection between Lx and Ly in Table 5-2 is `Y'. Compatibility between Lx and Ly is symmetric if Lx is compatible with Ly implies that Ly is compatible with Lx. This is the case in Table 5-2. The mode exclusive m relationship is a partial ordering relationship. Example 1: This set of locks {FS, TS, FSD, TSD, FSN, FSH, TSH, TXH, FSO, TSO} are compatible with FS. In other words, C(FS, Lx) Y where Lx { FS, TS, FSD, TSD, FSN, FSH, TSH, TXH, FSO, TSO}. This set of locks {FSD, TSD, TSH, TXH} are compatible with FX. In other words, C(FX, Lx) Y where Lx { FSD, TSD, TSH, TXH }. The set of locks that are compatible with FX is a subset of locks that are compatible with FS. More simply, in every column of Table 5-2 where FX has a `Y', so does FS. We can say that FX is more mode restrictive than FS. Example 2: The locks of the set S = {FS, TS, FSD, TSD, FSN, FSH, TSH, TXH, FSO, TSO} are compatible with FS. In other words, C(FS, Lx) Y, for all Lx in S. The locks of the set T = {FSD, TSD, TSO, TXO} are compatible with FXH. In other words, C(FXH, Lx) Y for all Lx in T. The set of locks that are compatible with FXH is not a subset of locks that are compatible with FS; i.e. T S. More simply, it is not true that in every column of Table 5-2 where FXH has a `Y', so does FS. We cannot say that FXH is more mode restrictive than FS. 62 5.9.1.2 Lock Coverage Restriction Lock coverage restriction deals with the resource coverage of a lock. If lock X implicitly locks more resources than lock Y on the same resource, we can say that lock Y covers fewer resources than lock X or it is more coverage restrictive than lock Y. Lock Coverage Restriction Definition 5-3: Let L1, L2 be two lock modes. L1 is more coverage restrictive than L2, L1 c L2 if and only if Ox where Ox is an lockable granular unit, OC(Ox, L1) OC(Ox, L2), where OC(Ox, Li) denotes the set of objects that are locked explicitly or implicitly when lock Li is obtained for Ox The coverage restrictive c relationship is a partial ordering relationship also. Example 1: An FS lock on class X locks the class object and all its instance objects. In other words, OC(Oclass(X), FS) = {class object X, all instance objects of class X}. A FSH lock on class X locks all classes rooted at class X and all instances of these classes. In other words, OC(Oclass(X), FSH) = {class object X, subclass objects of class X, instance objects of all classes rooted at class X}. The set of objects that are locked by class lock FS is a subset of objects that are locked by FSH lock. Therefore, we can say that class lock FS is more coverage restrictive than class lock FSH. Example 2: An FSO lock on composite object X locks the object itself and all its component objects. In other words, OC(Ocomposite_object(X), FSO) = {object X, all component instance objects of object X}. An FS lock on composite object X locks the object itself. In other words, OC(Occomposite_object(X), FS) = {object X}. The set of objects that are locked by instance lock FS is a subset of objects that are locked by FSO lock. Therefore, we can say that instance lock FS is more coverage restrictive than the composite instance lock FSO. 63 As mentioned before, both the mode restrictive m and the coverage restrictive c relationships are partial ordering relationships. Using these two relationships, locks can be upgraded or downgraded with respect to either of these partial orderings. Here we define the meaning of upgrading and downgrading a lock. Lock Upgrade Definition 5-4: A lock L1 is upgraded to L2 if there is a lock conversion from L1 to L2 and L1 m L2 or L1 c L2 Lock Downgrade Definition 5-5: A lock L1 is downgraded to L2 if there is a lock conversion from L1 to L2 and L2 m L1 or L2 c L1 Therefore, a lock x can be upgraded/downgraded to a lock y if there is a conversion from lock x to lock y that satisfies either the partial ordering of lock mode restriction or the partial ordering of lock coverage restriction. 5.9.2 Lock Escalation and De-escalation Definitions With the definitions of LG graph and lock conversions, lock escalation and de-escalation can now be defined as follows: Lock Escalation Definition 5-6: Let L1, L2 be two locks. Lock escalation is defined as the process of lock conversion from L1 to L2 such that L1 is upgraded to L2 on lockable granular unit Ox or if given the compatibility matrix in Table 5-2, C(L1(Ox), L2(Oy)) Y where Li(Oj) is the lock Li that is applied to lockable granular unit Oj and A in the LG graph. The definition specifies that a lock x can be escalated to another lock y in two ways. First, it can be done through the process of lock upgrade. That is, lock x is upgraded to lock y using the lock mode restriction ordering or the lock coverage restriction ordering. Second, lock escalation can also be done by locking a larger granular unit in 64 which the original granular unit is contained. In other words, a lock is obtained on a parent node of a node in the LG graph when lock escalation happens. It should also be noted that even though the compatibility table defined in Table 5-2 deals with compatibility among lock types, lock granular units for each lock type are also implied in the Table 5-1. Lock De-escalation Definition 5-7: Let L1, L2 be two locks. Lock de-escalation is defined as the process of lock conversion from L1 to L2 such that L1 is downgraded to L2 on lockable granular unit Ox or if given the compatibility matrix in Table 5-2, C(L1(Ox), L2(Oy)) Y where Li(Oj) is the lock Li that is applied to lockable granular unit Oj and A in the LG graph. The definition is the opposite of the definition of lock escalation. It specifies that a lock x can be de- escalated to another lock y through either the process of lock downgrade or by locking a smaller granular unit in the LG graph. Escalation and De-escalation Examples: * FS lock on class X escalates to FX lock on class X. This escalation expands the access rights from read access to exclusive access on class X. * FS lock on class X escalates to FSH lock on class X. This escalation expands the lock coverage from only the class and its instances to the class hierarchy rooted at class X. * FSH lock on class X escalates to FSH lock on the parent class of class X. This escalation also expands the lock coverage. However, this is accomplished by applying a lock on a granular unit that contains the granular unit intended. Therefore, instead of locking the class hierarchy rooted at class X, the class hierarchy rooted at the parent of class X is locked. * FSO lock on composite object O escalates to FSH lock on class hierarchy object that contains all classes of the component instances in the composite object O. We escalate the lock by locking a larger granular unit. Here we 65 lock the class hierarchy that comprises all the classes of the composite object instead of just the composite object itself. * FSH lock on class X de-escalates to FS lock on class X. This de-escalation contracts the lock coverage from the class hierarchy rooted at class X to only the class X and its instances. 5.9.3 Triggers for Escalation and De-escalation When should an escalation or de-escalation happen during a transaction? Several choices exist. For escalation, here are some of the choices: 1) When a transaction exceeds a certain number of locks. 2) When the total number of locks of all transactions exceeds a certain number. 3) When a lock is requested for a transaction. 4) When the number of transactions is small. 5) When the number of conflicting transactions is small. For de-escalation, here are some of the choices: 1) When there is a conflict with another transaction. 2) When the waiting time of another conflicting transaction exceeds a certain threshold. 3) When the current transaction is done. 4) When the number of transactions is large. 5) When the number of conflicting transactions is large. Each of these choices has advantages and disadvantages. For the proposed protocol, escalation is done when a transaction exceeds a certain number of locks. De-escalation is done when there is a conflict with another transaction. These choices are selected to reflect the nature of applications that are the target of the proposed object- oriented database, namely long transaction with relatively few conflicts among transactions. 5.9.4 Optimistic Protocols for Requesting Locks With the ability to escalate and de-escalate locks in a transaction, a transaction can be more optimistic in determining the granularity of resources that should be acquired when a resource is needed. This is possible since if 66 the transaction is wrong in its initial assumption and locks too many resources (thus causing conflicts with other transactions), these conflicts will be resolved by the system through the de-escalation mechanism. For this reason, a more optimistic protocol is appropriate for locking resources when lock escalations and de-escalations are possible. The protocol in section 5.6 is modified with this property in mind. The additional updates are listed in the following sections. 5.9.4.1 Locking Instances a) To lock instance I of class C in shared mode or exclusive mode, a class hierarchy lock is requested for the whole class inheritance tree (or the root class) using protocol 4a or 4b. See Section 5.6.1.2. If the lock can be granted, the actual object needed and the access type are recorded and the process ends successfully. b) If the lock request cannot be granted, a lock request for the subtree of the inheritance tree that includes class C is issued. If the lock can be granted, the actual object needed and the access type are recorded and the process ends successfully. The process is repeated until one of the subtrees can be locked or when there is no subtree left. c) If no subtree can be locked, a class lock is requested for class C using protocol 3a or 3b. See Section 5.6.1.1. If the lock can be granted, the actual object needed and the access type are recorded and the process ends successfully. d) If the lock request cannot be granted, a lock request for the instance I of class C is issued using protocol 2a or 2b. See Section 5.6.2.1. 5.9.4.2 Locking Composite Objects a) To lock composite object instance I of class C in shared mode or exclusive mode, a class hierarchy lock is requested for the whole class inheritance tree using protocol 4a or 4b. See Section 5.6.1.2. If the lock can be granted, the actual object needed and the access type are recorded and the process ends successfully. b) If the lock request cannot be granted, a lock request for the subtree of the inheritance tree that includes all classes of I is issued. If the lock can be granted, the actual object needed and the access 67 type are recorded and the process ends successfully. The process is repeated until one of the subtrees that contains all classes can be locked or when there is no subtree left. c) If no subtree can be locked, a composite object lock is requested for object instance I using protocol 5a or 5b. See Section 5.6.2.2. 5.9.4.3 Locking Classes a) To lock class C and all its instances in shared mode or exclusive mode, a class hierarchy lock is requested for the whole class inheritance tree using protocol 4a or 4b. See Section 5.6.1.2. If the lock can be granted, the actual object needed and the access type are recorded and the process ends successfully. b) If the lock request cannot be granted, a lock request for the subtree of the inheritance tree that includes class C is issued. If the lock can be granted, the actual object needed and the access type are recorded and the process ends successfully. The process is repeated until one of the subtrees can be locked or when there is no subtree left. c) If no subtree can be locked, a class lock is requested for class C using protocol 3a or 3b. See Section 5.6.1.1. 5.9.4.4 Locking Class Hierarchies a) To lock class hierarchy H in shared mode or exclusive mode, a class hierarchy lock is requested for the whole class inheritance tree using protocol 4a or 4b. See Section 5.6.1.2. If the lock can be granted, the actual object needed and the access type are recorded and the process ends successfully. b) If the lock request cannot be granted, a lock request for the subtree of the inheritance tree that includes class hierarchy H is issued. If the lock can be granted, the actual object needed and the access type are recorded and the process ends successfully. The process is repeated until one of the subtrees can be locked or when there is no subtree left. 68 5.9.4.5 Locking Class definitions a) To lock class definition S of class C in shared mode or exclusive mode, a class definition lock is requested for the root class using protocol 4a or 4b. See Section 5.6.1.2. If the lock can be granted, the actual object needed and the access type are recorded and the process ends successfully. b) If the lock request cannot be granted, a lock request for the subclass that is a superclass of class C is issued. If the lock can be granted, the actual object needed and the access type are recorded and the process ends successfully. The process is repeated until one of the superclasses can be locked or when there is no superclass left. c) If no superclass can be locked, a class definition lock is requested for class C using protocol 1a or 1b. See Section 5.6.1.3. 5.9.5 Examples I will illustrate how the protocol works in practice with an example in this section. Assume that there are five transactions executing concurrently, T1...T5. The database consists of six classes named A through F. These classes form a class inheritance tree with class A at the root. Classes D, E F have three instances each. See Figure 5-10. I will use a small letter to denote these instances, d1 through d3, e1 through e3, f1 through f3. 69 Transaction T1 is the first transaction being executed and it tries to read object d1. Following the proposed T1:FXH A B C D E F d1 Figure 5-10: Example: object locking with one transaction protocol, an FXH lock is acquired for the whole class inheritance tree rooted at class A, since this will be the largest granularity unit. Two points should be noted. First, the minimum set of objects that need to be locked for this transaction is a shared mode lock for the object instance d1. This piece of information is stored within the lock manager to facilitate de-escalation in the future if needed. Second, although we only need a shared mode access to the database, an exclusive lock is acquired since we would like to issue the broadest access permission and the largest granularity unit at the beginning. The locks obtained and the object being locked are shown in Figure 5-10. 70 T1,T2:TXH T2:FXH A T1:FXH B C D E F d1 f3 Figure 5-11: Example: object locking with two transactions In Figure 5-11, transaction T2 comes in and is trying to access object instance f3. Since the whole inheritance tree is locked by T1 and T1 does not access f3, a lock de-escalation process is performed. First, T1 demotes the current lock it holds to a soft lock. Then it tries to acquire the next largest granularity unit with the broadest access rights. In this case, it locks the whole inheritance tree rooted at class B. The soft lock TXH on class A serves as a reminder that dependent objects are being accessed by T1. T2 also tries to lock the largest unit that includes object instance f3. In this case, it locks the inheritance tree rooted at C with a class hierarchy exclusive lock. Before it can acquire this lock, it needs to first set a soft lock on the class inheritance tree rooted at class A to indicate that it is accessing its subparts. Next, T2 tries to modify the value stored in object instance f2. Since T2 already has an exclusive lock on the inheritance tree to which f2 belongs, no additional lock is required. However, the fact that T2 requires exclusive access to f2 is recorded by the lock manager. This is shown in Figure 5-12. 71 T1,T2:TXH T2:FXH A T1:FXH B C D E F d1 f1 f2 f3 Figure 5-12: Example: object locking with two transactions continues... Two more transactions T3 and T4 begin execution and try to access object instances e3 and f1 respectively. See Figure 5-13. Each of them requires lock de-escalation to be performed. Suppose that T3 needs shared access to e3. This requires T1 to be notified and its lock for the inheritance tree rooted at class B demoted to a soft exclusive lock, while it acquires a class hierarchy exclusive lock at class D. This allows T3 to acquire a class hierarchy exclusive lock at class E. T3 also acquires soft locks on the class inheritance trees rooted at class A and B along the way. On the other hand, suppose that T4 needs exclusive access to f1. Since T2 holds a lock for a granularity unit that includes f1, T2 has to de-escalate its lock. To avoid conflicts with T4, T2 has to de-escalate all the way to the minimum set of locks that it needs. Namely, it acquires a shared lock on f3 and an exclusive lock on f2. Since T4 cannot obtain a lock that would not conflict with T3 for any granularity unit other than the object instance itself, it takes an exclusive lock on it. 72 In Figure 5-14, transaction T5 tries to lock a composite object. The composite object is made up of c1 and e2. To lock this composite object, the protocol would first try to lock the largest granularity unit that contains all these object instances. The largest unit would be the class inheritance tree rooted at class A. This unit will include all classes and all instances of these classes. However, an exclusive lock cannot be obtained for this unit without creating conflicts with other transactions. Again, the protocol looks for the next highest granularity unit. This would be the collection of classes to which component instances belong, namely class E and class C. However, class E is T1,T2,T3,T4:TXH A T2,T4:TXH T1,T3:TXH B C T1:FXH T2,T4:TX D E F d1 e3 f1 f2 f3 T2:FX T2:FS T3:FXH T4:FX Figure 5-13: Example: object locking with four transactions also being used by transaction T3. Thus, a lock cannot be granted for this unit either. The next level would be to lock the set of instances comprising the composite object, namely c1 and e2. This lock can be granted since no other transaction is using this set of instances. However, it does require T3 to first de-escalate its locks to make e2 available for T5. In addition, soft locks are acquired by T5 on all superclasses of the classes of the composite objects. 73 T1,T2,T3,T4,T5:TXH A T2,T4:TXH T1,T3,T5:TXH T5:TX T5:FXO B C T1:FXH T3:TX T5:TX T2,T4:TX D E c1 F d1 e2 e3 f1 f2 f3 T2:FX T2:FS T3:FX T4:FX Figure 5-14: Example: object locking with five transactions 74 Chapter 6 Simulation Overview This chapter presents the development of the simulation model. Components of the simulation model are discussed, namely the user model, the database system model, and the transaction model. Next, the performance statistics collected during various simulation runs are also listed and are explained. The implementation of the simulation environment and the programming toolkit used for creating the environment are described. Finally, a sample of the programming code is inserted in the last section for reference. 6.1 Simulation Model The simulation model consists of three models. The user model specifies the types of transactions generated by users. It describes the frequencies and the access patterns of these transactions. It also describes the types of users that would be using the database management system. The database model describes the characteristics and the structure of the database. It specifies the types of objects in the database and the relationships among these objects. Finally, the transaction model details the characteristics of the transaction processing system. It describes the resources being used by the transaction system. It also spells out the elements and the processing order of various components. 6.1.1 User Model The typical users of the database system that employs the proposed concurrency control protocols generate transactions that are long-lived and involve relatively few update conflicts with other users. These transactions are generally interactive in nature and may involve a relatively large number of database objects. Therefore, there is no 75 predictable common access patterns among these transactions. The duration of these transactions could be measured in seconds, minutes or even hours. 6.1.2 Database System Model The database model is a modification of the database model used in the OO7 database [39]. In the OO7 database, the key component is a set of composite parts. Each composite part corresponds to a design component, like a module in a CAD application or a procedure in a software development project. However, OO7 by itself does not model some aspects of the database required by these experiments. First, the OO7 database does not model the class inheritance relationship. There are no classes and subclasses in the OO7 database. Class and class hierarchies are added to our database. Secondly, OO7 is designed to test various operations like query, update, and indexing of object-oriented databases. The aim of the proposed experiments is only to test one aspect of the object-oriented database; namely, the concurrency control subsystem. Therefore, OO7 contains many components that are not necessary in our case. The database consists of a set of classes. These classes form a class hierarchy. The exact nature of the organization is controlled by two parameters; numSubClassPerClass and numClassLevel. The parameter numSubClassPerClass defines the number of subclasses of each class. The depth of the class hierarchy tree or the number of class levels is defined by numClassLevel. This specifies the number of class levels that should be created below the root class. Together these two parameters determine the number of classes in the database, which is 1 + n iC Cn -1 or where C is the number of subclasses per class and n is the number of class levels of the class i=0 C -1 hierarchy. Each class has a number of attributes, including an integer id and a buildDate. Each class also has a number of instances associated with it. The exact number of instances is controlled by two parameters numMaxInstancePerClass and numMinInstancePerClass. A random number uniformly distributed between these two numbers is used to determine the number of instances per class for each class. Therefore, each class could have a different number of instances associated with it. Each instance also has two attributes; an integer id and a buildDate. Since my primary interest is in the effects of granularity units on locking performance and I do not consider the assoication relationship as part of a granularity unit, there is no need to model association relationships among instances. 76 A key granularity unit is the composite object. In the model, each composite object is an instance of a composite class. A composite class is similar to a regular class except that it contains composite links or PART OF links to other classes. The number of composite classes in the database is controlled by the parameter numCompositeClass. Each composite class can be linked to multiple classes. These classes themselves can form a part hierarchy. The number of classes that are associated with a composite class is controlled by the parameter numClassPerComposite. A composite instance is a group of instances rooted at a composite class. It consists of a root instance, that is an instance of the composite class, and a set of part instances, that are instances of the classes linked with the composite class. The number of composite instances in the database is determined by the parameter numCompositeInstance. Each composite instance also has an integer id and a buildDate. If a composite object corresponds to a procedure in a CASE application, each of the part instances in its associated graph might correspond to a variable, statement, or expression in the procedure. Parameters Description NumMaxInstancePerClass Maximum number of instances per class. NumMinInstancePerClass Minimum number of instances per class. NumClassPerComposite Number of different classes of all component instances contained in a composite object. NumCompositeClass Number of classes that contain composite instances. NumCompositeInstance Total number of composite objects in the database. NumSubClassPerClass Number of subclasses in a class. NumClassLevel The depth of the class hierarchy. Table 6-1: Summary of Database Parameters 77 6.1.3 Transaction Model The transaction model assumes a closed queuing model of a single-site database system. Transactions will Terminals ready queue RESTART concurrency control queue Concurr COMMIT ency Control ACCESS blocked queue BLOCK Delay object access queue no More? yes Figure 6-1: Simulation Model be generated from a fixed number of terminals. These transactions will be simulated by a transaction generator. The transaction generator generates transactions following an exponential (Poisson) distribution with parameter . The number of transactions generated by the transaction generator is determined by NumIncomingTransactions. Each transaction is also assigned a unique identification number, transID. All transactions are part of the transaction set. 78 A transaction set is randomly generated by the transaction generator using a binomial distribution. Schema-change transactions can be included in the transaction set; the proportion of schema-change transactions is given by the variable ratioSchemaChange. This transaction set represents all possible transactions that will enter the system during the simulation. During the simulation run, one of the transactions in the transaction set is removed from the set and entered into the system at random intervals. In addition to schema change transactions, there are two other types of transactions. The first type of transaction consists of only read operations. The proportion of this type of transactions out of the total number of transactions is given by the variable ratioTransactionRead. The second type of transactions consists of a mixture of read and write operations. The portion of this type of transactions out of the total number of transactions is controlled by the variable ratioTransactionMix. Both types of transactions are defined here. Transaction Definition 6-1: A typical transaction T, can be defined as follows: T = {R[xi], RandomDelay(t), W[xi] | xi is an object in the database} where R[xi] is a set of read operations and W[xi] is a set of write operations, and t is the time delay between each pair of access operations. The set of objects in the set of write operations is a subset of the set of objects in the set of read operations. In other words, W[xi] R[xi]. W[xi] can be an empty set, in this case, the transaction consists of only read operations. Each of the transactions in the transaction set is represented by a set of object access operations or the access set of the transaction, modeled according to the number of objects that it reads and writes. The maximum number of objects that can be accessed by a transaction is guided by the parameter TotalObject. The actual set of objects accessed is further determined by eight additional parameters. SimpleRead gives a ratio of the TotalObject that are simple instance object reads. SimpleRatioWrite gives a ratio of the SimpleRead that are simple instance object writes. CompositeRead gives a ratio of the TotalObject that are composite instance object reads. CompositeRatioWrite gives a ratio of the CompositeRead that are composite instance object writes. ClassRead gives a ratio of the TotalObject that are class instance object reads. ClassRatioWrite gives a ratio of the ClassRead that are class instance object writes. HierarchyRead gives a ratio of the TotalObject that are class hierarchy instance object 79 reads. HierarcyRatioWrite gives a ratio of the HierarchyRead that are class hierarchy instance object writes. All these objects are selected randomly from among all of the objects in the database. A maximum of MaxTransactionsInRunning can be active simultaneously in the system. Any transaction exceeding this limit would be put into the ready queue. The transaction ready queue uses first-come-first-serve (FCFS) scheduling. A transaction becomes active when it leaves the ready queue. This happens when one of the active transactions either completes or aborts. The transaction enters the concurrency control queue after the ready queue. The concurrency control queue is where object access requests are made. If the requests can be granted by the concurrency control manager, the transaction continues to enter the object access queue where object access requests are being served. One or more object access requests can be served in this queue. However, one request is served at a time. Therefore, if requests contain several objects, several requests are issued to the object access queue. The transaction cycles through the concurrency control queue every time it has another object access request. A delay is inserted after each object access request to simulate data processing time. This delay can also be used to simulate long duration transactions and interactive transactions. If the object access request is not granted, the transaction enters the blocked queue and waits for the request to be granted. If a transaction aborts because of deadlock or any other reasons, it is restarted and goes back to the ready queue. Those transactions that have all object access requests granted successfully are moved to the commit stage. If the transaction is read-only, there is nothing more to do. If the transaction has write operations, the new objects are written to the disk. Several resources used in the simulation model are not explicitly shown in Figure 6-1. The resource model is shown in Figure 6-2. There are several physical resources, terminals, the CPU and the I/O resources, namely the disks. The corresponding physical queuing model is a collection of terminals, multiple CPU servers, and multiple I/O servers. Parameters numTerminals, numCPUs, numIO are used to specify the number of terminals, CPU servers, and I/O servers. Although there may be more than one CPU, the CPUs, together, are treated as a single server with a single queue, since we consider the CPUs are interchangeable. As soon as a CPU is free, it will be assigned to the next request. The request in the CPU queue uses the FCFS queuing discipline. The system assumes a uniform distribution of the database across all I/O devices. When an I/O request arrives, it has equal likelihood of being for each of the disks. There is one global I/O queue for all I/O devices. All transactions will be waiting on that queue. The requests are served on a FCFS basis. 80 The parameters ObjectIO and ObjectCPU are the amounts of I/O and CPU time associated with reading or writing an object. Reading an object takes time equal to ObjectIO followed by ObjectCPU. Writing an object takes time equal to ObjectCPU at the time of the write request and ObjectIO at commit time. The parameters LockIO and LockCPU are the amounts of I/O and CPU time associated with reading or writing a lock. In addition to the locking overhead, there is other overhead in the database system, like context switching, semaphore contention, memory bandwidth, etc. In this study, we assume that all these costs are negligible since we want to concentrate on the locking overhead only. TERMINALS RESTART No Disk concurrency control queue I/O queue Yes Lock Request Disk CPU CPU queue Lock Release CPU Figure 6-2: Physical Resource Usage Model 81 6.1.4 Summary of Simulation Parameters Parameters Description ObjectIO The amount of I/O time associated with reading or writing an object. ObjectCPU The amount of CPU time associated with reading or writing an object. LockIO The amount of I/O time required to request and set a lock for one granularity unit. LockCPU The amount of CPU time required to request and set a lock for one granularity unit. NumTerminals Number of terminals. NumCPUs Number of CPUs. NumIO Number of I/O devices. MaxIncomingTransactions Maximum number of transactions allowed in the system. MaxTransactionsInRunning Maximum number of running transactions allowed in the system MaxEscalationLockCount Maximum number of locks held before lock escalation process begins DurationTransaction The average amount of time a transaction needs for processing all objects read by the transaction. MaxRunTime The maximum amount of time the simulation can run. TotalObject The maximum number of objects a transaction access. SimpleRead The average number of simple objects read by a transaction. SimpleRatioWrite The ratio of simple objects written to the number of simple objects read. CompositeRead The average number of composite objects read by a transaction. CompositeRatioWrite The ratio of composite objects written to the number of composite objects read. ClassRead The average number of class objects read by a transaction. ClassRatioWrite The ratio of class objects written to the number of class objects read. HierarchyRead The average number of class hierarchy objects read by a transaction. HierarchyRatioWrite The ratio of hierarchy objects written to the number of hierarchy objects read. RatioTransRead The fraction of read transactions in the transaction set. RatioTransactionMix The fraction of mix transactions in the transaction set. RatioSchemaChange The fraction of schema change transactions in the transaction set. Table 6-2: Summary of Simulation Parameters 82 6.2 Criteria of Performance Evaluation In our simulation experiments, the following criteria are measured to evaluate the performance of each locking protocol. 6.2.1 Locking-related Metrics: * Lock Attempts: The total number of lock attempts performed by all transactions in one session. * Lock Count: The total number of locks obtained by all transactions in one session. These locks include those obtained in the escalation/de-escalation process. * Demotion Lock Attempts: The total number of lock attempts performed by all transactions in one session during the de-escalation process. * Demotion Lock Count: The total number of locks obtained by transactions in one session during the de- escalation process. * Release Lock Count: The total number of locks released by transactions in one session. * Lock Escalation Count: The total number of times the lock escalation process is performed * Lock De-escalation Count: The total number of times the lock de-escalation process is performed. * Total Lock Count: The total number of locks held by all transactions at commit time. * Aborted Lock Attempt: The total number of times a lock attempt is aborted. * Lock Ratio: Transaction Access Count divided by Lock Count. This gives an idea of how powerful a single lock is on average. 6.2.2 Conflict-related Metrics: * Transaction Block Count: The total number of times transactions block in one session. * Transaction Access Count: The total number of object access as requested by transactions in one session. 83 6.3 Simulation of the Concurrency Control Protocols 6.3.1 Simulation Environment In this section, the toolkit that was used to build the simulation program and the environment used to run the simulation is described. The simulation model built was an abstraction of an object-oriented database management system. It contained the important elements that are relevant to the concurrency control protocols. It is also built to simulate transactions being executed through a database management system. Lock Managers, concurrency control managers and transaction managers are all simulated for the control of the database operations. In addition to these elements, several other processes are also simulated in the system. These elements include the transaction generator, the database generator, and simulation control process. 6.3.1.1 Programming Tool Kit The entire simulation environment was built from scratch using the Smalltalk object-oriented language (VisualWorks environment). This approach was chosen over using simulation languages to provide a more customizable and flexible environment for testing various aspects of the locking protocols. The simulation uses a discrete event model. The state of the system can only change at event times. 6.3.1.2 Smalltalk Classes The simulation consists of many Smalltalk classes. The interaction of these classes creates the simulation environment and the experiments within the simulation. A brief description of the more important classes is listed in Table 6-3, Error! Reference source not found., and Error! Reference source not found.. Sample code for these classes are shown following the table. 84 Class Name Description CC_AccessManager Object Access Manager. It is responsible for managing access requests to resources from transactions. CC_AccessQueue Object Access Queue. It is the queue where all pending access requests are stored. CC_EventManager Simulation Event Manager. It manages events generated within the running of the simulation. CC_SimulationManager Simulation Manager. This is the main control class for the whole simulation. It is responsible for initializing and starting up various managers like lock manager, transaction manager, etc. It also starts and ends the simulation. CC_PerformanceSimulationData Performance Collection. This class is responsible for collection various statistics generated during the simulation run. CC_Transaction Transaction. This class simulates the transactions. Each transaction contains a list of object access requests. CC_TransactionManager Transaction Manager. This class manages the transactions existing within the simulation. CC_ReadyQueue Transaction Ready Queue. This is the queue for storing ready transactions. CC_CompletedQueue Transaction Completion Queue. This is the queue for storing completed transactions. CC_Access Object Access Request. This simulates the object access requests within a transaction. CC_Event Event. These are the events generated in the simulation run. CC_EventQueue Event Queue. This is the queue for storing pending events. CC_BlockQueue Transaction Blocked Queue. This is the queue where blocked transactions are stored. Blocked transactions are transactions that cannot obtain appropriate locks for their object access requests. CC_CCManager Concurrency Control Manager. This manager manages concurrent object requests from transactions. CC_CCQueue Concurrency Control Queue. This is the queue where ready transactions are stored. Ready transactions are transactions that are ready to issue object access requests. Table 6-3: Smalltalk Classes 85 Class Name Description CC_LockManager Lock Manager. This is a superclass of all lock managers in the simulation. CC_LockManager_MGL MGL Lock Manager. This manager implements the multi- granularity locking protocol. CC_LockManager_Simple Simple Lock Manager. This manager implements the simple locking protocol. CC_LockManager_Class Class Lock Manager. This manager implements the class locking protocol. CC_LockManager_AMGL Adaptive Multi-Granularity Lock Manager. This manager implements the adaptive multi-granularity locking protocol. CC_Lock_AMGL Lock. The is the lock that is used for locking resources CC_LockQueue Lock Queue. This is the queue where locks for each lockable resource are stored. There is a CC_LockQueue associated with each CC_LockTableEntry. CC_LockTableEntry_AMGL Lock Table Entry. This simulates the lock entry in the lock table for each resource that is locked in AMGL. CC_LockTableEntry Lock Table Entry. This is used for lock protocols other than AMGL CC_LGN Lock Granularity Node. This is the superclass of all other LGN. CC_LGN_* Various LGN. These classes represent different types of LGN in the LG graph. CC_AtomicInstance Database Atomic Instance. An atomic instance in the database. CC_Class Database Class Instance. A class in the database. CC_CompositeInstance Database Composite Instance. A composite instance in the database. CC_Database Database. This represents the whole database. It contains links to classes, instances, composites instances, in the database. CC_Parameters Database Parameters. This is a list of user-configurable parameters. It is used for generating the database. CC_RootClass Database Root Class. This represents the root class in the database. Table 6-3: Smalltalk Classes continue... 86 Class Name Description CC_Debug Debug. This class is used for debugging purpose. CC_MyRandom Random Number Generator. This class is used for generating random numbers. CC_Timer Virtual Clock. Virtual Timer for the simulation. CC_DatabaseManager Database Manager. This is responsible for generating the database using the database parameters given. CC_Terminal Terminal. This represents the terminal from which transactions come. CC_TerminalManager Terminal Manager. This is responsible for generating transactions from the terminal and inserting them into the simulation. Table 6-3: Smalltalk Classes continue... 6.3.1.3 Sample Smalltalk Code Here I show the Smalltalk code of some of the main classes. The classes shown are CC_CCManager, CC_LockManager_MGL, CC_Transaction and CC_SimulationManager. CC_CCManager Class name CC_CCManager Superclass Object Instance variable LockManager names class variable names pool dictionaries Category Conrad - Simulation, CC Control CC_CCManager is responsible for granting object access requests from transactions. It works closely with the lock manager to make sure consistency within the database is maintained among concurrent access. Instance Variables: lockManager points to the lock manager. Protocol for initialize-release initialize self initialize: (CC_LockManager_MGL new). initialize: aLockManager lockManager := aLockManager. Protocol for operation buildLockGranularityGraph: db lockManager buildLockGranularityGraph: db. 87 generateBlockedTransactionReadyEvent | time anEvent | time := CC_SimulationManager timer tick + 1. anEvent := CC_Event_BlockedTransactionReady new: time. CC_EventManager add: anEvent. generateCCRequestEvent | time anEvent | time := CC_SimulationManager timer tick + 1. anEvent := CC_Event_CCRequest new: time. CC_EventManager add: anEvent. grantAccessRequest: aTransaction ^lockManager grantLocksForTransaction: aTransaction printLockResourceGraph lockManager printLockResourceGraph. processBlockedTransactionReadyRequest: aTransaction CC_SimulationManager s_CCQueue enqueue: aTransaction. processCCRequest: aTransaction "check commit" aTransaction currentAccessRequest type = #O_COMMIT ifTrue: [self releaseLocks: aTransaction. CC_SimulationManager transactionManager removeTransaction: aTransaction] ifFalse: ["check access request" (self grantAccessRequest: aTransaction) ifTrue: [CC_SimulationManager s_AccessQueue enqueue: aTransaction] ifFalse: [CC_SimulationManager s_BlockQueue enqueue: aTransaction]] "Restart" "Reset transaction" "CC_SimulationManager s_ReadyQueue enqueue: aTransaction" releaseLocks: aTransaction ^lockManager releaseLocksForTransaction: aTransaction CC_LockManager_MGL class name CC_LockManager_MGL superclass CC_LockManager instance variable rootLGG lockTable compatibilityTable modeGraph currentRequestedSet names cannotGrantLockFlag class variable names pool dictionaries category Conrad - Simulation, Lock Control CC_LockManager_MGL implements the multigranularity lock manager. It allows multiple granularity locking, lock escalation and lock deescalation in the database. Initially, the lock manager would try to obtain the largest granularity unit that can be locked. So it can also be considered as a optimistic locking scheme with the ability to downgrade a lock if necessary during the execution of transaction. Protocol for private, compatibility table createModeGraph | rootNode fsNode fxNode | rootNode := CC_Mode new: nil. fsNode := CC_Mode new: #FS. fxNode := CC_Mode new: #FX. 88 rootNode childSet: fsNode. fsNode childSet: fxNode. lockCompatible: mode1 with: mode2 ^compatibilityTable at: (mode1 , mode2) asSymbol ifAbsent: [compatibilityTableat:(mode2 , mode1)asSymbol ifAbsent: [self error: 'Compatibility mode not found in table. This should not happen!']] Protocol for private, LGN locking getClassDefinitionLock: obj with: mode in: aTransaction getClassHierarchyLock: obj with: mode in: aTransaction | resourceLockEntry successFlag resourceObject | obj isNil ifTrue: [^nil]. cannotGrantLockFlag ifTrue: [^nil]. resourceObject := self findResourceToLock: obj. resourceLockEntry := self getResourceLockEntry: resourceObject. mode == #FSH ifTrue:[successFlag := resourceLockEntrygetLock:modein:aTransaction by:self. successFlagifTrue: [currentRequestedSet add: resourceLockEntry] ifFalse: [cannotGrantLockFlag := true]. self getClassHierarchyLock: obj superClass with: #TSH in: aTransaction]. mode == #FXH ifTrue:[successFlag := resourceLockEntrygetLock:modein:aTransaction by:self. successFlagifTrue: [currentRequestedSet add: resourceLockEntry] ifFalse: [cannotGrantLockFlag := true]. self getClassHierarchyLock: obj superClass with: #TXH in: aTransaction]. mode == #TSH ifTrue:[successFlag := resourceLockEntrygetLock: modein: aTransaction by: self. successFlagifTrue:[currentRequestedSet add:resourceLockEntry] ifFalse: [cannotGrantLockFlag := true]. self getClassHierarchyLock: obj superClass with: #TSH in: aTransaction]. mode == #TXH ifTrue:[successFlag := resourceLockEntrygetLock:modein:aTransaction by:self. successFlagifTrue:[currentRequestedSet add:resourceLockEntry] ifFalse: [cannotGrantLockFlag := true]. self getClassHierarchyLock: obj superClass with: #TXH in: aTransaction] getClassLock: obj with: mode in: aTransaction | resourceLockEntry successFlag resourceObject | obj isNil ifTrue: [^nil]. cannotGrantLockFlag ifTrue: [^nil]. resourceObject := self findResourceToLock: obj. resourceLockEntry := self getResourceLockEntry: resourceObject. mode == #FS ifTrue: [successFlag := resourceLockEntrygetLock:modein:aTransaction by:self. successFlagifTrue:[currentRequestedSet add:resourceLockEntry] ifFalse: [cannotGrantLockFlag := true]. self getClassHierarchyLock: obj superClass with: #TSH in: aTransaction]. mode == #FX ifTrue: 89 [successFlag := resourceLockEntry getLock: mode in: aTransaction by: self. successFlagifTrue:[currentRequestedSet add:resourceLockEntry] ifFalse: [cannotGrantLockFlag := true]. self getClassHierarchyLock: obj superClass with: #TXH in: aTransaction]. mode == #TS ifTrue: [successFlag := resourceLockEntrygetLock:modein:aTransaction by:self. successFlagifTrue: [currentRequestedSet add: resourceLockEntry] ifFalse: [cannotGrantLockFlag := true]. self getClassHierarchyLock: obj superClass with: #TSH in: aTransaction]. mode == #TX ifTrue: [successFlag := resourceLockEntrygetLock: modein: aTransaction by: self. successFlagifTrue:[currentRequestedSet add:resourceLockEntry] ifFalse: [cannotGrantLockFlag := true]. self getClassHierarchyLock: obj superClass with: #TXH in: aTransaction]. mode == #FSN ifTrue:[successFlag := resourceLockEntrygetLock:modein:aTransaction by:self. successFlagifTrue:[currentRequestedSet add:resourceLockEntry] ifFalse: [cannotGrantLockFlag := true]. self getClassHierarchyLock: obj superClass with: #TSH in: aTransaction]. mode == #FXN ifTrue:[successFlag := resourceLockEntrygetLock:modein:aTransaction by:self. successFlagifTrue:[currentRequestedSet add:resourceLockEntry] ifFalse: [cannotGrantLockFlag := true]. self getClassHierarchyLock: obj superClass with: #TXH in: aTransaction] getCompositeClassLock: obj with: mode in: aTransaction getCompositeInstanceLock: obj with: mode in: aTransaction | resourceLockEntry successFlag resourceObject | obj isNil ifTrue: [^nil]. cannotGrantLockFlag ifTrue: [^nil]. resourceObject := self findResourceToLock: obj. resourceLockEntry := self getResourceLockEntry: resourceObject. mode == #FSO ifTrue:[successFlag := resourceLockEntrygetLock:modein:aTransaction by:self. successFlagifTrue: [currentRequestedSet add: resourceLockEntry] ifFalse: [cannotGrantLockFlag := true]. self getCompositeInstanceLock: obj parentPart with: #TSO in: aTransaction. self getClassLock: obj parentClass with: #TS in: aTransaction. obj partSet do: [:each | self getClassLock: each parentClass with: #TS in: aTransaction]]. mode == #FXO ifTrue:[successFlag := resourceLockEntrygetLock:modein:aTransaction by:self. successFlagifTrue:[currentRequestedSet add:resourceLockEntry] ifFalse: [cannotGrantLockFlag := true]. self getCompositeInstanceLock: obj parentPart 90 with: #TXO in: aTransaction. self getClassLock: obj parentClass with: #TX in: aTransaction. obj partSet do: [:each | self getClassLock: each parentClass with: #TX in: aTransaction]]. mode == #TSO ifTrue:[successFlag := resourceLockEntrygetLock:modein:aTransaction by:self. successFlagifTrue: [currentRequestedSet add: resourceLockEntry] ifFalse: [cannotGrantLockFlag := true]. self getCompositeInstanceLock: obj parentPart with: #TSO in: aTransaction]. mode == #TXO ifTrue:[successFlag := resourceLockEntrygetLock:modein:aTransaction by:self. successFlagifTrue:[currentRequestedSet add:resourceLockEntry] ifFalse: [cannotGrantLockFlag := true]. self getCompositeInstanceLock: obj parentPart with: #TXO in: aTransaction]. getInstanceLock: obj with: mode in: aTransaction | resourceLockEntry successFlag resourceObject | cannotGrantLockFlag ifTrue: [^nil]. resourceObject := self findResourceToLock: obj. resourceLockEntry := self getResourceLockEntry: resourceObject. mode == #FS ifTrue: [successFlag := resourceLockEntrygetLock:modein:aTransaction by:self. successFlagifTrue: [currentRequestedSet add: resourceLockEntry] ifFalse: [cannotGrantLockFlag := true]. self getClassLock: obj parentClass with: #TS in: aTransaction]. mode == #FX ifTrue: [successFlag := resourceLockEntrygetLock: modein: aTransaction by: self. successFlagifTrue:[currentRequestedSet add:resourceLockEntry] ifFalse: [cannotGrantLockFlag := true]. self getClassLock: obj parentClass with: #TX in: aTransaction] Protocol for private, locking findResourceToLock: obj | aNode | obj class == CC_AtomicInstance ifTrue: [aNode := self findInstanceNode: obj with: rootLGG]. obj class == CC_Class ifTrue: [aNode := self findClassNode: obj with: rootLGG]. ^aNode getLocksForResource: request in: aTransaction | obj | obj := request object. obj class == CC_AtomicInstance ifTrue: [| mode | request type == #O_READ ifTrue: [mode := #FS] ifFalse: [mode := #FX]. self getInstanceLock: obj with: mode in: aTransaction]. obj class == CC_Class ifTrue: 91 [| mode | request type == #O_READ ifTrue: [mode := #FS] ifFalse: [mode := #FX]. self getClassLock: obj with: mode in: aTransaction]. obj class == CC_CompositeInstance ifTrue: [| mode | request type == #O_READ ifTrue: [mode := #FSO] ifFalse: [mode := #FXO]. self getCompositeInstanceLock: obj with: mode in: aTransaction]. getResourceLockEntry: resourceObject | resourceLockEntry | resourceLockEntry := lockTable at: resourceObject resourceID ifAbsentPut: [CC_LockTableEntry new]. resourceLockEntry resourceObject: resourceObject. ^resourceLockEntry Protocol for private, LGN building buildClassHierarchyNodes: aNode with: aDatabaseNode | aClassNode aClassHierarchyNode aClass | aClass := aNode rootObject. aClass subClassSet do:[:eachClass | "Create a class node for each subclass." aClassNode := aDatabaseNode newClassNode: eachClass. "Create instance nodes and make them dependent on the class node." eachClass instanceSet do: [:anObject | | aInstanceNode | aInstanceNode := aDatabaseNode newInstanceNode: anObject. aClassNode addDependent: aInstanceNode]. "If there are subclasses for this class, create a class hierarchy node also." eachClass subClassSet isEmpty ifTrue: [aNode addDependent: aClassNode] ifFalse: [aClassHierarchyNode := aDatabaseNode newClassHierarchyNode: eachClass. aNode addDependent: aClassHierarchyNode. aClassHierarchyNode addDependent: aClassNode. self buildClassHierarchyNodes: aClassHierarchyNode with: aDatabaseNode.]] buildCompositeClassNodes: aDb with: aNode | compositeClassCollection | compositeClassCollection := aDb compositeClassSet. compositeClassCollection do: [:item | | aCollection rootCommonClass aCompositeNode classHierarchyNode | aCollection := Set new. aCollection add: item. aCollection addAll: item subPartSet. rootCommonClass := aCollection inject: item into: [:commonParentClass :next | self findCommonCoverClass: commonParentClass with: next]. classHierarchyNode := self findClassHierarchyNode: rootCommonClass with: rootLGG. aCompositeNode := rootLGG newCompositeClassNode: item with: aCollection. classHierarchyNode addDependent: aCompositeNode] buildCompositeInstanceNodes: aDb with: aNode | compositeInstanceCollection | compositeInstanceCollection := aDb compositeInstanceSet. compositeInstanceCollection do: [:item | | aCollection aCompositeInstanceNode compositeClassNode | aCollection := Set new. aCollection add: item. 92 aCollection addAll: item partSet. compositeClassNode := self findCompositeClassNode: item parentClass with: rootLGG. aCompositeInstanceNode := CC_LGN_CompositeInstance new: item with: aCollection. compositeClassNode addDependent: aCompositeInstanceNode. "Add instance nodes as dependents of the composite instance node." aCollection do: [:aInstance | | instanceNode | instanceNode := self findInstanceNode: aInstance with: rootLGG. aCompositeInstanceNode addDependent: instanceNode]] findClassHierarchyNode: aClass with: rootNode ^rootNode findClassHierarchyNode: aClass findClassNode: aClass with: rootNode ^rootNode findClassNode: aClass. findCommonCoverClass: class1 with: class2 ^class1 commonCoverClass: class2. findCompositeClassNode: aCompositeClass with: rootNode ^rootNode findCompositeClassNode: aCompositeClass findInstanceNode: anInstance with: rootNode ^rootNode findInstanceNode: anInstance. Protocol for printing printLockResourceGraph rootLGG printGraph Protocol for operation buildLockGranularityGraph: db "Build the lock granularity graph." | aClassNode aClassHierarchyNode | rootLGG := CC_LGN_Database new: db rootClass. "Create class hierarchy node for root class. Also create a class node for root class and make it a dependent of the class hierarchy node. Then create instance nodes and make them dependents of the class node." aClassHierarchyNode := rootLGG newClassHierarchyNode: db rootClass. rootLGG addDependent: aClassHierarchyNode. aClassNode := rootLGG newClassNode: db rootClass. aClassHierarchyNode addDependent: aClassNode. db rootClass instanceSet do: [:anObject | aClassNode addDependent: (rootLGG newInstanceNode: anObject)]. "Build the rest of class hierarchy, class, and instance nodes." self buildClassHierarchyNodes: aClassHierarchyNode with: rootLGG. "Build the composite class nodes." self buildCompositeClassNodes: db with: rootLGG. "Build the composite instance nodes." self buildCompositeInstanceNodes: db with: rootLGG. finalizeRequestFor: aTransaction currentRequestedSet do: [:each | each finalize] grantLocksForTransaction: aTransaction | accessRequest | 93 currentRequestedSet := Set new. cannotGrantLockFlag := false. accessRequest := aTransaction currentAccessRequest. "Find the resource object to lock first. Optimistic locking can be done within this." "We can either choose the smallest granular unit or the largest granular unit" self getLocksForResource: accessRequest in: aTransaction. cannotGrantLockFlag ifTrue: [^nil] ifFalse: [self finalizeRequestFor: aTransaction. ^true] releaseLocksForTransaction: aTransaction Protocol for initialize-release initialize lockTable := Dictionary new. compatibilityTable := IdentityDictionary new. self createCompatibilityTable. self createModeGraph CC_SimulationManager class name CC_SimulationManager superclass Object instance variable names class variable names AccessManager CCManager DatabaseManager PerformanceData P_DurationTransaction P_LockCPU P_LockIO P_MaxRunTime P_MaxTransactionsInRunning P_NumCPU P_NumIncomingTransactions P_NumIO P_NumTerminals P_ObjectCPU P_ObjectIO P_RatioCompositeRead P_RatioCompositeWrite P_RatioObjectWrite P_RatioSchemaChange P_RatioTransactionMix P_SizeObjectRead P_Stop S_AccessQueue S_BlockQueue S_CCQueue S_CompletedQueue S_EventQueue S_ReadyQueue TerminalManager Timer TransactionManager pool dictionaries category Conrad - Simulation, Simulation Manager CC_SimulationManager should have no instances. It is control center for the simulation. It also control the flow of the simulation. The simulation itself is a discrete event simulation. Various parameters of the simulation can also be set here with the exception of the parameters used for creating the test database. Class Variables: AccessManager description of AccessManager CCManager description of CCManager DatabaseManager description of DatabaseManager LockManager description of LockManager PerformanceData description of PerformanceData P_DurationTransaction description of P_DurationTransaction P_LockCPU description of P_LockCPU P_LockIO description of P_LockIO P_MaxRunTime description of P_MaxRunTime P_MaxTransactionsInRunning description of P_MaxTransactionsInRunning P_NumCPU description of P_NumCPU P_NumIncomingTransactions description of P_NumIncomingTransactions P_NumIO description of P_NumIO P_NumTerminals description of P_NumTerminals P_ObjectCPU description of P_ObjectCPU P_ObjectIO description of P_ObjectIO P_RatioCompositeRead description of P_RatioCompositeRead P_RatioCompositeWrite description of P_RatioCompositeWrite P_RatioObjectWrite description of P_RatioObjectWrite P_RatioSchemaChange description of P_RatioSchemaChange P_RatioTransactionMix description of P_RatioTransactionMix P_SizeObjectRead description of P_SizeObjectRead 94 P_Stop description of P_Stop S_AccessQueue description of S_AccessQueue S_BlockQueue description of S_BlockQueue S_CCQueue description of S_CCQueue S_CompletedQueue description of S_CompletedQueue S_EventQueue description of S_EventQueue S_ReadyQueue description of S_ReadyQueue TerminalManager description of TerminalManager Timer description of Timer TransactionManager description of TransactionManager Protocol for initialize-release dummy "This is needed for Code Printer to work. Code Printer needs a class to have some instance methods present." CC_SimulationManager class Protocol for run simulation run self initialize. self start. Protocol for printing printEndingResult CC_Debug print: 'Items in Ready Queue: ' ; print: S_ReadyQueue size; cr. CC_Debug print: 'Items in CC Queue: ' ; print: S_CCQueue size; cr. CC_Debug print: 'Items in Access Queue: ' ; print: S_AccessQueue size; cr. CC_Debug print: 'Items in Block Queue: ' ; print: S_BlockQueue size; cr. CC_Debug print: 'Items in Completed Queue: ' ; print: S_CompletedQueue size; cr. Protocol for operation currentTime ^Timer tick. start | dbManager | dbManager := CC_DatabaseManager new. dbManager generateDb. self start: dbManager withTerminals: (CC_TerminalManager new) withCC: (CC_CCManager new). start: aDatabaseManager withTerminals: aTerminalManager withCC: aCCManager DatabaseManager := aDatabaseManager. TerminalManager := aTerminalManager. CCManager := aCCManager. TerminalManager generateTransactions. DatabaseManager printClassHierarchy. CCManager buildLockGranularityGraph: DatabaseManager db. CCManager printLockResourceGraph. "Insert Initial events" CC_Debug show: 'START: insert initial events'. TerminalManager generateTransactionEvent. TransactionManager generateTransactionReadyEvent. CCManager generateCCRequestEvent. AccessManager generateAccessRequestEvent. CCManager generateBlockedTransactionReadyEvent. 95 "Event Loop" [Timer tick < P_MaxRunTime & (P_Stop = false)] whileTrue: [| eventSet | eventSet := S_EventQueue currentTimeEventSet: Timer tick. eventSet do: [:anEvent | anEvent perform]. Timer increment]. self printEndingResult. Protocol for initialize-release initialize CC_Debug initialize. self initializeAllSequenceNumbers. self initializeSimulationParameters. "Initialize internal data" Timer := CC_Timer new. S_CCQueue := CC_CCQueue new. S_ReadyQueue := CC_ReadyQueue new. S_BlockQueue := CC_BlockQueue new. S_AccessQueue := CC_AccessQueue new. S_EventQueue := CC_EventQueue new. S_CompletedQueue := CC_CompletedQueue new. TransactionManager := CC_TransactionManager new. AccessManager := CC_AccessManager new. PerformanceData := CC_SimulationPerformanceData new. initializeAllSequenceNumbers CC_Class id: 1. CC_AtomicInstance id: 1. CC_CompositeInstance id: 1. CC_LGN id: 1. initializeSimulationParameters "Experiment Parameters" P_Stop := false. P_MaxRunTime := 20. "Resource Usage Time" P_ObjectIO := 1. P_ObjectCPU := 1. P_LockIO := 1. P_LockCPU := 1. P_DurationTransaction := 2. "Resources" P_NumTerminals := 1. P_NumCPU := 1. P_NumIO := 1. P_MaxTransactionsInRunning := 2. P_NumIncomingTransactions := 5. "Transaction makeup" "Number of object read access in a single" P_SizeObjectRead := 5. "Ratio of object written out of all read object access" P_RatioObjectWrite := 0.2. "Ratio of composite object read access out of all read access in a single transaction" P_RatioCompositeRead := 0.2. "Ratio of composite object read access out of all read access in a single transaction" P_RatioCompositeWrite := 0.2. "Ratio of schema change transactions of all transactions" 96 P_RatioSchemaChange := 0.1. "Ratio of mix read and write transactions of all transactions" P_RatioTransactionMix := 0.2. Protocol for clean up clear DatabaseManager db clear. S_CCQueue := nil. S_ReadyQueue := nil. S_BlockQueue := nil. S_AccessQueue := nil. S_EventQueue := nil. S_CompletedQueue := nil. DatabaseManager := nil. CCManager := nil. TransactionManager := nil. AccessManager := nil. TerminalManager := nil. PerformanceData := nil. Timer := nil. Protocol for performance data lc_up PerformanceData lc: (PerformanceData lc + 1). lo_up PerformanceData lo: (PerformanceData lo + 1). CC_Transaction class name CC_Transaction superclass Object instance variable tid type lastModifiedTime accessSet currentAccessIndex lockList names class variable names pool dictionaries category Conrad - Simulation, Transaction Control Class CC_Transaction represents the database transactions in the simulation. Instance Variables: accessSet contains the list of access requests. currentAccessIndex indicates the current access request that is waiting to be processed. lastModifiedTime indicates the last modified virtual time. It is used for differentiating the next state and the previous state in the simulation. tid is the transaction id. type indicates the type of the transaction. Protocol for operation addAccess: aAccess accessSet add: aAccess addLocks: locks lockList addAll: locks. 97 currentAccessRequest ^accessSet at: currentAccessIndex. moveToNextAccess currentAccessIndex := currentAccessIndex + 1. Protocol for accessing accessSet ^accessSet accessSet: anObject accessSet := anObject currentAccessIndex ^currentAccessIndex currentAccessIndex: anObject currentAccessIndex := anObject lastModifiedTime ^lastModifiedTime lastModifiedTime: anObject lastModifiedTime := anObject tid ^tid tid: anObject tid := anObject type ^type type: anObject type := anObject Protocol for initialize-release initialize: id tid := id. currentAccessIndex := 1. accessSet := OrderedCollection new. lockList := OrderedCollection new. Protocol for printing printOn: aStream "Append to the argument aStream a sequence of characters that describes the receiver." aStream print: tid; space; print: type; space. CC_TransactionManager class name CC_TransactionManager superclass Object instance variable currentNumTransactions names class variable names pool dictionaries category Conrad - Simulation, Transaction Control 98 CC_TransactionManager is responsible for entering transactions into the system. Entering a transaction into the system means putting the transaction in the concurrency control queue. Since there is a maximum on the number of concurrent transactions in the system. Some incoming transactions might have to wait outside the system. Instance Variables: currentNumTransactions is the current number of transactions in the system. Protocol for initialize-release initialize currentNumTransactions := 0. Protocol for operation addTransaction: aTransaction "Add transaction to the concurrency control queue, and record the number of running transactions in the system" currentNumTransactions := currentNumTransactions + 1. CC_SimulationManager s_CCQueue enqueue: aTransaction. generateTransactionReadyEvent | time anEvent | time := CC_SimulationManager timer tick + 1. anEvent := CC_Event_TransactionReady new: time. CC_EventManager add: anEvent. removeTransaction: aTransaction "Put the completed transaction into the completed queue, and record the number of running transactions in the system" currentNumTransactions := currentNumTransactions - 1. CC_SimulationManager s_CompletedQueue enqueue: aTransaction. Protocol for accessing currentNumTransactions ^currentNumTransactions currentNumTransactions: anObject currentNumTransactions := anObject 99 Chapter 7 Experiments, Results and Analysis This chapter discusses the simulation experiments that were performed. Three different protocols were tested against the adaptive multi-granularity locking protocol. For each protocol, a set of experiments was performed. These experiments are discussed in the following sections and the simulation parameters for each experiment are listed. At the end of each experiment, performance statistics were collected and analyzed. The results are presented following each experiment. 7.1 Locking Protocols Several locking protocols are used in the simulations. They are designed to use various logical choices for different units of granular locking. Thus, they mainly differ from each other in terms of the granular units used for locking. Variations of some of these protocols are used in several research and commercial object-oriented database systems like ORION [2], Versant [14]. 7.1.1 Instance Granularity Locking This protocol uses instances as the unit of granularity. In this protocol, locks are set on instances being accessed. The maximum number of locks required by a database equals the total number of leaf granularity units or instances of classes. That is, if a read or write access is needed on an instance of a class, a firm read or firm write lock must be set on the instance. If a read access on all instances of a class is needed, a lock must be set on all its instances before access operations can begin. If a read access on all instances of a class hierarchy is needed, a lock must be obtained for all instances of the parent class and all instances of the subclasses. To change a class definition of a class C, an exclusive lock must be set on all instances belonging to class C and its subclasses. Locking a 100 composite object as a single unit is not supported. Locks must be obtained for the parent composite object and each component object. This protocol is relatively simple to implement. 7.1.2 Class Granularity Locking This protocol allows classes to be considered as granularity units. Instance objects can be locked with shared or exclusive locks similar to the instance granularity locking protocol. However, class objects may also be locked. Locking a class implicitly locks all its instances. In this protocol, when accessing a class hierarchy, a shared or exclusive lock is set not only on a class but also on each of its subclasses, explicitly. That is, if a read or write access is needed on a class and its subclasses, a traversal is performed on the class tree and locks must be set on each visited subclass. Once a lock is obtained for a granularity unit, the degree of granularity cannot be changed until the end of the transaction. For example, if a read lock were obtained for a class, the class lock would be released only by the end of the transaction. Locking a composite object as a single unit is not supported. Locks must be obtained for the parent composite object and each component object. In other words, all classes that have instances participating in the composite object are locked. 7.1.3 Multi-Granularity Locking In this protocol, locking a class or an instance is conducted in the same manner as in class granularity locking. Besides the various instance locks and class locks, class hierarchy locks are added to extend the locking granularity units to the class hierarchy level. Setting a lock on a class C is in essence an explicit lock on the class C, and implicit locks on all subclasses of the class C and its instances. Instances are all implicitly locked in each class in the class hierarchy. Since subclasses are implicitly locked in the hierarchy, superclasses of these subclasses must be notified of their locked status along all of the ancestor chains. Locking a composite object as a single unit is not supported. Locks must be obtained for the parent composite object and each component object. The locking mechanism is more complex than instance granularity locking and class granularity locking. However, it does reduce the locking overhead of a class hierarchy to a single lock in some cases. Once a lock is obtained for a class hierarchy, the degree of granularity cannot be changed until the end of the transaction. 101 7.1.4 Adaptive Multi-Granularity Locking In this protocol, instance, class, class-hierarchy locking are all supported similar to the multi-granularity locking. Locking a class or an instance is conducted in the same manner as in class granularity locking. Locking a class hierarchy is performed in the same manner as in multi-granularity locking. However, once a lock is obtained for any granularity unit, the degree of granularity can be adjusted during the transaction in an attempt to decrease the overall locking overhead and increase the degree of concurrency among transactions. The locking mechanism is complex compared to the other protocols. By setting various parameters, the protocol can be used to simulate the other protocols. For example, by limiting the granularity unit to the smallest granularity unit and disallowing the changing of the degree of granularity unit, this protocol would act like the instance granularity locking protocol. 7.2 Values of Simulation Parameters In all the experiments described in the following section, it is assumed that certain simulation parameters are constant throughout. These parameters include the number of CPU, terminal, and I/O resources. The I/O time and CPU time for each object access and lock usage is also fixed. Various database parameters are also fixed so that one database is used for all experiments. All these parameters are kept constant to eliminate excessive variance in the simulation. This focuses the experiments onto the areas that are of most concern, namely the effect of different granularity locking protocols, on the locking overhead of the database. Parameters Value NumMaxInstancePerClass 50 NumMinInstancePerClass 50 NumClassPerComposite 5 NumCompositeClass 10 NumCompositeInstance 500 NumSubClassPerClass 3 NumClassLevel 3 Table 7-1: Database Generation Parameters 102 Parameters Value Object / Lock Time Object IO 1 unit ObjectCPU 1 unit LockIO 0 unit LockCPU 1 unit Resource NumTerminals 1 unit NumCPU 1 unit NumIO 1 unit Transaction RatioSchemaChange 0.01 RatioTransactionMix 0.8 Table 7-2: Simulation Parameters that are constant 7.3 Experiments Four major groups of experiments were conducted. Experiment T1s tested different locking protocols against a set of transactions that only access instance objects. Experiment T2s tested different locking protocols against a set of transactions that only access class objects. Experiment T3s tested different locking protocols against a set of transactions that only access class hierarchy objects. Finally, Experiment T4s tested different locking protocols against a set of transactions that a mixture of different objects. The intention of the experiments is to show the effect of different locking protocols on the database when transactions access different type of objects. T1, T2, T3 are more extreme cases. T4 represents the ideal set of transactions where transactions can specify the level of granularity to be locked. It should be noted that this specification could be automatically generated by the database system or generated by user directives. However, automatic determination of the appropriate granularity level could be a challenging problem. 7.3.1 Description of Simulation Results The simulation result of each experiment is presented in two bar charts. The first bar chart shows the different statistics collected during each experiment for different locking protocols. The y-axis lists these protocols 103 and the statistics associated with each of them. The x-axis shows the value for these statistics. Table 7-3 lists the labels used in the chart and their corresponding metrics described in section 6.2.1. The second chart shows the lock ratio for each protocol. The lock ratio shows the number of objects that are covered by a single lock on average. It can be seen as a rough estimate on how well each protocol does in terms of lock overhead. LABEL METRIC Block Transaction Block Count Lock Escalation Lock Escalation Count Lock De-escalation Lock De-escalation Count Access Transaction Access Count Final LC Total Lock Count Aborted Getting Lock Attempt Aborted Lock Attempt Release LC Release Lock Count Demotion LA Demotion Lock Attempts Demotion LC Demotion Lock Count LA Lock Attempts LC Lock Count Table 7-3: Simulation Chart Legend Description 104 7.3.2 T1a: Object Access, Short Time, Small Workload Parameters Value MaxIncomingTransactions 5 MaxTransactionsInRunning 5 DurationTransaction 100 units MaxRunTime Infinite TotalObject 20 SimpleRead 0.8 SimpleRatioWrite 0.25 CompositeRead 0.2 CompositeRatioWrite 0.25 ClassRead 0 ClassRatioWrite 0 HierarchyRead 0 HierarchyRatioWrite 0 Table 7-4: T1a Simulation Parameters 7.3.2.1 Description In this simulation, each of the protocols is run with a set of transactions. The duration of each of these transactions is short. The transaction spends 100 units of time for processing all the objects read. In this case, the transaction spends 5 units of time (100 units / 20 objects) to process each object after this object is read from the database. When it is done processing, the transaction ends. The set of objects accessed is a relatively small set. The set contains both simple instance objects and composite instance objects. The whole simulation is run until completion, when all transactions have committed. 105 7.3.2.2 Result Lock Protocols SIMPLE Block Lock Escalation Lock Deescalation Access Final LC Aborted Getting Lock Attempt CLASS Release LC Demotion LA Demotion LC LA LC MGL AMGL 0 100 200 300 Count 400 500 600 700 Figure 7-1: Experiment T1a, part 1 106 Lock Protocols Lock Ratio SIMPLE CLASS MGL Lock Ratio AMGL 0 0.5 1 1.5 2 2.5 Ratio Figure 7-2: Experiment T1a, part 2 AMGL protocol performs the best in the experiment in terms of the lock ratio. MGL protocol performs the worst. SIMPLE protocol uses the same number of locks as the number of objects accessed, as expected. CLASS protocol reduces the lock count somewhat as multiple instances can be locked by a single class lock. The main reason for the MGL protocol's poor performance is due to the fact that larger granular locking units are not utilized since all accesses are instance object accesses. Yet, it has to pay the price of getting all the intention locks of every instance object. The AMGL protocol eliminates this weakness by automatically using the larger granular locking units. In addition, the relatively small number of objects accessed decreases the likelihood of lock conflicts. This benefits the inherently optimistic AMGL protocol. 7.3.3 T1b: Object Access, Short Time, Large Workload Parameters Value DurationTransaction 100 units TotalObject 200 Table 7-5: T1b Simulation Parameters 107 7.3.3.1 Description In this simulation, each of the protocols is run with a set of transactions. The duration of each of these transactions is short. The transaction spends 100 units of time for processing all the objects read. In this case, the transaction spends 0.5 unit of time (100 units / 200 objects) to process each object after this object is read from the database. When it is done processing, the transaction ends. The set of objects accessed is a relatively large set. The set contains both simple instance objects and composite instance objects. The whole simulation is run until completion when all transactions have committed. 7.3.3.2 Result Lock Protocols SIMPLE Block Lock Escalation Lock Deescalation Access Final LC Aborted Getting Lock Attempt CLASS Release LC Demotion LA Demotion LC LA LC MGL AMGL 0 10000 20000 30000 40000 50000 60000 Count Figure 7-3: Experiment T1b, part 1 108 Lock Protocols Lock Ratio SIMPLE CLASS MGL Lock Ratio AMGL 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 Ratio Figure 7-4: Experiment T1b, part 2 CLASS protocol performs the best in the experiment in terms of the lock ratio. MGL protocol performs the worst. SIMPLE protocol uses the same number of locks as the number of objects accessed, as expected. With a larger set of instance objects to access, CLASS protocol reduces the lock count significantly as multiple instances can be locked by a single class lock. The main reason for MGL protocol's poor performance is due to the fact that larger granular locking units are not utilized since all accesses are instance object accesses. AMGL also performs poorly as the larger set of objects accessed increases the likelihood of lock conflicts. Each time a lock conflict occurs, the lock de-escalation process will be executed. The de-escalation process releases all conflicting locks of other transactions that were obtained optimistically, since these conflicting locks are not real conflicts with the current lock request. The process then reacquires the locks required by these transactions at the most optimistic level, without conflicting with the current transaction. This process involves a number of locks being acquired and released. Thus, the total number of locks acquired is increased. 109 7.3.4 T1c: Object Access, Long Time, Small Workload Parameters Value DurationTransaction 1000 units TotalObject 20 Table 7-6: T1c Simulation Parameters 7.3.4.1 Description In this simulation, each of the protocols is run with a set of transactions. The duration of each of these transactions is long. The transaction spends 1000 units of time for processing all the objects read. In this case, the transaction spends 50 units of time (1000 units / 20 objects) to process each object after this object is read from the database. When it is done processing, the transaction ends. The set of objects accessed is a relatively small set. The set contains both simple instance objects and composite instance objects. The whole simulation is run until completion when all transactions have committed. 110 7.3.4.2 Result Lock Protocols SIMPLE Block Lock Escalation Lock Deescalation Access Final LC Aborted Getting Lock Attempt CLASS Release LC Demotion LA Demotion LC LA LC MGL AMGL Count 0 100 200 300 400 500 600 700 Figure 7-5: Experiment T1c, part 1 111 Lock Protocols Lock Ratio SIMPLE CLASS MGL Lock Ratio AMGL 0 0.5 1 1.5 2 2.5 Ratio Figure 7-6: Experiment T1c, part 2 AMGL protocol performs the best in the experiment. MGL protocol performs the worst. The outcome is similar to T1a. The longer transaction time does not seem to alter the outcome from T1a. 7.3.5 T1d: Object Access, Long Time, Large Workload Parameters Value DurationTransaction 1000 units TotalObject 200 Table 7-7: T1d Simulation Parameters 7.3.5.1 Description In this simulation, each of the protocols is run with a set of transactions. The duration of each of these transactions is long. The transaction spends 1000 units of time for processing all the objects read. In this case, the transaction spends 5 units of time (1000 units / 200 objects) to process each object after this object is read from the database. When it is done processing, the transaction ends. The set of objects accessed is a relatively large set. The set contains both simple instance objects and composite instance objects. The whole simulation is run until completion when all transactions have committed. 112 7.3.5.2 Result Lock Protocols SIMPLE Block Lock Escalation Lock Deescalation Access Final LC Aborted Getting Lock Attempt CLASS Release LC Demotion LA Demotion LC LA LC MGL AMGL Count 0 10000 20000 30000 40000 50000 60000 70000 80000 90000 Figure 7-7: Experiment T1d, part 1 113 Lock Protocols Lock Ratio SIMPLE CLASS MGL Lock Ratio AMGL 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 Ratio Figure 7-8: Experiment T1d, part 2 CLASS protocol performs the best in the experiment. AMGL protocol performs the worst. The outcome is similar to T1b. The longer transaction time and larger transaction workload does not seem to alter the outcome from T1b. 114 7.3.6 T2a: Class Access, Short Time, Small Workload Parameters Value MaxIncomingTransactions 5 MaxTransactionsInRunning 5 DurationTransaction 100 units MaxRunTime Infinite TotalObject 20 * 0.2 (maximum 4) SimpleRead 0 SimpleRatioWrite 0 CompositeRead 0 CompositeRatioWrite 0 ClassRead 1 ClassRatioWrite 0.25 HierarchyRead 0 HierarchyRatioWrite 0 Table 7-8: T2a Simulation Parameters 7.3.6.1 Description In this simulation, each of the protocols is run with a set of transactions. The duration of each of these transactions is short. The transaction spends 100 units of time for processing all the objects after they have been read from the database. When it is done processing, the transaction ends. The set of objects accessed is a relatively small set. The set contains only class instance objects. The whole simulation is run until completion when all transactions have committed. 115 7.3.6.2 Result Lock Protocols SIMPLE Block Lock Escalation Lock Deescalation Access Final LC Aborted Getting Lock Attempt CLASS Release LC Demotion LA Demotion LC LA LC MGL AMGL 0 500 1000 1500 2000 2500 3000 3500 Count Figure 7-9: Experiment T2a, part 1 116 Lock Protocols Lock Ratio SIMPLE CLASS MGL Lock Ratio AMGL 0 0.2 0.4 0.6 0.8 1 1.2 1.4 Ratio Figure 7-10: Experiment T2a, part 2 AMGL protocol performs the best in the experiment. SIMPLE protocol performs the worst. SIMPLE protocol has to lock every instance of the class accessed. This requires a significant number of locks. CLASS protocol performs quite well as expected. The locking granularity of the CLASS protocol corresponds exactly to the granular object being accessed. MGL protocol performs less well than CLASS protocol because of the overhead of getting all the intention locks of every class object lock. AMGL protocol eliminates this weakness by automatically using the larger granular locking units. In addition, the relatively small number of objects accessed decreases the likelihood of lock conflicts. This benefits the inherently optimistic AMGL protocol. 7.3.7 T2b: Class Access, Short Time, Large Workload Parameters Value DurationTransaction 100 units TotalObject 200 * 0.2 (maximum 20) Table 7-9: T2b Simulation Parameters 117 7.3.7.1 Description In this simulation, each of the protocols is run with a set of transactions. The duration of each of these transactions is short. The transaction spends 100 units of time for processing all the objects after they have been read from the database. When it is done processing, the transaction ends. The set of objects accessed is a relatively large set. The set contains only class instance objects. The whole simulation is run until completion when all transactions have committed. 7.3.7.2 Result Lock Protocols SIMPLE Block Lock Escalation Lock Deescalation Access Final LC Aborted Getting Lock Attempt CLASS Release LC Demotion LA Demotion LC LA LC MGL AMGL 0 1000 2000 3000 4000 5000 6000 7000 8000 Count Figure 7-11: Experiment T2b, part 1 118 Lock Protocols Lock Ratio SIMPLE CLASS MGL Lock Ratio AMGL 0 0.5 1 1.5 2 2.5 3 Ratio Figure 7-12: Experiment T2b, part 2 AMGL protocol performs the best in the experiment. SIMPLE protocol performs the worst. The outcome is similar to T2a. However, the larger transaction workload presents an even bigger challenge to the SIMPLE protocol, as many more instance objects need to be locked. 7.3.8 T2c: Class Access, Long Time, Small Workload Parameters Value DurationTransaction 1000 units TotalObject 20 * 0.2 (maximum 4) Table 7-10: T2c Simulation Parameters 7.3.8.1 Description In this simulation, each of the protocols is run with a set of transactions. The duration of each of these transactions is long. The transaction spends 1000 units of time for processing all the objects after they have been read from the database. The set of objects accessed is a relatively large set. The set contains only class instance objects. The whole simulation is run until completion when all transactions have committed. 119 7.3.8.2 Result Lock Protocols SIMPLE Block Lock Escalation Lock Deescalation Access Final LC Aborted Getting Lock Attempt CLASS Release LC Demotion LA Demotion LC LA LC MGL AMGL 0 500 1000 1500 2000 2500 3000 3500 Count Figure 7-13: Experiment T2c, part 1 120 Lock Protocols Lock Ratio SIMPLE CLASS MGL Lock Ratio AMGL 0 0.2 0.4 0.6 0.8 1 1.2 1.4 Ratio Figure 7-14: Experiment T2c, part 2 AMGL protocol performs the best in the experiment. SIMPLE protocol performs the worst. The outcome is similar to T2a. The longer transaction time does not seem to alter the outcome from T2a. Although longer transaction time does not seem to alter the comparative performance of the locking protocols from T2a, it is expected in general that longer transaction time will likely result in more overlaping transactions running at the same time. This will increase the likelihood for lock conflicts among transactions. Therefore, protocols that can handle lock conflicts well will perform better and use fewer locks in longer transactions. This translates into less lock counts for these protocols. 7.3.9 T2d: Class Access, Long Time, Large Workload Parameters Value DurationTransaction 1000 units TotalObject 200 * 0.2 (maximum 20) Table 7-11: T2d Simulation Parameters 121 7.3.9.1 Description In this simulation, each of the protocols is run with a set of transactions. The duration of each of these transactions is long. The transaction spends 1000 units of time for processing all the objects after they have been read from the database. When it is done processing, the transaction ends. The set of objects accessed is a relatively large set. The set contains only class instance objects. The whole simulation is run until completion when all transactions have committed. 7.3.9.2 Result Lock Protocols SIMPLE Block Lock Escalation Lock Deescalation Access Final LC Aborted Getting Lock Attempt CLASS Release LC Demotion LA Demotion LC LA LC MGL AMGL 0 1000 2000 3000 4000 5000 6000 7000 8000 Count Figure 7-15: Experiment T2d, part 1 122 Lock Protocols Lock Ratio SIMPLE CLASS MGL Lock Ratio AMGL 0 0.5 1 1.5 2 2.5 3 Ratio Figure 7-16: Experiment T2d, part 2 AMGL protocol performs the best in the experiment. SIMPLE protocol performs the worst. The outcome is similar to T2a. The longer transaction time and larger transaction workload does not seem to alter the outcome from T2a. 123 7.3.10 T3a: Hierarchy Access, Short Time, Small Workload Parameters Value MaxIncomingTransactions 5 MaxTransactionsInRunning 5 DurationTransaction 100 units MaxRunTime Infinite TotalObject 20 * 0.05 (maximum 1) SimpleRead 0 SimpleRatioWrite 0 CompositeRead 0 CompositeRatioWrite 0 ClassRead 0 ClassRatioWrite 0 HierarchyRead 1 HierarchyRatioWrite 0.25 Table 7-12: T3a Simulation Parameters 7.3.10.1 Description In this simulation, each of the protocols is run with a set of transactions that access only class hierarchy objects. The duration of each of these transactions is short. The transaction spends 100 units of time for processing all the objects after they have been read from the database. When it is done processing, the transaction ends. The set of objects accessed is a relatively small set. The whole simulation is run until completion when all transactions have committed. 124 7.3.10.2 Result Lock Protocols SIMPLE Block Lock Escalation Lock Deescalation Access Final LC Aborted Getting Lock Attempt CLASS Release LC Demotion LA Demotion LC LA LC MGL AMGL 0 100 200 300 400 500 600 Count Figure 7-17: Experiment T3a, part 1 125 Lock Protocols Lock Ratio SIMPLE CLASS MGL Lock Ratio AMGL 0 0.2 0.4 0.6 0.8 1 1.2 Ratio Figure 7-18: Experiment T3a, part 2 AMGL protocol and CLASS protocol perform the best in the experiment. The reason for the poor performance of the SIMPLE protocol is similar to T2a. SIMPLE protocol has to lock every instances of the class hierarchy accessed. This requires a significant number of locks. CLASS protocol locks each class in the class hierarchy. Since AMGL and CLASS perform equally well in this experiment, it seems to suggest that the overhead of obtaining soft locks for AMGL compares roughly to the overhead of obtaining multiple class objects locks for each class hierarchy. However, the fact that the MGL does not perform as well as CLASS also suggests that the overhead of obtaining soft locks by itself without optimistic lock escalation is greater than the overhead of the CLASS protocol. 7.3.11 T3b: Hierarchy Access, Short Time, Large Workload Parameters Value DurationTransaction 100 units TotalObject 200 * 0.05 (maximum 10) Table 7-13: T3b Simulation Parameters 126 7.3.11.1 Description In this simulation, each of the protocols is run with a set of transactions. The duration of each of these transactions is short. The transaction spends 100 units of time for processing all the objects after they have been read from the database. The set of objects accessed is a relatively large set. The set contains only class hierarchy objects. The whole simulation is run until completion when all transactions have committed. 7.3.11.2 Result Lock Protocols SIMPLE Block Lock Escalation Lock Deescalation Access Final LC Aborted Getting Lock Attempt CLASS Release LC Demotion LA Demotion LC LA LC MGL AMGL Count 0 200 400 600 800 1000 1200 1400 1600 1800 2000 Figure 7-19: Experiment T3b, part 1 127 Lock Protocols Lock Ratio SIMPLE CLASS MGL Lock Ratio AMGL 0 0.5 1 1.5 2 2.5 3 3.5 Ratio Figure 7-20: Experiment T3b, part 2 AMGL protocol performs the best in the experiment. SIMPLE protocol performs the worst. The outcome is similar to T3a. However, the larger transaction workload increases the number of class locks needed by the CLASS protocol. The same workload, however, does not increase the overhead of obtaining soft locks for AMGL protocols. It suggests that, as the workload increases, the lock overhead for the CLASS protocol will increasingly exceed that of the AMGL protocol. 7.3.12 T3c: Hierarchy Access, Long Time, Small Workload Parameters Value DurationTransaction 1000 units TotalObject 20 * 0.05 (maximum 1) Table 7-14: T3c Simulation Parameters 7.3.12.1 Description In this simulation, each of the protocols is run with a set of transactions. The duration of each of these transactions is long. The transaction spends 1000 units of time for processing all the objects after they have been read from the database. The set of objects accessed is a relatively small set. The set contains only class hierarchy objects. The whole simulation is run until completion when all transactions have committed. 128 7.3.12.2 Result Lock Protocols SIMPLE Block Lock Escalation Lock Deescalation Access Final LC Aborted Getting Lock Attempt CLASS Release LC Demotion LA Demotion LC LA LC MGL AMGL 0 50 100 150 200 250 300 350 400 450 500 Count Figure 7-21: Experiment T3c, part 1 129 Lock Protocols Lock Ratio SIMPLE CLASS MGL Lock Ratio AMGL 0 0.2 0.4 0.6 0.8 1 1.2 Ratio Figure 7-22: Experiment T3c, part 2 AMGL protocol and CLASS protocol perform the best. SIMPLE protocol performs the worst. The outcome is similar to T3a. The long transaction time does not seem to affect the outcome. 7.3.13 T3d: Hierarchy Access, Long Time, Large Workload Parameters Value DurationTransaction 1000 units TotalObject 200 * 0.05 (maximum 10) Table 7-15: T3d Simulation Parameters 7.3.13.1 Description In this simulation, each of the protocols is run with a set of transactions. The duration of each of these transactions is long. The transaction spends 1000 units of time for processing all the objects after they have been read from the database. The set of objects accessed is a relatively large set. The set contains only class hierarchy objects. The whole simulation is run until completion when all transactions have committed. 130 7.3.13.2 Result Lock Protocols SIMPLE Block Lock Escalation Lock Deescalation Access Final LC Aborted Getting Lock Attempt CLASS Release LC Demotion LA Demotion LC LA LC MGL AMGL 0 2000 4000 6000 8000 10000 12000 Count Figure 7-23: Experiment T3d, part 1 131 Lock Protocols Lock Ratio SIMPLE CLASS MGL Lock Ratio AMGL 0 0.5 1 1.5 2 2.5 3 3.5 Ratio Figure 7-24: Experiment T3d, part 2 AMGL protocol performs the best. SIMPLE protocol performs the worst. The outcome is similar to T3b. However, the performance of the CLASS protocol and that of the MGL protocol are reversed. In this experiment, the MGL protocol performs better. Although the difference is not statistically significant, it might suggest that as the transaction workload increases, the overhead in the CLASS protocol increases faster than that of the MGL protocol. As a transaction accesses more class hierarchies, the CLASS protocol will need to lock each of the subclasses of these class hierarchies. On the other hand, the MGL protocol only needs to obtain the same number of locks as the number of class hierarhies accessed by the transaction. Although the MGL also needs to obtain intention locks for each class hierarchies, it would requires fewer number of intentions locks than the number of locks required for the subclasses in general. Therefore, as workload increases, it is likely that the MGL protocol will perform better than the CLASS protocol. 132 7.3.14 T4a: Mixed Access, Short Time, Small Workload Parameters Value MaxIncomingTransactions 5 MaxTransactionsInRunning 5 DurationTransaction 100 units MaxRunTime Infinite TotalObject 20 SimpleRead 0.725 SimpleRatioWrite 0.25 CompositeRead 0.2 CompositeRatioWrite 0.25 ClassRead 0.05 ClassRatioWrite 0.25 HierarchyRead 0.025 HierarchyRatioWrite 0.25 Table 7-16: T4a Simulation Parameters 7.3.14.1 Description In this simulation, each of the protocols is run with a set of transactions. The duration of each of these transactions is short, thus spends a small amount of time processing objects accessed. When it is done processing, the transaction ends. The set of objects accessed is a relatively small set. The set contains a mixture of objects including simple instance objects, composite instance object, class instance objects, and class hierarchy objects. The whole simulation is run until completion when all transactions have committed. 133 7.3.14.2 Result Lock Protocols SIMPLE Block Lock Escalation Lock Deescalation Access Final LC Aborted Getting Lock Attempt CLASS Release LC Demotion LA Demotion LC LA LC MGL AMGL 0 100 200 300 400 500 600 700 Count Figure 7-25: Experiment T4a, part 1 134 Lock Protocols Lock Ratio SIMPLE CLASS MGL Lock Ratio AMGL 0 0.5 1 1.5 2 2.5 Ratio Figure 7-26: Experiment T4a, part 2 AMGL protocol performs the best in the experiment in terms of Lock Ratio. SIMPLE protocol performs the worst. SIMPLE protocol has to lock every instance of every class and class hierarchy accessed. This requires a significant number of locks. CLASS protocol locks each classes in the class hierarchy. The fact that the MGL does not perform as well as CLASS also suggests that the overhead of obtaining soft locks by itself without optimistic lock escalation is greater than the overhead of the CLASS protocol. The overhead of the MGL protocol mainly lies in the process of obtaining intention locks for the locks acquired. The overhead of the CLASS protocol increases when the object being locked is not a class object. If it is a class hierarchy, the CLASS protocol will have to lock every class in the hierarchy. This experiment suggests that although the CLASS protocol requires more locks when it is dealing with a granular unit larger than a class. It will still require fewer locks than the MGL protocol in a mixed access load. 135 7.3.15 T4b: Mixed Access, Short Time, Large Workload Parameters Value DurationTransaction 100 units TotalObject 200 Table 7-17: T4b Simulation Parameters 7.3.15.1 Description In this simulation, each of the protocols is run with a set of transactions. The duration of each of these transactions is short. The transaction spends 100 units of time for processing all the objects after they have been read from the database. The set of objects accessed is a relatively large set. The set contains a mixture of objects including simple instance objects, composite instance object, class instance objects, and class hierarchy objects. The whole simulation is run until completion when all transactions have committed. 136 7.3.15.2 Result Lock Protocols SIMPLE Block Lock Escalation Lock Deescalation Access Final LC Aborted Getting Lock Attempt CLASS Release LC Demotion LA Demotion LC LA LC MGL AMGL 0 10000 20000 30000 40000 50000 60000 70000 Count Figure 7-27: Experiment T4b, part 1 137 Lock Protocols Lock Ratio SIMPLE CLASS MGL Lock Ratio AMGL 0 0.5 1 1.5 2 2.5 3 3.5 4 Ratio Figure 7-28: Experiment T4b, part 2 CLASS protocol performs the best in the experiment. SIMPLE protocol performs the worst. SIMPLE protocol uses the same number of locks as the number of objects accessed, as expected. With a larger set of instance objects to access, CLASS protocol reduces the lock count significantly as multiple instances can be locked by a single class lock. The overhead of obtaining soft locks for these instance objects in MGL protocol contributes to its poor performance. AMGL also performs poorly as the larger set of objects accessed increases the likelihood of lock conflicts. Each time a lock conflict occurs, a number of locks have to be acquired and released. Thus, the total number of locks acquired is increased. 7.3.16 T4c: Mixed Access, Long Time, Small Workload Parameters Value DurationTransaction 1000 units TotalObject 20 Table 7-18: T4c Simulation Parameters 138 7.3.16.1 Description In this simulation, each of the protocols is run with a set of transactions. The duration of each of these transactions is long. The transaction spends 1000 units of time for processing all the objects after they have been read from the database. The set of objects accessed is a relatively small set. The set contains a mixture of objects including simple instance objects, composite instance object, class instance objects, and class hierarchy objects. The whole simulation is run until completion when all transactions have committed. 7.3.16.2 Result Lock Protocols SIMPLE Block Lock Escalation Lock Deescalation Access Final LC Aborted Getting Lock Attempt CLASS Release LC Demotion LA Demotion LC LA LC MGL AMGL 0 100 200 300 400 500 600 700 Count Figure 7-29: Experiment T4c, part 1 139 Lock Protocols Lock Ratio SIMPLE CLASS MGL Lock Ratio AMGL 0 0.5 1 1.5 2 2.5 Ratio Figure 7-30: Experiment T4c, part 2 In this experiment, AMGL protocol performs the best. SIMPLE protocol performs the worst. The outcome is similar to T4a. The longer transaction time seems to have no effect on the outcome. 7.3.17 T4d: Mixed Access, Long Time, Large Workload Parameters Value DurationTransaction 1000 units TotalObject 200 Table 7-19: T4d Simulation Parameters 7.3.17.1 Description In this simulation, each of the protocols is run with a set of transactions. The duration of each of these transactions is long. The transaction spends 1000 units of time for processing all the objects after they have been read from the database. The set of objects accessed is a relatively large set. The set contains a mixture of objects including simple instance objects, composite instance object, class instance objects, and class hierarchy objects. The whole simulation is run until completion when all transactions have committed. 140 7.3.17.2 Result Lock Protocols SIMPLE Block Lock Escalation Lock Deescalation Access Final LC Aborted Getting Lock Attempt CLASS Release LC Demotion LA Demotion LC LA LC MGL AMGL 0 100 200 300 400 500 600 700 Count Figure 7-31: Experiment T4d, part 1 141 Lock Protocols Lock Ratio SIMPLE CLASS MGL Lock Ratio AMGL 0 0.5 1 1.5 2 2.5 Ratio Figure 7-32: Experiment T4d, part 2 In this experiment, AMGL protocol performs the best. SIMPLE protocol performs the worst. The outcome is similar to T4a. 7.4 Experiment Summary In Table 7-20, the best and the worst protocol in terms of Lock Ratio for each experiment are listed. Several observations can be made from this table. First, SIMPLE protocol is undesirable as a locking protocol in most cases. It simply requires too much locking overhead. MGL protocol also does not perform well in most cases. It often comes in as the second worst protocol after the SIMPLE protocol. The fact that most transactions will not be able to specify the appropriate granularity objects for locking precisely makes it hard for the MGL protocol to perform at its best. If one desires to use a multiple granularity locking protocol, AMGL should be the more desirable choice. It allows for automatic adjustment of granularity objects for locking. Thus, it eliminates one of the major weaknesses of the MGL protocol. Overall, the best locking protocols seem to be either the AMGL or CLASS protocol, with a slight edge to the AMGL protocol. CLASS protocol performs quite well when the transaction workload is large, not 142 as well with small transaction workload. AMGL, however, seems to perform quite well both with small and large transaction workloads. Experiment Best Worst T1a: Object Access, Short Time, Small Workload AMGL MGL T1b: Object Access, Short Time, Large Workload CLASS MGL T1c: Object Access, Long Time, Small Workload AMGL MGL T1d: Object Access, Long Time, Large Workload CLASS AMGL T2a: Class Access, Short Time, Small Workload AMGL SIMPLE T2b: Class Access, Short Time, Large Workload AMGL SIMPLE T2c: Class Access, Long Time, Small Workload AMGL SIMPLE T2d: Class Access, Long Time, Large Workload AMGL SIMPLE T3a: Hierarchy Access, Short Time, Small Workload AMGL, SIMPLE CLASS T3b: Hierarchy Access, Short Time, Large Workload AMGL SIMPLE T3c: Hierarchy Access, Long Time, Small Workload AMGL, SIMPLE CLASS T3d: Hierarchy Access, Long Time, Large Workload AMGL SIMPLE T4a: Mixed Access, Short Time, Small Workload AMGL SIMPLE T4b: Mixed Access, Short Time, Large Workload CLASS SIMPLE T4c: Mixed Access, Long Time, Small Workload AMGL SIMPLE T4d: Mixed Access, Long Time, Large Workload AMGL SIMPLE Table 7-20: Best and Worst of Each Experiment 143 Chapter 8 Conclusion and Future Work 8.1 Conclusion In the preceding chapters, we have presented a concurrency control protocol for object-oriented databases that is adaptive to the transaction requirements and requires significantly less overhead in many situations compared to conventional locking protocols. This chapter summarizes this work, highlights the contributions and sketches out ways in which it might be extended with further research efforts. We presented the underlying assumptions about the system model upon which our adaptive multi- granularity locking protocol was built in chapter 4. We considered the data model, transaction model, and the concurrency control model. The data model describes the underlying object-oriented database model. Some of the basic types of data include classes, instance objects, and class definitions. Some of the basic relationships include ISA and PART OF relationships. Relationships like associations among objects in object-oriented databases are not modeled in the data model, as they do not have a direct impact on the granularity units of the locking protocols. The transaction model assumes a traditional transaction model consisting of read and write accesses as defined by Bernstein [4]. The proposed concurrency control model makes use of the concept of serializability for providing a consistency guarantee with the augmentation of several types of semantic information gathered from the databases. This semantic information, however, is common to all object-oriented databases. No application specific information is needed by the concurrency control protocols. Thus, they can be employed in any object-oriented databases. 144 In chapter 5, an adaptive multi-granularity locking protocol was introduced. The chapter describes the possible granularity units for locking in traditional relational databases and in object-oriented databases. In object- oriented databases, there are three possible dimensions one can use to determine the possible granularity units. They are the class inheritance dimension, class instance dimension, and object composition dimension. Once a set of granularity units is determined, several types of locks can be applied to each of them. These locks can be grouped into two main categories. First, they can either be soft locks or firm locks. A soft lock is similar to an intention lock, except that it also keeps track of information about underlying objects covered by the lock. This information is used in the lock escalation and de-escalation process. It also serves as a notice to all ancestor objects that the object is locked. A firm lock is like a regular lock except that lock escalation and de-escalation can be performed on it. In addition, a lock on an object can be either an explicit lock or an implicit lock. An explicit lock is a lock that is requested by a transaction directly. An implicit lock is a lock derived from explicit locks. The adaptive multi- granularity locking protocol consists of three components. First, eighteen different lock modes are presented corresponding to the different types of granularity units existing in the database and properties of these units. Secondly, a lock compatibility matrix for these lock modes is shown. The compatibility matrix allows one to determine whether a lock mode is compatible, or can be obtained concurrently, with another lock mode. The third component of the adaptive multi-granularity protocol is a set of rules concerning which of these lock modes should be used, and how they should be obtained by a certain database locking operation. The rules are divided into two groups. One group deals with the rules on how to get locks for class-related objects such as classes, class inheritance hierarchies, and class definitions. The second group deals with how to get locks for instance-related objects such as object instances, and composite object instances. A formal definition of the lock granularity graph is given for the locking protocol to illustrate how the lock resource graph is constructed. The correctness proof for the locking protocol is also given to ensure that the protocol follows the theory of serializability and is consistent. Finally, formal definitions of the lock escalation and de-escalation process are shown. These definitions are incorporated into the rules for locking objects, resulting in the final set of rules for the adaptive granularity locking protocol. The simulation performed in this thesis is described in chapter 6. The simulation model consists of the database system model, user model, and transaction model. The database system model describes the database structure including number of classes, number of instances per class, and others. The transaction model describes the 145 transaction structures and properties used in the simulation. These properties include the incoming rate of transactions, transaction contents, resource usage and locking overhead, and others. In chapter 7, we describe our experiments and results. We performed a series of experiments on four different locking protocols. They are instance locking, class locking, multi-granularity locking, and our adaptive multi-granularity locking. What we observed from the experiments is that the adaptive multi-granularity locking protocol performs well in both high lock conflict and low lock conflict situations compared to other types of locking protocols. It is the best choice for situations where lock conflicts are not high. In situations where lock conflicts are high, it performs close to the class locking protocol, which is the best choice. We also observed that it is in general a bad choice to have a locking protocol based on only object instance granularity units. Although multi-granularity locking protocol seems like a good choice intuitively, it performs not as well as class protocol in most cases, unless the appropriate granular units can be supplied by the applications. In an environment where this is not possible, it is best to avoid a multi-granularity locking protocol and opt for a simpler protocol, like the class locking protocol. However, the usefulness of multi-granularity shines through with the addition of lock escalation and de-escalation. This modified version of the multi-granularity locking protocol, which we call the adaptive multi-granularity protocol, becomes the best choice among all locking protocols tested. In sum, the main contribution of our work is the identification of potential significant reductions in lock overhead with the use of locking protocol with the ability to use different lock granularity units dynamically at run time. With lock escalation and lock de-escalation, the adaptive multi-granularity locking protocol is able to reduce lock overhead significantly. We have presented a detailed design and architecture of an adaptive multi-granularity locking protocol that has proven its feasibility in our simulation. Its correctness is also shown in our formal proof. In addition, we formalized the notion of lock escalation and de-escalation in object-oriented databases, and we have shown how this notion can be incorporated in our locking protocol. Finally, we also implemented a simulation program to quantify the performance of this protocol compared to other types of locking protocol in different transaction mixes. Several issues are worth discussing further. First, we have shown that the AMGL protocol works well in most situations from the simulation experiments. However, it does not perform as well as CLASS protocol in situations when there is a high level of conflicts. In almost all cases, MGL and SIMPLE protocols perform poorly. It should be noted that variations of these two protocols are used in many research and commercial object-oriented 146 database systems. This suggests that there is a significant opportunity to improve on the performance of the concurrency control protocol in current object-oriented database systems by simply changing the protocols. The decision between using the AMGL protocol or the CLASS protocol depends on the level of conflicts and the transaction access patterns. AMGL protocol is suitable for applications where conflicts are not extremely high and the transaction accesses include higher granularity units like class hierarchies or a mixture of higher granularity units and lower granularity units. CLASS protocol might be more suitable if conflicts are high and the transaction accesses include only object instances. Second, the schema of the database used in the simulation is setup to be uniform. If the schema of database were non-uniform, the performance of the tested protocols would be affected. For example, a schema that contains deeper class hierarchies would decrease the performance of the multi-granularity locking protocol since that would increase the number of intention locks needed for locking instances on average. It would have some effect on the adaptive multi-granularity locking protocol for the same reason. However, the effect would be a lot smaller because of the optimistic nature of the protocol. The protocol would not need to acquire all these intentions locks as the largest granularity unit is locked first in most cases. Overall, the relative performance of the four tested protocols in the simulation should not change. Nevertheless, a more irregular schema may increase or sharpen the performance differences among protocols. Finally, the performance metric used in the simulation mainly deals with locking overhead in terms of the number of locks required by each transaction. However, there are other kinds of performance metrics like transaction response time. Response time is not measured in the experiments, as it requires accurate estimation of instruction count of various protocols that is in many ways implementation dependent. 8.2 Future Work The work described in this thesis deals with the concurrency control issues in object-oriented database systems. Concurrency control issues are quite well investigated in relational databases, but remain a relatively unexplored area of research in object-oriented databases. This section will discuss some of the opportunities for further research related to this thesis. The proposed protocol uses serializability as the consistency guarantee. Serializability is a too restrictive criterion for transactions in many applications. It prevents a transaction from seeing the intermediate results of another transaction. In many applications, this is not necessary or desirable. The additional semantics in object- 147 oriented databases may be used to express more flexible correctness criteria than serializability. How to use other types of correctness criteria in a locking protocol that employs lock escalation and de-escalation is an interesting area to explore. Versions are often used in object-oriented database system. For instances, they are used frequently in design environments. Objects related by being part of a particular version represent a type of relationship in the object database. This type of relationship is not modeled in the proposed locking protocol. How to incorporate this information in the protocol will be an interesting issue to investigate. This also extends to the general question of how one would incorporate the rich semantics of object-oriented databases into the locking protocol. The proposed protocol only uses a small portion of this information. There is a good reason for this choice, namely that this portion of information exists in all object-oriented databases and thus is not application specific. Nevertheless, it might be useful in some applications for the locking protocol to make use of the additional semantics stored in the database to achieve greater performance. The issue of how to incorporate this information with lock escalation and de-escalation is a challenging problem. In addition to semantics stored in the database, the semantics employed by transactions may also be used to enhance concurrency further. For example, if we know that a transaction only reads objects, the locking protocol may be able to reduce overhead for managing accesses for this transaction. Finally, the smallest granularity unit in the proposed protocol is the object instance. However, there are other finer grained granularity units. For instance, an object method or an object attribute could also be treated as a granularity unit. Employing these units in a locking protocol may increase the degree of concurrency. However, the tradeoff is that there are more objects to keep track of in the protocol. The questions of whether using a finer granularity unit increases performance should be investigated further. 148 REFERENCES [1] Cattell, R.G.G., Object Data Management: Object-Oriented and Extended Relational Database Systems. 1991: Addison-Wesley Publishing Company. [2] Kim, W., Introduction to object-oriented databases. Computer systems. 1990, Cambridge, Mass.: MIT Press. 234. [3] Kim, W. and F.H. Lochovsky, Object-oriented concepts, databases and applications. Frontier series. 1989, New York, N.Y. Reading, Mass.: ACM Press; Addison-Wesley. 602. [4] Bernstein, P.A., V. Hadzilacos, and N. Goodman, Concurrency control and recovery in database systems. Addison-Wesley series in computer science. 1987, Reading, Mass.: Addison-Wesley Pub. Co. 370. [5] Barghouti, N.S. and G.E. Kaiser, Concurrency Control in Advanced Database Applications. Computing Surveys, 1991: p. 269-317. [6] Olsen, D.H. and S. Ram, Towards a Comprehensive Concurrency Control Mechanism for Object- Oriented Databases. Journal of Database Management, 1995. 6(4): p. 24-34. [7] Chang, C. and B. Schatz. Performance and Implications of Semantic Indexing in a Distributed Environment. in Eighth International Conference on Information and Knowledge Management (CIKM). 1999. Kansas City. [8] Date, C.J., An introduction to database systems. 4th ed. Addison-Wesley systems programming series. 1986, Reading, Mass.: Addison-Wesley Pub. Co. [9] Date, C.J., An introduction to database systems. 5th ed. Addison-Wesley systems programming series. 1990, Reading, Mass.: Addison-Wesley. [10] Elmasri, R. and S. Navathe, Fundamentals of database systems. 1989, Redwood City, Calif.: Benjamin/Cummings. 802. [11] Lalonde, W.R. and J.R. Pugh, Inside Smalltalk: Volumn 1. 1990: Prentice Hall. [12] Bancilhon, F., C. Dolobel, and P. Kanellakis, Building an Object-Oriented Database Systems: The Story of O2. 1992: Morgan Kaufmann. [13] ObjectStore, I., ObjectStore Reference. 1998. [14] Versant, Versant ODBMS 5.0: System Manual. 1997. 149 [15] Kim, W., J.M. Nicolas, and S. Nishio, Deductive and object-oriented databases: proceedings of the First International Conference on Deductive and Object-Oriented Databases (DOOD89), Kyoto Research Park, Kyoto, Japan, 4-6 December, 1989. 1990, Amsterdam ; New York New York: North Holland; Elsevier Science Pub. Co. distributors for the United States and Canada. 607. [16] Kim, W., Object-Oriented Databases: Definition and Research Directions. IEEE Transactions on Knowledge and Data Engineering, 1990. 2(3): p. 327-341. [17] Kim, W., Y. Kambayashi, and I.S. Paik, Database systems for next-generation applications : principles and practice : papers from the Proceedings of the First International Symposium on Database Systems for Advanced Applications [held in Seoul, Korea, April, 1989]. Advanced database research and development series. Vol. 1. 1992, River Edge, N.J.: World Scientific. 312. [18] Eswaran, K.P., et al., The Notions of Consistency and Predicate Locks in a Database System. Communications of the ACM, 1976. 19(11): p. 624-633. [19] Gray, J. and A. Reuter, Transaction processing : concepts and techniques. The Morgan Kaufmann series in data management systems. 1993, San Mateo, Calif.: Morgan Kaufmann Publishers. 1070. [20] Fortier, P.J., Database systems handbook. 1997, New York: McGraw-Hill. 611. [21] Korth, H.F. and A. Silberschatz, Database system concepts. 2nd ed. McGraw-Hill computer science series. 1991, New York: McGraw-Hill. 694. [22] Reuter, A., Concurrency on High-Traffic Data Elements. ACM PODS, 1982. 1st: p. 83-92. [23] Kung, H. and J. Robinson, On optimistic methods for concurrency control. ACM Trans. Database Syst., 1981. 6(2): p. 213-226. [24] Kung, H.T. and C.H. Papadimitriou, An optimality theory of concurrency control for databases. Cmu-Cs-80-147. 1980, Pittsburgh, Pa.: Carnegie-Mellon University Dept. of Computer Science. [25] Gray, J., et al., Granularity of Locks and Degrees of Consistency in a Shared Database. Modeling in Data Base Management Systems, 1976. [26] Lee, S.-Y. and R.-L. Liou, A Multi-Granularity Locking Model for Concurrency Control in Object-Oriented Database Systems. IEEE Computer Society, 1996. 8(1). [27] Gray, J.N., Operating Systems: An Advanced Course, in Lecture Notes in Computer Science, R. Bayer, R.M. Graham, and G. Seegmuller, Editors. 1978, Springer-Verlag. p. 393-481. [28] Garcia-Molina, H., Using semantic knowledge for transaction processing in a distributed database. ACM Transaction on Database System, 1983. 8(2): p. 186-213. [29] Hadzilacos, T. and V. Hadzilacos, Transaction Synchronization in Object Bases. Journal of Computer and System Sciences, 1988. 43(1): p. 2-24. [30] Beeri, C., P.A. Bernstein, and N. Goodman, A model for concurrency in nested transactions systems. Journal of the ACM, 1989. 36(2): p. 230-269. [31] Moss, J.E.B., Nested Transactions: An Approach to Reliable Distributed Computing. 1985, Cambridge, Massachusetts: MIT Press. 150 [32] Muth, P., et al. Semantic Concurrency Control in Object-Oriented Database Systems. in Proceedings of the 9th IEEE International Conference on Data Engineering. 1993. [33] Agrawal, D., A. El Abbadi, and A.K. Singh, Consistency and Orderability: Semantic-Based Correctness Criteria for Databases. ACM Transactions on Database Systems, ACM Computing Surveys, 1993. 18(3): p. 460-486. [34] Cart, M. and J. Ferrie. Integrating Concurrency Control into an Object-Oriented Database System. in Proceedings of the International Conference on Extending DataBase Technology. 1990: Springer-Verlag. [35] Taniguchi, S., Budiarto, and S. Nishio, On Locking Protocols in Object-Oriented Database Systems. IEICE Trans. Inf. & Syst., 1995. E78-D(11): p. 1449-1457. [36] Lehman, T.J. and M.J. Carey, A Concurrency Control Algorithm for Memory-Resident Database Systems. Proceedings of Third International Conference on Foundations of Data Organization and Algorithms, 1989. [37] Joshi, A.M., Adaptive Locking Strategies in a Multi-node Data Sharing Environment. Proceedings of the 17th International Conference on Very Large Data Bases, 1991: p. 181-191. [38] Banerjee, J., et al. Semantics and Implementation of Schema Evolution in Object-Oriented Databases. in ACM SIGMOD Int. Conf. Management Data. 1987. [39] Carey, M.J., D.J. DeWitt, and J.F. Naughton. The OO7 Benchmark. in SIGMOD. 1993. Washington: ACM. 151 VITA Conrad Chang was born on September 10, 1970 in Hong Kong. He graduated from the St. Margaret's High School in 1987. He attended the Illinois State University in Normal-Bloomington, Illinois where he studied Applied Computer Science and earned a B.S. in 1990. Following graduation, he continued to graduate school at Illinois State University to pursue a Master degree in Applied Computer Science and earned a M.S. in 1992. While at the university he was also employed as a software engineer at the U.S. Army Corps of Engineers Research Lab (USACERL) where he designed and developed data models and relational database software for various environmental agencies of the government. In 1993, he went to the University of Illinois at Urbana-Champaign to pursue a Doctorate in Computer Science. During his enrollment, he was employed as a research programmer at the Community Architecture Network Information System (CANIS) research laboratory where he did research on information retrieval technology in large-scale distributed information system. He developed architecture and software for a research prototype that used neural network, distributed object-oriented database, visualization techniques, and semantic information retrieval algorithms to enhance the effectiveness of information retrieval. He is currently employed at the MITRE Corporation in Boston, Massachusetts where he is involved in research and development in text mining and data mining technology for the government. 152