스케줄 (컴퓨터 과학)

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 표기법
3. 스케줄의 유형
4. 직렬 가능성 클래스 관계
참조

1. 개요

스케줄(컴퓨터 과학)은 데이터베이스 시스템에서 트랜잭션의 실행 순서를 의미한다. 스케줄은 표기법, 유형, 직렬 가능성 클래스 관계에 따라 분류된다. 표기법에는 그리드 표기법, 연산 표기법, 비순환 유향 그래프(DAG)가 있으며, R(X), W(X), Com.과 같은 연산을 사용한다. 스케줄 유형에는 직렬 스케줄, 직렬 가능 스케줄, 충돌 직렬 가능 스케줄, 뷰 직렬 가능 스케줄, 복구 가능 스케줄, 연쇄 복귀 방지 스케줄, 엄격한 스케줄 등이 있다. 직렬 가능성 클래스 관계는 직렬, 충돌 직렬 가능, 뷰 직렬 가능, 복구 가능, 엄격한 스케줄 등으로 계층적으로 나타낼 수 있다.

더 읽어볼만한 페이지

분산 컴퓨팅 문제 - 교착 상태
교착 상태는 둘 이상의 프로세스가 자원을 점유하고 서로의 자원을 요청하여 더 이상 진행할 수 없는 상태를 의미하며, 상호 배제, 점유 대기, 비선점, 순환 대기 네 가지 조건이 모두 충족되어야 발생하고, 운영 체제는 이를 예방, 회피, 무시, 발견하는 방법으로 관리한다.
분산 컴퓨팅 문제 - 비잔티움 장애 허용
비잔틴 장애 허용(BFT)은 분산 컴퓨팅 시스템에서 일부 구성 요소가 오류나 악의적인 행위를 하더라도 시스템 전체가 정상적으로 작동하도록 보장하는 속성으로, 비잔틴 장애에 대한 대응책으로 합의 알고리즘을 통해 신뢰성을 확보하며, 블록체인, 항공, 군사, 암호화폐 등 다양한 분야에서 활용된다.
동시성 제어 - 세마포어
세마포어는 데이크스트라가 고안한 정수 변수로, P/V 연산을 통해 자원 접근을 제어하고 동기화 문제를 해결하며, 계수 세마포어와 이진 세마포어로 나뉘어 멀티스레드 환경에서 자원 관리 및 스레드 동기화에 기여한다.
동시성 제어 - 모니터 (동기화)
모니터는 공유 자원 접근을 제어하여 프로세스 간 동기화를 구현하는 프로그래밍 구조로, 뮤텍스 락, 조건 변수 등으로 구성되어 경쟁 상태를 방지하며 여러 프로그래밍 언어에서 지원된다.
트랜잭션 처리 - 2단계 커밋 프로토콜
2단계 커밋 프로토콜은 분산 컴퓨팅 환경에서 트랜잭션의 원자성을 보장하는 분산 알고리즘으로, 조정자와 참가자로 구성되어 모든 참가자가 트랜잭션을 완료하거나 아무도 완료하지 못하도록 하며, 커밋 요청 및 커밋 단계를 거쳐 모든 참가자의 동의를 얻어야 커밋된다.
트랜잭션 처리 - 온라인 트랜잭션 처리
온라인 트랜잭션 처리(OLTP)는 실시간 데이터베이스 트랜잭션 처리 방식으로, 가용성, 속도, 동시성, 내구성을 목표로 은행, 항공사, 전자 상거래 등에서 활용된다.

스케줄 (컴퓨터 과학)
일반 정보
제목	스케줄
분야	컴퓨터 과학
관련 주제	동시성 제어, 트랜잭션 관리
유형	직렬 스케줄, 직렬화 가능 스케줄, 비직렬 스케줄
상세 정보
정의	데이터베이스 트랜잭션의 실행 순서
목표	데이터 일관성 유지 동시성 극대화
관련 개념	ACID 속성 직렬성 잠금 프로토콜
스케줄 유형	직렬 스케줄: 트랜잭션이 순차적으로 실행 직렬화 가능 스케줄: 직렬 스케줄과 동일한 결과를 보장 비직렬 스케줄: 트랜잭션이 동시에 실행
스케줄 속성
직렬성	스케줄이 직렬 스케줄과 동일한 결과를 나타내는 정도
회복 가능성	스케줄에서 커밋된 트랜잭션이 롤백되지 않도록 보장하는 정도
엄격함	스케줄에서 커밋되지 않은 데이터를 읽거나 덮어쓰는 것을 방지하는 정도
스케줄 충돌
충돌	동일한 데이터 항목에 대해 서로 다른 트랜잭션이 충돌하는 경우
충돌 유형	읽기-쓰기 충돌 (read-write conflict) 쓰기-쓰기 충돌 (write-write conflict) 쓰기-읽기 충돌 (write-read conflict)

2. 표기법

그리드 표기법에서 열은 스케줄에 포함된 트랜잭션을 나타내고, 행은 시간 순서에 따른 연산을 나타낸다. 연산은 다음과 같다.

R(X): 트랜잭션이 객체 X를 읽는 연산이다.
W(X): 트랜잭션이 객체 X에 쓰는 연산이다.
Com.: 트랜잭션 커밋 연산이다.

Ri(X)는 i번 트랜잭션이 객체 X를 읽는 연산을 나타낸다. Wi(X)는 i번 트랜잭션이 객체 X에 쓰는 연산을 나타낸다.

연산 간의 순서를 방향성 간선으로 표현하는 비순환 유향 그래프(DAG)로 스케줄을 나타낼 수 있다. 각 "정렬된 쌍"의 연산 사이에는 호(즉, 방향성 간선)가 존재한다.

2. 1. 그리드 표기법

그리드 표기법에서 열은 스케줄에 포함된 트랜잭션을 나타내고, 행은 시간 순서에 따른 연산을 나타낸다. 연산은 다음과 같다.

R(X): 트랜잭션이 객체 X를 읽는 연산이다.
W(X): 트랜잭션이 객체 X에 쓰는 연산이다.
Com.: 트랜잭션 커밋 연산이다.

스케줄은 각 "정렬된 쌍"의 연산 사이에 호( 방향성 간선)가 있는 유향 비순환 그래프로 표현될 수 있다.

2. 2. 연산 표기법

Ri(X)는 i번 트랜잭션이 객체 X를 읽는 연산을 나타낸다. Wi(X)는 i번 트랜잭션이 객체 X에 쓰는 연산을 나타낸다.

2. 3. 비순환 유향 그래프 (DAG)

연산 간의 순서를 방향성 간선으로 표현하는 유향 비순환 그래프(DAG)로 스케줄을 나타낼 수 있다. 각 "정렬된 쌍"의 연산 사이에는 호(즉, 방향성 간선)가 존재한다.

그리드 표기법에서 열은 스케줄의 서로 다른 트랜잭션을 나타내고, 행은 연산(액션)의 시간 순서를 나타낸다.

연산(액션)은 다음과 같다:

'''R(X):''' 해당 트랜잭션이 객체 X를 "읽는" 것을 나타낸다. 즉, X에 저장된 데이터를 검색한다. 이 작업은 "쓰기" 작업 중에 데이터를 수정(예: X=X+4)할 수 있도록 수행된다. 스케줄이 그리드가 아닌 목록으로 표현될 때, 해당 액션은 Ri(X)로 표현되며, 여기서 i는 특정 트랜잭션에 해당하는 숫자이다.
'''W(X):''' 해당 트랜잭션이 객체 X에 "쓰는" 것을 나타낸다. 즉, X에 저장된 데이터를 수정한다. 스케줄이 그리드가 아닌 목록으로 표현될 때, 해당 액션은 Wi(X)로 표현되며, 여기서 i는 특정 트랜잭션에 해당하는 숫자이다.
'''Com.:''' 해당 트랜잭션이 이전 작업을 성공적으로 완료하고 데이터베이스에 모든 변경 사항을 영구적으로 적용했음을 나타내는 "커밋" 연산이다.

3. 스케줄의 유형

데이터베이스에서 사용되는 여러 스케줄 유형은 다음과 같이 정의된다.

직렬 스케줄 (Serial Schedule)

직렬 스케줄은 트랜잭션 연산들이 다른 트랜잭션의 연산들과 섞이지(interleaving) 않고 순차적으로 실행되는 스케줄이다. 각 트랜잭션 T에 대해 T에 속한 모든 연산은 연속적으로 실행되며, 한 번에 하나의 트랜잭션만 수행된다. 연산들의 동시성과 섞임(interleaving)을 제한하여 CPU 자원이 낭비될 수 있다. 실행 중인 트랜잭션이 종료될 때까지 다른 트랜잭션은 시작되지 않는다.

일정 D는 직렬 스케줄의 예시이다.

D
T1	T2	T3
R(X)
W(X)
Com.
	R(Y)
	W(Y)
	Com.
		R(Z)
		W(Z)
		Com.

직렬 가능 스케줄 (Serializable Schedule)

직렬 가능 스케줄은 실행 결과가 직렬 스케줄과 동일한 스케줄을 의미한다. 이는 데이터베이스의 데이터 일관성과 동시성을 모두 보장하는 중요한 개념이다.^[1]^[2]^[3]

일정 E에서 트랜잭션의 작업이 실행되는 순서는 D와 같지 않지만, 결국 E는 D와 동일한 결과를 제공한다.

E
T1	T2	T3
R(X)
	R(Y)
		R(Z)
W(X)
	W(Y)
		W(Z)
Com.	Com.	Com.

직렬가능성은 데이터 항목의 데이터를 일관된 상태로 유지하는 데 사용된다. 이는 동시 트랜잭션 일정의 정확성에 대한 주요 기준이며, 따라서 모든 범용 데이터베이스 시스템에서 지원된다. 직렬 가능하지 않은 일정은 오류가 발생하기 쉬우며, 이는 매우 해로울 수 있다(예: 은행 내에서 돈을 다룰 때).^[1]^[2]^[3]

응용 프로그램에서 일부 트랜잭션 간의 특정 순서를 요청하는 경우, 이는 기본 직렬 가능성 메커니즘과 독립적으로 적용된다. 이러한 메커니즘은 일반적으로 특정 순서에 무관하며, 이러한 트랜잭션의 여러 직렬 순서와 일반적으로 호환되는 예측할 수 없는 부분 순서를 생성한다.

충돌 직렬 가능성 (Conflict-serializable)

두 개의 액션이 다음 조건을 모두 만족하면 상충(conflict)한다고 한다.

# 서로 다른 트랜잭션에 속한다.

# 적어도 하나는 쓰기 연산이다.

# 동일한 객체에 접근한다(읽기 또는 쓰기).^[4]^[5]

다르게 표현하면, 두 액션은 비가환적인 경우에만 상충한다. 또한, 두 액션은 읽기-쓰기, 쓰기-읽기, 쓰기-쓰기 충돌인 경우에만 상충한다.

다음 액션 집합은 상충한다.

R1(X), W2(X), W3(X) (3개의 상충 쌍)

반면, 다음 액션 집합은 상충하지 않는다.

R1(X), R2(X), R3(X)
R1(X), W2(Y), R3(X)

상충을 줄이면 성능이 향상된다. 왜냐하면 상충은 지연과 중단의 근본적인 원인이기 때문이다.

요청된 상충 연산이 실제로 실행되면 해당 충돌이 '''구체화'''된다. 그렇지 않고 데이터베이스 자체에서 실행되지 않으면, 해당 충돌은 '''비구체화'''된다. 비구체화된 충돌은 우선순위 그래프에서 간선으로 표현되지 않는다.

스케줄 S1과 S2가 다음 두 조건을 모두 만족하는 경우, 두 스케줄은 충돌 등가(conflict equivalent)라고 한다.

# 두 스케줄 S1과 S2는 동일한 트랜잭션 집합을 포함하며, 각 트랜잭션은 동일한 순서로 동일한 작업을 수행한다.

# 두 스케줄은 동일한 충돌 쌍 집합을 갖는다(각 충돌 쌍의 작업은 동일한 순서로 정렬된다).^[6]

다르게 말하면, 두 스케줄은 비 충돌 연산 쌍(인접 여부와 상관없이)을 서로 교환하여 다른 스케줄로 변환할 수 있고, 각 트랜잭션의 작업 순서를 유지하는 경우 충돌 등가라고 한다.^[4]

스케줄은 하나 이상의 직렬 스케줄과 충돌 동등할 때 '''충돌 직렬 가능(conflict serializable)'''이라고 한다.

동등하게, 스케줄은 해당 선행 그래프가 커밋된 트랜잭션만 고려할 때 비순환적일 경우에만 충돌 직렬 가능성이 있다.

스케줄 K는 직렬 스케줄 <T1, T2>와 충돌 동등하지만, <T2, T1>과는 그렇지 않다.

K
T1	T2
R(A)
	R(A)
W(B)
Com.
	W(A)
	Com.

충돌 직렬 가능성은 선행 그래프에서 사이클 내의 모든 트랜잭션을 다시 시작하거나, 2단계 잠금, 타임스탬프 순서 또는 직렬 가능 스냅샷 격리를 구현하여 강제할 수 있다.^[8]

뷰 직렬 가능성 (View-serializable)

두 개의 스케줄 S1과 S2는 다음 조건이 충족될 때 뷰 동등하다고 한다.

# S1에서 트랜잭션

T_i

가 객체 X의 초기 값을 읽는 경우, S2의 동일한 트랜잭션

T_i

도 그렇게 한다.

# S1에서 트랜잭션

T_j

가 기록한 값(객체 X에 대해)을 트랜잭션

T_i

가 읽는 경우, S2에서도 그렇게 해야 한다.

# S1에서 트랜잭션

T_i

가 객체 X에 대한 최종 쓰기를 수행하는 경우, S2의 동일한 트랜잭션

T_i

도 그렇게 한다.

또한, 두 개의 뷰 동등한 스케줄은 동일한 순서로 동일한 작업을 수행하는 동일한 트랜잭션 집합을 포함해야 한다.

아래 예제에서 스케줄 S1과 S2는 뷰 동등하지만 S1과 S2는 스케줄 S3과 뷰 동등하지 않다.

S1		S2		S3
T1	T2	T1	T2	T1	T2
R(A)		R(A)		R(A)
W(A)		W(A)		W(A)
R(B)⁽¹⁾			R(A)		R(A)
W(B)			W(A)		W(A)
Com.		R(B)⁽¹⁾			R(B)⁽¹⁾
	R(A)	W(B)			W(B)
	W(A)	Com.		R(B)⁽²⁾
	R(B)⁽²⁾		R(B)⁽²⁾	W(B)⁽³⁾
	W(B)⁽³⁾		W(B)⁽³⁾	Com.
	Com.		Com.		Com.

S3이 S1 및 S2와 뷰 동등하기 위한 조건은 다음 이유로 해당 위첨자에서 충족되지 않았다.

# T1이 S1과 S2에서 B의 초기 값을 읽었지만 T2가 S3에서 B의 초기 값을 읽었기 때문에 뷰 동등성의 첫 번째 조건을 충족하지 못했다.

# T2가 S1과 S2에서 T1이 기록한 B의 값을 읽었지만 T1이 S3에서 T2가 기록한 값을 읽었기 때문에 뷰 동등성의 두 번째 조건을 충족하지 못했다.

# T2가 S1과 S2에서 B에 대한 최종 쓰기를 수행했지만 T1이 S3에서 B에 대한 최종 쓰기를 수행했기 때문에 뷰 동등성의 세 번째 조건을 충족하지 못했다.

두 스케줄이 뷰 동등한지 빠르게 분석하려면 각 작업의 아래 첨자가 일치하는 뷰 동등성 조건을 나타내는 목록으로 두 스케줄을 작성한다. 두 스케줄 모두에서 모든 작업의 아래 첨자가 동일하거나 없는 경우에만 해당 스케줄은 뷰 동등하다.

S1: R1(A)_{초기 읽기}, W1(A), R1(B)_{초기 읽기}, W1(B), Com1, R2(A)_{T1에 의해 쓰여짐}, W2(A)_{최종 쓰기}, R2(B)_{T1에 의해 쓰여짐}, W2(B)_{최종 쓰기}, Com2
S2: R1(A)_{초기 읽기}, W1(A), R2(A)_{T1에 의해 쓰여짐}, W2(A)_{최종 쓰기}, R1(B)_{초기 읽기}, W1(B), Com1, R2(B)_{T1에 의해 쓰여짐}, W2(B)_{최종 쓰기}, Com2
S3: R1(A)_{초기 읽기}, W1(A), R2(A)_{T1에 의해 쓰여짐}, W2(A)_{최종 쓰기}, '''R2(B)_{초기 읽기}, W2(B), R1(B)_{T2에 의해 쓰여짐}, W1(B)_{최종 쓰기},''' Com1, Com2

일정은 특정 직렬 일정과 뷰-동등한 경우 '''뷰 직렬 가능'''이라고 한다. 정의에 따라 모든 충돌 직렬 가능 일정은 뷰 직렬 가능하다.

G
T1	T2
R(A)
	R(A)
W(B)

위 예시(충돌 직렬 가능성에 대한 논의에 나오는 예시와 동일)는 뷰 직렬 가능하며 동시에 충돌 직렬 가능하다. 그러나 블라인드 쓰기를 수행하는 트랜잭션이 있는 충돌 직렬 가능하지 않은 뷰 직렬 가능 일정이 있다.

H
T1	T2	T3
R(A)
	W(A)
	Com.
W(A)
Com.
		W(A)
		Com.

위 예시는 충돌 직렬 가능하지 않지만 뷰-동등 직렬 일정 <T1,| T2,| T3>를 가지므로 뷰 직렬 가능하다.

일정의 뷰 직렬 가능성을 결정하는 것은 NP-완전 문제이므로, 뷰 직렬 가능성은 실질적인 관심이 거의 없다.

복구 가능 스케줄 (Recoverable Schedule)

복구 가능한 스케줄은 트랜잭션이 실패했을 때 데이터베이스를 일관된 상태로 복구할 수 있는 스케줄이다. 트랜잭션은 해당 트랜잭션이 변경 사항을 읽은 모든 트랜잭션이 커밋된 후에만 커밋된다. 스케줄은 트랜잭션

T_i

가 다른 트랜잭션

T_j

의 변경 사항을 읽고 의존한 다음

T_i

가 커밋되고

T_j

가 중단되면 '''복구 불가능'''하게 된다.

F		F2		J
T1	T2	T1	T2	T1	T2
R(A)		R(A)		R(A)
W(A)		W(A)		W(A)
	R(A)		R(A)		R(A)
	W(A)		W(A)		W(A)
Com.		Abort			Com.
	Com.		Abort	Abort

스케줄 F는 T2 전에 T1이 커밋되므로 T2가 읽은 값이 올바르기 때문에 복구 가능하다. 그러면 T2는 자체적으로 커밋할 수 있다. F2 스케줄에서 T1이 중단되면 T2가 읽은 A의 값이 잘못되었으므로 T2도 중단해야 한다. 두 경우 모두 데이터베이스는 일관된 상태로 유지된다.

스케줄 J는 T2가 이전에 T1이 기록한 값을 읽었음에도 불구하고 T1 전에 커밋되었기 때문에 복구 불가능하다. T2가 커밋된 후 T1이 중단되었기 때문에 T2가 읽은 값은 잘못되었다. 트랜잭션은 커밋된 후 롤백할 수 없으므로 스케줄은 복구 불가능하다.

연쇄 복귀 방지 스케줄 (Cascadeless Schedule)

'''연쇄 중단 방지 일정''' (일명 "연쇄 중단 방지 (ACA) 일정")은 더티 읽기를 허용하지 않음으로써 연쇄 중단을 방지하는 일정이다.^[9] '''연쇄 중단'''은 한 트랜잭션의 중단으로 인해 다른 트랜잭션이 객체에 대한 첫 번째 트랜잭션의 변경 사항을 읽고 의존했기 때문에 중단되는 경우 발생한다. '''더티 읽기'''는 트랜잭션이 다른 트랜잭션에서 커밋되지 않은 쓰기로부터 데이터를 읽는 경우 발생한다.^[9]

다음 예제는 복구 가능성에 대한 논의에서 사용된 것과 동일하다.

F		F2
T1	T2	T1	T2
R(A)		R(A)
W(A)		W(A)
	R(A)		R(A)
	W(A)		W(A)
Com.		Abort
	Com.		Abort

이 예에서 F2는 복구 가능하지만 연쇄 중단을 방지하지 않는다. T2가 T1이 작성한 커밋되지 않은 값을 이미 읽었으므로 T1이 중단되면 일정의 정확성을 유지하기 위해 T2도 중단해야 함을 알 수 있다.

다음은 연쇄 중단을 방지하는 복구 가능한 일정이다. 그러나 T1이 중단되므로 T1에 의한 A 업데이트는 항상 손실된다.

F3
T1	T2
	R(A)
R(A)
W(A)
	W(A)
Abort
	Commit

이 일정은 T1이 커밋되면 직렬화 가능하지 않다.

연쇄 중단 방지는 일정이 복구 가능하기 위한 충분 조건이지만 필요 조건은 아니다.

엄격한 스케줄 (Strict Schedule)

일정은 두 개의 트랜잭션 T1, T2에 대해 T1의 쓰기 연산이 T2의 ''충돌'' 연산(읽기 또는 쓰기)보다 먼저 발생하면, T1의 커밋 또는 중단 이벤트도 T2의 해당 충돌 연산보다 먼저 발생하는 경우 '''엄격'''하다고 한다. 예를 들어, 위의 일정 F3은 엄격하다.

모든 엄격한 일정은 캐스케이드가 없지만, 그 반대는 성립하지 않는다. 엄격성은 데이터베이스의 장애로부터 효율적인 복구를 가능하게 한다.

3. 1. 직렬 스케줄 (Serial Schedule)

직렬 스케줄(Serial Schedule)은 트랜잭션 연산들이 다른 트랜잭션의 연산들과 인터리빙 되지 않고 연속적으로 실행되는 스케줄이다. 각 트랜잭션 T에 대해서 T에 속한 모든 연산이 연속적으로 실행되며, 오직 한번에 하나의 트랜잭션이 수행된다. 연산들의 동시성과 인터리빙을 제한해서 CPU의 자원 낭비를 초래한다. 실행 중인 트랜잭션이 종료될 때까지 다른 트랜잭션이 시작되지 않는다.

일정 D는 직렬 일정의 예시이다.

D
T1	T2	T3
R(X)
W(X)
Com.
	R(Y)
	W(Y)
	Com.
		R(Z)
		W(Z)
		Com.

3. 2. 직렬 가능 스케줄 (Serializable Schedule)

직렬 가능 스케줄은 실행 결과가 직렬 스케줄과 동일한 스케줄을 의미한다. 이는 데이터베이스의 데이터 일관성과 동시성을 모두 보장하는 중요한 개념이다.^[1]^[2]^[3]

일정 E에서 트랜잭션의 작업이 실행되는 순서는 D와 같지 않지만, 결국 E는 D와 동일한 결과를 제공한다.

E
T1	T2	T3
R(X)
	R(Y)
		R(Z)
W(X)
	W(Y)
		W(Z)
Com.	Com.	Com.

직렬가능성은 데이터 항목의 데이터를 일관된 상태로 유지하는 데 사용된다. 이는 동시 트랜잭션 일정의 정확성에 대한 주요 기준이며, 따라서 모든 범용 데이터베이스 시스템에서 지원된다. 직렬 가능하지 않은 일정은 오류가 발생하기 쉬우며, 이는 매우 해로울 수 있다(예: 은행 내에서 돈을 다룰 때).^[1]^[2]^[3]

응용 프로그램에서 일부 트랜잭션 간의 특정 순서를 요청하는 경우, 이는 기본 직렬 가능성 메커니즘과 독립적으로 적용된다. 이러한 메커니즘은 일반적으로 특정 순서에 무관하며, 이러한 트랜잭션의 여러 직렬 순서와 일반적으로 호환되는 예측할 수 없는 부분 순서를 생성한다.

3. 2. 1. 충돌 직렬 가능성 (Conflict-serializable)

두 개의 액션이 다음 조건을 모두 만족하면 상충(conflict)한다고 한다.

# 서로 다른 트랜잭션에 속한다.

# 적어도 하나는 쓰기 연산이다.

# 동일한 객체에 접근한다(읽기 또는 쓰기).^[4]^[5]

다르게 표현하면, 두 액션은 비가환적인 경우에만 상충한다. 또한, 두 액션은 읽기-쓰기, 쓰기-읽기, 쓰기-쓰기 충돌인 경우에만 상충한다.

다음 액션 집합은 상충한다.

R1(X), W2(X), W3(X) (3개의 상충 쌍)

반면, 다음 액션 집합은 상충하지 않는다.

R1(X), R2(X), R3(X)
R1(X), W2(Y), R3(X)

상충을 줄이면 성능이 향상된다. 왜냐하면 상충은 지연과 중단의 근본적인 원인이기 때문이다.

요청된 상충 연산이 실제로 실행되면 해당 충돌이 '''구체화'''된다. 그렇지 않고 데이터베이스 자체에서 실행되지 않으면, 해당 충돌은 '''비구체화'''된다. 비구체화된 충돌은 우선순위 그래프에서 간선으로 표현되지 않는다.

스케줄 S1과 S2가 다음 두 조건을 모두 만족하는 경우, 두 스케줄은 충돌 등가(conflict equivalent)라고 한다.

# 두 스케줄 S1과 S2는 동일한 트랜잭션 집합을 포함하며, 각 트랜잭션은 동일한 순서로 동일한 작업을 수행한다.

# 두 스케줄은 동일한 충돌 쌍 집합을 갖는다(각 충돌 쌍의 작업은 동일한 순서로 정렬된다).^[6]

다르게 말하면, 두 스케줄은 비 충돌 연산 쌍(인접 여부와 상관없이)을 서로 교환하여 다른 스케줄로 변환할 수 있고, 각 트랜잭션의 작업 순서를 유지하는 경우 충돌 등가라고 한다.^[4]

스케줄은 하나 이상의 직렬 스케줄과 충돌 동등할 때 '''충돌 직렬 가능(conflict serializable)'''이라고 한다.

동등하게, 스케줄은 해당 선행 그래프가 커밋된 트랜잭션만 고려할 때 비순환적일 경우에만 충돌 직렬 가능성이 있다.

스케줄 K는 직렬 스케줄 <T1, T2>와 충돌 동등하지만, <T2, T1>과는 그렇지 않다.

K
T1	T2
R(A)
	R(A)
W(B)
Com.
	W(A)
	Com.

충돌 직렬 가능성은 선행 그래프에서 사이클 내의 모든 트랜잭션을 다시 시작하거나, 2단계 잠금, 타임스탬프 순서 또는 직렬 가능 스냅샷 격리를 구현하여 강제할 수 있다.^[8]

3. 2. 2. 뷰 직렬 가능성 (View-serializable)

두 개의 스케줄 S1과 S2는 다음 조건이 충족될 때 뷰 동등하다고 한다.

# S1에서 트랜잭션

T_i

가 객체 X의 초기 값을 읽는 경우, S2의 동일한 트랜잭션

T_i

도 그렇게 한다.

# S1에서 트랜잭션

T_j

가 기록한 값(객체 X에 대해)을 트랜잭션

T_i

가 읽는 경우, S2에서도 그렇게 해야 한다.

# S1에서 트랜잭션

T_i

가 객체 X에 대한 최종 쓰기를 수행하는 경우, S2의 동일한 트랜잭션

T_i

도 그렇게 한다.

또한, 두 개의 뷰 동등한 스케줄은 동일한 순서로 동일한 작업을 수행하는 동일한 트랜잭션 집합을 포함해야 한다.

아래 예제에서 스케줄 S1과 S2는 뷰 동등하지만 S1과 S2는 스케줄 S3과 뷰 동등하지 않다.

S1		S2		S3
T1	T2	T1	T2	T1	T2
R(A)		R(A)		R(A)
W(A)		W(A)		W(A)
R(B)⁽¹⁾			R(A)		R(A)
W(B)			W(A)		W(A)
Com.		R(B)⁽¹⁾			R(B)⁽¹⁾
	R(A)	W(B)			W(B)
	W(A)	Com.		R(B)⁽²⁾
	R(B)⁽²⁾		R(B)⁽²⁾	W(B)⁽³⁾
	W(B)⁽³⁾		W(B)⁽³⁾	Com.
	Com.		Com.		Com.

S3이 S1 및 S2와 뷰 동등하기 위한 조건은 다음 이유로 해당 위첨자에서 충족되지 않았다.

# T1이 S1과 S2에서 B의 초기 값을 읽었지만 T2가 S3에서 B의 초기 값을 읽었기 때문에 뷰 동등성의 첫 번째 조건을 충족하지 못했다.

# T2가 S1과 S2에서 T1이 기록한 B의 값을 읽었지만 T1이 S3에서 T2가 기록한 값을 읽었기 때문에 뷰 동등성의 두 번째 조건을 충족하지 못했다.

# T2가 S1과 S2에서 B에 대한 최종 쓰기를 수행했지만 T1이 S3에서 B에 대한 최종 쓰기를 수행했기 때문에 뷰 동등성의 세 번째 조건을 충족하지 못했다.

두 스케줄이 뷰 동등한지 빠르게 분석하려면 각 작업의 아래 첨자가 일치하는 뷰 동등성 조건을 나타내는 목록으로 두 스케줄을 작성한다. 두 스케줄 모두에서 모든 작업의 아래 첨자가 동일하거나 없는 경우에만 해당 스케줄은 뷰 동등하다.

S1: R1(A)_{초기 읽기}, W1(A), R1(B)_{초기 읽기}, W1(B), Com1, R2(A)_{T1에 의해 쓰여짐}, W2(A)_{최종 쓰기}, R2(B)_{T1에 의해 쓰여짐}, W2(B)_{최종 쓰기}, Com2
S2: R1(A)_{초기 읽기}, W1(A), R2(A)_{T1에 의해 쓰여짐}, W2(A)_{최종 쓰기}, R1(B)_{초기 읽기}, W1(B), Com1, R2(B)_{T1에 의해 쓰여짐}, W2(B)_{최종 쓰기}, Com2
S3: R1(A)_{초기 읽기}, W1(A), R2(A)_{T1에 의해 쓰여짐}, W2(A)_{최종 쓰기}, '''R2(B)_{초기 읽기}, W2(B), R1(B)_{T2에 의해 쓰여짐}, W1(B)_{최종 쓰기},''' Com1, Com2

일정은 특정 직렬 일정과 뷰-동등한 경우 '''뷰 직렬 가능'''이라고 한다. 정의에 따라 모든 충돌 직렬 가능 일정은 뷰 직렬 가능하다.

G
T1	T2
R(A)
	R(A)
W(B)

위 예시(충돌 직렬 가능성에 대한 논의에 나오는 예시와 동일)는 뷰 직렬 가능하며 동시에 충돌 직렬 가능하다. 그러나 블라인드 쓰기를 수행하는 트랜잭션이 있는 충돌 직렬 가능하지 않은 뷰 직렬 가능 일정이 있다.

H
T1	T2	T3
R(A)
	W(A)
	Com.
W(A)
Com.
		W(A)
		Com.

위 예시는 충돌 직렬 가능하지 않지만 뷰-동등 직렬 일정 를 가지므로 뷰 직렬 가능하다.

일정의 뷰 직렬 가능성을 결정하는 것은 NP-완전 문제이므로, 뷰 직렬 가능성은 실질적인 관심이 거의 없다.

3. 3. 복구 가능 스케줄 (Recoverable Schedule)

복구 가능한 스케줄은 트랜잭션이 실패했을 때 데이터베이스를 일관된 상태로 복구할 수 있는 스케줄이다. 트랜잭션은 해당 트랜잭션이 변경 사항을 읽은 모든 트랜잭션이 커밋된 후에만 커밋된다. 스케줄은 트랜잭션

T_i

가 다른 트랜잭션

T_j

의 변경 사항을 읽고 의존한 다음

T_i

가 커밋되고

T_j

가 중단되면 '''복구 불가능'''하게 된다.

F		F2		J
T1	T2	T1	T2	T1	T2
R(A)		R(A)		R(A)
W(A)		W(A)		W(A)
	R(A)		R(A)		R(A)
	W(A)		W(A)		W(A)
Com.		Abort			Com.
	Com.		Abort	Abort

스케줄 F는 T2 전에 T1이 커밋되므로 T2가 읽은 값이 올바르기 때문에 복구 가능하다. 그러면 T2는 자체적으로 커밋할 수 있다. F2 스케줄에서 T1이 중단되면 T2가 읽은 A의 값이 잘못되었으므로 T2도 중단해야 한다. 두 경우 모두 데이터베이스는 일관된 상태로 유지된다.

스케줄 J는 T2가 이전에 T1이 기록한 값을 읽었음에도 불구하고 T1 전에 커밋되었기 때문에 복구 불가능하다. T2가 커밋된 후 T1이 중단되었기 때문에 T2가 읽은 값은 잘못되었다. 트랜잭션은 커밋된 후 롤백할 수 없으므로 스케줄은 복구 불가능하다.

3. 3. 1. 연쇄 복귀 방지 스케줄 (Cascadeless Schedule)

'''연쇄 중단 방지 일정''' (일명 "연쇄 중단 방지 (ACA) 일정")은 더티 읽기를 허용하지 않음으로써 연쇄 중단을 방지하는 일정이다.^[9] '''연쇄 중단'''은 한 트랜잭션의 중단으로 인해 다른 트랜잭션이 객체에 대한 첫 번째 트랜잭션의 변경 사항을 읽고 의존했기 때문에 중단되는 경우 발생한다. '''더티 읽기'''는 트랜잭션이 다른 트랜잭션에서 커밋되지 않은 쓰기로부터 데이터를 읽는 경우 발생한다.^[9]

다음 예제는 복구 가능성에 대한 논의에서 사용된 것과 동일하다.

F		F2
T1	T2	T1	T2
R(A)		R(A)
W(A)		W(A)
	R(A)		R(A)
	W(A)		W(A)
Com.		Abort
	Com.		Abort

이 예에서 F2는 복구 가능하지만 연쇄 중단을 방지하지 않는다. T2가 T1이 작성한 커밋되지 않은 값을 이미 읽었으므로 T1이 중단되면 일정의 정확성을 유지하기 위해 T2도 중단해야 함을 알 수 있다.

다음은 연쇄 중단을 방지하는 복구 가능한 일정이다. 그러나 T1이 중단되므로 T1에 의한 A 업데이트는 항상 손실된다.

F3
T1	T2
	R(A)
R(A)
W(A)
	W(A)
Abort
	Commit

이 일정은 T1이 커밋되면 직렬화 가능하지 않다.

연쇄 중단 방지는 일정이 복구 가능하기 위한 충분 조건이지만 필요 조건은 아니다.

3. 3. 2. 엄격한 스케줄 (Strict Schedule)

일정은 두 개의 트랜잭션 T1, T2에 대해 T1의 쓰기 연산이 T2의 ''충돌'' 연산(읽기 또는 쓰기)보다 먼저 발생하면, T1의 커밋 또는 중단 이벤트도 T2의 해당 충돌 연산보다 먼저 발생하는 경우 '''엄격'''하다고 한다. 예를 들어, 위의 일정 F3은 엄격하다.

모든 엄격한 일정은 캐스케이드가 없지만, 그 반대는 성립하지 않는다. 엄격성은 데이터베이스의 장애로부터 효율적인 복구를 가능하게 한다.

4. 직렬 가능성 클래스 관계

직렬 가능성과 복구 가능성 클래스 간의 계층적(포함) 관계는 다음과 같다.

직렬 ⊂ 충돌 직렬 가능 ⊂ 뷰 직렬 가능 ⊂ 모든 스케줄
직렬 ⊂ 엄격 ⊂ 캐스케이드 방지(ACA) ⊂ 복구 가능 ⊂ 모든 스케줄

위의 내용은 벤 다이어그램을 통해 확인할 수 있다.

참조

_[1] 서적 Concurrency Control and Recovery in Database Systems http://research.micr[...] Addison Wesley Publishing Company 1987
_[2] 서적 Transactional Information Systems http://www.elsevier.[...] Elsevier 2001
_[3] 논문 Transactional memory: architectural support for lock-free data structures. 1993-05
_[4] 웹사이트 Conflict Serializability in DBMS https://www.geeksfor[...] 2015-12-29
_[5] 서적 Database system concepts McGraw-Hill Education 2020
_[6] 서적 Database management systems McGraw-Hill 2000
_[7] 서적 Database systems: the complete book Pearson/Prentice Hall 2009
_[8] 간행물 Serializable isolation for snapshot databases http://portal.acm.or[...] Proceedings of the 2008 ACM SIGMOD international conference on Management of data 2008-06
_[9] 웹사이트 Cascadeless in DBMS https://www.geeksfor[...] 2019-08-06

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com