Transactions

임승섭·2023년 6월 18일
0

Database system

목록 보기
22/22

Transaction Concept

  • A transaction is a unit of program execution
    that accesses and possibly updates various data items
  • ex). Transfer $50 from account A to account B
  1. read(A)		// tuple이 disk에서 buffer로 올라오고, 그 buffer로부터 "read"
  2. A = A - 50		// register에서 값 변경 (buffer 값 변경 x)
  3. write(A)		// buffer 값 업데이트
  4. read(B)
  5. B = B + 50
  6. write(B)
  • 2가지 main issue
    • hardware failure, system crash와 같은 다양한 실패
    • 여러 transaction들의 동시 실행

ACID Properties

4가지 requirement

Atomicity Requirement

  • 만약 step 3와 step 6 사이에서 transaction이 fail했으면,
    money will be "lost"
  • ALL OR NOTHING. 100% 반영하거나, 그게 아니라면 아예 database에 반영하지 않는다.

Durability requirement

  • user가 transaction이 완료되었다고 notify하면,
    transcaction에 의한 db update는 반드시 진행되어야 한다.
    (even if there are software or hardware failures)

Consistency requirement

  • 위 예시에서). transaction 실행에 의한 A + B 값은 변함이 없어야 한다.
  • 일반적으로 consistency requirement는 다음을 포함한다 :
    • explicitly specified integrity constraints such as primary keys and foreign keys
    • implicit integrity constraints such as sum of balances of all accounts
    • During transaction execution, db may be temporarily inconsistent
    • When transaction completes successfully, db must be consistent

Isolation requirement

  • 위 예시에서). 3번과 6번 step 사이에 다른 transaction T2가 A, B값에 접근하려고 하면, inconsistent database가 된다.
  • transaction들을 순차적으로(serially) 실행시킴으로서 보장받을 수 있다.
  • 하지만, multiple transaction을 동시에 실행시키는 건 분명히 이점이 있다.

Summary

  • A transaction is a unit of program execution
    that accesses and possibly updates various data items.
    To preserve integrity of data, db system must ensure 4 things

  • Atomicity : Either all operations of the transaction are properly reflected in the db or none are.

  • Consistency : Execution of a transaction in isolation preserves the consistency of the db.

  • Isolation : Although multiple transaction may execute concurrently,
    each transaction must be unaware of other concurrently executing transactions.
    Immediate transaction results must be hidden from other concurrently executed transactions.

  • Durability : After a transaction completes successfully,
    the change it has made to the db persist,
    even there are system failures.


Transaction State

  • Active : 현재 진행중.
    • the initial state;
    • transaction이 실행중일 때 이 state에 있는다
  • Partially committed : buffer에 update 완료 (disk에 쓰기 전)
    • after the final statement has been executed
  • Failed
    • after the discovery that normal execution can no longer proceed
  • Aborted : 실행 중단 -> 실행하기 전 상태
    • after the transaction has been rolled back and the db restored to its prior to the start of the transaction.
    • Two options
      • Restart the transaction
        • internal logical error가 없을 때 가능
      • Kill the transaction
  • Committed : disk에 write 완료
    • after successful completion

Concurrent Executions

  • multiple transaction은 동시에 실행될 수 있다
  • Advantages :
    • 향상된 processor와 disk의 utilization,
      leading to better transaction throughput
    • transaction에 대한 average response time 감소 :
      short transactions need NOT wait behind long ones
  • Concurrency control schemes
    : Mechanisms to achieve isolation
    • concurrent transactions 사이의 interaction을 control한다

Schedule

  • A sequence of instructions that specify the chronological order in which instructions of concurrent transactions are executed
    • transaction 집합의 schedule은 그 transaction들의 모든 instruction을 포함하고 있어야 한다
    • 각 transaction의 instruction 순서를 유지해야 한다
  • 성공적으로 실행을 마친 transaction은 마지막 statement에서
    commit instruction을 갖는다
  • 성공적으로 실행을 실패한 transaction은 마지막 statement에서
    abort instruction을 갖는다

Schedule 1

A serial schedule in which T1 is followed by T2 :

  • A + B 계속 200 유지
    • (100, 100) (50, 150) (45, 155)

Schedule 2

A serial schedule where T2 is followed by T1 :

  • A + B 계속 200 유지
    • (100, 100) (90, 100) (40, 160)

Schedule 3

NOT a serial schedule, equivalent to Schedule 1

  • A + B 계속 200 유지
    • (100, 100) (50, 100) (45, 100) (45, 150) (45, 155)

Schedule 4

  • Does NOT preserve the value of A + B
    • (100, 100) (90, 100) (50, 100) (50, 150) (50, 110)

Serializability

  • 기본 가정 : Each transaction preserves db consistency
  • 따라서, transaction 집합의 serial execution은 preserves db consistncy
  • 어떤 schedule이 serial schedule과 동일한 결과를 내면,
    it is serializble
  • Conflict serializabilityView serializability가 있는데, 주로 conflict serializability에 대해 배운다.
  • Simplified View of transaction
    • readwrite 이외의 operation은 모두 무시한다

Conflict Instruction

  • transaction Ti, Tj와
    각각의 instruction Ii, Ij,
    얘네가 둘 다 접근하는 item Q에 대해,
    다음과 같은 상황에서 conflict 발생 (전자가 Ii, 후자가 Ij)
    • read(Q), read(Q) : Don't conflict
    • read(Q), write(Q) : conflict
    • write(Q), read(Q) : conflict
    • write(Q), write(Q) : conflict
  • 둘 사이의 conflict는 강제적으로 순서를 갖게 한다
  • schedule에서 둘이 연속적이고, conflict가 발생하지 않으면,
    둘이 순서가 바뀌어도 결과는 동일하다

  • 만약 non-conflicting instruction의 swap에 의해
    schedule S가 S'으로 바뀌었다면,
    S와 S'은 conflict equivalent하다

  • schedule S가 serial schedule과 conflict equivalent하면,
    S는 conflict serializable하다

conflict serializable example

  • schedule 3는 schedule 6로 바뀔 수 있다.
    • T2의 read(A)/write(A)와 T1의 read(B)/write(B)는 서로 conflict하지 않기 때문에 위치가 바뀔 수 있다.
  • schedule 6는 serial schedule이기 때문에,
    schedule 3는 conflict serializable하다

NOT conflict serializable example

  • 위 schedule을 <T3, T4> 또는 <T4, T3>처럼 serial schedule로 바꿀 수 없다.

NOT conflict serial but same outcome

Testing for Serializability

  • Consider some schedule of a set of transactions T1, ..., Tn
  • Precedence graph : vertices가 transaction name인, direct graph
  • 만약 graph가 acyclic하면, schedule is conflict serializable
  • acyclic한지는 DFS를 이용해서 찾는다. (n^2 or n+e)
  • graph가 acylic할 때, serializability order는 topological sorting에 의해 계산될 수 있다.
    • 노드의 indegree가 0인 노드 먼저 하고, 이거 삭제하고
      다음 indegree가 0인 노드 하고, 삭제하고,
      계속 반복한다

Recoverability

Recoverable schedule

  • Tj가 이전에 Ti에 의해 write된 data를 읽을 때,
    Ti의 commit operation이 Tj의 commit 보다 이전에 나타나야 한다.
  • NOT recoverable
    • 뭐가 문제나면,
      만약 T8이 abort되면, T8에 의한 작업은 모두 취소가 되어야 한다.
      T9은 이미 commit이 되었기 때문에 취소가 안되는 상태인데,
      그럼 얘가 읽은 A값은 inconsistent한 값이 된다!!

Cascading Rollback

  • single transaction failure가 series of transaction rollbacks을 발새시킨다
  • 아래 그림은 아무 transaction도 commit이 되지 않은 schedule이다.
    • T10이 abort나면, T11, T12도 모두 취소된다.
    • recoverable

Cascadeless Schedule

  • cascading rollback이 일어날 수 없다.
  • Tj가 Ti에 의해 write된 data를 read할 때,
    Ti의 commit operation이 Tj의 read보다 먼저 나타난다.
  • Every cascadeless schedule is also recoverable
  • 아주 바람직한 방법이다.

Concurrency Control

  • db는 반드시 모든 schedule이 다음 조건을 만족하게 해야 한다
    • conflict serializable 하거나,
    • recoverable하고 가능하다면 cascadeless.
  • 단순히 serializable하게 하면 좋긴 하지만 concurrency 측면에서 낮은 결과가 나온다.
  • Goal : to develop concurrency control protocols that will ensure serializability
  • Schedule은 반드시 conflict serializable하고, recoverable하고, 가능하다면 cascadeless해야 한다. db의 consistency를 위해.
  • concurrency-control은 amount of concurrency they allowamount of overhead that they incur 사이의 tradeoff가 있다.

0개의 댓글