타임스탬프 기반 동시성 제어 (Timestamp Ordering)

타임스탬프 기반 동시성 제어 (Timestamp Ordering)

각 트랜잭션에 시작 시간 기반 타임스탬프(TS)를 부여하고, 데이터 항목의 읽기/쓰기 타임스탬프와 비교하여 직렬가능 순서를 보장하는 비잠금(Lock-free) 동시성 제어 기법

목적: 잠금 없이 직렬가능성 보장, 교착상태 원천 방지

특징: 비잠금 기반, 타임스탬프 순서 강제, 충돌 시 롤백(Abort), 교착상태 없음

구성요소

• •TS(Ti): 트랜잭션 Ti의 타임스탬프 (시작 시간 또는 카운터)
• •R-TS(X): 데이터 X를 읽은 가장 최근 트랜잭션의 타임스탬프
• •W-TS(X): 데이터 X를 쓴 가장 최근 트랜잭션의 타임스탬프

동작규칙 (Basic TO)

• •Read(X): TS(Ti) < W-TS(X)이면 롤백(나보다 새로운 쓰기가 있음), 아니면 읽기 후 R-TS(X) 갱신
• •Write(X): TS(Ti) < R-TS(X) 또는 TS(Ti) < W-TS(X)이면 롤백, 아니면 쓰기 후 W-TS(X) 갱신

Thomas Write Rule: Write 시 TS(Ti) < W-TS(X)이면 롤백 대신 쓰기를 무시(Obsolete Write 건너뜀), 불필요한 롤백 감소, 뷰 직렬가능 스케줄 허용

Strict TO: 커밋되지 않은 트랜잭션이 쓴 데이터는 읽기/쓰기 모두 대기, 캐스케이드 롤백 방지

비교: TO(비잠금/교착상태없음/롤백빈번) vs 2PL(잠금기반/교착상태가능/롤백적음) vs MVCC(다버전/읽기무잠금) vs 낙관적(사후검증/읽기위주적합)

연관: 동시성 제어, 직렬가능성, 2PL, MVCC, 교착상태