램포트 시계

램포트 시계는 여러 서버에서 일어난 사건에 번호를 매겨 앞뒤를 맞춥니다. 서버는 사건이 날 때마다 자기 번호를 1 올립니다. 메시지를 보낼 때는 그 번호를 함께 실어, 원인이 된 사건이 늘 작은 번호를 갖게 합니다. 시계가 서로 어긋난 기계들 사이에서도 이 앞뒤는 뒤집히지 않습니다.

쉽고 빠른 이해

램포트 시계는 서버들이 겪은 사건에 번호를 붙입니다. 주문 서버가 결제 서버에 요청을 보냈다면, 요청을 보낸 사건이 요청을 받은 사건보다 늘 작은 번호를 받습니다.

시각으로 앞뒤를 매기면 기계마다 어긋난 시계 탓에 순서가 뒤집힐 수 있습니다. 받은 사건이 보낸 사건보다 이른 시각을 달고 기록에 남는 식입니다. 번호는 주고받는 쪽끼리 맞추므로 이런 뒤집힘이 없습니다.

1. 서버마다 번호 하나를 0 에서 시작합니다
2. 사건이 하나 날 때마다 그 번호를 1 올립니다
3. 메시지를 보낼 때는 그 번호를 함께 싣습니다
4. 메시지를 받는 사건만은 따로 셉니다. 자기 번호와 실려 온 번호 중 큰 쪽에 1 을 더합니다

대가는 번호만으로는 두 사건이 서로 무관했는지 알 수 없다는 것입니다. 번호가 작다고 그 사건이 다른 사건의 원인이었던 것은 아닙니다. 그것까지 가리려면 서버 수만큼 칸을 든 벡터 시계가 필요합니다.

그래서 모든 서버가 사건을 같은 순서로 세워야 할 때 씁니다. 여러 서버가 같은 데이터를 들고 요청을 같은 차례로 처리해야 할 때가 그렇습니다.

상세

이 절은 주문 서버와 결제 서버가 요청 하나를 주고받는 장면으로 끝까지 갑니다. 먼저 시각으로 앞뒤를 매기면 무엇이 깨지는지 봅니다. 그다음 번호 하나가 그 문제를 어떻게 푸는지, 그 번호를 어디까지 믿을 수 있는지를 봅니다.

시각으로 앞뒤를 매길 때 깨지는 것

이 절은 서버마다 시계 시각을 적어 사건의 앞뒤를 매기면 무엇이 깨지는지 봅니다. 그 전에 서버와 사건이 무엇인지부터 정합니다.

분산 시스템은 여러 대의 기계가 메시지를 주고받으며 함께 일하는 시스템입니다. 이 글에서는 기계마다 서버가 하나씩 돈다고 봅니다.

서버가 겪는 일 하나가 사건입니다. 주문을 저장하는 것, 메시지를 한 통 보내는 것, 메시지를 한 통 받는 것이 각각 사건 하나입니다.

한 서버 안에서는 사건의 앞뒤가 분명합니다. 서버가 사건을 하나씩 차례로 처리하기 때문입니다. 서버가 둘이 되면 두 서버의 사건을 한 줄로 세워 줄 기준이 없습니다.

먼저 떠오르는 기준은 시각입니다. 사건마다 그 서버의 시계가 가리키는 시각을 적고, 이른 쪽을 앞으로 칩니다.

이 방법은 기계마다 시계가 조금씩 어긋나 있어서 깨집니다. 이 어긋남이 클록 스큐입니다. 시계를 주기적으로 맞춰 주어도 어긋남이 0 이 되지는 않습니다.

주문 서버가 결제 요청을 보내고 결제 서버가 곧바로 받는다고 합시다. 결제 서버의 시계가 조금 느리면, 받은 사건이 보낸 사건보다 이른 시각을 달고 기록에 남습니다. 기록만 보면 요청을 받은 뒤에 요청을 보낸 것처럼 읽힙니다. 원인과 결과가 뒤집힌 것입니다.

먼저 일어났다는 말의 뜻

램포트 시계가 지키려는 앞뒤는 시각이 아니라 영향입니다. 한 사건이 다른 사건에 영향을 줄 수 있었으면 앞으로 칩니다.

영향을 줄 수 있었는지는 세 규칙으로 따집니다.

1. 같은 서버 안에서는 먼저 처리한 사건이 앞입니다
2. 메시지를 보낸 사건은 그 메시지를 받은 사건보다 앞입니다
3. 사건 a 가 b 보다 앞이고 b 가 c 보다 앞이면, a 는 c 보다 앞입니다

이 세 규칙으로 정해지는 관계가 happens-before입니다. 우리말로는 「먼저 일어났다」입니다.

주문과 결제 장면에 이 규칙을 대 봅니다. 주문 서버는 주문을 저장한 뒤 결제 요청을 보냅니다. 결제 서버는 그 전에 정산을 마감해 두었습니다. 요청을 받은 뒤에는 결제를 승인합니다.

flowchart TD
    subgraph SA["주문 서버"]
        A1["주문 저장"] --> A2["결제 요청 보내기"]
    end
    subgraph SB["결제 서버"]
        B1["정산 마감"] --> B2["결제 요청 받기"] --> B3["결제 승인"]
    end
    A2 --> B2

서버 안의 화살표는 규칙 1 이고, 서버를 건너는 화살표는 규칙 2 입니다. 화살표를 이어 따라가는 것이 규칙 3 입니다. 이어 따라가면 주문 저장에서 결제 승인까지 닿으므로, 주문 저장은 결제 승인보다 앞입니다.

주문 저장과 정산 마감 사이에는 어느 쪽으로도 화살표 길이 없습니다. 서로에게 영향을 줄 수 없었던 두 사건입니다. 이런 두 사건을 동시라고 부릅니다.

동시는 같은 시각에 일어났다는 뜻이 아닙니다. 몇 분 차이가 나도 서로를 못 봤으면 동시입니다.

부분 순서는 모든 쌍이 아니라 일부 쌍에만 앞뒤가 정해지는 순서입니다. 동시인 쌍이 남으므로 happens-before 는 부분 순서입니다.

번호 하나와 규칙 셋

램포트 시계는 서버마다 정수 하나를 둡니다. 이 수가 앞에서 말한 번호입니다. 번호는 몇 시인지를 말하지 않고 사건의 앞뒤를 가리는 데만 씁니다. 이름은 이 방법을 처음 내놓은 레슬리 램포트에게서 왔습니다.

넣는 것은 서버마다 차례로 일어나는 사건과 그 사이를 오가는 메시지입니다. 나오는 것은 사건마다 붙는 번호입니다. 번호를 바꾸는 규칙은 셋입니다.

1. 서버에서 사건이 하나 나면 번호를 1 올립니다. 메시지를 보내는 것도 사건 하나입니다. 받는 사건은 규칙 3 이 대신합니다
2. 메시지를 보낼 때는 방금 올린 번호를 메시지에 함께 싣습니다
3. 메시지를 받으면 자기 번호와 실려 온 번호 중 큰 쪽을 골라 1 을 더합니다

셋째 규칙의 목적은 받은 사건이 보낸 사건보다 반드시 큰 번호를 달게 하는 것입니다. 받는 쪽 번호가 아무리 작았어도 실려 온 번호를 넘어섭니다.

받는 쪽 번호가 1 이고 실려 온 번호가 2 면, 받는 사건은 3 을 답니다. 번호가 1 에서 3 으로 건너뛴 것입니다. 번호는 촘촘히 이어질 필요가 없습니다. 커지기만 하면 됩니다.

한 장면으로 따라가기

주문과 결제 장면 전체에 번호를 매겨 봅니다. 가운뎃점 뒤의 수가 그 사건을 처리한 뒤의 번호입니다.

sequenceDiagram
    participant 주문 as 주문 서버
    participant 결제 as 결제 서버
    Note over 주문: 주문 저장 · 1
    Note over 결제: 정산 마감 · 1
    Note over 주문: 결제 요청 보내기 · 2
    주문->>결제: 요청에 2 를 싣는다
    Note over 결제: 결제 요청 받기 · max(1, 2) + 1 → 3
    Note over 결제: 결제 승인 · 4

보낸 사건은 2 이고 받은 사건은 3 입니다. 결제 서버의 번호가 실려 온 번호를 따라 올라갔기 때문입니다. 화살표로 이어진 사건은 이렇게 번호가 늘 커집니다.

시계가 지키는 약속

램포트 시계가 약속하는 것은 한 방향입니다. 사건 a 가 사건 b 보다 먼저 일어났으면 a 의 번호가 b 의 번호보다 작습니다. 이 약속을 시계 조건이라고 부릅니다.

세 규칙이 이 약속을 만듭니다. 같은 서버 안에서는 사건마다 번호가 오릅니다. 메시지를 건너면 받는 쪽이 실려 온 번호를 넘어섭니다. 화살표를 몇 번 이어 가도 번호는 줄곧 커집니다.

거꾸로는 성립하지 않습니다. 번호가 작다고 먼저 일어난 것은 아닙니다. 장면 속 정산 마감은 1 이고 결제 요청 보내기는 2 지만, 둘은 서로를 못 본 동시 사건입니다.

그래서 번호 둘만 보고는 두 사건이 원인과 결과인지, 서로 무관한지를 가를 수 없습니다. 이것이 램포트 시계의 한계입니다.

번호가 같을 때

서로 다른 서버의 사건이 같은 번호를 받기도 합니다. 장면에서 주문 저장과 정산 마감이 둘 다 1 입니다.

이럴 때는 미리 정해 둔 서버 순서로 앞뒤를 가립니다. 주문 서버를 결제 서버보다 앞에 두기로 정했다면, 둘 다 1 인 두 사건 중 주문 저장이 앞에 섭니다. 번호를 먼저 견줍니다. 번호가 같을 때만 서버 순서를 견줍니다.

전체 순서는 모든 쌍에 앞뒤가 정해지는 순서입니다. 이 방법으로 견주면 어떤 두 사건을 골라도 앞뒤가 하나로 나옵니다. 사건 전부가 한 줄로 섭니다.

이 줄은 happens-before 를 거스르지 않습니다. 먼저 일어난 사건은 번호가 작으므로 줄에서도 앞에 섭니다. 동시인 두 사건은 정해 둔 규칙에 따라 줄 어딘가에 놓일 뿐입니다.

전체 순서로 하는 일

같은 데이터를 여러 서버에 두는 것이 복제입니다. 복제에서는 모든 서버가 요청을 같은 순서로 처리해야 데이터가 똑같이 남습니다. 요청마다 램포트 번호를 붙입니다. 모든 서버가 번호 순서로 처리하기로 약속하면 그 순서가 하나로 정해집니다.

이 약속을 지키려면 번호가 더 작은 요청이 아직 오는 중이 아닌지 알아야 합니다. 여기서는 한 서버가 보낸 메시지가 보낸 순서대로 도착한다고 가정합니다. 그러면 어느 서버에게서 번호 7 이 실린 메시지가 왔을 때, 그 서버가 보낸 7 보다 작은 번호는 이미 다 도착한 것입니다. 번호는 서버마다 줄곧 커지므로 그 서버가 앞으로 보낼 번호도 7 보다 큽니다.

그래서 서버는 요청 하나를 처리하기 전에 기다립니다. 다른 모든 서버에게서 그 요청의 번호보다 큰 번호가 실린 메시지를 받은 뒤에야 그 요청을 처리합니다.

이 기다림에는 약점이 있습니다. 서버 하나가 조용해지면 그 서버의 메시지를 기다리느라 모두가 멈춥니다.

한 자원을 한 번에 한 서버만 쓰게 하는 상호 배제도 같은 줄로 풀 수 있습니다. 가장 작은 번호로 요청한 서버가 먼저 씁니다.

드는 비용

번호는 정수 하나라서 드는 비용이 작습니다. 연산마다 드는 값은 이렇습니다.

네 줄 모두 서버가 몇 대든 값이 그대로입니다. 서버 수를 N 이라고 하면, 서버마다 칸을 하나씩 두는 벡터 시계는 받기·싣기·견주기가 모두 O(N) 입니다.

벡터 시계와 가르는 선

논리 시계는 시각 대신 사건의 앞뒤만 매기는 시계를 통틀어 부르는 이름입니다. 램포트 시계는 그중 가장 단순한 것입니다. 벡터 시계도 논리 시계에 듭니다.

벡터 시계는 번호 하나 대신 서버 수만큼의 칸을 듭니다. 칸마다 그 서버에서 난 사건을 몇 개까지 알고 있는지 적습니다. 그 덕분에 두 사건이 앞뒤인지 동시인지를 가려냅니다.

램포트 시계는 그 답을 못 내는 대신 정수 하나로 끝납니다. 동시인지 물을 필요 없이 한 줄로 세우기만 하면 되는 일에는 램포트 시계를 씁니다.

맞는 경우와 안 맞는 경우

여러 서버가 메시지를 주고받으며 모두가 같은 순서로 사건을 세워야 하는 곳에 맞습니다. 앞에서 본 복제 요청의 처리 순서와 상호 배제가 그렇습니다.

같은 데이터를 두 곳에서 따로 고쳤을 때 갈라졌는지를 가려야 하는 곳에는 안 맞습니다. 램포트 번호는 두 수정 중 하나를 앞에 세울 뿐입니다. 둘이 서로를 몰랐다는 것은 알려 주지 않습니다. 이럴 때는 벡터 시계를 씁니다.

사람이 읽을 시각이 필요한 곳에도 안 맞습니다. 번호 7 이 몇 시에 난 사건인지는 알 수 없으므로, 시각이 필요하면 타임스탬프를 따로 남깁니다.

한 서버 안에서만 순서를 매기면 되는 일에도 필요 없습니다. 늘어나는 수 하나면 충분해서 메시지에 번호를 실을 까닭이 없습니다.

관련 항목

램포트 시계가 속하는 상위 분류

논리 시계 · 분산 시스템 · 분산 알고리즘 · 시간과 시계

램포트 시계가 매기는 사건 사이의 관계

happens-before · 인과 관계 · 부분 순서 · 전체 순서 · 동시성

램포트 시계와 같은 문제를 푸는 다른 논리 시계

벡터 시계 · 버전 벡터 · 하이브리드 논리 시계 · 시퀀스 번호 · 에포크 · 리비전

램포트 시계가 대신하는 물리 시계와 그 오차

벽시계 · 단조 시계 · 타임스탬프 · 클록 스큐 · 클록 드리프트 · NTP · TrueTime

램포트 시계처럼 전체 순서를 세우는 분산 기법

상호 배제 · 원자적 브로드캐스트 · 상태 머신 복제 · 복제 · 합의 · Paxos · Raft

램포트 시계를 실어 나르는 통신 요소

메시지 · 노드 · 프로세스 · 메시지 전달