All
락(Lock) 기반 규약
•
직렬 가능성을 보장하기 위해 락(Lock: 잠금)을 사용해 데이터 항목에 연산 적용전 트랜잭션이 락을 획득하고 연산 후 반납하도록 하는 규약
공유 락 (shared lock: S)
•
다른 트랜잭션의 읽기는 허용하되, 쓰기는 차단
•
해당 데이터 항목에 대해 Read 연산만 수행 가능
•
여러 트랜잭션이 동시에 획득 가능 (읽기 동시성 보장)
•
쓰기(Write)나 배타 락(X)은 획득 불가
배타락(exclusive lock: X)
•
해당 데이터 항목에 대한 모든 다른 접근(읽기·쓰기)을 차단
•
획득한 트랜잭션만 Read/Write 모두 수행 가능
•
다른 트랜잭션은 S·X 락 모두 획득 불가
•
오직 하나의 트랜잭션만 소유 가능
락 양립성
공유 락(S) | 배타 락(X) | |
공유 락(S) 요청시 | 가능
다른 트랜잭션들의 읽기와 충돌 없음 | 불가능
이미 읽고 있는 트랜잭션이 있어 쓰기 차단 |
배타 락(X) 요청시 | 불가능
다른 트랜잭션의 읽기 차단 필요 | 불가능
이미 쓰기 중이므로 중복 금지 |
•
S–S 가능: 여러 트랜잭션이 동시에 읽을 수 있으므로 공유 락끼리는 양립
•
S–X 불가: 누군가 읽고 있을 때는 쓰기를 막아야 하므로 배타 락은 대기
•
X–S 불가, X–X 불가: 쓰기 중에는 어떤 접근도 허용되지 않음
•
배타 락(X) 요청 시, 기존의 공유 락이 모두 반납될 때까지 대기하고, 반납 즉시 획득
•
락 반납은 트랜잭션이 Commit 또는 Rollback 시 자동으로, 또는 명시적 UNLOCK 명령으로 수행
예제
T1: Read(A), Write(B)
T2: Read(B), Write(A)
SQL
복사
만약 락을 걸지 않고 동시에 실행되면, A, B의 값이 엉켜서 일관성 없는 결과가 나올 수 있음 → 락 기반 스케줄을 적용해서 이런 문제를 방지함
락 반납이 지연된 트랜잭션
•
락 반납이 늦어질 경우 서로 락을 획득하기 위해 무한 대기에 빠질 수 있음 → 교착상태
T1: X에 배타 락 → Y에 배타 락 요청 (대기)
T2: Y에 배타 락 → X에 배타 락 요청 (대기)
SQL
복사
2단계 락킹 규약(Two-Phase Locking, 2PL)
트랜잭션은 락을 요청, 반납하는 두 단계로 구성
1.
확장 단계
•
트랜잭션이 필요한 락을 자유롭게 요청 가능
•
락 반납은 금지
2.
축소 단계
•
트랜잭션이 락을 하나라도 반납하면 즉시 이 단계로 전환됨
•
이후엔 새로운 락을 절대 요청 불가
•
→ 기존 락만 해제 가능
•
락을 얻고 반납하는 시기를 분리해 직렬성을 보장하나 락 반납 지연에 따른 교착상태 발생할 수 있는 단점 존재
타임스탬프 순서 규약
락을 사용하지 않고도 직렬 가능성을 보장하는 방법
→ 트랜잭션마다 고유한 "타임스탬프"를 부여해서 실행 순서를 시간 기준으로 관리
타임스탬프란?
•
시스템이 트랜잭션 Ti를 시작할 때 고유 번호 TS(Ti) 를 부여함
•
이 번호는 트랜잭션의 논리적 실행 순서를 나타냄
•
TS는 보통 시스템 시간 or 단순 증가하는 숫자(논리 카운터)로 할당
데이터 항목 Q는 트랜잭션들이 접근할때마다 :
W-TS(Q) | 지금까지 Q를 쓴 트랜잭션들 중 가장 늦은 트랜잭션의 TS |
R-TS(Q) | 지금까지 Q를 읽은 트랜잭션들 중 가장 늦은 트랜잭션의 TS |
Ti가 Read(Q)를 수행할때
1.
TS(Ti) < W - TS(Q)
•
Ti보다 나중에 Write(Q)가 이미 발생함 → 이미 미래 데이터가 기록된 상태
•
→ Ti가 과거 데이터 보려는 것이므로 Read 거부 + 롤백
2.
TS(Ti) ≥ W - TS(Q)
•
최신 Write 이후이므로 Read 허용
•
→ R-TS(Q) 값을 max(R-TS(Q), TS(Ti)) 로 업데이트
Ti가 Write(Q)를 수행할때
1.
TS(Ti) < R - TS(Q)
•
나보다 나중 트랜잭션이 이미 Q를 읽어버림
•
→ 내가 Write 하면 읽은 결과를 무효화함 → Write 거부 + 롤백
2.
TS(Ti) < W - TS(Q)
•
나보다 신선한 값이 이미 Q에 기록됨
•
→ 내가 쓰는 건 낡은 데이터 덮어쓰기 → Write 거부 + 롤백
3.
둘다 아니면 Wirte 연산 수행하고 W-TS(Q)는 TS(Ti)로 업데이트
동작 | 실패 조건 | 설명 |
Read(Q) | TS(Ti) < W-TS(Q) | 미래에 쓴 값을 읽으려 함 → 위험해서 거부 |
Write(Q) | TS(Ti) < R-TS(Q)또는 TS(Ti) < W-TS(Q) | 이미 누군가 읽었거나 더 신선한 값이 있음 → 덮어쓰기 방지 |
토마스 기록 규칙
타임스탬프 기반 Write 연산 시 더 공격적으로 Write를 생략하는 규칙
•
기존 규칙:
◦
TS(Ti) < W-TS(Q) → Write 거부 + 롤백
•
토마스 규칙:
◦
TS(Ti) < W-TS(Q) → 그냥 무시하고 Write도 안 하고, 롤백도 안 함
어차피 최신 값보다 더 옛날 값을 덮어쓰려는 시도라서 그냥 무시하고 넘어감
교착상태(Deadlock)
특정 트랜잭션 집합 내에 속하는 모든 트랜잭션이 집합 내의 다른 트랜잭션을 기다리고 있는 상태
교착상태 발생이 잦은 시스템의 처리 전략
예방이 중요 → 교착상태 방지 규약 사용
교착방지 규약
1.
모든 데이터 항목에 락을 미리 걸기
2.
타임스탬프 기반 선점 기법
•
wait-die 기법(비선점)
◦
나보다 오래된 트랜잭션이 자원을 점유하고 있다면 → 기다린다
◦
나보다 더 오래된 트랜잭션이 아닌데 자원을 점유하고 있다면 → 내가 롤백
•
TS(Ti) < TS(Tj) : 더 오래된 Ti가 기다림
•
TS(Ti) > TS(Tj) : 더 최근인 Ti가 롤백
•
wound-wait 기법(선점):
◦
내가 오래된 트랜잭션이면 → 새 트랜잭션을 밀어내고 락을 가져옴
◦
내가 새 트랜잭션이면 → 그냥 기다림
•
TS(Ti) < TS(Tj) : 더 오래된 Ti가 Tj를 롤백시키고 락을 선점
•
TS(Ti) > TS(Tj) : 더 최근인 Ti는 기다림
교착상태 발생 빈도가 낮은 시스템의 처리 전략
예방보다 발생 후 감지하고 회복하는 방식이 더 효율적
•
주기적으로 교착 상태가 발생했는지 검사하고, 발생한 경우 회복 절차 수행
교착상태 탐지
•
대기그래프(wait-for graph)를 이용하여 확인 가능
◦
노드(Vertex): 트랜잭션 (Ti, Tj, ...)
◦
간선(Edge): Ti → Tj는 Ti가 Tj가 가진 락을 기다리는 상태
•
대기 그래프에 사이클이 있다면 교착상태 발생
교착상태의 회복
교착상태 해결을 위해 시스템에서 한 트랜잭션을 희생(victim)시켜 강제 롤백
1.
희생자선정: 롤백 비용이 가장 적은 트랜잭션을 선택
•
작업한 시간 vs 남은 작업량
•
점유/요청한 데이터 자원량
•
롤백 시 다른 트랜잭션에 미치는 영향 (연쇄 롤백 발생 가능성)
2.
희생자 롤백: 어느 시점까지 롤백할 것인지 결정
•
전체 롤백할지, 교착상태를 해결하는 지점까지 할지
•
이를 위해 모든 트랜잭션의 상태와 로그 정보를 별도 저장해 관리
3.
무한정 기다림(starvation) 해결
•
동일 트랜잭션이 계속 희생자로 선정되지 않도록 희생자 선정 시 롤백 횟수를 기록하고 일정 이상일 경우 희생자에서 제외하는 로직 적용