램포트 시계 & 하이브리드 시계

램포트 시계 & 하이브리드 시계 — 분산 시스템에서 시간을 다루는 법

1. 문제: 분산 시스템에 "지금"은 없다

서버들의 물리 시계는 어긋난다. NTP로 동기화해도 수 ms의 오차(clock skew)가 남고,
가상머신에서는 시계가 멈췄다 튀기도 하며, NTP 보정 과정에서 한 노드의 시계가 뒤로
점프하기도 한다. 시계가 뒤로 가면 "나중 사건이 더 작은 타임스탬프"를 받아 순서가 꼬인다.

그런데 곰곰이 보면, 우리가 정말 필요한 것은 "몇 시 몇 분"이라는 절대 시각이 아니라 대부분
"어떤 사건이 어떤 사건보다 먼저였는가"라는 순서다. Lamport의 1978년 논문("Time, Clocks,
and the Ordering of Events")의 통찰이 바로 이것이다. 시계를 버리고 순서만 남기자.

happened-before 관계

사건 a가 사건 b보다 먼저 일어났다(happened-before, a → b) 고 말할 수 있는 경우는 세
가지뿐이다.

1. 같은 프로세스에서 a가 b보다 먼저 실행됐다.
2. a가 메시지 송신이고 b가 그 메시지의 수신이다.
3. a → c이고 c → b인 c가 있다(추이성).

이 셋으로 연결되지 않는 두 사건은 동시(concurrent) 다.

2. 램포트 시계 (Lamport Clock)

규칙 세 개짜리 알고리즘

각 노드는 정수 카운터 하나를 들고, 규칙 세 개를 따른다.

1. 로컬에서 사건이 일어나면: counter += 1
2. 메시지를 보낼 때: counter를 메시지에 실어 보냄
3. 메시지를 받을 때: counter = max(내 counter, 받은 counter) + 1

3번이 핵심이다. 메시지를 받는 순간 상대의 시간까지 반영해 내 시계를 앞으로 당긴다.
이 규칙 덕분에 다음이 보장된다.

a → b 이면 L(a) < L(b)

인과적으로 앞선 사건은 반드시 더 작은 타임스탬프를 갖는다. 물리 시계 없이, 정수 하나로.

예제로 직접 돌려보기

노드 A, B, C의 카운터가 모두 0에서 시작한다.

A: a1 발생        → counter = 1          (a1 = 1)
   B에게 전송      → 메시지에 1을 실음
B: 수신 = b1      → max(0, 1) + 1 = 2   (b1 = 2)
   b2 발생        → counter = 3          (b2 = 3)
C: c1 발생        → counter = 1          (c1 = 1)   ← C는 아무와도 통신 없음
   c2 발생        → counter = 2          (c2 = 2)

인과 사슬 a1 → b1 → b2를 따라 타임스탬프가 1 < 2 < 3으로 증가하는 것을 확인할 수 있다.
a1과 c1이 같은 타임스탬프 1을 갖는 것도 눈여겨보자. 동시 사건에서는 자연스러운 일이다.

역은 성립하지 않는다 — 이 패턴의 가장 중요한 문장

위 예제에서 c2 = 2 < b2 = 3이다. 그렇다면 "c2가 b2보다 먼저 일어났다"고 결론 내릴 수
있을까? 없다. B와 C는 통신한 적이 없으므로 두 사건은 동시이고, 숫자의 대소는 인과에
대해 아무것도 말해주지 않는다.

a → b 이면 L(a) < L(b)        ← 보장됨
L(a) < L(b) 라고 a → b는 아님  ← 동시 사건도 대소는 생긴다

여기서 정밀한 구분이 필요하다. 타임스탬프의 값 비교는 언제나 가능하다(램포트 시계는
결정적 알고리즘이다). 알 수 없는 것은 값이 아니라 그 대소가 의미하는 바다. "비교할 수
없다"와 "비교할 수 있지만 인과로 해석하면 안 된다"는 다른 진술이고, 이 구분이 흐려지면 설계
실수로 이어진다. 예컨대 LWW에 램포트 타임스탬프를 쓰면 항상 승자를 고를 수는 있지만, 그
승자가 "진짜 나중 쓰기"라는 보장은 없다. 버전 벡터라면 이 경우를 충돌로 보고했을 것이다.

즉 램포트 시계는 동시성을 감지할 수 없다. 버전 벡터와의 관계는 압축의 트레이드오프다.
버전 벡터는 노드 수만큼의 공간을 쓰는 대신 인과 관계를 온전히 보존하고, 램포트 시계는 정수
하나로 압축하는 대신 동시성 정보를 버린다.

전순서 만들기

타임스탬프가 같은 두 사건은 노드 ID로 타이브레이크하면 모든 사건의 전순서(total order)
를 만들 수 있다: (counter, nodeId) 쌍으로 비교. "정답인 순서"가 아니라 "모두가 동의하는
임의의 순서"지만, 인과율을 위반하지 않는다는 것이 중요하다.

실전에서는 순수한 램포트 시계 그대로보다 그 아이디어가 스며든 형태로 만난다. MVCC 저장소의
버전 번호(Versioned Value 패턴), etcd의 revision 번호가 그 예다.

3. 하이브리드 시계 (Hybrid Logical Clock, HLC)

문제: 램포트 시계는 사람의 시간과 무관하다

램포트 시계의 값은 인과율은 지키지만 실제 시각과 아무 관계가 없는 정수다. 두 가지가
아쉽다. 첫째, "어제 오후 3시 시점의 데이터 상태를 보여줘" 같은 시각 기반 쿼리가
불가능하다 — 3시가 램포트 값 몇에 해당하는지 알 길이 없다. 둘째, 통신이 잦은 노드의
카운터만 치솟는 식으로 값이 물리적 시간과 제멋대로 어긋난다.

그렇다고 물리 시계로 돌아가면 원점이다. 시계는 어긋나 있고, NTP 보정으로 뒤로 점프하면
인과율이 깨진다. 원하는 것을 정리하면:

1. 값이 실제 시각과 가깝고
2. 인과율을 보존하며 (a → b이면 반드시 증가)
3. 물리 시계가 뒤로 가도 절대 역행하지 않는 타임스탬프

이 셋을 동시에 잡는 것이 HLC다.

구조: 물리 시각 + 논리 카운터

HLC = (l, c)
  l: 지금까지 관측한 물리 시각의 최댓값   ← "대략 몇 시인지"
  c: 같은 l 안에서 순서를 세는 논리 카운터 ← "l이 못 전진할 때의 램포트 카운터"

동작 원리는 램포트 시계의 max 규칙을 물리 시계와 합친 것이다.

로컬 사건/송신 시: 내 물리 시계 pt를 읽어서, pt가 현재 l보다 크면 l = pt, c = 0으로
전진한다(정상 상황). pt ≤ l이면 — 시계가 뒤로 갔거나 같은 밀리초 안에 여러 사건이 난 경우 —
l은 그대로 두고 c만 올린다.

수신 시: 램포트의 max 규칙 그대로 l = max(내 l, 메시지의 l, 내 pt)를 취하고, 최댓값이
어디서 왔느냐에 따라 c를 정한다. 내 pt가 제일 크면 c = 0, 메시지의 l이 제일 크면
c = 메시지의 c + 1, 내 l과 같으면 c = max(내 c, 메시지의 c) + 1.

요컨대 "l은 최대한 물리 시각을 따라가되, 따라갈 수 없을 때만 c로 순서를 만든다" 이다.

class HybridClock(private val wallClock: () -> Long) {
    private var l = 0L  // 관측된 최대 물리 시각
    private var c = 0L  // 논리 카운터

    @Synchronized
    fun now(): HlcTimestamp {                    // 로컬 사건/송신
        val pt = wallClock()
        if (pt > l) { l = pt; c = 0 } else c++   // 시계 역행/정체 시 c로 전진
        return HlcTimestamp(l, c)
    }

    @Synchronized
    fun onReceive(remote: HlcTimestamp): HlcTimestamp {
        val pt = wallClock()
        val newL = maxOf(l, remote.l, pt)
        c = when (newL) {
            l, remote.l -> maxOf(if (newL == l) c else 0,
                                 if (newL == remote.l) remote.c else 0) + 1
            else -> 0                             // 내 물리 시계가 최신
        }
        l = newL
        return HlcTimestamp(l, c)
    }
}

비교는 (l, c) 사전순(l 먼저, 같으면 c)이다. 구현 디테일 하나 — l에 밀리초 48비트, c에
16비트를 쓰면 전체가 64비트 정수 하나에 들어간다. 기존에 타임스탬프를 long으로 저장하던
시스템에 그대로 끼워 넣을 수 있다는, 채택을 결정지은 실용적 장점이다.

시계 역행 시나리오 — l은 절대 뒤로 가지 않는다

노드 A의 HLC가 (10:00.005, 0)인 상태에서 NTP 보정으로 물리 시계가 10:00.002로 뒤로
점프했고, 직후 로컬 쓰기가 두 번 들어왔다고 하자.

현재 상태: l = 10:00.005, c = 0
물리 시계: 10:00.002로 역행

첫 번째 쓰기: pt(10:00.002) ≤ l(10:00.005) → l 유지, c++ → (10:00.005, 1)
두 번째 쓰기: pt 여전히 ≤ l               → l 유지, c++ → (10:00.005, 2)
...
물리 시계가 10:00.006 도달: pt > l → l = 10:00.006, c = 0

여기서 흔한 착각이 "물리 시계를 따라 (10:00.002, 0)을 발급한다"는 것인데, 그러면 이미
발급된 (10:00.005, 0)보다 작은 타임스탬프가 나중 쓰기에 붙는다. 이 타임스탬프로 MVCC
버전을 정렬하는 저장소라면 나중 쓰기가 과거에 삽입되는 것이고, 같은 노드 안에서조차
인과율이 깨진다. l은 "내 물리 시계"가 아니라 "관측된 물리 시각의 최댓값"이며, max로만
갱신되므로 구조적으로 역행이 불가능하다. c는 물리 시계의 역행·정체로부터 타임스탬프의
단조성을 지키는 완충재다.

무엇이 보장되는가

인과율: a → b이면 HLC(a) < HLC(b). 램포트 시계의 성질이 그대로 유지된다. 역은 여전히
성립하지 않는다 — HLC도 동시성 감지는 못 한다. 그것은 버전 벡터의 일이다.

물리 시각 근접성: 노드들의 시계가 NTP로 ε 이내로 동기화되어 있다면, l과 실제 시각의
차이도 ε 수준으로 유계다. "오후 3시 시점"을 HLC 값으로 번역하는 것이 (ε의 오차 안에서)
가능해지고, 시각 기반 스냅샷 읽기가 열린다.

단조성: 물리 시계가 뒤로 점프해도 HLC는 절대 뒤로 가지 않는다.

실전 — 누가 왜 쓰는가

MongoDB는 클러스터 시간(cluster time)으로 HLC를 쓰고, 세션의 인과적 일관성(causal
consistency)을 이것으로 구현한다. 클라이언트가 마지막으로 본 HLC를 들고 다니면서 "이 시각
이후의 상태를 보여달라"고 요구하는 방식이다. CockroachDB, YugabyteDB는 분산 트랜잭션의
타임스탬프 정렬과 MVCC 스냅샷에 쓴다.

비교 대상으로 Google Spanner의 TrueTime이 있다. Spanner는 데이터센터에 GPS·원자시계를
설치해 "지금 시각은 [t-7ms, t+7ms] 사이"라는 유계 불확실성 구간을 하드웨어로 보장받고,
커밋 시 그 구간만큼 기다려서(commit-wait) 전역 순서를 만든다. HLC는 그런 하드웨어 없이
소프트웨어만으로 비슷한 효과를 노리는 접근이다. 불확실성 구간을 기다리는 아이디어는 책의
다음 패턴인 시계 제한 대기(Clock-Bound Wait)로 이어진다.

4. 정리 — 세 시계의 지도

시간 관련 도구 세 개를 한 줄씩으로 정리하면:

도구	형태	인과율 보존	동시성 감지	실시각 근접
램포트 시계	정수 1개	O	X	X
버전 벡터	노드별 카운터 맵	O	O	X
하이브리드 시계	(물리 시각, 카운터)	O	X	O

HLC는 버전 벡터의 대체재가 아니라 램포트 시계의 상위 호환이다. 동시성 감지가 필요하면
여전히 버전 벡터(또는 그 정보를 보존하는 다른 수단)가 필요하고, "모두가 동의하는, 실시각에
가까운, 절대 역행하지 않는 순서"가 필요하면 HLC가 답이다.

참고 자료

• 『30가지 패턴으로 배우는 분산 시스템 설계와 구현 기법』 — 램포트 시계, 하이브리드 시계