The concept of one event happening before another in a distributed system is examined, and is shown to define a partial ordering of the events. A distributed algorithm is given for synchronizing a system of logical clocks which can be used to totally order the events. The use of the total ordering is illustrated with a method for solving synchronization problems. The algorithm is then specialized for synchronizing physical clocks, and a bound is derived on how far out of synchrony the clocks can become.
이 논문에 대해서는 Paxos Made Simple에서 이미 아래와 같은 소개를 한 적이 있습니다.
Leslie Lamport는 분산 컴퓨팅 분야에서는 너무나 유명한 분이기 때문에 따로 설명할 필요가 없을 정도입니다. 예를 들어, 1978년에 출판된 “Time, Clocks, and the Ordering of Events in a Distributed System”과 같은 페이퍼는 인용 회수로 볼 수 있는 그 영향력 뿐만 아니라 OS 수업의 읽기 과제로도 빠질 수 없는 그야말로 seminal work입니다.
1. “Happened before” 관계
가장 먼저, “Happened before” 관계라는 분산시스템 내에서 사건(event)들의 순서를 표현할 수 있는 부분순서(partial ordering)를 제안하고 있습니다.
“Happened before” relation은 분산시스템에서 구현이 어려운 물리적 시계 (physical clock)를 사용하지 않더라도 사건들의 순서를 표현할 수 있음을 보여주고 있습니다. 즉, 사건이 발생한 전역적으로 통용되는 시각을 알지 못해도 우리는 자연스럽게 사건의 순서를 정할 수 있습니다.
또한, 서로 다른 프로세스 사이에서 메시지를 주고 받을 경우에 사건 사이의 인과성(causality)이 발생하는 것을 다음과 같은 정의에 담고 있습니다.
Definition. The relation → on the set of events of a system is the smallest relation satisfying the following
three conditions:
- If a and b are events in the same process, and a comes before b, then a → b.
- If a is the sending of a message by one process and b is the receipt of the same message by another process, then a → b.
- If a → b and b → c then a → c.
Two distinct events a and b are concurrent if a ↛ b and b ↛ a. Assume a ↛ a for any event a. So → is an irreflexive partial ordering on the set of all events in the system.
2. Logical Clocks
논리적 시계는 하나의 프로세스 내의 각 사건들에 대해 단조 증가하는 숫자를 할당하는 것으로 볼 수 있으며, 물리적 시계가 아니라 사건이 발생한 순서에 기초해야 합니다.
Clock Condition. For any events a, b:
if a → b then C(a) < C(b).
“Happened before” 관계의 정의에 따라, 각 프로세스는 사건이 발생할 때마다 증가하는 타임스탬프를 부여하며, 프로세스 사이에 메시지를 송신할 때 타임스탬프를 함께 송신하며, 메시지를 수신하는 측에서는 수신한 타임스탬프보다 더 큰 타임스탬프를 새로운 사건에 할당합니다.
3. Ordering the Events Totally
위에서 정의된 논리적 시계만으로는 분산시스템 내의 사건들의 완전순서(total ordering)는 불가능하기 때문에, 프로세스 사이의 임의의 순서(!)를 도입해, 완전순서를 만들 수 있습니다.
In case two or more events occur at the same time, an arbitrary total ordering ≺ of processes is used. To do this, the relation ⇒ is defined as follows:
If a is an event in process Pi and b is an event in process Pj , then a ⇒ b if and only if either:
i. Ci<a> < Cj<b> or
ii. Ci<a> = Cj<b> and Pi ≺ Pj
이렇게 정의된 완전순서를 이용해 분산시스템에서의 상호배제(mutual exclusion) 문제를 해결하는 방법을 제시하고 있습니다.
간단히 얘기하면, 어떤 프로세스가 자원을 요청할 때는 자신의 타임스탬프를 함께 다른 모든(!) 프로세스들에게 전송하고, 이 자원의 요청은 요청한 프로세스 뿐만 아니라 모든 프로세스의 큐에 위에서 정의된 완전순서대로 정렬됩니다. 이 큐에서 가장 앞에 있는 자원 요청이 자원을 획득해야한다고 볼 수 있는데, 모든 프로세스들이 동일한 큐를 유지해야하기 때문에, 자원 획득을 위해서는 모든 다른 프로세스들로부터 receipt 메시지를 수신한 조건에서만 자원 획득이 가능합니다. 또한, 다른 프로세스의 자원 요청에 대한 응답과 자신의 자원 요청의 (타임스탬프의 순서는 올바르다고 하더라도) 전송 순서가 바뀌는 경우는 두 프로세스 사이의 통신은 순서대로 일어난다는 가정에 의해 발생하지 않습니다.
이 구현은 1개 이상의 프로세스의 실패나 메시지의 소실 등을 가정하고 있지 않기 때문에 현실적으로 사용할 수 있는 알고리즘은 아니지만, 분산시스템에서의 완전순서의 유용성을 보여주고 있다고 생각합니다. 그리고, Lamport가 이후에 제안한 Paxos가 바로 현실적인 환경 하에서의 완전순서를 보장하기 위한 방법을 제공하고 있는 것으로 보입니다.
4. Anomalous Behavior
위에서 제시한 상호배제 알고리즘에서 사건 사이의 인과성이 외부화됨으로써 발생할 수 있는 문제를 제시하고 있습니다. 예를 들어, 자원 요청 A를 한 후, 전화를 걸어 다른 컴퓨터에서 자원 요청 B를 한 경우, 자원 요청 A와 자원 요청 B 사이에는 실제로 인과성이 존재하지만, 논리적 시계의 체계는 이를 인지하지 못하므로, 자원 요청 B가 더 낮은 타임스탬프를 획득해 먼저 자원을 획득할 수 있다는 것입니다.
이를 해결하기 위한 방법으로 2가지 방법을 제시하고 있는데, 첫번째는 “happened-before” 관계에 필요하지만 외부화된 정보를 시스템 내로 도입하는 것입니다. 즉, 자원 요청 B를 하는 사용자에게 자원 요청 A 보다 더 이후의 타임스탬프를 발급하도록 자원요청 A의 타임스탬프를 전화를 통해 알려주는 방법 등으로 논리적 시계 체계를 유지하는 책임을 부여하는 것입니다.
다른 방법은 외부화된 사건들 사이의 관계를 포함해 모든 사건들을 정렬할 수 있는 물리적인 시계의 체계를 구성하는 것입니다. 이 시계들은 다음의 Strong Clock Condition을 만족해야 합니다.
Let S be the set of all system events and S be the set containing S along with relevant events external
to the system. Let ↪ denote the “happened before” relation for S.For any events a, b in S: if a ↪ b then C<a> < C<b>.
5. Physical Clocks
Strong Clock Condition을 만족하기 위해서는 물리적 시계는 다음과 같은 조건을 만족해야합니다.
Let Ci(t) denote the reading of clock Ci at physical time t. Assume that Ci(t) is a continuous, differentiable
function of t except for isolated discontinuities introduced by clock resets.
PC1. There exists a constant k << 1 such that for all i: |dCi(t) / dt – 1| < k.
PC2. For all i, j : |Ci(t) – Cj(t)| < e.
PC1은 물리적 시계가 가는 속도가 물리적 시간이 흐르는 속도와 일정 오차 범위 내에 있다는 것을 의미합니다. 일반적인 수정 발진 방식의 시계의 경우, k는 약 10-6정도로 언급하고 있으며, PC1 자체는 만족되는 것으로 가정하고 있습니다.
한편, PC2는 물리적 시계들 사이의 오차가 일정 범위 내에 있다는 것을 의미합니다. PC2를 보장하기 위해서 물리적 시계의 보정을 위한 구현 방법을 제시하고 있습니다.
Let vm = t’ – t be the total delay of m which is unknown to the receiving process. Let µm be some minimum delay >= 0 known by the receiving process such that µm <= vm.
IR2′. a. If Pi sends a message m at physical time t, then m contains a timestamp Tm = Ci(t).
b. Upon receiving a message m at time t’, process Pj sets Cj(t’) equal to max(Cj(t’ – 0), Tm +
µm).
메시지에 타임스탬프를 넣어서 보내고, 이를 수신하는 측에서는 메시지를 통해 받은 타임스탬프와 최소 통신 지연 시간 이후의 시각으로 시계를 재설정하는 방식이라고 할 수 있고, 이러한 구현 요구사항을 만족한다면, PC2를 만족하는 것을 증명할 수 있다고 합니다. 이 증명에서는 일정 시간 내에 메시지가 전체 프로세스 사이로 전송되는 상황을 가정하고 있으므로, 메시지를 주고 받지 않는 조건을 염두에 두고 있는 것 같지는 않습니다.
한편, 최소 지연시간에 해당하는 µm은 일반적으로 거리와 빛의 속도로 계산할 수 있는 수준의 값으로 언급되고 있습니다. 그리고, 주어진 µm에 대해 k와 e가 얼마나 작아야 하는지에 대한 계산 방법도 설명하고 있습니다.
현실적으로는 이 논문에서 정의된 Physical Clock은 항상 가장 빠른 시계에 맞춰지게 되므로 실제 시간 (physical time)보다 더 빨라지게 되겠지만, 분산시스템의 동기화 문제를 해결하는 능력과는 무관하다고 할 수 있을 것 같습니다.
6. Closing
이 논문은 분산시스템의 문제에 대한 이해에 가장 중요한 사고 도구로 사용할 수 있는 중요한 개념들을 정의하고 있는 것 같습니다. 내용 자체를 정확하게 이해했는지의 여부를 차치하더라도, 이러한 개념이 마음에 와닿기 위해서는 몇 번은 더 읽어봐야 할 것 같습니다.
다음에는 Vector Clock에 관한 논문인 C. Fidge의 Timestamps in Message-Passing Systems That Preserve the Partial Ordering을 읽어볼 예정입니다.