https://lamport.azurewebsites.net/pubs/time-clocks.pdf
분산 시스템에서 이벤트 순서를 표현하기 위한 방법인 Lamport Clock을 살펴봅니다. 이 논문은 분산 시스템에서 매우 유명하며, 여러 시스템에서 보편적으로 적용하고 있습니다.
From Pekora
이 방식은 동시에 발생한 이벤트에 대하여 충돌을 해결하거나, 요청의 순서를 보장하려는 방식이 아니다.
따라서 노드들의 동기화에 대한 신경을 쓸 필요가 없다. 이 방식이 해결하고 싶은 문제는 조금 더 보편적이다.
단순히 이벤트의 발생 시각을 어떻게 나타내야하는지에 대한 문제를 해결하는 방법이다.
이벤트가 발생한 순서를 표현하는 것은 꽤나 중요한 문제입니다. 당연하겠지만 우리는 순서가 뒤틀려서 이벤트가 발생하는걸 원하지 않습니다. 예를들어, 돈을 입금하는 것과 출금하는 것은 순서대로 일어나야 성공합니다. 만약 출금이 먼저 처리된다면 출금 시도가 실패하면서 사용자는 슬퍼하겠죠.
분산 시스템에서 이벤트가 발생한 시간은 정확하지 않을 수 있습니다. 모든 컴퓨터의 시계가 정확히 같은 시간을 가르키지도 않으며, 네트워크 지연을 인하여 언제든지 뒤집힐 수 있습니다. 또한 물리적인 시계가 시간을 거슬러 올라가는 일도 발생할 수 있습니다.
따라서 우리는 이벤트의 순서를 나타내고, 그 순서를 비교하여 발생 순서를 확인할 수 있어야합니다.
Lamport는 논리 시계를 통해 이벤트의 상대적인 순서를 표현합니다. 알고리즘은 매우 간단합니다. 아래 정의된 동작은 논문에 소개된 알고리즘을 조금 각색하여 만들었습니다.
- 모든 머신은 0으로 초기화된 시계를 갖고있습니다.
- 머신은 모든 이벤트가 발생할 때마다 시계를 1 증가시킵니다. 하나의 머신에서 같은 시간을 갖는 이벤트는 발생할 수 없습니다.
- 다른 머신이 영향을 주는 경우, 그 머신의 시계 값과 자신이 가진 시계 값을 비교하여 더 큰 값의 + 1로 기록합니다.
이 방법을 사용할 경우 이벤트의 전체 순서(total order)를 보장하는 것은 불가능합니다. 영향을 준 이벤트끼리의 순서를 일부 보장합니다.
N1, N2가 A~H의 이벤트가 발생하면서 상호작용시 Lamport Clock의 시간 값이 어떻게 변하는지 나타냈습니다. 예를들자면, LC(A) = 1라는 문장이 있을 때, LC(A)는 A이벤트에 대한 Lamport Clock의 시간 값을 나타내며, 이 값이 1이라는 의미입니다.
Lamport Clock은 X 이벤트가 Y 이벤트에 영향을 주었다면 LC(X) < LC(Y)가 항상 성립합니다. 하지만, 역으로 LC(X) < LC(Y)라고 해서 항상 영향을 주었다는 것을 보장하지는 못합니다.
From Pekora
위 경우에서 LC(X) 값을 구해보세요!
Vector Clock은 Lamport Clock의 개선된 버전입니다.
From Pekora
자세한 내용은 partial order & total order을 확인해주세요. 이 글에서는 위 내용을 어느정도 알고있다는 전제 하에 이야기합니다.