In this thesis, we present a new concurrency control scheme for long-lived transactions, named ALOT (Algorithm for scheduling LOng-lived Transactions), in order to coordinate concurrent design activities in collaborative design applications. ALOT consists of two complementary concurrency control schemes: ALOT/SCC (ALOT for Semantic Concurrency Control) and ALOT/CBL (ALOT for Conditional Blocking). ALOT/SCC weakens the usual notion of serializability with the semantics of target applications. On the other hand, ALOT/CBL guarantees to produce serializable executions and it does not depend on any application-specific semantics. ALOT allows to exploit the semantics of target applications with ALOT/SCC, and thus support more concurrent executions for long-lived transactions. Furthermore, with ALOT/CBL, ALOT is able to also support applications where their semantics are not well understood.
Unlike the previous approaches for coordinating design activities, in which each designer faces complexity of a design activity, ALOT/SCC encapsulates this complexity from designers. This is achieved by two notions: (1) transaction template that guides the designer not to produce incorrect design results due to misunderstanding of complex design activities, and (2) interleaving specification that enables the designer to cooperate with his group members in a consistent way. Transaction templates are usually predefined by expert designers and stored in the template database. Interleaving specification is generated automatically when a designer retrieves a transaction template and instantiates it. In ALOT/SCC, therefore, any designer does not need to know the details of his design activities, and also does not need to concern about the moment of release for his intermediate results.
ALOT/CBL extends the conventional 2PL on the basis of cycle detection to determine if conflicting lock modes could be hold on the same data. In order to guarantee the serializability, ALOT/CBL maintains a transaction dependency graph (TDG). Unlike serialization graph testing (SGT) that is also on the basis of cycle detection, ALOT/CBL could reject a conflicting lock request even though the resulting TDG does not contain cycles. Whether a conflicting lock request could be accepted is determined by the notion of dependency depth. When the dependency depth is limited to nonnegative integer d, the transactions with larger dependency depths than d should be blocked; however, those with smaller dependency depths than d can access locked data with conflicting mode. This implies that, with the value of d, ALOT/CBL can properly balance the aborting effect and waiting effect due to long-lived transactions, and thus it can attain more concurrent executions than 2PL with fewer aborts than SGT.
본 논문에서는 상호 협조적인 설계 작업에서 실행되는 장기 거래를 위한 새로운 동시성 제어 기법으로 ALOT (Algorithm for scheduling LOng-lived Transactions)을 제안한다. ALOT은 상호 보완적인 두가지 동시성 제어 기법인 ALOT/SCC (ALOT for Semantic Concurrency Control)와 ALOT/CBL (ALOT for Conditional Blocking)로 구성된다. ALOT/SCC는 적용될 작업의 의미를 이용하여 기존 동시성 제어 기법의 정확성 기준인 직렬화 가능성을 완화함으로써 동시성의 정도를 향상시킨다. 이와는 달리, ALOT/CBL은 직렬화 가능한 동시 실행만 지원하지만 일반적인 작업에 적용 가능하다. 두가지 상호 보완적인 동시성 제어 기법을 통합함으로써 ALOT은 ALOT/SCC를 이용하여 적용될 작업의 의미를 트랜잭션 관리에 적용할 수 있으며, ALOT/CBL을 이용하여 작업의 의미가 잘 파악되지 않는 일반적인 작업도 지원 가능하다.
동시에 실행되는 설계 행위들을 조정하기 위해 기존에 제안된 기법들의 공통점은 설계 데이타의 일관성을 사용자가 책임진다는 것이다. 이러한 경우 발생할 수 있는 가장 큰 문제점은 사용자가 설계 행위의 복잡성으로 인해 오류를 범할 수 있다는 점이다. ALOT/SCC는 이러한 설계 행위의 복잡성을 사용자로부터 은폐함으로써 사용자 오류 발생의 확률을 줄인다. 이를 위해 ALOT/SCC는 트랜잭션 틀과 끼워넣기 명세의 개념을 이용한다. 사용자는 트랜잭션 틀의 개념을 통하여 자신의 설계 행위를 수행함으로써 복잡한 설계 행위의 그릇된 이해로 인해 발생할 수 있는 오류로부터 보호될 수 있다. 뿐만아니라, 끼워넣기 명세를 이용함으로써 동일한 그룹에 속한 사용자들간의 협조 작업에대한 일관성이 보장된다. 트랜잭션 틀은 전문가에 의해 정의되어 틀 데이타베이스에 저장되며, 끼워넣기 명세는 사용자가 자신의 설계 행위를 수행하기 위한 트랜잭션 틀을 선택하여 실행할 때 자동적으로 생성된다. 그러므로, ALOT/SCC에서는 사용자가 자신의 설계 행위에 대한 세부 사항을 자세히 이해하지 않아도 되며, 사용자가 설계 행위의 중간 결과를 어느 시점에서 다른 동료에게 보여줄 것인지를 결정할 필요가 없다.
ALOT/CBL은 기존의 두단계 로킹 기법 (2 Phase Locking: 2PL)을 확장한 기법으로 순환 검색 (cycle detection)에 바탕을 둔다. 즉, 순환이 발생하지 않을 경우 동일한 데이타에 대해 상충되는 모드의 로크들이 허용될 수 있다. 직렬화 가능성을 보장하기 위해 ALOT/CBL은 트랜잭션 의존 그래프 (Transaction Dependency Graph: TDG)를 유지한다. 순환 검색을 이용한 동시성 제어 기법인 직렬화 그래프 검사 기법 (Serialization Graph Testing: SGT)와는 달리 ALOT/CBL은 TDG에 순환이 발생하지 않더라도 상충되는 모드의 로크를 허용하지 않을 수 있다. 상충되는 모드의 로크 요청을 허용할 지의 여부는 의존 거리의 개념을 이용하여 결정된다. 즉, 의존 거리가 음이 아닌 정수 d로 제한될 경우, 로크 요청의 결과로 TDG의 의존 거리가 d보다 커지면 요청된 로크는 거절되고 그렇지 않으면 그 로크는 허락된다. 그러므로, ALOT/CBL은 d의 값에 따라 장기 거래로 인한 철회 효과와 대기 효과의 균형을 기할 수 있고, 그 결과로 2PL보다 동시성이 향상되며 SGT보다 트랜잭션 철회의 수를 줄일 수 있다.
