동시성 제어 (병행수행, Concurrency)

병행제어, LDIC, 2PC, Timestamp

낙관(Validation), 웨다운웨(WDWW)

 

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

[유형] 낙관적 검증, Locking, Timestamp

 

[제어누락 오류]

1) Lost Update(동일 데이터 동시 갱신)

2) Dirty Read(중간 수행데이터 참조)

3) Inconsistency(두 트랜잭션의 연산 순서 바뀜)

4) Cascading Rollback

 

동시성 제어를 하지 않을시 발생 문제점 - LDIC

조회 중심의 업무는 타임스탬프 적용

업무구분이 명확하여 중복이 없다면 validation

 

락킹,타임스탬프,낙관적,다중버전 병행제어 ,

문제점(갱신손실(나중T덮어씀),현황파악오류(다른T참조),모순성(동시T),연쇄복귀(복수T데이타공유→취소문제)

 

 

Locking 기법

 

공유락(Shared Lock)

전용락(Exclusive Lock)

상호배제

 

[개념] 트랜잭션이 사용하는 자원에 대하여 상호배제 기능을 제공하는 기법

[종류] 공유Lock (Shared Lock) - 잠금한 트랜잭션은 잠금항목 읽기만 가능

전용Lock (Exclusive Lock) - 잠금한 트랜잭션은 읽기와 기록 가능

[문제점] 블로킹, 교착상태, 성능저하 최소화방안

공유락,전용락,락에스칼레이션,

[해결방안]

블로킹(커밋,롤백),데드락(한쪽 세션 오류),성능저하(락 타임아웃설정)

 

2PL (2 Phase Locking)

 

read_lock(), write_lock(), unlock()

확장단계,수축단계

교착상태 미발생

 

[개념] 다중 트랜잭션 환경에서 직렬성을 보장하기 위해 모든 트랜잭션들이 lock연산과 unlock연산을 확장단계와 수축단계로 구분하여 수행하는 동시성 제어 기법.

[절차] 확장단계 -> 차단단계(연산) -> 수축단계 / lock ->unlock

1)확장단계: 새로운 Lock 획득가능, 해제 불가

2)수축단계:보유 Lock해제, 새로운 Lock 획득불가

[변형]

1)스트릭트(전용락 완료 기다림),

2)리고로스(모든락기다림)

3)스태틱(읽기집합, 쓰기집합 미리선언, 모든락 획득)

 

TimeStamp Ordering

 

생성(system clock, 논리적 계수기)

직렬성 보장, 순차처리

데드락방지, 연쇄복구 초래 가능

 

[개념] 트랜잭션 순서대로 timestamp 지정하여 동시성 제어의 기준으로 사용

[구성] 1)read_TS(X): X를 성공적으로 읽은 트랜잭션 타임스탬프 중 가장 큰 값

2)write_TS(X): X를 성공적으로 기록한 트랜잭션 타임스탬프 중 가장 큰 값

[절차]

가.트랜잭션 T가 write_item(X) 연산을 수행시

1) TS(T) < read_TS(X) or TS(T) < write_TS(X)이면 T를 철회/복귀 연산 거부(reject)

2) 조건이 미발생시 T는 write_item(X) 연산 수행 write_TS(X)를 TS(T)로 설정

나. 트랜잭션 T 가 read_item(X) 연산을 수행시

1)TS(T) <=  write_TS(X)면 T를 철회하고 복귀시키고 그 연산을 거부

2)TS(T) >=  write_TS(X)면 READ수행

 

시스템시계(system clock), 논리적계수기(counter),

데드락방지기법(웨잇다이,운드웨이트)

[알고리즘]

1)Wait-Die 알고리즘

TS(Ti) ＜ TS(Tj)이면(Ti가 Tj보다 먼저 시작되었다면)

Ti는 대기(Wait)

그렇지 않으면(Ti가 Tj보다 나중에 시작되었다면)

Ti가 철회(Die). 나중에 Ti 재시작

2)Wound-Wait 알고리즘

TS(Ti) ＜ TS(Tj)이면(Ti가 Tj보다 먼저 시작되었다면)

Tj를 철회(Wound).

그렇지 않으면 Ti는 대기(Wait)

 

낙관적 검증기법

(Validation)

 

판독단계(Read Phase:R)

확인단계(Validation Phase: V)

기록단계(Execution Phase: E)

판독집합, 기록집합

Start(Ti)/Validation(Ti)/Finish(Ti)

 

[개념] 트랜잭션이 어떠한 검증도 수행하지 않고, 일단 트랜잭션을 수행하고 종료시 검증을 수행하여 DB에 반영 (배치작업)

[처리단계] 1)판독 - Buffer에서 수행. 트랜잭션의 모든 갱신은 이 사본에 대해서만 수행하고 실제 DB에 대해서는 수행하지 않음

2)확인 - 일괄로 위반여부 확인 3)기록 - 성공시 디스크 반영

 

확인 작업을 위해 트랜잭션의 판독 집합(read set)과 기록 집합(write set)을 유지함

판독집합(read set) : Ti가 판독한 데이터 아이템의 집합

기록집합(write set) : Ti가 기록한 데이터 아이템의 집합

 

 

다중버전 동시성제어

(MVCC; Multiversion concurrency control)

 

[개념] 트랜잭션이 데이터 아이템에 접근 시 데이터 아이템의 다중버전 상태 중 직렬 가능성이 보장되는 버전을 선택하여 처리하는 기법

[특징] UNDO영역(Rollback Segment), CR Copy(일관된 읽기)

[프로세스] 데이터 변경발생 → Undo영역에 저장 → CR Copy생성 → Trx보다 버전이 최신인 값 발견 → Undo영역의 CR Copy Read

[세부절차]

1)데이터 변경시 변경사항을 Undo영역 저장

2)쿼리시작시점 이후에 변경된 값을 발견하면, Undo 영역에 저장된 정보를 이용해 쿼리시작시점의 일관성 있는 버전을 생성하고 READ

3)Undo 블록 I/O, CR 블록 캐싱 등의 부가적인 오버헤드가 발생

 

[세부]Ti가 Read(Q)실행-반환되는 값은 버전 Qk의 내용

Ti가 Write(Q)실행

TS(Ti) < R-Timestamp(Qk)면 Ti는 복구

TS(Ti) < W-Timestamp(Qk)이면 Qk의 내용은 Overwritten

그 외의 경우에는 Q의 새로운 버전 생성

W-Timestamp(Qk) :버전 Qk를 생성한 트랜잭션의 타임스탬프

R-Timestamp(Qk) : 버전 Qk를 성공적으로 판독한 트랜잭션중 가장 큰 값

[고려사항]1)Snapshot Too Old 문제 → Undo크기 조절, 불필요한 Commit 줄임. 너무 긴 트랜잭션 조정 수행