(Chapter 13) Concurrency Control

( 출처 : 연세대학교 데이터베이스 시스템 수업 (CSI6541) 강의자료 )

Chapter 13. Concurrency Control

Contents

• 병행 수행 & 병행 제어

  • 병행 수행 ( concurrency )

  • 병행/동시성 제어 ( concurrency control )

• 병행 수행 시, 발생 가능 문제점

  • 갱신 분실 ( lost update )

  • 모순성 ( inconsistency )

  • 연쇄 복귀 ( cascading rollback )

• 병행 제어 기법
  • 로킹 (Locking) 기법
  • Lock-based Protocols
  • Two-phase Locking Protocols
  • Deadlock

(1) 병행 수행 & 병행 제어

a) 병행 수행 ( concurrency )

• 여러 사용자가 DB를 동시에 공유 할 수 있도록,

  여러 개의 transaction을 동시에 수행하는 것을 의미

• 방식 : interleaving (인터리빙)

  ( = 여러 transaction이 차례로 “번갈아서” 수행됨 )

b) 병행/동시성 제어 ( concurrency control )

• 병행 수행 시, 같은 data에 접근하여 연산을 실행해도,

  문제가 발생하지 않고, 정확한 수행 결과를 얻을 수 있도록 transaction을 제어하는 것!

(2) 병행 수행 시, 발생 가능 문제점

a) 갱신 분실 ( lost update )

• 하나의 transaction이 수행한 데이터 변경 연산의 결과를,

  다른 transaction이 덮어써서 변경 연산이 무효화 되는 것

• 여러 transaction이 동시에 수행되더라도, 갱신 분실 문제가 발생하지 않고, 마치 transaction들이 순차적으로 수행한 것과 같은 결과를 얻어야!

b) 모순성 ( inconsistency )

• 하나의 transaction이 여러 개 data 변경 연산을 실행할 때,

  일관성 없는 상태의 DB의 데이터를 가져와 연산함으로써 모순된 결과 발생!

• 여러 transaction이 동시에 수행되더라도, 모순성 문제가 발생하지 않고, 마치 transaction들이 순차적으로 수행한 것과 같은 결과를 얻어야!

c) 연쇄 복귀 ( cascading rollback )

• transaction이 완료되기 전에 장애가 발생하여 rollback 수행 시,

  장애 발생 전에 이 transaction이 변경한 데이터를 가져가서 변경 연산을 실행한 다른 transaction에도 rollback 연산을 “연쇄적으로” 실행해야!

• 여러 transaction이 동시에 수행되더라도, 연쇄 복귀 문제가 발생하지 않고, 마치 transaction들이 순차적으로 수행한 것과 같은 결과를 얻어야!

(3) 병행 제어 기법

• 의미 : 병행 수행 하면서도, 직렬 가능성을 보장하기 위한 기법

• 방법 : 모든 transaction이 준수하면 직렬 가능성이 보장되는 규약을 정의하고, transaction들이 이 규약을 따르도록!

• Ex) 로킹 기법

a) 로킹 (Locking) 기법

• 원리 : 한 transaction이 먼저 접근한 데이터에 대한 연산을 끝날때까지 다른 transaction이 접근 못하도록 상호 배제 (mutual exclusion) 함

• 방법 : lock / unlock 통해 동시 접근 X 도록!
  • lock : transaction이 데이터에 대한 독접권을 “요청”하는 연산
  • unlock : transaction이 데이터에 대한 독접권을 “반환”하는 연산
• 로킹 단위 ( = lock 연산을 실행하는 data의 범위/크기 )
  • 전체 DB ~ relation/tuple/attribute 전부 가능
  • locking 단위가..
    • 커질수록 \(\rightarrow\) 병행성 down, 제어 up
    • 작아질수록 \(\rightarrow\) 병행성 up, 제어 down

b) Lock-based Protocols

Data items can be locked in 2 modes:

• (1) Exclusive (X) mode
  • can be both read as well as written.
  • X-lock : requested using lock-X instruction
• (2) Shared (S) mode
  • can only be read
  • S-lock : requested using lock-S instruction

Lock requests are made to concurrency-control manager

\(\rightarrow\) Transaction can proceed only after request is granted

• A transaction may be granted a lock on an item if the requested lock is compatible with locks already held

• If a lock cannot be granted….

  \(\rightarrow\) the requesting transaction has to wait untill all incompatible locks have been released

Locking protocol

• def ) a set of rules followed by all transactions while requesting and releasing locks
• restrict the set of possible schedules

c) Two-phase Locking Protocols

protocol which ensures conflict-serializable schedules

Phase 1: Growing phase

• Transaction may obtain locks **( **not release locks )

Phase 2: Shrinking phase

• Transaction may release locks ( not obtain locks )

It can be proved that the transactions can be serialized in the order of their lock points (i.e. the point where a transaction acquired its final lock)

Details

• does not ensure freedom from deadlocks

• Cascading rollback is possible under two-phase locking.

  • To avoid this, follow a modified protocol called strict two-phase locking

    ( = transaction must hold all its exclusive locks till it commits/aborts )

• Rigorous two-phase locking is even stricter

  ( = all locks are held till commit/abort )

  • transactions can be serialized in the order in which they commit

ex) Cascading Rollback

ex) Rigorous Two-Phase Locking

d) Deadlock

Def) cycle of transaction WAITING FOR locks to be released by each other

2 ways of dealing with deadlocks :

• (1) deadlock DETECTION
• (2) deadlock PREVENTION

Deadlock Detection

Deadlocks can be described as a wait-for graph G = (V,E)

• V : transactions
• E : ordered pair \(T_i \rightarrow T_j\)

If there is edge ( \(T_i \rightarrow T_j\) )

\(\rightarrow\) \(T_i\) is waiting for \(T_j\) to release a data term

When \(T_i\) requests a data item currently being held by \(T_j\)

\(\rightarrow\) edge \(T_i \rightarrow T_j\) is inserted in the wait-for graph

( this edge is removed only when \(T_j\) is no longer holding the data )

The system is in a deadlock state

\(\leftrightarrow\) wait-for graph has a cycle

\(\rightarrow\) Must invoke a deadlock-detection algorithm periodically to look for cycles

Deadlock Recovery

When deadlock is detected …

• Some transactions will have to be rolled back (made a victim) to break deadlock . Select the transaction as victim “that will incur minimum cost”

Determine how far to roll back transaction !

• Total rollback: Abort the transaction and then restart it

• More effective to roll back transaction only as far as necessary to break deadlock

Starvation happens, if SAME transaction is always chosen as victim

Include the NUMBER of rollbacks in the cost factor to avoid starvation