Schedule
여러 transaction들이 동시에 실행될 때 각 transaction에 속한 operation들의 실행 순서를 말한다.
read를 r, write를 w, commit을 c라고 표현했을 때 다음과 같이 case 별로 실행 순서를 작성할 수 있다.
- case 1: r1(K) -> w1(K) -> r1(H) -> w1(H) -> c1 -> r2(H) -> w2(H) -> c2
- case 2: r2(H) -> w2(H) -> c2 -> r1(K) -> w1(K) -> r1(H) -> w1(H) -> c1
- case 3: r1(K) -> w1(K) -> r2(H) -> w2(H) -> c2 -> r1(H) -> w1(H) -> c1
- case 4: r1(K) -> w1(K) -> r1(H) -> r2(H) -> w2(H) -> c2 -> w1(H) -> c1
r1, r2와 같이 뒤에 붙은 숫자가 다른 것은 서로 다른 사용자가 요청했다는 것을 의미하고 (H), (K)는 다른 테이블에 접근했다는 것을 의미한다.
Serial Schedule
transaction들이 겹치지 않고 한 번에 하나씩 실행되는 schedule을 말한다. 위에서 case1, case2가 해당된다.
- case 1:
r1(K) -> w1(K) -> r1(H) -> w1(H) -> c1->r2(H) -> w2(H) -> c2 - case 2:
r2(H) -> w2(H) -> c2->r1(K) -> w1(K) -> r1(H) -> w1(H) -> c1
한 번에 하나의 transaction만 실행되기 때문에 좋은 성능을 낼 수 없고 현실적으로 사용할 수 없는 방식이다.
Nonserial Schedule
transaction들이 겹쳐서 실행되는 schedule을 말한다. 위에서 case3, case4가 해당된다.
- case 3:
r1(K) -> w1(K)->r2(H) -> w2(H) -> c2->r1(H) -> w1(H) -> c1 - case 4:
r1(K) -> w1(K) -> r1(H)->r2(H) -> w2(H) -> c2->w1(H) -> c1
transaction들이 겹쳐서 실행되기 때문에 동시성이 적용되어 같은 시간 동안 더 많은 transaction들을 처리할 수 있다. 하지만 transaction들이 어떤 형태로 겹쳐서 실행되는지에 따라 잘못된 결과가 나올 수 있다.
따라서 Nonserial Schedule을 사용하면서 잘못된 결과가 나오지 않도록하기위해 equivalent라는 개념이 나오게 되었다.
Conflict
아래 세 가지 조건을 만족하면 conflict
- 서로 다른 transaction에 소속해야한다.
- 같은 데이터에 접근한다.
- 최소 하나는 write를 수행한다.
case3을 예시로 확인해보면 r2(H)와 w1(H)가 conflict한다.
- case 3: r1(K) -> w1(K) ->
r2(H)-> w2(H) -> c2 -> r1(H) ->w1(H)-> c1
이렇게 하나는 read를 수행하고 다른 하나는 write를 수행할 경우 read-write conflict라고도 부른다. 이외에도 w2(H), w1(H)와 w2(H), r1(H)가 conflict하다.
Conflict equivalent
아래 두 조건을 만족하면 conflict equivalent
- 두 schedule은 같은 transaction들을 가진다.
- 어떤 conflicting operation의 순서도 양쪽 schedule 모두 동일하다.
예시로 case2와 case3가 해당된다.
- case 2:
r2(H) -> w2(H) -> c2->r1(K) -> w1(K) -> r1(H) -> w1(H) -> c1 - case 3:
r1(K) -> w1(K)->r2(H) -> w2(H) -> c2->r1(H) -> w1(H) -> c1
먼저 두 schedule은 같은 작업을 실행하는 transaction들을 가지기 때문에 첫 번째 조건을 만족한다. 그리고 conflicting operation의 순서를 확인해보면 동일하다.
- r2(H) -> w1(H): transaction2가 H를 read한 후 transaction1이 H를 write
- w2(H) -> w1(H): transaction2가 H를 write한 후 transaction1이 H를 write
이렇게 nonserial schedule과 serial schedule가 conflict equivalent할 때 conflict serializable이라고 부른다.
Unrecoverable schedule
schedule 내에서 commit된 transaction이 rollback된 transaction이 write 했었던 데이터를 읽은 경우를 말한다.
예: r1(K) -> w1(K) -> r2(H) -> w2(H) -> r1(H) -> w1(H) -> c1 -> abort2
따라서 이전 상태로 회복이 불가능하기 때문에 이런 schedule은 DBMS가 혀용하면 안된다.
Recoverable schedule
schedule 내에서 어떤 transaction도 자신이 읽은 데이터를 write한 transaction이 먼저 commit/rollback 되기 전까지는 commit하지 않는 경우를 말한다.
예: r1(K) -> w1(K) -> r2(H) -> w2(H) -> r1(H) -> w1(H) -> c2-> c1
H의 데이터에 접근할 때 transaction1은 write를 먼저 수행한 transaction2에 의존성을 가진다. 따라서 transaction2가 먼저 commit하고 난 후 transaction1이 commit되어야한다. 또한 transaction2가 먼저 rollback하고 난 후에도 transaction1이 rollback되어야한다.
이렇게 의존성을 가지는 다른 transaction도 rollback되는 것을 cascading rollback이라고 한다. 하지만 여러 transaction의 rollback이 연쇄적으로 일어나면 처리하는 비용이 많이 든다.
Cascadeless schedule
schedule 내에서 어떤 transaction도 commit 되지 않은 transaction들이 wrtie한 데이터는 읽지 않는 경우를 말한다.
예: r1(K) -> w1(K) -> r2(H) -> w2(H) -> c2 -> r1(H) -> w1(H) -> c1
transaction2가 commit을 수행한 후 transaction1이 접근할 수 있는 것이다.
하지만 다음과 같은 경우에서는 문제가 발생 할 수 있다.
예: w1(P) -> w2(P) -> c2 -> abort1
transaction1 내에서 transaction2가 write, commit을 수행하고 난 후 rollback을 하게되는 경우이다. 이럴 경우 transaction2가 write한 결과가 사라지게되는 것이다. 따라서 이를 위해 commit 되지 않은 transaction들이 wrtie한 데이터를 읽지 못할 뿐만 아니라 쓰지도 못하게하도록한 schedule을 strict schedule이라고 한다.
- strict schedule: w1(P) -> c1/abort1 -> w2(P) -> c2
[reference]