동시성(병행) 제어

• 동시성 제어의 개요
  • 정의
    • 데이터베이스 일관성의 파괴를 막기 위해 병행 트랜잭션 들 간의 상호 작용을 제어하는 것을 의미
    • 여러 개의 데이터베이스 트랜잭션들이 동시에 성공적으로 실행될 수 있도록 지원하는 것을 의미
  • 목적
    • 프로세스와 디스크 활용(즉, 시스템 활동도)의 증가
    • 트랜잭션 처리도(Throughput) 증가, 즉 단위 시간당 트랜잭션 처리 건수의 증가
    • 트랜잭션의 평균 응답 시간의 감소
    • 데이터베이스 공유도의 최대화 보장
         
• 동시성 제어의 필요성
  동시성 제어가 실패하는 경우 발생하는 오류 현상
  • 갱신 분실(Lost Update)
    2개 이상의 트랜잰션이 같은 데이터를 공유하여 갱신할 때, 한 트랜잰션이 갱신한 내용이 다른 트랜잭션의 갱신에 의해 잃어버리게 되는 현상
  • 불일치성(Inconsistency)
    다수의 사용자가 동시에 데이터베이스에 접근하여 갱신한 결과, 데이터베이스 내의 데이터들이 상호 일치하지 않아 모순된 정보가 발생하는 현상
  • 연쇄 복구(Cascading Rollback)
    다수의 트랜잭션들이 실행 중에 특정 트랜잭션이 처리한 내용을 복구해야 하는 경우, 다른 트랜잭션이 처리한 부분에 대해서도 연쇄적으로 복구해야 하는 현상
  • 부정확한 요약
    한 트랜잭션이 일부 레코드들을 갱신하고 있는 중에 다른 트랜잭션이 전체 레코드들에 대해 그룹 합수를 수행하고 있을 때, 어떤 값은 갱신 전의 값으로, 어떤 값은 갱신 후의 값으로 계산하는 현상
     
• 동시성 제어 기법
  • 스케줄의 정의 및 종류
    • 스케줄이란 트랜잭션들의 연산들이 실행되는 순서를 의미
    • 직렬 스케줄은 서로 다른 트랜잭션들의 연산 사이에 인터리빙이 없는 스케줄이고, 병행 스케줄은 서로 다른 트랜잰션들의 연산 사이에 인터리빙이 있는 스케줄
      • 인터리빙이 없는 스케줄 - 여러 개의 트랜잭션들의 연산들이 순차적으로 나타나는 스케줄을 의미
      • 인터리빙이 있는 스케줄 - 여러 개의 트랜잭션들의 연산들이 섞여 있는 스케줄을 의미
  • 직렬 가능성(Serialilzability)
    • 만일 n개의 트랜잭션들에 대한 병행 스케줄 S가 동일한 n개의 트랜잭션에 대한 어떤 직렬 스케줄 S'와 동등하다면 스케줄 S는 직렬 가능 스케줄이라 함
    • 병행 스케줄 S가 직렬 가능 스케줄이라면 S는 갱신 분실, 불일치성, 연쇄복구 문제 등이 발생하지 않는 스케줄을 의미
    • 대부분의 DBMS는 모든 트랜잭션들이 특정 규약을 준수한다면, 그 트랜잭션들이 참여하고 있는 병행 스케줄이 직렬 가능하다는 것을 보장할 수 있는 동시성 제어 기법을 사용함
  • 충돌 직렬 가능성
    • 주어진 데이터 항목 Q에 대해서 만약에 I_i 와 I_j 가 각각 트랜잭션 T_i와 T_j의 명령어일 때
      • I_i = read(Q), I_j = read(Q) : 비충돌
      • I_i = read(Q), I_j = write(Q) : 충돌
      • I_i = write(Q), I_j = read(Q) : 충돌
      • I_i = write(Q), I_j = write(Q) : 충돌
    • 만약 I_i 와 I_j 가 스케줄 내에서 연속적인 위치에 있고 비충돌이며, 이들이 스케줄 내에서 서로 교환되어도 결과에는 영향을 주지 않음
    • 만약 S가 비충돌 명령어들의 연속적인 교환으로 S'로 변환되었다면 S와 S'은 충돌 동치(Equivalent)라고 함
    • 만약 S가 직렬 스케줄과 충돌 동치이면 S는 충돌 직렬 가능이라 함
  • 주요 동시성 제어 기법
    • 기본 락킹(Locking) 기법, 2단계 락킹(2PL; 2 Phase Locking) 기법
    • 타입 스탬프, 낙관적 기법, 다중 버전(MVCC; Multi-Version Concurrency Control) 기법
         
• 기본 락킹 기법
  • 기본 락킹 기법의 정의
    • 트랜잭션이 데이터에 접근하기 전에 먼저 랑킹 연산 수행
    • 접근하고자 하는 데이터에 락이 걸려 있으면 해제될 때까지 대기
    • 언제나 어떤 한 데이터 항목에 대해 하나의 트랜잭션만이 락 가능
  • 락킹의 단위
    • 락킹되는 데이터의 크기 또한 락 연산의 대상
    • 락킹 단위가 커지면 락킹 수가 적어 관리하기 쉽지만 공유성 수준이 낮아지고, 락킹 단위가 작아지면 락킹 수가 많아 관리하기 복잡하지만 공유성 수준이 높아짐
      
  • 락킹의 구현
    • Lock과 Unlock 연산으로 트랜잭션의 데이터 항목을 제어
      • 하나의 트랜잭션이 데이터 x에 접근할 때 먼저 lock(x) 연산 수행하고, 작업이 끝나면 unlock(x) 연산 수행(즉, 데이터 x에 대한 읽기 락을 걸기 위해서 lock-S(x)(공유(Shared)락)을 수행하고 쓰기 락을 걸기 위해서는 lock-X(x)(배타(Exclusive)락)을 수행)
      • 다른 트랜잭션은 unlock(x) 연산이 수행되어 락이 해제된 후에 접근이 가능
    • 락은 데이터 항목에 대한 접근 상호 배타적(Mutual Exclusion)으로 하기 위한 것
    • 락 호환성

	공유 락	배타 락
공유 락	허용	불가
배타 락	불가	불가

• 기본 락킹 기법의 문제점
  • 데이터 항목에 대하여 너무 일찍 Unlock을 수행하는 경우, 질렬 가능성을 보장하지 못함
    • 트랜잭션이 Lock, Unlock을 하는 시점에 대한 규약이 추가로 필요
  • 직렬 가능성을 보장하지 못하는 락킹을 수행하고 있는 트랜잭션 예
    • T1, T2와 같은 락킹은 직렬 가능성을 조장하기에는 불충분
    • T1의 A와 B의 read 사이에 T2에 의해 A나 B가 갱신되면 출력되는 합계가 틀려짐

T1	T2
lock-S(A) read(A) unlock(A) lock-S(B) read(B) unlock(B) display(A+B)	. . . lock-X(A) update(A+100) unlock(A)

• 데드락(Deadlock)
  • T2가 lock-S(B)룰 실행하면 T1이 B에 걸고 있는 락을 해제할 때까지 T2는 대기하게 되고, 반면에 T1이 lock-X(A)를 실행하면 T2가 A에 걸고 있는 락을 해제할 때까지 T1이 대기하게 되어, T1과 T2 모두는 무한정 대기 상태에 놓이게 되는 현상
  • 데드락을 처리하려면 T1또는 T2 중 하나를 복구 시켜 해당 락을 해제해야 함

T1	T2
Lock-X(B) Read(B) B := B-50 Write(B)         Lock-X(A)	. . . . Lock-S(A) Read(A) Lock-S(B)

• 데드락 예방 방법
  • Predeclaration 기법
    각 트랜잭션이 실행을 시작하기 전에 필요한 모든 데이터 항목들에 미리 락을 걸도록 요구
  • Graph-Based 기법
    모든 데이터 항목들에 대해서 부분 순서를 부여하고 트랜잭션은 이 부분 순서에 따라 데이터 항목들에 대해 락을 걸 수 있도록 함
  • Wait-Die 기법(Non-Preemptive)
    • Older 트랜잭션은 younger 트랜잭션이 데이터 항목에 대해 해제하는 것을 기다릴 수 있지만, younger 트랜잭션은 older 트랜잭션이 데이터 항목에 대해 해제하는 것을 기다리지 않고 대신 복구됨
    • 복구된 트랜잭션이 처음 부여된 타임 스탬프를 가지고 재 시작 된다면 스타베이션을 예방할 수 있음
  • Wound-Wait 기법(Preemptive)
    • younger 트랜잭션들은 older 트랜잭션들을 기다릴 수 있으나, older 트랜잭션은 기다리는 대신에 younger 트랜잭션의 복구를 강요함
    • 복구된 트랜잭션이 처음 부여된 타임 스탬프를 가지고 재 시작 된다면 스타베이션을 예방할 수 있음
  • Timeout-Based 기법
    • 트랜잭션이 주어진 시간 동안만 락을 기다리다가 그 시간이 초과되면 복구됨
    • 구현하기는 간단하지만 스타베이션이 발생할 수 있음
• 데드락 탐지 방법
  트랜잭션 대기(Wait-for) 그래프를 작성하여 사이클(Cycle)의 존재성을 검사(즉, 사이클이 있으면 데드락이 존재)

• 스타베이션(Starvation)
  • 다른 트랜잭션들(T1, .., Tn)이 연속적으로 한 데이터 항목에 대해 S-락을 요청하고 부여받고 있는 동안에 트랜잭션 T()이 같은 데이터 항목에 대한 X-락을 대기하고 있는 경우
  • 특정 트랜잭션 T_i가 데드락 발생 이유로 반복적으로 복구되는 경우
     

• 2단계 락킹 규약(Twoo-Phase Locking Protocol)
  • 정의 및 특징
    • 기본 락킹 기법의 문제점을 해결
    • 모든 트랜잭션들이 Lock과 Unlock 연산을 2단계로 구분하여 실행
    • 직렬 가능성을 보장하는 규약이나 데드락을 예방할 수 없음
  • 2단계

구분	내용
증가 단계(Growing Phase)	트랜잭션은 Lock만 수행 가능 Unlock은 수행할 수 없는 단계
감소 단계(Shrinking Phase)	트랜잭션은 Unlock만 수행 가능 Lock은 수행할 수 없는 단계

• 2단계 락킹 규약의 스케줄 예

T1	T2
lock-S(A) read(A) lock-X(B) unlock(A) read(B) write(B) unlock(B)	lock-S(B) read(B) lock-X(A) unlock(B) read(A) write(A) unlock(A)

• 종류
  • Strict 2 단계 락킹 규약
    • 트랜잭션이 Commits/Abort 할 때까지 모든 배탁 락들을 우지
    • 연쇄 복구를 방지할 수 있음
  • Rigorous 2 단계 락킹 규약
    • 트랜잭션이 Commits/Aborts 할 때까지 모든 락(즉, 공유 락 및 배타 락)들을 유지
    • 트랜잭션들이 Commit한 순서대로 직렬 가능
• 유령 현상(Phantom Phenomenon)
  • 튜플단위 락이 사용되는 경우 릴레이션을 스캔하는 트랜잭션과 릴레이션에 튜플을 삽입하는 트랜잭션은 공통으로 접근하는 튜플은 없지만 (개념적으로) 충돌이 발생할 수 있음(즉, 비직렬 가능 스케줄)
  • 이때, 스캔하는 트랜잭션은 다른 트랜잭션이 삽입한 어떤 튜플들은 볼 수 없지만 다른 튜플들은 볼 수 있는 현상
  • 해결책 : 인덱스 락킹 규약 사용
     

• 타입 스탬프(Timestamp) 기법
  • 타임스탬프 기법의 개념
    • 각 트랜잭션이 시스템에 들어오는 순서대로 시스템에서 생성하는 고유 번호인 타임스템프를 부여하여 트랜잭션간의 순서를 미리 지정
    • 타임스템프를 동시성 제어의 기준으로 사용하여 상충되는 연산들을 타임스탬프 순서대로 처리함으로써 직렬성을 보장
  • 타입스탬프의 생성 방법

구분	내용
시스템 시계 사용법	트랜잭션이 시스템에 들어올 때의 시스템 시계의 시간을 적요
논리적 카운터 사용법	트랜잭션이 시스템으로 들어올 때의 계수기 값을 적용

• 타입스탬프 기반 프로토콜
  • 각각의 데이터 Q는 다음과 같은 2가지 타임스탬프를 가짐
    • W-Timestamp(Q)
      Write(Q)를 성공적으로 수행시킨 어떤 트랜잭션의 최대 타임 스태프
    • R-Timestamp(Q)
      Read(Q)를 성공적으로 수행시킨 어떤 트랜잭션의 최대 타임 스태프
  • 트랜잭션 T_i가 Read(Q)를 실행할 때(여기서 TS(T_i)는 T_i의 타임스템프를 의미)
    • TS(T_i) ≤ W-Timestamp(Q)이면, T_i는 복구
    • TS(T_i) ≥ W-Timestamp(Q)이면, T_i의 Read(Q)는 실행
  • 트랜잭션 T_i가 Write(Q)를 실행할 때
    • TS(T_i) < R-Timestamp(Q)이면, T_i는 복구
    • TS(T_i) < W-Timestamp(Q)이면, T_i는 복구
    • 나머지의 경우이면 T_i의 Write(Q)는 실행
• 타임스탬프 기법 특징
  • 트랜잭션이 기다리는 경우가 없으므로 데드락을 방지
  • 복구 발생 확률이 높으면, 연쇄복구를 초래할 수 있음
       

• 낙관적 기법
  • 개념
    트랜잭션 수행 동안은 어떠한 검사도 하지 않고, 트랜잭션 종료 시에 일괄적으로 검사하는 동시성 제어 기법
  • 특징
    • 연산은 버퍼에서 이루어지며, 검증한 후 결과를 디스크에 반영하거나 복구
    • 트랜잭션 수행 마지막에 갱신 사항들의 직렬 가능성 위반 여부를 검사하여 검증될 경우 일시에 데이터베이스로 반영
    • 읽기 연산이 많은 경우에 적합하며, 데드락과 연쇄 복구가 발생하지 않음
  • 트랜잭션 생명주기
    • 판독 단계(Read Phase)
      지역 변수만을 이용해 트래잭션 실행
    • 검증 단계(Validation Phase)
      무결성 유지 여부 검사 후 복구 여부 판정
    • 기록 단계(Write Phase)
      실행 결과를 디스크에 반영
  • 트랜잭션의 3가지 타임스탬프
    • Start(T_i)
      트랜잭션 T_i가 판목 단계에 들어가면서 실행을 시작한 시간
    • Validation(T_i)
      트랜잭션 T_i가 검증 단계에 들어가면서 검증을 시작한 시간(TS(T_i)는 Validation(T_i) 값으로 주어짐
    • Finish(T_i)
      트랜잭션 T_i가 최종 기록 단계를 완료한 시간
  • 트랜잭션 T_j에 대한 검증 테스트
    • 만약, TS(T_i) < TS(T_j)인 모든 트랜잭션 Ti 에 대해 아래의 조건들 중에서 하나가 만족되면 검증이 성공되어 T_j는 완료될 수 있음
      • Finish(T_i) < Start(T_j)
      • Finish(T_j) < Start(T_i) < Validation((T_j)이고 T_i에 의해 기록된 데이터 항목들의 집합이 트랜잭션 T_i에 의해서 판독된 데이터 항목들의 집합과 교차(intersect)되지 않음
    • 그렇지 않으면, 검증은 실패되어 T_i는 abort됨
       
• 다중 버전 기법
  • 개념
    동시성 제어를 위해 데이터 항목이 변경될 때 그 데이터 항목의 이전 값을 보존하는 기법
  • 한 데이터 항목에 대해 여러 개의 버전을 유지하는 기법
    • 데이터 항목Q에 대해 여러 버전<Q₁, Q₂, …, Q_m>이 시스템에 의해 유지
    • 각 데이터 항목의 버전들을 유지하기 위해 많은 저장 공간이 필요
  • 각각의 버전 Q_K에 대해 3개의 필드 값 보유
    • 내용(Content) : 버전 Q_K의 값
    • W-Timestamp(Q_K) : 버전 Q_K를 생성한 트랜잭션의 타임스템프
    • R-Timestamp(Q_K) : 버전 QK를 성공적으로 판독한 트랜잭션 중에서 제일 큰 타임스탬프
  • 다중 버전 타임스탬프 기법
    • T_i가 Read(Q) 실행
      반환되는 값은 버전 Q_K의 내용(Q_K는 기록 타임스탬프가 TS(T_i) 보다 작거나 같으면서 가장 큰 값을 갖는 Q의 버전을 의미)
    • T_i가 Write(Q) 실행
      • 만약에 TS(T_i) < R-Timestamp(Q_K)이면, 트랜잭션 T_i는 복구됨
      • 만약에 TS(T_i) < W-Timestamp(Q_K)이면, Q_K의 내용은 Overwritten 됨
      • 그 이외의 경우이면, Q의 새로운 버전이 생성됨
  • 연쇄 복구를 초래
    연쇄 복구란 다수의 트랜잭션들이 실행 중 특정 트랜잭션의 처리를 복구해야 하는 경우, 다른 트랜잭션이 처리한 부분에 대해서도 연쇄적으로 복구해야 하는 현상