[DB]동시성 제어

📚동시성 제어

트랜잭션 직렬화와 회복하는 스케줄이 데이터 일관성에 영향을 미치는 여부를 판별하고 일관성이 유지되는 상태로 복원시키기 위해 정의한 개념입니다.

일관성 훼손을 발생시키는 트랜잭션에 대해 동시성 제어를 통해 일관성 유지에 개입합니다.

동시성 제어는 트랜잭션 간 연산의 순서를 제어하여 어떠한 데이터 읽기, 갱신 연산에도 무결성을 유지하면서도 동시에 실행되는 트랜잭션 수를 증가시킬 수 있는 기법을 말합니다.

• 동시성 제어 규약
  • 락기반 규약
  • 타임스탬프 규약
  • 검증 기반 규약

📚락 기반 규약

직렬 가능성을 보장하기 위해 락을 사용하여 데이터 항목에 연산 적용 전 트랜잭션이 락을 획득하고 연산 후 반납하도록 하는 규약입니다.

• 락의 종류
  • 공유 락(S): 트랜잭션 T가 LS(Q) 명령으로 데이터 항목 Q에 공유 락을 획득하면, T가 Q를 읽을 수는 있지만 쓸 수 없는 락
  • 배타 락(X): 트랜잭션 T가 LX(Q) 명령으로 데이터 항목 Q에 대한 배타 락을 획득하면, T가 Q를 읽고 쓸 수 있는 락

📄락 양립성

트랜잭션은 연산하고자 하는 데이터에 대한 락을 획득해야만 연산 진행이 가능합니다.

	공유 락(S)	배타 락(X)
공유 락(S)	가능	불가능
배타 락(X)	불가능	불가능

• 공유 락은 다른 공유 락과 양립 가능
• 배타 락은 다른 락과 양립 불가능
• 배타 락의 요청은 공유 락이 반납될 때까지 대기
• 락의 반납은 UN() 명령 사용

📄동시 실행 스케줄

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

• 락 반납이 지연된 스케줄
  T₁₂가 B에 대한 배타 락을 반환할 때까지 T₁₃은 대기하고 T₁₃이 A에 대한 공유 락을 반환할 때까지 T₁₂는 대기하는 상태입니다. 공유 락이 걸려있는 상태에서 배타 락은 양립할 수 없어 두 트랜잭션은 모두 대기 상태에 머물러 있습니다. 정상적인 실행이 불가능한 교착상태가 발생하여 더 이상 진행이 불가능하여 두 트랜잭션 중 하나를 롤백시켜야 합니다. 트랙잭션이 롤백되면 그 트랜잭션이 획득했던 모든 락은 반납됩니다.

📄2단계 락킹 규약

직렬성을 보장하는 규약의 하나로 2단계 락킹 규약(2 Phase Locking Protocol)이 있습니다. 트랜잭션은 락을 요청, 반납하는 두 단계로 구성되어 있습니다.

• 확장 단계: 락을 얻을 수 있으나 반납할 수 없는 단계
• 축소 단계: 락을 반납할 수는 있지만 새로운 락을 얻을 수 없는 단계

트랙재션은 확장 단계부터 시작되며 락을 하나라도 반납을 하는 순간 축소 단계로 전환됩니다. 2단계 락킹 규약은 직렬성을 보장하지만 교착상태는 예방할 수 없습니다.

📄엄격한 2단계 락킹 규약

엄격한 2단계 락킹 규약은 트랜잭션이 모든 락을 유지하다가 커밋이 되거나 중단될 경우에만 락을 해지합니다.

• 트랜잭션 T가 Read(A) 연산을 수행하면 시스템은 해당 읽기 연산에 대하여 락을 설정한다.

• T가 Write(A) 연산을 수행하면 시스템은 T가 A에 공유 락을 보유하고 있는지 확인한다. 만약 T가 공유 락을 보유하고 있다면 공유 락을 배타 락으로 변환하고 공유 락을 보유하고 있지 않다면 바로 A에 대해 배타 락을 설정한다.

• T에 의하여 얻어진 모든 락은 해당 트랜잭션이 커밋되거나 중단되면 해지된다.

📚타임 스탬프 기반 규약

📄타임 스탬프 순서 규약

각 트랜잭션 T실행의 순서를 판단하기 위해 타임스탬프 TS(T)를 부여합니다.

• 데이터 항목에 대한 타임 스탬프 할당
  • W-TS(Q): Write(Q)를 성공적으로 실행한 트랜잭션 중 가장 큰 타임 스탬프
  • R-TS(Q): Read(Q)를 성공적으로 실행한 트랜잭션 중 가장 큰 타임 스탬프

• 타임 스탬프 할당 방법
  • 시스템 클럭: 트랜잭션의 타임스탬프를 그 트랜잭션의 시스템으로 들어올 때의 시스템 클럭 값으로 설정
  • 논리적 계수기: 새로운 타임스탬프가 발급될 때마다 증가되는 논리적 계수기의 값으로 설정

• 트랜잭션 T_i가 Read(Q)를 한다고 가정
  • TS(T_i) < W-TS(Q)이면 Read 연산은 거부되고 T_i는 롤백
  • TS(T_i) >= W-TS(Q)이면 Read 연산은 실행되고 R-TS(Q)는 기존 R-TS(Q)와 TS(Q) 중 더 큰 타임스탬프값으로 설정

• 트랜잭션 T_i가 Write(Q)를 한다고 가정
  • TS(T_i) < R-TS(Q) 또는 TS(T_i) < W-TS(Q)이면 Write 연산은 거부되고 T_i는 롤백
  • 위 두 경우가 아니면 Write 연산은 실행되고 W-TS(Q)는 TS(T_i) 값으로 설정

📄토마스 기록 규칙

토마스 기록 규칙은 타임스탬프 순서 규약을 일부 수정하여 더 높은 동시성을 제공하는 규칙입니다.

• TS(T_i) < R-TS(Q) 이면 Write 연산은 거부되고 T_i는 롤백
• TS(T_i) < W-TS(Q)이면 Write 연산은 거부(T_i는 롤백될 필요는 없다.)
• 위 두 경우가 아니면 Write 연산은 실행되고 W-TS(Q)는 TS(T_i) 값으로 설정

📚교착 상태

📄교착 상태의 개념

특정 트랜잭션 집합 내에 속하는 모든 트랜잭션이 집합 내의 다른 트랜잭션을 기다리고 있는 상태

https://www.geeksforgeeks.org/deadlock-in-dbms/

📄교착상태 방지

교착상태 발생이 비교적 높은 시스템의 경우 교착상태 방지 규약 사용

• 모든 데이터 항목에 대해 락을 설정하는 기법
  • 트랜잭션이 시작되기 전에 어떤 데이터에 락을 걸어야하는지 미리 알기 어려움
  • 락이 걸린 상태에서 많은 데이터들이 오랫동안 사용되지 않아 데이터 항목에 대한 이용률이 매우 낮아짐

• 타임스탬프를 이용한 선점유 기법
  • wait-die: 이 기법은 비선점유를 기반으로 합니다. T_j가 락을 소유한 데이터 항목을 T_i가 요청하는 상황에서 TS(T_i) < TS(T_j)일 때 T_i가 기다리고 그렇지 않은면 T_i를 롤백합니다.
    
    
  • wound-wait: 이 기법은 선점유를 기반으로 합니다. TS(T_j) < TS(T_i)일 때 T_i가 기다리고 그렇지 않은면 T_j를 롤백하고 락을 이양합니다.

📄교착상태 탐지 및 회복

교착상태 발생이 비교적 높지 않은 시스템의 경우 주기적으로 교착상태를 탐지하고 교착상태가 검출되면 회복 절차를 수행해야 합니다.

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

• 교착상태 탐지
  • 대기 그래프: 정점 V는 시스템 내의 트랜잭션으로 구성되고 간선 E는 트랜잭션의 순서쌍 (T_i, T_j)으로 구성됩니다. T_i가 요청한 데이터의 락을 T_j가 소유하고 있으며 T_i는 T_j가 락을 반납하기를 기다리고 있는 상태로 대기 그래프에 사이클이 있다면 교착상태가 발생합니다.

• 교착상태 회복
  • 희생자 선정: 롤백 비용이 가장 적은 트랜잭션을 선택하여 롤백시키는 방법입니다. 롤백 비용을 결정하는 요소는 다음과 같습니다.
    • 연산을 수행한 시간과 남은 작업을 마치기 위한 시간
    • 사용한 데이터와 트랜잭션 실해에 필요한 추가적인 데이터
    • 롤백에 포함된 트랜잭션 개수
      
      
  • 희생자 롤백: 어느 시점까지 롤백할 것인지 결정해야 합니다. 가장 간단한 방법은 전체 롤백이 있습니다. 전체 트랜잭션을 중단하고 다시 시작한다는 의미입니다. 교착상태를 해결하는 데 필요한 시점까지만 트랜잭션을 롤백시키는 것이 효율적입니다. 하지만 이 방법은 시스템이 현재 실행되고 있는 모든 트랜잭션의 상태에 대한 정보를 부가적으로 유지해야하는 부담이 있습니다.
    
    
  • 무한정 기다림 해결: 같은 트랜잭션이 항상 희생자로 선정되지 않도록 희생자 선정 시 롤백 횟수를 고려해야 합니다. 가장 일반적인 해결책은 비용 요소에 복귀 횟수를 추가하는 것입니다.