[DB] Serializablilty

Serializability

여러 트랜잭션을 병렬로 동시에 처리하면서도 순차적으로 수행한것과 같은 결과를 냄

Correct 조건

• Conflict serializable
• View serializable

Nonserializable Execution 의 조건

• Dirty read

• Lost update
  

  

• Unrepeatable read
  

  

 

Schedule

어떤 스케쥴이 correct 하면 이는 serializable 함

여러 트랜잭션들을 동시에 수행하기 위해서는 그 순서를 스케쥴링해야하는데 스케쥴은 다음 조건을 만족

• 스케쥴은 트랜잭션의 모든 연산들을 포함하고 있어야함
• 스케쥴의 연산 순서는 트랜잭션 내에서의 연산 순서와 동일해야함
• 스케쥴 내 트랜잭션이 성공적으로 마무리되면 commit statement를, 실패했다면 abort statement를 수행한다.

Correct

Incorrect

T1, T2 실행 전 후의 A + B 값이 같아야함 + T1 -> T2 또는 T2 -> T1 의 결과와 같아야함

 

Conflicting instructions

서로 다른 트랜잭션 Ti, Tj 의 instruction Ii, Ij 가 같은 테이블 Q에 write하는 연산이 하나라도 있다면 conflict

Ii = read(Q), Ij = read(Q)  -> Conflict X

Ii = read(Q), Ij = write(Q)  -> Conflict O -> read, write의 순서가 바뀌면 결과가 다르기 때문

Ii = write(Q), Ij = read(Q)  -> Conflict O

Ii = write(Q), Ij = write(Q)  -> Conflict O

 

Conflict serializable schedule

Concurrent execution 되고 있는 스케쥴 S를 Serial 하게 수행되는 S`으로 바꿀 수 있다면 S를 conflict serializable schedule이라고 함

 

S` 을 만드는 규칙 : 서로 conflict 하지 않은 두 명령어의 순서를 바꿈(swap)

S와 S`의 결과가 같으면 correct

예시

Schedule 5는 6으로 변환이 가능함

이게 swap 이라고 표현해서 T1에는 A관련된 연산만 몰려있는 형태가 되는 것으로 생각하면 안됨

Serializable 을 판단하기 위해서는 Schedule 6처럼 serial 하게 수행되는 <T1, T2>의 꼴을 만들어야함

• Conflict instruction 에서 read + read 조합만 non-conflict 하다고 했지만 그건 같은 테이블 Q를 대상으로 할 때만 통하는 이야기임
• Write(B)와 Write(A) 는 A와 B, 서로 다른 테이블을 가리키므로 conflict 하지 않음

 

스케쥴 7은 conflict serializable 하지 않음

<Read(T1, Q), Write(T2, Q)>, <Write(T2, Q), Write(T1, Q)> 이들 모두 conflict 하므로 swap이 불가함

View equivalent

S와 S`이 같은 트랜잭션의 집합을 스케쥴한 것이고, 다음 조건을 만족하면 View equivalent

• S가 읽은 Q의 초기값과 S`이 읽은 Q의 초기값이 같아야함
• S의 Tj가 write(Q)하고, Ti에서 read(Q) 했다면 S`또한 Tj 의 write(Q)를 먼저, Ti의 read(Q)가 나중에 수행되어야함 (순서가 중요)
• 어느 한 스케쥴이 최종 write를 했다면(디스크에 저장) 다른 스케쥴 또한 write를 해야함

View serializability

위 스케쥴은 view serializable 하지만 conflict serializable 하지 않음

 

S` 을 <T5, T6, T7> 라고 해보자

T5	T6	T7
Read(Q)
Write(Q)	Write(Q)
		Write(Q)

 

위와 같을 때 View equivalent 의 세 조건을 모두 만족

 

blind write(read 없이 write만 하는 무지성 write) 를 가진 모든 non-conflict serializable 은 view serializable 함

 

위 스케쥴은 Conflict serializable 하지도, view serializable 하지도 않지만 <T1, T2> 와 같은 결과를 냄으로서 serializable 함

이런 현상은 commutable operator( = 덧셈 뺄셈으로만 이루어진 연산자)로만 이루어진 경우에 가능

 

 

S`<T1, T2>

T1	T2
Read(A)
A := A - 50
Write(A)
Read(B)
B := B + 50
Write(B)
	Read(B)
	B := B - 10
	Write(B)
	Read(A)
	A := A + 10
	Write(A)

 

S와 S`<T1, T2> 가 view serializable 하지 않은 이유

S의 경우 A를 T1 이 쓰고, T2가 읽음. 따라서 <T1, T2>는 가능하지만 <T2, T1> 은 불가능(<T2, T1> 은 A를 T2가 먼저 쓰고, T1이 읽기 때문)

하지만 S는 B에 대해서 T2가 먼저 쓰고, T1이 읽고, <T1, T2> 는 B에 대해서 T1이 먼저 쓰고, T2가 나중에 읽으므로 불가능

 

Serializability 테스트

Conflict serializability 테스트

Precedence graph 의 사이클 유무 판단

그래프 그리는 법 :

Ti와 Tj 가 서로 conflict 한 연산을 가지며 Ti 가 Tj 보다 해당 데이터 아이템에 먼저 접근한다면 Ti -> Tj 의 edge 추가

 

예시

이 경우 T1 -x-> T2 는 <Read(T1, x), Write(T2, x)> 가 conflict 하며 x에 먼저 접근하는 것이 T1 임

T2 -y-> T1 은 <Read(T1, y), Write(T2, y)>가 conflict 하며 y에 먼저 접근하는 것이 T2임

 

 

사이클 검사는 N^2 또는 N+E 의 시간 복잡도로 가능 (N = 정점 수, E = 간선 수) DFS

그래프가 비순환적이라면 topological sorting 을 통해 serializable 하게 만들 수 있음

 

View serializability 테스트

이는 precednece graph 로 테스트할 수 없음

NP-complete 문제