벡터 시계

벡터 시계는 여러 대에 흩어져 일어난 일의 앞뒤를 가려 줍니다. 장바구니 하나를 두 서버가 따로 고쳤을 때 어느 쪽이 나중 것인지를 가립니다. 서로를 모른 채 갈라져 나온 둘도 가려냅니다. 시각 대신 대마다 따로 세는 횟수만 봅니다.

상세

이 절은 장바구니 하나를 두 대가 각각 고치는 예로 끝까지 갑니다. 먼저 시각으로 앞뒤를 매길 때 무엇이 깨지는지 보고, 그다음 벡터 시계가 그 문제를 어떻게 푸는지 봅니다.

여러 대에 흩어진 일의 앞뒤

분산 시스템은 여러 대가 각자 일을 하면서 서로 메시지를 주고받는 시스템입니다. 그 한 대를 노드라고 부릅니다.

노드에서 일어난 사건 하나를 아래에서는 짧게 일이라고 부르겠습니다. 값을 하나 고치는 것도, 메시지를 하나 받는 것도 일입니다.

한 노드 안에서는 어느 일이 먼저인지 헷갈릴 까닭이 없습니다. 명령이 한 줄로 서서 차례로 실행되기 때문입니다. 노드가 둘로 늘면 그 줄이 사라집니다. A 에서 난 일과 B 에서 난 일 사이에는 누가 먼저랄 것이 없습니다.

먼저 떠오르는 방법은 일마다 시각을 적어 두고 이른 쪽을 먼저로 치는 것입니다. 이 방법은 두 곳에서 깨집니다.

하나는 기계마다 시계가 어긋나 있다는 것입니다. 이 어긋남을 클록 스큐라고 부릅니다. 어긋남이 백분의 몇 초만 돼도, 나중에 일어난 수정이 이른 시각을 달고 오는 일이 생깁니다.

sequenceDiagram
    participant A as 노드 A
    participant B as 노드 B
    Note over A: 먼저 고쳤다 · 적힌 시각은 늦다
    Note over B: 나중에 고쳤다 · 적힌 시각은 이르다
    Note over A,B: 적힌 시각과 실제 순서가 뒤집혔다

그림에서 위가 먼저 일어난 일입니다. A 가 먼저 고쳤는데 B 의 수정에 더 이른 시각이 적혔습니다. 시각만 보고 나중 것을 고르면 A 의 수정이 살아남습니다.

다른 하나가 더 아픕니다. 시각은 두 일이 서로를 보고 일어났는지를 말해 주지 못합니다. 두 시각이 다르기만 하면 언제나 앞뒤가 나옵니다. 그 앞뒤가 정말 영향을 주고받은 것인지 우연히 시각이 갈린 것인지는 가르지 못합니다.

앞이라는 말의 뜻

여기서 앞은 시각이 아니라 영향으로 정합니다. 어떤 일이 다른 일에 영향을 줄 수 있었으면 앞이고, 줄 수 없었으면 앞이 아닙니다. 이 관계를 인과 관계라고 부릅니다.

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

1. 같은 노드 안에서는 먼저 실행된 일이 앞입니다
2. 메시지를 보낸 일은 그 메시지를 받은 일보다 앞입니다
3. 첫째가 둘째보다 앞이고 둘째가 셋째보다 앞이면, 첫째는 셋째보다 앞입니다

세 규칙은 일 사이에 화살표를 긋는 규칙입니다. 화살표를 따라 갈 수 있으면 앞이고, 못 가면 앞이 아닙니다.

flowchart TD
    subgraph SA["노드 A"]
        A1["일 1"] -->|앞| A2["일 2 · 메시지 보냄"]
    end
    subgraph SB["노드 B"]
        B1["일 3"]
        B2["일 4 · 메시지 받음"] -->|앞| B3["일 5"]
    end
    A2 -->|앞| B2
    N["일 1 과 일 3 은 어느 화살표로도 안 닿는다 · 동시"]

일 1 에서 일 5 까지는 화살표 셋을 이어 갈 수 있습니다. 셋째 규칙이 말하는 것이 이 사슬입니다. 일 1 은 일 5 보다 앞입니다.

일 1 과 일 3 사이에는 어느 쪽으로도 길이 없습니다. 서로 상대를 모른 채 일어난 것입니다. 이런 둘을 동시라고 부릅니다.

동시는 같은 시각에 일어났다는 뜻이 아닙니다. 한 시간 차이로 일어났어도 서로를 못 봤으면 동시입니다. 시각으로 앞뒤를 매기면 이 답이 아예 안 나옵니다. 벡터 시계는 이 답을 내려고 만든 것입니다.

시계의 모양 — 노드마다 칸 하나

벡터 시계는 참여하는 노드마다 칸을 하나씩 둔 수의 묶음입니다. 노드가 A 와 B 둘이면 칸도 둘입니다.

칸에 적히는 것은 시각이 아니라 횟수입니다. A 칸에 2 가 적혀 있으면 A 에서 난 일 두 개까지를 내가 알고 있다는 뜻입니다. 그래서 시계 한 벌은 "내가 지금까지 본 것"의 요약입니다.

아래에서는 A 칸이 1 이고 B 칸이 0 인 시계를 A 1 · B 0 으로 적겠습니다.

시계를 고치는 세 규칙

노드는 저마다 시계를 한 벌씩 들고 있습니다. 모든 칸이 0 에서 시작합니다.

1. 자기 노드에서 일이 나면 자기 칸을 하나 올립니다
2. 바뀐 내용을 남에게 보낼 때 자기 시계를 함께 싣습니다
3. 받은 쪽은 칸마다 큰 쪽을 골라 자기 시계를 덮고, 그다음 자기 칸을 하나 올립니다

한 번 고쳐진 데이터 한 벌을 아래에서 판이라고 부릅니다. 장바구니에 우유를 담으면 담기 전 판과 담은 뒤 판이 생깁니다. 값을 고칠 때는 그때의 시계를 그 판에 함께 적어 둡니다. 그래서 시계는 노드마다 한 벌, 그리고 저장된 판마다 한 벌 있습니다.

셋째 규칙의 "칸마다 큰 쪽을 고른다"가 이 방법의 핵심입니다. 상대가 본 것이 내가 본 것에 더해집니다. 이 더하기를 합친다고 부르겠습니다.

B 가 A 0 · B 3 을 들고 있는데 A 2 · B 1 이 실린 메시지를 받았다고 합시다.

mine = {"A": 0, "B": 3}
msg  = {"A": 2, "B": 1}

for n in mine:
    mine[n] = max(mine[n], msg[n])
mine            # {'A': 2, 'B': 3}
mine["B"] += 1
mine            # {'A': 2, 'B': 4}

A 칸은 받은 쪽이 커서 2 로 올라갔습니다. B 칸은 내 것이 커서 3 이 남았습니다. 받는 것도 하나의 일이므로 마지막에 자기 칸을 올려 4 가 됐습니다.

두 시계를 견주는 법

견주기도 칸마다 합니다. 한쪽의 모든 칸이 다른 쪽의 같은 칸보다 작거나 같습니다. 그러면서 한 칸이라도 더 작으면 그쪽이 앞입니다.

칸이 모두 똑같으면 같은 시계입니다. 앞도 아니고 같지도 않으면 둘은 동시입니다. 한 칸은 이쪽이 크고 다른 칸은 저쪽이 크다는 뜻입니다. 서로 상대가 본 것을 못 봤다는 뜻입니다.

셋째 줄처럼 두 시계가 똑같을 수도 있습니다. 앞도 뒤도 아니고 갈라진 것도 아닙니다.

장바구니를 두 노드가 고치는 예

장바구니 하나가 노드 A 와 노드 B 에 복제되어 있다고 합시다. 복제는 같은 데이터를 여러 노드에 겹쳐 두는 것입니다. 손님은 어느 노드에든 요청을 보낼 수 있습니다.

sequenceDiagram
    participant A as 노드 A
    participant B as 노드 B
    Note over A: 우유 담기 · A 1 · B 0
    A->>B: 바뀐 장바구니와 시계를 보낸다
    Note over A: 달걀 담기 · A 2 · B 0
    Note over B: 합치고 자기 칸 올림 · A 1 · B 1
    Note over B: 빵 담기 · A 1 · B 2
    Note over A,B: 달걀과 빵은 서로를 못 봤다 · 동시

A 의 시계 A 2 · B 0 과 B 의 시계 A 1 · B 2 를 견주어 봅니다. A 칸은 왼쪽이 크고 B 칸은 오른쪽이 큽니다. 앞선 쪽이 없으니 판정은 동시입니다. A 는 B 의 빵을 모르고 B 는 A 의 달걀을 모릅니다.

시각으로 골랐다면 늦게 적힌 하나만 남고 다른 하나는 사라졌을 것입니다. 벡터 시계는 그 둘이 갈라졌다는 것을 말해 줍니다.

동시로 갈린 두 판을 다루는 법

벡터 시계는 갈라졌다는 것까지만 말합니다. 무엇을 남길지는 정해 주지 않습니다. 그 뒤를 맡는 일을 충돌 해소라고 부릅니다.

처리는 대개 셋 중 하나입니다. 두 판을 다 남겨 두었다가 다음에 읽는 쪽에 둘 다 돌려주거나, 데이터의 뜻을 아는 규칙으로 합치거나, 사람에게 고르게 합니다. 장바구니라면 담긴 물건을 합치는 규칙이 자연스럽습니다.

첫째 갈래는 읽는 쪽과 노드 사이에 왕복이 한 번 생깁니다.

sequenceDiagram
    participant C as 손님
    participant A as 노드 A
    participant B as 노드 B
    C->>A: 장바구니를 읽는다
    A->>B: 서로 가진 판을 맞춰 본다
    A-->>C: 갈라진 두 판을 다 돌려준다
    C->>A: 합친 판 하나를 다시 쓴다
    Note over C,B: 다시 쓴 판의 시계는 두 판을 다 덮는다

합친 판은 두 판의 시계를 합친 시계를 답니다. 그래서 다음에 읽는 쪽은 이 판이 앞의 둘보다 뒤라는 것을 견주기만으로 압니다. 갈라짐이 거기서 닫힙니다.

늦게 적힌 쪽을 무조건 택하는 방법도 있습니다. 이것을 Last Write Wins라고 부릅니다. 규칙이 단순한 대신 갈라진 한쪽이 조용히 사라집니다. 벡터 시계를 두는 까닭은 그 사라짐을 선택으로 바꾸려는 것입니다.

시계 길이와 견주는 비용

노드 수를 N 이라고 하고, 시계 한 벌에 드는 값과 두 시계를 다룰 때 드는 값을 봅니다.

노드가 몇 대뿐이면 이 비용은 눈에 안 띕니다. 노드 수가 커지면 세 곳에서 아픕니다. 데이터 한 건마다 칸 N 개가 붙어 저장됩니다. 메시지마다 그 칸이 실려 나갑니다. 견줄 때마다 N 번을 봅니다.

값 하나가 몇 바이트인 데이터에 칸 수십 개가 붙으면 시계가 데이터보다 커집니다.

노드가 오가는 시스템에서는 문제가 하나 더 붙습니다. 떠난 노드의 칸이 시계에 남습니다. 아무도 올리지 않는 칸인데 시계 길이는 줄지 않습니다.

그래서 시계가 길어지는 것을 막는 규칙을 함께 두곤 합니다. 오래 안 고쳐진 칸부터 버리는 식입니다. 칸을 버리면 그 칸이 담고 있던 앞뒤도 같이 사라집니다. 그래서 어디까지 버릴지는 갈라짐을 놓칠 위험과 맞바꾸는 선택입니다.

램포트 시계와 가르는 선

논리 시계는 시각 대신 순서만 매기는 시계를 통틀어 부르는 이름입니다. 벡터 시계도 그중 하나입니다.

가장 단순한 논리 시계는 칸이 하나뿐인 램포트 시계입니다. 수 하나만 들고 다닙니다. 일이 날 때마다 그 수를 올립니다. 메시지를 받으면 받은 수와 자기 수 중 큰 쪽에 하나를 더합니다.

램포트 시계는 앞선 일이 언제나 작은 수를 갖는다는 것까지 보장합니다. 그런데 거꾸로는 못 갑니다. 수가 작다고 해서 앞선 일이라고 말할 수 없습니다. 갈라진 두 일도 수는 어차피 다르게 나오기 때문입니다.

벡터 시계는 그 거꾸로를 해냅니다. 칸을 노드 수만큼 늘린 대가로 "앞인가 갈라진 것인가"에 답할 수 있게 됐습니다.

맞는 경우와 안 맞는 경우

여러 노드가 각자 쓰기를 받고 나중에 서로 맞추는 저장소에 맞습니다. 같은 데이터가 두 곳에서 따로 고쳐질 수 있고, 그 갈라짐을 버리지 않고 다뤄야 하는 곳입니다.

한 곳이 모든 쓰기를 순서대로 받는 시스템에는 필요 없습니다. 받는 순서가 곧 앞뒤라서 따로 셀 것이 없습니다.

갈라져도 상관없는 데이터에도 필요 없습니다. 마지막 값만 뜻이 있는 센서 측정값이라면 늦게 온 값으로 덮으면 그만입니다.

노드가 수백 대로 늘고 데이터 한 건이 작으면 이 비용이 커집니다. 이럴 때는 칸을 데이터 한 건이 아니라 더 굵은 단위에 붙이거나, 칸 수가 노드 수를 안 따라가는 다른 방법을 봅니다.

관련 항목

벡터 시계가 가려 주는 사건 사이의 관계

인과 관계 · 선후 관계 · 부분 순서 · 전체 순서 · 동시성 · 인과 일관성

벡터 시계와 같은 문제를 푸는 다른 논리 시계

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

벡터 시계가 손대지 못하는 물리 시계의 오차

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

벡터 시계를 주고받는 분산 시스템의 참여자

분산 시스템 · 노드 · 복제 · 복제본 · 코디네이터 · 가십 · 선호 목록 · 정족수

동시라고 판정된 두 판을 합치는 수단

충돌 해소 · 병합 · 형제 판 · Last Write Wins · CRDT · 읽기 복구 · 머클 트리

벡터 시계로 쓰기 충돌을 가리는 저장소

Amazon Dynamo · Riak · Voldemort · 분산 키-값 저장소 · 최종 일관성 · 리더 없는 복제