• 동시성 제어의 개요
    • 정의
      • 데이터베이스 일관성의 파괴를 막기 위해 병행 트랜잭션 들 간의 상호 작용을 제어하는 것을 의미
      • 여러 개의 데이터베이스 트랜잭션들이 동시에 성공적으로 실행될 수 있도록 지원하는 것을 의미
    • 목적
      • 프로세스와 디스크 활용(즉, 시스템 활동도)의 증가
      • 트랜잭션 처리도(Throughput) 증가, 즉 단위 시간당 트랜잭션 처리 건수의 증가
      • 트랜잭션의 평균 응답 시간의 감소
      • 데이터베이스 공유도의 최대화 보장

           

  • 동시성 제어의 필요성

    동시성 제어가 실패하는 경우 발생하는 오류 현상

    • 갱신 분실(Lost Update)

      2개 이상의 트랜잰션이 같은 데이터를 공유하여 갱신할 때, 한 트랜잰션이 갱신한 내용이 다른 트랜잭션의 갱신에 의해 잃어버리게 되는 현상

    • 불일치성(Inconsistency)

      다수의 사용자가 동시에 데이터베이스에 접근하여 갱신한 결과, 데이터베이스 내의 데이터들이 상호 일치하지 않아 모순된 정보가 발생하는 현상

    • 연쇄 복구(Cascading Rollback)

      다수의 트랜잭션들이 실행 중에 특정 트랜잭션이 처리한 내용을 복구해야 하는 경우, 다른 트랜잭션이 처리한 부분에 대해서도 연쇄적으로 복구해야 하는 현상

    • 부정확한 요약

      한 트랜잭션이 일부 레코드들을 갱신하고 있는 중에 다른 트랜잭션이 전체 레코드들에 대해 그룹 합수를 수행하고 있을 때, 어떤 값은 갱신 전의 값으로, 어떤 값은 갱신 후의 값으로 계산하는 현상

       

  • 동시성 제어 기법
    • 스케줄의 정의 및 종류
      • 스케줄이란 트랜잭션들의 연산들이 실행되는 순서를 의미
      • 직렬 스케줄은 서로 다른 트랜잭션들의 연산 사이에 인터리빙이 없는 스케줄이고, 병행 스케줄은 서로 다른 트랜잰션들의 연산 사이에 인터리빙이 있는 스케줄
        • 인터리빙이 없는 스케줄 - 여러 개의 트랜잭션들의 연산들이 순차적으로 나타나는 스케줄을 의미
        • 인터리빙이 있는 스케줄 - 여러 개의 트랜잭션들의 연산들이 섞여 있는 스케줄을 의미
    • 직렬 가능성(Serialilzability)
      • 만일 n개의 트랜잭션들에 대한 병행 스케줄 S가 동일한 n개의 트랜잭션에 대한 어떤 직렬 스케줄 S'와 동등하다면 스케줄 S는 직렬 가능 스케줄이라 함
      • 병행 스케줄 S가 직렬 가능 스케줄이라면 S는 갱신 분실, 불일치성, 연쇄복구 문제 등이 발생하지 않는 스케줄을 의미
      • 대부분의 DBMS는 모든 트랜잭션들이 특정 규약을 준수한다면, 그 트랜잭션들이 참여하고 있는 병행 스케줄이 직렬 가능하다는 것을 보장할 수 있는 동시성 제어 기법을 사용함
    • 충돌 직렬 가능성
      • 주어진 데이터 항목 Q에 대해서 만약에 Ii Ij 가 각각 트랜잭션 Ti와 Tj의 명령어일 때
        • Ii = read(Q), Ij = read(Q) : 비충돌
        • Ii = read(Q), Ij = write(Q) : 충돌
        • Ii = write(Q), Ij = read(Q) : 충돌
        • Ii = write(Q), Ij = write(Q) : 충돌
      • 만약 Ii Ij 가 스케줄 내에서 연속적인 위치에 있고 비충돌이며, 이들이 스케줄 내에서 서로 교환되어도 결과에는 영향을 주지 않음
      • 만약 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-락을 대기하고 있는 경우
    • 특정 트랜잭션 Ti가 데드락 발생 이유로 반복적으로 복구되는 경우

       

  • 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)를 성공적으로 수행시킨 어떤 트랜잭션의 최대 타임 스태프

    • 트랜잭션 Ti가 Read(Q)를 실행할 때(여기서 TS(Ti)는 Ti의 타임스템프를 의미)
      • TS(Ti) ≤ W-Timestamp(Q)이면, Ti는 복구
      • TS(Ti) ≥ W-Timestamp(Q)이면, Ti의 Read(Q)는 실행
    • 트랜잭션 Ti가 Write(Q)를 실행할 때
      • TS(Ti) < R-Timestamp(Q)이면, Ti는 복구
      • TS(Ti) < W-Timestamp(Q)이면, Ti는 복구
      • 나머지의 경우이면 Ti의 Write(Q)는 실행
  • 타임스탬프 기법 특징
    • 트랜잭션이 기다리는 경우가 없으므로 데드락을 방지
    • 복구 발생 확률이 높으면, 연쇄복구를 초래할 수 있음

         

  • 낙관적 기법
    • 개념

      트랜잭션 수행 동안은 어떠한 검사도 하지 않고, 트랜잭션 종료 시에 일괄적으로 검사하는 동시성 제어 기법

    • 특징
      • 연산은 버퍼에서 이루어지며, 검증한 후 결과를 디스크에 반영하거나 복구
      • 트랜잭션 수행 마지막에 갱신 사항들의 직렬 가능성 위반 여부를 검사하여 검증될 경우 일시에 데이터베이스로 반영
      • 읽기 연산이 많은 경우에 적합하며, 데드락과 연쇄 복구가 발생하지 않음
    • 트랜잭션 생명주기
      • 판독 단계(Read Phase)

        지역 변수만을 이용해 트래잭션 실행

      • 검증 단계(Validation Phase)

        무결성 유지 여부 검사 후 복구 여부 판정

      • 기록 단계(Write Phase)

        실행 결과를 디스크에 반영

    • 트랜잭션의 3가지 타임스탬프
      • Start(Ti)

        트랜잭션 Ti가 판목 단계에 들어가면서 실행을 시작한 시간

      • Validation(Ti)

        트랜잭션 Ti가 검증 단계에 들어가면서 검증을 시작한 시간(TS(Ti)는 Validation(Ti) 값으로 주어짐

      • Finish(Ti)

        트랜잭션 Ti가 최종 기록 단계를 완료한 시간

    • 트랜잭션 Tj에 대한 검증 테스트
      • 만약, TS(Ti) < TS(Tj)인 모든 트랜잭션 Ti 에 대해 아래의 조건들 중에서 하나가 만족되면 검증이 성공되어 Tj는 완료될 수 있음
        • Finish(Ti) < Start(Tj)
        • Finish(Tj) < Start(Ti) < Validation((Tj)이고 Ti에 의해 기록된 데이터 항목들의 집합이 트랜잭션 Ti에 의해서 판독된 데이터 항목들의 집합과 교차(intersect)되지 않음
      • 그렇지 않으면, 검증은 실패되어 Ti는 abort됨

         

  • 다중 버전 기법
    • 개념

      동시성 제어를 위해 데이터 항목이 변경될 때 그 데이터 항목의 이전 값을 보존하는 기법

    • 한 데이터 항목에 대해 여러 개의 버전을 유지하는 기법
      • 데이터 항목Q에 대해 여러 버전<Q1, Q2, …, Qm>이 시스템에 의해 유지
      • 각 데이터 항목의 버전들을 유지하기 위해 많은 저장 공간이 필요
    • 각각의 버전 QK에 대해 3개의 필드 값 보유
      • 내용(Content) : 버전 QK의 값
      • W-Timestamp(QK) : 버전 QK를 생성한 트랜잭션의 타임스템프
      • R-Timestamp(QK) : 버전 QK를 성공적으로 판독한 트랜잭션 중에서 제일 큰 타임스탬프
    • 다중 버전 타임스탬프 기법
      • Ti가 Read(Q) 실행

        반환되는 값은 버전 QK의 내용(QK는 기록 타임스탬프가 TS(Ti) 보다 작거나 같으면서 가장 큰 값을 갖는 Q의 버전을 의미)

      • Ti가 Write(Q) 실행
        • 만약에 TS(Ti) < R-Timestamp(QK)이면, 트랜잭션 Ti는 복구됨
        • 만약에 TS(Ti) < W-Timestamp(QK)이면, QK의 내용은 Overwritten 됨
        • 그 이외의 경우이면, Q의 새로운 버전이 생성됨
    • 연쇄 복구를 초래

      연쇄 복구란 다수의 트랜잭션들이 실행 중 특정 트랜잭션의 처리를 복구해야 하는 경우, 다른 트랜잭션이 처리한 부분에 대해서도 연쇄적으로 복구해야 하는 현상

'데이터베이스 > 트랜잭션 관리 및 동시성 제어' 카테고리의 다른 글

트랜잭션 관리  (0) 2011.03.01
동시성(병행) 제어  (0) 2011.03.01

댓글을 달아 주세요

블로그 이미지

무강

이바닥에 살아남을려면 어떻게 해야 할까..

카테고리

정보시스템감리 (395)
사는이야기 (1)
감리 (31)
사업관리 (39)
소프트웨어공학 (49)
데이터베이스 (64)
네트워크 (77)
컴퓨터구조 (65)
정보보안 (36)
경영 및 최신기술 (31)
정보시스템감리사 (0)
정보관리기술사 (0)