데이터베이스가 데드락을 감지하고 처리하는 방식

[sangjun121]

데드락이 감지되면 교착상태에 빠졌으니, 데이터베이스가 아예 멈출까요?
데이터베이스는 데드락을 어떻게 감지하고, 실제로 어떤 방식으로 처리하는지 서술해주세요.

[koreaioi]

• MySQL 기준으로 학습했습니다.

데드락 감지

MySQL은 WFG(Waiting-For-Graph)를 기반으로 탐지합니다. MySQL DeadLock Detection

WFG는 Thread와 Resource로 이루어진 자원할당 그래프에서 Resource노드를 제거하고 프로세스 간 대기 관계만 남긴 그래프입니다.
각 자원의 유형이 하나인 경우, 이 노드들 중 사이클이 존재하면 그것이 바로 데드락입니다.
그래서 MySQL에서 요청이 들어왔을 때, 대기 그래프에 사이클이 존재하는 지 확인합니다.

• 공룡책 371p에 나와있네용

자원할당 -> 대기 그래프

데드락 처리

MySQL에서는 데드락이 발견되면 하나의 트랜잭션이나 작은 단위의 트랜잭션을 롤백합니다. 이때 기준은 INSERT, UPDATE, DELETE 쿼리 수에 따라서 결정합니다.

조금 더 찾아보니, TRX_WEIGHT라는 트랜잭션 가중치에 따라 결정되며, 이는 트랜잭션이 변경한 행수와 잠근 행수를 반영한다고 합니다!

이 트랜잭션 가중치가 가장 작은 트랜잭션을 희생하여 롤백합니다.

The weight of a transaction, reflecting (but not necessarily the exact count of) the number of rows altered and the number of rows locked by the transaction. To resolve a deadlock, InnoDB selects the transaction with the smallest weight as the “victim” to roll back. Transactions that have changed nontransactional tables are considered heavier than others, regardless of the number of altered and locked rows.

[softmoca]

데이터베이스는 데드락 상황에서 전체가 멈추는 것이 아니라,
트랜잭션들이 서로 어떤 락을 기다리는지 나타내는 대기 그래프를 추적하다가 사이클이 생기면 데드락으로 감지하고,
보통 비용이 적은 트랜잭션 하나를 희생자로 선택해 롤백시킨 뒤 나머지 트랜잭션이 계속 진행되도록 처리합니다.

[Uechann]

결론을 먼저 이야기 하자면 데드락이 감지돼도 데이터베이스는 멈추지 않습니다.
싸이클에 엮인 트랜잭션 몇 개만 교착 상태일 뿐이고,
DB는 그 중 하나를 골라 강제 롤백해서 그부분만 끊는다고 합니다.

데드락은 둘 이상의 트랜잭션이 서로 쥐고 있는 락을 기다리며 순환 대기 에 빠진 상태이므로,
싸이클 밖의 트랜잭션들은 처음부터 끝까지 정상적으로 돌아가고
DB가 이 사이클을 찾아내서 한쪽을 끊어주는 역할을 한다.
데드락 처리는 감지 후 희생자 롤백 방식이 표준이라고 알게되었습니다.

---

어떻게 데드락을 감지하고, 해결할까?

1. 대기 그래프 (wait-for Graph)

대기 그래프 (wait-for Graph)를 통해서 트랜잭션, 간선 별로 T1 → T2 형태로
각 트랜잭션마다 어느 트랜잭션에서 가지고 있는 락을 기다린다는 의미를 부여한다.

해당 그래프를 검사하는 트리거 방식은 DB 마다 다르다고 합니다.

능동 감지 (MySQL InnoDB)

락 요청이 대기에 들어갈 때마다 대기 그래프에서 사이클을 검사한다.
innodb_deadlock_detect가 기본이다.

타임아웃 트리거 감지 (PostgreSQL)

평소에 검사를 돌지 않다가, 락 대기가 deadlock_timeout(기본 1초)을 넘기면 그제서야 그래프를 만들어 검사한다.
대부분의 락 대기가 짧으면 감지 비용을 거의 안낸다.

순수 타임아웃

innodb_lock_wait_timeout(기본 50초) 같은 값을 넘기면 그냥 그 트랜잭션을 죽인다.
그래프 감지가 놓친 경우의 안전망 역할을 한다.

2. 희생자 선정 후 강제 롤백

데드락 사이클이 판단되면 DB는 한 트랜잭션을 골라 롤백해 연결을 끊는다.

InnoDB는 보통 수정한 행이 가장 적은 트랜잭션을 희생자로 삼는다.

MySQL: 1213 Deadlock found
PostgreSQL: ERROR: deadlock detected

3. 재시도는 애플리케이션에서

희생당한 트랜잭션이 롤백되어 처음부터 다시 시도해야 한다.
즉, 데드락은 운영 중 정상적으로 발생할 수 있는 이벤트이고, 앱은 이 에러를 잡아 재시도하게 한다.

[haeyoon1]

데드락이 발생했다고 해서 데이터베이스 전체가 멈추지는 않습니다.

데드락이 감지되면 DB는 보통 다음과 같이 처리합니다.

1. 데드락에 걸린 트랜잭션들을 찾는다.
2. 그중 하나를 victim으로 선택한다.
3. 선택된 트랜잭션을 롤백한다.
4. 롤백된 트랜잭션이 잡고 있던 락을 해제한다.
5. 나머지 트랜잭션이 계속 실행될 수 있게 한다.

희생자 트랜잭션은 보통 비용이 적은 쪽이 선택됩니다.
DBMS마다 기준은 다르지만 예를 들어 이미 수행한 작업이 적거나, 롤백 비용이 낮은 트랜잭션이 선택될 수 있습니다.

데드락은 DB가 자동으로 감지하고 한쪽 트랜잭션을 롤백해 해결하지만, 애플리케이션에서는 해당 트랜잭션이 실패했다는 사실을 알고 적절히 처리해야 합니다.

따라서 어플리케이션은 다음과 같은 해결책이 필요합니다.

• 트랜잭션 재시도 로직
• 락 획득 순서 통일
• 트랜잭션 범위 최소화
• 불필요한 락 줄이기
• 인덱스를 적절히 사용해 잠금 범위 줄이기
• 같은 자원을 여러 트랜잭션이 다른 순서로 접근하지 않도록 설계