Locking is a widely-used technique for concurrency control in database management systems(DBMSs). In locking, a transaction has to acquire a lock before accessing the data to insure the consistency of the database. Since DBMSs have limited lock resources, when locks are requested excessively, lock resources can be exhausted. Thus, the transactions that are not able to secure locks should be aborted, degrading the performance. In the worst case, all transactions could fall in cyclic restart without being able to commit. We call this situation live halt. Live halt is a fatal situation where the system becomes paralyzed.
Lock escalation can be effectively used to alleviate this problem. Lock escalation reduces the number of locks in use by converting many fine granularity locks to a coarse granularity lock. However, existing lock escalation methods abort transactions unnecessarily since they use a local approach, in which individual transactions determine whether or not to execute lock escalation without global consideration on the total number of locks being used in the system. Moreover, they have been designed in an ad hoc manner without a formal model. So, they do not provide a complete solution.
In this dissertation, to solve the problems of the existing methods, we first propose a new lock escalation method, simple adaptive lock escalation, that executes lock escalation based on the total number of locks. Simple adaptive lock escalation does not have the problem of aborting a transaction unnecessarily since it considers the total number of locks and globally determines the transaction to execute lock escalation and the target file. Nevertheless, simple adaptive lock escalation cannot prevent cyclic restart and live halt because the lock resources can also be exhausted.
Next, we propose a general model for lock escalation for its formal understanding. In particular, we introduce the concept of the unescalatable lock, which we define as the the one that cannot be escalated due to lock conflict. We identify that the unescalatable lock is the major cause of lock resource exhaustion. We then analyze the reasons why unescalatable locks are generated and propose techniques to counter them: semi lock escalation, meta locking, and selective relief. Based on these techniques, we propose adaptive lock escalation, which controls lock escalation based on the total number of unescalatable locks. Even under excessive lock requests, adaptive lock escalation guarantees that the DBMS do not fall in live halt, gradually transiting to a serial execution of transactions.
Through extensive simulation, we show that adaptive lock escalation significantly outperforms existing methods reducing the number of aborts and the average response time and increasing the throughput to a great extent. Given the same amount of lock resources, the number of concurrent transactions allowable is increased more than 16~256 fold compared with the existing methods. Moreover, it drastically reduces(more than 10 fold) the number of lock resources required to maintain the same level of throughput.
Adaptive lock escalation is very useful for self-tuning DBMSs. In existing lock escalation methods, the user(or the system administrator) has to estimate the number of lock resources accurately at system initialization time since the performance is sensitive to the number of lock resources. In contrast, adaptive lock escalation relieves the users of this burden because the performance is rather insesitive to the number of lock resources.
The contribution of this paper is significant in that it has formally analyzed the role of lock escalation in lock resource management, which has been only vaguely understood, and in that it has clarified the underlying mechanisms of lock escalation.
대부분의 데이타베이스 관리 시스템(DBMS)에서는 동시성 제어 방법으로 로킹 기법을 사용한다. 로킹 기법은 각 트랜잭션이 액세스하는 데이타에 대하여 미리 로크를 획득함으로써 일관성을 파괴할 수 있는 다른 트랜잭션의 연산이 수행되는 것을 방지하는 방법이다. 로킹 기법을 사용하는 DBMS에서는 가용 로크자원의 한계로 인하여, 과다한 로크요청이 발생하면 로크자원이 부족하게 된다. 이러한 경우, 로크를 획득하지 못한 트랜잭션들이 철회되면서 시스템의 성능이 저하된다. 더구나 최악의 경우에는 모든 트랜잭션이 순환 재시작 상태가 되어 어떤 트랜잭션도 완료하지 못하는 현상이 발생한다. 이러한 현상을 활성정지라고 정의하는데, 활성정지는 시스템이 정지된 것과 같은 치명적인 현상이다.
로크상승은 로크자원의 부족으로 발생하는 문제를 해결하는 방법이다. 로크상승은 여러 개의 하위수준 로크를 반환하고, 대신 그 하위수준 로크들을 포함하는 하나의 상위수준 로크를 획득함으로써 로크의 갯수를 감소시킨다. 그러나 기존의 로크상승 기법들은 각 트랜잭션이 획득한 로크의 갯수에 따라 로크상승 여부를 결정하는 지역적 접근법을 사용하기 때문에 트랜잭션들을 불필요하게 철회시키는 문제점이 있다. 또한, 정형적인 모델이 없이 임의적(ad hoc)으로 설계되어 로크자원이 부족할 때 발생하는 문제를 완전히 해결하지는 못한다.
본 논문에서는 먼저 기존 로크상승 기법들의 문제점을 해결하기 위하여 시스템의 총 로크사용량에 따라 로크상승의 수행 여부를 결정하는 기본 적응형 로크상승 기법을 제안한다. 이 방법은 총 로크사용량을 고려하여 로크상승을 수행할 트랜잭션과 화일을 전역적으로 결정하기 때문에 트랜잭션들을 불필요하게 철회하는 문제가 발생하지 않는다. 그러나 기본 적응형 로크상승 기법도 활성정지를 방지하지는 못한다. 왜냐하면 로크모드의 충돌로 인하여 로크상승을 수행할 수 없는 경우가 있기 때문이다.
다음으로, 본 논문에서는 로크상승을 보다 체계적으로 이해하기 위하여 로크상승에 대한 정형적 모델을 제안한다. 제안한 모델에서 로크모드의 충돌로 인하여 로크상승을 수행할 수 없는 상승불가능 로크 개념을 제안하고, 상승불가능 로크가 로크자원의 부족으로 인한 트랜잭션 철회의 원인임을 규명한다. 이에 따라, 상승불가능 로크가 생성되는 원인을 세 가지로 분류하고, 각각의 원인에 대한 해결방법으로 준로크상승, 메타 로킹, 그리고 선택적 강제수행의 개념을 제안한다. 마지막으로, 제안한 개념들을 이용하여 상승불가능 로크의 갯수를 기반으로 로크상승의 수행여부를 결정하는 적응형 로크상승 기법을 제안한다. 적응형 로크상승 기법은 과다한 로크요청이 발생하는 경우에 점차적으로 트랜잭션의 직렬 수행을 유도함으로써 활성정지가 발생하지 않음을 보장한다.
본 논문에서는 실험을 통하여 적응형 로크상승 기법이 기존의 로크상승 기법들보다 매우 우수함을 보인다. 실험 결과, 적응형 로크상승 기법은 과다한 로크요청이 발생하는 환경에서 트랜잭션의 철회 및 평균 응답시간을 크게 줄이고, 단위시간 당 트랜잭션 처리율을 크게 향상시킨다. 특히, 동일한 로크자원을 사용할 때 기존 로크상승 기법들에 비하여 16에서 256배이상의 트랜잭션을 동시에 수행시킬 수 있다. 또한, 비슷한 수준의 성능을 유지하기 위하여 필요로하는 로크자원의 갯수를 $\frac{1}{10}$ 이하로 크게 감소시킨다.
응용측면에서 적응형 로크상승 기법의 중요한 특징은 자체-조율 DBMS에 매우 유용하다는 것이다. 기존의 로크상승 기법들에서는 총 로크자원의 갯수가 시스템의 성능에 큰 영향을 미치기 때문에 사용자 또는 시스템 관리자가 정확하게 예측하여 설정하여야만 한다. 반면에, 적응형 로크상승 기법에서는 시스템의 성능이 총 로크자원의 갯수에 민감하지 않으므로 사용자가 총 로크자원의 갯수를 설정하는 것이 용이하다.
본 논문은 모호하게 인식되던 로크자원 관리 측면에서의 로크상승의 역할을 체계적으로 규명하고 상세한 작동원리를 명확히 했다는 점에서 커다란 의의가 있다.
