램포트 시계 & 벡터 클락

분산 시스템에서 "무엇이 먼저 일어났는가?"를 벽시계 없이 판단하는 논리적 시계

1. 왜 벽시계로는 안 되는가

모든 컴퓨터의 수정 진동자(clock)는 온도·전압에 따라 조금씩 빠르거나 느리게 간다. 이것을 클럭 드리프트(clock drift)라 하고, 그 결과 생기는 시계 차이를 클럭 스큐(clock skew)라 한다. NTP로 주기적으로 맞춰도 수 ms~수십 ms의 오차는 남는다. 네트워크 지연은 그보다 크고 들쭉날쭉하다.

2. "먼저 일어났다"의 정확한 정의 — happens-before (→)

레슬리 램포트는 1978년, 시각 대신 인과관계로 순서를 정의했다. 사건 a → b ("a가 b보다 먼저 일어났다")는 다음 세 경우다:

3. 램포트 시계 — 사건마다 +1

각 프로세스가 정수 카운터 L 하나를 갖는다.

아래 타임라인에서 프로세스 3개가 메시지를 주고받는다. 다음 단계를 눌러 사건이 하나씩 일어나는 것을 지켜보자. 각 점 위/아래 숫자가 그 사건의 논리적 시계 값이다.

4. 램포트 시계의 한계

램포트 시계는 "a → b 이면 L(a) < L(b)"를 보장한다. 하지만 역은 성립하지 않는다. 즉 L(a) < L(b)라고 해서 a가 b의 원인이라는 보장은 없다 — 그냥 서로 무관한 동시 사건인데 숫자만 다를 수 있다.

5. 벡터 클락 — 프로세스마다 칸을 따로

프로세스가 N개면, 각자 길이 N짜리 벡터 V를 갖는다. V[i]는 "프로세스 i에서 일어난 사건을 내가 몇 개나 알고 있는가"를 뜻한다.

두 벡터 비교 규칙

6. 두 사건 비교기

타임라인의 두 사건을 골라 관계를 확인해 보자. 램포트 값만으로 판단했다면 틀렸을 경우를 함께 표시한다.

7. 어디에 쓰나

8. 코드로 보기

# 프로세스 i (전체 N개) 의 벡터 클락
class VectorClock:
    def __init__(self, i, N):
        self.i = i
        self.V = [0] * N

    def local_event(self):
        self.V[self.i] += 1

    def send(self):
        self.V[self.i] += 1
        return list(self.V)          # 메시지에 벡터 사본을 실어 보냄

    def receive(self, other):
        for k in range(len(self.V)):
            self.V[k] = max(self.V[k], other[k])
        self.V[self.i] += 1

def happens_before(a, b):        # a → b ?
    return all(x <= y for x, y in zip(a, b)) and a != b

def concurrent(a, b):           # a ∥ b ?
    return not happens_before(a, b) and not happens_before(b, a) and a != b

핵심 한 줄 — 스칼라(램포트) 시계는 "순서"를 주고, 벡터 클락은 거기에 더해 "동시성"까지 구분한다.