Time, Clocks & State Ordering

1. Overview

분산 시스템의 시간과 상태 정렬(Time, Clocks & State Ordering)은 분산된 수천 대의 서버에서 발생하는 이벤트들 중 "무엇이 먼저 일어났는가?"라는 단순한 질문이 물리적으로 얼마나 대답하기 불가능한 난제인지 해부합니다.

학습자는 각 서버의 물리적 시계(NTP)가 네트워크 지연으로 인해 필연적으로 어긋날 수밖에 없는 현실을 뼈저리게 인지하고, 물리적 시간이 아닌 '이벤트의 인과관계(원인과 결과)'만으로 선후 관계를 정렬하는 **논리적 시계(Logical Clocks, Lamport & Vector Clocks)**의 우아한 수학적 설계를 뜯어봅니다. 나아가 Google Spanner가 원자 시계(Atomic Clock)와 GPS를 동원해 물리적 시계의 오차 범위를 밀리초 단위로 강제하는 TrueTime API의 기적을 해부합니다. 마지막으로, 두 클라이언트가 동시에 장바구니를 수정했을 때 발생하는 충돌(Conflict)을 어떻게 병합하고 해결(CRDT)할 것인지 데이터 정합성 방어 역량을 확보합니다.

2. Scope & Boundaries

In-Scope

• Time and Order (시간과 순서): 분산 환경에서 전역 시계(Global Clock)의 부재, 시간의 상대성.
• Physical Clocks (물리적 시계): NTP (Network Time Protocol)의 한계, Clock Skew(시계 편차).
• Logical Clocks (논리적 시계): Lamport Timestamp (단순 선후 관계), Vector Clock (동시성 및 충돌 감지).
• Conflict Resolution (충돌 해결): LWW (Last-Write-Wins), 시계열 데이터 병합.
• TrueTime API: Google Spanner의 물리적 시계 동기화 하드웨어 인프라.

Out-of-Scope

• 네트워크 합의 알고리즘 (Raft, Paxos): 노드 간 리더 선출 및 로그 강제 복제 $\rightarrow$ 07-02-02 Consensus Algorithms 영역으로 위임.
• 데이터베이스 격리 수준 (Isolation Levels): 단일 DB 내의 락(Lock) 기반 트랜잭션 순서 정렬 $\rightarrow$ 06-01-03 ACID & Transactions 영역.

Boundaries

• Physical Time vs Logical Time: 로깅이나 모니터링 대시보드(Datadog 등)에 찍히는 타임스탬프는 NTP로 동기화된 물리적 시간(Physical Time)을 쓰면 충분합니다. 1~2초 오차가 나도 상관없기 때문입니다. 하지만, 아마존 장바구니에서 A 유저가 '추가' 버튼을 누르고 B 유저가 '삭제' 버튼을 거의 동시에 눌렀을 때, DB가 "무엇이 마지막 상태인가?"를 결정해야 하는 비즈니스 로직(Data Conflict Resolution)에서는 절대 물리적 시계를 믿어선 안 되며(오차 때문에 삭제가 추가보다 앞설 수 있음), 반드시 카운터 기반의 논리적 시계(Vector Clock)로 인과관계를 추적해야 함을 명확히 구분합니다.

3. Counterexample

• 물리적 시계(NTP) 맹신의 재앙 (The Last-Write-Wins Trap): 분산 데이터베이스(Cassandra 등)에서 타임스탬프가 더 늦은(큰) 것을 최종 데이터로 덮어쓰는 LWW(Last-Write-Wins) 전략을 채택했습니다. A 서버의 시계가 B 서버보다 3초 빠릅니다. B 서버에서 유저가 비밀번호를 바꾼 후 1초 뒤에, A 서버에서 예전 비밀번호로 덮어쓰기 요청이 들어왔습니다. 현실에선 B가 나중에 일어난 일이지만, 타임스탬프는 A가 2초 더 크기 때문에 A의 옛날 데이터가 최종 데이터로 덮어씌워져 버립니다. 서버 간 시계가 완전히 똑같을 거라는 헛된 믿음이 낳은 데이터 유실 안티 패턴입니다.
• 동시성(Concurrency)의 오해: 분산 시스템에서 동시(Concurrent)라는 말은 "정확히 같은 마이크로초에 발생했다"는 물리적 의미가 아닙니다. "A 이벤트가 B 이벤트의 존재를 모른 채 발생했다(서로 인과관계가 없다)"는 논리적 의미입니다. 이를 구분하지 못하고 두 이벤트를 무조건 시간순으로 줄 세우려다 영원히 락(Lock)을 걸어버리는 교착 상태(Deadlock)가 발생합니다.

4. Prerequisites

• 분산 시스템의 오류 (Basic): 네트워크 지연 시간(Latency)은 0이 아님. (07-02-01 Theorems)
• 자료구조 (Basic): 1차원 배열(Vector)을 이용한 카운터 증가 원리. (04-02 Core Data Structures)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 상대성 이론, 전역 시계의 환상 (The Illusion of Time)

• Why to Learn: 하나의 서버에서 쓸 수 있었던 System.currentTimeMillis()가 네트워크를 넘는 순간 쓰레기 값이 되는 이유를 깨닫고, 시간(Time)에 대한 엔지니어의 상식을 파괴하기 위함입니다.
• What to Learn:
  • Concepts: Global Clock(전역 시계 부재), Clock Skew(시계 편차), Clock Drift(시계 흐름 속도 차이), NTP (Network Time Protocol).
  • Skills: 물리적 타임스탬프 의존성 제거, 분산 로그 상의 순서 불일치 식별.
• How to Learn:
  • 1단계: NTP의 한계: 서버들은 타임 서버(NTP)에 "지금 몇 시야?"라고 물어봐서 시계를 맞춥니다. 그런데 응답 패킷이 오는데 50ms가 걸릴지 200ms가 걸릴지 네트워크 상황마다 다릅니다. 이 지연 시간의 불확실성 때문에 서버들의 시계는 필연적으로 수십~수백 밀리초씩 어긋나게 됨을 해부합니다.
  • 2단계: 인과율의 파괴: 서울 서버(느린 시계)에서 게시물을 쓰고, 뉴욕 서버(빠른 시계)에서 답글을 달았습니다. 데이터베이스에 찍힌 타임스탬프로 정렬했더니, "답글이 게시물보다 먼저 달린" 기괴한 인과율 붕괴 현상을 뜯어봅니다.
• Implement: 시계 오차(Clock Skew) 시뮬레이터. 서버 A와 서버 B의 시계 변수에 의도적으로 오프셋(+5초, -2초)을 줌. A가 이벤트를 발생시키고 네트워크 지연 1초 후 B가 이벤트를 받았을 때, 타임스탬프를 비교하여 원인(A)이 결과(B)보다 나중에 일어난 것으로 찍히는 치명적 로그 렌더링.

Recommended

Core Topic 02: 인과율의 회복, 램포트 타임스탬프 (Lamport Clocks)

• Why to Learn: 절대적인 시간(물리적 시간)을 포기하는 대신, "원인은 항상 결과보다 숫자가 작다"는 상대적인 논리적 순서(인과율)를 보장하는 수학적 기법을 장악하기 위함입니다.
• What to Learn:
  • Concepts: Logical Clock, Lamport Timestamp, Happens-Before Relationship ($A \rightarrow B$).
  • Skills: 노드 간 메시지 송수신 시 카운터(Counter) 교환 및 동기화 설계.
• How to Learn:
  • 1단계: 로컬 카운터의 증가: 각 서버는 시계 대신 '정수 카운터(초기값 0)'를 가집니다. 자기 안에서 이벤트가 발생할 때마다 카운터를 +1 합니다.
  • 2단계: 메시지에 숫자 묻히기: 서버 A(카운터 5)가 서버 B(카운터 2)로 메시지를 보냅니다. 메시지에 [5]를 적어 보냅니다. B는 메시지를 받고, 자기 숫자(2)와 받은 숫자(5) 중 더 큰 값(5)을 고른 뒤 +1을 하여 자신의 카운터를 6으로 덮어씁니다. 물리적 시간과 상관없이 원인(A=5)은 항상 결과(B=6)보다 숫자가 작아지는 인과율 보장 마법을 해부합니다.
• Implement: 램포트 시계 파이썬 클래스. node_a.send(node_b) 호출 시, node_a의 카운터가 node_b로 전달되고, node_b가 max(local, received) + 1 로직을 수행하여 서로 독립적인 노드 간의 인과적 선후 관계 정수가 정렬되는 과정을 콘솔 궤적으로 출력.

Practical

Core Topic 03: 충돌을 감지하라, 벡터 시계 (Vector Clocks & Conflict)

• Why to Learn: 램포트 시계는 A와 B 중 누가 먼저 일어났는지는 알 수 있지만, 두 이벤트가 "아예 인과관계 없이 동시에(Concurrent) 일어났는지"는 알 수 없는 한계를 극복하기 위함입니다.
• What to Learn:
  • Concepts: Vector Clocks, Concurrency(동시성), Conflict Detection(충돌 감지), Dynamo (Amazon's Shopping Cart).
  • Skills: 다차원 배열(Vector)을 이용한 다중 노드 버전(Version) 관리 및 충돌 병합(Merge) 로직 작성.
• How to Learn:
  • 1단계: 배열로 기억하기: 이제 단일 정수가 아니라, 클러스터 노드 개수만큼의 배열 [A카운터, B카운터, C카운터]을 들고 다닙니다. A 노드에서 이벤트가 생기면 [1, 0, 0], 이 데이터가 B로 복제되어 B에서 수정되면 [1, 1, 0]이 됩니다.
  • 2단계: 충돌 감지: 어느 날 A 노드는 [2, 0, 0] 상태의 장바구니를 DB에 밀어 넣고, 동시에 B 노드는 [1, 1, 0] 상태의 장바구니를 밉니다. DB가 두 배열을 비교해보니, 하나가 다른 하나보다 모든 숫자가 크거나 같지 않습니다(서로 엇갈림). 즉, 두 유저가 "서로의 변경 사항을 모른 채 동시에 장바구니를 수정했다"는 충돌(Conflict)을 완벽히 감지해 내는 알고리즘을 뜯어봅니다.
• Implement: 벡터 시계 충돌 감지기(Conflict Detector) 함수. 두 배열 v1과 v2를 입력받아, 모든 인덱스에서 v1[i] <= v2[i]이면 v2가 최신, v1[i] >= v2[i]이면 v1이 최신, 크고 작음이 엇갈려 있으면 "CONCURRENT (충돌 발생)"을 리턴하는 수학적 비교 스크립트 작성.

Advanced

Core Topic 04: 구글 스패너와 시간의 정복 (Google TrueTime)

• Why to Learn: 논리적 시계의 복잡한 카운터 관리를 포기하고, 돈과 하드웨어를 쏟아부어 전 지구적 분산 데이터베이스에서 "물리적 시간의 신뢰성"을 복구해 낸 구글의 극한의 인프라 공학을 장악하기 위함입니다.
• What to Learn:
  • Concepts: Google Spanner, TrueTime API, Atomic Clocks(원자 시계), GPS 수신기, Uncertainty Window (불확실성 구간).
  • Skills: 오차 범위(Confidence Interval)를 런타임 코드에 반영하는 Commit Wait 메커니즘 설계.
• How to Learn:
  • 1단계: GPS와 원자 시계: 일반 NTP(인터넷 타임 서버)를 버리고, 구글의 모든 전 세계 데이터센터 랙(Rack)에 GPS 안테나와 초정밀 원자 시계를 물리적으로 때려 박아 시계 오차(Skew)를 최대 7밀리초(7ms) 이내로 물리적으로 가둬버립니다.
  • 2단계: 불확실성 대기 (Commit Wait): TrueTime API는 시간을 [현재 시간 - 7ms, 현재 시간 + 7ms]라는 불확실성 구간(Interval)으로 반환합니다. 트랜잭션을 저장(Commit)할 때, 이 오차 범위인 7ms 동안 시스템을 아예 대기(Wait)시킵니다. 7ms가 지나면 "이 시간은 완벽히 과거가 되었다"는 것이 물리적으로 증명되므로, 절대적인 시간순 정렬을 보장하는 미친 인프라 철학을 뜯어봅니다.
• Implement: TrueTime 대기(Commit Wait) 시뮬레이션. get_truetime() 함수가 [earliest, latest] 범위를 반환. latest 시간이 실제 시스템 시간보다 과거가 될 때까지 스레드를 강제로 sleep() 시키는 안전 장치(Safety Margin) 로직을 통해 분산 트랜잭션의 엄격한 직렬화(Strict Serializability)를 구현하는 데모.

7. Terminology

8. References

Primary

• [P1] CS2023 - Parallel and Distributed Computing (PDC) - Distributed Systems Properties (Time)
• [P5] SFIA - Systems Design (DESN) - Data Synchronisation

Secondary

• [Time, Clocks, and the Ordering of Events in a Distributed System] Leslie Lamport - (The foundational paper on Logical Clocks)
• [Designing Data-Intensive Applications] Martin Kleppmann - Time, Clocks, and Ordering

Industry

• [Dynamo: Amazon's Highly Available Key-value Store] - Vector Clocks for Conflict Resolution
• [Google Spanner Paper] - TrueTime API and Strict Serializability

9. Final Checklist

Primary

• 분산된 두 서버에서 발생한 이벤트의 선후 관계를 판별할 때, 각 서버의 시스템 타임스탬프(System.currentTimeMillis())를 비교하는 것이 왜 치명적인 안티 패턴인지 설명할 수 있는가?
• 램포트 타임스탬프(Lamport Clock)가 "이벤트 A가 이벤트 B의 원인이라면, A의 카운터는 B보다 작다($A \rightarrow B$)"는 명제를 수신 측 max() 로직을 통해 어떻게 보장하는지 증명할 수 있는가?

Secondary

• 벡터 시계(Vector Clock) 알고리즘을 이용해 두 배열 상태 [2, 1, 0]과 [1, 2, 0]을 비교했을 때, 어느 한쪽이 최신이 아니라 서로 '충돌(Concurrent)' 상태임을 판별하는 수학적 기준을 해부할 수 있는가?
• 아마존 장바구니와 같이 고가용성(AP)을 추구하는 시스템에서 충돌(Conflict)이 발생했을 때, LWW를 버리고 클라이언트 측에 두 버전을 모두 내려주어(Siblings) 유저가 병합하게 만드는 이유를 논증할 수 있는가?

Industry

• 물리적 시간 오차(Clock Skew)로 인한 데이터 유실을 혐오한 Google Spanner가, GPS와 원자 시계를 결합한 TrueTime API로 어떻게 오차를 $\pm 7ms$ 이내로 가둬버렸는지 인프라 관점으로 설계할 수 있는가?
• TrueTime API가 트랜잭션을 커밋(Commit)할 때, 그 오차 범위(예: 7ms)만큼 시스템을 강제로 대기(Wait)시켜 절대적인 선후 관계(Strict Serializability)를 물리적으로 확정 짓는 메커니즘을 평가할 수 있는가?