Akira's Research Focus

Concurrency control (CC) algorithms support serializability (SR) of the transactions. Applications related to billing, retailing, and decision support share a common problem of performance degradation, often caused by the interferences between long hauling query transactions and update transactions. In particular, recent database applications built on the Internet environment have found strict SR too restrictive. A serious performance problem may arise when these applications developed on top of Java/JDBC and Servlet interface extensively rely on the use of Java's thread control for their parallel processing. Java's thread control is to maintain synchronization points, not to achieve sophisticated concurrency control. Epsilon serializability (ESR) is introduced to explore a possible solution for this problem.

Importance of Epsilon Serializability: The ESR concept is proposed to alleviate SR constraints by allowing a transaction history to have some bounded inconsistency. In particular, a limited amount of inconsistency can be seen by read-only transactions. The specification of this error tolerance is called an epsilon specification (epspec). It can be defined as a measure of distance in the database state space. A simple example is the checking account sum-up query---a bank manager wants to know how many millions of dollars a customer has in all the checking accounts with the error tolerance rate of half a million (i.e., epspec = $0.5 M). The round-off error of the query is half a million dollars. This query returns a meaningful result even it could contain errors due to non-serializable conflicts with some updates, up to half a million dollars. By measuring state distances for non-serializable operations rather forcing strict serialization, this sum-up query ends significantly faster. Divergence control (DC) algorithms have been designed to bound the amount of inconsistency for ESR the same way concurrency control maintains SR. In fact, DC algorithms extend classic CC algorithms such as two-phase locking, optimistic validation, and timestamps.

Java Serializability: A Java thread allows a programmer to write code that executes in parallel. Multiple threads usually share objects, and therefore the objects must use synchronization mechanisms to coordinate thread access to these objects. Concurrency control for a group of active threads is based on this synchronization---only one thread is allowed to run at a time on an object and all the competing threads to access that object are queued. Java's thread synchronization uses a monitor primitive that implements a mutual exclusion using a lock, where the lock granularity is an object. Deadlock prevention is programmer's responsibility as the monitor does not support any deadlock resolution. In a typical thread environment, data members of a collection object, say an object having an array of some objects as data members, are simultaneously read and written. A naive approach to maintain consistent state change of such an object is to use a Java language primitive, called synchronized method, that will sequentialize read and write operations. This would however yield high overhead if the application built on the collection object mainly reads the data elements. Remember that more than one read operation cannot coexist even the read operation does not modify the status of the object. It is better if multiple read operations do not interfere; it is even better if a lock granule is finer, that is, each data element in the array is chosen for a lock unit instead of the collection object (holding such data elements) as a whole. This observation motivates us to explore the ESR framework, particularly under the situation that the application is tolerated with a limited inconsistency for faster processing.

Significance of Project: This project aims to realize an alternative to the Java's synchronization method. The ESR concept is applied to realize Java Divergence Control. Divergence Control based on two phase-locking was implemented and its correctness was verified in the year 2000, as planned in the original proposal. The next stage is to realize optimistic divergence control (ODC) for the Java's thread synchronization. By optimistic, we mean that the check of sharable (read) lock will be deferred until the state of the object gets changed by a write operation. Every thread that has read an object will abort and re-execute in order to guarantee serializability if one of the threads writes that object. A deadlock will never occur in this case. Optimistic concurrency control, in contrast to two-phase locking (as in Java monitor implementation), was proposed in 1980's in the context of database processing. Several simulation studies showed that, under the read intensive environment, the optimistic method outperforms other concurrency control methods. The importance of using ESR based optimistic method might increase when the application gains a performance advantage in the presence of a limited amount of inconsistency. Many read intensive applications built on top of the Internet might benefit from this approach. Therefore, a goal of the project is to demonstrate a potential advantage of using Divergence Control for Java thread environment. This is one of the first pieces of work that explores extension of the Java's thread control. The results of this study will provide many useful guidelines such as technical solutions and comparison metrics for designing a new thread control mechanism.