위키득계정 ↗
기술

람포트 시계

람포트 시계기술
영어
Lamport clock
종류
스칼라 논리 시계
보존하는 관계
인과적 선후 관계
한계
번호 비교만으로 인과관계 확정 불가
람포트 시계는 분산 시스템의 사건에 논리적 번호를 붙여 인과적 선후 관계와 모순되지 않는 순서를 만드는 방식이다. 실제 시각이나 경과 시간을 측정하는 시계가 아니라 프로세스의 사건과 메시지 전달 순서를 표현한다.

사건의 선후 관계

한 프로세스에서 먼저 실행한 사건은 뒤의 사건에 선행한다. 메시지를 보내는 사건은 그 메시지를 받는 사건보다 앞선다. 이런 관계를 연결해서 선후 관계를 확장한다. 어느 방향으로도 연결되지 않는 두 사건은 이 모형에서 동시적이며 반드시 같은 물리적 순간에 발생했다는 뜻은 아니다.

번호 갱신

일반적인 정수 구현은 각 사건을 처리할 때 로컬 번호를 증가시킨다. 메시지에는 보내는 쪽의 번호를 싣고 수신자는 자신의 번호와 받은 번호 중 큰 값보다 더 큰 번호를 수신 사건에 붙인다. 따라서 메시지가 전해지는 경로에서 번호가 거꾸로 흐르지 않는다.

역으로 추론할 수 없는 것

a가 b에 인과적으로 선행하면 C(a)<C(b)다. 그러나 번호가 작다는 사실만으로 a가 b의 원인이라고 결론 내릴 수는 없다. 예를 들어 서로 통신하지 않은 두 프로세스의 사건에도 서로 다른 번호가 붙을 수 있다. 번호의 차이 역시 실제 시간 차이를 나타내지 않는다.

전체 순서 만들기

서로 다른 프로세스의 사건에 같은 논리 번호가 붙으면 고정된 프로세스 식별자 순서 등을 함께 사용해 순서를 정할 수 있다. 이렇게 만든 전체 순서는 인과적 선후 관계를 존중하지만 동시적인 사건의 순서는 추가 규칙이 정한 것이다. 모든 사건이 실제로 그 순서대로 실행됐다는 뜻으로 해석해서는 안 된다.

관련 문서

분산 시스템 / 프로세스 / 네트워크 / 동시성 / 부분 순서 / 전순서 / CRDT / 알고리즘