[Database] - 트랜잭션 스케줄과 Serializability
- 이번 포스팅에서는 트랜잭션 스케줄과 Serializabililty의 개념에 대해서 살펴볼 예정입니다.
트랜잭션 스케줄
지난 포스팅에서 살펴본 것처럼 트랜잭션은 원자성, 일관성, 독립성, 영속성의 성질을 지니고 있습니다. 데이터베이스는 트랜잭션의 이러한 성질을 유지하면서도 프로세서와 디스크 활용의 효율을 높이고, 사용자에게 더 빠른 평균 응답 시간을 보장하기 위해 여러 트랜잭션들을 동시에 실행합니다.
그렇기 때문에 여러 트랜잭션들 간의 순서를 조율할 필요가 생기는데요, 이를 위해서 트랜잭션의 스케줄 개념을 활용합니다. 트랜잭션 스케줄이란 동시에 실행되고 있는 트랜잭션들의 명령들(instructions) 간의 순서입니다.
이때, 각 트랜잭션들이 순차적으로 실행되는 스케줄을 Serial 스케줄이라고 합니다. 예를 들어, 아래와 같이 트랜잭션 T1과 T2가 실행된다면 이는 Serial한 스케줄이라고 할 수 있습니다.
T1 | T2
read(A) |
A:= A-50 |
write(A) |
commit |
| read(A)
| A:= A+50
| write(A)
| commit
이렇게 Serial한 스케줄로 트랜잭션들의 명령어를 실행할 경우, 당연하게도 각 트랜잭션들이 순차적으로 실행되기 때문에, 여러 트랜잭션들을 동시에 실행하더라도 트랜잭션의 독립성을 해치지 않고 실행이 가능하게 됩니다. 따라서 트랜잭션의 스케줄을 관리함에 있어서, Serial한 스케줄과 동일한 결과를 산출할 수 있는 스케줄이 되도록 만드는 것이 중요해집니다. 아래의 Serializability 개념은 어떤 스케줄이 Serial한 스케줄과 동일한 결과를 산출할 수 있는지를 판단하기 위한 개념이라고 할 수 있습니다.
Serializability
특정 트랜잭션 스케줄이 있을 때, 해당 스케줄이 Serial한 스케줄과 동등(equivalent)하다면, 이 스케줄을 Serializable한 스케줄이라고 합니다. 즉, serial한 스케줄로 만들 수 있는 스케줄이라는 의미로 이해할 수 있습니다.
그렇다면 해당 스케줄이 Serial한 스케줄과 동등한지를 판단하는 기준은 무엇일까요? 이와 관련해서는 여러 개념들이 존재하지만, 이번 포스팅에서는 Conflict Serializability의 개념과 View Serializability의 개념을 살펴보도록 하겠습니다.
먼저 해당 개념들을 살펴보기에 앞서, Conflict Serializability와 View Serializability는 어디까지나 개념이라는 점을 명확히 해야 합니다. 실제로 데이터베이스에서 트랜잭션 스케줄을 관리함에 있어서 모든 스케줄을 대상으로 Conflict Serializability와 View Serializability를 체크하면서 스케줄을 관리하기는 어렵습니다. 즉, 이 두 개념들을 적절히 활용하여 실제 데이터베이스에서는 여러 기법들을 활용해 Serializable한 스케줄을 만들기 위해 노력하고 있다고 생각하면 이해가 편할 것 같습니다.
또한 두 개념을 설명하는 과정을 간소화하기 위해, 트랜잭션의 명령어에는 read와 write만 있다고 가정하겠습니다.
Confilct Serializability
Conflict Serializability에서는 우선적으로 트랜잭션을 구성하는 각 명령어들에 대해서 conflict의 개념을 정립합니다. 두 명령어가 동일한 데이터에 접근한다고 가정했을 때, 두 명령어 중 하나라도 해당 데이터에 대해서 쓰는(write) 행위를 한다면, 두 명령어는 conflict 관계에 있다고 이야기 할 수 있습니다.
만약 두 명령어가 conflict 관계에 있지 않다면, 이 두 명령어는 서로 순서를 바꿔도 전체 스케줄의 결과에는 영향을 미치지 않는다고 판단합니다.
이러한 개념적 배경 아래에서, 특정 스케줄을 conflict가 발생하지 않는 명령어들 간의 순서 변경을 통해 Serial한 스케줄로 만들 수 있다면 해당 스케줄은 Serial한 스케줄과 Conflict Equivalent하다고 합니다. 또한 이렇게 Serial한 스케줄과 Equivalent한 스케줄을 Conflict Serializable한 스케줄이라고 합니다.
예를 들어, 아래의 스케줄을 살펴보겠습니다. 이 스케줄을 스케줄1이라고 부르겠습니다.
T1 | T2
read(A) |
| read(B)
write(A) |
| write(B)
스케줄1에서 트랜잭션 T1의 명령어 write(A)는 트랜잭션 T2의 명령어 read(B)와 서로 다른 데이터에 대해서 접근하고 있기 때문에, 이 두 명령어는 conflict가 발생하지 않습니다. 따라서 두 명령어 간의 순서를 변경할 수 있습니다. 두 명령어의 순서를 변경하면 아래와 같아집니다. 변경한 스케줄을 스케줄2라고 부르겠습니다.
T1 | T2
read(A) |
write(A) |
| read(B)
| write(B)
결국 스케줄1은 스케줄2와 Conflict Equivalent하다고 할 수 있습니다. 또한 스케줄2는 Serial한 스케줄이기 때문에, 결과적으로 스케줄1은 Conflict Serializable한 스케줄이라고 할 수 있습니다.
예시를 하나 더 들어보겠습니다. 아래의 스케줄을 스케줄3이라고 부르겠습니다.
T1 | T2
read(A) |
| read(A)
write(A) |
스케줄3에서, T1의 명령어 write(A)와 T2의 명령어 read(A)는 동일한 데이터에 대해서 접근하고 있으며, 둘 중 하나는 쓰는 행위를 하고 있기 때문에 두 명령어는 conflict가 발생한다고 할 수 있습니다. 이에 따라 두 명령어는 순서를 변경할 수 없게 되고, 그렇기 때문에 스케줄3은 Conflict Serializable하지 않다고 판단할 수 있습니다.
View Serializability
두 스케줄이 있을 때, 아래의 세 가지 조건을 만족한다면 두 스케줄은 View Equivalent하다고 할 수 있습니다.
- 두 스케줄의 첫 read는 동일한 데이터에 대해 동일한 트랜잭션에 의해 수행되어야 합니다.
- 두 스케줄에서 트랜잭션이 특정 데이터를 read했다면, 해당 데이터는 두 스케줄에서 동일한 트랜잭션에 의해서 write 된 데이터여야 합니다.
- 두 스케줄의 마지막 write는 동일한 데이터에 대해서 동일한 트랜잭션에 의해 이루어져야 합니다.
예를 들어 아래와 같이 트랜잭션 세 개로 이루어진 스케줄이 있다고 가정하겠습니다. 이를 스케줄4라고 부르겠습니다.
T1 | T2 | T3
read(A) | |
| read(A) |
write(A) | |
| | write(A)
그리고 아래와 같이 Serial한 스케줄을 스케줄5라고 부르겠습니다.
T1 | T2 | T3
read(A) | |
write(A) | |
| read(A) |
| | write(A)
스케줄4와 스케줄5를 비교했을 때, 두 스케줄 모두 동일한 데이터 A에 대해서 트랜잭션 T1이 처음 read를 수행하고 있습니다. 또한 두 스케줄 모두 트랜잭션 T3에 의해서 마지막 write(A)가 수행되고 있기 때문에, 두 스케줄은 View Equivalent하다고 할 수 있습니다.
이에 따라 스케줄4는 Serial한 스케줄5와 View Equivalent하게 되고, 그렇기 때문에 View Serializable하다고 할 수 있습니다.
개념적으로 View Serializable은 Conflict Serialzable을 포함합니다. 즉, 어떤 한 스케줄이 View Serializable하다면 그 스케줄은 Conflict Serializable하다고 할 수 있습니다. 그러나 그 반대는 성립하지 않습니다. 다시말해 Conflict Serializable하지 않지만 View Serializable한 스케줄이 존재한다고 할 수 있습니다.
정리
이번 포스팅에서는 트랜잭션을 동시에 실행하는 과정에서 트랜잭션의 스케줄을 어떤식으로 관리하는지 파악하기 위해 트랜잭션 스케줄과 Serializability의 개념에 대해서 살펴봤습니다. 다음 포스팅에서는 Serializability 개념을 바탕으로 트랜잭션의 격리 수준 개념에 대해 살펴보겠습니다.
Reference