[Database] DBA급 개발자로 - #17 Timestamp Ordering Concurrency Control

이전 포스팅에서는 2 phase locking을 통해 어떻게 concurrent transaction을 처리하는지 살펴봤습니다. 이번 포스팅에서는 timestamp를 통해 concurrent transaction을 처리하는 방법을 살펴보겠습니다. 

Timestamp Ordering 

Timestamp ordering 방식도 2 phase locking처럼 concurrent transaction을 처리하기 위한 프로토콜입니다. 주된 차이점은 2 phase locking의 경우 트랜잭션이 실행되는 과정에서 충돌이 발생하면 해당 트랜잭션을 롤백하지만 timestamp ordering의 경우 트랜잭션이 실행되기 전에 충돌 여부를 미리 확인합니다. 

두 트랜잭션 Ti, Tj이 동시에 진행되고 트랜잭션이 시작된 시간이 TS(Ti) < TS(Tj)라고 가정할 때 timestamp ordering 프로토콜에 맞게 구현된 DBMS는 Ti와 Tj가 순차적으로 실행됐을 때의 결과와 timestamp ordering 프로토콜에 의해 실행된 Ti, Tj의 결과가 동일합니다.

 

$$ TS(T_i): timestamp\,of\,T_i $$ 

Basic Timestamp Ordering 

Basic timestamp ordering 프로토콜은 데이터(X라고 부르겠습니다)에 성공적인 읽기 또는 쓰기 작업이 발생했을 때 해당 작업이 발생한 시간(timestamp)을 별도로 저장합니다. 

$$ R-TS(X): read\,timestamp\,of\,object\,X $$

$$ W-TS(X): write\,timestamp\,of\,object\,X $$ 

Reads 

다음과 같은 경우 읽기 작업이 실패합니다. 만약 Ti가 특정 데이터 X를 읽으려 할 때, X는 Ti보다 나중에 실행된 Tj에 의해 성공적으로 쓰기 작업이 수행됐다면 Ti는 abort 하게 됩니다. 즉 더 나중에 실행된 트랜잭션에 의해 성공적으로 수정된 데이터를 읽으려 하면 이전 트랜잭션은 abort 됩니다. 

Writes 

트랜잭션의 쓰기 작업도 읽기 작업과 유사한 경우 실패합니다. 만약 Ti가 특정 데이터 X에 쓰기 작업을 처리하려 할 때, W-TS(X)가 TS(Ti) 보다 더 크다면, 즉 더 나중에 발생한 트랜잭션에 의해 데이터 X에 쓰기 작업이 성공적으로 수행됐었으면, 트랜잭션 Ti는 abort 됩니다. 

Thomas write rule 
Basic timestamp ordering 프로토콜의 경우 더 나중에 발생한 트랜잭션에 의해 수정된 데이터를 이전에 발생한 트랜잭션(Ti)이 수정하려 하면 이전에 발생한 트랜잭션(Ti)은 abort 됩니다. 하지만 Thomas write rule을 적용하게 되면 Ti는 쓰기 작업을 무시하고 트랜잭션을 계속 진행합니다. 결과적으로 outdated 된 쓰기 작업(Ti에 의해 write 작업)을 무시함으로써 전체 트랜잭션을 성공적을 완료시킵니다.

Basic Timestamp Ordering 단점 

Basic timestamp ordering 프로토콜을 위해 모든 데이터에 timestamp를 기록해야 하는 오버헤드가 존재합니다. 또한 실행기간이 긴 트랜잭션의 경우 다른 트랜잭션과 충돌이 발생할 확률이 높아지기 때문에 해당 트랜잭션은 starvation 될 확률이 높습니다. 만약 트랜잭션 간 충돌이 적고 트랜잭션이 수행되는 시간이 짧다면 basic timestamp ordering처럼 pessimistic 방식보다는 optimistic 방식으로 동시 트랜잭션을 처리하는 게 유리할 수 있습니다. 

Optimistic Concurrency Control(timestamp ordering) 

Basic timestamp ordering의 경우 트랜잭션 실행 시점 이전에 충돌 여부를 미리 판단합니다(pessimistic). 이러한 방식은 트랜잭션 간 충돌이 적고 트랜잭션의 실행 시간이 짧은 경우 불필요하게 트랜잭션 충돌 여부를 확인하기 때문에 효율적이지 않습니다. 따라서 이를 해결하기 위해 optimistic concurrency control timestamp ordering 프로토콜을 활용할 수 있습니다. 

동작 방식 

Optimistic concurrency control timestamp ordering은 다음과 같이 동작합니다. 읽기 대상의 데이터는 모두 임시 영역에 복사됩니다. 데이터에 대한 쓰기는 해당 임시 영역에서 수행됩니다. 트랜잭션이 커밋하기 직전에 임시 영역에 복사된 데이터가 실제 데이터베이스에서 다른 트랜잭션에 의해 쓰인 데이터와 논리적으로 충돌하는지 확인합니다(검증 단계). 만약 논리적으로 충돌하는 관계라면 해당 트랜잭션은 abort 됩니다. 충돌하지 않는다면 임시 영역에 쓰인 데이터는 데이터베이스에 반영됩니다. 

이러한 방식은 트랜잭션의 수행 시간이 짧고 트랜잭션 간 충돌이 적을 때 효율적입니다. 또한 트랜잭션의 작업이 읽기 위주라면 더욱 효율적입니다. 단점으로는 데이터를 임시 영역에 복사해야 하기 때문에 오버헤드가 큽니다. 

마무리 

이번 포스팅을 통해 timestamp을 활용하여 트랜잭션 동시성 제어를 하는 방법을 살펴봤습니다. 다음 포스팅에서는 MVCC(Multi-Version Concurrency Control) 프로토콜에 대해 살펴보겠습니다.