The notion of nested transactions has been introduced to overcome the deficiencies of single-level transactions. Nested transactions allow intra-transaction parallelism and failure independence. Thus, a nested transaction mechanism must provide proper synchronization and recovery for nested transactions. In this thesis, for complete transaction management in nested transaction systems, concurrency control schemes, deadlock detection schemes, and recovery scheme are proposed.
For concurrency control scheme, a new lock transformation scheme for nested transaction model which allows parent/child parallelism and commitment independence is proposed. The basic principle of lock transformation scheme is to permit early release of locks, which prevents commit deadlocks incurred by permitting parent/child parallelism. In addition, two locking rules based on the lock transformation scheme, pessimistic locking rule(PLR) and optimistic locking rule(OLR), are proposed. PLR strictly follows the policy of traditional locking rules in nested transactions, whereas OLR follows a new policy in favor of a higher concurrency. Then, the performance of two locking rules is studied using a simulation approach. According to the simulation results, OLR is superior to PLR with respect to the number of aborts, the number of deadlocks, and the degree of concurrency.
Deadlock detection algorithms based on edge-chasing method for nested transactions using two proposed locking rules are proposed. Then, they are refined to reduce the overhead incurred by deadlock detection. The proposed deadlock detection algorithms fully make use of nested structures of transactions in detecting deadlocks. As a result, in our algorithms, messages do not need to traverse transaction tree to detect deadlocks. This implies that our algorithms are able to detect deadlocks with constant message passing overhead regardless of the depth of nesting in a transaction tree. In addition, the principle of victim selection is discussed in order to resolve deadlocks.
For recovery scheme, the concept of double log sequence numbers (LSNs) is proposed. The recovery scheme using double LSNs can support operation logging as well as value logging, which is required in order to allow semantically-rich lock modes. Unlike previous recovery schemes, our recovery scheme based on double LSNs is able to avoid unnecessary redos and subsequent undos. Furthermore, our scheme can cope with successive crashes which might occur during recovery.
중포 트랜잭션의 개념은 일차 단위 트랜잭션의 단점을 보완하기 위하여 도입되었다. 중포 트랜잭션은 트랜잭션간의 동시 실행과 고장 독립성을 허용하므로 중포트랜잭션에서는 세분화된 동시성 제어와 복구 방안이 제공되어야 한다. 본 논문에서는, 중포 트랜잭션 시스템에서의 효율적인 트랜잭션 관리를 위하여 동시성 제어방법, 교착상태 검출 방법, 그리고 복구 방법을 제안한다.
동시성 제어를 위하여 새로운 로크 변환 기법을 제안하였다. 로크 변환 기법의 기본 원리는 완료 교착상태를 방지할 수 있도록 로크를 일찍 반납하는 것이다. 또한, 제안한 로크 변환 방법을 기반으로 하는 비관적 로킹 규칙과 낙관적 로킹 규칙을 제안하고 두 로킹 규칙의 성능을 시뮬레이션을 통하여 분석하였다. 분석 결과에 따르면, 낙관적 로킹 규칙이 비관적 규칙보다 철회 갯수, 교착상태 발생 횟수, 그리고 동시 실행 정도에서 우월한 것으로 나타났다.
제안한 두 로킹 규칙을 사용하는 중포 트랜잭션에 대하여 에지-추적 방법을 기반으로 하는 교착상태 검출 알고리즘을 각각 제안하였으며 검출에 따르는 비용을 줄이는 방안에 대하여 논의 하였다. 제안된 알고리즘은 교착상태 검출을 위하여 트랜잭션들이 중포된 구조를 충분히 이용하므로, 교착상태 검출을 하기 위하여 트랜잭션 트리를 메시지가 순회할 필요가 없다. 따라서, 제안된 알고리즘은 중포의 깊이와 무관하게 일정한 메시지 전송 비용으로 교착상태를 검출할 수가 있다. 또한, 검출된 교착상태를 해결하기 위하여 희생자 트랜잭션의 선택에 대한 논의도 하였다.
복구를 위하여 이중 로그 순차번호 개념을 제안하였다. 이중 로그 순차번호를 사용하는 복구 방법은 의미가 부여된 로크 모드를 허용하는 경우에 필요한 연산로깅을 지원할 수 있다. 기존의 복구 방법과는 달리, 이중 로그 순차번호를 기반으로 하여 본 논문에서 제안한 복구 방법은 불필요한 복구 조치를 피할 수 있으며 복구 도중에 발생할 수 있는 고장에도 대처할 수 있다.