동시성제어개요

1. 데이터 베이스의 무결성 확보를 위한 동시성 제어(Concurrency)의 개요

  가. 동시성 제어의 정의

   1) 다중 사용자 환경을 지원하는 데이터 베이스 시스템에서 여러 트랜잭션들이 성공적으로 동시에 실행될 수 있도록 지원하는 기능

   2) 다중 사용자 환경을 지원하는 DB system의 경우 필수적으로 지원해야 하는 기능으로 병행제어라고도 함

   3) 트랜잭션의 직렬화 수행 보장

  나. 동시성 제어의 목적

   1) 트랜잭션의 직렬성 보장

   2) 공유도 최대, 응답 시간 최소, 시스템 활동의 최대 보장

   3) 데이터의 무결성 및 일관성 보장

 

  다. 동시성 제어 기법의 종류

   1) 로킹 기법

   2) 타임스탬프 순서에 기반을 둔 동시성 제어 기법

   3) 다중버전 동시성 제어 기법

   4) 검증(낙관적) 동시성 제어 기법

 

 

2. 동시성 제어를 하지 않은 경우 발생하는 문제점

  가. 문제점 목록

구분	내용
갱신 손실 (Lost Update)	- 트랜잭션들이 동일 데이터를 동시에 갱신 할 경우 발생 - 이전 트랜잭션이 데이터를 갱신한 후 트랜잭션을 종료하기전에 나중 트랜잭션이 갱신 값을 덮어쓰는 경우 발생
현황파악오류 (Dirty Read)	-트랜잭션의 중간 수행결과를 다른 트랜잭션이 참조함으로써 발생하는 오류
모순성 (Inconsistency)	-두 트랙잭션이 동시에 실행할 때 DB가 일관성이 없는 상태로 남는 문제
연쇄복귀 (Cascading Rollback)	-복수의 트랜잭션이 데이터 공유시 특정 트랜잭션이 처리를 취소할 경우 다른 트랜잭션이 처리한 부분에 대해 취소 불가능

  나. 문제의 원인

  1) 충돌(conflict)

     - 상이한 트랜잭션에 속하고 있으면서 동일한 데이타 아이템을 처리 대상으로 하는 두 연산

     - 최소한 하나의 기록(write) 연산

     - 공용하는 충돌된 데이타를 통해 트랜잭션 사이에 간섭이 일어나기 때문

       . 충돌이 일어나는 경우 : readi(x)와 writej(x), writei(x)와 readj(x), writei(x)와 writej(x)

       . 충돌이 일어나지 않는 경우 : read(x)와 write(y), write(x)와 read(y), write(x)와 write(y)

 

  다. 갱신내용 손실(Lost update) – Dirty Wirte

   - 트랜잭션들이 동일 데이터를 동시에 갱신할 경우 발생하는 문제

   - 이전 트랜잭션이 데이터를 갱신한 후 트랜잭션을 종료하기 전에 나중 트랜잭션이 갱신 값을 덮어 쓰는 경우에 발생

      예제 1)

- T1과 T2가 순서없이 동시에 갱신을 시도하여 늦게 일어난 T2의 Write 연산으로 인해 T1의 갱신이 무료화 되었음

예제 2)

    - 트랜잭션들이 동일 데이터를 동시에 갱신할 경우 발생하는 문제

    - 이전 트랜잭션이 데이터를 갱신한 후 트랜잭션을 종료하기 전에 나중 트랜잭션이 갱신 값을 덮어쓰는 경우에 오류가 발생

 (예) 잔고가 1000원인 계좌 A에서 고객 갑이 500원을 인출하고 동시에 갑의 배우자가 400원을 인출할 때

   - 트랜잭션 1의 실행결과는 DB에 기록되지 않고 실종됨 (A는 100이 되어야 함)

 

  라. 현황 파악 오류(Dirty Read)

   - 트랜잭션 의 중간 수행 결과를 다른 트랜잭션이 참조함으로서 발생하는 오류

    예) 1000, 2000, 1000원의 잔고가 있는 A, B, C 계좌에 2% 이자를 가산하여 합을 구함

  마. 모순성(inconsistency)

   - 두 트랜잭션이 동시에 실행 할 때 DB가 일관성이 없는 모순된 상태로 남는 문제

   - 복수의 사용자가 동시에 DB를 Access 하여 갱신한 결과 DB내의 Data들이 상호 일치하지 않거나 출력된 정보에 모순이 나타나는 경우

예제1)

-T1의 예상 결과값은 x=600, y=600이며, T2의 예상값은 x=1000, y=1000 이었으나, 실제 최종 결과 값은 x=1300, y=1100으로 모순되는 결과를 가져옴

 

 

  바. 연쇄 복귀(Cascading Rollback) or 회복 불능(Unrecoverability)

    - 복수의 트랜잭션이 Data 공유시 특정 Transaction이 처리의 취소를 하고자 할 때, 다른 Transaction이 처리한 부분에 대해서는 취소 불가한 상태 발생

    

    예제 1)

      -T1의 Read(Y) 이후에 Fail시 Roll back 해야 하는 경우 발생 가정시

        T1의 개시 최초 상태인 X=500, y=500인 상태로 복귀해야 하지만 T2가 이미 트랜잭션을 완료하고 시스템을 떠난 상태이기 때문에 초기 상태로 복귀 불가함

   

   예제 2)

- 트랜잭션들이 동시에 같은 레코드에 접근하여 갱신하여 도중에 한 트랜잭션은 성공 완료된 상태에서 다른 트랜잭션이 갱신을 취소하고 원래 상태로 복귀하는 과정에서 다른 트랜잭션이 처리한 부분에 대해서는 취소 불가

- 트랜잭션들이 동시에 같은 레코드에 접근하여 갱신하는 도중에
ㆍ 한 트랜잭션은 성공완료된 상태

ㆍ 다른 트랜잭션이 갱신을 취소하고 원래 상태로 복귀 하는 과정

- 다른 트랜잭션이 처리한 부분에 대해서는 취소 불가

          (예) 트랜잭션1이 A를 100 증가시키고 트랜잭션 2는 2를 곱하는 연산 

 

2.트랜잭션 직렬

  가. 직렬가능 스케쥴

   - 비직렬 스케쥴의 결과가 직렬 스케쥴의 결과와 동일한 비직렬 스케쥴 (B)

 

  나. 직렬 가능성 검사의 어려움

   - 트랜잭션을 임의로 수행시킨 뒤 직렬 가능성 검사가 어려움, 직렬 가능이 안 될 때 스케줄 취소가 어려움

   - 시스템에 트랜잭션들이 계속 들어올 경우, 어떤 스케줄이 언제 시작해서 언제 끝나는지 결정 어려움

    ⇒ 문제 복잡, 직렬 가능 검사 불가능

 

  다. 직렬 가능성 검사 하지 않고 직렬 가능성 보장 기법

   - 로킹(locking), 타임스탬프(timestamp)

 

3. 동시성 제어 기법인 로킹 기법

  가. Locking 기법의 정의

   - 트랜잭션이 사용하는 자원에 대하여 상호 배제(Mutual Exclusive) 기능을 제공하는 기법

   - 상호배제는 특정 트랜잭션이 데이터 항목에 대하여 잠금(Lock)을 설정한 트랜잭션이 해제(unlock) 할 때까지 데이터를 독점적으로 사용할 수 있는 것

  나. Locking 연산의 종류

종류	주요개념
공유Lock (Shared Lock)	공유 잠금한 트랜잭션이 데이터 항목에 대하여 읽기(read)만 가능 다른 트랜잭션도 읽기(Read) 만을 실행 할 수 있는 형태
전용 Lock (Exclusive Lock)	전용 잠금한 트랜잭션은 데이터 항목에 대해서 읽기(read)와 기록(write)가 모두 가능 다른 트랜잭션은 읽기(read)와 기록(write) 모두 할 수 없음

  다. 로킹 단위

Locking단위가 클수록☞병행성 수준 떨어지고, 병행제어기법 간단해짐

Locking단위가 작을수록☞병행성 수준 높아지고, 관리 복잡해짐

 

  라. 2단계 로킹(2PL : 2 Phase Locking) – lock하는 시간이 있고, unlock 하는 시간이 있음

   - 모든 트랜잭션들이 Lock과 Unlock 연산을 확장단계와 수축 단계로 구분하여 수행함(read_lock(), write_lock(), unlock() 연산으로 구성)

   - 확장단계 : 트랜잭션은 lock만 수행할 수 있고, unlock은 수행할 수 없는 단계

   - 수축단계 : 트랜잭션은 unlock만 수행할 수 있고, lock은 수행할 수 없는 단계

   - 직렬 가능성을 보장할 수 있는 규약으로 가장 많이 사용됨

   - 문제점 : 교착 상태 발생 가능성 - 교착상태 예방과 교착 상태 탐지로 해결

 

   -하나의 트랜잭션 내에서 확장단계를 거치고, 수축단계를 거치면서 lock à unlock 수행

 

마. 기타 locking 기법

종류	Strict 2PLP	Rigorous 2PLP	Static 2PL
내용	1) 2단계 Locking 2)  모든 독점 lock(Lock-X)는 그 Transaction이 완료될 때까지 unlock 하지 않음. 그대로 유지	3)  Rigorous 2단계 Locking 4)  모든 lock는 그 Transaction이 완료될 때까지 unlock 하지 않음.	5)  Transaction 수행 전부터 그 Transaction의 읽기 집합과 쓰기집합을 미리 선언하여 그 Transaction이 접근하려는 모든 항목들에 Lock을 획득
특징	6)  연쇄복귀 문제 발생하지 않음	7) Strict 2PLP보다 더 제한적	8)  Dead lock 발생 하지 않음. 9)  현실성 없음

 

 

4. Time Stamp 기법의 개요

  가. Time Stamp의 정의 (Dead Lock 발생 안함)

트랜잭션을 식별하기 위해서 DBMS가 부여하는 유일한 식별자인 타임 스탬프를 지정하여 트랜잭션 간의 순서를 미리 선택함

시스템에서 생성하는 고유 번호인 시간 스탬프를 트랜잭션에 부여하는 것으로 트랜잭션 간의 순서를 미리 선택하는 것

트랜잭션의 순서대로 시간 스탬프를 지정하여 동시성 제어의 기준으로 사용하는 개념

 

  나. Time Stamp의 종류

구분	내용
System 시계사용법	System Clock 트랜잭션이 시스템에 들어 올 때의 시스템 시계 적용 개념
논리적인 계수기 사용법	트랜잭션의 시간 스탬프는 그 트랜잭션이 시스템에 들어올 때의 시스템 계수기의 값과 같은 개념

 

  다. 타임스탬프 순서 알고리즘

   1)  타임스탬프 순서 기법에서는 스케줄이 트랜잭션들의 타임스탬프의 순서에 해당하는 특정 직렬 순서와 동치이다.

   2) 각 데이터베이스 항목 X에 대해 두 개의 타임스탬프 값들을 연관시킨다.

-  read_TS(X): 항목 X의 읽기 타임스탬프(read timestamp)로서 항목 X를 성공적으로 읽은 트랜잭션들의 타임스탬프 중 가장 큰 값이다. 즉, read_TS(X) = TS(T)이고 여기서 T는 X를 성공적으로 읽은 가장 최근의(youngest) 트랜잭션이다.

-  write_TS(X): 항목 X의 쓰기 타임스탬프(write timestamp)로서 항목 X를 성공적으로 기록한 트랜잭션들의 타임스탬프 중 가장 큰 값이다. 즉, write_TS(X) = TS(T)이고 여기서 T는 X를 성공적으로 기록한 가장 최근의 트랜잭션이다.

 

  라. 기본적 타임스탬프 순서(Basic Timestamp Ordering)

   1)트랜잭션 T가 write_item(X) 연산을 수행하려고 할 경우:

- read_TS(X) > TS(T) 또는 write_TS(X) > TS(T)이면 T를 철회하고 복귀시키고 그 연산을 거부(reject)한다.

- a의 조건이 발생하지 않으면 T는 write_item(X) 연산을 수행하고 write_TS(X)를 TS(T)로 설정한다.

  2) 트랜잭션 T 가 read_item(X) 연산을 수행하려고 할 경우:

- write_TS(X) > TS(T)이면 T를 철회하고 복귀시키고 그 연산을 거부한다.

- write_TS(X) ≤ TS(T)이면 T의 read_item(X) 연산을 수행하고 read_TS(X)를 TS(T)와 현재의 read_TS(X) 중 큰 값으로 설정한다.

 

5. 낙관적(Validation)  검증기법

  가. Validation 검증(낙관적 병행 제어 : Optimistic Concurrency Control)

Locking 기법, 타임스탬프 기법은 모두 데이터베이스 연산을 실행하기 이전에 어느 정도의 검사가 수행

트랜잭션이 어떠한 검증도 수행하지 않고, 일단 트랜잭션을 수행하고, 트랜잭션 종료시 검증을 수행하여 데이터베이스에 반영

모든 갱신은 일단 이 트랜잭션을 위해 유지되는 작업 구역시 사본에만 저장

단점 : 장기 트랜잭션 철회시 자원낭비 가능성, 동시 사용 빈도가 낮은 시스템에서 사용

    

 

6. 동시성 보장 기법 비교

기법	장점	단점
Locking(2PL)	-데이터 오류 가능성 사전 예방 -간단한 알고리즘	-Lock 대기시간 발생 -Deadlock 발생
Timestamp	-Deadlock 발생 없음 -트랜잭션 대기 시간 없음	-Rollback 발생 확률이 높음 -Cascading Rollback 가능성
낙관적 검증	-동시 처리 능력 증가 -트랜잭션 대기 시간 없음	-장기 트랜잭션 철회시 자원 낭비

 

7. 다중버전 병행제어 기법

  가. 다중버전 병행제어 기법의 정의

- 트랜잭션이 한 데이터 아이템을 접근하려 할 때, 그 트랜잭션의 타임스탬프와 접근하려는 데이터 아이템의 여러 버전의 타임스탬프를 비교하여, 현재 실행하고 있는 스케줄의 직렬가능성이 보장되는 적절한 버전을 선택하여 접근하도록 하는 기법

- 하나의 데이터 아이템에 대해 여러 버전의 값 유지

  나. 다중버전 병행 제어 기법의 특징

- 판독 요청을 거절하지도, 대기하지도 않음

- 기록보다 판독 연산이 주류를 이루는 데이터 베이스 시스템에 큰 이점

- 데이터 아이템을 판독할 때마다 중복되는 디스크 접근

- 트랜잭션간의 충돌문제는 대기가 아니라 복귀처리 함으로 연쇄 복귀초래 발생 가능성

 

  다. 다중 버전 병행 기법 제어 방법

1) 트랜잭션 T1은 A구좌 값을 100에서 50으로 바꿀 때 롤백 세그먼트에는 A구좌 튜플의 잔액 어트리뷰트 값을 100에서 50으로 바꾸었다고 기록

2) 이후 T2 트랜잭션에서 시점 2에서의 A구좌 튜플의 버전을 필요로 할 때는, 현재의 A구좌 잔액 100과 롤백 세그먼트에 기록된 50으로 바뀐 정보를 합해 잔액 100을 갖는 A구좌 튜플의 버전을 만들고 T2에서는 그 버전을 이용하게 된다