18장. 순서가 시각보다 중요하다 — Lamport 논리적 시계

만화로 보는 요약 — 먼저 읽어보세요

만화로 보는 요약 — 먼저 읽어보세요

믿을 수 없는 물리 시각 → 메시지 순서로 올리는 논리 카운터 → 순서는 만들되 인과까지 증명하지 못하는 Lamport 시계.

면접 실전 질문: ① happened-before 관계는 어떤 조건으로 정의되는가? ② Lamport 논리 시계의 로컬·발신·수신 규칙은? ③ C(a) < C(b)가 인과관계를 증명하지 못하는 이유는?

시각을 포기하고 무엇이 무엇보다 먼저 일어났는지만 세면, 흔들리는 시계 없이도 순서를 지킬 수 있다 — 다만 그 순서가 진짜 인과관계라는 보장은 어디에도 없다.

면접 실전 질문: ① happened-before 관계는 어떤 세 조건으로 정의되고, “동시적(concurrent)“은 정보 부족이 아니라 무엇을 뜻하는가? ② Lamport 논리적 시계 알고리즘의 세 규칙은 무엇인가? ③ C(a) < C(b)라는 사실이 왜 “a가 b의 원인이다”를 증명하지 못하는가?

배경 — 시계를 더 잘 맞추는 대신, 시계를 버린다

17장은 한 가지를 확인하고 끝났습니다. 아무리 NTP로 정교하게 맞춰도, 두 서버의 시계는 한 번도 완전히 같은 시각을 가리킨 적이 없다는 것. 그리고 그 어긋남 위에서 “타임스탬프가 더 늦은 쪽이 이긴다”는 last-write-wins가 실제로 나중에 일어난 쓰기를 조용히 지워버리는 걸 봤습니다. 17장의 마지막 질문은 이거였죠. 시각을 아예 묻지 않고, 오직 순서만 기록하는 시계가 있다면 어떨까?

여기서부터 지금까지의 모든 장과 다른 방향으로 갑니다. 1장부터 17장까지, 이 책은 시계를 더 정확하게 만드는 이야기였습니다. 표준시로 통일하고, 원자시계로 초를 정의하고, NTP로 오차를 줄이고. 이번 장은 그 노력을 그만둡니다. 시계를 고치는 대신, 애초에 시계가 필요했던 이유를 다시 봅니다.

분산 시스템에서 시각을 알고 싶은 진짜 이유는 대개 하나입니다. 무엇이 무엇보다 먼저 일어났는지 알고 싶은 것. “이 쓰기가 저 읽기보다 먼저였나?”, “이 커밋이 저 커밋을 봤나?” — 이 질문들은 전부 순서에 관한 질문이지, “정확히 몇 시 몇 분 몇 초”를 요구하지 않습니다. 1978년, 레슬리 램포트(Leslie Lamport)는 논문 “Time, Clocks, and the Ordering of Events in a Distributed System”(Communications of the ACM, vol. 21, no. 7, 1978, pp. 558–565)에서 바로 이 지점을 짚었습니다. 시각을 동기화하려 애쓰는 대신, 순서만 정의하면 된다는 것.

스토리 — 시각 없이 순서를 세우는 법

happened-before — 세 줄로 끝나는 정의

램포트가 정의한 관계는 happened-before, 기호로 →입니다. a → b는 “a가 b보다 먼저 일어났다”는 뜻이고, 딱 세 가지 규칙으로만 성립합니다.

같은 프로세스 안의 순서. a와 b가 같은 프로세스에서 일어났고, a가 b보다 먼저 실행됐다면 a → b.
메시지 전송. a가 메시지를 보내는 이벤트이고 b가 그 메시지를 받는 이벤트라면 a → b. (신호가 수신자에 닿기 전에 발신자를 떠났다는, 물리적으로 당연한 사실 하나만 씁니다.)
전이성(transitivity). a → b 이고 b → c 이면 a → c.

이 세 규칙이 만드는 건 **부분 순서(partial order)**입니다. 전체 순서가 아니라는 게 핵심이에요. 두 이벤트 a, b 사이에 이 세 규칙을 아무리 적용해도 a → b도 b → a도 성립하지 않을 수 있습니다. 그럴 때 램포트는 이 둘을 **동시적(concurrent)**이라 부르고 a ∥ b로 씁니다.

동시적이라는 건 “아직 순서를 몰라서 못 정한 상태”가 아닙니다. 서로 영향을 주고받을 방법이 원천적으로 없었다는, 그 자체로 확정된 사실입니다. 두 프로세스가 서로 메시지를 주고받은 적이 없다면, 그 사이에서 일어난 이벤트들은 어느 쪽이 먼저인지 따지는 게 애초에 의미가 없습니다. 물리학의 “인과적으로 분리된(causally disconnected)” 사건과 같은 발상이에요 — 정보가 빛보다 빠르게 갈 수 없듯, 여기서는 정보가 메시지 없이 갈 수 없습니다.

알고리즘 — 규칙 세 개, 변수 하나

happened-before는 관계일 뿐, 그 자체로 비교 가능한 숫자를 주진 않습니다. 램포트는 여기에 정수 카운터 하나를 붙여 실제로 계산 가능하게 만들었습니다. 각 프로세스는 카운터 C를 하나씩 갖고, 딱 세 규칙만 따릅니다.

로컬 이벤트를 처리할 때: C = C + 1.
메시지를 보낼 때: C = C + 1 하고, 그 값을 메시지에 실어 보낸다.
메시지를 받을 때: C = max(C, 받은 값) + 1.

이게 전부입니다. 벽시계도, NTP도, 오실레이터도 없습니다. 정수 하나와 덧셈뿐이에요.

핵심 — 한쪽으로만 성립하는 약속

보장되는 것 — `a → b`이면 `C(a) < C(b)`

이 알고리즘을 따르면 다음이 항상 성립합니다.

a → b 이면 C(a) < C(b) 이다.

규칙을 그대로 따라가 보면 왜 그런지 보입니다. 같은 프로세스 안이면 카운터는 매 이벤트마다 증가하니 당연히 커지고, 메시지를 보내고 받는 관계라면 수신 규칙의 max(...) + 1이 발신 시점의 값보다 최소 1 큰 값을 만들어냅니다. 전이성은 부등호의 전이성 그대로 따라옵니다.

보장되지 않는 것 — 역은 성립하지 않는다

이 장의 중심은 사실 여기부터입니다. 위 명제의 역은 성립하지 않습니다.

C(a) < C(b) 라고 해서 a → b 라는 보장은 없다.

카운터가 크다는 건 “그 이벤트 이전에 로컬 이벤트나 메시지 교환이 그만큼 누적됐다”는 뜻일 뿐, 그 누적이 a로부터 왔다는 뜻은 아닙니다. 다른 두 프로세스가 서로 메시지를 주고받으며 카운터를 빠르게 올리는 동안, a를 만든 프로세스는 그 대화에 전혀 끼지 않았을 수 있습니다. 그러면 a의 카운터는 낮게 남고, 저쪽 대화의 카운터는 a와 아무 상관 없이 높아집니다. 숫자만 보면 순서가 있어 보이지만, 그 순서 뒤에 인과관계는 없습니다.

말로는 애매할 수 있으니, 실제로 돌려서 확인합니다.

실측 — 세 프로세스, 그리고 무너지는 역

세 프로세스 P1·P2·P3가 메시지를 주고받는 상황을 코드로 그대로 재현했습니다. 실행 순서는 스크립트에 고정돼 있고 난수나 벽시계 호출은 전혀 없습니다 — 그래서 몇 번을 실행해도 같은 결과가 나옵니다.


import java.util.ArrayList;
import java.util.List;
 
public class LamportClockDemo {
 
    static class Stamp implements Comparable<Stamp> {
        final int counter;
        final int nodeId;
        final String label;
 
        Stamp(int counter, int nodeId, String label) {
            this.counter = counter;
            this.nodeId = nodeId;
            this.label = label;
        }
 
        @Override
        public int compareTo(Stamp o) {
            if (this.counter != o.counter) return Integer.compare(this.counter, o.counter);
            return Integer.compare(this.nodeId, o.nodeId); // 동점이면 nodeId로 강제 결정
        }
 
        @Override
        public String toString() {
            return String.format("(counter=%d, node=%d) %s", counter, nodeId, label);
        }
    }
 
    static class Process {
        final String name;
        final int nodeId;
        int clock = 0;
 
        Process(String name, int nodeId) {
            this.name = name;
            this.nodeId = nodeId;
        }
 
        int local(String label) {
            clock += 1;
            System.out.printf("%-2s | local     | %-20s | C=%d%n", name, label, clock);
            return clock;
        }
 
        int send(String label) {
            clock += 1;
            System.out.printf("%-2s | send      | %-20s | C=%d (메시지에 첨부)%n", name, label, clock);
            return clock;
        }
 
        int receive(String label, int received) {
            int before = clock;
            clock = Math.max(clock, received) + 1;
            System.out.printf("%-2s | receive   | %-20s | C=max(%d,%d)+1=%d%n", name, label, before, received, clock);
            return clock;
        }
    }
 
    public static void main(String[] args) {
        Process p1 = new Process("P1", 1);
        Process p2 = new Process("P2", 2);
        Process p3 = new Process("P3", 3);
        List<Stamp> allEvents = new ArrayList<>();
 
        int a = p1.local("a (기준 이벤트)");
        allEvents.add(new Stamp(a, 1, "P1.a"));
 
        int p2e1 = p2.local("e1");
        allEvents.add(new Stamp(p2e1, 2, "P2.e1"));
 
        int p3e1 = p3.local("e1");
        allEvents.add(new Stamp(p3e1, 3, "P3.e1"));
 
        int m1 = p2.send("m1 -> P3");
        allEvents.add(new Stamp(m1, 2, "P2.send(m1)"));
 
        int p3rm1 = p3.receive("m1 from P2", m1);
        allEvents.add(new Stamp(p3rm1, 3, "P3.recv(m1)"));
 
        int b = p3.local("b (비교 대상)");
        allEvents.add(new Stamp(b, 3, "P3.b"));
 
        int m2 = p1.send("m2 -> P2");
        allEvents.add(new Stamp(m2, 1, "P1.send(m2)"));
 
        int p2rm2 = p2.receive("m2 from P1", m2);
        allEvents.add(new Stamp(p2rm2, 2, "P2.recv(m2)"));
 
        int m3 = p2.send("m3 -> P3");
        allEvents.add(new Stamp(m3, 2, "P2.send(m3)"));
 
        int p3rm3 = p3.receive("m3 from P2", m3);
        allEvents.add(new Stamp(p3rm3, 3, "P3.recv(m3)"));
 
        System.out.printf("C(a)=%d, C(b)=%d%n", a, b);
 
        List<Stamp> ordered = new ArrayList<>(allEvents);
        java.util.Collections.sort(ordered);
        for (Stamp s : ordered) System.out.println("  " + s);
    }
}


=== 1. 세 프로세스가 메시지를 주고받는다 (고정된 순서, 랜덤 없음) ===
P1 | local     | a (기준 이벤트)           | C=1
P2 | local     | e1                   | C=1
P3 | local     | e1                   | C=1
P2 | send      | m1 -> P3             | C=2 (메시지에 첨부)
P3 | receive   | m1 from P2           | C=max(1,2)+1=3
P3 | local     | b (비교 대상)            | C=4
P1 | send      | m2 -> P2             | C=2 (메시지에 첨부)
P2 | receive   | m2 from P1           | C=max(2,2)+1=3
P2 | send      | m3 -> P3             | C=4 (메시지에 첨부)
P3 | receive   | m3 from P2           | C=max(4,4)+1=5

=== 2. 센터피스 — C(a) < C(b) 인데 a와 b는 동시적(concurrent)이다 ===
C(a) = 1
C(b) = 4

=== 3. (선택) (counter, nodeId) 타이브레이크로 만든 총서(total order) ===
  (counter=1, node=1) P1.a
  (counter=1, node=2) P2.e1
  (counter=1, node=3) P3.e1
  (counter=2, node=1) P1.send(m2)
  (counter=2, node=2) P2.send(m1)
  (counter=3, node=2) P2.recv(m2)
  (counter=3, node=3) P3.recv(m1)
  (counter=4, node=2) P2.send(m3)
  (counter=4, node=3) P3.b
  (counter=5, node=3) P3.recv(m3)

(✅ 실측 — 2026년 7월, Temurin JDK 21 컨테이너.)

여기서 a는 P1이 시뮬레이션 시작 직후 만든 첫 이벤트입니다(C=1). 이 시점까지 P1은 누구에게도 메시지를 보내지 않았어요. b는 그보다 한참 뒤 P3에서 일어난 이벤트로, C=4입니다 — 그런데 그 카운터는 P2가 P1과는 무관하게 먼저 P3로 보낸 m1 덕분에 올라간 겁니다. a에서 b로 이어지는 메시지 경로는 없고, b에서 a로 이어지는 경로도 없습니다(P3가 P1에게 보낸 메시지 자체가 이 시나리오에 존재하지 않으니까요). happened-before 규칙 세 개를 아무리 적용해도 a → b도 b → a도 만들어지지 않습니다. a와 b는 정의상 동시적입니다.

그런데 숫자만 보면 C(a) = 1 < C(b) = 4, 명백히 참입니다. 카운터의 대소 비교는 실재하는 사실이고, 그 뒤에 있어야 할 인과관계는 존재하지 않습니다. 이 코드를 처음 보는 사람이 “카운터가 작은 쪽이 먼저고, 그러니 원인이다”라고 결론 내린다면 — 그 결론은 근거 없이 틀렸습니다. 램포트 카운터는 순서를 매길 뿐, 왜 그 순서인지는 말해주지 않습니다.

총서(total order) — 사고 싶으면 살 수 있지만, 대가가 있다

실무에서는 종종 인과 순서가 아니라 그냥 하나로 정해진 순서가 필요할 때가 있습니다. 로그를 정렬해야 한다든지, 락 요청 큐를 세워야 한다든지. 이럴 때 카운터가 같은 값일 경우를 대비해 프로세스 ID로 동점을 깨면, 모든 이벤트에 유일한 순서를 매길 수 있습니다 — (counter, nodeId) 튜플로 비교하는 겁니다.

위 시뮬레이션의 3번 블록이 그 결과입니다. P2.e1과 P3.e1은 둘 다 counter=1인 동시적 이벤트인데, nodeId 비교(2 < 3) 때문에 P2.e1이 먼저인 것으로 정렬됩니다. 이 순서는 매번 같은 결과를 내는 진짜 전순서(total order)이고, a → b인 두 이벤트의 상대 순서는 절대 뒤집지 않습니다 — 카운터가 이미 그 관계를 보장하니까요. 하지만 동시적인 두 이벤트 사이에도 순서를 하나 만들어 버립니다. 그 순서는 재현 가능할 뿐, 누가 먼저였다는 사실을 반영한 게 아니라 타이브레이크 규칙이 지어낸 것입니다.

현장으로 — 왜 시퀀스 번호와 텀(term)이 타임스탬프를 대신하는가

📄 문서 기반(미검증) — Raft 합의 프로토콜의 논문(“In Search of an Understandable Consensus Algorithm”)은 각 서버가 갖는 텀(term) 번호를 명시적으로 “논리적 시계(logical clock)“라고 부릅니다. 텀은 벽시계와 무관하게 오직 증가만 하는 정수이고, 서버끼리 통신할 때마다 서로의 텀을 비교해 더 큰 쪽으로 맞춥니다 — 램포트 수신 규칙의 max(...)와 같은 발상입니다. 큐의 시퀀스 번호, 데이터베이스의 로그 순번(LSN)도 같은 이유로 존재합니다. 이런 시스템들이 “시각”이 아니라 “증가하는 정수”로 순서를 정의하는 이유는 이 장의 결론과 정확히 같습니다 — 순서만 필요할 땐, 시계가 굳이 필요하지 않기 때문입니다.

거꾸로 말하면, updated_at 컬럼 두 개를 비교해 “더 늦은 쪽이 최신”이라 판단하는 코드는 17장에서 본 것과 같은 함정을 그대로 안고 있습니다. 벽시계 타임스탬프는 오차를 갖고 흔들리지만, 시퀀스 번호나 텀 번호는 흔들리지 않습니다. “순서가 필요하면 순서를 세는 메커니즘을 쓰고, 시각이 필요하면 그때만 시계를 쓴다” — 이게 이 장이 남기는 실무 규칙입니다.

정리

17장은 벽시계 타임스탬프로는 두 이벤트의 순서를 믿을 수 없다는 걸 보였다. 이 장은 그 대안으로 시각을 아예 묻지 않는 시계를 제시한다.
**happened-before(→)**는 세 규칙으로 정의된다 — 같은 프로세스 내 순서, 발신-수신, 전이성. 이 세 규칙으로 순서가 정해지지 않는 두 이벤트는 **동시적(∥)**이며, 이는 정보 부족이 아니라 확정된 상태다.
알고리즘은 세 줄이다 — 로컬 이벤트에서 C+1, 발신 시 C+1을 메시지에 첨부, 수신 시 C = max(local, received) + 1.
보장은 한쪽으로만 성립한다. a → b 이면 C(a) < C(b). 그러나 역은 성립하지 않는다 — C(a) < C(b)는 인과관계를 증명하지 못한다. 실측 시뮬레이션에서 C(a)=1 < C(b)=4이지만 a와 b는 동시적이라는 걸 직접 확인했다.
(counter, nodeId) 타이브레이크로 총서를 만들 수 있다. 인과 순서를 뒤집지는 않지만, 동시적 이벤트 사이에는 순서를 지어낸다.
📄 문서 기반(미검증) — Raft의 텀 번호는 논문에서 스스로 “논리적 시계”라 불리며, 시퀀스 번호·LSN도 같은 원리로 벽시계 대신 순서를 정의한다.

생각해볼 질문: 램포트 카운터 하나로는 a → b인지 a ∥ b인지 구분할 수 없습니다. 카운터가 정수 하나뿐이라, “누구로부터 이 값이 왔는지”에 대한 정보가 계산 과정에서 뭉개져 버리기 때문입니다. C(a) < C(b)라는 사실 하나만으로는 둘 중 어느 쪽인지 알 길이 없다면 — 정수 하나가 아니라, 각 프로세스가 자신이 아는 만큼을 통째로 들고 있다면 어떨까요?

▶ 19장 · 인과를 기록하다 — 벡터 클록

Last updated on August 22, 2026

Overview