18. Concurrency Control

Overview

Concurrency Control(동시성 제어): 충돌하는 명령 간의 실행 순서를 변경하지 않으면서, 동시성 레벨을 가능한 한 높게 만드는 스케줄 생성

Lock-based Protocols

Lock: 데이터 아이템에 대한 동시 접근을 제어하는 메커니즘
데이터 아이템은 두 가지 모드로 잠길 수 있음.
1. eXclusive (X) mode: 데이터 아이템을 읽고 쓸 수 있음.
- lock-X 및 unlock 명령을 사용하여 X-lock을 요청하고 해제
1. Shared (S) mode: 데이터 아이템을 읽을 수만 있음.
- lock-S 및 unlock 명령을 사용하여 S-lock을 요청하고 해제
모든 transaction은 데이터 아이템 Q에 대해 수행할 operation 유형에 따라 적절한 모드로 lock을 요청
- Lock 요청은 Concurrency-Control Manager로 전달
- Lock 요청이 승인된 후에만 transaction이 진행 가능
요청된 lock이 해당 아이템에 대해 다른 transaction이 이미 보유하고 있는 lock과 compatible하면 transaction은 lock을 부여받을 수 있음.
S-lock: 임의의 수의 transaction이 아이템에 대해 보유 가능
X-lock: 한 transaction이 X-lock을 보유하고 있다면, 다른 transaction은 해당 아이템에 대해 어떠한 lock도 보유할 수 없음.

	S	X
S	true	false
X	false	true

Lock compatibility Matrix

Schedule with Lock Grants

나머지 장에서는 grant 생략
Lock 요청 바로 다음에 오는 다음 명령 직전에 grant가 발생한다고 가정
이 스케줄은 serializable하지 않음.
- Lock을 단순히 획득/해제하는 것만으로는 Transaction isolation serializability을 보장하지 못함.

$T_1$	$T_2$	Concurrency-Control manager
$\text{lock-X}(B)$		$\text{grant-X}(B,~T_1)$
$\text{read}(B)$ $B:=B-50$ $\text{write}(B)$ $\text{unlock}(B)$
	$\text{lock-S}(A)$
		$\text{grant-S}(A,~T_2)$
	$\text{read}(A)$ $\text{unlock}(A)$ $\text{lock-S}(B)$
		$\text{grant-S}(B,~T_2)$
	$\text{read}(B)$ $\text{unlock}(B)$ display( $A+B$ )
$\text{lock-X}(A)$
		$\text{grant-X}(A,~T_1)$
$\text{read}(A)$ $A:=A+50$ $\text{write}(A)$ $\text{unlock}(A)$

Locking Protocols

Locking Protocol: 모든 transaction이 lock을 요청하고 해제할 때 따르는 규칙의 집합
가능한 스케줄 집합을 제한하여 직렬성을 강제
주어진 locking Protocol 하에서,
- 스케줄 S는 해당 Protocol을 따르는 transaction 집합에 의해 생성될 수 있다면 해당 Protocol 하에서 legal
- Protocol은 해당 Protocol 하의 모든 legal 스케줄이 serialiazable하다면 직렬성을 보장

Deadlock and Starvation

부분 스케줄(Partial Schedule)을 고려했을 때
- $T_3$ 와 $T_4$ 모두 진행할 수 없음.
- $\text{lock-S}(B)$ 실행은 $T_4$ 가 $T_3$ 가 B에 대한 X-lock을 해제하기를 기다리게 하고, lock-X(A) 실행은 $T_3$ 가 $T_4$ 가 A에 대한 S-lock을 해제하기를 기다리게 함.
이러한 상황을 Deadlock이라고 함.
Deadlock을 처리하려면 $T_3$ 또는 $T_4$ 중 하나가 rollback되어야 하고 lock이 해제되어야 함.
Deadlock의 잠재성은 대부분의 locking protocol에 존재하며, 이는 필요악
Starvation 또한 concurrency control manager가 잘못 설계되면 발생 가능
- Case 1: 한 transaction이 아이템에 대한 X-lock을 기다리는 동안, 다른 transaction들의 연속적인 S-lock 요청이 승인되는 경우
- Case 2: 동일한 transaction이 deadlock으로 인해 반복적으로 rollback되는 경우
Concurrency control manager는 starvation을 방지하도록 설계될 수 있음.

$T_3$	$T_4$
$\text{lock-X}(B)$ $\text{read}(B)$ $B:=B-50$ $\text{write}(B)$
	$\text{lock-S}(A)$ $\text{read}(A)$ $\text{lock-S}(B)$
$\text{lock-X}(A)$

Two-Phase Locking (2PL) Protocol

Conflict-Serializable 스케줄을 보장하는 protocol
각 transaction은 lock 요청과 해제를 두 단계로 나누어 실행해야 함.

단계 1: Growing 단계
- Transaction은 lock을 획득할 수 있음.
- Transaction은 lock을 해제할 수 없음.
단계 2: Shrinking 단계
- Transaction은 lock을 해제할 수 있음.
- Transaction은 lock을 획득할 수 없음.
이 Protocol은 직렬성을 보장
- Transaction들은 lock Point(최종 lock을 획득한 시점) 순서로 serialize될 수 있음이 증명 가능
Two-Phase locking은 직렬성을 위한 필수 조건은 아님
- 2PL을 사용하지 않아도 얻을 수 있는 conflict Serializable 스케줄이 있음.
그러나 Data 접근 순서와 같은 추가 정보가 없는 경우, Two-Phase locking은 충돌 직렬성에 필요
추가 정보가 있다면, 2PL 이외의 다른 locking Protocol을 고안할 수 있음.
Two-Phase locking은 deadlock으로부터의 자유를 보장하지 않음.
Cascading roll-back이 없는 recoverability를 보장하기 위해 기본 2PL에 확장이 필요함.
- Strict Two-Phase locking: Transaction은 commit 또는 abort할 때까지 모든 X-lock을 보유해야 함.
  - Recoverability를 보장하고 cascading roll-back을 방지
- Rigorous Two-Phase locking: Transaction은 commit 또는 abort할 때까지 모든 lock을 보유해야 함.
  - Transaction은 commit 순서로 serialize될 수 있음.
Lock conversions
- $T_1$ : $\text{read}(a_1),~\text{read}(a_2),~\dots,~\text{read}(a_n),~\text{write}(a_1)$
- $T_2$ : $\text{read}(a_1),~\text{read}(a_2),~\dots,~\text{display}(a_1+a_2)$
- $T_1$ $T_{1}$ 은 $a_1$ $a_{1}$ 에 대한 X-lock을 획득해야 함.
  - $T_1$ 이 $T_2$ 보다 먼저 시작하면, $T_1$ 과 $T_2$ 의 모든 동시 실행은 직렬 실행과 같음.
  - 그러나 $T_1$ 은 최종 실행에서만 X-lock이 필요
- $T_1$ 이 먼저 S-lock을 획득하고 나중에 lock을 X-lock으로 변경한다면, $T_1$ 과 $T_2$ 가 $a_1$ 과 $a_2$ 에 동시에 접근할 수 있으므로 더 높은 동시성을 얻을 수 있음.
- Lock upgrade: S-lock을 X-lock으로 변환
- Lock Downgrade: X-lock을 S-lock으로 변환
Lock conversion을 포함한 Two-Phase locking Protocol
- Growing Phase
  - 아이템에 대한 S-lock 획득
  - 아이템에 대한 X-lock 획득
  - S-lock을 X-lock으로 변환 (Upgrade)
- Shrinking Phase
  - S-lock 해제
  - X-lock 해제
  - X-lock을 S-lock으로 변환 (Downgrade)
이 Protocol은 직렬성을 보장
Strict Two-Phase locking 및 rigorous Two-Phase locking (Lock conversion 포함)은 상용 Database 시스템에서 광범위하게 사용되며, 단순히 Two-Phase locking으로 지칭되기도 함.

Automatic Acquisition of Locks

Transaction $T_i$ 는 명시적인 locking 호출 없이 표준 read/write 명령을 실행
operation read(D) 처리 방식

if Ti has a lock on D then read(D);
else begin
    if necessary wait until no other transaction has a X-lock on D;
    grant Ti a S-lock on D;
    read(D);
end

operation write(D) 처리 방식

if Ti has a X-lock on D then write(D);
else begin
    if necessary wait until no other transaction has any lock on D;
    if Ti has a S-lock on D then
        upgrade lock on D to X-lock;
    else grant Ti a X-lock on D;
    write(D);
end

모든 lock은 commit 또는 abort 후에 해제 (Rigorous 2PL 사용)

Implementation of Locking

Lock manager는 별도의 프로세스로 구현될 수 있음.
Transaction은 lock 및 unlock 요청을 lock Manager에게 메시지로 보냄
Lock manager는 lock Grant 메시지(또는 Deadlock의 경우 transaction에게 rollback을 요청하는 메시지)를 보내 lock 요청에 응답
요청하는 transaction은 요청에 응답할 때까지 대기
Lock Table
- Lock manager가 관리하는 인메모리 자료구조
- 승인된 lock과 보류 중인 요청을 기록
- 일반적으로 lock이 걸린 데이터 아이템의 이름을 인덱스로 하는 해시 테이블로 구현
- 각 해시된 데이터 아이템에 대해, 요청이 도착한 순서대로 각 요청에 대한 레코드의 연결 리스트가 존재
- 충돌 해결을 위해 chaining 사용

Lock Table

연결 리스트의 각 레코드에 포함되는 것들
- 요청을 보낸 transaction
- 요청한 lock 모드
- 현재 요청이 승인되었는지의 여부
새로운 lock 요청 메시지 도착 시
- 데이터 아이템에 대한 연결 리스트 끝에 레코드 추가 (비어 있으면 리스트 생성)
- 이전의 모든 lock과 compatible하면 승인
unlock 메시지 도착 시
- 리스트에서 해당 레코드 삭제
- 뒤따르는 레코드 (있는 경우)를 검사하여 이제 승인될 수 있는지 확인
Transaction이 Abort하면, transaction의 대기 중이거나 승인된 모든 요청이 삭제됨.
- Lock manager는 이를 효율적으로 구현하기 위해 각 transaction이 보유한 lock의 리스트를 유지할 수 있음.

(Optional) Graph-based Protocols

alt text

추가 정보가 있다면 충돌 직렬성을 보장하는 Two-Phase locking 이외의 다른 locking protocol을 고안할 수 있음.
간단한 추가 정보: Database 아이템에 접근하는 순서
- 모든 데이터 아이템의 집합 $\mathbf{D} = \{d_1,~d_2,~\dots,~d_h\}$ 에 partial ordering (→)를 부과
- $d_i \to d_j$ 이면, $d_i$ 와 $d_j$ 모두에 접근하는 모든 transaction은 $d_j$ 보다 $d_i$ 에 먼저 접근해야 함.
- 이러한 partial ordering은 Data의 논리적 또는 물리적 조직의 결과일 수도 있고, 오로지 concurrency control 목적으로만 부과될 수도 있음.
- 집합 D는 이제 directed Acyclic Graph(Database Graph)로 볼 수 있음.
Tree Protocol: X-lock만 사용하도록 제한된 간단한 Graph-based Protocol
- 각 transaction $T_i$ $T_{i}$ 는 데이터 아이템을 최대 한 번 lock할 수 있으며, 다음 규칙을 준수해야 함.
  - $T_i$ 의 첫 번째 lock은 모든 데이터 아이템에 걸릴 수 있음.
  - 그 후, 데이터 아이템 Q는 $Q$ 의 parent가 현재 $T_i$ 에 의해 lock된 경우에만 $T_i$ 에 의해 lock될 수 있음.
  - 데이터 아이템은 언제든지 unlock될 수 있음.
  - $T_i$ 에 의해 lock되고 unlock된 데이터 아이템은 그 후에 $T_i$ 에 의해 다시 lock될 수 없음.
Tree Protocol은 충돌 직렬성과 deadlock으로부터의 자유를 보장
Tree Protocol에서는 2PL보다 unlock이 더 일찍 발생할 수 있음.
- 대기 시간 단축 및 동시성 증가
- Protocol은 Deadlock-free: rollback이 필요 없음.
단점
- 이 역시 recoverability 또는 cascade freedom을 보장하지 않음.
  - Recoverability 보장을 위해 commit dependency 도입 필요
  - $T_i$ 가 uncommitted 데이터 아이템 Q를 읽을 때, Q를 마지막으로 write한 uncommitted transaction에 대한 $T_i$ 의 commit dependency를 기록
  - $T_i$ 는 commit dependency를 가진 모든 transaction이 commit될 때까지 commit이 허용되지 않음: 이들 중 하나라도 abort하면 $T_i$ 도 abort되어야 함.
- Transaction은 접근하지 않는 데이터 아이템도 lock해야 할 수 있음.
  - 예: A와 J에 접근하기 위해 B, D, H 아이템도 lock해야 함.
  - Locking overhead 증가 및 추가 대기 시간
  - 잠재적인 동시성 감소
2PL에서는 불가능한 스케줄이 tree protocol에서 가능하며, 그 반대도 가능

Deadlock Prevention

$T_3$	$T_4$
$\text{lock-X}(B)$ $\text{read}(B)$ $B:=B-50$ $\text{write}(B)$
	$\text{lock-S}(A)$ $\text{read}(A)$ $\text{lock-S}(B)$
$\text{lock-S}(A)$

Deadlock: Transaction 집합이 존재하여, 집합 내의 모든 transaction이 집합 내의 다른 transaction을 기다리고 있는 상태
Deadlock Prevention Protocols: 시스템이 deadlock 상태로 진입하지 않도록 보장하는 protocol. 일부 예방 전략
- 각 transaction이 실행을 시작하기 전에 모든 데이터 아이템을 lock하도록 요구 ('Hold-and-wait' 조건 제거)
- 모든 데이터 아이템에 partial ordering를 부과하고 transaction이 데이터 아이템을 지정된 순서로만 lock할 수 있도록 요구 ('Circular wait' 조건 제거)
Transaction timestamp-based Schemes
- Wait-Die Scheme (Non-preemptive)
  - older transaction은 Younger transaction이 데이터 아이템을 해제하기를 기다릴 수 있음.
  - Younger transaction은 older transaction을 절대 기다리지 않으며, 대신 rollback됨.
- Wound-Wait Scheme (Preemptive)
  - older transaction은 기다리는 대신 Younger transaction을 wound(Rollback 강제)
  - Younger transaction은 older transaction을 기다릴 수 있음.
- 두 Scheme 모두
  - 경로우대사상 기반
  - Rollback된 transaction은 원래 timestamp로 다시 시작되어 starvation을 방지
  - 불필요한 rollback이 발생할 수 있음.
Lock Timeout-based Schemes (Deadlock 탐지 & 복구와 유사)
- Transaction은 lock을 위해 지정된 시간 동안만 대기
- 그 후, 대기 시간이 초과되면 transaction이 rollback됨.
- Deadlock이 발생하면 timeout으로 해결되도록 보장
- 구현은 간단하지만, deadlock이 없는 경우에도 transaction을 불필요하게 rollback할 수 있음.
- 적절한 timeout 간격 값을 결정하기 어려움
- Starvation 또한 발생 가능

Deadlock Detection

Wait-for Graph: Transaction을 정점으로 하는 directed graph
- $T_i \to T_j$ 로의 Edge: $T_i$ 가 $T_j$ 가 conflicting 모드로 보유한 lock을 기다리고 있는 경우
- 시스템이 deadlock 상태 $\iff$ wait-for Graph에 cycle이 있음.
주기적으로 deadlock-Detection 알고리즘을 호출하여 cycle을 찾음.
Deadlock이 감지되면
- Deadlock cycle을 깨기 위해 일부 transaction이 rollback되어야 함 (Victim)
- Victim으로 최소 비용을 초래하는 transaction을 선택
- Rollback: Transaction을 어디까지 rollback할지 결정
  - Total rollback: Transaction을 abort하고 다시 시작
  - Partial rollback: Cycle 내의 다른 transaction이 기다리고 있는 lock을 해제하는 데 필요한 만큼만 victim transaction을 rollback
- Starvation 가능성 → 해결책
  - 가장 오래된 transaction은 victim으로 선택하지 않음.

Multiple Granularity

지금까지 개별 데이터 아이템을 locking unit으로 사용
때로는 여러 데이터 아이템을 그룹화하여 하나의 개별 locking unit으로 처리하는 것이 유리
- 예: 전체 relation을 스캔할 때, Tuple-level lock을 발행하는 대신 전체 relation을 lock하는 단일 lock 요청을 발행하는 것이 좋음.
- → 시스템이 다중 수준의 Granularity를 정의할 수 있도록 하는 메커니즘이 필요
데이터 아이템이 다양한 크기를 갖도록 허용하고, 작은 Granularity가 더 큰 Granularity 내에 Nest되는 계층 구조를 정의
- Tree 형태로 그래픽적으로 표현 가능
Transaction이 Tree의 노드를 명시적으로 lock하면, 해당 노드의 모든 Descendant를 같은 모드로 암묵적으로 lock
Locking Granularity(Locking이 수행되는 Tree의 수준)
- Fine Granularity (Tree의 하위): 높은 동시성, 높은 locking overhead
- Coarse Granularity (Tree의 상위): 낮은 locking overhead, 낮은 동시성

Example of Granularity Hierarchy

가장 거친(상위) 수준부터 시작하는 수준
- Database (DB) → Area $(A_1, A_2)$ → File $(F_a,~F_b,~F_c)$ → record

문제: $T_1$ $T_{1}$ 이 $F_c$ $F_{c}$ 에 X-lock을 보유하고 있다고 가정. $F_c$ $F_{c}$ 에 속하는 모든 레코드에 X-lock을 암묵적으로 보유
- Case 1: $T_2$ $T_{2}$ 가 $r_{c1}$ $r_{c 1}$ 에 대한 lock 요청을 발행 (명시적으로 lock되지 않음). $T_2$ $T_{2}$ 가 $r_{c1}$ $r_{c 1}$ 을 lock할 수 있는지 어떻게 결정?
  - Root에서 $r_{c1}$ 까지 Tree를 Traverse해야 하며, 해당 경로의 어떤 노드라도 Incompatible 모드로 lock되어 있으면 $T_2$ 는 대기해야 함.
- Case 2: $T_3$ $T_{3}$ 가 전체 DB에 대한 lock 요청을 발행. 이는 승인되어서는 안 됨. 어떻게 결정?
  - Incompatible lock이 있는지 전체 Tree를 Traverse하여 확인해야 함.
해결책: Intention lock 모드

Intention Lock Modes

S 및 X lock 모드 외에, Multiple Granularity를 위한 세 가지 추가 lock 모드(Intention lock Modes)
- Intention-shared (IS): Tree의 하위 수준에서 명시적 locking이 Shared 모드 lock으로만 수행됨을 나타냄
- Intention-exclusive (IX): Tree의 하위 수준에서 명시적 locking이 Exclusive 모드 또는 Shared 모드 lock으로 수행됨을 나타냄
- Shared and intention-exclusive (SIX): 해당 노드를 root로 하는 Subtree가 Shared 모드로 명시적으로 lock되어 있으며, 하위 수준에서 Exclusive 모드 lock으로 명시적 locking이 수행되고 있음을 나타냄
노드가 명시적으로 lock되기 전에 해당 노드의 모든 ancestor에 intention lock이 설정됨.
- Ancestor 노드를 S 또는 X 모드로 lock할 때 모든 descendant 노드를 확인할 필요 없이 허용
모든 lock 모드에 대한 compatibility Matrix

	IS	IX	S	SIX	X
IS	true	true	true	true	false
IX	true	true	false	false	false
S	true	false	true	false	false
SIX	true	false	false	false	false
X	false	false	false	false	false

Multiple Granularity Locking Protocol

Transaction $T_i$ $T_{i}$ 는 다음 규칙을 사용하여 Node $Q$ $Q$ 를 lock할 수 있음.
1. Lock compatibility matrix를 준수해야 함.
2. Tree의 root가 가장 먼저 lock되어야 하며, 어떤 모드로든 lock될 수 있음.
3. Node $Q$ 는 $T_i$ 의 parent가 현재 IX 또는 iS 모드로 lock된 경우에만 S 또는 iS 모드로 lock될 수 있음.
4. Node $Q$ 는 $T_i$ 의 parent가 현재 IX 또는 SIX 모드로 lock된 경우에만 X, sIX, 또는 iX 모드로 lock될 수 있음.
5. $T_i$ 는 이전에 어떠한 노드도 unlock하지 않은 경우에만 노드를 lock할 수 있음 (즉, $T_i$ 는 Two-Phase)
6. $T_i$ 는 $Q$ 의 자식 중 $T_i$ 에 의해 현재 lock된 것이 없는 경우에만 Node $Q$ 를 unlock할 수 있음.
Lock은 root에서 leaf 순서로 획득되는 반면, leaf에서 root 순서로 해제됨을 관찰
Lock Granularity Escalation: 특정 수준에 lock이 너무 많은 경우, 더 높은 Granularity S 또는 X lock으로 전환

Insert/Delete Operations

지금까지 read 및 write 연산에 국한하여 논의
일부 transaction은 새로운 데이터 아이템을 생성 (Insert)하거나 기존 데이터 아이템을 제거 (Delete)
Insert/Delete 연산에 대한 locking 규칙
- Read/write 충돌과 delete를 방지하기 위해 아이템이 Delete되기 전에 X-lock을 획득해야 함.
- Transaction이 데이터베이스에 새로운 tuple을 삽입할 때, 해당 Tuple에 대한 X-lock이 자동으로 부여 → Tuple을 삽입하는 transaction이 commit될 때까지 삽입된 Tuple은 다른 transaction이 접근할 수 없음.

Timestamp-Based Protocols

각 transaction $T_i$ 는 시스템에 진입할 때 timestamp $\text{TS}(T_i)$ 가 부여됨.
각 transaction은 고유한 timestamp를 가짐.
Newer transaction은 Earlier transaction보다 timestamp가 엄격하게 큼.
Timestamp는 시스템 클럭 또는 논리적 counter일 수 있음.
Timestamp-based Protocols은 transaction의 timestamp가 serializability order를 결정하도록 동시 실행을 관리
- $\text{TS}(T_i) < \text{TS}(T_j)$ 이면, 시스템은 생성된 스케줄이 $T_i$ 가 $T_j$ 보다 먼저 나타나는 직렬 스케줄과 동등하도록 보장해야 함.
구현을 위해 각 데이터 아이템 Q에 두 개의 timestamp를 연결
- $\text{W-timestamp}(Q)$ : $\text{write}(Q)$ 를 성공적으로 실행한 transaction 중 가장 큰 Timestamp
- $\text{R-timestamp}(Q)$ : $\text{read}(Q)$ 를 성공적으로 실행한 transaction 중 가장 큰 Timestamp
- 이러한 Timestamp는 새로운 $\text{read}(Q)$ 또는 $\text{write}(Q)$ Instruction이 실행될 때마다 업데이트됨.
Timestamp를 기반으로 하는 몇 가지 대안적인 protocol 존재

Timestamp-Ordering Protocol

Timestamp-Ordering (TSO) Protocol
Read 및 write 연산에 규칙을 부과하여 다음을 보장
- 모든 conflicting 연산은 Timestamp order로 실행
- out of order 연산은 transaction rollback 및 새로운 TS로 재시작을 유발
Transaction $T_i$ $T_{i}$ 가 $\text{read}(Q)$ $read (Q)$ 를 발행한다고 가정
1. $\text{TS}(T_i) < \text{W-timestamp}(Q)$ $TS (T_{i}) < W-timestamp (Q)$ 이면, $T_i$ $T_{i}$ 는 나중 transaction에 의해 이미 overwrite된 $Q$ $Q$ 의 값을 읽으려고 함.
  - 따라서 read 연산은 거부되고 $T_i$ 는 rollback됨.
2. $\text{TS}(T_i) \ge \text{W-timestamp}(Q)$ 이면, read 연산은 실행되고 $\text{R-timestamp}(Q)$ 는 $\text{max}(\text{R-timestamp}(Q),~\text{TS}(T_i))$ 로 설정됨.
Transaction $T_i$ $T_{i}$ 가 $\text{write}(Q)$ $write (Q)$ 를 발행한다고 가정
1. $\text{TS}(T_i) < \text{R-timestamp}(Q)$ $TS (T_{i}) < R-timestamp (Q)$ 이면, $T_i$ $T_{i}$ 가 생성하는 $Q$ $Q$ 의 값이 이전에 나중 transaction에 의해 필요했음 (즉, 그 값은 결코 생성되지 않을 것임)
  - 따라서 write 연산은 거부되고 $T_i$ 는 rollback됨.
2. $\text{TS}(T_i) < \text{W-timestamp}(Q)$ $TS (T_{i}) < W-timestamp (Q)$ 이면, $T_i$ $T_{i}$ 는 $Q$ $Q$ 의 obsolete value를 write하려고 함.
  - 따라서 이 write 연산은 거부되고 $T_i$ 는 rollback됨.
3. 그렇지 않으면, write 연산은 실행되고 $\text{W-timestamp}(Q)$ 는 $\text{TS}(T_i)$ 로 설정됨.

Example of Schedule under TSO

이 스케줄이 TSO 하에서 유효한가?
- 초기 가정
  - $\text{R-TS}(A) = \text{W-TS}(A) = 0$
  - $\text{R-TS}(B) = \text{W-TS}(B) = 0$
- $\text{TS}(T_{25}) = 25$ 이고 $\text{TS}(T_{26}) = 26$ 이라고 가정

$T_{25}$	$T_{26}$
$\text{read}(B)$
	$\text{read}(B)$ $B:=B-50$ $\text{write}(B)$
$\text{read}(A)$
	$\text{read}(A)$
$\text{display}(A+B)$
	$A:=A+50$ $\text{write}(A)$ $\text{display}(A+B)$

이 스케줄은 TSO 하에서 유효함.
초기에 $\text{R-TS}(Q) = \text{W-TS}(Q) = 0$ 인 이 스케줄은?

Time	$T_{27}$ ( $\text{TS}=27$ )	$T_{28}$ ( $\text{TS}=28$ )
$1$	$\text{read}(Q)$
$2$		$\text{write}(Q)$
$3$	$\text{write}(Q)$

$T_{27}$ 의 두 번째 $\text{write}(Q)$ 시도에서 $\text{TS}(T_{27}) = 27 < \text{R-TS}(Q) = 28$ 이므로, write 연산은 거부되고 $T_{27}$ 은 rollback됨.

Thomas’ Write Rule

Timestamp-Ordering Protocol의 수정된 버전으로, obsolete write 연산은 특정 상황에서 무시될 수 있음.
$T_i$ $T_{i}$ 가 데이터 아이템 Q를 write하려고 할 때, (규칙의 순서 중요)
1. $\text{TS}(T_i) < \text{R-timestamp}(Q)$ 이면, write 연산은 거부되고 $T_i$ 는 rollback됨.
2. $\text{TS}(T_i) < \text{W-timestamp}(Q)$ 이면, $T_i$ 는 $Q$ 의 obsolete value를 write하려고 함.
- $T_i$ 를 rollback하는 대신, 이 write 연산은 그냥 무시될 수 있음.
1. 그렇지 않으면, write 연산은 실행되고 $\text{W-timestamp}(Q)$ 는 $\text{TS}(T_i)$ 로 설정됨.
이 Protocol의 첫 번째와 세 번째 규칙은 Timestamp-Ordering Protocol과 동일
Thomas’ write rule의 correctness
- $T_i$ 가 첫 번째 규칙을 통과. 따라서 $\text{TS}(T_i) \ge \text{R-timestamp}(Q)$
- $\text{TS}(T_i) < \text{W-timestamp}(Q)$ 이면, $\text{R-timestamp}(Q) \le \text{TS}(T_i) < \text{W-timestamp}(Q)$
- 이는 Q를 write한 transaction이 Q를 읽은 적이 없음을 의미 (Blind write)
- Blind write는 아이템의 이전 값에 의존하지 않음 → 이전 write는 안전하게 무시될 수 있음.
Thomas’ write rule은 더 큰 잠재적 동시성을 허용
Conflict-Serializable하지 않은 일부 View-Serializable 스케줄을 허용

Validation-based Protocols (Optimistic Concurrency Control)

Concurrency-Control Scheme
- Code 실행 overhead를 부과
- Transaction 실행을 지연시킬 수 있음.
대다수 transaction이 read-only이고 transaction 간의 충돌 비율이 낮은 경우
- Concurrency-Control 없이 실행되더라도 많은 transaction이 시스템을 일관된 상태로 남길 것
- → 더 적은 overhead를 부과하는 대안적인 Concurrency-Control Scheme을 사용하는 것이 좋음.
Idea: Concurrency control 없이 (로컬 변수에서) 실행한 다음, serializability 위반을 일으키지 않으면 DB에 write (유효성 검사 테스트를 통해)
- Write는 transaction 종료 시점으로 연기
- Transaction이 read/write한 데이터 아이템을 추적
- Commit 시점에 유효성 검사를 수행하여 Serialization order를 벗어난 read/write를 감지
Transaction이 유효성 검사 동안 모든 것이 잘 될 것이라는 희망으로 완전히 실행되므로 **Optimistic Concurrency Control (OCC)**이라고도 함.
Transaction $T_i$ $T_{i}$ 의 실행은 세 단계로 수행
1. Read and Execution Phase: $T_i$ 실행. 데이터 아이템을 (임시) 로컬 변수에 읽고 저장. 실제 데이터베이스 업데이트 없이 로컬 변수에 write
2. Validation Phase: $T_i$ 는 직렬성을 위반하지 않고 로컬 변수를 write할 수 있는지 결정하기 위한 Validation test(유효성 검증)를 수행. transaction이 validation test에 실패하면 Abort됨 (Rollback 필요 없음).
3. Write Phase: $T_i$ 가 validate되면 업데이트가 데이터베이스에 적용됨 (Read-only transaction은 이 단계를 생략)
동시에 실행되는 transaction의 세 단계는 interleave될 수 있음.
하지만 각 transaction은 반드시 그 순서대로 세 단계를 거쳐야 함.
단순화를 위해 validation 및 write 단계는 원자적이고 직렬적으로 함께 발생한다고 가정
- 즉, 한 번에 하나의 transaction만 validation/write를 실행
각 transaction $T_i$ $T_{i}$ 는 3개의 timestamp를 가짐.
- $\text{StartTS}(T_i)$ : $T_i$ 가 실행을 시작한 시간
- $\text{ValidationTS}(T_i)$ : $T_i$ 가 validation 단계에 진입한 시간
- $\text{FinishTS}(T_i)$ : $T_i$ 가 write 단계를 완료한 시간
$\text{ValidationTS}(T_i)$ $ValidationTS (T_{i})$ 를 사용하여 TSO에 의해 serializability order를 결정
- 즉, $\text{TS}(T_i) = \text{ValidationTS}(T_i)$
- $\text{TS}(T_j) < \text{TS}(T_k)$ 이면, 생성된 모든 스케줄은 $T_j$ 가 $T_k$ 보다 먼저 나타나는 직렬 스케줄과 동등해야 함.
Validation test는 위 timestamp와 read/write Set을 사용하여 serializability order가 validation time에 의해 결정되도록 보장
- Read Set of $T_i$ : $T_i$ 가 read한 데이터 아이템의 집합
- Write Set of $T_i$ : $T_i$ 가 write한 데이터 아이템의 집합
Validation-based protocol은 충돌 확률이 낮은 경우 locking/TSO보다 더 높은 동시성을 제공하는 것으로 밝혀짐.

Validation Test

Transaction $T_i$ $T_{i}$ 에 대한 validation test는 $\text{TS}(T_k) < \text{TS}(T_i)$ $TS (T_{k}) < TS (T_{i})$ 인 모든 $T_k$ $T_{k}$ 에 대해 다음 조건 중 하나가 hold해야 함을 요구
- $\text{FinishTS}(T_k) < \text{StartTS}(T_i)$ $FinishTS (T_{k}) < StartTS (T_{i})$
  - $T_k$ 가 $T_i$ 가 시작하기 전에 실행을 완료했으므로, serializability order는 실제로 유지됨.
- Write Set of $T_k$ $T_{k}$ $\cap$ $\cap$ read Set of $T_i = \emptyset$ $T_{i} = \emptyset$ , AND $T_k$ $T_{k}$ 가 $T_i$ $T_{i}$ 가 validation 단계를 시작하기 전에 write 단계를 완료
  - $\text{StartTS}(T_i) < \text{FinishTS}(T_k) < \text{ValidationTS}(T_i)$
위 조건 중 하나가 hold하면 validation은 성공하고 $T_i$ 는 write 단계로 진행할 수 있음. 그렇지 않으면 validation은 실패하고 $T_i$ 는 abort됨.
Justification
- 첫 번째 조건: Transaction의 실행이 concurrent하지 않을 때 적용
  - Serializability order는 자연스럽게 유지됨.
- 두 번째 조건: 실행이 concurrent하지만, $T_i$ $T_{i}$ 는 $T_k$ $T_{k}$ 가 write한 어떤 아이템도 read하지 않았고, $T_i$ $T_{i}$ 는 $T_k$ $T_{k}$ 의 read에 영향을 미칠 수 없음.
  - $\text{FinishTS}(T_k) < \text{ValidationTS}(T_i)$ 는 $T_i$ 에 의한 write가 실제로 데이터베이스에 write되지 않았기 때문에 $T_k$ 가 $T_i$ 에 의한 어떤 write도 보지 않았음을 보장

Schedule Produced by Validation

Validation을 사용하여 생성된 스케줄의 예

$T_{25}$	$T_{26}$
$\text{read}(B)$
	$\text{read}(B)$ $B:=B-50$ $\text{read}(A)$ $A:=A+50$
$\text{read}(A)$ $\text{<validate>}$ $\text{display}(A+B)$

Read set of $T_{25} = \{A,~B\}$
Write set of $T_{25} = \emptyset$

Read set of $T_{26} = \{A,~B\}$
Write set of $T_{26} = \{A,~B\}$

$\text{StartTS}(T_{26}) < \text{Finish}$

위 스케줄은 직렬 스케줄 $<T_{25},~T_{26}>$ (Validation timestamp order)과 동등