분산 시스템에서의 시간 동기화

분산 시스템에서 시간이 어려운 이유

분산 시스템에는 단일 전역 시계가 없습니다. 모든 기계는 자체 시계를 가지고 있으며, NTP 동기화를 해도 데이터센터 내 서버 시계는 수십~수백 밀리초 차이가 날 수 있습니다. 이는 서로 다른 기계의 이벤트 순서를 결정하는 것을 근본적으로 어렵게 만듭니다.

문제: 클록 스큐

서버 A가 T=100ms에 이벤트를 처리하고 B에 메시지를 보낸다고 가정합니다. B의 시계가 약간 뒤처져 T=90ms에 응답을 처리하면, 순진하게 보면 B의 이벤트가 A의 원래 이벤트보다 먼저 일어난 것처럼 보입니다 — 인과관계 위반입니다.

논리 시계: Lamport 타임스탬프

Leslie Lamport의 1978년 해결책: 물리적 시간을 인과 순서를 추적하는 논리 카운터로 대체합니다:

class LamportClock:
    def __init__(self):
        self.time = 0

    def tick(self):
        self.time += 1
        return self.time

    def update(self, received_time: int) -> int:
        self.time = max(self.time, received_time) + 1
        return self.time

Lamport 시계는 "이벤트 A가 B를 유발했다면 L(A) < L(B)"를 보장합니다. 역은 성립하지 않습니다.

벡터 시계

벡터 시계는 Lamport 시계를 확장해 인과관계를 완전히 추적합니다. 각 프로세스는 프로세스별 카운터 벡터를 유지합니다. Amazon DynamoDB, Riak, 버전 관리 시스템에서 사용됩니다.

하이브리드 논리 시계 (HLC)

하이브리드 논리 시계는 물리적 시간과 논리 카운터를 결합해 실제 타임스탬프를 유지하면서도 인과 순서를 보장합니다. CockroachDB, YugabyteDB에서 사용됩니다.

TrueTime: Google의 접근법

Google의 Spanner 데이터베이스는 시간을 단일 값이 아닌 구간 [earliest, latest]으로 제공하는 TrueTime을 사용합니다. 모든 데이터센터에 GPS와 원자 시계를 배치해 불확실성 구간을 7밀리초 이하로 유지합니다.

실용적 권장 사항

• 여러 소스에서 NTP를 사용하고 클록 드리프트를 모니터링하세요
• 인과 순서가 중요한 시스템에는 벡터 시계나 HLC를 사용하세요
• 시스템이 클록 스큐를 허용하도록 설계하세요 — 타임스탬프가 가까운 두 이벤트가 올바르게 순서화되어 있다고 가정하지 마세요