데이터베이스

14. 병행 제어

트랜잭션

트랜잭션 = 일련의 연산들의 집합

• 하나의 논리적 기능을 수행하기 위한 작업의 단위
• 데이터베이스의 일관된 상태를 다른 일관된 상태로 변환
  • 이를 위해 트랜잭션의 연산은 원자성을 가져야함
    • All or Nothing방식
• 트랜잭션은 Begin_Trans ... End_Trans로 묶어서 표시

트랜잭션의 예

A계좌에서 100원을 B 계좌로 이체하는 트랜잭션

T:  Read(A)
    A=A-100
    Write(A)
    Read(B)
    B=B+100
    Wrtie(B)

• 실행 도중 장애 발생시 모순 상태 발생
• 트랜잭션 전체가 실행되거나 실행되지 말아야한다.
• DBMS는 어느 부분이 트랜잭션인지 알 수 없다
  • 사용자가 명시해야함

트랜잭션의 특성 ACID

• 원자성(Atomicity)
  • 전부 or 전무(아무것도 하지마) 실행
  • 모든 연산이 반영되거나 아니면 말거나
• 일관성(Consistency)
  • 트랜잭션 실행 후에도 일관성 유지
• 격리성(Isolation)
  • 트랜잭션 실행 중 연산 중간 결과에 다른 트랜잭션이 접근 불가
  • 여러 트랜잭션이 실행되더라도 순서에 따라 하나씩 처리해야한다.
• 영속성(Durability)
  • 트랜잭션이 성공하면 그 결과는 영구적이다.
  • 결과는 데이터베이스가 장애가 있어도 결과 값이 손실되서는 안된다.

트랜잭션의 연산

트랜잭션의 원자성을 보장해야한다

Commit(완료)

• 트랜잭션이 성공적으로 실행되었다는 것을 선언
  • 일관성이 있는 데이터베이스 상태로 변환됨
• 갱신된 데이터 값이 영속성을 갖도록 보장
  • DB에 값을 영구적으로 보관될 수 있도록 반영

Rollback(복귀)

• 트랜잭션의 실행이 실패했다는 것을 선언
  • 데이터 베이스 상태가 모순적인 상태
• 트랜잭션이 수행한 모든 연산은 원상 복귀 되어야함
  • 트랜잭션 수행 이전 상태로 되돌려

트랜잭션의 상태

트랜잭션이 성공적으로 수행되기 위해서는 시스템에 오류나 장애가 없어야한다.

트랜잭션은 5가지의 상태를 가진다

• 활동 Active
  • 트랜잭션 실행 시작
• 부분 완료 Partially Commited
  • 마지막 명령문을 실행시킨 직후의 상태
• 실패 Failed
  • 실행 중 장애나 오류가 발생해 비 정상적인 상태
  • 부분완료에서 커밋 전에 장애가 나면 실패 상태로 간다
• 철회 Aborted
  • 실행을 실패해 Rollback을 한 상태
  • 트랜잭션을 재 시작하거나 강제 종료 함
• 완료 Commited
  • 트랜잭션이 성공적으로 완료 됨
  • 변경된 내용이 DB내에 저장되어 영속성을 보장한다.

병행제어

여러 사용자가 사용하는 DBMS에서는 병행 수행을 지원한다.

• 여러 트랜잭션을 동시에 수행시켜야 하기 때문이다.
• 프로그램이 인터리브형태로 병행 수행된다.
  • RR처럼

여러 개의 트랜잭션이 실행될 때 병행수행이 적절히 제어되지 않는다면 트랜잭션들의 간섭으로 인해 문제가 생길 수 있다.

병행수행의 문제점

• 갱신 분실 Lost Update
• 모순성 Inconsistency
• 연쇄 복귀 Cascading rollback

갱신 분실

• T1의 연산 결과를 write하기 전에 T2가 x의 값을 읽었다
• 결과적으로 T1의 연산 결과 값은 분실되었고 T2만 갱신하게 되었다.

모순성

원래 x,y의 값은 100이다.

• T1과 T2는 각자의 수행 결과를 x,y=200으로 생각했을 것이다.
• 하지만 두 트랜잭션이 꼬여서 원하는 결과와 다른 결과가 나왔다.
  • 사용자가 원하는 결과도 아니고 데이터베이스가 일관성이 없는 모순상태로 남는다.

연쇄 복귀

• T1이 문제가 생겨 롤백 되어야하는 상황이 생겼다.
  • 하지만 T2는 이미 커밋이 되었다.
    • T1을 롤백하면 T2도 롤백이 되어야하지만 이미 커밋이 되어 롤백이 힘들다.

트랜잭션 스케줄

트랜잭션 스케줄

• 데이터 베이스 트랜잭션을 구성하는 연산들의 실행 순서를 의미

인터리브 형태로 여러 트랜잭션들이 병행되면 트랜잭션의 포함된 연산들의 순서를 정해주는 것은 매우 중요하다.

• 스케줄링이 중요하다.

직렬 스케줄 Serial Schedule

• 트랜잭션별로 연속적으로 실행하는 스케줄
  • 하나에 한 트랜잭션만 수행
• 직렬 스케줄로 수행이되면 데이터베이스에 대한 결과는 항상 정확
  • 하지만 CPU의 낭비가 있음
    • I/O시 CPU가 놀면 낭비다!!

직렬 가능 스케줄 Serializable schedule

비 직렬 스케줄

• 트랜잭션들이 병행적으로 수행하는 스케줄
• 인터리빙 방식으로 처리된다.
• CPU 활용도를 높일 수 있다
• 결과 값에 문제가 있을 수 있다.
• 두개의 트랜잭션이 같은 데이터에만 접근하지 않는다면 간섭이 없다

직렬 가능 스케줄

• 비 직렬로 수행되지만 직렬 스케줄로 수행되는 것과 같은 결과를 만드는 스케줄
• 하지만 이를 판단하기엔 어렵다

병행 제어(concurrency control) 기법

트랜잭션을 실행시킨 뒤 결과를 검사한다면 복잡하다.
그래서 대부분 시스템들은 직렬가능성이 보장되도록 병행성을 제어한다.

로킹과 타임스탬프가 있다

• 로킹(locking)
  • 여러 트랜잭션들이 동일한 항목에 병행접근을 하지 못하게 막음
• 타임스탬프(timestamp)
  • 타임스탬프 순서에 따라 트랜잭션이 실행되게 함

로킹 기법

Lock

• 기본적으로 lock과 unlock을 사용해 트랜잭션의 데이터를 제어한다.
• 로킹 규약(locking protocol)을 지킨다면 두개의 트랜잭션이 같은 데이터를 동시에 접근하는 경우는 없다

로킹 프로토콜

• 트랜잭션 T가 read나 write를 하려면 먼저 lock을 실행
• T는 실행을 종료하기 전에 unlock을 실행
• 다른 트랜잭션에 의해 이미 데이터가 lock 되어 있다면 lock을 실행 못함
• 자기 자신만이 unlock을 할 수 있음

이 프로토콜은 제한적일 수 있다

• 트랜잭션이 read인 경우 데이터 접근을 병행해도 괜찮다
  • 그래서 lock 연산이 나뉘어진다.

공용, 전용 로크

Lock-S: 공용 로크 (shared-lock)

• 트랜잭션은 read할 수 있지만 write할 수 없다
• 다른 트랜잭션은 공용 lock을 동시에 걸 수 있다.

Lock-X: 전용 로크(exclusive-lock)

• 트랜잭션은 read write 모두 할 수 있다.
• 다른 트랜잭션은 어떤 lock도 걸 수 없다.

양립성

한 데이터에 대해 공용 로크가 존재

• 다른 트랜잭션이 공용로크를 걸 수 있다
• 전용로크는 걸 수 없다. 끝날때까지 기다린다

한 데이터에 대해 전용 로크가 존재

• 로크를 걸 수 없다 기다려야한다.

하지만 이 프로토콜을 따라도 모순성이 발생할 수 있다.

T1 -> T2 를 했을때와 T1사이에 T2를 실행시키고 T1을 끝냈을 때의 결과는 다르다.

왜??

• T1이 너무 일찍 unlock을 했기 때문이다.

그래서 2단계 로킹 프로토콜이 만들어졌다.

2단계 로킹 규약 2PL: two phase locking protocol

모든 트랜잭션들은 2단계로 구분하여 수행되어야 한다.

• 확장 단계
  • lock만 할 수 있고 unlock은 못하는 단계
• 축소 단계
  • unlock만 할 수 있고 lock은 못하는 단계

스케줄 내의 모든 트랜잭션이 2단계 로킹 규약을 준수한다면 그 스케줄은 직렬 가능하다.

• 정확한 결과를 생성한다.

앞에서의 스케줄에 2단계 규칙을 적용했다.

• T1에서 확장단계에서 다 락을 해버린다
  • x에 대한 연산을 하고 언락을 축소단계가 해버린다
• T2는 x만 사용가능하니 x 수행
• T1이 Y연산 수행 후 언락
• T2가 연산 수행

결과가 정확하다

교착 상태 deadlock

2단계 로킹 규약은 강력하지만 교착 상태가 발생할 수 있다.

교착상태

• 아무도 Unlock을 할 수 없고 무한정 기다리는 상태

이를 회피하기 위해서는 회피,예방,탐지 방법이 있다.

해결 방법

회피

• 자원을 할당할때마다 deadlock이 발생하지 않도록 실시간 알고리즘을 사용
  • 현실성 없다.

예방

• 트랜잭션을 실행시키기 전에 필요한 lock을 한번에 모두 요청
  • 전부 부여받지 못하면 실행시키지 않음
• 현실성 없다.

탐지

• lock상태를 조사해 일단 교착상태가 탐지되면 한 트랜잭션을 취소시키고 다시 스케줄 실행
  • 취소시키는 트랜잭션??
    • 작업이 가장 적게 수행된 트랜잭션을 취소가 가장 효율적

회피 방법

• 타임스탬프를 이용해 교착 상태를 회피한다.
• 타임스탬프는 트랜잭션이 기다릴지, rollback해야할지를 결정하는데 사용된다.
• 두가지 기법이 있다.

wait-die기법

• A가 B가 lock한 데이터를 요구할 때 A의 타임스탬프가 B의 타임스탬프보다 작을 경우(A가 더 오래 되었을 때) A는 wait
  • 반대의 상황일 때는 A는 포기(die)했다가 나중에 다시 시작
• 즉, 이 기법은 다른 트랜잭션이 데이터를 점유할때 기다리거나 포기하는 방식

wound-wait기법

• 트랜잭션 A가 이미 트랙잭션 B가 lock한 데이터를 요구할 때 만약 A의 타임스탬프가 B의 타임스탬프보다 작을 경우 A는 데이터를 선점(wound)한다.
  • B가 못쓰도록, A가 권한을 뺏는다.
  • 그렇지 않으면 wait 한다.

예방 방법

트랜잭션을 실행하기 전 필요한 lock을 한꺼번에 모두 요청해 전부 부여받지 못하면 실행시키지 않는다

• 데이터 요구에 대한 사전 지식이 있어야하니 현실성이 없다
• 데이터가 한번에 lock되기 때문에 데이터 활용도가 낮아진다.

탐지 방법

lock 상태를 조사해 교착상태가 발견되면 트랜잭션 하나를 취소시켜 다시 스케줄을 실행한다.

• 대기 그래프(wait graph)를 이용해 교착을 탐지한다.
• B가 lock한 데이터 항목을 A가 lock하기 위해 기다린다면
  • A->B로 표현
  • 이때 그래프에 사이클이 생긴다면 교착 상태가 발생했다고 판단
• 취소시킬 트랜잭션은 작업이 가장 적게 수행된 트랜잭션을 취소하는 것이 효율적이다.

아직 완전히 교착을 해결할 방법은 없다.

로킹 단위

• 로킹의 대상이 되는 데이터 객체의 크기
  • 병행 제어의 데이터 단위가 된다.
• 로킹 단위가 클수록 병행성 수준이 낮아짐
  • 병행 제어 기법은 간단해짐
• 로킹 단위가 작을수록 병행성 수준이 높아짐
  • 병행 제어는 복잡해짐
• 극단적으로 로킹 단위가 DB 전체가 된다면 병행성은 전혀 없게 된다.
  • 왜?? 디비를 lock하게 되니깐...

로킹 단위가 크면 많은 데이터를 한번에 lock하게 되니 병행성 수준이 낮아진다.
그치만 이를 관리 하기 쉬우니 간단해진다.

로킹 단위가 작으면 세세하게 데이터를 lock하니 병행성 수준이 높아지지만, 이를 완벽히 하기엔 복잡해진다.

적절한 로킹단위의 결정은 시스템 성능향상을 위해 중요하다.

데이터 항목으로만 lock을 한다면 모든 데이터에 대해 lock을 해야하니 많은 로킹 연산이 필요하다.

그렇기 때문에 여러 종류의 로킹 단위를 지원할 수 있는 다중 단위 로킹기법이 필요하다.

• 여러종류??
  • 레코드, 파일 ,Db...