시간 및 전역 상태
시간 및 전역 상태는 공유 클록이 없고 즉각적인 전역 보기가 없는 분산 시스템에서 이벤트의 순서를 정하고 집합적 조건에 대해 추론하는 방식과 관련됩니다.
Definition
분산 시스템에서 이벤트는 공유 클록이 없는 별도의 프로세스에서 발생합니다. 시간 및 전역 상태 연구는 시스템이 이벤트를 인과적으로 정렬하고 일관된 전역 상태를 캡처할 수 있도록 하는 관계 및 알고리즘(논리적 및 벡터 클록, 스냅샷, 순서 지정된 전달)을 제공합니다.
Scope
이 영역은 논리적 클록과 선행 관계, 물리적 클록 동기화, 벡터 클록 및 인과성 및 동시성 감지, 일관된 전역 스냅샷 결정, 그리고 신뢰할 수 있는 멀티캐스트에 필요한 순서 보장(FIFO, 인과적, 전체)을 다룹니다. 이러한 도구들은 분산 시스템이 전역 클록이 없음에도 불구하고 '언제' 그리고 '어떤 상태'에 대한 의미 있는 진술을 할 수 있도록 합니다.
Sub-topics
Core questions
- 공유 물리적 클록 없이 서로 다른 프로세스에서 발생하는 이벤트의 순서를 어떻게 정할 수 있는가?
- 두 이벤트가 인과적으로 관련되어 있는지 또는 동시적인지 프로세스가 어떻게 판단할 수 있는가?
- 계산이 계속되는 동안 일관된 전역 스냅샷을 어떻게 기록할 수 있는가?
- 인과성을 보존하기 위해 메시지 전달에 어떤 순서 보장이 필요한가?
Key theories
- 선행 관계 및 논리적 클록
- 램포트의 선행 관계는 이벤트에 대한 부분적인 인과적 순서를 정의하며, 논리적(스칼라) 클록은 이에 일치하는 타임스탬프를 할당하여 많은 프로토콜에 대해 전체 순서를 구축하기에 충분한 클록 없는 순서 개념을 제공합니다.
- 벡터 클록 및 인과성
- 벡터 클록은 논리적 클록을 확장하여 두 타임스탬프를 비교함으로써 한 이벤트가 다른 이벤트에 인과적으로 선행하는지 또는 두 이벤트가 동시적인지를 정확하게 포착하여 정밀한 인과성 추적을 가능하게 합니다.
- 일관된 전역 스냅샷
- 챈디-램포트 스냅샷 알고리즘은 시스템을 중단시키지 않고 채널을 따라 마커를 전파함으로써 일관된 전역 상태(프로세스 상태 및 전송 중인 메시지)를 기록합니다.
Clinical relevance
논리적 및 벡터 클록은 인과적 일관성, 복제된 저장소의 충돌 감지, 분산 실행 디버깅의 기반이 됩니다. 일관된 스냅샷은 분산 체크포인트, 교착 상태 및 종료 감지, 스트림 처리 오류 복구의 기반이 됩니다.
History
램포트(Lamport)의 1978년 논문은 컴퓨터 과학에서 가장 많이 인용된 결과 중 하나인 논리적 시간과 선행 관계를 소개했습니다. 챈디(Chandy)와 램포트는 1985년에 일관된 전역 스냅샷을 공식화했으며, 피지(Fidge)와 매턴(Mattern)은 1980년대 후반에 독립적으로 벡터 클록을 개발하여 시간과 상태에 대한 추론을 위한 기초 도구 키트를 완성했습니다.
Key figures
- Leslie Lamport
- K. Mani Chandy
- Colin Fidge
- Friedemann Mattern
Related topics
Seminal works
- lamport1978
- chandy1985
- fidge1988
Frequently asked questions
- 분산 시스템이 동기화된 물리적 클록을 사용할 수 없는 이유는 무엇인가요?
- 물리적 클록은 드리프트(drift)하며 가변적인 지연이 있는 네트워크에서 완벽하게 동기화될 수 없으므로, 두 이벤트의 실시간 순서는 모호할 수 있습니다. 대신 논리적 및 벡터 클록은 정확성에 실제로 중요한 인과적 순서를 포착합니다.
- 전역 스냅샷이 '일관적'이라는 것은 무엇을 의미하나요?
- 스냅샷은 메시지 수신을 포함할 때마다 해당 메시지의 송신도 포함하는 경우 일관적입니다. 이러한 상태는 전역적으로 단일 순간이 관찰되지 않았더라도 실행 중에 발생했을 수 있습니다.