글로벌 스냅샷 및 상태

글로벌 스냅샷은 분산 컴퓨테이션의 상태(각 프로세스의 로컬 상태와 전송 중인 메시지)에 대한 일관된 뷰를 시스템을 정지시키지 않고 포착합니다.

Definition

일관된 글로벌 상태는 일관된 컷(cut)에 해당하는 로컬 프로세스 상태 및 채널 내용의 집합입니다. 여기서 일관된 컷이란 기록된 모든 메시지 수신에 대해 해당 송신도 기록되는 것을 의미하며, 이는 전역적인 순간이 관찰되지 않았음에도 불구하고 해당 상태가 컴퓨테이션 중에 발생했을 수 있음을 나타냅니다.

Scope

이 주제는 일관된 글로벌 상태의 개념과 이를 정의하는 컷(cut), Chandy-Lamport 마커 기반 스냅샷 알고리즘 및 그 가정(FIFO 채널, 신뢰할 수 있는 전달), 그리고 종료 및 교착 상태 감지와 같은 안정적인 속성 감지 및 분산 체크포인트 및 복구에 대한 스냅샷의 적용을 다룹니다.

Core questions

• 기록된 글로벌 상태가 불가능한 상태가 아닌 일관된 상태가 되게 하는 요인은 무엇입니까?
• 컴퓨테이션이 계속 실행되는 동안 이러한 상태를 어떻게 기록할 수 있습니까?
• 스냅샷에서 종료 및 교착 상태와 같은 안정적인 속성은 어떻게 감지됩니까?

Key theories

일관된 컷(Consistent cuts)

글로벌 상태는 프로세스 이벤트 시퀀스에 걸친 컷에 해당합니다. 컷은 happened-before 관계에 대해 닫혀 있을 때 일관적이며, 기록된 상태에서 메시지가 전송되기 전에 수신되지 않도록 보장합니다.

Chandy-Lamport 스냅샷 알고리즘

시작자는 자신의 상태를 기록하고 각 송신 채널에 마커를 보냅니다. 각 프로세스는 마커를 처음 수신하면 자신의 상태를 기록한 다음, 다른 채널에서 마커가 도착할 때까지 수신 메시지를 기록하여 채널 내용을 포착합니다.

안정적인 속성 감지

스냅샷은 시스템이 있을 수 있었던 상태를 포착하므로, 스냅샷에서 감지된 안정적인 속성(종료 또는 교착 상태와 같이 일단 참이 되면 계속 참인 속성)은 실제로 참이므로, 스냅샷은 일반적인 감지 도구가 됩니다.

Clinical relevance

스냅샷 알고리즘은 오류 복구를 위한 분산 체크포인트/재시작을 지원하며, 여기에는 정확히 한 번(exactly-once) 보장을 제공하기 위해 최신 스트림 처리 엔진에서 사용되는 비동기 스냅샷, 그리고 장기 실행 컴퓨테이션에서의 교착 상태 및 종료 감지가 포함됩니다.

History

Chandy와 Lamport의 1985년 알고리즘은 시스템을 중단시키지 않고 일관된 글로벌 상태를 기록하는 최초의 실용적인 방법을 제시했습니다. Mattern과 다른 연구자들은 기본 컷 이론을 일반화했으며, 이 기술은 이후 내결함성 스트림 처리의 기초가 되었습니다.

Key figures

• K. Mani Chandy
• Leslie Lamport
• Friedemann Mattern

Seminal works

• chandy1985
• mattern1989
• lynch1996

Frequently asked questions

스냅샷을 찍으려면 시스템을 일시 중지해야 합니까?

아닙니다. Chandy-Lamport 알고리즘은 컴퓨테이션이 계속되는 동안 채널을 따라 마커를 전파하여 일관된 글로벌 상태를 기록합니다. 기록된 상태는 시스템이 전역적으로 정지된 적이 없더라도 시스템이 있을 수 있었던 상태입니다.