Timestamp Ordering

Timestamp Ordering

타임스탬프(Timestamp) Ordering(순서) 기법 TS라고 함, 토마스(Thomas)쓰기규칙에서는 불필요한 write연산 무시하여 TS(Ti) < write-TS(x)인 경우 write연산을 수행하지 않고 Ti 수행가능, 장점 : 직렬가능, 교착상태방지, 단점 : 연쇄복귀, 기아문제

토마스 쓰기 규칙

토픽 이름 (상)	Timestamp Ordering
분류	DB > 동시성제어(병행 제어) > Timestamp Ordering
키워드(암기)	타임스탬프 지정, 생성방법(논리적계수, 시스템시계), 종류(read_TS, write_TS)
암기법(해당경우)

기출문제

번호	문제	회차
1	13. 타임스탬프 순서(Timestamp Ordering) 기법에 대하여 설명하시오.	모의_2017.01
2	8. 동시성 제어 기법에 대하여 다음을 설명하시오. 가. 타임스탬프 순서(Timestamp Ordering) 기법에 대하여 설명하시오. 나. Wait-Die, Wound-Wait 알고리즘에 대하여 설명하시오..	합숙_2016.07
3	데이터베이스 동시성 제어기법인 2PL(2 Phase Locking), Timestamp Ordering, 낙관적 검증기법을 비교 설명하시오.	합숙_2014.01

 

I. 시스템 시계와 논리적 계수기를 이용한 순서지정 방식, Timestamp Ordering의 개요

가. Timestamp Ordering의 정의

- 트랜잭션을 식별하기 위해 DBMS가 부여하는 유일한 식별자인 타임 스탬프를 지정하여 트랜잭션 간의 순서를 미리선택하는 순서대로 직렬화하여 실행한 결과가 같음을 보장하는 동시성 제어 기법

- DBMS 가 부여하는 트랜젝션의 식별자인 타임스탬프를 이용하여 트랜젝션 실행의 순서를 미리 결정

나. Timestamp Ordering 특징

구분	설명
직렬성 보장	- 상충되는 연산들이 타임 스탬프 순서로 처리됨으로 직렬성 (Serializability)이 보장
교착상태 방지	- 트랜잭션이 결코 기다리는 경우가 없으므로 교착상태 (Deadlock) 를 방지
연쇄복귀 초래	- 문제점은 연쇄복귀 (Cascading Rollback) 를 초래

 

II. Timestamp Ordering 개념도 및 생성 메커니즘

가. Timestamp Ordering 개념도

- DBMS 가 부여하는 트랜젝션의 식별자인 타임스탬프를 이용하여 트랜젝션 실행의 순서를 미리 결정

나. Timestamp Ordering 생성 메커니증

분류	구분	설명
생성방법	논리적 계수 (Logical Counter)	트랜잭션이 시스템에 들어올 때마다 계수를 하나씩 증가시켜 트랜잭션의 타임스탬프 값으로 부여
	시스템 시계 (System Clock)	트랜잭션이 시스템에 들어오면 시스템 시계의 값을 그 트랜잭션의 타임스탬프 값으로 부여
타임스탬프 종류	read_TS(x)	데이터 아이템 x 의 판독 타임스탬프로서 read(x)를 성공적으로 수행한 트랜잭션의 타임스탬프 중에서 제일 큰 타임스탬프
	write_TS(x)	데이터 아이템 x 의 기록 타임스탬프로서 write(x)를 성공적으로 수행한 트랜잭션의 타임스탬프 중에서 제일 큰 타임스탬프

- 타임스탬프를 동시성 제어의 기준으로 사용하여 상충되는 연산들을 타임스탬프 순서대로 처리함으로써 직렬성 보장

다. Timestamp Ordering의 순서 규약

구분	규약	설명
트랜젝션 Ti가 읽기 시도 시 - read(x) 수행	TS(Ti) < write_TS(x)	- read(x)를 거부하고 Ti를 취소시켜 복귀시킴 - TS(Ti)보다 타임스탬프가 큰 어떤 트랜젝션이 Ti가 접근하기 전에 이미 x의 값을 먼저 생성
	TS(Ti) >= write_TS(x)	- read(x)를 허용하고 read_TS(x)는 TS(Ti)와 현재의 read_TS(x) 중에서 큰 것으로 설정
트랜젝션 Ti가 쓰기 시도 시 - write(x) 수행	TS(Ti) < read_TS(x)	- write(x)를 거부하고 Ti를 취소시켜 복귀시킴 - TS(Ti)보다 타임스탬프가 큰 트랜젝션이 x의 값을 먼저 판독
	TS(Ti) < write_TS(x)	- write(x)를 거부하고 Ti를 취소시켜 복귀시킴 - TS(Ti)보다 타임스탬프가 큰 트랜젝션이 x의 값을 이미 기록
	TS(Ti) >= read_TS(Ti) 또는 TS(Ti) >= write_TS(Ti)	- write(x)를 허용하고 write_TS(x)의 값은 TS(Ti)로 고정

- 타임스탬프를 이용하여 Dead Lock 을 방지하기 위해 Wait-Die/Wound-Wait 알고리즘이 사용됨

 

III. 타임스탬프 이용한 Dead Lock 방지 알고리즘

Wait-Die	Wound-Wait

- 두 기법 모두 불필요한 복귀가 자주 발생한다는 문제점이 있으며, 토마스의 기록 규칙을 통해 개선 가능