Schedule(스케줄)
여러 트랜잭션들이 동시에 실행될 때, 각 트랜잭션에 속한 명령들의 실행순서를 말한다.
위 사진에서 'r'은 Read, 'w'는 Write, 'c'는 Commit 명령을 말한다.
명령 옆에 숫자는 트랜잭션의 아이디를 말한다.
괄호 안에 들어있는 것은 데이터를 의미한다.
Case4를 예로 들어보자.
- r1(K): 트랜잭션1이 K에 있는 데이터를 읽어온다.
- w1(K): 트랜잭션1이 K에 데이터를 쓴다.
- r1(H): 트랜잭션1이 H에 있는 데이터를 읽어온다.
- r2(H): 트랜잭션2가 H에 있는 데이터를 읽어온다.
- w2(H): 트랜잭션2가 H에 데이터를 쓴다.
- c2: 트랜잭션2를 커밋한다.
- w1(H): 트랜잭션1이 H에 데이터를 쓴다.
- c1: 트랜잭션1을 커밋한다.
여기서 기억할 점은
각각의 트랜잭션(1, 2...) 내의 명령들의 순서는 바뀌지 않는다.
즉, 스케줄 번호에 상관없이 아래 순서는 동일하다.
트랜잭션1: r1(K) -> w1(K) -> r1(H)...
트랜잭션2: r2(H) -> w2(H) -> c2
Serial schedule
트랜잭션들이 겹치지 않고 한 번에 하나씩 실행되는 스케줄
Read/Write 작업은 I/O 작업이다. 디스크에서 데이터를 가져오고 가져온 데이터를 다시 디스크에 저장하는 작업을 진행한다. 그 동안에는 CPU가 일을 하지 않는다.
Serial schedule의 경우 한 번에 하나의 트랜잭션만 실행한다.
그래서 잘못된 데이터를 만들 일이 없다.
하지만 한 번에 하나의 트랜잭션만 실행되기 때문에 TPS가 좋지 않다.
현실적으로 사용할 수 없는 방식이다.
Nonserial schedule
트랜잭션들이 겹쳐서(interleaving) 실행되는 스케줄
Serial schedule과 달리 하나의 트랜잭션에서 I/O 작업을 하고 있을 때,
또 다른 트랜잭션을 실행하여 작업을 진행한다.
트랜잭션들이 겹쳐서 실행되기 때문에 동시성이 높아져서
같은 시간 동안 더 많은 트랜잭션들을 처리할 수 있다.(TPS가 높다.)
하지만 Nonserial schedule은
트랜잭션들이 어떤 형태로 겹쳐서 실행되는지에 따라
원치 않는 결과가 나올 수 있다.
해결할 점
성능을 위해 여러 트랜잭션들을 겹쳐서 실행할 수 있으면서도 정확한 결과가 나오게 해야한다.
-> NonSerial Schedule로 실행해도 잘못된 결과가 나오지 않을 수 있는 방법이 필요하다.
아이디어 : Serial schedule과 동일한 NonSerial schedule을 만들자.
-> schedule이 동일하다는 의미가 무엇인지부터 정의하는 것이 필요하다.
사전지식
Conflict(충돌)
두 개의 명령(Operation)이 아래의 세 가지 조건을 모두 만족하면 Conflict라고 한다.
- 서로 다른 트랜잭션 소속
- 같은 데이터에 접근
- 최소 하나는 write 명령
예시)
r2(H)와 w1(H)은 서로 다른 트랜잭션이고 같은 데이터 H에 접근한다.
트랜잭션1은 Write를 하고 있고 트랜잭션2는 Read를 하고 있다.
따라서 두 명령은 Conflict 상태이다. -> Read-Write Conflict
w2(H)와 w1(H) 또한 서로 다른 트랜잭션,
같은 데이터 H에 접근, 둘 다 Write를 하고 있으므로
Conflict 상태이다. -> Write-Write Conflict
Conflict가 중요한 이유는 순서가 바뀌면 결과도 바뀌기 때문이다.
만일 w2(H)가 먼저 실행되어 H가 230이 되고 그 다음 r1(H)가 실행되면 r1(H)는 230을 읽어온다.
반면, r1(H)가 먼저 실행되면, r1(H)는 H로부터 200을 읽어오고 그 다음 w2(H)에 의해 H가 230이 된다.
정리하면 첫 번째 경우에는 r1(H)는 230, 두 번째 경우는 r1(H)가 200을 읽어오게 되는 것이다.
Conflict equivalent
conflict의 개념을 가지고 스케줄의 동일성을 정의한다.
Conflict equivalent는 두 개의 스케줄이 두 조건을 모두 만족할 경우이다.
- 두 스케줄은 같은 트랜잭션들을 가진다.
- Conflict Operations의 순서도 양쪽 모두 동일해야 한다.
예시 1)
트랜잭션1은 20만원을 이체하는 트랜잭션이고
트랜잭션2는 30만원을 입금하는 트랜잭션이다.
스케줄 3, 4는 동일한 트랜잭션1, 2를 가지고 있다.
-> 1번 조건을 만족
Conflict가 발생하는 operation의 순서가 동일하다.
-> 스케줄3: r2(H) -> w1(H)과 스케줄2: r2(H) -> w1(H)로 일어나는 순서가 동일.
-> 이외의 Conflict Operation들의 순서도 모두 동일
따라서 스케줄2와 3은 Conflict equivalent하다.
여기서 더욱 자세히 보면, 스케줄2는 Serial Schedule이다.
반면, 스케줄3은 NonSerial Schedule이다.
이를 Conflict Serializable이라고 부른다.
이때 스케줄3은 NonSerial Schedule임에도 불구하고
Serial schedule과 같이 정상적인 결과를 낼 수 있다.
예시 2)
트랜잭션1은 20만원을 이체하는 트랜잭션이고
트랜잭션2는 30만원을 입금하는 트랜잭션이다.
두 스케줄 모두 같은 트랜잭션을 가지고 있.
하지만 스케줄4에서는 r1(H) -> w2(H)로 실행되고
스케줄2에서는 w2(H) -> r1(H)로 실행된다.
순서가 서로 바뀌어 있기 때문에 Conflict Equivalent하지 않다.
스케줄1도 Serial schedule이기 때문에 스케줄4가 Conflict Equivalent가 될 가능성이 있다.
하지만 비교를 해보면
스케줄4: r2(H) -> w1(H)
스케줄1: w1(H) -> r2(H)이다.
Conflict Equivalent 하지 않다.
스케줄4번은
serial schedule인 1,2 모두와
conflict serializable할 수 없고
원치 않는 결과가 나오는 스케줄이다.
정리하면 해결책은
Conflict serializable한 NonSerial schedule은 허용
하면 된다.
하지만 RDBMS에서 Conflict Equivalent인지
확인하는 방법으로 문제를 해결하지는 않는다.
대신 여러 트랜잭션을 동시에 실행해도
스케줄이 conflict serializable을 보장하는
프로토콜을 적용하는 방식으로 구현한다.
결국 Concurrency control의 목적은
어떠한 스케줄도 Serializable하게 만들어주는 것이다.
그리고 Serializable을 실현시켜주는 속성이 Isolation 이다.
출처
