[데이터베이스] #13. 동시성 제어

bien·2023년 5월 28일

데이터베이스

목록 보기

11/17

01. 락 기반 규약

락 기반 규약의 개념

동시성 제어의 개념

트랜잭션 직렬화와 회복화는 스케줄이 데이터 일관성에 영향을 미치는 여부를 판별하고, 일관성이 유지되는 상태로 복원시키기 위해 정의한 개념
- 직렬성 유무 = 결과의 일관성 훼손 여부 판단가능
- 회복화 = 원자성 회복 가능 여부 판단 가능
  DBMS는 스케줄을 직렬화와 회복화가 유지되는 상태로 스케줄을 만들어야만 결과의 일관성, 원자성 유지 가능하다!
일관성 훼손을 발생시키는 트랜잭션에 대해 동시성 제어를 통해 일관성 유지에 개입
- 틀랜잭션 간 연산의 순서를 제어
- 어떠한 데이터 읽기, 갱신 연사에도 무결성을 유지
- 동시에 실행되는 트랜잭션 수를 증가
동시성 제어 규약

(우리는 앞의 두개만 살펴볼 것!)

락 기반 규약의 개념

직렬 가능성을 보장하기 위해 락(장금)을 사용하여 데이터 항목에 연산 작용 전 트랜잭션이 락을 획득하고 연산 후 반납하도록 하는 규약
지금 이거 내가 찜뽕햇으니까, 아무도 쓰지마!!!!!!! =락
락의 종류
- 공유락(shared lock, S): 트랜잭션 T가 LS(Q)명령으로 데이터 항목 Q에 공유 락을 획득하면 T는 Q를 읽을수는 있지만 쓸수는 없는 락
  주로 읽기 락에 사용한다
- 배타락(exclusive lock, X): 트랜잭션T가 LX(Q)명령으로 데이터항목 Q에 대한 배타 락을 획득하면, T가 Q를 읽고 쓸 수 있는 락
  읽기도 하고, 쓰기도 할때 사용한다

락 양립성

트랜잭션은 연산하고자 하는 데이터에 대한 락을 획득해야만 연산 진행 가능
반드시 선 락을 걸고 후처리 한다
락 양립성 함수
- 공유 락은 다른 공유 락과 양립 가능
- 배타 락과 다른 락과 양립 불가능
- 배타 락의 요청은 공유 락이 반납될 때 까지 대기
- 락의 반납은 UN() 명령 사용

공유락은 무조건 같이 사용 가능. 배타락은 무조건 같이 사용 불가능.
이미 락이 걸린 경우에는, 무조건 락이 끝날때까지 대기.

예제 트랜잭션

T10은 계좌 B에서 A로 천원을 이체하는 트랜잭션.
Write(B)를 위해 LX(B) 배타락을 미리 걸어놓음.

T11은 두 계좌의 값을 읽어서 출력하는 트랜잭션.
write없이 Read작업만 있어 LS(A) 공유락만 걸어 놓음.

동시 실행 스케줄

이 두 트랜잭션이 동시에 요청되면 어떤 현상이 일어날까?

B에는 2만원, A에는 1만원이 있는 상황. 일련의 연산이 수행진다.
락을 정상적으로 사용했음에도 불구하고, T10의 계좌요청 사이에 T11이 끼어들어 일관성이 훼손된다.

T10이 락을 일찍 반납하여 비일관적인 상태에서 데이터 접근이 가능해저 T11이 정확하지 않은 결과값을 출력

락 반납이 지연된 트랜잭션

이전 버전

일찍 안하고 락을 늦게 반납하면 되지 않을까?

이전과 달리 락 반납을 지연시켰다. 쓰고나서 바로 UN하지 않고, UN의 부분은 모두 뒤로 밀려났다.

락 반납 지연의 문제

이 스케줄은 정상적으로 작동할까?

T13에서 LS(B)를 실행할 수 있을까? 이미 T12에서 배타락 LX(B)을 건 상태이므로, 공유락과 배타락은 양립될 수 없기에 T13는 대기하게 된다. T13이 유지되고 있는 상태에서 T12가 A라는 데이터에 배타락(LX(A))을 요청한다. 그러나 이미 A데이터는 T13에 공유락(LS(A))되어 있는 상태다. 그래서 T12도 대기 상태가 된다. T12, T13이 서로의 요청이 끝날때까지 기다리고 있는 상황인 것이다. 이를 교착상태라 하며 롤백 없이는 영원히 유지된다.

T12, T13에 대한 부분 스케줄
- T12이 B에 대한 배타 락을 반환할 때까지 T13은 대기
- T13이 A에 대한 공유 락을 반환할 때까지 T12는 대기

교착상태(deadlock)

두 트랜잭션 중 하나를 롤백

한 트랜잭션이 롤백되면 그 트랜잭션이 획득했던 모든 락은 반납

2단계 락킹 규약

락을 일찍 반납하면 일관성이 훼손되고, 락을 늦게 반납하면 교착상태에 부딫힌다. 이를 해소하기 위해 이른 반납과 지연 반납 사이의 규약.

트랜잭션은 락을 요청, 반납하는 두 단계로 구성
- 확장 단계: 락을 얻을 수 있으나 반납할 수 없는 단계
- 축소 단계: 락을 반납할 수는 있지만 새로운 락을 얻을 수 없는 단계
  트랜잭션은 확장단계로 시작하고, 어느 시점부터 축소단계로 전환되어 반납만 가능하게 한다.

하나의 트랜잭션이 연산을 수행하면서 필요한 데이터에 관한 락을 획득하기만 하다가, 하나의 데이터에 대한 반납이 이루어지는 순간부터 축소단계로 이루어져 반납만 가능하게 된다.
굉장히 유명한 락킹규약. 2PL(Two-Phase Locking Protocol)이라고도 부른다.

직렬성을 보장하나 교착상태 예방 불가.

02. 타임스탬프 기반 규약

타임스탬프 순서 규약의 개념

타임스탬프 기반 규약의 개념

각 트랜잭션 Ti 실행의 순서를 판단하기 위해 타임스탬프 TS(Ti)를 부여
타임스탬프: 시간 보장. 언제 어떤 이벤트가 밸생했음을 명시할 때 타임스탬프를 사용한다. 어떤 트랜잭션이 DBMS에 진입하여 시행요청할 때, 그 시간을 타임스태프라 부름
데이터 항목에 대한 타임스탬프 할당

트랜잭션 뿐 아니라 사용되는 데이터에게도 타임스탬프라 부여된다. Ti가 어떤 데이터 Q에 대해 쓰기작업을 수행하면 W-TS(Q)는 Ti의의 Ts로 같이 결정된다. 이 중에서 가장 마지막에 수행했던 타임스탬프를 WTS라고 한다.

타임스탬프 할당 방법
타임스탬프를 뭘로 사용할 것인가?
- 시스템 클럭 값
  운영체제 내부에 있는 명령어 계수기 사용. 일반적으로 많이 사용한다.
- 논리적 계수기
  값이 하나씩 증가되는 변수 마련하여 들어올 때 타임스탬프 값을 가져와 1씩 증가시켜 사용.

타임스탬프 순서 규약: 먼저 들어온 트랜잭션(타임스탬프가 작은)은 먼저 수행되도록 함으로써 직렬성 확보

𝑇𝑖가 Read(Q)를 수행할 때

Ti가 시작되고 나중에 Tj가 시행됨. Ti가 값을 작성해 Q값이 변경될 예정인데 그 전에 Tj가 Q를 읽어버림. 잘못된 값을 읽은 상태.
이런 경우를 고려하여, TS(Ti)와 W-TS(Q)를 비교해 롤백하거나 연산을 수행한다.
읽으려는 시간보다 최종 작성(쓰기) 시간이 최신이면 롤백 수행
내가 읽은 값을 누가 수정하려고 하면 롤백

TS(Ti) < W-TS(Q)이면 Read 연산이 거부되고 Ti는 롤백
TS(Ti) >= W-TS(Q)이면 Read 연산이 수행되고 R-TS(Q)는 기존 R-TS(Q)와 TS(Ti) 중 최대값으로 설정

TS(Ti)=내가 읽으려고 함. W-TS(Q) =누가 Q를 덮어씀.
TS(Ti) < W-TS(Q): 내가 이미 읽었는데 누가 그거 수정함 => 문제됨
TS(Ti) >= W-TS(Q): 누가 수정먼저하고 나서 내가 읽음 =>문제 안됨

𝑇𝑖가 Write(Q)를 수행할 때

Ti의 값이 최종적으로 작성되어 Tj가 입력한 값은 무시되고 Ti의 값만 남게됨.
내가 쓰려는 시간보다 최종 읽기,쓰기 시간이 더 최신이면 롤백 수행
내가 쓰려는 값을 이미 누가 읽거나 썼으면 롤백

TS(Ti) < R-TS(Q) 또는 TS(Ti) < W-TS(Q)이면 Write 연산이 거부되고 Ti는 롤백
그렇지 않으면 Write 연산을 수행하고 W-TS(Q)는 TS(Ti)로 설정

타임스탬프 순서 규약의 적용

1. TS(T14) < TS(T15)

< 만들어진 스케쥴 >

이 스케쥴은 정상적으로 작동 될까?

T15의 Read(B)

T14가 B를 Read했으나, Read는 문제가 되지 않는다.

T15의 Write(B)

B에 대한 R-TS값, W-TS값을 따져봐야 함.
모두 자기보다 작은 상태.
따라서 Write(B) 작동 가능.

T14의 Read(A)

어디에도 Read(A)한적 없음. = A에대한 R-TS, W-TS는 초기화되어 있는 상태
Read(A)하면서 T14의 타임스탬프 값이 A의 R-TS값으로 셋팅.

T15의 Read(A)

Read와 Read끼리는 문제없이 연산 가능

T15의 Write(A)

A에 대한 R-TS값, W-TS값을 따져봐야 함.
모두 자기보다 작음 = 먼저 들어왔음.
여기서써도 문제없다.

=> 일관성 손상없이 정상 작동 가능한 스케줄!

토마스 기록 규칙

토마스라는 연구자가 타임스탬프 규약에 개선점을 제시함.

TS(Ti) < R-TS(Q)이면 Write 연산이 거부되고 Ti는 롤백. (동일)
TS(Ti) < W-TS(Q)이면 Write 연산은 거부된다. (차이점. 원래는 롤백까지 했었다.)
그렇지 않으면 Write 연산을 수행하고 W-TS(Q)는 TS(Ti)로 설정

나보다 나중에 실행된 트랜잭션에서의 쓰기값은, 최종결과가 나보다 나중에 실행된 트랜잭션의 값으로 남는게 옳기때문에, 굳이 값을 쓰지 않더라도 문제 없다. 즉, 굳이 롤백하지 않고 쓰기값만 무시하고 Ti는 처리하는 것이 맞다.
롤백 자체가 DBMS에게는 큰 부담을 주는 연산이므로, 이 롤백의 연산을 줄여줌으로써 DBMS의 성능 개선이 가능하다.

~~뮈치겠다. 너무 헷갈린다.~~

03. 교착 상태

교착상태(deadlock)의 개념

특정 트랜잭션 집합 내에 속하는 모든 태랜잭션이 집합 내의 다른 트랜잭션을 기다리고 있는 상태
A가 B를 기다림. B가 C를 기다림. C가 A를 기다림. 셋이서 서로 물고 물면서 영원히 대기만함.

해결방법: 두 트랜잭션 중 하나를 반드시 롤백

교착상태 방지

교착상태 처리 방법

교착상태 발생이 비교적 높은 시스템의 경우
- 교착 상태 방지 규약 사용
  - 모든 데이터항목에 대해 락을 설정하는 방법 (트랜잭션 시작 전에 자기가 사용하는 데이터 A,B,C의 락을 모두 확보해야만 트랜잭션을 시작하도록 설정)
  - 단점1: 트랜잭션이 시작되기 전에 어떤 데이터에 락을 걸어야할지 미리 알기가 어려움
  - 단점2: 락이 걸린 상태에서 많은 데이터들이 오랫동안 사용되지 않아 데이터 항목에 대한 이용률이 매우 낮아짐 (데이터항목 자원이용률 매우 떨어짐)
  - 타임스탬프를 이용한 선점유 기법
  이 애플리케이션 자체가 이상하게 교착상태가 많이 나타나는 경우, 그냥 처음부터 교착상태 방지 규약을 사용해버린다. 교착상태 유발 하는지 연산 수행마다 판단해 교착상태 유발시 중간에 실패를 만들업러림.
교착상태 발생이 비교적 높지 않은 시스템의 경우
- 교착상태 탐지와 회복 기법 사용
  - 대기 그래프
  - 희생자 선정

교착상태가 드물게 생김. 미리 교차상태 장지 규약으로 DBMS 성능을 떨구는것보다, 일단 맘대로 처리해, 발생하면 롤백할게!하는 것이 더 낫다. 교착상태를 트랜잭션이 DBMS에 보고하지 않고, DBMS가 알고리즘으로 교착상태 발생 여부를 탐지함. 회복은 일정 트랜잭션을 롤백시키는 것을 말함

교착상태 방지

타임스탬프를 이용
- Tj가 락을 소유한 데이터 항목을 Ti가 요청하는 상황

wait-die기법(비선점유 기반): TS(Ti) < TS(Tj)일 때 Ti가 기다리고 그렇지 않으면 Ti를 롤백.
(Ti가 먼저 시행됐으면 Ti가 Tj가 락을 반납할 때까지 기다린다. Ti가 나중에 시행됐으면 롤백한다.)

선점유: 특정 값에 의해 우선순위를 매겨두고 우선순위로 먼저 작업이 처리되도록 함. 비선점유: 우선순위로 작업순위를 매기지 않음.

wait	die

T18 = 대기	T20 = 롤백

wound-wait 기법(선점유 기반): TS(Tj) < TS(Ti)일 때 Ti가 기다리고 그렇지 않으면 Tj를 롤백.
선점유기법으로 타임스탬프를 특정 우선순위로 둔다. 타임스탬프가 더 낮은것은 먼저 실행되었기 때문에, 먼저 락을 요구할 권리가 있다고 본다. 나중에 실행된 트랜잭션은 먼저 실행된 트랜잭션의 락을 요구하는 경우는 기다린다

wound	wait

T18은 바로 Q에 대한 락을 획득하고, T19는 락을 해제하고 롤백한다.	T20은 T19가 락을 해제할때까지 대기한다.
(우선순위가 T18 > T19이므로)	(우선순위가 T19 > T20이므로)

교착상태의 회복

교착상태 탐지와 회복

교착상태 발생이 비교적 높지 않은 시스템의 경우 주기적으로 교착 상태를 탐지하고 발생 시 회복 절차를 수행
탐지 및 회복 절차
- 트랜잭션이 할당된 데이터 항목과 현재 요청되고 있는 데이터 항목에 대한 정보를 유지
- 교착상태가 발생여부를 판별하기 위해 시스템의 상태를 검사하는 알고리즘을 주기적으로 시행
- 교착상태가 검출되면 시스템은 교착상태로부터 회복을 위한 절차를 수행

어떤 트랜잭션이 어떤 데이터항목을 가지고 있는지 정보를 쭉 가지고 있다가, 교착상태 판별 알고리즘을 주기적으로 돌려서, 발생 발견시 해결

교착상태 탐지

대기 그래프(wait-for graph)를 이용하여 확인
- 정점 V는 시스탬 내의 트랜잭션으로 구성되며
- 간선 E는 트랜잭션의순서쌍(Ti, Tj)으로 이루어짐
  - Ti가 요청한 데이터의 락을 Tj가 소유하고 있으며, Ti는 Tj가 락을 반납하기 대기하는 상태
대기 그래프에 사이클이 있다면 교착 상태가 발생

교착상태 X	교착상태 O

교착상태 아님. T15가 끝나기만 대기하면 됨.	서로 물고 물리는 순환 관계(사이클)가 생김.

교착상태의 회복

회복은 어떻게 할까? 롤백을 해야만 회복이 가능하다. 롤백을 수행하는 대상자를 희생자라고 이야기한다. 롤백 대상은 어떻게 선정할까? 아무나 선정하면 될까? 그렇지 않다. 롤백을 가장 빨리 할 수 있도록, 트랜잭션 시행 사태가 가장 짧은 트랜잭션이 좋지 않을까?

희생자 선정: 롤백 비용이 가장 적은 트랜잭션을 선택
- 연산을 수행한 시간과 남은 작업을 마치기 위한 시간
  (지금까지 시행한 시간 + 앞으로 시행해야 할 시간. 이때까지 수행을 30분했는데, 앞으로 2시간 더할거야. 이럼 롤백하는 편이 나을수도 있음)
- 사용한 데이터와 트랜잭션 실행에 필요한 추가적인 데이터
  _(이미 너무 많은 데이터 확보했고, 앞으로 조금만 더 확보하면 됨. 이런 트랜잭션을 희생하는 것 보다 아직 조금 획득했고 할 양이 많이 남은 트랜잭션을 희생자로 선택하는 편이 나음)
- 롤백에 포함되는 트랜잭션의 개수
  _(12345 5개의 트랜잭션이 롤백에 빠졌는데, 1,2,3 회복보다 4,5 롤백하면 트랜잭션의 수가 작으므로 롤백의 수가 작아진다.)
희생자 롤백: 어느 시점까지 롤백 할 것인지 결정
- 전체 롤백 VS. 고착 상태를 해결하는 지점(세이브 포인트)
- 모든 트랜잭션의 상태에 대한 정보를 부가적으로 유지
무한정 기다림 해결
- 같은 트랜잭션이 항상 희생자로 선정되지 않도록 희생자 선정시 롤백 횟수를 고려
  13,14,15가 교착상태에 처해서 13이 희생자로 선정됐음. 그런데 13,16,17이 또 교착상태에 처함. 근데 이번에 또 13이 희생자로 선정됨. 이런 방식으로 13이 계속 희생자로 선정되는 것을 무한정 기다림이라고 함. 이럼 롤백횟수에 불균형이 있을 수 있으므로, 롤백횟수도 희생자선정의 기준으로 넣을 수 있음

bien

Good Luck!

이전 포스트

[데이터베이스] #12. 트랜잭션

다음 포스트

[데이터베이스] #13. 동시성 제어