분산 시스템 교착 상태 (Distributed Deadlocks)¶

분산 시스템 환경에서는 전역 상태(Global State)에 대한 정확한 지식을 갖기 어렵고 통신 지연이 발생하기 때문에, 교착 상태를 다루는 전략이 단일 시스템과는 다릅니다. 이 문서는 분산 환경에서의 교착 상태 처리 전략과 대표적인 탐지 알고리즘인 에지 체이싱(Edge Chasing)을 설명합니다.

문서 범위와 프로토콜 전제¶

범위: 분산 lock/resource manager가 명시적인 wait-for 관계를 관측할 수 있는 교과서 모델을 설명합니다. 일반 메시지 지연, 합의 교착, 애플리케이션 livelock을 모두 다루는 알고리즘은 아닙니다.
전제: Chandy-Misra-Haas에는 AND/OR 대기 모델별 변형이 있으며, 프로세스·사이트 식별자, 메시지 전달, 중복 억제와 wait 관계의 유효 시점을 정의해야 합니다.
근거 상태와 환경: “효율적”이라는 평가는 메시지 수, 탐지 지연, WFG 변화율과 장애 모델을 고정한 뒤 비교해야 합니다. 운영 적용은 대상 DB/lock manager 버전의 공식 프로토콜과 로그로 확인합니다.
실패/재시도: probe 지연·중복·유실, 사이트 단절과 stale edge를 교착으로 즉시 확정하지 않습니다. 탐지 epoch와 TTL을 두고 제한 재시도하며, 결과 불명 상태는 재검증 또는 운영자 격리로 전환합니다.
완료 증거: 선언된 교착은 동일 epoch의 cycle/probe 기록으로 입증하고, 해결은 희생 트랜잭션의 abort·보상, 자원 해제와 나머지 작업의 진행을 확인해야 완료입니다.

1. 교착 상태 처리 전략¶

분산 시스템에서 교착 상태를 다루는 전략은 크게 예방(Prevention), 회피(Avoidance), **탐지 및 해결(Detection and Resolution)**로 분류됩니다. 어느 전략이 실용적인지는 자원 요구량 예측 가능성, 실패 모델, rollback 비용과 탐지 지연에 따라 달라집니다.

1.1 교착 상태 예방 (Deadlock Prevention)¶

교착 상태 발생 가능성을 원천적으로 차단하는 방법입니다. * 방법: 프로세스 시작 전 모든 자원을 한 번에 획득하거나, 자원 점유 프로세스를 선점(Pre-emption)합니다. * 한계: 선할당과 선점 제약이 활용률·가용성을 낮출 수 있지만, 전역 lock ordering이나 lease처럼 제한된 자원 경계에서는 실용적일 수 있습니다.

1.2 교착 상태 회피 (Deadlock Avoidance)¶

자원 할당 전 시스템이 안전한 상태(Safe state)로 남을지 미리 판단하는 방법입니다. * 방법: 자원 요청 승인 시 안전 상태가 유지될 경우에만 할당합니다. * 한계: 모든 사이트가 시스템의 전역 상태를 실시간으로 파악해야 하므로 분산 환경에서 구현하기 어렵습니다.

1.3 교착 상태 탐지 및 해결 (Detection and Resolution)¶

교착 상태 발생을 허용하되, 주기적으로 검사하여 해결하는 방식입니다.

가. 탐지 (Detection)¶

프로세스 간 대기 관계를 나타내는 **대기 그래프(Wait-For Graph, WFG)**에서 사이클(Cycle)을 찾습니다.

주요 탐지 알고리즘:
1. 경로 푸싱(Path-pushing): 로컬 WFG 정보를 이웃으로 전송하여 전역 WFG를 구축.
2. 에지 체이싱(Edge-chasing): 전역 WFG 없이 '프로브(Probe)' 메시지를 따라 이동하며 사이클 탐지. (오버헤드가 적어 효율적)
3. 확산 연산(Diffusion computation): 에코 알고리즘 활용.
4. 전역 상태 탐지(Global state detection): 시스템 스냅샷을 찍어 검사.

나. 해결 (Resolution)¶

탐지된 사이클 내의 프로세스 중 하나를 중단(Abort)**시켜 자원을 회수하고 진행을 재개합니다. 단, 정보 지연으로 인한 **유령 교착 상태(Phantom deadlock) 오인 가능성에 주의해야 합니다.

2. 에지 체이싱 (Edge Chasing) 알고리즘 상세¶

에지 체이싱은 전역 그래프를 구축하는 대신, 그래프의 간선(Edge)을 따라 프로브(Probe) 메시지를 전달하여 사이클 존재 여부를 확인합니다.

2.1 작동 단계¶

1. 시작 (Initiation)¶

트랜잭션 간 대기 관계를 모니터링하다가 특정 조건에서 탐지를 시작합니다. * 조건: 트랜잭션 \(T\)가 \(U\)를 기다리는데, \(U\)가 다른 서버**의 자원을 기다리는 경우. * **동작: 대기 관계(예: \(\langle T \rightarrow U \rangle\))를 포함한 프로브 메시지를 생성하여 \(U\)가 대기 중인 자원의 관리 서버로 전송합니다.

2. 탐지 및 전달 (Detection and Forwarding)¶

프로브를 수신한 서버는 경로 정보를 업데이트하고 전달합니다. * 확장: 프로브 \(\langle T \rightarrow U \rangle\)를 받은 서버는 \(U\)가 또 다른 트랜잭션 \(V\)를 기다리는지 확인합니다. 맞다면 정보를 추가하여 \(\langle T \rightarrow U \rightarrow V \rangle\)로 확장합니다. * 전달: \(V\)가 또 다른 서버의 자원을 기다린다면, 해당 서버로 프로브를 전달(Forwarding)합니다.

3. 사이클 확인 (Cycle Found)¶

프로브 메시지가 계속 전달되다가 시작 트랜잭션(Initiator)**으로 되돌아오는 경우입니다. * **판단: 프로브 경로에 이미 포함된 트랜잭션 \(T\)로 다시 돌아오면(예: \(\langle T \rightarrow U \rightarrow V \rightarrow T \rangle\)) 사이클이 형성된 것이며, 이는 교착 상태를 의미합니다. * 해결: 정책에 따라 희생 트랜잭션을 abort/rollback하거나 lease를 만료시킵니다. 외부 부작용이 있으면 보상과 멱등 재실행이 필요하며, 복구 자체도 실패할 수 있습니다.

2.2 대표 알고리즘 (Chandy-Misra-Haas)¶

프로브 메시지를 (i, j, k) 형태의 삼중쌍(triplet)으로 구성합니다.
- \(P_i\): 탐지를 시작한 프로세스
- \(P_j\): 현재 메시지를 보내는 프로세스
- \(P_k\): 메시지를 받는 프로세스
해당 변형의 대기 모델과 동일한 탐지 epoch에서 유효한 프로브가 시작 프로세스 \(P_i\)로 되돌아오면 교착 후보로 판정하고 현재 wait 관계를 재확인합니다.

삼중쌍 probe는 경로 전체를 싣는 방식보다 메시지 크기를 제한할 수 있습니다. 전체 비용은 전달된 probe 수, 중복, topology와 상태 변화에 좌우되므로 항상 “매우 효율적”이라고 단정하지 않습니다.