슬라이드 버전 공유

Outline

• Lock-Based Protocols
• Timestamp-Based Protocols
• Deadlock Handling

주요 내용

• Atomicity Consistency Isolation Durability (ACID) : Transaction이 지켜야할 4가지 성질

• A, C, D : recovery manage에서 설명(log)

• I : concurrence control manager(locking)

• Lock허용 여부 : data의 consistence가 유지되면 허용

• Lock-based / Timestamp-Based Protocol 설명 / Lock-based는 대체적으로 Deadlock을 발생시킴.

Lock-Based Protocols (1/3)

• lock 메카니즘은 데이터 엑세스에 대한 동시성 제어

• 2가지 모드

  • Exclusive mode read x, write x
  • Shared mode read o, write x
• lock 요청은 concurrency control 매니저에게 요청하는 것 ( 트랜젝션은 granted 된 이후 진행 됨)

Lock-Based Protocols (2/3)

• Lock compatibility matrix

• 위 matrix에 true 일때만 lock을 얻을 수 있음

• 1개 이상의 트랜젝션이 shared lock을 쥐고 있을 수 있음

• Exclusive lock은 하나의 트랜젝션을 초과해서 얻을수 없음

• lock을 못 얻으면 트랜젝션은 대기

Lock-Based Protocols (3/3)

• 아래의 lock은 A와 B사이에 무언가가 침투하면 serializability가 보장되지 않음

• 아래 예제는 잘못된 locking Lock을 너무 빨리 풀면 data consistence가 깨짐.

• lock 프로토콜은 모든 트랜젝션이 따라하야 하는 rule임

Pitfalls of Lock-Based Protocol (1/2)

• T3와 T4 모두 진행이 안됨 lock-S(B)와 lock-X(A)가 각 트랜젝션을 wait로 만들기 때문

• 이 상황을 데드락이라 함

  • T4의 lock-S(B)는 이미 B data에 X-lock이 걸려있기 때문에 wait

  • T3의 lock-X(A)는 이미 A data에 S-lock이 걸려있기 때문에 wait

Pitfalls of Lock-Based Protocol (2/2)

• 데드락 가능성은 대부분은 lock 프로토콜에 존재함
• starvation은 concurrency control 매니저가 잘못 설계되어있으면 가능함
  • 트랜젝션이 X-lock을 기다리는 동안 다른 트랜젝션에 S-lock을 기다릴 경우
  • 데드락 상황에서 같은 트랜젝션은 반복적으로 롤백됨
• concurrency control 매니저를 잘 설계하면 starvation 방지가능

Two-Phase Locking Protocol (1/2)

• conflict-serializable 스케쥴을 보장

• Phase 1 : Growing Phase

  • 트랜젝션이 lock 획득 가능
  • 트랜젝션이 lock release 불가능

• Phase 2 : Shrinking Phase

  • 트랜젝션이 lock 획득 불가능
  • 트랜젝션에 lock release 가능

• 트랜젝션이 각 lock 포인트에 따라 직렬화 가능한것이 보장됨

Two-Phase Locking Protocol (2/2)

• two-phase locking은 데드락 방지를 보장하진 않음

• Cascading rollback은 가능함

• Strict 2PL : Transaction이 종료되는 시점에 모든 x-lock들을 전부 unlock하는 방법(x-lock은 종료될 때까지 계속 유지)

• Rigorous 2PL : x-lock 뿐만 아니라 s-lock을 포함한 모든 lock을 Transaction이 종료될 때까지 유지

Example of Cascading Rollback #1

Example of Cascading Rollback #2

• T5에 Failure가 발생 : T5가 했던 변경사항을 전부 Rollback 해야함. -> Write(A)를 원복해야 함.

• 그러면 T6의 read(A)값도 잘못된 값을 읽었기 때문에 Rollback 됨.

• T7의 read(A)값도 잘못된 값을 읽었기 때문에 Rollback 발생 -> Cascading Rollback -> 치명적

Timestamp-Based Protocols (1/3)

• 각 트랜젝션이 시작 될 때 timestamp를 발행

• old transaction에 우선권 부여

• 트랜젝션 매니저는 아래를 관리

  • W-timestamp(Q) is the largest timestamp of any transaction that executed write(Q) successfully
  • R-timestamp(Q) is the largest timestamp of any transaction that executed read(Q) successfully

Timestamp-Based Protocols (2/3)

• read나 write 연산의 conflict시 ts를 따짐

• 만약 Ti가 read(Q)를 발행한다고 가정

  • TS(Ti) < W-timestamp(Q)이면 이미 dirty된 데이터를 읽는 다는 것이니 Ti를 롤백
  • TS(Ti) >= W-timestamp(Q)이면 read 연산이 수행되고 R-timestamp(Q)가 max(R-timestamp(Q), TS(Ti))로 업데이트

Timestamp-Based Protocols (3/3)

• Ti가 write(Q)를 발행했다고 가정
  • TS(Ti) < R-timestamp(Q) 이면 이미 읽은 시간보다 과거 시간에 write를 시도하는 것이므로 reject
  • TS(Ti) < W-timestamp(Q)이면 이미 써진 시간보다 과거에 write를 시도한 것이므로 역시 reject
  • 위 케이스가 아니면 write연산은 수행되고 W-timestamp(Q)는 TS(Ti)로 업데이트

Correctness of Timestamp-Ordering Protocol

• timestamp-ordering 프로토콜은 serializability를 보장하여 precedence graph의 cycle이 없음

• 타임스탬프 프로토콜은 트랜젝션의 대기가 없으므로 데드락이 없음

• 하지만 cascade-free는 아니며 recoverable 하지 않음

Recoverability and Cascade Freedom

• 타임스탬프 프로토콜의 문제점
  • Ti가 abort, Tj가 Ti에 의해 쓰여진 데이터를 이미 읽었다 가정
  • Tj는 반드시 abort 되어야하지만 이미 commit되었다면 복구 불가능
  • 나아가, Tj의 값을 읽은 경우 모두 롤백되어야 함
  • 이런 형태의 롤백을 cascading rollback이라 부름
• 솔루션
  • 트랜젝션의 구조화 되어 write가 제일 마지막에 처리 되어야함
  • 모든 쓰기 트랜젝션은 atomic해야함

Deadlock Handling

• 모든 트랜젝션이 다른 트랜젝션을 기다리고 있으면 시스템이 데드락됨

• 데드락 방지 프로토콜이 이를 막아줌

  • 각 트랜젝션이 시작되기 전 사용되는 모든 데이터를 lock함(pre-declaration)
  • (graph-based protocol)

Deadlock Handling #2

• Prevention : 아예 Deadlock을 발생시키지 않기 위해 까다로운 제약조건을 건다.

• Detection : 일정 주기로 deadlock이 발생할 지 체크.

• Resolution : Cycle이 구성된 Transaction 중 하나를 강제종료해서 Deadlock 복구 –> Cycle 해제 (victim)

• “wait-for graph” : Dead-lock 발생여부를 Check하는 그래프. Cycle이 있으면 Deadlock 이다.

Timeout-Based Schemes

• 롤백 트랜젝션이 원본 타임스탬프 기준으로 재시작 됨

• 오래된 트랜젝션이 우선함

• Timeout-Base 스키마

  • 트랜젝션은 특정 시간 동안만 기다리고 이후 트랜젝션이 롤백됨
  • 데드락이 불가능해짐
  • 구현이 간단하지만 starvation문제 가능성 있음 좋은 timeout 값을 정하기 어려움

Deadlock Detection (1/2)

• 데드락은 wait-for 그래프로 탐지됨

• 그래프에서 cycle이 발생하면 데드락 상태임

Deadlock Detection (2/2)

Deadlock Recovery

• 데드락이 탐지되면
  • 몇몇 트랜젝션은 롤백되어야함 최소한의 롤백비용을 가지는 희생자를 찾아야함
  • 롤백
  • 전체 롤백
  • 더 효과적인 롤백은 데드락을 끊을수 있는 트랜젝션만 롤백
  • 같은 트랜젝션이 계속 victim으로 지정되면 starvation가능성 있음 롤백 횟수를 가중치로 만들어 starvation을 피해야함