동시에 여러 트랜잭션이 실행되는 것은 많은 장점이 있다.

• 단위 시간당 처리할 수 있는 트랜잭션의 증가 : cpu, disk 사용량의 증가
• 응답시간의 감소 : 짧은 트랜잭션은 긴 트랜잭션이 끝날 때까지 기다릴 필요가 없다.

하지만 이때에도 가장 중요한 것은 database의 consistency를 계속해서 유지해야한다는 점이다. 이를 위한 것이 Concurrency Control Schems이다.

Schedule

동시성 제어를 위해서는 실행되는 여러 트랜잭션의 명령어들을 제어해야합니다. 이때 시간의 흐름에 따라 실행되는 명령어의 순서를 schedule이라고 합니다.

• 성공적으로 실행을 마친 트랜잭션은 commit 명령을 마지막에 수행해야합니다.
• 반대로 끝까지 실행에 실패한 트랜잭션은 abort 명령을 마지막에 수행해야합니다.

Serial Schedule

Serial Schedule이란 N개의 트랜잭션이 실행될 때 각 트랜잭션이 순선대로 실행되는 Schedule입니다. 이 방식은 databse consistency를 지킬 수 있지만 응답시간이 길어집니다.
두 개의 트랜잭션 T1, T2 가 있을 때 가능한 Serial Schdule은 2개 입니다.

Schedule 3

다음과 같이 Schedule 3은 Serial한 Schedule은 아니지만 Schedule 1과 equivalent하다고 말할 수 있습니다. 그 이유는 T1의 명령어를 위로 T2의 명령어를 아래로 이동 시키면 Schedule 1과 동일합니다.

Schedule 4

다음과 같은 Schedule 4는 A + B의 값을 보존하지 못한다. 즉 결과값의 consistency를 유지하지 못한다. 하지만 이런 방식으로 Schedule의 정확성을 검증하는 것은 시스템이 복잡해질 수록 어렵다. 그렇기 때문에 다른 방식으로 Schedule의 정확성을 판단해야 하는데 Serializability를 기준으로 판단할 수 있다.

Serializability(직렬화 가능성)

각 트랜잭션은 database consistency를 유지해야한다. 이때 any Serial Schedule이라면 databse consistency를 유지할 수 있다.

따라서 어떠한 Schedule이 Serial Schedule과 equivalent하다면 그 Schedule은 Serializable하다고 할 수 있다.

Conflicting Instructions

Conflict Serializability

만약 Schedule S가 Schedule S'로 NON-CONFLICTING 명령어들을 SWAP해서 변경가능하면 S와 S'는 conflict equivalent 하다고 할 수 있다.
그리고 S'가 serial schedule이라면 S는 conflict serializable이라고 할 수 있다. Schedule 3은 은 conflict serializable하다. 왜냐하면 read(B), write(B) 는 read(A), write(A)는 NON-CONFLICT한 Instructions이기 때문에 swap 가능하다.

<T1,T5> 혹은 <T5,T1>으로 직렬화가 불가능하다. 왜냐하면 T1 , T2 의 명령어들이 서로 CONFLICT하기 때문이다. 하지만 해당 트랜잭션은 송금이라는 응용면에서는 정확성을 보장한다. 그렇지만 Serializablilty 관점에서는 옳지 않다. 따라서 datbase system은 Serializability를 만족하지 못하는 Scheudle은 Accept해서는 안된다.

Recoverable Schedule

그리고 databse system에서 data consistency 만큼 중요한 것이 복구 가능성이다. 언제 오류가 발생할 지 모르기 때문에 항상 데이터를 복구 가능해야 합니다.

이를 정의하면, 만약 Tj가 Ti가 쓴 data를 읽는다면, Ti의 commit은 Tj의 commit보다 먼저 이루어져야 복구가능한 schedule이라고 할 수있다.

그런 관점에서 다음 Schedule은 복구 가능하지 않다. 왜냐하면 T9는 T8이 write한 데이터 A를 read하고 있는데 T9의 commit이 먼저 이루어졌기 때문이다. 이렇게 되면 T8이 이후에 abort가 되면 T9는 inconsistent한 data를 읽은 것일 수 있기 때문이다.

• commit 되지 않은 data를 dirty data라고 한다.

Cascading Rollbacks

cascading rollback이란 한 transaction이 오류로 인해 rollback 될
때 나머지 transaction도 연쇄적으로 rollback 되는 것을 의미한다.
다음과 같은 Schedule을 보면 recoverable하다. 하지만 T10이 abort된다면 T10이 WRITE한 A를 READ, WRITE하는 T11이 rollback 될 것이고 마찬가지로 T12도 rollback될 것이다. 즉 cascading rollback을 막기위해서는 dirty data를 read해서는 안된다.

Cascadeless schedules

• cascading rollack이 발생하지 않는 Schedule.
• 모든 cascadeless schedule은 recoverable하다.
• recoverable하기만 해도 좋지만 cascadeless한 schedule이면 더 좋다.

결론

database system은 스케줄링 할 때 반드시 serializable해야하고 recoverable schedule을 작성해야 한다. 그리고 cascadeless하면 더 좋다!

---

출처
임팔라 쵝오