방송대 데이터베이스시스템 - 13강. 동시성 제어
1. 락 기반 규약
동시성 제어의 개념
· 트랜잭션 직렬화(결과의 일관성)와 회복화(원자성 회복)는 스케줄이 데이터 일관성에 영향을 미치는 여부를 판별하고 일관성이 유지되는 상태로 복원시키기 위해 정의한 개념
· 일관성 훼손을 발생시키는 트랜잭션에 대해 동시성 제어를 통해 일관성 유지에 개입
- 트랜잭션 간 연산의 순서를 제어
- 어떠한 데이터 읽기, 갱신 연산에도 무결성을 유지
- 동시에 실행되는 트랜잭션의 수를 증가 → 자원 이용률 극대화, 사용자 만족도 최대화
· 동시성 제어 규약 종류 : 락 기반 규약, 타임스탬프 기반 규약, 검증 기반 규약
락 기반 규약
직렬 가능성을 보장하기 위해 락(잠금)을 사용하여 데이터 항목에 연산 적용 전 트랜잭션이 락을 획득하고 연산 후 반납하도록 하는 규약
락의 종류
| 공유 락(shared lock: S) | 트랜잭션 T가 LS(Q) 명령으로 데이터 항목 Q에 공유 락을 획득하면, T는 Q를 읽을 수 있지만 쓸 수는 없는 락 |
| 배타 락(exclusive lock: X) | 트랜잭션 T가 LX(Q) 명령으로 데이터 항목 Q에 대한 배타 락을 획득하면, T가 Q를 읽고 쓸 수 있는 락 |
락 양립성
트랜잭션은 연산하고자 하는 데이터에 대한 락을 획득해야만 연산 진행 가능 (락 → 처리)
락 양립성 함수
| 공유 락(S) | 배타 락(X) | |
| 공유 락(S) | 가능 | 불가능 |
| 배타 락(X) | 불가능 | 불가능 |
·공유락은 다른 공유 락과 양립 가능
·배타 락과 다른 락과 양립 불가능
·배타 락의 요청(양립될 수 없는 락의 요청)은 공유 락이 반납될 때까지 대기
·락의 반납은 UN() 명령 사용
• LS(Q) : 데이터 Q에 대한 공유 락을 요청한다.
• LX(Q) : 데이터 Q에 대한 배타 락을 요청한다.
• UN(Q) : 데이터 Q에 대한 공유/배타 락을 반납한다.
락을 데이터 접근 직후 반납하는 경우
락을 너무 일찍 반납하면 일관성이 훼손됨.
 |
 |
| T10 : Write(B)를 위해서 B에 대한 배타 락(LX(B))을 걸어둠. T11 : Read(A)를 위해서 A에 대한 공유 락(Read(A))을 걸어둠. |
T10이 락을 일찍 반납하여 비일관적인 상태에서 데이터접근이 가능해져 T11이 정확하지 않은 결과값을 출력 (T10의 모든 작업이 이루어져야 T11에서 출력되는 값이 정확함) |
락 반납 지연의 문제
락을 너무 늦게 반납하면 일관성은 유지되나, 교착 상태가 발생함.
 |
 |
T12가 B에 대한 배타 락을 확보한 이후, T13이 B에 대한 공유 락을 요청함.
→ 배타 락과 공유 락은 양립하지 못하므로 T13은 T12가 배타 락 반납할 때까지 기다림. ( LS(B)~ )
T13이 A에 대한 공유 락을 확보한 이후, T12가 A에 대한 배타 락을 요청함.
→ 배타 락과 공유 락은 양립하지 못하므로 T12는 T13이 공유 락을 반납할 때까지 기다림. ( LX(A)~ )
교착상태(deadlock)
· 두 트랜잭션 중 하나를 롤백해야 해결됨.
· 한 트랙잭션이 롤백되면 그 트랜잭션이 획득했던 모든 락은 반납
· 데이터베이스에서 여러 트랜잭션들이 자원을 점유한 상태에서 상호적으로 다른 트랜잭션의 자원을 기다리는 상황
→ 모든 트랜잭션이 무한정 기다리게 되어 시스템이 정지될 수 있음.
Ti → Tj
· 트랜잭션 Ti가 Tj에 선행한다
· 동등한 연산 순서를 가지는 모든 스케줄에서 Ti가 Tj에 우선해야 한다는 의미임.
· Ti가 Q에 대해 A락을 소유하고, 이후 Tj가 Q에 대해 B락을 소유하면서 COMP(A, B)='불가능'인 경우
적법한 스케줄(legal schedule) : 스케줄 S가 락킹 규약을 준수하는 트랜잭션에 대한 스케줄
충돌 직렬성을 보장한다 : 모든 적법한 스케줄에서의 각 드랜잭션들에 대해 '→' 관계가 사이클(cycle)을 포함하지 않은 경우
결론 :
- 락을 너무 일찍 반납하면 일관성 훼손됨.
- 락을 너무 늦게 반납하면 교착 상태가 발생함.
→ 2단계 락킹규약이 마련됨.
2단계 락킹 규약(2PL, two-phase locking protocol)
· 확장 단계(growing phase) : 트랜잭션이 락을 얻을 수 있으나, 락을 반납할 수 없는 단계
· 축소 단계(shrinking phase) : 트랜잭션이 락을 반납할 수는 있으나, 새로운 락을 얻을 수 없는 단계
초기 트랜잭션은 확장단계에서부터 시작되며, 데이터 접근을 위해 락을 추가적으로 요청할 수 있음.
→ 트랜잭션이 획득한 락 중 하나라도 반납할 때
→ 트랜잭션은 축소 단계로 전환되며, 더 이상 락 요청을 할 수 없음.
직렬성을 보장하나 교착상태는 예방할 수 없음.
엄격한 2단계 락킹 규약(Rigorous 2PL)
기존의 2단계 락킹 규약과 달리 트랜잭션이 모든 락을 유지하다가 커밋이 되거나 중단될 경우에만 락을 해지함.
트랜잭션 Ti가 Read(A) 연산을 수행하면 시스템은 해당 읽기 연산에 대하여 락을 설정한다.
Ti가 Write(A) 연산을 수행하면 시스템은 Ti가 A에 공유 락을 보유하고 있는지 확인한다.
- Ti가 공유 락을 보유하고 있다면 공유 락을 배타 락으로 변환함.
- Ti가 공유 락을 보유하고 있지 않다면 바로 A에 대하여 배타 락을 설정함.
Ti에 의해 얻어진 모든 락은 해당 트랜잭션이 커밋되거나 중단되면 해지된다.
2단계 락킹 규약 vs 엄격한 2단계 락킹 규약
| 2단계 락킹 규약 | 엄격한 2단계 락킹 규약 | |
| 정의 | 트랜잭션은 락을 요청하기 전에 락을 획득해야 함 | 트랜잭션은 락을 획득할 때까지 기다렸다가 한 번에 획득 |
| 락 | 공유락과 배타적 락 사용 | 배타적 락만 사용 |
| 획득 순서 | 획득한 락을 언락하기 전까지 임의의 순서로 획득 가능 | 획득한 락을 언락하기 전까지 엄격한 순서로 획득 |
| 장점 | 단순하고 유연한 구조 | 데드락 가능성이 더 적음 |
| 단점 | 데드락 가능성이 높음 | 구현이 복잡하고 비효율적임 |
| 예시 | 트랜잭션 T1이 공유 락을 획득하고, 이후 트랜잭션 T2도 공유 락을 획득 가능. 트랜잭션 T1이 공유 락을 획득한 상태에서 배타적 락을 요청하면 대기해야 함. |
트랜잭션 T1이 배타적 락을 획득하면, 이후 트랜잭션 T2는 락을 획득하기 위해 대기해야 함. 트랜잭션 T1이 배타적 락을 획득한 이후에는 T2가 락을 획득할 수 없음. |
2. 타임스탬프 기반 규약
타임스탬프 기반 규약
· 각 트랜잭션 Ti 실행의 순서를 판단하기 위해 타임스탬프 TS(Ti)를 부여
· 트랜잭션의 타임스탬프는 늦을수록 값이 커짐
· 실행순서 : T1 → T2 → T3이면 Ts(T1) < Ts(T2) < Ts( T3)
TS(Ti) < TS(Tj)라면 Ti가 Tj 이전에 나타나는 직렬 스케줄과 동등한 스케줄 생성
데이터 항목에 대한 타임스탬프 할당
• W-TS(Q) : Write(Q)를 성공적으로 실행한 트랜잭션 중 가장 큰 타임스탬프
• R-TS(Q) : Read(Q)를 성공적으로 실행한 트랜잭션 중 가장 큰 타임스탬프
타임스탬프 할당 방법
• 시스템 클럭 값 : 트랜잭션의 타임스탬프를 그 트랜잭션이 시스템으로 들어올 때의 시스템 클럭 값으로 설정, 대부분 사용
• 논리적 계수기 : 새로운 타임스탬프가 발급될 때마다 증가되는 논리적 계수기의 계수기 값으로 설정
Ti가 Read(Q)를 수행할 때
 |
TS(Ti) < W-TS(Q) → Read 연산이 거부되고, Ti는 롤백 |
 |
TS(Ti) ≥ W-TS(Q) → Read 연산이 수행되고, R-TS(Q)는 기존 R-TS(Q)와 TS(Ti) 중 최대값으로 설정 |
Ti가 Write(Q)를 수행할 때
 |
TS(Ti) < R-TS(Q) 또는 TS(Ti) < W-TS(Q) TS(Ti) < R-TS(Q) : Ti가 쓰려고 하는 데이터 항목 Q읙 값은 이미 변경된 값을 읽은 것이므로 순서에 위배됨. TS(Ti) < W-TS(Q) : Ti가 쓰려고 하는 Q의 값은 무의미한 값임. → Write 연산이 거부되고 Ti는 롤백 |
 |
TS(Ti) ≥ R-TS(Q) 또는 TS(Ti) ≥ W-TS(Q) → Write 연산을 수행하고 W-TS(Q)는 TS(Ti)로 설정 |
타임스탬프 기반의 동시성 제어 기법의 효과
· 상충되는 연산이 타임스탬프 순서로 처리되므로 직렬성이 보장됨.
· 트랜잭션이 기다려야 하는 경우가 없기 때문에 교착상태를 방지할 수 있음.
· 연쇄적 롤백을 초래할 수 있음.
→ 완료 비트(commit bit)를 통해 트랜잭션이 완료된 값만 읽을 수 있도록 보장
타임스탬프 기반 규약의 적용
TS(T14) < TS(T15)
 |
 |
타임스탬프 기반 규약에 어긋나는 부분이 없음.
토마스(Thomas) 기록 규칙
타임스탬프 순서 규약 중 읽기 연산에 대해서는 규약을 변경할 필요가 없지만 쓰기 연산을 위한 규약은 수정함.
트랜잭션에서 무의미한 Write 연산을 제거하는 방법으로 직렬성을 제공함.
트랜잭션 Ti가 Write(Q)를 수행하려고 할 때,
· TS(Ti) < R-TS(Q)이면 Write 연산이 거부되고, Ti는 롤백
· TS(Ti) < W-TS(Q)이면 Write 연산은 거부됨. (차이점: Ti가 롤백 X)
· 그렇지 않으면 Write 연산을 수행하고 W-TS(Q)는 TS(Ti)로 설정함.
 |
 |
3. 교착상태
교착상태(deadlock)
특정 트랜잭션 집합 내에 속하는 모든 트랜잭션이 집한 내의 다른 트랜잭션을 기다리고 있는 상태
트랜잭션 Ti, Tj, Tk가 있을 때, Ti가 Tj이 소유한 데이터를, Tj는 Tk가 소유한 데이터를, Tk는 Ti가 소유한 데이터를 무한정 기다리는 상태
→ 해결 방법은 그중에 일부분을 반드시 롤백시키는 것임.
교착상태 처리 방법
· 교착상태 방지(prevention) : 교착상태가 발생하지 않도록 보장
· 교착상태 검출(detection) : 교착상태 여부를 검사
· 교착상태 복구(recovery) : 손실을 최소화하고 빠르게 회복
교착상태 발생이 비교적 높은 시스템의 경우
→ 교착상태 방지 규약 사용
· 모든 데이터 항목에 대해 락을 설정하는 기법
- 트랜잭션이 시작되기 전에 어떤 데이터에 락을 걸어야 하는지 미리 알기가 어려움.
- 락이 걸린 상태에서 많은 데이터들이 오랫동안 사용되지 않아 데이터 항목에 대한 이용률이 매우 낮아짐.
· 타임스탬프를 이용한 선점유 기법
교착상태 발생이 비교적 높지 않은 시스템의 경우
→ 교착상태 탐지와 회복 기법 사용
· 대기 그래프
· 희생자 선정
교착상태 방지
교착상태가 발생할 가능성이 있는 트랜잭션의 실행을 막아 발생을 원천적으로 불가능하게 만드는 기법
타임스탬프를 이용
Wait-die 기법
오래된 트랜잭션(타임스탬프가 작은 트랜잭션)이 새로운 트랜잭션을 기다리는 방법, 비선점유 기반
Ti가 Tj에 주어진 락이 걸린 데이터를 요청하는 경우
→ TS(Ti) < TS(Tj)일 때 Ti가 기다리고 TS(Ti) ≥ TS(Tj)이면 Ti가 롤백됨.
T18, T19, T20의 타임스탬프가 8, 11, 20이라고 가정
· T18이 T19에 의해 점유된 데이터 항목을 요청하면 T18은 기다려야 함.
· T20이 T18에 의해 점유된 데이터 항목을 요청하면 T20은 롤백됨.
wound-wait 기법
오래된 트랜잭션(타임스탬프가 작은 트랜잭션)이 새로운 트랜잭션을 강제로 롤백시키는 방법, 선점유 기반
Ti가 Tj에 주어진 락이 걸린 데이터를 요청하는 경우
→ TS(Ti) > TS(Tj)일 때 Ti가 기다리고, TS(Ti) ≤ TS(Tj)인 경우 Tj를 롤백하고 락을 이양함.
T18, T19, T20의 타임스탬프가 8, 11, 20이라고 가정
· T18이 T19에 의해 점유된 데이터 항목을 요청하면 T18은 T19로부터 데이터 항목을 선점유하고, T19는 롤백됨.
· T20이 T18에 의해 점유된 데이터 항목을 요청하면 T20은 기다림.
wait-die 기법 vs wound-wait 기법
| wait-die 기법 | wound-wait 기법 |
| 오래된 트랜잭션(타임스탬프가 작은 트랜잭션)이 새로운 트랜잭션을 기다리는 방법 | 오래된 트랜잭션(타임스탬프가 작은 트랜잭션)이 새로운 트랜잭션을 강제로 롤백시키는 방법 |
| 타임스탬프가 작은 트랜잭션은 타임스탬프가 큰 트랜잭션이 데이터 항목을 반납하길 기다려야 함. 트랜잭션의 타임스탬프가 작을수록 기다리는 경향이 많음. |
타임스탬프가 작은 트랜잭션은 절대 타임스탬프가 큰 트랜잭션을 기다리지 않음. |
| 롤백되는 수가 많을 수 있음. Ti가 요청, TS(Ti) ≥ TS(Tj)이면 Ti가 롤백 Ti는 필요한 데이터 항목을 얻기 전에 여러번 롤백될 수 있음. |
롤백되는 수가 적을 수 있음. Ti가 요청, TS(Ti) ≤ TS(Tj)이면 Tj가 롤백되고 락을 이양 Tj가 다시 시작되어 Ti가 소유한 데이터 요청하면 기다림. |
선점유 vs 비선점유
| 선점유(Preemptive Approach) | 비선점유(Non-preemptive Approach) |
| 트랜잭션이 다른 트랜잭션의 락을 선점할 수 있음 | 트랜잭션이 다른 트랜잭션의 락을 선점할 수 없음 |
| 더 높은 우선순위의 트랜잭션이 더 낮은 우선순위의 트랜잭션을 강제로 롤백시키고 해당 락을 획득할 수 있음. | 더 높은 우선순위의 트랜잭션이 더 낲은 우선순위의 트랜잭션을 기다려야 함. |
| Wound-wait 기법 오래된 트랜잭션(더 작은 값의 타임스탬프)이 우선권을 가짐. |
Wait-Die 기법 오래된 트랜잭션(더 작은 값의 타임스탬프)이 새로운 트랜잭션을 기다리는 방법 |
교착상태 탐지와 회복
교착상태 발생이 비교적 높지 않은 시스템의 경우 주기적으로 교착상태를 탐지하고 발생 시 회복 절차를 수행
탐지 및 회복 절차
· 트랜잭션이 할당된 데이터 항목과 현재 요청되고 있는 데이터 항목에 대한 정보를 유지
· 교착상태가 발생여부를 판별하기 위해 시스템의 상태를 검사하는 알고리즘을 주기적으로 수행
· 교착상태가 검출되면 시스템은 교착상태로부터 회복을 위한 절차를 수행
교착상태 탐지
대기 그래프(wait-for graph)를 이용하여 확인 가능
· 정점 V : 시스템 내의 트랜잭션으로 구성
· 간선 E : 트랜잭션의 순서쌍(Ti, Tj)
· Ti가 요청한 데이터의 락을 Tj가 소유하고 있으며, Ti는 Tj가 락을 반납하기 대기하는 상태
대기 그래프에 사이클이 있다면 교착 상태가 발생
 |
트랜잭션 T12는 트랜잭션 T13과 T14를 기다리고 있다. 트랜잭션 T13은 트랜잭션 T15를 기다리고 있다. 트랜잭션 T14는 트랜잭션 T13을 기다리고 있다. 트랜잭션 T15는 트랜잭션 T14를 기다리고 있다. 이 그래프는 사이클 T13 → T15 → T14를 포함하고 있음. 트랜잭션 T13, T14, T15는 교착상태에 있음. |
대기그래프를 통해 사이클이 있는지 없는지를 판별하고 그 사이클을 해결하기 위한 또다른 회복 절차를 돌입함.
교착상태의 회복
• 희생자 선정 : 롤백 비용이 가장 적은 트랜잭션을 선택
- 연산을 수행한 시간과 남은 작업을 마치기 위한 시간
- 사용한 데이터와 트랜잭션 실행에 필요한 추가적인 데이터
- 롤백에 포함되는 트랜잭션의 개수
• 희생자 롤백 : 어느 시점까지 롤백할 것인지 결정
- 전체 롤백 VS 교착상태를 해결하는 지점
- 모든 트랜잭션의 상태에 대한 정보를 부가적으로 유지
• 무한정 기다림 해결 : 같은 트랜잭션이 항상 희생자로 선정되지 않도록 희생자 선정시 롤백 횟수를 고려