[Database] - Transaction

 

📕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를 할당 받음.
  • 프로토콜은 충돌하는 작업이 트랜잭션 타임스탬프 순서로 실행되도록 보장합니다.