동시성 제어(락킹, 교착 상태, 타임스탬프)

# 동시성 제어 기법(concurrency-control scheme)
- 스케줄이 충동, 뷰 직렬적, 복구 가능, 비연쇄적임을 보장하면서 높은 수준의 동시성을 제공
- 데이터베이스의 일관성 보존을 위해 트랜잭션들 간의 상호 작용 제어
- 직렬성 보장 위함
- 가장 핵심(만들기 어려움) DBMS는 일관성 유지, 보존, 보장해야 함
- 성능 좋으면 정확성 나쁨, 성능 나쁘면 정확성 좋음
- 연산을 지연하거나 트랜잭션을 롤백시킴
- 락킹 규약, 타임스탬프 순서화 기법, 검증 기법, 다중 버전 기법

 

# 락 기반의 규약 (lock-based protocols) : 충돌 직렬성 구현
- 고립성 보장
- 데이터 항목들이 상호 배타적으로 액세스
- 공유하는 데이터 아이템에 대한 락 검
- 트랜잭션이 데이터 항목을 액세스하고자 한다면 반드시 그 항목에 자신의 락을 걸어야 함

1. 독점적 락 모드 (exclusive (X) mode)
- 트랜잭션은 읽을 수 있고 쓸 수 있음
- lock-X
- 하나의 트랜잭션이 lock-X 쥐고 있으면 어떤 트랜잭션도 lock-X, S 못 얻음

2. 공유 락 모드 (shared (S) mode)
- 트랜잭션은 읽을 수 있고 쓸 순 없음
- lock-S
- 공유 락 얻으려면 다른 공유 락들에 대해 나의 락이 호환되어야 함
- 여러 트랜잭션들이 동시에 얻을 수 있음

- 동시성 제어 관리자한테 락 요청 보냄
- 허용하면 연산 진행
- 대답 없으면 비호환적인 락이 해제될 때까지 대기 상태로 존재

 

 

# 락 호환성 행렬(lock-compatibility matrix)

- 모든 공유 락은 다른 공유 락들과 호환되지만 독점적 락과는 호환되지 않음
- 독점적 락을 걸기 위해서 모든 공유 락 해제될 때까지 기다림

 

# 락 명령어
- lock-S(Q) : 공유 락 요청
- lock-X(Q) : 독점적 락 요청
- unlock(Q) : 락 해제

 

 

# 직렬성 보장 안 되는 경우

- 트랜잭션이 데이터 항목을 액세스 한 다음 바로 락을 해제하는 것이 바람직하지 못한 경우
- T1이 B를 너무 일찍 락 해제해서 T2가 비일관성 상태의 데이터를 액세스함
- T2가 A+B를 250 이라고 보여줌(원래는 300)
- 락 해제 트랜잭션의 마지막에 해야 함

 

 

# 락 기반 규약 함정
1) 교착 상태 (deadlock)

- 서로 맞물려서 있음
- 자신들이 요청한 락이 얻어질 때까지 기다림
- 정상적인 수행 못함
- 두 트랜잭션 중의 하나를 취소시켜야 함
- 다른 데이터 항목에 락을 요청하기 전에 자신이 가진 락을 해제하지 않으면 발생
- 비일관성 상태보다 나음(트랜잭션 취소 후 다시 시작 가능)

2) 기아 (starvation)
- 희생자(victim) 선정
- 계속 혼자만 손해 봄(T1,2가 공유 락을 해제하길 기다리는 T3(독점적 락 요청)이 T4, T5가 공유 락 요청하면 계속 독점적 락 허용 못 받음)
< 기아 회피 방법 >
Ti가 특정 모드 M으로 데이터 항목 Q에 락을 요청할 경우 동시성 제어 관리자는 두 경우에만 락 허용
1. M과 충돌되는 락 모드로 Q에 락을 걸고 있는 다른 트랜잭션들이 없음
2. Ti보다 먼저 Q에 락을 요청해서 기다리고 있는 트랜잭션이 없음

 

# 2단계 락킹 규약 (two-phase locking protocol)
- 트랜잭션이 데이터 항목에 언제 락을 걸고 해제할 수 있는지 알려줌
- 트랜잭션들의 실행 스케줄의 수를 제한함
- 락킹 규약의 규칙을 따르는 일련의 트랙잭션들의 스케줄이면 S는 정당함
- 두 단계는 절대 안 겹침(락을 해제하지 않을 때만 락 요청)
- 순차적 스케줄과 충돌 동등하면 충돌 직렬적
- 교착상태 피할 수 없음
- 연쇄적 롤백 발생(카밋되지 않은 값 읽도록 해서 발생) => strict 2PL으로 방지
- unlock 명령문이 트랜잭션의 끝에 있을 필요는 없음(2단계 락 특성만 가지면 됨)
- 락 지점 (lock point) : 마지막 락 얻는 부분. 직렬성 순서(직렬성 보장)
1. 증가 단계 (growing phase) : 트랜잭션의 처음
- 트랜잭션이 락을 얻을 수 있으나 락을 해제할 수는 없음

2. 감소 단계 (shrinking phase)
- 트랜잭션이 락을 해제할 수 있으나 락을 얻을 수는 없음

- 락 변환 (lock conversion) 가능한 형태로 수정할 필요 있음
- upgrade : 공유 락을 독점적 락으로 올림 (증가 단계에서만 가능)
- downgrade : 독점적 락을 공유 락으로 낮춤 (감소 단계에서만 가능)
- 독점적 락 가진 트랜잭션이 끝날 때까지 스케줄은 연쇄성 없음

 

 

# strict 2단계 락킹 규약
- lock-X를 트랜잭션이 commit이나 abort로 종료할 때까지 다른 트랜잭션이 못 가져가도록 쥐고 있다가 종료되면 풀어줌
- 연쇄적 롤백 방지 => 비연쇄성 보장

 

# rigorous 2단계 락킹 규약
- lock-S, X를 트랜잭션이 commit이나 abort로 종료할 때까지 다른 트랜잭션이 못 가져가도록 쥐고 있다가 종료되면 풀어줌
- 직렬적인 트랜잭션과 동일
- 고립성 수준의 직렬적 단계

 

# 락 얻기
- 모든 락은 트랜잭션이 commit 이나 abort로 종료된 후 해제
1. read(Q)
- 한 트랜잭션이라도 lock-X(Q) 있으면 대기 => unlock 시키면 
- lock-S(Q) 허용되면 read(Q) 수행

2. write(Q)
1) Ti가 lock-X(Q)이면 write(Q) 실행
2) Ti가 lock-X(Q) 아니면 대기(다른 트랜잭션들이 lock-S(Q)이거나 Tj가 lock-X(Q)인 경우)
2-1) Tj가 lock-X(Q) 풀거나 다른 트랜잭션들이 lock-S(Q) 다 풀면 
=> lock-X(Q) 요청해서 허용되면 write(Q) 실행
2-2) 이미 Ti가 lock-S(Q)이면 upgrade(Q)해서 lock-X(Q)로 변경 

 

# 락킹의 구현
- 락 관리자는 요청 메시지를 받고 응답 메시지를 트랜잭션으로 보냄
- grant 메시지만 가고 waiting 메시지는 안 보냄
- 트랜잭션 취소 요청 메시지 보냄(교착 상태인 경우)
- 접수되는 순서대로 데이터 항목의 연결 리스트를 유지
- 데이터 항목의 이름을 기반으로 인덱스 된 해시 테이블 사용 => 락 테이블

 

# 락 테이블
- 크기 작아서 메인 메모리가 커버 가능
- 해시 이용
- 오버플로우 사슬 사용

 

 

# 락 관리자 프로세스

1. 락 요청 메시지 들어오면
1-1) 락이 걸릴 데이터 항목의 연결 리스트가 이미 존재할 경우
     => 그 연결 리스트에 레코드 하나 추가한 후 
     1-1-1) 호환되고, 모든 이전 요청들이 이미 허용되었을 경우 요청 허용
     1-1-2) 이외의 경우에는 요청은 대기 상태로
1-2) 존재하지 않을 경우
     => 요청한 락의 레코드만 가지는 새로운 연결 리스트 생성한 후 락 요청을 허용

2. 락 해제 요청 메시지 받으면
2-1) 연결 리스트에서 데이터 항목의 레코드 삭제
2-2) 삭제된 레코드 바로 뒤에 레코드 있으면 그 레코드의 락 요청이 허용될 수 있는지 아닌지를 테스트한 후 허용될 수 있으면 락 요청 허용(다음 레코드에도 유사하게 처리)

3. 트랜잭션이 취소되면
3-1) 그 트랜잭션에서 요청하여 대기 중인 모든 락 요청을 취소
3-2) 그 트랜잭션에 의해 걸려있던 모든 락 해제

 

# 교착 상태 처리
- 트랜잭션을 롤백 시킴
1. 교착 상태 예방
- 시스템이 교착 상태에 빠지지 않도록 보장
- 시스템이 교착 상태에 빠질 확률이 상대적으로 높을 때 사용
1-1) 락 요청 순서에 사이클이 일어나지 않도록 함(사이클 있으면 교착 상태)
1-2) 그렇지 않은 경우 필요한 락을 한꺼번에 요청
     => 트랜잭션 시작 전 어떤 데이터 항목에 락이 걸려야 하는지 알기 어려움
     => 데이터 항목의 이용률 떨어짐
1-3) 락을 대기하도록 하는 대신 트랜잭션을 롤백시킴
     => 데이터 항목에 순서를 매긴 다음 트랜잭션이 이 순서와 동일하게 락 요청

 

 

# 타임스탬프 사용한 교착 상태 예방 기법
1) 대기-롤백 (wait-die)
- 비선점 기법
- older tx가 충돌시키면 그 트랜잭션 대기 상태
- younger tx이 충돌시키면 그 트랜잭션 죽임(롤백)
- older tx (먼저 시작한 트랜잭션)
- younger tx (나중에 시작한 트랜잭션)

2) 롤백-대기 (wound-wait)
- 선점 기법(락의 강제로 뺏음)
- older tx는 그대로 실행
- younger tx에 피해 줌
- older tx가 충돌시키면 younger tx 죽임
- younger tx가 충돌시키면 younger tx 대기 상태


# timeout-based schemes
- 복잡. 사이클 체크 어려움 => 타임아웃 정해줌
- 가만히 있으면 죽임
- 최대로 지정한 시간만큼만 대기한 후 롤백
- 트랜잭션들이 짧을 때, 교착 상태에 의해 대기시간이 길 때 유용
- 기아 현상 발생 가능

 

 

2. 교착 상태 탐지
- 시스템이 교착 상태에 빠질 수 있지만 탐지 복구 이용
- 시스템이 교착 상태에 빠질 확률이 상대적으로 높지 않을 때 사용
- 시스템적으로 부담
- 사이클 하나 죽임

 

# wait-for graph (대기 그래프)

예 ) T17이 T18,19의 데이터 항목 대기
- 사이클 있으면 교착 상태 발생

 

# 교착 상태로부터의 복구
1. 희생자 선택 : 최소 비용 드는 트랜잭션 롤백(했던 일의 양 적은 것 선택)
2. 롤백 – 전체 롤백(시작~끝) or 부분 롤백(교착 상태 풀 수 있는 시점까지 롤백)
3. 기아 => 희생자로 선택되는 횟수 제한

 

# 다중 세분도 (multiple granularity) : 락의 굵기
- 그룹화한 다음 그룹 단위로 동기화
- 락 크게, 작게 잡을 수 있음
- 명시적인 락 (explicit lock) : 파일에 걸면 그 파일의 모든 레코드들에 암묵적인 락 걸림
- 암묵적인 락 (implicit lock)
- fine granularity : 락의 크기 작음. 트리의 밑(file-table-record)
- coarse granularity : 락의 크기 큼. 트리의 위(오버헤드 큼, 동시성 레벨 큼, 충돌 적어짐)
- 락을 어느 단위에서 걸 것인지
- 프로토콜 복잡

 

# 타임스탬프 기반의 규약 : 뷰 직렬성 구현
- 지금은 많지 않음
- 언제 시작했는지 찍어줌
- Ti가 Tj보다 먼저 시작했으면 ts(Ti) < ts(Tj)
- 모든 데이터마다 W-timestamp, R-timestamp 찍어줌
- W-timestamp(Q) : write(Q) 연산을 수행한 트랜잭션들의 타임스탬프 중 가장 큰 것
- R-timestamp(Q) : read(Q) 연산을 수행한 트랜잭션들의 타임스탬프 중 가장 큰 것

 

 

# 타임스탬프 순서 규약
1. Ti가 read(Q) 하려 하는 경우

W-ts(Q) 봄 : write(Q) 한 트랜잭션이 Ti 시작 전에 시작되고 write까지 한 경우 읽기 가능

1-1) ts(Ti) < W-ts(Q) 이면 read(Q) 연산 실행 안되고 롤백됨

1-2) W-ts(Q) <= ts(Ti) 이면 read(Q) 연산 실행되고 R-ts(Q)는 R-ts(Q)와 ts(Ti) 중 큰 값으로 설정됨

 

2. Ti가 write(Q) 하려 하는 경우

2-1) ts(Ti) < R-ts(Q) 이면 write(Q) 연산 실행 안되고 롤백됨

2-2) ts(Ti) < W-ts(Q) 이면 write(Q) 연산 실행 안되고 롤백됨

2-3) 이외의 경우에는 write(Q) 연산 실행하고 W-ts(Q)를 ts(Ti)로 설정

나보다 먼저 시작한 트랜잭션이 read나 write 하면 write 함

스케줄은 트랜잭션의 시작 순서ts(Ti) < ts(Tj) < ts(Tk) 순차적인 스케줄과 뷰 동등함

=> 일관성 보장

 

 

# 다중 버전 기법

- 다중 버전 동시성 제어 기법에는 각 write(Q) 연산이 Q의 새로운 버전 만듦(복사본)

- 직렬성을 보장

- Ti에 ts(Ti)로 표기되는 하나의 유일한 정적 타임스탬프 부여

- 트랜잭션 실행 시작 전 타임스탬프 부여

 

< 데이터 필드 >

1) Content : 버전 Qk가 가지는 값. Ti에 의해 기록된 값 보관

2) W-timestamp(Qk) : 버전 Qk가 만든 트랜잭션에게 부여된 타임스탬프

3) R-timestamp(Qk) : 버전 Qk의 값을 성공적으로 읽은 트랜잭션의 타임스탬프 중 가장 큰 스탬프

R-ts(Q) < ts(Ti) 이면 언제든 R-ts(Q) 값 변경

 

 

# 다중 버전 타임스탬프 순서화 기법(multiversion timestamp-ordering scheme)

- 직렬성 보장

- Qk는 Q의 버전 중 ts(Ti) 보다 작거나 같은 W-ts(Q)중 가장 큰 값을 가지는 버전

- 읽기 연산할 때 R-ts()R-ts() 값 변경해야 하므로 두 번의 디스크 액세스 필요

- 트랜잭션들 간의 충돌을 트랜잭션을 대기시킴으로써 해결 못하고, 롤백시킴으로써 해결

- 복구 성과 비연쇄성 보장 안 함

 

1) Ti가 read(Q) 실행할 경우

버전 Qk의 content 필드에 있는 값

2) Ti가 wirte(Q) 실행하고

2-1) ts(Ti) < R-ts(Q) 라면 Ti는 롤백됨

2-2) ts(Ti) == R-ts(Q) 이면 Qk의 값 덮어씀

2-3) 이외의 경우는 Q의 새로운 버전 만듦

 

 

# 다중 버전 2단계 락킹

- 다중 버전 동시성 제어의 장점과 2단계 락킹의 장점 결합

- 갱신 트랜잭션은 rigorous 2단계 락킹 수행 (카밋되기 전까지 모든 락 쥐고 있음)

=> 직렬화. 데이터 항목의 각 버전은 하나의 타임스탬프 가짐. ts-counter(논리적 카운터)

     이 카운터는 카밋을 처리하는 동안 값이 증가됨

- ts-counter의 현재 값을 읽어 읽기 전용 트랜잭션이 실행 전에 타임스탬프 할당

- 읽기 연산을 수행하는 데에 타임스탬프 순서화 규약 사용

- 갱신 트랜잭션이 값을 읽을 때 먼저 그 항목에 공유 락을 걸고 가장 큰 버전의 값 읽음

- 갱신 트랜잭션이 값을 기록할 때 독점적 락 걸고 그 데이터 항목의 새로운 버전 생성

- 이 버전에 값을 기록하고 이 버전의 초기 스탬프를 무한대로 지정함으로써 가장 크게 함

- 갱신 트랜잭션이 끝날 때는 카밋 처리 수행

- Ti는 자신이 만든 모든 버전의 타임스탬프를 ts-counter의 값보다 하나 큰 값으로 지정

- ts-counter값을 1 증가 시킴 (한 번에 오직 하나의 갱신 트랜잭션만 카밋 처리)

- 값을 증가시킨 후에 시작되는 읽기 전용 트랜잭션들은 Ti가 변경한 값 읽음

- 값을 증가하기 전에 시작되는 읽기 전용 트랜잭션들은 갱신 전 값 읽음

- 어떤 경우든 락을 걸기 위해 대기할 필요 없음

- 스케줄 복구 가능하고 비연쇄적임

- 버전들은 다중 버전 타임스탬프 순서화와 같이 삭제됨

- 한 데이터 항목의 두 버전 Qk와 Qj, 오래된 트랜잭션의 타임스탬프보다 작거나 같은 타임스탬프 가지면 Qk와 Qj보다 - 더 오래된 버전은 사용되지 않으므로 삭제됨