교착 상태 복구 (Deadlock Recovery)

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

본질: 교착 상태 복구 (Recovery)는 탐지 알고리즘(Detection)을 통해 시스템에 데드락이 발생했음을 확인한 후, 특정 프로세스를 강제로 종료(Kill)하거나 자원을 뺏어(Preemption) 데드락의 순환 고리(Cycle)를 물리적으로 끊어내는 사후 조치다.

가치: 데드락 예방이나 회피에 드는 막대한 런타임 오버헤드를 지불하는 대신, 평소에는 자원을 100% 효율로 자유롭게 쓰게 놔두고, 가끔 터지는 사고(데드락)만 외과 수술처럼 도려내는 **가장 경제적인 트레이드오프(Trade-off)**를 제공한다.

융합: 복구 과정에서 가장 어려운 점은 "누구를 죽일 것인가(희생자 선택, Victim Selection)"와 "죽인 놈이 어질러놓은 데이터를 어떻게 되돌릴 것인가(Rollback)"이며, 이 때문에 완벽한 복구는 언두 로그(Undo Log)를 갖춘 데이터베이스(RDBMS) 환경에서만 제한적으로 완성된다.

Ⅰ. 개요 및 필요성 (Context & Necessity)

개념: 데드락 탐지(Detection) 알고리즘이 "현재 4개의 스레드가 꼬리를 물고 무한 대기 중이다"라고 경고를 띄웠을 때, 운영체제나 DBMS가 개입하여 이 엉킨 실타래를 강제로 끊어 시스템을 다시 굴러가게 만드는 일련의 과정이다.
필요성: 암세포(데드락)를 찾기만 하고(탐지) 수술을 하지 않으면 환자(시스템)는 죽는다. 인간 관리자가 키보드로 kill 명령어를 치기를 기다릴 순 없다. 1초에 수천 건의 트랜잭션이 도는 서버에서는, 시스템 스스로가 100밀리초 안에 암세포를 제거하고 자동으로 지혈(Rollback)하는 능력이 있어야만 진정한 무중단 시스템이 성립한다.
💡 비유: 교차로에 4대의 차가 꼬리를 물고 서서(데드락) 10분째 클락션만 울리고 있을 때, 하늘에서 거대한 크레인이 내려와 '가장 똥차(Victim) 한 대를 집어서 교차로 밖으로 던져버리는' 과격하지만 확실한 교통정리와 같다.
등장 배경: 자원을 아끼는 것이 미덕이던 시절, 1년에 한 번 날까 말까 한 데드락을 막자고 은행원 알고리즘을 돌리는 짓이 너무 바보 같다는 것을 학자들이 깨달았다. 결국 "예방하지 말고 터지면 고치자"는 낙관적(Optimistic) 철학이 대두되며 복구 알고리즘이 연구되었다.

  [교착 상태 복구(Recovery)의 2가지 근본적 접근법]

  [ 1. 프로세스 종료 (Process Termination) ] ─▶ 깡패식 접근
  - 방법 A: "다 죽여!" (데드락에 연루된 모든 프로세스 동시 사살)
    ▶ 장점: 확실함 / 단점: 그동안 했던 연산 다 날아감 (피해 막심)
  - 방법 B: "원 풀릴 때까지 한 놈씩 죽여!" (희생자 골라 죽이기)
    ▶ 장점: 피해 최소화 / 단점: 죽일 때마다 데드락 탐지 알고리즘을 또 돌려봐야 함

  [ 2. 자원 선점 (Resource Preemption) ] ─▶ 신사적 접근
  - 방법: "프로세스는 살려둘 테니, 네가 쥐고 있는 자원(Lock)만 내놔!"
  - 문제점: 뺏긴 놈이 쓰던 데이터를 10분 전으로 되돌려야 함 (Rollback).
           일반 C/Java 프로그램은 이런 타임머신 기능이 없음.

[다이어그램 해설] 복구는 결국 '누군가의 희생'을 강요한다. 스레드를 통째로 날려버리든, 스레드가 쥔 자원만 뺏든, 누군가는 자기가 하던 작업을 포기하고 처음부터 다시 시작(Restart)해야만 한다. 이 희생의 크기를 최소화하는 것이 복구 알고리즘의 예술이다.

📢 섹션 요약 비유: 엉킨 낚싯줄(데드락)을 푸는 두 가지 방법입니다. 1번(프로세스 종료)은 그냥 엉킨 부분을 가위로 싹둑 잘라버리고 새 줄을 묶는 것이고, 2번(자원 선점)은 시간을 들여서 매듭을 하나씩 뒤로 풀어내는(Rollback) 섬세한 작업입니다. 전자는 빠르지만 줄이 짧아지고, 후자는 줄은 보존되지만 풀기 위한 특별한 기술(Undo Log)이 필요합니다.

Ⅱ. 아키텍처 및 핵심 원리 (Deep Dive)

복구의 제1원칙: 희생자 선택 (Victim Selection)

"누구를 죽일 것인가?" 운영체제나 DB는 사람처럼 감정으로 고르지 않는다. 철저하게 비용(Cost)이 가장 싼 놈을 고른다.

희생자 선정 척도 (Cost Metric)	판단 기준 및 이유
실행 시간 (Execution Time)	10시간 돈 놈을 죽이면 너무 아깝다. 방금 시작한 놈을 죽이는 게 경제적이다.
자원 점유량 (Resources Held)	자원을 100개 쥐고 있는 놈을 죽이면, 자원 100개가 풀리므로 데드락이 한 방에 해결된다.
남은 시간 (Remaining Time)	거의 다 끝나가는 놈은 살려두고, 아직 90% 남은 놈을 죽이는 게 맞다.
롤백 비용 (Rollback Cost)	DB에서, `UPDATE`를 10만 건 친 놈을 죽이면 롤백하는 데만 1시간 걸린다. 아무것도 안 쓴 놈을 죽여야 한다.

복구의 제2원칙: 롤백 (Rollback)

스레드 C를 희생자로 골라 자원을 뺏었다. 그럼 C는 어떻게 되는가?

Total Rollback (완전 재시작): C를 그냥 완전히 죽이고(Abort), 처음부터 다시 실행(Restart) 시킨다. 가장 구현이 쉽다.
Partial Rollback (부분 롤백): 데드락이 풀릴 만큼만 시간을 되돌린다(Checkpoint 사용). 완벽하지만 구현이 미치도록 어렵다. DB 엔진만이 가능하다.

복구의 제3원칙: 기아 상태 (Starvation) 방지

가장 만만한 놈(비용이 싼 놈)만 계속 희생자로 고르다 보면, 그 불쌍한 놈은 평생 10초 돌고 죽고, 10초 돌고 죽기를 반복하며 영원히 작업을 못 끝내는 기아 상태에 빠진다. ▶ 해결책: 희생자 선정 공식에 반드시 "지금까지 희생자로 선정된 횟수 (Rollback Count)"를 가산점으로 넣어서, 3번 이상 죽은 놈은 무적 방패를 씌워주어야 한다.

📢 섹션 요약 비유: 은행 강도를 잡기 위해 인질 1명을 희생시켜야 한다면(희생자 선택), 나이 든 사람보다 구하기 쉬운 사람, 혹은 이미 다친 사람을 먼저 구하는 식의 피도 눈물도 없는 공학적 계산이 들어갑니다. 단, 매번 같은 사람만 희생시키면 그 사람은 너무 억울하니까(기아 상태), 몇 번 희생된 사람은 다음엔 무조건 살려주는 보상 제도가 필요합니다.

Ⅲ. 융합 비교 및 다각도 분석 (Comparison & Synergy)

OS의 무시(Ostrich) vs RDBMS의 적극적 복구(Recovery)

왜 똑같은 데드락인데 범용 OS는 포기하고, 데이터베이스는 악착같이 복구를 해낼까?

구분	범용 운영체제 (Linux, Windows)	RDBMS (Oracle, MySQL InnoDB)
데드락 인지	못 함 (타조 알고리즘)	1초마다 Wait-For Graph로 탐지
희생자 선택	사용자가 작업 관리자로 맘에 안 드는 거 죽임	Undo 로그량이 가장 적은 트랜잭션 자동 선택
롤백 능력	❌ 없음. (C/C++ 메모리를 과거로 돌릴 방법 없음)	✅ 완벽함. (Undo Log 덮어쓰기로 1ms 만에 과거로 회귀)
장애 결과	데드락 걸린 프로그램 영원히 응답 없음 (무한 로딩)	1초 만에 `Deadlock found` 에러 뱉고 정상 트랜잭션은 돌아감

범용 OS가 데드락 복구를 포기한 진짜 이유는 "롤백(Rollback) 기술의 부재"다. 스레드가 프린터에 문서 절반을 쏴놨는데 킬(Kill)해버리면, 프린터엔 쓰레기 종이가 찍혀 나온다. 하지만 DB는 모든 데이터 수정을 "일단 임시 장부(Undo Log)에 적고 나중에 확정(Commit)"하는 구조이기 때문에, 언제든지 롤백으로 타임머신을 탈 수 있는 완벽한 면허증이 있었다.

📢 섹션 요약 비유: 화가가 캔버스에 물감으로 그림을 그리는 중(일반 OS)에 붓을 뺏으면 그림이 망가져 복구가 안 됩니다. 하지만 포토샵(RDBMS)으로 그림을 그릴 때는 붓을 뺏겨도 **Ctrl+Z (Undo Log)**를 누르면 완벽하게 1분 전으로 돌아갈 수 있기 때문에, 맘 놓고 뺏어도(데드락 복구) 되는 것입니다.

Ⅳ. 실무 적용 및 기술사적 판단 (Strategy & Decision)

실무 시나리오

DB 개발자의 데드락 에러 핸들링 (Retry Pattern): 백엔드 개발자라면 누구나 한 번쯤 로그에서 Deadlock found when trying to get lock; try restarting transaction 이라는 DB 에러를 본 적이 있을 것이다.
- 아키텍트의 의미 부여: 이 에러는 DB가 고장 난 게 아니다! DB가 데드락 탐지(Detection)와 복구(Recovery)를 매우 빠르고 훌륭하게 성공했다는 기쁜 소식이다. DB가 나 대신 한 놈을 죽여서 전체 서버의 멈춤을 막아준 것이다.
- 실무 조치: 이 에러를 받으면 개발자는 절대 당황하지 않고, Exception을 캐치(catch)하여 0.1초 쉬었다가 해당 트랜잭션을 처음부터 다시 쏘는 **Retry 로직(Spring @Retryable)**만 짜주면 끝난다. (죽은 놈 스스로가 부활하는 완벽한 아키텍처 완성).
Kubernetes의 OOM Killer와 Liveness Probe (클라우드 시대의 Recovery): 일반 컨테이너 앱에서 데드락이 터지면 롤백이 안 된다고 했다. 그럼 클라우드 환경은 이를 어떻게 복구할까?
- 무식함의 미학: 파드(Pod) 안에 데드락이 터져 스레드가 멈추면 헬스체크(Liveness Probe API)가 실패한다.
- 실무 조치: K8s는 복잡하게 락을 뺏고 롤백하지 않는다. 아예 그 컨테이너 자체를 **SIGKILL로 통째로 폭파(Abort)**시키고, 깨끗한 새 컨테이너를 복제해 띄워버린다. MSA 시대에는 컨테이너 자체가 무상태(Stateless)이므로 가능한, 가장 무식하지만 완벽한 형태의 데드락 복구(Recovery) 아키텍처다.

  ┌────────────────────────────────────────────────────────────────────┐
  │     실무에서 데드락(Deadlock) 에러를 맞이하는 백엔드 아키텍처      │
  ├────────────────────────────────────────────────────────────────────┤
  │                                                                    │
  │   [ MySQL InnoDB에서 Deadlock Found 에러 발생! ]                   │
  │                │                                                   │
  │                ▼ [ 1차 방어막: Application Retry ]                 │
  │     ▶ `try-catch` 또는 `@Retryable`로 감싸서 3번까지 재시도.       │
  │     ▶ 효과: 데드락은 타이밍 문제이므로 100ms 뒤에 다시 쏘면        │
  │             대부분 정상적으로 통과됨. (유저는 에러를 못 느낌)      │
  │                │                                                   │
  │                ▼ [ 2차 방어막: 코드 구조 리팩토링 ]                │
  │     ▶ 데드락이 하루에 100번 이상 터진다면 재시도 오버헤드가 큼.    │
  │     ▶ 조치: 트랜잭션 길이를 짧게 쪼개거나(Short Transaction),      │
  │            테이블 업데이트 순서(Lock Ordering)를 알파벳순으로 통일!│
  └────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 초보자는 데드락 에러가 나면 무서워서 락을 다 풀어버리거나 동기화를 포기한다. 시니어는 데드락 에러가 나는 것을 "DB가 일 잘하고 있네"라며 자연스러운 일상으로 받아들이고, 에러 발생 시 부드럽게 재시도(Retry)하는 래퍼(Wrapper) 코드를 짜서 시스템의 회복 탄력성(Resilience)을 올리는 데 집중한다.

📢 섹션 요약 비유: 게임을 하다가 버그로 캐릭터가 벽에 끼었습니다(데드락). 옛날엔 이걸 풀려고 복잡한 코드를 입력해야 했지만, 지금은 그냥 자살 버튼(DB 강제 킬)을 누르고 부활 지점(Retry)에서 1초 만에 다시 시작하는 것이 가장 빠르고 스트레스 없는 쾌적한 게임 방법입니다.

Ⅴ. 기대효과 및 결론 (Future & Standard)

기대효과

데드락 복구 메커니즘을 시스템에 잘 구현해 두면, 평상시에는 락 순서나 은행원 알고리즘 같은 무거운 제약 없이 최고 속도(100% 스루풋)로 자원을 남용하다가, 만에 하나 터지는 데드락 지뢰만 외과 수술처럼 정밀 타격하여 제거함으로써 극한의 성능과 안정성이라는 두 마리 토끼를 잡을 수 있다.

결론 및 미래 전망

교착 상태 처리의 4단계 진화(예방 ─▶ 회피 ─▶ 탐지/복구 ─▶ 무시)는 결국 "버그를 완벽히 막는 비용이, 버그가 터졌을 때 복구하는 비용보다 비싸다"는 컴퓨터 공학의 절대 진리를 증명하는 과정이었다. 미래의 동시성 제어 모델인 **소프트웨어 트랜잭셔널 메모리 (STM)**와 분산 Saga 패턴은 아예 이 "탐지와 복구"의 철학을 언어와 아키텍처의 기본 문법으로 흡수했다. 처음부터 데드락을 겁내지 않고 낙관적(Optimistic)으로 막무가내로 연산한 뒤, 충돌이 나면 뒤도 안 돌아보고 롤백(Rollback)하는 '실패를 가정한 설계(Design for Failure)'가 21세기 시스템 공학의 영원한 패러다임이 되었다.

📢 섹션 요약 비유: 옛날엔 도자기를 구울 때 금이 가지 않게(예방/회피) 며칠 밤낮을 온도계만 쳐다봤습니다. 지금의 공장(탐지/복구)은 일단 1만 개의 도자기를 미친 속도로 구워낸 뒤, 금이 간 몇 개만 망치로 깨서(Kill) 버리는 것이 훨씬 돈을 많이 번다는 것을 깨달은 것입니다.

📌 관련 개념 맵 (Knowledge Graph)

개념 명칭	관계 및 시너지 설명
교착 상태 탐지 (Detection)	엑스레이(탐지)로 암을 발견해야 수술(복구)을 할 수 있듯이, 복구와 100% 한 몸으로 움직이는 쌍둥이 기술이다.
희생자 선택 (Victim Selection)	데드락의 고리를 끊기 위해 총알받이로 내세울 가장 만만한 스레드를 고르는 복구의 핵심 판단 로직이다.
롤백 (Rollback / Undo Log)	총에 맞고 죽은 희생자 스레드가 어질러 놓은 데이터를 원래대로 되돌리는, DB만이 가진 마법의 시간 여행 기술이다.
타조 알고리즘 (Ostrich)	롤백(Rollback) 기술이 없는 일반 윈도우/리눅스 OS가 복구를 포기하고 선택해 버린 극단적 무시 전략이다.
기아 상태 (Starvation)	만만한 놈만 계속 희생자(Victim)로 쏴 죽이다가 그놈이 평생 실행을 못 하고 죽어버리는 부작용이다.

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

4명의 아이가 장난감을 서로 꽉 쥐고 안 놔줘서(데드락) 1시간째 아무도 놀지 못하고 울고만 있어요.
선생님이 나타나서 **"아 안 되겠다, 제일 늦게 온 철수야! 네가 쥐고 있는 로봇 놔! 넌 이따 놀아!"**라며 강제로 장난감을 뺏어버렸어요(희생자 선택).
철수가 울면서 장난감을 놨지만, 그 장난감을 받은 다른 3명은 꼬인 게 풀려서 꺄르르 웃으며 놀기 시작했답니다. 이렇게 강제로 하나를 희생시켜 꼬인 걸 푸는 걸 데드락 복구라고 해요!