논리 시계

논리 시계는 시각을 재지 않고 사건의 앞뒤만 매깁니다. 사건이 하나 일어날 때마다 번호를 하나씩 올립니다. 그 번호 둘을 맞대 무엇이 먼저였는지 가립니다. 기기마다 달린 시계가 서로 어긋나 있어도 순서만은 이렇게 지킬 수 있습니다.

상세

이야기가 건너온 다리 수

동네에 도는 이야기 하나를 놓고 사람들이 저마다 몇 다리 건너 들었는지 셉니다. 나에게 그 이야기를 들려준 사람은 반드시 나보다 다리 수가 적습니다. 나보다 다리 수가 적은 사람 중에는 나보다 늦게 들은 사람도, 나와 한마디도 나눠 본 적 없는 사람도 있습니다.

시각이 아니라 앞뒤

번호가 붙는 단위는 사건입니다. 사건은 서버가 기록으로 남기는 일 하나를 말합니다. 주문을 하나 저장하는 일, 메시지를 한 통 보내는 일, 도착한 메시지를 받는 일이 각각 사건 하나입니다.

컴퓨터가 들고 있는 보통의 시계는 둘입니다. 사람이 읽는 시각을 내주는 벽시계와, 흐른 시간만 재는 단조 시계입니다. 둘을 묶어 물리 시계라고 부릅니다.

시계는 기기에 달려 있습니다. 그 위에서 도는 서버가 그 시계를 읽습니다. 아래에서는 기기 하나에 서버 하나를 놓고 말합니다.

여러 기기가 함께 일하는 분산 시스템에서는 이 시계가 곧 문제가 됩니다. 물리 시계의 값은 기기마다 조금씩 어긋나 있습니다. 이 어긋남을 클록 스큐라고 합니다.

서버 둘이 각자 벽시계를 읽어 시각을 찍으면, 나중에 일어난 사건이 더 이른 시각을 달고 나타날 수 있습니다. 시계를 주기적으로 맞춰 주는 장치를 두어도 어긋남이 0이 되지는 않습니다.

논리 시계는 시각을 버립니다. 순서만 남깁니다. 남는 값은 정수 하나입니다. 이 글에서는 그 정수를 번호라고 부릅니다.

번호 하나만 읽어서는 아무것도 알 수 없습니다. 두 번호를 맞대 볼 때만 뜻이 생깁니다.

먼저 일어났다고 말할 수 있을 때

앞뒤를 매기려면 먼저 「먼저 일어났다」가 무슨 뜻인지 정해야 합니다. 두 사건 사이에 앞뒤가 정해지는 경우는 셋입니다.

• 한 서버 안에서 벌어진 두 사건이면, 그 서버가 처리한 차례가 곧 앞뒤입니다
• 한쪽이 메시지를 보낸 사건이고 다른 쪽이 그 메시지를 받은 사건이면, 보낸 쪽이 먼저입니다
• 첫째 사건이 둘째보다 먼저이고 둘째가 셋째보다 먼저이면, 첫째가 셋째보다 먼저입니다

이 세 경우를 묶은 관계를 happens-before라고 부릅니다. 우리말로 옮기면 「먼저 일어났다」입니다.

셋 어디에도 안 걸리는 두 사건이 있습니다. 떨어진 서버에서 메시지 한 통 주고받지 않은 채 각자 벌어진 일들입니다. 이런 두 사건은 동시(concurrent)라고 부릅니다. 동시라고 해서 「같은 시각에 일어났다」는 뜻은 아닙니다. 서로에게 영향을 줄 수 없었으니 「누가 먼저인지 물을 까닭이 없다」는 뜻입니다.

서버 둘을 가와 나라고 하겠습니다. 세 규칙이 사건을 어떻게 잇는지 그려 봅시다. 화살표 하나가 「먼저 일어났다」 하나입니다.

flowchart TD
    subgraph SA["서버 가"]
        A1["첫째"] --> A2["둘째 · 보내기"]
    end
    subgraph SB["서버 나"]
        B1["첫째"] --> B2["둘째 · 받기"] --> B3["셋째"]
    end
    A2 --> B2
    A1 -. 이 둘은 동시 .- B1

가의 첫째와 둘째는 같은 서버 안의 차례라 앞뒤가 있습니다. 가의 둘째가 보낸 메시지를 나의 둘째가 받았으니 그 둘도 앞뒤가 있습니다. 화살표를 계속 따라가면 가의 첫째가 나의 셋째보다 먼저라는 것까지 나옵니다.

가의 첫째와 나의 첫째 사이에는 어느 방향으로도 화살표가 없습니다. 그래서 이 둘은 동시입니다.

모든 사건 쌍의 앞뒤가 정해지지는 않으므로 이 관계는 부분 순서입니다. 사건을 늘어놓으면 한 줄이 아니라 여러 갈래가 나옵니다.

번호 하나로 도는 램포트 시계

가장 단순한 논리 시계는 서버마다 정수 하나만 듭니다. 이 시계를 램포트 시계라고 부릅니다. 서버마다 그 번호를 0에서 시작합니다.

번호를 올리는 규칙을 코드로 적으면 이렇습니다. c 는 그 서버가 지금 들고 있는 번호입니다. sent 는 메시지에 실려 온 번호입니다.

def on_event(c):
    return c + 1              # 2 → 3

def on_receive(c, sent):
    return max(c, sent) + 1   # (1, 3) → 4

방금 본 것은 규칙 둘입니다. 자기 서버에서 사건이 일어났을 때와 메시지가 도착했을 때 번호를 어떻게 바꾸는지입니다. 남은 셋째 규칙은 계산이 아니라 약속입니다. 메시지를 보낼 때 올린 번호를 메시지에 함께 싣습니다.

받는 쪽이 큰 번호를 고르는 까닭이 이 시계의 전부입니다. 보낸 사건보다 받은 사건이 반드시 큰 번호를 달게 만들려는 것입니다.

번호가 어떻게 움직이는지 한 장면으로 따라가 봅시다. 앞 절의 서버 가와 나를 그대로 씁니다. 가운뎃점 뒤의 숫자가 그 순간의 번호입니다.

sequenceDiagram
    participant 가
    participant 나
    Note over 가: 사건 · 1
    Note over 나: 사건 · 1
    Note over 가: 사건 · 2
    가->>나: 보내기 · 3 을 싣는다
    Note over 나: max(1, 3) + 1 → 4
    Note over 나: 사건 · 5

나의 번호가 1에서 4로 건너뜁니다. 건너뛴 2와 3은 가가 쓴 번호입니다. 번호는 촘촘히 이어질 필요가 없습니다. 커지기만 하면 됩니다.

한 방향으로만 맞는 보장

이 시계가 약속하는 것은 한 방향뿐입니다. 먼저 일어난 사건의 번호는 나중에 일어난 사건의 번호보다 반드시 작습니다.

거꾸로는 성립하지 않습니다. 번호가 작다고 먼저 일어난 것은 아닙니다. 램포트 시계 그림에서 나의 「사건 · 1」은 가의 「사건 · 2」보다 번호가 작지만, 나의 사건이 먼저 일어난 것은 아닙니다. 둘은 메시지가 오가기 전에 각자 벌어진 동시 사건입니다.

번호가 같은 두 사건도 나옵니다. 그럴 때는 서버 이름처럼 미리 정해 둔 잣대로 앞뒤를 가릅니다. 그러면 모든 사건을 한 줄로 세울 수 있습니다.

이렇게 만든 줄이 전체 순서입니다. 다만 그 줄에서 앞에 선 사건이 뒤 사건의 원인이라는 보장은 없습니다.

그래서 번호만 손에 쥔 쪽은 「이 둘이 동시였나」를 되물을 수 없습니다. 이 한계가 다음 절의 벡터 시계를 낳았습니다.

칸을 나눠 가진 벡터 시계

벡터 시계는 번호 하나 대신 서버 수만큼의 칸을 듭니다. 서버가 셋이면 칸도 셋입니다. 각 칸은 「내가 아는 그 서버의 번호」입니다.

규칙도 같은 모양으로 늘어납니다. 자기 사건이 일어나면 자기 칸만 1 올립니다. 메시지를 보낼 때는 벡터 전부를 싣습니다.

받으면 칸마다 큰 쪽을 골라 덮어씁니다. 그다음 자기 칸을 1 올립니다.

서버 셋 가·나·다 가운데 둘이 주고받는 장면으로 따라가 봅시다. 다는 이 장면에서 아무 일도 하지 않아 셋째 칸이 0에 머뭅니다.

sequenceDiagram
    participant 가
    participant 나
    Note over 가: 사건 · [1,0,0]
    가->>나: [1,0,0] 을 싣는다
    Note over 나: 큰 쪽을 고른 뒤 자기 칸 +1 · [1,1,0]
    나->>가: [1,1,0] 을 싣는다
    Note over 가: 큰 쪽을 고른 뒤 자기 칸 +1 · [2,1,0]
    Note over 나: 사건 둘 · [1,3,0]

가는 나에게서 받은 뒤 [2,1,0]을 듭니다. 나는 자기 사건을 둘 더 치른 뒤 [1,3,0]을 듭니다. 아래에서 견주는 두 벡터가 이 둘입니다.

이렇게 들고 다니면 두 벡터를 맞대 보는 것만으로 앞뒤가 나옵니다. 한 벡터가 모든 칸에서 상대보다 작거나 같고 적어도 한 칸이 작으면 그쪽이 먼저입니다. 어느 쪽도 아니면 두 사건은 동시입니다.

flowchart TD
    A["두 벡터를 칸마다 견준다"] --> B{"한 벡터가 모든 칸에서 작거나 같고<br/>적어도 한 칸이 작나"}
    B -->|첫째 벡터가 그렇다| C["첫째 사건이 먼저다"]
    B -->|둘째 벡터가 그렇다| D["둘째 사건이 먼저다"]
    B -->|어느 쪽도 아니다| E["두 사건은 동시다"]

마지막 갈래가 램포트 시계에 없던 답입니다. 방금 얻은 두 벡터가 그 경우입니다.

가 칸은 첫째 사건이 큽니다. 나 칸은 둘째 사건이 큽니다. 어느 쪽도 상대보다 작거나 같지 않으니 두 사건은 동시입니다. 각자 모르는 채 벌어졌다는 뜻입니다. 둘을 합칠지 하나만 남길지는 따로 정해야 합니다.

대가는 크기입니다. 칸 수가 서버 수를 따라가므로 서버가 늘면 메시지마다 붙는 벡터도 함께 커집니다. 서버가 드나드는 시스템에서는 떠난 서버의 칸을 언제 버릴지도 정해 두어야 합니다.

쓰는 곳과 치르는 대가

논리 시계는 같은 데이터를 여러 곳에 두는 복제에서 제 몫을 합니다. 두 사본이 서로 다른 내용을 들고 있을 때, 한쪽이 다른 쪽의 최신본인지 아니면 둘이 갈라진 것인지를 논리 시계가 가립니다. 갈라졌다고 판정되면 충돌 해소로 넘어갑니다.

데이터에 붙는 리비전 번호를 논리 시계로 매기기도 합니다. 읽을 때 받은 번호를 쓸 때 같이 보냅니다. 서버는 그 번호가 아직 최신일 때만 쓰기를 받아 줍니다. 이렇게 미리 잠그지 않고 쓰는 순간에만 확인하는 방식이 낙관적 동시성 제어입니다.

sequenceDiagram
    participant 앱
    participant 서버
    앱->>서버: 읽는다
    서버-->>앱: 값과 리비전 7
    앱->>서버: 쓴다 · 리비전 7 을 싣는다
    Note over 서버: 리비전이 7 그대로면 받아 준다
    Note over 서버: 그새 8 로 올라갔으면 거절한다

거절당한 쪽은 다시 읽습니다. 새 리비전을 받아 쓰기를 다시 시도합니다. 부딪히지 않는 동안에는 아무도 기다리지 않습니다. 대신 부딪히면 그 일을 다시 해야 합니다.

치르는 대가는 셋입니다. 첫째, 사람이 읽는 시각이 사라집니다. 「이 사건이 몇 시에 났나」는 논리 시계로 답할 수 없어 벽시계 시각을 따로 남겨야 합니다. 둘째, 번호가 메시지마다 따라다녀 주고받는 양이 늡니다. 셋째, 번호를 올리고 합치는 일을 애플리케이션이 직접 해야 합니다.

첫째 대가를 줄이려고 벽시계 시각과 논리 시계를 한 값에 담는 방식이 있습니다. 하이브리드 논리 시계라고 부릅니다. 사람이 읽는 시각을 남긴 채 앞뒤 보장도 함께 갖는 것을 노립니다.

안 쓰는 쪽이 나은 경우도 있습니다. 한 기기 안에서만 벌어지는 일이라면 그 기기의 단조 시계나 늘어나는 번호 하나로 충분합니다. 여러 기기가 얽히더라도 순서가 더러 뒤집혀도 되는 데이터라면 타임스탬프를 찍고 마는 쪽이 훨씬 쌉니다.

관련 항목

논리 시계의 하위 종류

램포트 시계 · 벡터 시계 · 버전 벡터 · 하이브리드 논리 시계

논리 시계와 맞세워지는 물리 시계

벽시계 · 단조 시계 · 시스템 클록 · NTP · 유닉스 시간

물리 시계의 앞뒤를 흔드는 원인

클록 스큐 · 클록 드리프트 · 윤초 · 클럭 스텝

논리 시계가 매기는 순서 개념

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

논리 시계로 다루는 동시 수정

충돌 해소 · 낙관적 동시성 제어 · 리비전 · Last Write Wins · CRDT

논리 시계를 쓰는 분산 처리

분산 시스템 · 복제 · 가십 · 이벤트 소싱 · 합의

사건에 번호를 매기는 다른 수단

타임스탬프 · 시퀀스 번호 · 에포크 · 스노우플레이크