[Database] - Transaction

Computer Science/DataBase

[Database] - Transaction

재한 2022. 12. 19. 17:24

📕Transaction

Correctness와 Consistency를 보장하기 위해 데이터베이스 처리 전체를 완료해야 하는 작업의
논리적 단위

📕Transaction 과 General Program의 차이

📕Terminlogy

📗트랜잭션의 종류

Read-only : 데이터베이스를 업데이트하지 않는 트랜잭션, 오직 읽기만 함.
Read-Write : update 하는 트랜잭션

📗트랜잭션 처리 개념의 주 용어

Data item : 저장하는 단위
- record(tuple), disk block , field value , file , database 전체가 될 수 있다.
- Granularity : data item의 크기
  - 이 값에 따라 lock의 범위가 달라짐.
  - 트랜잭션 처리의 concurrency를 결정함.
- Database : data items들의 집합

📗Transaction operation

b - begin transaction
r - read_item(X) :data item을 읽음.
w - write_item(x) : data item을 작성
e - end transaction
c - commit transaction
a - abort transaction

📕Transaciton States

BEGIN_TRANSACTION : transaction execution의 beginning
READ or WRITE : database item에 read or write operation 수행
END_TRANSCATION : transaction execution의 end
- 트랜잭션의 상태를 파악하기 위해 commited or aborted가 수행되어야 함
COMMIT_TRANSACTION : 트랜잭션의 성공적인 종료, 레코드가 변경된 것을 영구적으로 기록함
ROLL_BACK (or ABORT) : 트랜잭션의 정상적으로 종료되지 않음 -> 실행을 취소하고 원상복구

Partially committed : 사용자에게 더 빠른 반응을 하기 위해서
- DBMS는 각 트랜잭션 단위가 아닌 disk의 변경사항을 한꺼번에 반영
- concurrency control protocols의 일부는 추가적으로 가능한 commit을 확인
- recovery 일부는 실패 사항과 database에 끼치는 영향을 확인
Failed : checks 중 하나가 실패하거나 트랜잭션이 roll_back or abort 된 경우
- Failed 또는 abort 트랜잭션은 재시작된다.
- Partially committed -> Abort -> Failed의 대표적인 예 : Deadlock
Terminated : 트랜잭션이 시스템을 떠나는 것

📗Recovery가 필요한 이유

데이터가 소실 안 되는 것이 중요하다.

📗Committed

트랜잭션의 모든 operation이 성공적으로 완료되었고, 해당 변경사항이 database에 영구적으로 기록된 상태

📗Aborted (roll back)

트랜잭션이 database 또는 다른 어떤 트랜잭션에 영향을 주지 않은 상태

📕Causes of Failures

📗Failures

트랜잭션, 시스템 및 미디어 오류로 분류됨

📗Failures의 종류

computer failure
- hardware/software/network error는 트랜잭션이 실행되는 동안에 컴퓨터 시스템의 오류를 발생시킨다.
transaction or system error
- overflow, division by zero; 또는 유저의 방해
Local error or exception conditions detected by transaction : 예외적인 제외 조건
Concurrency control enforcement : 직렬화 위반 또는 deadlock 탐지로 인해
Disk failure : 오작동하는 disk block
physical problems and catastrophe : fire, theft, power failures

따라서 이러한 Failures들을 복구하기 위해 DBMS는 recovery system이 필요하다.

📕The System Log

트랜잭션 복구를 도와주는 방법
Failure로부터 복구하기 위해 dbms에 의해 유지 관리되는 시스템 로그
Database items의 value에 영향을 끼치는 transaction operations을 추적함.
Log buffer : logs를 기록하기 위해 사용하는 하나 또는 이상의 main memory buffer
- log entries로 가득 차는 경우 disk의 log file 끝에 append 함.
Log file은 주기적으로 Log file이 들어있는 저장공간에서 백업된다.
- catastrophic failures을 대비하기 위해서

📗Log records의 종류

[start_transaction, T]
[read_item, T, X] : X를 read
[write_tiem , T, X, old_value, new_value]
[commit, T]
[abort, T]
- T : 자동으로 생성된 고유 트랜잭션 식별자
- system crash가 발생하면 log를 확인하고 ARIES와 같은 recovery 기술을 이용하여
  consistent 한 database로 복구
UNDO operation : X에 old value를 다시 저장함.
- write operation의 영향을 backward로 되돌림
REDO operation: X에 new_value로 update
- log에는 update 기록이 남아있지만 failure로 인해 database에는 new_value가 update 되지 않는 경우에 수행
- forward action

📕Commit Point of Transaction T

해당 트랜잭션의 database에 접근하는 모든 operation이 성공적으로 완료되고, log에 모두 기록되었다면,
T는 committed 되었다고 합니다
[commit, T] -> commit record를 log에 write
Failure가 발생했을 때
- T의 commit record가 있지만, redo thier effect -> database에 반영되지 않은 경우
- start_transaction_record가 있지만, commit record가 없는 경우
  undo their effect(roll back) -> commit point까지 도달 못한 경우
Force writing : transaction을 commit 하기 전에 log buffer를 disk에 flush 함.
- 트랜잭션이 커밋 지점에 도달하기 전에 아직 디스크에 기록되지 않은 로그 부분을
  디스크에 기록함을 나타냅니다.
- 복구 중에 디스크에 저장된 로그 항목만 고려할 수 있음

📕ACID Properties of Transaction

모든 트랜잭션은 ACID 속성을 만족해야 한다.
- Atomicity : recovery subsystem이 책임
  - 트랜잭션은 processing의 atomic unit : All or nothing
- Consistency : programmer가 책임
  - 트랜잭션은 consistency를 보존해야 함.
- Isolation : concurrency control subsystem에 의한 시행
  - 트랜잭션은 다른 트랜잭션이 없는 것처럼, 방해받지 않고 독립적으로 실행되는 것처럼
    보여야 한다.
- Durability : recovery subsystem이 책임
  - committed transaction에 의해 적용된 변경 사항들은 database에 무조건 저장되어야 한다.
  - Failure에 빠지면 안 됨.

📕Schedules of Transactions

n개의 concurrent 한 트랜잭션 T1, T2,..., Tn의 schedule S
- transaction의 operations 순서
- 서로 다른 transaction의 operation(read/write)은 S에서 serial 하거나, interleaved 해야 한다.
  - serial : correctness ↑, 성능 ↓
  - interleaved(serail의 단점을 보완)
- example : S(a)의 interleaving two transactions T1, T2
  - S(a) : r1(X) ; r2(X); w1(X);r1(Y); w2(X); w1(Y);
  - non-serial 하다.

📗Total ordering of operations in S

S에 있는 2개의 opeartions 중에서 하나의 operation이 다른 operation 전의 무조건 일어나야 하는 경우
작업 순서가 명확함

📗Partial ordering of operations in S

특정 작업 간의 순서가 명확하지 않다.

📕Serial Schedule

Schedule S의 모든 transaction T의 모든 operations이 다른 operations의
interleaved operations 없이 연속적으로 실행되는 경우, 해당 schedule은 serial

T1의 operation이 실행되는 동안 T2의 operation이 실행되지 않음.

모든 serial schedule은 correct 하다.
- correct 하다의 의미는 error가 없다는 뜻.
serial schedule의 문제점
- 위 그림과 같은 경우 T2는 T1이 끝나야 실행된다.
  - 트랜잭션의 동시성을 제한
- 많은 트랜잭션이 있는 경우는 거의 사용이 불가능함.
해결책
- serial schedule과 비슷하게 동작하는 schedule을 사용해야 함.
- 동시에 처리할 수 있게 해야 함.
  - 하지만 동시에 처리하게끔 하는 것은 굉장히 어렵다.

📕Conflicting Operations in a (Nonserial) Schedule

Schedule에 있는 두 트랜잭션은 다음 조건을 만족하면 confilct가 발생한다.
- operations이 서로 다른 transaction에 존재
- operations이 동일한 Item X에 접근
- 적어도 하나의 operationㄴ은 write_item(x) 여야 한다.
  - read 끼리는 충돌이 일어나지 않음.
- 또한 operation의 순서 변경이 서로 다른 결과를 초래한다면 이는 conflict 하다.
  - r1(x); w2(x)!= w2(x); r1(x); or w1(x);x2(x)!= w2(x);w1(x)
Conflict의 두 가지 종류
- read-write
  - r1(w);w2(x)
- wrtie-write
  - w2(x);w1(x)
- 이러한 충돌을 방지, Concurrency control technique을 이용해서 correctness를 보장할 수 있다.

📜Quiz1

가정
- X=90, Y=90 , N=3, M=2
- 두 트랜잭션은 서로의 operation이 실행되는 동안 다른 트랜잭션에서 실행되지 않으므로 serial 하다.
- 스케줄 A를 실행하면
  - X=89, Y=93
- 스케쥴 B를 실행하면
  - X=89, Y=93
- T1과 T2의 순서를 바꿔도 결과는 동일한 것을 알 수 있다. -> Serial 한 것을 알 수 있다.
- T1 operations : 2개의 read와 2개의 write, T2 operations : 1개의 read, 1개의 write

📜Quiz2

X, Y, M, N값은 위와 동일
스케줄 C의 결과 : X=92, Y=93
스케쥴 D의 결과 : X=89, Y=93
스케쥴 C와 D는 Nonserial이지만,
스케쥴 D는 Serializable 하기 때문에 순서를 변경시켜도 결과가 동일하다.
read와 write가 하나의 pair로 수행되면 충돌이 일어나지 않는다.

📕Concurrency control problems

📗Lost update problem (갱신 손실)

두 트랜잭션이 동일한 데이터베이스 item에 접근할 때 interleaved 하게 operations이 수행되면
값의 손실이 일어나는 경우

T1이 write 한 값 위에 T2의 값이 덮어 쓰임(Overwrite) -> T1 입장에서는 lost

📗dirty read problem

하나의 트랜잭션이 데이터베이스 항목을 업데이트한 후 몇 가지 이유로 트랜잭션이 실패할 때 발생합니다.
업데이트된 항목이 원래 값으로 변경(또는 롤백)되기 전에 다른 트랜잭션에서 읽힙니다.

트랜잭션 T1이 실패하고 T2가 일시적으로 잘못된 X 값을 읽는 동안 X 값을 이전 값으로 다시 변경해야 합니다.
T2에서는 T1에서 write 하고 abort 된 dirty data를 read 한다.
X의 value를 old value로 복구해야 함.

📗Incorrect summary problem(Phantom read)

다른 트랜잭션이 이러한 아이템 중 일부를 업데이트하는 동안 한 트랜잭션이 여러 데이터베이스 항목에 대한 집계 요약 함수를 계산하는 경우
집계 함수는 값이 업데이트되기 전후에 요약을 계산할 수 있습니다.

T3는 A,... X and Y의 값들을 누적하려는 transaction
T1이 T3의 선택 조건에 매칭 되는 새로운 record를 삽입하는 경우 결괏값이 달라지게 되는 문제
즉 저 그림에서 기존 X에서 N이 빠진 값을 요약, 기존 Y에서 N이 더해지기 전에 값을 요약-> 문제 발생

📗Unrepeatable read problem

어떤 트랜잭션이 같은 item을 두 번 read 하려는데, 이 두 번의 read 사이에 다른 transaction의 영향으로 item의 값이 달려져 있는 문제

📕Serialize a (non-serial) schedule

이러한 문제점들을 해결하기 위해서 non-serial 하지만, Serializable 한 스케줄을 만들어야 한다.
-> good concurrency control이 필요하다.
하지만 모든 스케쥴을 serialized화 할 필요는 없다.
트랜잭션이 커밋되면 절대로 roll back X

만약 S1 : serial schedule , S2 is non-serial

-> 똑같은 결과를 만들어 낸다면 S2는 serializable 하다고 할 수 있다.

모든 값에 대해서 똑같은 결과를 만들어 내야 함.

해당 스케줄은 초기값이 100일때는 결과가 동일하지만 초기값이 100이 아니게되면 결과가 달라지게 된다.

📜Serializable schedule by example

📕A recoverable schedule

스케쥴은 복구하기 쉬운 것도 있지만 어려운 것도 있다.
- 때로는 불가능한 것도 있다. = nonrecoverable schedule
우리는 절대로 committed 된 트랜잭션을 복구하면 안 된다.

스케줄 S는 다음과 같은 경우 복구 가능하다고 정의한다.
- 스케줄에 있는 Transaction T가 T'의 모든 트랜잭션이 T가 읽은 item X를 write할때까지 커밋하지 않은 경우
트랜잭션 T는 스케쥴 S에 있는 T'를 읽는다. 만약 일부 item X가 T'에 처음 write 되고, T가 다음으로 읽는 경우
T'는 T가 item X를 읽기 전까지 절대로 abort 할 수 없다.
모든 트랜잭션 Ti와 Tj에 대해, Ti가 이전에 기록한 데이터 항목을 Tj가 읽었다면,
Ti의 commit 연산이 Tj의 연산보다 먼저 발생하는 스케줄

📜Recoverable test example

S(a) : r1(X);r2(x);w1(x);r1(Y);w2(x);c2;w1(Y);c1;
- is not incorrect but recoverable
Sc: r1(x);w1(x);r2(X);r1(Y);w2(X);c2;a1; -> dirty
- Sc의 문제점
  - T2 is commit but T1 is abort , -> X invalid
  - T2는 roll back을 해야 하지만, 이미 T2는 commit 했기에 복구 불가능하다.
    따라서 Sc는 nonrecoverable 하다.
Sa : r1(X);w1(x); r2(X); r1(y);w2(x);w1(y); c1;c2 -> correct
Se : r1(x);w1(x);r2(x);r1(Y);w2(x);w1(y);a1;a2 -> correct

📕Testing for serializability of a schedule

📜Example

네모 박스 친 부분에서 충돌이 발생할 수 있다.
충돌은 다음과 같은 조건을 만족해야 한다.
- 다른 트랜잭션에서의 operation
- operation은 같은 아이템에 접근해야 하고, 적어도 하나는 write이어야 한다.
하지만 위의 스케줄은 non-serializable 하다.

📕Serializability testing algorithm

precedence graph (PG) -> direct graph : 테스트하는 데 사용됨.
G = (N, E) : N= {T1, T2,,,. Tn} E = {e1, e2,,,.. em}
Schedule에서 Ti의 각 트랜잭션에 대해 하나의 노드가 생성
Tk에 있는 각각의 노드 ei의 형식 Tj-> Tk 1 <=j <=n, 1 <=k <=n, ei의 스타팅 노드 : Tj, Tk is end node
충돌하는 operation 쌍이 존재하는 경우에만 edge를 생성합니다.
Example
- Sc : r1(x) lw1(x);r2(X); r1(Y);w2(X);c2;a1; [dirty data read]

해당 스케줄은 graph에서 cycle이 존재하지 않을 때 serializable 하다고 할 수 있다.

📜testing example1

T1에서 write 한 뒤 T2에서 read를 하기에 conflict 발생 : 1->2

T2에서 write한뒤 T1에서 read 하기에 conflict 발생 : 2->1

T2에서 read X 후 T1에서 write X -> conflict 발생 : 2->1 edge

T1에서 write 후 T2에서 write -> conflict 발생 : 1->2 edge

T1에서 wrtie 후 T2에서 read X -> conflict : 1->2

📜testing example2

T2 write Y -> T3 read Y : conflict edge : T2->T3(Y)
T2 write Y -> T3 write Y : conflict edge : T2->T3(Y)
T1 write X -> T2 read X : conflict edge : T1 -> T2(X)
T3 write Y -> T1 read Y : conflict edge : T3 -> T1(Y)
T2 write Y -> T1 read Y : conflict edge : T2->T1(Y)

non serial schedules
why
- cycle 발생
  - T1->T2(X) , T2->T1(Y)
  - T1->T2(X), T2->T3(YZ) -> T3->T1(Y)

📜Testing example 3

T3 write (YZ) -> T2 read (YZ) : conflict 발생 edge : T3->T2(YZ)
T3 write(Y) -> T1 read Y : conflict 발생 , edge T3->T1(Y)
T1 write(Y) -> T2 read Y : conflict , edge : T1->T2(Y)
T1 write X -> T2 read X : conflict , edge : T1->T2(X)

스케줄은 cycle을 형성하지 않기에 serial 하다.

📜Testing example 4

T3 write Z -> T2 read Z conflict , edge : T3->T2(Z)
T3 write Y -> T2 read Y conflict , edge : T3->T2(Y)
T3 wrtie Y -> T1 read Y conflict, edge T3->T1(Y)
T1 write X -> T2 read X conflict, edge T1->T2(X)
T1 write Y -> T2 read Y conflict, edge T1->T2(Y)

📕Serializablity를 보장하는 방법

Concurrency Control (CC) protocols :
- Two -phase locking (2PL) : 가장 흔하게 사용하는 기법
  - concurrent transaction이 서로 방해하는 것을 방지하기 위해 data items에 lock을 검.
  - Two - phase :growing(acquiring), shrinking(releasing) on lock
  - Serializablity를 보장하는 추가 조건 적용
Snapshat isolation : less overhead than 2PL , used by some DBMSes;
- 트랜잭션이 시작될 때 데이터베이스 스냅숏에 있는 항목의 커밋된 값을 기준으로 트랜잭션이 읽는 데이터 항목을 봅니다.
- 팬텀 레코드 문제가 발생하지 않도록 합니다.
TimeStamp ordering
- 각 트랜잭션은 고유의 timestamp를 할당 받음.
- 프로토콜은 충돌하는 작업이 트랜잭션 타임스탬프 순서로 실행되도록 보장합니다.

저작자표시 (새창열림)