트랜잭션의 개념, 트랜잭션 스케줄, 직렬, 직렬가능(seializability), 회복가능(recoverablility)
1.1 트랜잭션 개념
- 하나의 논리적 작업을 수행하는 데이터베이스 연산 순서(sequence)
- 데이터를 접근하고 갱신하는 데이터베이스 프로그램의 논리적 수행 단위
read(A)
A := A - 50
write(A)
read(B)
B := B + 50
write(B)
위 예제는 read/write 연산만 사용한 단순화된 트랜잭션을 사용한 프로그램이다.
트랜잭션 관리
- 회복기능(recovery): 다양한 시스템 장애를 극복
- 동시실행(concurrent): 다수개의 트랜잭션을 동시에 수행 / 자원 활용성이 증가하고, 트랜잭션의 평균 응답시간이 감소한다.
ACID (트랜잭션의 성질)
Atomicity : All or nothing / 연산 모두가 수행되거나 어느 연산도 수행되지 않아야 함
Consistency : 단일 트랜잭션의 수행은 무결성을 지님 (트랜잭션을 잘 수행하면 상태 값이 맞아야 함)
Isolation : 다수의 트랜잭션이 동시에 수행되어도, 사용자는 하나 뿐이 수행된다는 느낌을 받아야 함
Durability : 완료된 트랜잭션은 후에 failure가 발생하여도 DB상태에 반영되어야 함
APAC (트랜잭션의 상태)
Active : 수행 중인 상태
Partially committed : 모든 문장이 실행된 상태 (완료를 위한 조치(로그 기록)는 아직 수행되지 않음)
Aborted : 시스템 고장, 트랜잭션 연산 오류 등으로 인하여 트랜잭션 수행 불가 상태
Committed : 성공적으로 완료를 위한 조치까지 수행된 상태
1.2 직렬가능 (Serializable)
- Conflict Serializable
- View Serializable
트랜잭션을 순차적으로 수행하는 직렬수행 방법(Serializable)은 항상 correct(Consistency성질)
- Concurrency Anomalies (틀린 실행 현상)
-dirty read (오손읽기)
완료되지 않은 값을 읽는 연산 / T₂가 읽는 값은 아직 완료되지 않아 T₁에서 철회함(이 경우, T2도 철회하여야 함)
-lost update (갱신손실)
T₂가 쓴 값을 T₁이 덮어쓰는 현상
-unrepeatable read(반복불가 읽기)
T₁입장에서 처음에 읽은 A값이 읽을 때마다 다른 값이 나오게 됨
Schedules (Histories)
동시적으로 수행되는 다수 트랜잭션에 속하는 연산이 수행된 시간적 순서 (트랜잭션의 모든 연산이 스케줄에 나와 있어야 함)
트랜잭션의 마지막 문장은 commit(성공) 또는 abort(실패)이어야 함
Serializable (직렬가능 스케줄)
스케줄이 직렬수행 스케줄 결과와 동일한 스케줄
예제
- Serial schedule
하나씩 수행하는 스케줄은 무조건 참 / 트랜잭션 전과 후에 값의 변화가 없음
그 외 다양한 스케줄 예제
각각 트랜잭션끼리 swap을 하여 결국 한쪽으로 몰았을때 serial schedule이 나오도록 (T1 <-> T2 이 동일해야 함)
- #1 schedule
Serial schedule은 아니지만, 효과가 Serial schedule과 동일
T₁과 T₂가 각각 A와 B 서로 다른 값을 보고 있기 때문에 상관 없음.
Read()~Write() 인 한 덩어리는 서로 교환해도 문제되지 않음
- #2 schedule
올바른 schedule이 아니다.
효과(결과값)가 Serial schedule과 같지 않음
Swap을 할 수 없음
- 스케줄에 관련된 트랜잭션 개수가 N 개 이면 가능한 직력 스케줄 후보는 N! 개
- N! 의 스케줄 중에서 적어도 하나가 직렬 스케줄과 같다면 해당 스케줄은 Serializability 함
- 스케줄 결과의 동일함을 정의하는 방식, 충돌직렬가능 스케줄 & 뷰 직렬가능성 스케줄
Conflicting Instructions 조건 (충돌 연산)
I₁ = read(Q), I₂ = read(Q) Don't conflict
I₁ = read(Q), I₂ = write(Q) conflict
I₁ = write(Q), I₂ = read(Q) conflict
I₁ = write(Q), I₂ = write(Q) conflict
conflict equivalent
한개의 연산이 쓰기 연산이면 두 연산은 서로 충돌(conflict)함 / 직렬실행 순서를 위한 Swap 불가
위의 조건에 따라 위치를 바꾸어 만든 스케줄S'이 직렬 스케줄이 나온다면 스케줄 S'은 충돌 직렬가능
View Serializability 조건 (뷰 직렬가능)
-
initial read: 스케줄 S의 T₁이 Q의 초기값을 read() 했다면, 스케줄 S'에서도 T₁은 Q의 초기값을 read() 함
-
same read: 만약 스케줄 S의 T₁이 T₂로부터 생성된 Q를 read 했다면, 스케줄 S'에서도 T₁은 T₂로부터 생성된 Q을 읽어야 한다.
-
final write: 만약 스케줄 S의 T₁이 final write(Q)를 했다면 스케줄 S'에서도 T₁이 final write(Q)를 해야 한다.
위의 조건에 부합하고 스케줄 S가 Serial schedule과 View equivalent하면 스케줄 S'는 뷰 직렬가능
연산이 더하기 빼기로 구성되어 있을 경우, 충돌 직렬가능 스케줄 & 뷰 직렬가능 스케줄이 모두 아님에도 연산결과 동일한 결과를 보일 수 있음 (더하기 빼기의 상호교환 특징 때문)
1.3 직렬가능 시험
충돌 직렬가능 시험
해당 스케줄이 Conflict Serializability 스케줄인지 판별하기 위해 선행 그래프를 사용하여 표현
예제
- #3 schedule
선행그래프에 사이클이 있으므로 Conflict Serializability 스케줄이 아님
- #4 schedule
선행그래프에 사이클이 없으므로 Conflict Serializability 스케줄
#4 schedule과 같이 다수개의 Transaction이 있을 때, 하나의 데이터에 대해 한방향으로 check하는 방법이 수월함
위상정렬(topological sort)는 부분 순서를 가지는 노드(트랜잭션)에 대하여 부분 순서를 만족하면서 전체 노드를 정렬하는 방식이다. (N!의 위상정렬이 가능함)
뷰 직렬가능 시험
NP-complete 영역의 문제이기에, 선행 그래프로 구할 수 없음
blind write(읽지 않고 쓰기)의 연산의 존재여부를 활용하여 check
1.4 회복가능
스케줄은 Serializable함과 동시에 복구 가능해야 함
회복가능 스케줄
예제
- #5 Schedule
T₉이 Commit을 했음에도 다른 T₈에서 Rollback을 한다면 T₉은 정상적으로 일을 마쳤음에도 Fail
이는 T₉ 트랜잭션의 Durable성질을 위배하는 것
연쇄 철회
예제
- #6 Schedule
트랜잭션의 isolation(분리성)이 제대로 지원되지 않아 철회하는 경우
T₁₀ -> T₁₁ -> T₁₂ 로 수행되었지만 T₁₀의 Rollback으로 인해 다른 트랜잭션이 모두 die
T₁₁, T₁₂은 dirty read (commit 되지 않은 값을 읽기) -> dirty read의 방지가 연쇄 철회를 예방avoids cascading aborts : 스케줄은 commit(완료)된 데이터 읽기만을 허용
스케줄 관계
RC: recoverable (회복가능 스케줄)
트랜잭션 중 하나가 failure 시 회복 가능
ACA: avoids cascadign aborts (연속 철회를 방지하는 스케줄)
write()이후에 read()만 하면 되는 것, write()직후에 무조건 commit을 함 -> commit 된 값만을 읽음
ST: strict (제한적인 스케줄)
write()연산 A 이후에 read()또는 write()연산 B가 수행된다면 A와 B 사이에 반드시 commit or abort 이 있어야함
ACA이지만 ST가 아닌 경우가 있으니 주의
SR: conflict serializable (직렬가능 스케줄) -> 다른 스케줄과 비포함 관계로 존재
