Transaction
하나 이상의 데이터베이스 조작 작업을 묶어서 원자적으로 실행되며, 성공 시에는 모두 반영되고 실패 시에는 모두 취소되는 논리적 단위
- 사용자 관점: 논리적인 작업의 단위
- 시스템 관점: 동시성 제어와 회복의 단위
트랜잭션 상태 전이도
ACID
| 속성 | 설명 |
|---|---|
| 원자성(Atomicity) | All or Nothing. 트랜잭션은 나누어져서는 안되는 작업들의 모음 |
| 일관성(Consistency) | 트랜잭션이 성공했다면, 데이터베이스는 그 일관성을 유지 |
| 고립성(Isolation) | 실행 중간의 결과가 노출되지 않아야 함 트랜잭션을 수행하는 도중에 다른 연산작업이 끼어들면 안됨 |
| 영구성(Durability) | 성공적으로 완료된 트랜잭션의 결과는 영구적으로 반영되어야 함 |
Concurrent execution
-
System throughput 증가
-
Transaction의 평균 응답 시간 감소
-
Concurrency control
- 동시에 실행되는 트랜잭션들의 실행 결과의 정확성을 보장
- 대신, 동시성을 도입했을 때, 오버헤드 이상의 효과가 필요
Schedule
- 프로그램으로서의 트랜잭션은 어떤 작업을 수행하고 다른 프로그램과 어떻게 상호 작용하는지를 이해하기 어려울 수 있음
- 스케줄러가 주로 주목하는 함수는 read(Q)와 write(Q)
- 트랜잭션은 로컬 버퍼에 있는 Q의 사본에 대해 read와 write 사이에서 임의의 순서로 작동할 수 있음
Serial Schedule
스케줄 1과 스케줄 2가 있습니다. 스케줄 1과 2내의 T1, T2 각각 모두를 시간 순으로 실행했을 때, A, B의 결과의 합이 모두 2,000으로 동일합니다.
T1, T2이 구분되어 한 트랜잭션이 종료되어야 다음 트랜잭션을 실행하는 것을 Serial schedule이라고 합니다.
Concurrent Schedule
Serial schedule은 리소스 사용률과 처리량이 낮습니다. 이를 개선하기 위해 두 개 이상의 트랜잭션이 동시에 실행하면 성능을 높일 수 있습니다.
대신, 동시에 실행함으로서 발생하는 연산 수행 과정의 주의점에 대해 살펴보겠습니다.
스케줄 3은 합이 이전과 동일한 2,000이지만 스케줄 4의 결과 합은 2,050으로 다른 값
스케줄 3과 4가 있습니다. 이전의 serial schedule과는 다른게 각각 내부의 트랜잭션은 다른 트랜잭션의 시작과 종료에 상관없이 동시에 실행됩니다.
결과값을 살펴보면 스케줄 3은 실행했을 때, A, B의 결과의 합이 2,000으로 순차적으로 실행했을 때처럼 결과 값이 올바릅니다.
하지만, 스케줄 4의 경우, 합이 2,050으로 잘못된 값이 생깁니다. 그 이유는 트랜잭션의 흐름이 한 가지가 아니라 파란색과는 반대 방향인 빨간 실행 흐름이 존재하기 때문입니다.
Serializability
직렬화 가능성
- Sc: Concurrent schedule, SS: Set of serial schedules
- 어느 Sc 의 실행 결과가 SS내의 한 schedule의 실행 결과와 동일할 떄, 이 Sc는 Serializable schedule이라고 합니다.
이전의 예시들로 말하자면, schedule 3은 직렬화 가능하다고 하고, schedule 4는 직렬화 불가능이라고 말할 수 있습니다.
Serializability는 여러 집합으로 표현 가능하지만 크게 2가지 종류로 나눌 수 있습니다.
serializable은 serial schedule과 순서가 변경하면 안되는 instruction 쌍이 동일하다를 의미
N개의 트랜잭션 중, 모든 트랜잭션들을 순회하며 올바른 결과를 도출하는 스케줄을 찾는 알고리즘의 시간 복잡도는 O(N!)입니다. 이는 NP-complete 문제로 다항 시간내에 찾을 수 없습니다.
그래서 올바른 결과를 도출하는 serializable한 스케줄을 모두 찾는 알고리즘 대신, 일부만 찾는 알고리즘이 존재합니다. 그러한 Conflict serializability에 대해서 살펴보겠습니다.
Conflict serializability
먼저, conflict와 conflict equivalent 개념을 정의하겠습니다.
Conflict
변경되면 안 되는 요소
Swapping은 스케줄 S1, S2가 서로 논리적으로 동일할 때만 가능합니다.
- Here, S1 = S2. That means it is non-conflict.
- Here, S1 ≠ S2. That means it is conflict.
Conflict equivalent
순서가 변경하면 안되는 instruction 쌍이 동일하다는 개념
다시 말해, conflict serializability는 conflict operations들인 read-write, write-read, write-write 간의 순서가 변경되지 않고 동일한 스케줄에서 발생하는 것을 의미합니다.
- 스케줄 S2는 serial schedule
- 스케줄 S1은 S1의 충돌이 없는 작업을 swap하여 serial schedule로 변환할 수 있음
Conflict operations
| Operation | Conflict 여부 |
|---|---|
| Read vs. Read | X |
| Read vs. Write | O |
| Write vs. Read | O |
| Write vs. Write | O |
- 오직 둘다 read인 경우에만 순서가 중요하지 않다는 것을 확인할 수 있습니다.
확인 방법
스케쥴 S의 non-conflicting instruction을 swap하여 스케쥴 S'로 만들 수 있으면 S와 S'은 conflict equivalent하다 합니다.
특수하게, 스케쥴 S가 serial schedule과 conflict equivalent하면, S는 conflict serializable하다고 말할 수 있습니다.
-
Precedence graph
G = (V, E)라 할 때,V는 스케줄에 참가하는 모든 트랜젝션의 집합E는 Ti → Tj 면서 아래 중 하나를 충족
- Ti가 write(Q)를 Tj가 read(Q)를 수행하기 전에 수행
- Ti가 read(Q)를 Tj가 write(Q)를 수행하기 전에 수행
- Ti와 Tj가 순차적으로 write(Q)를 수행
-
스케줄 S에 대한 precedence graph가 cycle이 없는 경우, S는 conflict serializable합니다.
한계점
스케줄 8, 9 모두 결과의 합이 올바릅니다.
하지만, conflict의 정의에 의해 둘다 Conflict serializable이 아닌 일반 serializable입니다.
이처럼 serializable 스케줄이지만 conflict schedule에 속하지 않을 수 있습니다.
하지만, conflict schedule인지 아닌지 판단하는 방법이 더욱 간단하기 때문에 사용합니다.
View serializability
모든 view serializability는 conflict serializability를 포함합니다.
Recoverability
회복 가능성
Recoverability란, 트랜잭션이 실패했을 때 회복가능성을 의미
- 즉, 트랜잭션은 atomicity가 보장되어야 하므로, 트랜잭션이 실패하면 트랜잭션 이전 상태로 복원될 수 있어야 함
Cascading rollback
- 하나의 롤백으로 인해 트랜잭션이 연쇄적으로 발생하는 것을 의미
cascadeless schedule
- cascade가 발생하지 않는 스케줄
- 모든 cascadeless schedule은 recoverable하다
Recoverable & Cascadeless Schedule 생성 방법
→ Commit 되지 않은 데이터에 대한 판독 금지
이어서 동시성 제어 방법에 대해 배워보겠습니다.