1. What is Transaction ?

1-1. Introduction

• Transaction processing systems (트랜잭션 처리 시스템)
  대규모 Database와 수 백명의 동시 사용자가 Database Transaction을 실행하는 System
  E.g., 항공 예약, 은행 업무, 신용 카드 처리, etc...
• Transaction
  Database에서 수행되는 여러 작업을 하나의 논리적 단위로 수행하는 것
  Correctnessand Consistency를 보장해야 한다.

1-2. Transaction Example

1-3. Difference Between Transaction and General Program

1-4. Terminology

• Types of transaction
  • Read-only : only reads; Database를 Update하지 않는 transaction이기 때문에 lock이 필요 없다.
  • Read-write : Database를 update하는 transaction
• Transaction 처리 개념의 주요 Terms
  • Data item : Database에 저장되는 단위; E.g., Tuple, Disk block, etc ...
  • Granulartity : The size of the data item
    • 이 값에 따라 lock의 범위가 달라진다..
    • Transaction 처리의 concurrency를 결정한다.
  • Database : A collection of "named data items"
• Transaction에 포함될 수 있는 Database access 작업
  • read_item(X): Reads a data item, X, into a program variable (X)
  • write_item(X): Writes the value of X into the data item named X

2. Transaction and system concepts, and desirable properties of transactions

2-1. Transaction States (트랜잭션 상태)

• BEGIN_TRANSACTION: Transaction execution의 beginning를 나타낸다.
• READ or WRITE: Database items에 read or write operation
• END_TRANSACTION: Transaction execution의 종료를 나타낸다.
  • Transaction의 상태를 체크 필수 : commited or aborted.
• COMMIT_TRANSACTION: Transaction의 성공적인 종료 신호
  • 변경된 것은 영구적으로 기록된다.
• ROLL_BACK(or ABORT): Transaction이 정상적으로 종료되지 않음의 신호
  • 실행을 취소해야 한다. (rollback)

• Partially commited
  • Why?
    • For fast response to user
  • DBMS는 각 트랜잭션 단위가 아닌 disk의 변경 사항을 한 번에 반영한다.
  • 일부의 Concurrency control protocols : 추가적으로 가능한 commit을 확인한다.
  • 일부의 Recovery protocols : 실패사항과 database에 끼치는 영향을 확인한다.
• Failed : checks 중 하나가 실패하거나, Transaction이 abort된 경우
  • Partially commited → Abort → Failed
    • EX) Deadlock
  • Failed or aborted transaaction이 재시작된다. (by user or automatically)
• Terminated : Transaction이 system을 떠남

2-2. Why Recovery Is Needed? To Handle Failure

• Transaction이 실행을 위해 DBMS에 submit될 때, 해당 Transaction의 최종 상태는 DBMS에 의해 결정되며 다음 두 가지 경우에 해당된다.
  • Committed
    • Transaction의 모든 operations이 성공적으로 완료되었고, 그 영향이 Database에 영구적으로 저장된다.
  • Àborted
    • Transaction은 Database 또는 다른 transaction에 아무런 영향도 주지 않는다.

• 만약 Transaction이 일부 Operation을 실행한 후, 모든 Operation을 실행하기 전에 실패하는 경우
  • 이미 실행된 Operation은 취소되어야 하며, 지속적인 효과는 존재하지 않는다. (영구 저장 X)

Failures : classified as transaction, system, and media failures
1) A computer failure
2) A transaction or system error
3) Local error or exception conditions detected by the transaction
4) Concurrency control enforcement
5) Disk failure
6) Physical problems and catastrophe


The DBMS must keep sufficient information to recover quickly from Types 1-4 failures (more common than the others).

2-3. The System Log

DBMS에서 장애로부터 복구하기 위해 유지된다.

• 데이터베이스 항목의 값을 영향을 미치는 트랜잭션 작업을 추적한다.
• 순차적이며, disk에 append-only 파일이 저장된다.
• 디스크나 심각한 장애를 제외하고는 안전하다.
• Log buffer: 로그를 기록하는 데 사용되는 주 기억 장치 버퍼 중 하나(또는 여러 개)
• 로그 항목으로 가득 차면 디스크의 로그 파일 "끝"에 추가된다.
• 로그 파일은 주기적으로 보관용 저장소에 백업된다.
• 모든 심각한 실패에 대비한다.

Types of "Log Records"
1. [start_transaction, T]
2. [read_item, T, X]
3. [write_item, T, X, old_value, new_value]
4. [commit, T]
5. [abort, T]
T: a unique transaction identifier generated automatically

System crashes가 발생하면 log를 확인하고 ARIES와 같은 recovery technique를 사용하여 consistent한 database로 복구할 수 있다.

• UNDO operations : Restore X to old_value
  • T의 WRITE operations의 영향을 역추적해서 작성한 내용을 복원한다.
• REDO operations : Updates X to new_value
  • Transaction이 log에 업데이트를 기록했지만, new_value를 기록하기 전에 실패가 발생한 경우 수행될 수 있다.
  • ARIES에서는 `forwardàction을 수행하는 데 사용

2-4. Commit Point of Transaction T

Transaction의 모든 operations이 성공적으로 완료되고, log에 모두 기록된다면
T는 committed되었다고 한다.

• 그 후, log에 commit record를 쓴다.
  • [commit, T]
• Failure가 발생했을 때,
  • 만약 T가 commit record를 가지고 있다면, Log record로부터 Database에 있는 그들의 영향을 REDO한다.
  • T에 commit record는 없지만 start_transaction레코드가 있는 경우, recovery process 중에 database에 그들의 영향을 Undo한다. (rollback)
• "Force-writing" : Transaction을 commit하기 전에 log buffer를 flush한다.
  • 트랜잭션이 커밋 지점에 도달하기 전에 디스크에 기록되지 않은 로그의 어떤 부분이라도 디스크에 기록되도록 하는 것을 나타낸다.
  • 회복 중에 디스크에 저장된 로그 항목만 고려할 수 있도록 한다.

2-5. ACID Properties of Transaction

Transaction이라면 무조건 충족해야하는 특성
Transaction이 안전하게 수행된다는 것을 보장하기 위한 성질

• Atomicity: Recovery subsystem이 책임 (By DBMS)
  • Transaction은 processing의 atomic unit: all or nothing
  • 하나가 전부 실행되든 실패하든 해야된다.

• Consistency: programmer가 책임 (By programmer)

  • Transaction은 Database 무결성 조건을 무조건 충족해야 한다.

• Isolation: concurrency control subsystem에 의한 시행 (By lock manager)

  • Transaction은 다른 Transaction에게 영향을 주거나, 받지도 않아야 한다.

• Durability: recovery subsystem이 책임 (By DBMS)

  • Transaction이 Commit되면 영구적으로 Database에 반영이 되어야 한다.

3. Characterizing schedules based on serializability

3-1. Schedules of Transactions

A schedule Sof n(concurrent) transactions T1, T2, ..., Tn

• Transactions의 operations의 순서
• 서로 다른 Transaction의 작업(Read/Write)는 S에서 Serial(직렬)혹은 Interleaved(교차)될 수 있다.
  • Example of a schedule (S) of “interleaving” two transactions, T1 and T2:
  • S: r1(X); w2(X); w1(X); r1(Y); w2(X); w1(Y);
• Total ordering of operations in S
  • `S에 두 개의 operation 중 하나의 Operation은 반드시 다른 operation 전에 발생해야 한다.
• Partial ordering of operations in S
  • 특정 작업 간의 시간 순서가 시스템에 의해 결정되지 않은 경우 사용된다.

3-2. Serial Schedule

• Schedule S가 serial(직렬)이라면 S에 있는 모든 Transcation에 대한 모든 Opertaion이 Interleaving(교차)없이 연속적으로 실행된다.

  • 그렇지 않으면, `nonserial라고 부른다.

• 모든 serial schedule은 Correct하다.

  • 하지만, 다음과 같은 문제점이 있다.
  • 다른 작업의 교차를 금지하기 때문에 concurrency(동시성)을 금지한다.
  • 다른 Transcation이 완료될 때까지 기다려야 한다.
    • 때문에 실무에서는 사용할 수 없다.

  Solution
  Serial schedule과 거의 비슷하게 동작하는 schedule을 사용한다.

  3-3. Conflicting Operations in a (Nonserial) Schedule

  Schedule에서 두 개의 작업이 충돌한다는 것은 다음을 의미한다. (세 가지 조건이 모두 충족되어야 한다.)

  • 두 개의 작업이 서로 다른 transaction에 속한다.
  • 작업들이 동일한 Item X에 접근한다.
  • 적어도 하나의 작업이 write_item(X)다.

• 또한, 두 개의 작업의 순서가 변경되었을 때, 결과가 다르게 나오는 경우도 충돌한다.

• Two Types of conflict

• read-write

  • r1(X) -> w2(X)

• write-write

  • w1(X) -> w2(X)

이러한 충동을 방지하기 위해, Concurrency Control technique으로 correctness를 보장해야 한다.

3-4. Why Concurrency Control Needed in a Schedule

3-4-1. Types of Problems (1/6)

다음과 같이 동시에 실행될 수 있는 Transaction을 고려하자

3-4-2. Types of Problems (2/6)

Serial 하기 때문에 순서를 변경 시켜도 결과는 동일하다.

Nonserial 하기 때문에 T1과 T2의 작업 간에 교차가 일어난다.
Nonserial은 순서에 따라 결과가 달라졌지만, Serializable은 순서를 변경시켜도 결과가 동일하다.

3-4-3. Types of Problems (3/6)

Lost update (갱신 손실)
두 개의 Transaction이 같은 Database item에 접근해서 Interleaving하게 작업을 수행할 때 몇 database item은 Incorrect하다.

T1이 write한 값에 T2가 해당 값을 다시 써서 값이 덮어쓰여졌다. (Overwrite)
이로써 T1이 작성한 Item X는 Lost

3-4-4. Types of Problems (4/6)

The Dirty read (or temporary update) problem

• 한 트랜잭션이 데이터베이스 항목을 업데이트하고 나중에 해당 트랜잭션이 어떤 이유로 인해 실패할 때 발생한다.
• 그 동안에 업데이트된 항목이 다른 트랜잭션에 의해 해당 값이 변경되기 전(또는 롤백되기 전)에 읽힐 때 발생한다.

T2에서는 T1에서 write하고 abort된 dirty data를 read한다. -> Dirty read
X의 Value가 Òld_value로 복구되어야 한다.

3-4-5. Types of Problems (5/6)

The Incorrect summary problem (called phantom read)

• 하나의 트랜잭션이 여러 데이터베이스 항목에 대한 집계 요약 함수를 계산하는동안 다른 트랜잭션이 이러한 항목 중 일부를 업데이트 하는 경우
• 합계 함수는 값이 업데이트되기 전과 후에 계산하면 문제 발생

T3는 A, ... , Y의 값의 누적합을 구한다.
T1에서 T3가 구하고자 하는 값을 변경하는 경우 결과 값이 달라진다.

3-4-6. Types of Problems (6/6)

Unrepetable read problem

• 한 트랜잭션이 동일한 item을 두 번 읽을 때, 두 번 사이에 다른 트랜잭션 T에 의해 해당 item이 변경되는 경우에 발생한다.
• 이 때, 두 번의 읽기에 대해 서로 다른 값을 가지게 된다.

3-4-7 Solution

이러한 문제들을 해결하기 위해 nonserial하지만, serializable schedule을 생성하기 위해 좋은 concurrency control이 필요하다.

3-5. Serializable(직렬가능한) Schedule

• 동일한 N개의 트랜잭션에 대한 Serial Schedule과 비슷하다.
• S1이 serial schedule이라고 가정하고, S2는 Non-serial이라고 가정하자.
  만약 S1과 S2의 데이터베이스의 최종 상태를 동일하게 만든다면 S1과 S2는 동등하다고 할 수 있다.
• 이 때, S2는 Serializable라고 할 수 있다.

3-6. How to Ensure Serializablity ?

Use concurrency control (CC) protocols

• Two-phase locking(2PL): most common technique
  • Serialized schedule을 생성한다.
  • 동시에 실행중인 트랜잭션들이 서로 간섭하지 않도록 데이터 항목에 Lock을 건다.
    • Lock에는 3가지 문제점이 있다.
      • A high overhead (lock 요청 이후, 읽기 or 쓰기)
      • Deadlock
      • Starvation
  • Two phases : growing(acquiring) and shrinking(releasing) phases on locks
  • Serializablity를 보장하는 추가적인 조건을 부과한다.
  • Deadlock예방은 보장하지 못한다.
    • 각 트랜잭션 T가 한 집합 내에서 다른 트랜잭션 T에 의해 Lock이 걸린 Item을 기다리는 경우 Deadlock 발생

Not Following 2PL

Following 2PL

The types oof concurrency control protocols

• Snapshot isolation
• Timestamp ordering
• Multiversion concurrent control(MVCC) protocols
• Optimistic protocol

4. Transaction support in SQL

4-1. Transaction support in SQL

• 일반적으로, 명시적인 Begin_Transactionstatement가 없다.
• 대신, 모든 트랜잭션은 명시적인 end statement를 가져야한다. COMMIT | ROLLBACK
• 모든 트랜잭션은 다음과 같은 특성을 가진다.
  • Isolation level으로 명시된다.
  • How to specify isolation level in SQL: ISOLATION LEVEL <isolation>

Isolation Level
READ UNCOMMITTED | READ COMMITTED (by default in Oracle)
REPEATABLE READ | SERIALIZABLE (by default in most DBMSes)

4-2. What Happens if Serializability is Violated ?

트랜잭션이 SERIALIZABLE보다 낮은 Level을 가질 경우 다음 문제가 발생할 수 있다.

• Dirty read(오손 읽기)
• Nonrepeatable read(반복 불가능)
• Phantoms(유령 데이터)

READ COMMITTED : 트랜잭션 성능 향상
SERIALIZABLE: Concurrency Control 가능

Reference
Database System Concepts | Abraham Silberschatz
데이터베이스 시스템 7th edition