番号は因果を守り、ベクトルは並行を見分ける

한 줄 요약

분산 시스템에서 "무엇이 먼저인가" 를 정하는 것은 벽시계가 아니라 메시지입니다. 램포트 시계는 인과를 거스르지 않는 번호를 붙이고, 벡터 시계는 한 걸음 더 나아가 "두 사건은 서로를 모른다(동시)" 까지 알려 줍니다. 이 차이를 모르면 LWW 가 갱신을 조용히 버리고, 계층마다 붙인 재시도가 곱셈으로 불어납니다.

왜 이게 필요했나

로그 두 줄의 타임스탬프를 보고 순서를 정하는 일은 흔합니다. 그런데 두 줄이 서로 다른 서버에서 왔다면 그 비교는 "두 시계가 맞다" 는 가정에 기대고 있습니다. 시계가 왜, 얼마나 어긋나는지와 NTP 는 '로그가 미래에서 왔다' 코스가 사건으로 다룹니다. 이 모듈은 반대쪽 질문에서 출발합니다 — 시계를 맞추지 않고도 순서에 대해 확실히 말할 수 있는 것은 무엇인가.

램포트는 Time, Clocks, and the Ordering of Events in a Distributed System(CACM 21권 7호, 1978)에서 물리적 시간 대신 시스템 안에서 관찰할 수 있는 사건만으로 '먼저 일어남(happened before, →)' 을 정의했습니다. 조건은 셋입니다. 같은 프로세스에서 a 가 b 보다 앞이면 a → b. a 가 어떤 메시지의 송신이고 b 가 그 메시지의 수신이면 a → b. a → b 이고 b → c 이면 a → c. 그리고 a → b 도 b → a 도 아닌 서로 다른 두 사건을 동시(concurrent) 라고 부릅니다. 논문은 이 관계가 사건 전체의 부분 순서일 뿐이라고 강조합니다. 순서가 정해지지 않는 쌍이 처음부터 있다는 뜻이고, 사람들이 이 사실을 충분히 의식하지 않아 문제가 생긴다고 적습니다.

어떻게 동작하나

램포트 시계. 구현 규칙은 둘입니다. IR1 — 각 프로세스는 연속한 두 사건 사이에 자기 시계를 올린다. IR2 — 메시지에는 보낸 시각 Tm 을 싣고, 받는 쪽은 자기 시계를 "지금 값 이상이면서 Tm 보다 크게" 맞춘다. 흔한 구현은 수신 때 max(자기 값, Tm) + 1 입니다. 여기서 max 를 빼고 +1 만 하면, 송신보다 작은 번호를 단 수신이 생겨 규칙이 깨집니다.

이 규칙이 보장하는 것은 Clock Condition — a → b 이면 C(a) < C(b) — 하나입니다. 논문은 역은 기대할 수 없다고 분명히 적습니다. 역이 성립하려면 동시인 두 사건이 모두 같은 시각이어야 하는데 그럴 수 없기 때문입니다. 그러니 C(a) < C(b) 를 보고 a → b 라고 말하면 틀립니다. 논문은 같은 번호를 프로세스에 매긴 임의의 순서로 갈라 전순서를 만들지만, 그것은 인과와 어긋나지 않는 여러 줄 세우기 가운데 하나일 뿐 인과를 알려 주지 않습니다.

벡터 시계. 역까지 필요하면 번호 하나로는 모자랍니다. Mattern 의 Virtual Time and Global States of Distributed Systems(1989)는 프로세스 수만큼 칸을 가진 벡터를 씁니다. 같은 논문은 Fidge 가 독립적으로 같은 생각을 내놓았다고 적습니다. 사건마다 자기 칸을 1 올리고, 메시지에는 벡터를 실어 보내며, 받는 쪽은 칸마다 max 를 취해 합칩니다. 비교도 칸별로 합니다. 모든 칸이 작거나 같고 둘이 다르면 u < v, 어느 쪽도 아니면 동시(u ‖ v)입니다. 논문의 Theorem 10 은 e < e′ 와 C(e) < C(e′) 가 동치이고, e ‖ e′ 와 C(e) ‖ C(e′) 도 동치임을 말합니다.

	램포트 시계	벡터 시계
a → b 이면	L(a) < L(b)	V(a) < V(b)
값이 작으면	아무것도 모른다	a → b 이다
동시를 알아보나	못 한다	V(a) ‖ V(b)
크기	정수 하나	프로세스 수만큼

대가는 크기입니다. 프로세스가 n 개면 메시지마다 n 칸을 싣고 다니고, 참여자가 드나드는 시스템에서는 칸을 관리하는 일이 따로 생깁니다.

현장에서 만나는 모습

LWW 가 갱신을 버린다. Cassandra 문서는 원래 Dynamo 논문이 벡터 시계로 동시 갱신을 맞춘 것과 달리 Cassandra 는 더 단순한 last-write-wins 를 쓴다고 적습니다. 모든 변경에 클라이언트나 코디네이터의 시계로 타임스탬프를 달고 가장 늦은 값이 이깁니다. 같은 문서는 정확성이 그 시계에 달려 있으니 NTP 같은 동기화를 꼭 돌리라고 합니다. 여기에는 손실이 두 겹 숨어 있습니다. 동시 쓰기 둘 가운데 하나는 오류 없이 사라지고, 시계가 빠른 복제본의 쓰기가 그것을 보고 나서 한 느린 복제본의 쓰기를 이깁니다(인과 역전). 벡터 시계를 달면 적어도 "이 둘은 동시였다" 는 사실은 남고, 합칠지 사람에게 물을지는 애플리케이션이 정할 수 있습니다.

재시도는 곱해진다. Google SRE 책의 Addressing Cascading Failures 장은 여러 계층에서 재시도하면 최상위 요청 하나가 계층별 시도 수의 곱만큼 최하위 호출을 만들 수 있다고 경고합니다. 책의 예에서는 DB 가 과부하일 때 백엔드·프런트엔드·자바스크립트가 각각 3번 재시도(시도 4번)하면 사용자 동작 하나가 DB 에 64번 닿습니다. 하필 DB 가 가장 약할 때입니다. 어느 계층에서 재시도할지, 재시도 예산·지터·멱등 키는 '멱등성 — 두 번 눌러도 한 번만 결제되게' 코스가 설계로 다루고, 번호로 순서를 세우는 또 다른 장치인 임기(term)는 '리더가 둘이었다' 코스가 다룹니다.

다음 실습에서 할 것

프로세스 넷의 사건 기록에 램포트 시계를 달고, 정의대로 happened-before 를 판정해 "번호가 작으면 먼저" 가 어느 쌍에서 틀리는지 봅니다. 벡터 시계로 동시인 쌍을 전부 세고, 벽시계가 어긋난 복제본 셋의 같은 키 쓰기에서 충돌 목록과 LWW 가 조용히 버리는 갱신을 찾습니다. 마지막으로 계층별 재시도 정책에서 DB 호출이 몇 배가 되는지 계산하고 종합 보고서를 씁니다.