Fidge, C.J., Timestamps in Message-Passing Systems that Preserve the Partial Ordering, Proc. 11th Australian Comp. Sci. Conf., 1988, pp. 56-66.
Timestamping is a common method of totally ordering events in concurrent programs. However, for applications requiring access to the global state, a total ordering is inappropriate. This paper presents algorithms for timestamping events in both synchronous and asynchronous message-passing programs that allow for access to the partial ordering inherent in a parallel system. The algorithms do not change the communication graph or require a central timestamp issuing authority.
이 논문은 Vector Clock으로 알려진 개념을 소개하고 있다. Vector Clock은 [Fidge 1998]과 [Mattern 1998]에서 독립적으로 고안된 알고리즘인데, Fidge의 논문쪽이 좀 더 읽기 쉬운 편이라고 한다.
Limitation of Lamport’s logical clock
Clock Condition. For any events a, b:
if a → b then C(a) < C(b).
Lamport가 정의한 논리적 시계는 두 사건 사이의 happened-before 관계가 있다면 이를 반영하는 시계를 정의하고 있습니다. 그리고 이를 이용해 임의의 완전순서를 정의하고 있습니다. 이 완전순서는 임의의 프로세스 사이의 순서를 이용하고 있으므로 사건들을 정렬할 수 있는 방법 중의 임의적인 한 방법이고, 논리적 시계 이상의 어떤 정보가 추가되지는 않습니다.
Lamport가 정의한 논리적 시계의 문제는 이 논리적 시계를 통해서 사건들 사이의 인과성 (causality)를 알아낼 수 없다는 것입니다. 즉, C(a) < C(b)라고 해서 a → b라고 말할 수 없는 것입니다. 구체적으로 말해, C(a) < C(b)가 의미할 수 있는 것은 a와 b 사이에 happend-before 관계가 있는 것, 즉 a → b인 경우와, a와 b 사이에 happend-before 관계를 판단할 수 없고 b가 a에 대해 happened-before가 아닌 것, 즉 b ↛ a인 경우가 있습니다.
Vector Clock
Vector Clock이라는 단어를 논문에서 사용하고 있지는 않지만, 그 단어가 의미하듯이 논리적 시계의 타임스탬프를 integer가 아니라 다음과 같이 프로세스 수 만큼의 타임스탬프를 가진 배열로 대체하고 있습니다.
[c1, c2 … cn]
그리고 이 타임스탬프를 유지하기 위한 알고리즘은 아래와 같습니다. 타임스탬프가 배열이 되었다는 것 이외에 Lamport의 알고리즘과 큰 차이가 없다고도 얘기할 수 있겠지만, 주의를 기울여야 하는 부분은 메시지를 수신하는 프로세스에서는 메시지를 송신한 프로세스에 해당하는 타임스탬프 배열 항목의 값만을 증가시킨다는 것입니다.
Rule RA 1: Initially all values are zero.
Rule RA 2: The local clock value is incremented at least once before each atomic event
Rule RA 3: The current value of entire timestamp array is piggybacked on every outgoing signal
Rule RA 4: Upon receiving a signal, a process sets the value of each entry in the timestamp array to be the maximum of the two corresponding values in the local array, and in the piggybacked array received. The value corresponding to the sender, however, is a special case and is set to be one greater than the value received (to allow for transit time), but only if the local value is not already greater than that received (to allow for signal “overtaking” as described below), i.e.
q?other_array; /* receive timestamp array from process q */ if local_array[q] <= other_array[q] then local_array[q] := 1 + other_array[q]; for i := 1 to n do local_array[i] := max(local_array[i], other_array[i]);Rule RA 5: Values in the timestamp arrays are never decremented.
이 논문에서는 설명하고 있지 않지만, 이러한 알고리즘으로 얻어지는 타임스탬프의 의미는 수신한 메시지에 근거해서 추측할 수 있는 가장 정확한 송신 측의 타임스탬프라는 것입니다. 또한, 수신한 프로세스에서 발생할 현재의 사건에 대해 happened-before 관계에 있는 송신 측의 프로세스의 가장 마지막 사건의 타임스탬프이기도 합니다.
이러한 타임스탬프 배열은 다음과 같이 비교될 수 있습니다.
각각 프로세스 p, q에서 실행된 사건 e, f를 ep, fq로 나타내고, 각 사건에 대한 타임스탬프 array를 Tep, Tfq, 그 타임스탬프 배열 중 프로세스 p에 해당하는 타임스탬프를 Tep[p], Tfq[p] 라고 할 때,
ep → fq iff Tep[p] < Tfq[p]
여기서 주목할 점은 iff 즉, 사건의 happened-before 관계와 타임스탬프의 대소 관계가 동치관계라는 것입니다. 임의의 두 사건이 주어졌을 때 인과성이 있는지 여부와 어떤 사건이 어떤 사건에 대해 인과성이 있는지를 판단할 수 있습니다.
ep ↔ fq if Tep[p] ≮ Tfq[p] and Tfq[p] ≮ Tep[p]
타임스탬프 사이의 대소 관계가 어느 방향으로도 성립하지 않는다면 두 사건은 동시적(concurrent)하다고 얘기할 수 있습니다.
Applications
그렇다면 논리적 시계를 통해서 인과성을 알아내는 것은 왜 필요한가에 대해서 이 논문이 예로 들고 있는 것 중 하나는 여러 프로세스들에 의해서 저장되는 상태의 스냅샷들에 타임스탬프를 이용해서, 전체 프로그램 상태에 대해 정상적인 상태인지 검사를 할 수 있고 이를 통해 역실행 (reverse execution), 에러의 복구, 롤백 등이 가능하다는 것입니다. 실제로 이후에 발표된 Dynamo나 Riak 등 Vector Clock을 이용하는 것으로 알려진 시스템에서는 동시적인 쓰기 등에 의해 어떤 데이터에 대해 2개 이상의 복제본이 발생했을 때 이를 해소하기 위해서 인과성을 활용하고 있는 사례를 볼 수 있습니다.
References
- [Fidge 1998] Fidge, C.J., Timestamps in Message-Passing Systems that Preserve the Partial Ordering, Proc. 11th Australian Comp. Sci. Conf., 1988, pp. 56-66.
- [Mattern 1998] Mattern, F. Virtual time and global states of distributed systems. Proc. “Parallel and distributed algorithms” Conf., (Cosnard, Quinton, Raynal, Robert Eds), North-Holland, 1988, pp. 215-226.