[CS][데이터베이스 시스템 3판] Chapter16. Transaction Processing Concepts

 

 

 

Single-User VS Multi-User Systems

• single-user systems : DBMS에 동시에 한 사람만 access 할 수 있는 시스템
• multi-user systems : DBMS에 동시에 여러 사람이 access 할 수 있는 시스템

 

 

 

Transactions

• transaction은 DBMS의 추상적인 view이다.
  • read와 write 순서를 포함하는 DB 처리의 logical한 unit
• DBMS에서의 논리적인 처리 단위(unit)
  • read, write 오퍼레이션으로 이루어져 있음
  • read 오퍼레이션은 변화 X
  • write 오퍼레이션은 변화 O
• Concurrent execution이 DBMS에 필수적이다.
  • usability : 사용자들이 동시 access을 원해서
  • performancd : 디스크 접근 속도가 상대적으로 느려서 여러 사람이 동시에 작업하여 CPU humming을 유지하는 것이 중요하다

 

 

 

Concurency in a DBMS

• 사용자는 각 transction을 자체적으로 실행한다고 생각할 수 있다
• Concurrency은 다양한 transaction 작업을 interleaving하는 DBMS에 의해 지켜진다.
• transaction이 시작될 때 DB가 consistent한 경우 각 transaction은 DB를 consistent하게 유지해야 한다.
• DBMS은 IC를 시행한다
• DBMS은 데이터의 의미를 이해하지 못한다 (Ex. 이자 계산 방법)

 

 

 

Reading Uncommitted Data ("Dirty reads")

• 완료되지 않은 데이터를 읽음
• write가 일어나면 dirty를 세팅해야 한다.
• dirty bit
  • 값이 변경되었으나 저장소에는 저장되지 않은 비트
  • 변경되었는지 알기 위해 하드웨어 차원에서 다루는 개념이다
  • parity bit로 변경된 것을 알아챈다
  • 메모리에 write 요청이 있다면 변경으로 간주한다
  • write가 있을 때 dirty bit 설정을 한다 → 실제로는 값이 변경 안되었을 수도 있다
• dirty read ★★
  • 다른 transaction에 의해 수정은 됐지만 아직 commit 되지 않은 데이터
  • transaction에서 uncommitted data를 읽을 때 발생할 수 있는 문제
  • commit : 완료가 되었다 (수정 불가)
  • 누군가가 write 한 것을 read 할 때 생길 수 있는 문제

 

 

 

Summary

• DBMS는 concurrent하게 transaction을 시행해야 한다.

1. 여러 개의 transaction에서 연산이 interleave 될 수 있다.
2. 작업을 interleaving하면 이상 현상이 발생할 수 있다
3. 이걸 피하기 위해 동시성 제어가 필요하다.
4. operation을 interleaving하면 anomaly(이상현상)이 발생할 수 있다.
5. 이런 anomalies를 피하기 위해 concurrency control이 필요하다.

 

 

Atomicity of Transactions

• transaction은 모든 작업을 완료한 후 commit되거나 일부 작업을 실행한 후 aobrt(중단) 될 수 있다.
• transaction의 원자성
  • DBMS가 보장해주어야 하는 것
  • transaction은 더이상 쪼갤 수 없는 logical atomic하다.
• 사용자는 transaction을 아래와 같이 생각할 수 있다.
  1. 항상 모든 작업을 실행한다.
  2. 아무런 작업도 실행하지 않는다.
• 하나의 transaction은 중간에 끊어질 수 없다
  • 만약에 fail이 나서 중간에 끊어지면? → 해당 transaction 하기 전으로 되돌아 가야 한다
  • all or nothing = 다하거나 아예 안하거나
  • 다 했다 = commit, 돌아갔다 = abort/rollback
  • rollback은 개발자가 못하면 DBMS가 해주어야 한다
  • 만약 read transaction이면 돌아가든 안가든 상관 없지만 write transaction이면 돌아가 줘야 한다.

 

 

 

Recovery is neede in DBMS

• Failure의 종류
  • Computer failure (system crash)
  • Transaction or system error
  • Local errors or exception conditions raised
  • Concurrency Control enforcement
  • Disk failure
  • Physical problems

• DBMS에서는 회복하는 시스템이 필요하다
  • DBMS는 un-committed 된 transaction의 작업을 undo(취소) 할 수 있도록 모든 작업을 기록(log)한다
  • log를 효율적으로 남겨야 한다 → 이걸 DBMS가 시스템을 개발해야 한다.

 

 

 

Transaction states and Transition Diagram

• Transaction States
  • Active : transaction 시작, read&wirte 가능
  • Committed : transaction이 발행한 commit operation
  • Aborted : transaction이 실패했거나 중단 작업을 발행
  • Treminated : transaction이 완료되고 system에서 종료

 

 

 

ACID Properties of Transaction

• ACID를 유지하도록 Processing 해주어야 한다

1. Atomicity
   • transaction 처리는 항상 transaction이 항상 atomic 한 것을 DBMS가 guarantee 해주어야 한다
   • 모든 연산이 실행되든지 실해되지 않든지
2. Consistency
   • transacton은 항상 일관성을 유지해야 한다 = integrity를 보장해야 한다
   • transaction가 시작하기 전에 consistent하면 transaction을 처리하고 나서도 consistent 해야 한다
   • transaction 중간에도 consistent 해야 한다는 것은 아니다
   • 그렇지 않으면 DBMS가 inconsistent한 결과를 가질 수 있다
3. Isolation
   • 한 transaction의 수행은 다른 transaction과 independent 해야 한다.
   • 사용자는 동시 수행 중인 다른 transaction의 영향을 고려하지 않고 transaction의 수행 결과를 이해할 수 있어야 한다.
   • transaction의 수행이 불필요하게 다른 transaction에게 방해(interfere) 받으면 안된다
   • 정당한 interfere은 방해 받아도 된다
4. Durability
   • transaction이 성공적으로 완료하였다는 것을 사용자에게 통보하자마자 그 transaction의 효과가 디스크에 반영되기 전에 시스템 장애가 발생한다 하더라도 지속적으로 남아 있어야 한다.
   • 어떤 commit된 transaction에 의한 변화는 DB에서 persistent 해야 한다
   • transaction이 끝난 작업은 DB에 견고하게 있어야 한다
   • change를 했다면 DB에 change 된 것으로 남아 있어야 한다
   • commit 되지 않은 것에 대해서는 durability를 논하지 않는다

 

 

 

Schedule of Transactions and Serializability

• transaction schedulig : operation의 순서를 정하는 일, concurrency control 하는 것, serializable 하게 하자
• serializable : serial 하도록 할 수 있는, ↔ parallel,
  • serial : 직렬, 하나 다음에 다른 하나 오고, 두 개가 같이 들어오지 않음, 줄을 세워 하나씩 순서를 매김, 순차 수행
• 하지만 우리는 concurrency processing 해야 하므로 실제로는 하나하나씩 처리하지 않는다
• 그러나 마치 하나 처리하고 하나 처리하는 것처럼 보이게 한다 = serial processing처럼 보이게 한다

• serial schedule
  • serial processing으로 schedule 하는 것
  • transaction operation끼리 섞이지 않는다.
  • 서로 다른 transaction 작업이 interleave되지 않는다.
• serializable schedule
  • 사실 serial schedule은 아니지만(Interleaving 되었지만), 어떤 serial schedule과 같아지는 schedule, transaction을 하나씩 수행한 것 같은 schedule
  • transaction의 일부 serial 실행

 

 

 

Conflict Serializable Schedules

• conflict 하는 경우
  • 다른 transaction에 속한다.
  • 같은 item에 접근한다.
  • operation 중 하나는 W(X)이다.
• conflict equivalent 하는 경우
  • 동일한 transaction의 동일한 operation으로 이루어진다.
  • 두 완료된 transaction의 conflict operation이 두 스케줄에서 동일한 순서로 나타날 때
• “conflict 측면에서 serializable이다” 라는 이론이 등장한다
  • serial schedule에서 conflict한 operation이 나타나야 충돌이 난다.
• Schedul S가 conflict serializable 하다.
  • S가 일부 serial schedule에 conflict equivalent 할 때
  • conflict한 operation을 찾을 수 있을 때
• 모든 conflict serializable schedule은 serialize 하다.
• 어떤 serial schedule과 같다 = DB에 저장되는 값들이 같다 = result equivalant
  • 위를 따지는 것이 transaction이 많아지면 알아내기 어렵다
• 만약 operation이 read만 있다면 DB에 저장되는 값들이 항상 같다
• 만약 operation에 write가 있다면 해당 operation에서 위치가 중요해진다
  • write가 나와야 concurrency scheduling을 논할 수 있다

 

 

 

Dependency Graph

• transaction을 graph로 modeling 한 것
• node와 link로 표현
• node = transaction
• link = edge = T1과 T2에게 conflict operation이 있을 때, 먼저 conflict가 나타난 곳에서 화살표가 출발한다.
  • Ex. Ti의 연산이 먼저이고 Tj의 연산과 충돌하는 경우 Ti에서 Tj로 edge를 그린다.

 

 

 

Lock-Based Concurrency Control

1. Two-phased Locking (2PL) Protocol

• 이 규약을 지켜 scheduling하면 항상 conflict serializable schedule을 만들어 준다. (제일 좋다고는 말 못하지만)
• lock : access를 control하기 위해, resource를 control하기 위해서
• locking mechanism을 사용한다 = lock을 걸고, 푸는 것을 부가적으로 하겠다
• 2가지 종류 : read 하기 전에 read lock, write 하기 전에 write lock → 끝나면 unlock 필요
  • read lock : 서로 공유 가능하다, = shared lock
  • write lock : 서로 공유 불가능하다, 핵심, = exclusive lock = X lock
• 3가지 조건
  1. 각 transaction은 read 전에 object에 대해 shared lock을 하고 wrtie 전에 object에 의해 exclusice lock을 해야 한다.
  2. unlock한 transaction은 다시 lock을 하지 않는다
     • unlock을 2-phase locking으로 한다 → locking 하는 phase, unlocking 하는 phase
  3. 누군가가 x lock을 가지고 있다면 다른 애는 x, shared lock을 가지지 못한다
  4. 누군가가 shared lock을 가지고 있다면 다른 애는 x lock을 가지지 못한다
  • 순서 제어가 되기도 한다
• locking을 쓰면 dead lock이 나올 수 있다.
• first face를 growing face라고 부른다. second face를 shrinking face라고 부른다.
  • growing face : transaction이 Lock을 얻어가는 단계
• 2PL은 serializable schedules의 conflict만 허용한다.
• 순서 제어하려면 lock 관리를 해야 한다.
• transaction이 새로운 operation을 요청하지 않는 순간 = transaction이 끝날 때
  • transaction이 끝날 수 있는 2가지 방법
    1. commit 하고
    2. abort/rollback 하고

2. Strict Twophase Locking (Strict 2PL) Protocol

• 2PL이다.
• 각 transaction은 읽기 전에 shared lock을, 쓰기 전에 exclusice lock이 되어야 한다.
• transaction이 가지고 있는 모든 lock은 transaction이 완료되면 해제된다.
• transaction이 X lock을 유지하면 다른 transaction은 해당 object에 대해 S 또는 X lock을 얻을 수 없다.
• transaciton이 object에 대해 S 또는 X lock을 유지하는 경우 어떤 trasaction도 object에 대해 X lock을 유지할 수 없다.
• Strict 2PL은 오직 conflict serilizable schedules에서만 허용된다.

 

 

 

Aborting a Transaction

• Ti가 abort 되면 모든 action은 취소되어야 한다. Tj가 Ti가 마지막으로 쓴 object를 읽는다면 Tj도 중단되어야 한다.
  • undo operation을 할 수 있도록 시스템이 지원을 해야 한다. → log로 보통 해결한다.
• cascading abort
  • 한 transaction이 철회하면 연쇄적으로 다른 transaction도 철회되는 것
• 모든 system은 cascading abort을 피해야 한다.
  • transaction이 완료한 transaction들만 읽어서 recoverable 하게 할 뿐만 아니라 transaction을 abort(철회)하는 것이 다른 transaction들을 연쇄적으로 abort하지 않고 이루어지게 한다.
• 대부분의 시스템은 cascading abort를 피하기 위해 commit 시간에만 transaction의 lock를 해제한다.
  • Ex. 만약 Ti가 object를 write한다면, Tj는 Ti가 commit 한 이후에만 read를 할 수 있다.

 

 

 

Summary

• 내가 돌릴 transaction이 순차적으로 실행되면 문제 없다.
• 동시에 수행될 때 문제가 생긴다. = concurrent processing
• DBMS는 자동으로 lock/unlock 요청을 넣고, 다른 transaction의 action을 예약하여 결과적인 실행이 어떤 순서로 transation을 차례로 실행하는 것과 동일하도록 한다.
• recovery는 중단된 transation의 action을 abort하고 충돌 후 시스템을 일관된 상태로 복원하는 데에 사용된다.
• 사용자는 recovery에 대해 걱정할 필요가 없다.

 

 

 

DeadLocks

• Lock이 해제되기를 서로 기다리는 Transaction들의 사이클
  • 이 두 transaction이 다른 transaction들이 요구하는 lock을 소유하고서 기다리기 때문에
• Locking만 쓰면 DeadLock 때문에 solution 해결이 안된다. 다른 기법도 필요하다.
  • DeadLock prevention : 사전에 가능성을 방지한다.
  • Deadlock detection : 일어나게 둔다.

 

 

 

DeadLock Prevention

• DeadLock이 발생할 순간을 안 만든다.
• 안 꼬이게 Lock 관리를 한다.
• priority를 주는 방법
  • 각 transaction의 시작시점에 timestamp를 부여한다.
  • timestamp가 작을수록 priority가 높다.
• Wait-Die
  • Ti의 우선순위가 높으면 Ti는 기다려야 한다. 아니면 Ti를 abort하던가
  • 더 낮은 우선순위를 갖는 transaction이 더 높은 우선순위를 갖는 transaction을 기다리지 않는다.
• Wound-wait
  • Ti의 우선순위가 높으면 Tj는 abort 되어야 한다. 아니면 Ti를 wait 하거나
  • 더 높은 우선순위를 갖는 transaction이 더 낮은 우선순위를 갖는 transaction을 기다리지 않는다.
• Deadlock이 발생했다면
  • wait-die 방법에서는 낮은 애가 높은 애를 기다리는거고
  • wound-wait에서는 높은 애가 낮은 애를 기다리는 거다.
• 위 과정이 생기면 절대 cycle이 안 생긴다.

 

 

 

DeadLock Detection

• Deadlock 발생 순간이 되면 잡는다.
• Deadlcok 해결하는 방법은 끊는 방법 밖에 없다. 그러려면 희생양이 필요하다.
• waits-for graph를 생성하여 cycle이 있는지 보는 것이 대표적인 방법이다.
• lcok을 가진 operation만 수행 가능하기 때문에 이렇게 순서 제어를 한다.
• handling까지는 안해준다.

 

 

 

Multiple-Granularity Locks

• transaction 유형에 따라 어떤 grnularity(잠금단위)를 할 것인지 결정한다.
  • 많은 transaction이 적은 수의 reocrd에 자주 access 할 때 → record를 lock
  • 많은 transaction이 동일한 table에 있는 많은 record에 자주 access 할 때 → table을 lock

 

 

 

Intention Locks

• item을 잠그기 전에 Xact는 모든 조상에게 intention lock을 설정해야 한다.
• lock 가능성을 높인다.
• IS : shared Lock 할 의도가 있다
• IX : exlusive Lock 할 의도가 있다
• SIX : S & IX 처럼 동시에 사용 가능, S와 IX mode를 동시에 요청하고 동시체 푼다.
• 잠금을 해제하려면 specific → general 로 이동한다.

 

 

 

Multiple Granularity Lock Protocol

• IX가 IS보다 세다.
• SIX가 IX보다 세다
• 센 Lock을 가지면 밑으로 갈 수 있다.
• IS와 IX는 직접적인 비교가 불가능하다.
• S가 IS도사 세다. (S를 가지면 IS가 필요 없어서)
• S를 가지려면 IS or IX가 필요하다.
• 이왕이면 Transaction에 덜 센 Lock을 준다. (확률을 높이기 위해)
• Lock escalation
  • transation에 적당한 granularity를 주기 위해 미세한 것부터 시작하여 수준을 높여가는 접근 방법
• node에서 S or IS 잠금을 얻으려면 부모 노드에 IS or IX가 있어야 한다.
• node에서 X or IX or SIX 잠금을 얻으려면 부모 노드에 IX or SIX가 있어야 한다.
• lock은 꼭 아래→위 순서대로 풀려야 한다.
• protocol은 계층의 leaf level에서 lock을 직접 설정하는 것과 동등하다.
• 이걸 사용하면 overhead가 줄어든다.

 

 

 

Optimistic Concurrency Control

• lock 기반이 아닌 다른 방법을 쓸 수도 있다. (optimistic)
• lock을 쓰는 것은 pessimistic 하다 = 다른 가능성을 배제시키는 것이다. (concurrency control)
• lock은 conflict를 방지하는 보수적인 approach이다.
  • Lock 관리의 overhead
  • Deadlock 감지와 해결
  • 자주 사용하는 object에 대한 lock의 경쟁
• 만약 conflict가 드문 경우에는 lock을 하지 않고 Xacts가 commit 하기 전에 conflict를 확인함으로써 concurrency를 확보할 수 있다.
  • 일단 transaction을 수행하고 conflict가 있으면 끝날 때 해결하는 것
  • 나중에 문제가 발생되면 commit 하지 않고 abort 한다 = optimsitic concurrency control
• Xacts의 3가지 단계
  • READ : Local에서 DB에서 읽은 Xacts이지만 object의 private copy를 변경한다. DB에서 값을 읽고 개별 작업 공간에 쓰기를 한다.
  • VALIDATE : conflict를 확인한다. 확인하고 R/W를 수용한다. 충돌이 있다면 transaction을 abort한다. 그럼 개별 작업공간은 제거되고 그 transaction은 다시 시작된다.
  • WRITE : Local에서 변경 사항의 local copy를 공개한다. 개별 작업공간에 한 변경이 DB에 복사된다.

 

 

 

Validation

• conflict가 발생했는지 확인하기 때문에 충분한 조건들을 test한다.
• 각 Xact에는 숫자 ID가 할당된다.
• timestamp를 사용한다.
  • transaction 시작 시에 할당한다.
  • 시간이 지나면 커진다.
  • ID처럼 사용 가능하다.
  • 일렬로 나란히 가능하다.
• 각 transaction에 대해 ReadSet(Ti)와 WriteSet(Ti)로 관리한다.

 

 

 

Overheads in Optimistic CC

• ReadSet, WriteSet에 read/write 활동을 기록해야 한다.
• 필요에 따라 이 세트들을 만들고 파괴해야 한다.
• 유효성 검사 중 충돌 여부를 확인해야 한다.
• 유효성 검사가 된 wirte를 global로 만들어야 한다.
• critical section은 concurrency를 줄일 수 있다.
• write를 global화 하는 방식은 object의 clustering을 줄일 수 있다.
• optimistic CC는 유효성 검사에 실패한 Xact를 다시 시작한다.
• 지금까지 한 일은 낭비되고 clean-up이 필요하다.
• read가 일반적이고 write가 드문 optimistic 환경에서 CC overhead를 최소화 하는 것을 목표로 한다.