Timestamp-Based Protocols
- 각 transaction Ti는 고유한 timestamp TS(Ti)를 가진다.
- Timestamp는 transaction이 시작할 때 할당되며, 새로운 transaction들은 이전 것들보다 큰 timestamp를 가진다.
- Timestamp는 logical counter를 기반으로 할 수 있다.
- Real time은 unique하지 않을 수 있으므로 (wall-clock time, logical counter)를 사용하여 uniqueness를 보장할 수 있다.
- Timestamp-based protocol은 timestamp order = serializability order가 되도록 concurrent execution을 관리한다.
Timestamp-Ordering Protocol
TSO(Timestamp-Ordering) protocol은 각 data Q에 대해 두 개의 timestamp value를 유지한다:
- W-timestamp(Q): write(Q)를 성공적으로 실행한 transaction 중 가장 큰 timestamp
- R-timestamp(Q): read(Q)를 성공적으로 실행한 transaction 중 가장 큰 timestamp
이 protocol은 read와 write operation에 규칙을 부과하여 다음을 보장한다:
- 모든 conflicting operation들이 timestamp 순서로 실행된다
- Out of order operation들은 transaction rollback을 야기한다
Read Operation 규칙
Transaction Ti가 read(Q)를 수행할 때:
- TS(Ti) >= W-timestamp(Q)인 경우:
- Read operation이 실행된다
- R-timestamp(Q)가 max(R-timestamp(Q), TS(Ti))로 설정된다
- TS(Ti) < W-timestamp(Q)인 경우:
- Ti는 이미 overwrite된 Q를 읽어야 한다
- Read operation이 거부되고 Ti가 rollback된다
Write Operation 규칙
Transaction Ti가 write(Q)를 수행할 때:
- TS(Ti) < R-timestamp(Q)인 경우:
- Ti가 생성하려는 Q의 value가 이전에 필요했고, system은 그 value가 절대 생성되지 않을 것이라고 가정했다.
- 즉, 시간 순서대로 라면 자신이 쓰고난 뒤 늦게 시작한 트랜잭션이 읽는것이 맞으므로 롤백돼야된다,.
- Write operation이 거부되고 Ti가 rollback된다
- TS(Ti) < W-timestamp(Q)인 경우:
- Ti가 Q의 obsolete value를 write하려고 시도한다
- Write operation이 거부되고 Ti가 rollback된다
- 그 외의 경우:
- Write operation이 실행되고 W-timestamp(Q)가 TS(Ti)로 설정된다
Example of Schedule Under TSO
TSO(Timestamp Ordering) 프로토콜은 각 트랜잭션(Transaction)의 타임스탬프(timestamp)를 기반으로 동시성 제어(concurrency control)를 수행하는 방법이다.
각 데이터 아이템(data item) A, B, Q 등은 다음 두 가지 타임스탬프를 가진다.
- R-TS(X): 데이터 아이템 X에 대해 가장 최근에 읽은 트랜잭션의 타임스탬프
- W-TS(X): 데이터 아이템 X에 대해 가장 최근에 쓴 트랜잭션의 타임스탬프
첫 번째 예시
초기 상태:
- R-TS(A) = W-TS(A) = 0
- R-TS(B) = W-TS(B) = 0
- TS(T25) = 25
- TS(T26) = 26
이 스케줄(schedule)이 TSO 하에서 유효(valid)한지 판단하려면, 각 read/write 연산이 타임스탬프 규칙을 위반하는지 확인해야 한다.
- read(X): 트랜잭션의 TS < W-TS(X)이면 abort
- write(X): 트랜잭션의 TS < R-TS(X) 또는 트랜잭션의 TS < W-TS(X)이면 abort
두 번째 예시
초기 상태:
R-TS(Q) = 27
W-TS(Q) = 28
rollback
세 번째 예시(Partial Schedule)
여러 데이터 아이템에 대해 트랜잭션 T1~T5가 타임스탬프 1~5를 가지고, 모두 R-TS, W-TS가 0에서 시작하는 경우이다.
이 예시에서는 T1, T3이 abort되는 것을 볼 수 있다. 이는 TSO 규칙에 따라 타임스탬프 조건을 위반했기 때문이다.
이렇게 TSO는 각 트랜잭션의 타임스탬프와 데이터 아이템의 R-TS, W-TS 값을 비교하여, 동시성 제어를 수행하고, 필요 시 트랜잭션을 abort시킨다.
TSO Protocol의 정확성
- Timestamp-ordering protocol은 precedence graph의 모든 arc가 특정 형태를 가지므로 serializability를 보장한다.
- 따라서 precedence graph에 cycle이 없다.
- Timestamp protocol은 어떤 transaction도 기다리지 않기 때문에 deadlock으로부터 자유롭다.
- 하지만 schedule이 cascade-free하지 않을 수 있고, 심지어 recoverable하지 않을 수도 있다.
- Schedule이 recoverable하려면 transaction들이 의존하는 모든 transaction들이 commit한 후에만 commit해야 한다.
- 예시로 T1이 롤백되면, T1이 수정한 값을 읽어서 의존성이 있는 T2도 롤백돼야된다.
Recoverability와 Cascade 예방
Solution 1: Transaction의 모든 write가 processing 마지막에 수행되도록 구조화한다.
Transaction의 모든 write가 atomic action을 형성하고, transaction이 write되는 동안 다른 transaction은 실행할 수 없다.
Solution 2: 제한된 형태의 locking을 사용하여 data가 commit되기를 기다린 후 읽는다.
Solution 3: Commit dependency를 사용하여 recoverability를 보장한다.
Thomas' Write Rule
- Timestamp-ordering protocol의 수정된 버전이다.
- Obsolete write operation들이 무시된다.
- Ti가 data item Q를 write하려고 시도할 때, TS(Ti) < W-timestamp(Q)이면 Ti는 Q의 obsolete value를 write하려고 시도하는 것이다.
- Timestamp ordering protocol이 Ti를 rollback하는 대신, 이 write operation을 무시할 수 있다. (blind write)
- 그 외에는 timestamp ordering protocol과 동일하다.
- Thomas' Write Rule은 더 큰 potential concurrency를 허용한다.
- Conflict-serializable하지 않지만 view-serializable한 일부 schedule들을 허용한다.
Validation-based Concurrency Control (Optimistic Concurrency Control)
- Validation-based protocol은 commit time을 serialization order로 사용할 수 있는지에 대한 아이디어에서 출발한다.
- 이를 위해 write를 transaction의 끝으로 연기하고, transaction이 read/write한 data item들을 추적한다.
- Validation은 commit time에 수행되어 serialization order를 벗어나는 read/write를 감지한다.
- 이 방법은 validation 동안 모든 것이 잘 진행될 것이라는 희망으로 transaction이 완전히 실행되기 때문에 optimistic concurrency control이라고도 불린다.
Execution Phase
Transaction Ti의 실행은 세 단계로 이루어진다:
- Read and Execution Phase: Transaction Ti는 temporary local variable에만 write한다.
- Validation Phase Transaction: Ti는 local variable들이 serializability를 위반하지 않고 write될 수 있는지 결정하기 위해 validation test를 수행한다.
- Write Phase: Ti가 validated되면 update들이 database에 적용되고, 그렇지 않으면 Ti가 rollback된다.
간단화를 위해 validation과 write phase가 atomically하고 serially하게 함께 발생한다고 가정한다. 즉, 한 번에 하나의 transaction만이 validation/write를 실행한다.
하지만 동시에 실행되는 transaction들의 세 phase는 interleaved(교차)될 수 있다.
Timestamp 구조
각 transaction Ti는 3개의 timestamp를 가진다:
- StartTS(Ti): Ti가 실행을 시작한 시간
- ValidationTS(Ti): Ti가 validation phase에 진입한 시간
- FinishTS(Ti): Ti가 write phase를 완료한 시간
Validation test는 위의 timestamp들과 read/write set을 사용하여 serializability order가 validation time에 의해 결정되도록 보장한다. 따라서 TS(Ti) = ValidationTS(Ti)이다.
Validation-based protocol은 conflict의 확률이 낮은 경우 locking/TSO보다 더 큰 정도의 concurrency를 제공하는 것으로 발견되었다.
Validation Test
Transaction Tj에 대한 validation test는 다음과 같다:
TS(Ti) < TS(Tj)인 모든 Ti에 대해 다음 조건 중 하나가 성립하면:
- finishTS(Ti) < startTS(Tj)
- Execution이 concurrent하지 않다 -> serial 하게 진행됐다.
- startTS(Tj) < finishTS(Ti) < validationTS(Tj) and Tj가 Ti에 의해 write된 어떤 data item도 read하지 않는다
- Dependency가 없다
이 경우 validation이 성공하고 Tj가 commit될 수 있다. 그렇지 않으면 validation이 실패하고 Tj가 abort된다.
Schedule Produced by Validation
Validation(검증) 기반 스케줄은 Optimistic Concurrency Control(OCC)에서 트랜잭션(Transaction)들이 종료 시점에 충돌(conflict) 여부를 검사하여 커밋(commit) 또는 abort를 결정하는 방식이다.
트랜잭션 흐름
- T25, T26 두 트랜잭션이 존재한다.
- 각 트랜잭션은 StartTS(시작 타임스탬프), ValidationTS(검증 타임스탬프), CommitTS(커밋 타임스탬프)를 가진다.
T25의 동작
- StartTS(T25)에서 read(B) 수행
- read(A) 수행
- ValidationTS(T25) 시점에 검증(<validate>)
- display(A+B) 수행
- CommitTS(T25)에서 커밋
T26의 동작
- StartTS(T26)에서 read(B) 수행
- B := B - 50 연산
- read(A) 수행
- A := A + 50 연산
- ValidationTS(T26) 시점에 검증(<validate>)
- write(B), write(A) 실행
- CommitTS(T26)에서 커밋
검증 순서와 의미
- T25가 먼저 검증(validation) 절차를 거치고 커밋된다.
- T26은 T25가 커밋된 이후에 검증을 시도한다.
- 하단 수식: startTS(T{26}) < finishTS(T{25}) < validationTS(T{26})
- T25는 이미 커밋되었지만, read-only 트랜잭션이므로 T26의 검증에 영향을 주지 않는다.
요약
- OCC에서는 각 트랜잭션이 종료 시점에만 충돌 검사를 수행한다.
- T25가 먼저 검증을 받고, 그 이후에 T26이 검증을 받는 순서로 스케줄이 진행된다.
- T25가 read-only이므로 T26의 update(write)에 영향을 주지 않고, 두 트랜잭션 모두 커밋된다.
Validation-Based Protocol (OCC) 예시
예시 시나리오
1. 기본 구조
- 각 트랜잭션(T1, T2)은 Read-Exec Phase에서 데이터베이스의 데이터(A)를 읽고, 자신의 workspace에 복사하여 연산을 진행한다.
- 트랜잭션은 Validate(검증) 단계에서 충돌 여부를 검사하고, 검증에 성공하면 Write(쓰기) 단계에서 변경 내용을 데이터베이스에 반영한다.
2. 실행 흐름
- T1, T2 모두 데이터베이스에서 A를 읽어 각자의 workspace에 저장한다.
- 각 트랜잭션은 workspace에서 A := A+1 연산을 수행한다.
- T2가 먼저 validation(검증) 단계에 진입하고, 충돌이 없으므로 write(쓰기) 단계에서 데이터베이스 A를 1로 갱신한다.
- 이후 T1이 validation 단계에 진입할 때, T2의 write로 인해 직렬성(serializability) 조건이 위배되어 T1은 abort된다.
3. Validation & Write
- Validation(검증) 단계: 트랜잭션이 종료 시점에 자신의 read set, write set이 다른 트랜잭션과 충돌하는지 검사한다.
- Write(쓰기) 단계: 검증에 성공한 트랜잭션만 실제 데이터베이스에 변경 내용을 반영한다.
- 위 그림에서 T2는 정상적으로 커밋되고, T1은 validation에서 실패하여 abort된다.
4. 단계별 설명
- Read-Exec Phase: 트랜잭션은 데이터베이스에서 데이터를 읽어 workspace에 저장하고, 필요한 연산을 workspace에서 수행한다.
- Validation Phase: 트랜잭션 종료 시점에 read set, write set을 기반으로 다른 트랜잭션과의 충돌 여부를 검사한다.
- Write Phase: 검증에 성공한 트랜잭션만 데이터베이스에 변경 내용을 반영한다. 검증에 실패한 트랜잭션은 abort된다.
정리
- OCC는 transaction이 동시에 실행되어도, commit 시점에 직렬성이 보장되지 않으면 rollback(abort)된다.
- Read-Exec Phase 동안은 실제 데이터베이스에 영향이 없고, validation에서만 충돌 여부를 확인한다.
- 충돌이 적은 환경에서 높은 동시성을 제공한다.
댓글