- 여러 서버가 동시에 작동할 때 “누가 먼저인가”를 결정하는 방법은 단일하지 않다
- 물리 시계만으로는 분산 시스템에서 “순서”를 보장할 수 없다
- Lamport·Vector·HLC의 세 가지 논리 시계 모델이 그 한계를 보완한다
분산 시스템에서 “시간”의 어려움
한 컴퓨터에서 일어나는 두 사건의 순서를 정하는 것은 쉽다. 같은 시계를 보면 된다. 그러나 서로 다른 컴퓨터에서 일어난 두 사건의 순서를 정하는 것은 어렵다. 두 컴퓨터의 시계가 정확히 같다는 보장이 없기 때문이다.
NTP·PTP로 시계를 매우 정확하게 맞춰도 마이크로초 단위 차이는 남는다. 분산 데이터베이스·블록체인·결제 시스템은 이 차이가 결과를 바꿀 수 있는 영역이다. 그래서 “물리 시계 + 논리 시계”의 결합이 필요하다.
인과 관계와 “happened-before”
1978년 Leslie Lamport는 분산 시스템의 시간을 정의하는 새로운 관계를 도입했다 — “happened-before”.
- 같은 프로세스 안에서 A가 B보다 먼저 실행되면, A → B.
- 한 프로세스가 메시지를 보내고 다른 프로세스가 받았다면, 보낸 사건 → 받은 사건.
- 이 두 규칙으로 연결되면 A → B (A는 B의 “원인 가능성” 안에 있다).
- 연결되지 않으면 A와 B는 “동시(concurrent)” — 인과 관계가 없다.
이 관계는 절대적 시간이 아니라 “인과적 시간”을 정의한다. 분산 시스템의 시간은 절대적 시간이 아니라 인과 관계의 그래프로 더 정확히 표현된다.
Lamport Clock — 가장 단순한 논리 시계
Lamport는 happened-before 관계를 보존하는 단순한 카운터를 제안했다.
- 각 프로세스가 카운터 L을 가진다(시작 0).
- 프로세스가 사건을 일으킬 때마다 L = L + 1.
- 메시지를 보낼 때 L 값을 함께 보낸다.
- 메시지를 받을 때 L = max(자기 L, 받은 L) + 1.
이 단순한 규칙으로 “A → B면 L(A) < L(B)”이 보장된다. 단, 역은 성립하지 않는다 — L(A) < L(B)라고 해서 A → B인 건 아니다.
Lamport Clock은 “전순서(total order)”를 만들 수 있지만, 인과 관계를 정확히 추적하지는 않는다.
Vector Clock — 인과 관계의 정확한 추적
Vector Clock은 각 프로세스가 카운터 1개가 아니라 “전체 프로세스 수만큼의 벡터”를 가진다.
- 3개 프로세스 시스템이라면 V = [0, 0, 0]에서 시작.
- 프로세스 i가 사건을 일으키면 V[i] = V[i] + 1.
- 메시지를 받을 때, 각 항목별로 max를 취한 후 자기 항목 + 1.
이 벡터로는 “A의 모든 항목이 B보다 작거나 같으면 A → B”라는 식으로 인과 관계를 정확히 추적할 수 있다. Lamport Clock의 한계를 보완한다.
그러나 Vector Clock은 메시지마다 “전체 프로세스 수의 정수 배열”을 보내야 해서 통신 부담이 크다. 수천 개의 노드가 있는 시스템에서는 부담이 비현실적이다.
HLC (Hybrid Logical Clock) — 물리 + 논리
2014년 등장한 Hybrid Logical Clock은 NTP의 물리 시계와 Lamport의 논리 시계를 결합한다.
- 각 사건은 (물리 시간, 논리 카운터)의 쌍을 가진다.
- 물리 시간은 NTP에서 가져온다.
- 같은 물리 시간 안에서 발생한 여러 사건은 논리 카운터로 구분한다.
- 메시지 받을 때 max를 취하는 방식은 Lamport와 유사.
HLC의 장점은 다음과 같다.
- NTP가 정상 작동하면 카운터는 거의 사용되지 않는다 — 효율적.
- NTP가 실패해도 인과 관계는 보존된다 — 안전.
- 크기가 일정하다 — Vector Clock의 통신 부담이 없다.
현대 분산 데이터베이스(CockroachDB·YugabyteDB·Spanner)는 HLC 또는 그 변형을 사용한다.
Google Spanner — 물리 시계의 “TrueTime API”
Google Spanner는 다른 접근을 채택했다. GPS·원자시계 기반의 정밀 동기화로 “모든 데이터센터의 시계 차이가 7ms 이내”를 보장한다. 그리고 트랜잭션 시 “안전한 대기”를 통해 시계 불확실성을 제거한다.
- 매 트랜잭션이 “2 × 시계 불확실성” 만큼 대기.
- 그 대기 후의 모든 트랜잭션은 정확한 “외부적 일관성”을 가진다.
- 일종의 “시간의 비용”을 지불해서 정확성을 사는 셈.
이 접근은 정밀 동기화 인프라(GPS·원자시계 + PTP)가 있어야 가능하다. GPS·PTP·NTP 비교에서 다룬 정밀 인프라가 여기서 실제로 쓰이는 셈이다.
분산 시스템에서 “시간”은 단일 개념이 아니다 — 물리 시간·논리 시간·인과 관계가 모두 합쳐져 작동한다. 우리가 일상에서 “지금 몇 시”라고 부르는 것은 단순한 단일 숫자지만, 그 뒤에는 NTP·Vector Clock·HLC·TrueTime 같은 다층의 시간 모델이 협업하고 있다. 인터넷 자체가 “시간의 합주”다.