분산 시스템의 글로벌 상태 스냅샷을 위한 Chandy-Lamport 알고리즘
전역 동기화 시계나 시스템 정지 없이 비동기 메시지 마커(Marker) 전파를 통해 분산 시스템의 일관된 글로벌 스냅샷을 캡처하는 Chandy-Lamport 알고리즘을 분석합니다.
발행·오류 제보: infostoa · 편집 기준
이 글의 개별 작성자와 전문 검토자 정보는 제공되지 않습니다.
계산을 멈추지 않고 전역 상태를 기록하는 방법
Chandy–Lamport 알고리즘은 분산 계산을 계속하면서 각 프로세스의 로컬 상태와 통신 채널에 남아 있는 메시지를 함께 기록해 의미 있는 전역 상태를 구성합니다. 모든 노드의 물리 시계를 맞춰 같은 순간에 저장하는 방식이 아닙니다. 기록된 전역 상태는 실제 한 시점에 시스템 전체가 가졌던 상태와 다를 수도 있지만, 메시지의 인과관계를 깨지 않는 일관된 경계가 됩니다.
개념도는 프로세스·마커·메시지의 방향을 그린 시각적 비유이며, 실제 시간순 추적은 아래 예에서 설명합니다.
마커와 채널 기록 규칙
원 논문은 신뢰할 수 있고 FIFO 순서를 지키며 메시지가 유한 시간 안에 전달되는 채널을 가정합니다. 스냅샷을 시작한 프로세스는 로컬 상태를 기록한 뒤 각 출력 채널에 마커를 보냅니다. 처음 마커를 받은 프로세스는 자신의 상태를 기록하고, 마커가 온 입력 채널의 상태를 비어 있다고 기록한 뒤 다른 출력 채널로 마커를 보냅니다. 이미 로컬 상태를 기록한 프로세스는 다른 입력 채널에서 마커를 받을 때까지 그 채널로 들어온 애플리케이션 메시지를 채널 상태에 기록합니다. 이 메시지 기록까지 있어야 전송은 기록됐지만 수신은 기록되지 않은 메시지를 빠뜨리지 않습니다.
가능한 이벤트 순서: A→B 메시지를 채널 상태에 담기
가능한 순서를 구체화해 보겠습니다. A→B, C→A, C→B 채널이 있고 세 프로세스가 같은 스냅샷에 참여한다고 가정합니다. 먼저 A가 메시지 m을 B로 보냅니다. C가 로컬 상태를 기록하고 A와 B에 마커를 보냅니다. A는 C의 마커를 받은 뒤 로컬 상태를 기록하고 A→B에 마커를 보냅니다. 이 마커는 그 채널에서 이후에 보낼 애플리케이션 메시지보다 먼저 보내야 하지만, 마커 뒤에 메시지를 보내는 것은 가능합니다. B에서는 C의 마커가 첫 마커이므로 B가 로컬 상태를 기록합니다. 그 뒤 A→B에서 m을 받고 A의 마커를 받습니다. m은 A의 마커보다 먼저 전송됐고 FIFO 순서로 먼저 도착하므로 B의 로컬 상태가 아니라 A→B 채널 상태에 기록됩니다.
반대로 A가 m을 보낸 뒤 스냅샷을 시작하고 B가 m을 받은 다음 A의 마커를 처음 받으면, FIFO 때문에 수신은 B의 로컬 상태에 포함되고 A→B 채널 상태는 비어 있습니다. 첫 번째 경우에는 C의 마커가 B의 첫 마커가 되도록 세 프로세스가 필요합니다. 두 순서는 설명을 위해 구성한 추적이며, 논문의 신뢰 가능한 FIFO 채널 가정에 따른 것입니다.
실제 체크포인트와 구분하기
Apache Flink 1.19는 체크포인트 배리어와 연산자 상태, 스트림 위치를 결합하며 여러 입력에서 배리어 정렬·비정렬 처리를 지원합니다. 이는 해당 버전의 엔진 구현이지 원 논문의 설명 그 자체는 아닙니다. 내부 상태를 복원할 수 있다는 사실만으로 외부 저장소 효과의 중복 방지까지 보장되지는 않습니다. 정확히 한 번 처리를 주장하려면 사용하는 소스·연산자·싱크와 복구 설정이 함께 보장하는 범위를 확인하세요.