451. 교착 상태 (Deadlock)와 회피 기법 (Wait-Die)

⚠️ 이 문서는 데이터의 무결성을 지키기 위해 서로 자물쇠(Lock)를 걸다가, **"네가 가진 자물쇠를 풀 때까지 나도 내 자물쇠를 안 풀 거야!"라며 두 트랜잭션이 영원한 무한 대기 상태에 빠져버리는 치명적인 시스템 마비 현상인 '교착 상태(데드락)'**를 다룹니다.

핵심 인사이트 (3줄 요약)

  1. 본질: 두 개 이상의 트랜잭션이 서로가 점유하고 있는 자원을 요구하면서, 아무도 양보하지 않아 영원히 멈춰버리는 현상이다.
  2. 해결책: 데드락이 발생하지 않도록 규칙을 정해두는 '회피(Avoidance)'와, 일단 발생하게 두고 주기적으로 검사해서 꼬인 실타래를 끊어버리는 '탐지(Detection)' 기법으로 나뉜다.
  3. 회피 기법: 트랜잭션에 나이표(Timestamp)를 붙여서 늙은 트랜잭션(먼저 온 사람)과 젊은 트랜잭션(나중에 온 사람) 간의 양보 규칙을 정하는 Wait-Die와 Wound-Wait 기법이 시험에 자주 출제된다.

Ⅰ. 개요: 좁은 골목길의 두 자동차 (Context & Necessity)

차 두 대가 외길 한가운데서 마주쳤다.

  • A 차: "네가 뒤로 빼라, 그럼 내가 지나가마."
  • B 차: "싫어, 네가 뒤로 빼라. 그럼 내가 지나가마."

데이터베이스에서도 똑같은 일이 벌어진다.

  • T1: A 데이터 잠금 획득 $\rightarrow$ (수정 중) $\rightarrow$ B 데이터 내놔! (T2가 잠그고 있어서 대기)
  • T2: B 데이터 잠금 획득 $\rightarrow$ (수정 중) $\rightarrow$ A 데이터 내놔! (T1이 잠그고 있어서 대기)

서로 락(Lock)을 쥔 채로 상대방의 락이 풀리기만을 기다린다. 2단계 잠금 규약(2PL, 450번 문서)에 따르면 작업이 끝날 때까지 락을 풀 수 없으므로, 이 두 트랜잭션은 우주가 멸망할 때까지 멈춰있게 된다.

📢 섹션 요약 비유: 데드락은 **'사과와 귤'**을 하나씩 나눠 가진 두 아이와 같습니다. 철수는 사과를 들고 "영희 네가 귤 주면 사과 줄게"라고 하고, 영희는 귤을 쥐고 "철수 네가 사과 먼저 주면 귤 줄게"라고 합니다. 어른(DB 관리자)이 개입해서 한 명의 손을 강제로 펴게 하지 않으면 평생 사과와 귤을 바꿀 수 없습니다.

Ⅱ. 데드락 회피 기법: Wait-Die vs Wound-Wait ★

나이(Timestamp)를 기준으로 "누가 양보할 것인가"를 수학적으로 정해둔 규칙이다. (오래된 트랜잭션 = 늙은이 / 최근에 시작된 트랜잭션 = 젊은이)

1. Wait-Die (기다리거나 죽거나)

늙은이가 대우받는 유교(?)적인 방식이다.

  • 늙은이가 젊은이의 자원을 원할 때 (Wait): "내가 어른이니까 기다릴게. 너 다 쓰면 줘." (대기)
  • 젊은이가 늙은이의 자원을 원할 때 (Die): "감히 어른의 물건을 넘봐? 넌 탈락이야!" (젊은이 트랜잭션 강제 종료/Rollback)

2. Wound-Wait (뺏거나 기다리거나)

늙은이가 깡패처럼 무자비하게 뺏는 방식이다.

  • 늙은이가 젊은이의 자원을 원할 때 (Wound): "어른이 쓰셔야겠다. 너 비켜!" (젊은이의 자원을 뺏고, 젊은이 강제 종료/Rollback)
  • 젊은이가 늙은이의 자원을 원할 때 (Wait): "어른이 쓰고 계시니 얌전히 기다려야지." (대기)

Ⅲ. 데드락 탐지(Detection)와 희생자 선택

실무(MySQL 등)에서는 회피 기법을 쓰지 않는다. 규칙을 지키느라 너무 많은 트랜잭션이 죽어나가기 때문이다. 대신 **"일단 자유롭게 써봐. 근데 데드락 걸리면 내가 주기적으로 찾아내서 죽여버릴게"**라는 탐지 기법을 쓴다.

  • DB 엔진 안에는 Deadlock Detector라는 순찰병이 있다.
  • 1초마다 누가 누구를 기다리는지 **'대기 그래프(Wait-for Graph)'**를 그린다.
  • 그래프에서 꼬리물기(Cycle, 원)가 발견되면 데드락이다!
  • 희생자(Victim) 선택: 꼬인 실타래를 풀기 위해 누군가 1명을 강제로 롤백시켜야 한다. 이때 가장 '만만한 놈'을 고른다. (지금까지 업데이트한 데이터가 제일 적은 놈, 방금 막 시작한 놈 등)
┌──────────────────────────────────────────────────────────────┐
│           교착 상태(Deadlock)의 원인과 사이클(Cycle) 시각화           │
├──────────────────────────────────────────────────────────────┤
│                                                              │
│ [ 🔄 대기 그래프 (Wait-for Graph) ]                           │
│                                                              │
│        (Lock 획득)            (요청하며 대기)                    │
│    A 데이터 ◀───── T1 ──────────────────┐                   │
│                    ▲                    │                   │
│                    │                    ▼                   │
│               (요청 대기)            B 데이터                   │
│                    │                    ▲                   │
│                    └───────── T2 ───────┘                   │
│                                (Lock 획득)                   │
│                                                              │
│ ★ 특징: 화살표가 꼬리를 물고 뱅글뱅글 도는 '원(Cycle)'이 그려지면,           │
│       DBA의 개입 없이는 절대 풀리지 않는 완벽한 데드락 상태다.              │
└──────────────────────────────────────────────────────────────┘

Ⅳ. 결론

"데드락을 완전히 없애는 것은 불가능하다. 어떻게 우아하게 죽일지를 고민하라." 교착 상태는 코드를 아무리 잘 짜도, 데이터베이스를 동시에 사용하는 사용자가 많아지면 필연적으로 마주칠 수밖에 없는 자연재해와 같다. 백엔드 개발자의 실력은 데드락이 발생했을 때 나타난다. 테이블을 접근하는 순서를 모든 트랜잭션에서 동일하게 맞추고(A->B 순서), 불필요한 롱 트랜잭션을 잘게 쪼개어 데드락 발생 확률을 극단적으로 낮추는 것, 그리고 에러(Deadlock found when trying to get lock)가 발생했을 때 앱 단에서 안전하게 Retry(재시도) 로직을 구현해 내는 것이 진정한 시니어의 역량이다.

📌 관련 개념 맵

  • 원인 기술: 2PL (2단계 잠금 규약 - 450번 문서), S/X Lock (449번 문서)
  • 운영체제(OS) 비교: OS의 데드락 발생 4조건 (상호배제, 점유대기, 비선점, 환형대기)과 동일함.
  • 해결책 알고리즘: Timestamp Ordering (452번), Wait-Die, Wound-Wait
  • 실무 대처법: Deadlock Timeout 설정, Retry 로직 구현

👶 어린이를 위한 3줄 비유 설명

  1. 밥을 먹으려면 포크와 숟가락이 모두 필요해요.
  2. 철수는 포크를 쥐고 영희의 숟가락을 달라고 하고, 영희는 숟가락을 쥐고 철수의 포크를 달라고 해요.
  3. 둘 다 자기가 가진 걸 절대 놓지 않으면서 남의 것만 달라고 하니까, 둘 다 굶어 죽을 때까지 밥을 한 술도 못 뜨는 바보 같은 상황이 바로 데드락이랍니다!