Home [데이터베이스 시스템] 14강 - 동시성 제어
Post
Cancel

[데이터베이스 시스템] 14강 - 동시성 제어

Posted May 18, 2025
By mxxikr
read 23 min

💡해당 게시글은 방송통신대학교 정재화 교수님의 '데이터베이스 시스템' 강의를 개인 공부 목적으로 메모하였습니다.



학습 개요

  • 여러 사용자의 데이터베이스 요청을 동시에 실행하는 것은 시스템의 처리 율과 자원 활용도를 높이고, 개별 요청의 응답 시간을 단축 시켜 전체적인 사용자 만족도를 향상 시키기 위한 중요한 방법임
  • 그러나 트랜잭션 간의 병행 실행은 자칫하면 데이터의 일관성을 훼손하거나 무결성 제약을 위반할 위험이 있음
  • 이를 방지하기 위해 DBMS는 직렬성(serializability) 이론을 기반으로, 트랜잭션 간의 실행 순서를 제어함으로써 동시에 수행 되는 연산이 하나씩 순차적으로 수행 된 것과 동일한 효과를 내도록 보장함
  • 트랜잭션의 동시 실행에서 발생할 수 있는 문제점을 이론적으로 분석할 수 있는 기반 개념을 학습하고, 이를 해결하기 위한 동시성 제어 기법을 살펴 봄
  • 대표적인 제어 방식인 락 기반 규약과 타임 스탬프 기반 규약의 구조와 작동원리를 중심으로, 병행성을 최대화하면서도 데이터베이스의 무결성을 안전하게 유지할 수 있는 방법에 대해 학습함



주요 용어

  • 양립성 함수
    • 락의 종류에 따라 동시에 수락 될 수 있는지 판단하는 함수
  • 2단계 락킹 규약
    • 요청 단계에서 트랜잭션은 락을 추가 요청할 수 있으며, 반납 단계부터는 락을 반납 해야 하는 방식으로 직렬성을 보장하는 규약
  • 토마스 기록 규칙
    • 타임스탬프 기반 규약의 규칙으로 오래 된 쓰기를 무시하는 규칙
  • 교착 상태
    • 특정 트랜잭션 집합 내에 속하는 모든 트랜잭션이 집합 내의 다른 트랜잭션을 기다리고 있는 상태



강의록

락 기반 규약

동시성 제어의 개념

  • 트랜잭션 직렬화와 회복화는 스케줄이 데이터 일관성에 영향을 미치는 여부를 판별하고 일관성이 유지되는 상태로 실행/복원 시키기 위해 정의한 개념
  • 일관성을 훼손시키는 트랜잭션에 대해 동시성 제어를 통해 일관성 유지에 개입
    • 트랜잭션 간 연산의 순서를 제어
    • 어떠한 데이터 읽기, 쓰기 연산에도 무결성을 유지
    • 동시에 실행되는 트랜잭션 수를 증가
  • 동시성 제어 규약의 종류
    • 락 기반 규약
    • 타임스탬프 기반 규약
    • 검증 기반 규약

락 기반 규약의 개념

  • 직렬 가능성을 보장하기 위해 락(lock: 잠금)을 사용하여 데이터 항목에 연산 적용 전 트랜잭션이 락을 획득하고 연산 후 반납하도록 하는 규약
  • 락의 종류
    • 공유 락(shared lock: S)
      • 트랜잭션 T가 LS(Q) 명령으로 데이터 항목 Q에 공유 락을 획득하면 T는 Q를 읽을 수 있지만 쓰기 연산은 할 수는 없는 락
      • 읽기는 함께 작업 가능
    • 배타 락(exclusive lock: X)
      • 트랜잭션 T가 LX(Q) 명령으로 데이터 항목 Q에 대한 배타 락을 획득하면, T가 Q를 읽기/쓰기 연산을 할 수 있는 락

락 양립성

  • 트랜잭션은 연산하고자 하는 데이터에 대한 락을 획득한 후 연산 진행 가능
    • 여러 트랜잭션이 같은 데이터 항목 Q에 동시에 락을 걸 수 있는지 여부
      • 같이 락을 공유할 수 있는 지를 판단

  • 락 양립성 함수

    | | 공유 락(S) | 배타 락(X) | | — | — | — | | 공유 락(S) | 가능 | 불가능 | | 배타 락(X) | 불가능 | 불가능 |

    • 공유 락은 다른 공유 락과 양립 가능(읽기만 가능)
    • 배타 락과 다른 락과 양립 불가능
    • 배타 락의 요청은 공유 락이 반납 될 때까지 대기
    • 락의 반납은 UN() 명령 사용

예제 트랜잭션

image.png

  • 어떤 트랜잭션이 A에 대한 락을 가지고 있다면 선점한 트랜잭션이 락을 해제할 때까지 중지 상태

동시 실행 스케줄

  • T₁₀ 이 락을 일찍 반납하여 비일관적인 사태에서 데이터 접근이 가능해져 T₁₁이 정확하지 않은 결과 값을 출력

    image.png

락 반납이 지연 된 트랜잭션

image.png

락 반납 지연의 문제

  • T₁₂, T₁₃에 대한 부분 스케줄
    • T₁₂가 B에 대한 배타 락을 반환 할 때까지 T₁₃은 대기
      • 이미 T₁₂가 락을 가지고 있으므로 대기
    • T₁₃이 A에 대한 공유 락을 반환 할 때까지 T₁₂는 대기
      • A에 대한 공유 락 선점

    image.png

    • T₁₂, T₁₃가 서로를 계속 기다리는 상태
      • 락 반납을 지연한 것이 교착 상태의 원인
  • 교착 상태(deadlock)
    • 연관 된 트랜잭션 모두가 대기 상태로 전환 되어 정상적인 실행이 불가능한 상태
    • 일부 트랜잭션이 반드시 롤백

2 단계 락킹 규약 (2PL)

  • 트랜잭션은 락을 요청 · 반납하는 두 단계로 구성
    • 확장 단계
      • 락 획득은 가능, 반납은 불가 단계
    • 축소 단계
      • 락 반납은 가능, 새로운 락 획득은 불가 단계

      image.png

    • 적절한 시기에 락 반납
      • 교착 상태 감소
  • 직렬성을 보장하나 교착 상태 완전한 예방은 불가
    • 이후 더 엄격한 2단계 락킹 규약 생성

타임스탬프 기반 규약

타임스탬프 기반 규약의 개념

  • 각 트랜잭션 Tᵢ 실행의 순서를 판단하기 위해 타임스탬프 TS(Tᵢ)를 부여
    • 트랜잭션에도 데이터 항목에도 타임스탬프가 부여 됨
    • 마지막에는 최종 실행 된 값이 남아있어야 함
    • 락 기반 규약에 비해 잦은 롤백이 발생
  • 데이터 항목에 대한 타임스탬프 할당
    • W-TS(Q)
      • Write(Q)를 성공적으로 실행한 트랜잭션 중 가장 큰 타임스탬프
      • 가장 마지막으로 실행, 요청 된 트랜잭션의 타임스탬프
    • R-TS(Q)
      • Read(Q)를 성공적으로 실행한 트랜잭션 중 가장 큰 타임스탬프
      • 가장 마지막으로 실행 된 트랜잭션의 타임스탬프
  • 타임스탬프 할당 방법
    • 시스템 클럭 값
    • 논리적 계수기

Tᵢ가 Read(Q)를 수행할 때

  • TS(Tᵢ) < W - TS(Q)이면 Read 연산이 거부 되고 Tᵢ는 롤백
    • W-TS(Q)
      • 여러 트랜잭션 중 가장 마지막에 실행 요청 된 트랜잭션의 타임스탬프
  • TS(Tᵢ) ≥ W - TS(Q)이면 Read 연산이 수행되고 R-TS(Q)는 기존 R-TS(Q)와 TS(Tᵢ) 중 최대 값으로 설정

image.png

Tᵢ가 Write(Q)를 수행할 때

  • TS(Tᵢ) < R-TS(Q) 또는 TS(Tᵢ) < W-TS(Q)이면 Write 연산이 거부되고 Tᵢ는 롤백
  • 그렇지 않으면 Write 연산을 수행하고 W-TS(Q)는 TS(Tᵢ)로 설정

image.png

타임스탬프 기반 규약의 적용

  • TS(T₁₄) < TS(T₁₅)

    image.png

    image.png

토마스 기록 규칙

  • TS(Tᵢ) < R-TS(Q)이면 Write 연산이 거부되고 Tᵢ는 롤백
  • TS(Tᵢ) < W-TS(Q)이면 Write 연산은 거부 (무시)
    • Tᵢ는 롤백하지 않음

  • 그렇지 않으면 Write 연산을 수행하고 W−TS(Q)는 TS(Tᵢ)로 설정

    image.png

    image.png

교착 상태

교착 상태(deadlock)의 개념

  • 특정 트랜잭션 집합 내에 속하는 모든 트랜잭션이 집합 내의 다른 트랜잭션을 기다리고 있는 상태

    image.png

    • 두 트랜잭션 중 하나를 반드시 롤백

교착 상태 처리 방법

  • 교착 상태 발생이 비교적 높은 시스템의 경우 → 미연에 방지
    • 교착 상태 방지 규약 사용
      • 모든 데이터 항목에 대해 락을 설정하는 기법
      • 타임스탬프를 이용한 선점유 기법
  • 교착 상태 발생이 비교적 높지 않은 시스템의 경우
    • 교착 상태 탐지와 회복 기법 사용
      • 대기 그래프
      • 희생자 선정

교착 상태 방지 규약

  • 타임스탬프를 이용
    • Tⱼ가 락을 소유한 데이터 항목을 Tᵢ가 요청하는 상황
      • wait-die 기법 (비선점유 기반)
        • TS(Tᵢ) < TS(Tⱼ)일 때 Tᵢ가 기다리고 그렇지 않으면 Tᵢ를 롤백

      image.png

      • wound-wait 기법 (선점유 기반)
        • TS(Tⱼ) < TS(Tᵢ)일 때, Tᵢ가 기다리고 그렇지 않으면 Tⱼ를 롤백하고 락을 이양

        image.png

교착 상태 탐지와 회복

  • 교착 상태 발생이 비교적 높지 않은 시스템의 경우 주기적으로 교착 상태를 탐지하고 발생 시 회복 절차를 수행
  • 탐지 및 회복 절차
    • 트랜잭션이 할당된 데이터 항목과 현재 요청되고 있는 데이터 항목에 대한 정보를 유지
    • 교착 상태가 발생 여부를 판별하기 위해 시스템의 상태를 검사하는 알고리즘을 주기적으로 수행
    • 교착 상태가 검출되면 시스템은 교착 상태로부터 회복을 위한 절차를 수행

교착 상태 탐지

  • 대기 그래프(wait-for graph)를 이용하여 확인 가능
    • 정점 V는 시스템 내의 트랜잭션으로 구성되며
    • 간선 E는 트랜잭션의 순서쌍 (Tᵢ, Tⱼ)으로 이루어짐
      • Tᵢ가 요청한 데이터의 락을 Tⱼ가 소유하고 있으며, Tᵢ는 Tⱼ가 락을 반납하기 대기하는 상태
  • 대기 그래프에 사이클이 있다면 교착 상태가 발생
  • 교착 상태 탐지-대기 그래프 이용

    • 교착 상태 아님

      image.png

      • T₁₅ 실행이 완료 되어 T₁₅가 데이터 항목 반납 → T₁₃ 실행 → T₁₄ 실행 → T₁₂ 실행
      • T₁₂
        • T₁₃이 소유하고 있는 데이터 항목의 락을 요청해서 대기 중
      • T₁₄
        • T₁₃이 소유하고 있는 데이터 항목의 락을 요청해서 대기 중
      • T₁₃
        • T₁₅가 소유하고 있는 데이터 항목의 락을 요청해서 대기 중

    • 교착 상태

      image.png

      • T₁₃, T₁₄, T₁₅가 서로 기다리는 교착 상태

교착 상태의 회복

  • 희생자 선정
    • 롤백 비용이 가장 적은 트랜잭션을 선택
      • 연산을 수행한 시간과 남은 작업을 마치기 위한 시간
      • 사용한 데이터와 나머지 트랜잭션 실행에 필요한 추가적인 데이터의 양
      • 롤백에 포함되는 트랜잭션의 개수
  • 희생자 롤백
    • 어느 시점까지 롤백 할 것인지 결정
    • 전체 롤백 VS 교착 상태를 해결하는 지점
    • 모든 트랜잭션의 상태에 대한 정보를 부가적으로 유지
  • 무한정 기다림(starvation) 해결
    • 동일 트랜잭션이 계속 희생자로 선정되지 않도록 희생자 선정 시 롤백 횟수를 고려
      • 롤백 횟수를 카운트



연습 문제

  1. 타임스탬프 순서 규약에서 타임스탬프를 할당하는 방법인 것은?

    a. 시스템 시계

    • 타임스탬프 순서 기법이란 로킹 규약으로 서로 상충되는 트랜잭션의 직렬성 순서를 결정하기 위해 트랜잭션에 부여 된 타임 스탬프 값을 이용하는 기법을 말함
    • 타임스탬프 순서 기법을 구현하는데 시스템 시계(system clock)와 논리적 계수기가 보편적으로 이용 됨

  2. 교착 상태 방지 기법으로, 오래 된 트랜잭션이 최근의 트랜잭션을 기다리는 대신 강제 복귀시킨다는 선점(preemptive) 기법인 것은?

    a. wound-wait 기법

    • 교착 상태 방지 기법에는 크게 wound-wait 기법과 wait-die 기법이 있음
    • 이 중 wound-wait 기법은 선 점유 기법을 기반으로 타임스탬프가 작은 트랜잭션(오래 된 트랜잭션)이 큰 트랜잭션을 복귀 시키는 방법으로 교착 상태를 방지함

  3. 교착 상태의 회복에서 ‘교착 상태의 트랜잭션 집합이 주어지면 교착 상태를 해결하기 위하여 복귀 시킬 트랜잭션을 결정하여야 한다.’라고 할 때, 이 대상을 무엇이라 하는가?

    a. 희생자

    • 교착 상태 회복을 위해서는 교착 상태에 관여하고 있는 트랜잭션 중 일부를 복귀 시켜야 하는데 복귀로 선택 된 트랜잭션을 희생자(victim)이라고 함



정리 하기

  • 동시성 제어는 다수의 트랜잭션이 동시에 동일한 데이터에 대해 읽기 연산을 수행하거나 갱신 연산을 수행하려고 할 때, 데이터의 무결성을 유지하면서도 동시에 실행될 수 있는 트랜잭션의 수를 제어하는 기법임
  • 대표적인 동시성 제어 기법에는 락 기반 규약, 타임스탬프 규약, 검증 기반 규약(protocol) 등이 있음
  • 락(lock)이란 한 트랜잭션이 데이터 항목에 접근하는 동안에는 다른 트랜잭션이 그 데이터 항목에 접근하는 것을 제어하는 기법임
  • 락킹 기법에는 공유 락(shared lock)과 배타 락(exclusive lock)이 있음
    • 공유 락은 양립 가능하지만 배타 락은 다른 공유, 배타 락과 양립될 수 없음
  • 2단계 락킹 규약(two–phase locking protocol)은 각 트랜잭션이 락을 요청하는 단계와 언락을 요청하는 두 단계로 구성되어 있음
    • 트랜잭션은 요청 단계에서부터 시작되며 필요에 따라서 락을 요청할 수 있음
    • 만약 트랜잭션이 하나의 락을 반납하게 되면 그때부터 트랜잭션은 반납 단계로 되며 더 이상 락 요청을 할 수 없음
  • 타임스탬프 순서(timestamp ordering) 기법은 트랜잭션 충돌을 위해 직렬 가능한 순서를 정하는 데 가장 많이 사용하는 방법으로, 시스템의 각 트랜잭션마다 고유한 타임스탬프를 부여함
  • 타임스탬프가 직렬 가능성을 보장하므로, TS(T₁)＜TS(T₂)라면 시스템은 T₁을 처리한 후 T₂를 처리하여 직렬 스케줄과 동등하도록 보장함



체크 포인트

  1. 5개 트랜잭션의 충돌 직렬 가능 스케줄에 대한 우선순위 그래프이다. 이에 대한 설명으로 옳은 것만을 모두 고르면?

    1
2
3
4

     ㄱ. 동등한 직렬 스케줄은 6개이다.
 ㄴ. 모든 동등한 직렬 스케줄은 T1에서 시작하고 T5에서 종료한다.
 ㄷ. T2와 T3은 동시에 수행할 수 있지만, T5는 T4가 수행된 후에 수행해야 한다.
 ㄹ. T2와 T5는 같은 데이터 항목에 대한 write 연산이 없다.

    image.png

    a. ㄱ, ㄹ

    • 우선 순위 그래프 분석
      • T₂는 T₁이 끝나기 만을 기다림
        • T₁보다 T₂가 먼저 실행될 수 없음
      • T₄는 T₂와 T₁이 끝나기 만을 기다림
      • T₅는 T₃가 끝나기 만을 기다림
      • T₃는 T₁이 끝나기 만을 기다림
    • 동등한 직렬 스케줄
      • T₁ → T₃ → T₅ → T₂ → T₄
      • T₁ → T₂ → T₄ → T₃ → T₅
      • T₁ → T₂ → T₃ → T₄ → T₅
      • T₁ → T₂ → T₃ → T₅ → T₄
      • T₁ → T₃ → T₂ → T₅ → T₄
      • T₁ → T₃ → T₂ → T₄ → T₅

  2. 다음 스케줄에 대해 타임스탬프 순서 기법을 적용하였을 때 설명이 올바른 것은? (TS(Ti)는 트랜잭션 Ti의 타임스탬프이고, read_TS(x)는 read(x) 연산을 성공적으로 수행한 트랜잭션의 타임스탬프 중 가장 큰 것이고, write_TS(x)는 write(x) 연산을 성공적으로 수행한 트랜잭션들의 타임스탬프 중 가장 큰 것이다. read_TS(x)와 write_TS(x)의 초기 값을 모두 10이라고 가정한다.)

    1
2
3

     2시: T1 read(x)
 3시: T2 write(x)
 4시: T1 write(x)

    a. 토마스 기록 규칙을 적용하면, T1의 write(x)는 무시된다.

    • TS(T1) < TS(T2)
Knou, 데이터베이스 시스템
knou database
Recently Updated
Contents

[데이터베이스 시스템] 13강 - 트랜잭션

[파이썬 프로그래밍 기초] 14강 - 실전 프로그래밍