Schedule과 Serializability

K가 H에게 H에게 20만원을 이체할 때, H도 ATM에서 본인 계좌에 30만원을 입금한다면 정말 여러가지 경우의 수로 실행될 수 있다.

여러 트랜잭션의 실행 경우의 수 중 위 그림과 같은 상황이라면, 문제가 발생한다.

3번에서 K가 H의 200만원을 읽었는데 중간에 H가 자신의 계좌에 30만원을 입금한 것이다.

K의 read 시점에는 200만원 이기때문에 20만원을 이체하고 commit하면 H의 30만원은 사라진다.

이러한 이상 현상을 Lost Update라고 한다.

schedule → conflict operations → conflict equivalent → conflict serializable 순서로 이해하려 한다.

Schedule

그림에서 1, 2, .. 5번과 같은 연산을 “operation”이라고 한다.

또, 여러 트랜잭션이 동시에 실행될 때, 각 트랜잭션에 속한 operation들의 실행 순서를 스케줄이라고 한다.

트랜잭션의 스케줄은 “여러 트랜잭션”을 동시에 처리하는 시간적 작업 순서를 의미한다.

즉, 그림 말고도 실행될 수 있는 다른 여러 케이스가 존재 할텐데, 그것들도 모두 스케줄이다.

• 각 트랜잭션에 속하는 operation들의 순서는 바뀌지 않는다.

쉽게 이해하기 위해서 두 개의 동일한 요청이 들어왔을 때, 하나의 스케줄링이 형성된다고 생각했다.

이 경우는 요청을 처리하는 서비스 로직이 하나의 트랜잭션을 갖고 있을 경우라고 생각한다.

Serial Schedule

직렬 스케줄은 DB에서 트랜잭션을 처리하는데 있어서 여러 트랜잭션이 순차적으로 하나씩 실행하는 스케줄을 의미한다.

즉, 트랜잭션이 동시에 실행되지 않고 한 트랜잭션이 완료된 후 다음 트랜잭션이 시작되는 방식이다.

따라서 각 트랜잭션이 독립적으로 실행되므로 데이터 무결성이 보장된다.

하지만 트랜잭션을 동시에 트랜잭션을 실행하는 기능을 활용하지 못하여 성능이 저하될 수 있다.

Non-Serial Schedule

비직렬 스케줄은 여러 트랜잭션이 동시에, 병렬로 실행되도록 하는 스케줄이다.

같은 시간이에 더 많은 트랜잭션을 처리할 수 있기 때문에 처리량이 증가하고 응답 시간을 단축할 수 있을것이다.

하지만 동시성을 제어하는 메커니즘이 없다면 무결성이 보장되지 않고 그림처럼 이상 현상이 발생할 수 있다.

Conflict

충돌은 DB 시스템에서 두 개 이상의 트랜잭션이 동일한 데이터에 동시에 접근하려고 할 때 발생하는 문제이다.

👀 두 operation이 3가지의 condition을 만족해야 conflict이다.

1. 서로 다른 transaction

2. 같은 data에 접근

3. 최소 하나는 write operation </aside>

충돌 유형은 다음과 같다.

1. 읽기-쓰기 (Read-Write)

   • 하나의 트랜잭션이 데이터를 read 하는 동안 다른 트랜잭션이 동일한 데이터를 write 하는 경우

2. 쓰기-읽기 (Write-Read)

   • 하나의 트랜잭션이 write 하는 동안 다른 트랜잭션이 동일한 데이터를 read 하는 경우

3. 쓰기-쓰기 (Write-Write)

   • 두 개 이상의 트랜잭션이 동시에 동일한 데이터를 write 하는 경우

충돌을 해결하는 방법은 이런게 있었다. 아직 다루지 않을 것이다.

1. 잠금 (Locking)

2. 타임스탬프 순서

3. 낙관적 동시성 제어

4. 직렬화 가능성 검사

Conflict Equivalent

두 개의 스케줄이 다음과 같은 조건을 만족하면 “conflict equivalent하다” 라고 한다.

2개의 condition을 모두 만족하면 conflict equivalent이다.

1. 두 Schedule은 같은 트랜잭션을 가진다.

2. 어떤 conflicting operations의 순서도 양쪽 schedule 모두 동일하다.

1번 조건은 무슨 얘기일까?

같은 트랜잭션을 가진다는 의미는 스케줄에 포함된 트랜잭션들이 동일한 트랜잭션이라는 것을 의미한다.

즉, 트랜잭션 T1, T2.. 가 스케줄 S1, S2에 모두 존재한다는 것이다.

Ex)

T1 : R(1), W(1)

T2 : R(2), W(2)

S1 : T1(R(1), W(1)) → T2(R(2), W(2))

S2 : T2(R(2), W(2)) → T1(R(1), W(1))

예시로 나타냈지만 실제로 트랜잭션의 실행 순서는 다를 수 있다.

S1 : R(1) → R(2) → W(2) → W(1)와 같이.

그럼 2번 조건은?

충돌 등가성은 두 스케줄이 충돌하는 연산의 순서가 동일한 경우를 얘기한다.

• 여기서 말하는 동일한 트랜잭션 순서는 트랜잭션의 호출 순서를 얘기하는 것이 아니라, 충돌이 발생하는 작업의 순서를 얘기하는 것이다.

즉, 두 스케줄이 서로 다른 순서로 실행되더라도 결과는 동일하다.

충돌 동등은 스케줄이 동일한 결과를 생성한다는 것을 보장함으로써 DB 시스템은 동시 트랜잭션이 존재하는 경우에도 데이터 일관성을 유지하고 직렬화 이상 현상을 방지할 수 있다.

직렬화 이상 현상은 non-serial schedule에서 발생하는 이상 현상을 얘기한다.

🌟 Conflict serializable

아래 조건을 만족하면 Conflict serializable 하다.

1. 다른 Serial Schedule과 Confilct equivalent 일 때.

충돌 직렬은 직렬 스케줄 + 충돌 등가성이다. 직렬 스케줄은 트랜잭션을 순차적으로 하나씩 실행한다고 했다.

따라서 Conflict serializable은 여러 트랜잭션이 동시에 실행되더라도 트랜잭션이 순차적으로 실행된 것과 동일한 결과를 보장할 수 있는 스케줄을 얘기한다.

Ex)

T1 : r1(k) → w1(k) → r1(h) → w1(h)

T2 : r2(h) → w2(h)

schedule1 : r1(k) → w1(k) → r2(h) → w2(h) → t2 commit → r1(h) → w1(h) → t1 commit

schedule2 : r2(h) → w2(h) → t2 commit → r1(k) → w1(k) → r1(h) → w1(h) → t1 commit

실행 흐름을 보면 스케줄 2는 트랜잭션이 순차적으로 실행되는 직렬 스케줄이다.

스케줄 1은 딱 봐도 직렬 스케줄이 아니고 non-serial schedule이다. 하지만 충돌 직렬 가능성 조건을 만족하기 때문에

Conflict serializable 하다.

UnRecoverable Schedule

아래 그림은 어떤 결과가 발생할까?

트랜잭션 2번이 롤백되면서 h를 다시 200만원으로 돌려놔야 한다. 하지만 k는 100만원에서 20만원이 사라졌다.

트랜잭션 2번의 5번의 write(h) 작업이 롤백으로 이해 더 이상 유효하지 않기 때문에 트랜잭션 1번에서의 6, 7번 작업도 롤백 되어야 한다.

하지만 트랜잭션 1번은 이미 commit 된 상태이지만, 영속성(durability) 때문에 롤백을 할 수 없다.

• durability : 한 번 commit된 트랜잭션은 rollback 될 수 없다.

이렇게 스케줄 내에서 롤백된 트랜잭션이 수행한 write 작업을 commit된 다른 트랜잭션이 읽은 스케줄을 unrecoverable schedule 이라고 한다.

롤백을 해도 이전 상태로 회복이 불가능하기 때문에 이런 스케줄은 DBMS가 허용해서는 안된다.

트랜잭션 스케줄이 unrecoverable 상태가 되면, 어떤 트랜잭션이 실패하거나 취소되었을 때, DB를 일관성 있는 상태로 복구할 수 없는 경우이다. 회복이 불가능하다.

따라서 우리는 recoverable한 스케줄을 허용 해야한다.

🤔 그럼 어떤 스케줄이 recoverable 할까?

Recoverable Schedule

회복 가능한 스케줄이 되기 위해서는 트랜잭션의 commit 순서가 중요하다.

그림을 보면 트랜잭션 1번이 트랜잭션 2번 안에서 operation을 수행하면서 의존하고 있다.

1. 2번 트랜잭션이 먼저 commit

2. 만약 2번 트랜잭션이 rollback 한다면, 먼저 롤백하고 트랜잭션 1번도 같이 abort 하여 롤백 시킨다.

즉, 한 트랜잭션이 다른 트랜잭션의 결과를 read 할 때, read 했던 트랜잭션이 커밋된 경우에만 해당 트랜잭션이 커밋될 수 있도록 한다.

Cascading Rollback (Cascadeless Schedule)

recoverable의 두 번째 그림처럼 하나의 트랜잭션이 rollback 하면, 이를 의존하는 다른 트랜잭션도 rollback 해야한다. 이는 여러 트랜잭션의 rollbakc이 “연쇄적”으로 발생하면서 처리하는 비용이 많이 든다.

이를 해결하기 위해 write 작업을 한 트랜잭션이 commit or rollback을 한 뒤에 read를 수행하는 스케줄만 허용하자 라는 방법이 나온다. 즉, 한 트랜잭션이 커밋되기 전까지 다른 트랜잭션이 그 트랜잭션이 수정한 데이터를 읽을 수 없도록 하는 방식이다. 이러한 방식으로 설계한 스케줄을 cascadeless schedule 이라고 한다.

Strict Schedule

그렇다면 위에서 소개한 cascadeless schedule은 문제가 없을까? 🤔

Ex) 3만원인 피자가 있다. 하지만 K는 1만원으로 수정하고, H는 2만원으로 수정하려고 한다.

그림의 스케줄에서 한 트랜잭션에서 write를 하고 commit 하지 않은 데이터를 다른 트랜잭션에서 read 하지 않기 때문에 cascadeless schedule이라고 볼 수 있다.

하지만 트랜잭션 1번이 rollback 되면서 트랜잭션 2번의 commit이 적용되지 않는다. (그대로 3만원)

이를 보강한 스케줄이 Strict Schedule이다. 위에 있는 그림은 Strict Schedule은 아니다.

한 트랜잭션이 커밋되기 전까지 다른 트랜잭션이 그 트랜잭션이 수정한 데이터를 읽을 수도 +쓸수도 없도록 하는 방식이다. (🔥 read, write 전부 불가능)

그럼 Strict으로 변경해보자.

Strict Schedule은 rollback 할 때 recovery가 쉽다.

Summary

성능으로 인해 여러 트랜잭션들을 동시에 실행해야 한다. (non-serial schedule)

하지만 이로인해 이상 현상이 발생하는 것을 피해야한다. 따라서 conflict serializable (충돌 직렬 가능성)한 non-serial schedule을 허용한다.

그럼 이를 RDB에서 어떻게 구현할까? 🤔

1. 여러 트랜잭션이 실행될 때마다 스케줄들이 conflict serializable 한지 확인한다.

→ 이 방법은 요청이 많다면 비용이 많이 들 수 있다.

1. 여러 트랜잭션을 동시에 실행해도 스케줄이 conflict serializable 하게 보장하는 프로토콜 사용

→ 아예 conflict serializable한 스케줄만이 실행되도록 보장하는 프로토콜을 적용하는 방법.

이 방법이 가장 많이 사용된다고 한다.

그 어떤 스케줄도 serializable 하게 동작하도록 하는 것이 concurrency control이다.

이것이 트랜잭션의 Isolation의 속성이 많이 연관되어 있다. 너무 엄격한 isolation은 성능을 저하시킬 수 있다.

이를 완화하려고 한 것이 isolation level이다.