DB 데드락이란?

 

---

데드락? 교착상태?

출처: 위키피디아

 OS에서 중요하게 다루는 문제로 데드락, 교착상태가 있다. OS에서 데드락을 안다는 가정하에 OS의 데드락을 간략히 설명하고 데이터베이스의 데드락을 보자.

 

 OS의 DeadLock, 교착상태란 둘 이상의 프로세스가 자원을 점유하고 다른 프로세스가 점유중인 자원을 요구하면서 무한정 기다리는 현상이다. 이런 이기적인 프로세스들은 상호배제, 점유대기, 비선점, 환형대기 4가지 조건하에 태어난다.

 해결방법으로는 위의 4가지 조건 중 하나라도 만족하지 않게 애초에 방지하거나, 교착상태가 발생할거 같으면 자원을 할당하지 않고 회피하거나, 교착상태가 발생하든말든 냅두다가 발생하면 탐지하고 회복하는 방법이 있다. 

 

---

데이터베이스에서의 데드락은 언제 왜 발생하고 어떻게 해결할까? 

 

데이터베이스의 교착상태도 OS와 똑같다. OS의 이기적인 프로세스가 문제라면 DB에는 이기적인(?) 트랜잭션이 문제다.

(==트랜잭션도 하나의 프로세스다.)

DeadLock, 교착상태란 둘 이상의 프로세스가 자원을 점유하고 다른 프로세스가 점유중인 자원을 요구하면서 무한정 기다리는 현상이다. 이런 이기적인 프로세스들은 상호배제, 점유대기, 비선점, 환형대기 4가지 조건하에 태어난다.

라고 위에서 말했는데 여기서 자원 -> 데이터, 프로세스-> 트랜잭션으로 바꾸기만 하면 DB에서의 데드락이 발생하는 상황을 이해하기 쉽다. 

 

자원, 점유하는 방법, 프로세스는 OS에서 알아보고 데이터베이스에서는 트랜잭션이 뭔지, 데이터를 왜 점유하는지, 어떻게 점유하는지, 어떻게 해결하는지 알아보자.

 

---

트랜잭션 

https://dana-study-log.tistory.com/entry/DB-%ED%8A%B8%EB%9E%9C%EC%9E%AD%EC%85%98%EA%B0%9C%EB%85%90%ED%8A%B9%EC%84%B1%EC%97%B0%EC%82%B0%EC%83%81%ED%83%9C?category=1081271

[DB] 트랜잭션(개념/특성/연산/상태)

 트랜잭션이란 ACID를 만족하여 무결성을 보장하며 데이터의 상태를 바꾸는 작업의 단위이다. 예를들어 INSERT, DELETE, UPDATE 등 DML은 트랜잭션으로 볼 수 있다. DML은 데이터의 상태를 변경하고, DB는 자동으로 Commit을 실행하여 변경된 내역을 데이터베이스에 반영한다. 실패한다면 데이터의 상태가 변경되기전으로 돌아가는 작업인 Rollback을 수행한다. 

 

 트랜잭션의 이기적인 부분은 ACID의 Isolation이다. 

 

Isolation 조건을 만족하기 위해 트랜잭션은 동시에 접근하는것을 제어하고 여기서 데드락이 발생할 수 있다. 

 

 트랜잭션하면 흔히 나오는 예시로 입출금이 있다. 내 계좌에서 돈을 빼고(UPDATE) 뺀만큼 상대방 계좌에 돈을 넣는(UPDATE) 작업은 UPDATE 두 개가 모두 성공한 뒤 Commit해야한다. 둘 중 하나라도 실패할 경우 Commit되지 않고 트랜잭션이 시작하기전으로 Rollback한다. 반드시 둘 다 성공해야만 Commit이 진행된다. 

 

 여기서 추가로 Isolation(고립성, 독립성)을 위한 예시를 들어보면,

동언이형은 전재산이 1000원이다.
난 동언이형한테 3000원을 송금했다. 
그리고 안채는 데이터베이스에 내 송금작업이 Commit되기전에 동언이형한테 5000원을 송금했다. 

1. 내 돈을 입금하며 동언이형의 계좌에 잔고를 (1000원 + 3000원)으로 UPDATE한다.
2. 그리고 Commit되기 전에 안채가 동언이형한테 5천원을 송금했다.
3. 이때 안채가 송금작업을 수행할 당시 바라본 동언이형의 잔고는 천원이고 (1000원 + 5000원)으로 UPDATE하게 된다. -> Dirty Read
4. 내 송금작업에 대해 Commit을 진행한다. ( 동언이형 잔고 1000원 + 3000원 ) 
5. 안채의 송금작업에 대해 Commit을 진행한다. ( 동언이형 잔고 1000원 + 5000원 ) -> 내 송금작업에 대한 갱신손실 

입금과 출금이 2번씩 UPDATE가 4번 발생했으며 모든작업이 Commit 됐음에도 동언이형은 3천원을 도둑맞았다.

이러한 문제(갱신손실)를 포함해서 다양한 문제를 해결하기위해 트랜잭션은 Isolation을 만족해야한다. 

Isolation

 트랜잭션은 동언이형의 3천원을 지키기위해 데이터를 고립(Lock)시켜서 데이터에 동시에 접근하는 것을 제어한다.

만약 동시에 접근하는것이 제어되지 않는다면 위의 예시를 포함하여 다음과 같은 상황에서 문제가 발생할 수 있다. 

	트랜잭션 1	트랜잭션 2	발생 문제	동시 접근?
상황 1	읽기	읽기	없음	허용
상황 2	읽기	쓰기	잘못된 데이터 읽기	허용-불가 선택
상황 3	쓰기	쓰기	갱신손실, 연쇄복구, 회복 불가능	불가(-> Lock)

 

즉 트랜잭션은 Isolation 을 만족하기위해 동시접근을 제어하여 위의 문제점들을 방지할 필요가 있다.

동시접근을 제어하는 방법으로는 트랜잭션스케줄링, LOCK이 있다. 우리는 데드락이 목적이니 스케줄은 대충하고 LOCK에대해서 자세히 알아보자. 

 

---

 

트랜잭션 스케줄

트랜잭션 스케줄 

여러 트랜잭션이 동시에 접근하는 것을 제어하기 위해 데이터를 고립시킨 뒤 순차적으로 실행하는 직렬 스케줄, 혹은 직렬 가능한 스케줄로 만들어야한다.

직렬 스케줄 : 하나의 트랜잭션이 실행되면, 해당 트랜잭션이 완료되어야만 다른 트랜잭션이 실행될 수 있다.
비직렬 스케줄 : 트랜잭션을 병행수행한다. 기존 트랜잭션이 진행중이더라도 다른 트랜잭션이 실행 될 수 있다. 
직렬 가능한 스케줄 : 서로 영향을 주지 않는 직렬 스케줄을 비직렬적으로 수행한다. 

즉, 다중사용자환경의 DBMS에서는 동시성(병행수행)을 최대한 보장하면서 직렬스케줄과 동일한 결과를 가지는 직렬 가능한 스케줄로 만드는 방법이 가장 좋다. 

 

직렬 스케줄

1. 읽기 연산만 수행한다면, 상호 간섭이 발생하지 않고 연산의 순서도 중요하지 않다. 
2. 같은 데이터 항목에 접근하지 않는다면, 상호 간섭이 발생하지 않고 연산의 순서도 중요하지 않다. 
3. 트랜잭션1, 트랜잭션2가 같은 데이터 항목에 접근하여 트랜잭션 1은 쓰기 연산을 하고 트랜잭션2가 읽기 또는 쓰기 작업을 수행한다면 상호 간섭이 발생하고 연산의 순서가 중요하다. 

LOCK

트랜잭션들이 동일한 데이터 항목에 대해 임의적 병행 접근을 하지 못하도록 제어하는 방법이다. 

Lock연산은 아래와 같은 조건들을 지키며 수행된다. 

• 트랜잭션 T가 데이터 항목 D에 대해 READ(D) or WRITE(D)연산을 수행하려면 반드시 LOCK(D) 연산을 수행해야한다. 
• 트랜잭션 T가 실행한 LOCK(D)에 대해서는 트랜잭션 T가 종료되기 전 반드시 UNLOCK(D)연산을 수행해야한다. 
• 트랜잭션 T는 다른 트랜잭션T2에 의해 이미 LOCK(D)이 걸려있는 D에 대해 다시 LOCK(D)를 수행하지 못한다. ->(S-LOCK끼리는 가능)
• 트랜잭션 T가 D에 LOCK(D)를 걸지 않았다면, 트랜잭션 T는 D에대해 UNLOCK(D)를 수행하지 못한다. 

공유락 Shared - LOCK (S-LOCK)

• Shared Lock를 설정한 트랜잭션은 데이터 항목에 대해 읽기 연산만 가능하다. 
  • 트랜잭션 T가 데이터항목 D에 대해 S-LOCK(D)을 설정하면 T는 읽기 연산만 가능하다. 
• 하나의 데이터 항목에 대해 여러개의 트랜잭션이 Shared Lock 할 수 있다. 
  • 트랜잭션 T1이 데이터항목 D에 대해 S-LOCK(D)을 설정한 경우에, 트랜잭션 T2도 데이터항목 D에대해 S-LOCK(D)를 설정할 수 있다. 
• S-LOCK(D)가 걸려있다면 S-LOCK을 건 트랜잭션 포함 다른 트랜잭션에서도 읽기연산은 수행가능하다. 
  • 트랜잭션 T1이 데이터항목 D에 대해 S-LOCK(D)를 설정한 경우, T1을 포함한 다른 트랜잭션들도 읽기 작업이 수행가능하다. (쓰기작업은 불가능하다.)

배타락 Exclusive-LOCK(X-LOCK)

• X-LOCK을 설정한 트랜잭션T1은 데이터항목 D에 대해 읽기와 쓰기 연산 모두 가능하다. 
• 하나의 데이터항목에대해 하나의 트랜잭션만 X-LOCK을 걸 수 있다. 
• 동시에 여러개의 트랜잭션이 X-LOCK을 걸 수 없다. 
  • 트랜잭션 T1이 X-LOCK(D)을 걸었다면 T1이 UNLOCK(D)하기 전에 T2에서는 X-LOCK(D)를 수행할 수 없다.
  • T2는 D에대해 X-LOCK(D)작업이 불가능하다.

 

 

잠금규칙

• 트랜잭션은 READ(D) 연산을 실행할 때 S-LOCK(D)이나 X-LOCK(D) 중 하나를 실행해야한다.
• WRITE(D)를 수행하려면 X-LOCK(D)를 실행해야한다. 
• 어떤 LOCK이든, 어떤 연산이든 작업 종료 후에는 UNLOCK(D) 연산을 실행해야 한다.
• UNLOCK(D)는 S-LOCK(D) 혹은 X-LOCK(D)가 수행된 후에만 실행될 수 있다. 
  • 즉, LOCK 없는 UNLOCK없고 UNLOCK없는 LOCK없다. 

잠금단위

잠금단위란 잠금의 대상이 되는 데이터 객체의 크기로 레코드의 필드값, 레코드, 물리적 입출단위인 디스크부터 테이이나 데이터베이스까지 하나의 잠금 단위로 설정할 수 있다. 

• 잠금 단위가 클수록 동시성(병행성)수준은 낮아지고, 동시성 제어 기법이 간단해진다. 
• 잠금 단위가 작을수록 동시성(병행성)수준은 높아지고, 동시성 제어 기법이 복잡해진다. 

따라서 여러개의 잠금 단위를 설정하고 필요에따라 사용할 수 있어야한다. 

---

교착상태, 데드락 

드디어 교착상태, 데드락이다. 이걸위해 LOCK이고 트랜잭션이고 설명했다. 

LOCK은 트랜잭션의 고립성을 만족시키기 위해, 또 동언이형의 3천원을 지키기 위해 꼭 필요하다. 

따라서 LOCK은 대부분의 DBMS에서 사용하는 방식이다. 하지만 큰 한계가 존재한다. 

 

트랜잭션 TA가 x에 X-LOCK를 걸고, 해당 LOCK이 끝나기 전에 y에도 X-LOCK(y)를 걸려고 한다.(하나의 트랜잭션이 여러개의 데이터에 접근하는 상황)

하지만 y는 트랜잭션 TB가 S-LOCK을 걸어놓은 상태고 트랜잭션 TB는 y에 대한 S-LOCK(y)를 끝내기 전에 데이터 x에 S-LOCK(x)를 걸려고 한다. 

x는 TA가, y는 TB가 LOCK을 걸어놨고, TA는 y에대한 UNLOCK을, TB는 x에대한 UNLOCK을 기다린다. 트랜잭션 둘 중 하나가 양보하지 않으면 한없이 기다리며 이때 교착상태, 데드락이 발생한다.

 

 Isolation을 만족시키지 않으면 동언이형은 3천원을 도둑맞고 Isolation을 만족시키기위해 LOCK을 걸자니 교착상태, 데드락이 발생할 수 있다.

 

위의 예시 상황은 데드락의 네가지 조건들을 만족한다.

• 상호배제  : 데이터의 한 항목에대해 함께 작업할 수 없고 독점적으로 사용한다. 
• 점유대기  : 트랜잭션은 데이터에 LOCK을 걸고 다른 데이터의 UNLOCK을 기다린다. 
• 비선점.    : 트랜잭션은 다른 트랜잭션이 걸어놓은 LOCK을 UNLOCK할 수 없다. 
• 환형 대기 : 각 트랜잭션이 서로 순환적으로 다른 트랜잭션의 UNLOCK을 기다린다.  

네가지 조건 모두 만족해야 데드락이 발생하고 이중 하나라도 만족하지 않으면 데드락이 발생하지 않는다. 

데이터베이스에서 데드락 해결하기 

DB에서 데드락을 해결하는 방법으로는 4가지 조건 중 하나라도 만족하지 않게 애초에 방지하거나, 교착상태가 발생할거 같으면 LOCK하지 않고 회피하거나, 교착상태가 발생하든말든 냅두다가 발생하면 탐지하고 회복하는 방법이 있다. 

 

방지기법

각 트랜잭션이 실행되기 전 미리 필요한 모든 데이터를 LOCK한다.

 위의 예시와는 다르게 TA는 시작할때 필요한 데이터를 파악하고, x와 y에 모두 LOCK을 실행한다. 그럼 중간에 TB가 y에 LOCK을 시도할때 TA의 UNLOCK을 기다려야하고 TA는 y에대한 데이터를 사용한뒤 UNLOCK하면 TB가 사용할 수 있다. 따라서 데드락을 애초에 방지할 수 있다.

 하지만 필요한 모든 데이터를 LOCK해야 하므로 병행성이 떨어진다. 즉, 현재 y데이터는 사용하지 않고 x에 대한 작업만 수행하고 있음에도 y에 접근할 수 없다. 

 

SET LOCK_TIMEOUT문을 통해 일정시간이 지나면 트랜잭션, 쿼리를 취소한다. 

 데드락인 데이터가 있다면 그 데이터에 대한 작업은 오랜시간 대기하게 될 것이므로, 일정시간이 지나면 취소하는 방법이다.

간단하게 방지할 수 있지만 일정시간 기다려야하므로 근본적인 해결책이 될 수 없다. 

 

회피기법 

데이터에 LOCK을 실행할 때 Time Stamp를 활용해서 교착상태가 일어나지 않도록 회피하는 방법이다. 

방지기법에서의 단점들때문에 실제로는 회피기법이 주로 사용된다.

 

Wait-Die방식

 

 트랜잭션 A가 트랜잭션 B에 의해 잠금된 데이터를 요청할 때 트랜잭션 A가 먼저 실행된 트랜잭션이라면 B가 끝날때까지 대기한다. 

 트랜잭션 A가 트랜잭션 B에 의해 잠금된 데이터를 요청할 때 트랜잭션 A가 늦게 실행된 트랜잭션이라면 포기하고 나중에 다시 요청한다. 

 

Wound-Wait방식

 트랜잭션 A가 트랜잭션 B보다 먼저 실행된 트랜잭션이라면, 데이터를 선점(Wound)한다. 

 트랜잭션 A가 트랜잭션 B보다 늦게 실행된 트랜잭션이라면, B가 끝날때까지 대기한다. 

낙관적 병행 제어 기법

낙관적 병행 제어 기법은 트랜잭션이 실행되는 동안 검사를 수행하지 않고 트랜잭션의 계산이 마무리 된 후에 데이터에 문제가 있다면 RollBack, 없다면 commit 하는 방법이다. 

낙관적 병행 제어 기법에서는 판독 -> 확인 -> 기록 단계를 따르는데 확인 단계를 거친 트랜잭션만 기록 단계를 수행할 수 있다. 

 

다시 동언이형의 사라진 3천원을 보자. 

내 잔고 + 동언이형 잔고 + 안채 잔고의 값은 일정해야한다. 총합에서 3천원이 사라진것은 문제고 이러한 문제는 판독 -> 확인 과정에서 문제가 발생시킨다. 그럼 RollBack되고 내 잔고에 다시 3천원이 돌아올 것이다. 

 

정확히 표현하면 트랜잭션은 다른 사본을 만들어 관리하고, 트랜잭션에서 갱신(UPDATE)은 사본에 대해 실행한다. 그리고 확인단계에서 트랜잭션 실행 결과가 직렬 가능성위반을 체크한다. 예를 들어 동시에 쓰기작업을 진행했다면, 문제가 있는 작업이다. 쓰기작업이 동시에 이뤄지지 않았다면 확인단계를 통과하고 Commit하며, 확인단계를 통과하지 못했다면 RollBack한다. 

 

 

https://covenant.tistory.com/85

데이터베이스 트랜젝션 ACID란?

https://velog.io/@gojung/%ED%8A%B8%EB%9E%9C%EC%9E%AD%EC%85%98%EA%B3%BC-%EA%B5%90%EC%B0%A9%EC%83%81%ED%83%9C

트랜잭션과 교착상태

https://parkmuhyeun.github.io/etc/database/2022-07-03-Deadlock/

데이터베이스 - 교착상태(Deadlock)

https://velog.io/@junu0516/%EA%B5%90%EC%B0%A9%EC%83%81%ED%83%9C-%EB%B0%A9%EC%A7%80%EA%B8%B0%EB%B2%95

교착상태 방지기법