Time, Clocks & State Ordering

1. Overview

시간, 시계 및 상태 순서 정렬(Time, Clocks & State Ordering, TCS)은 모든 컴퓨터의 시계가 조금씩 다르게 흐르는 '클록 드리프트(Clock Drift)'의 혼돈 속에서, 어떤 사건이 먼저 일어났는지 수리적으로 판결하는 분산 시스템의 시간 물리학입니다.

학습자는 하드웨어 시계(NTP)만으로는 분산 데이터의 선후 관계를 물리적으로 보장할 수 없음을 이해하고, 사건의 인과 관계(Causality)에 집중하는 **논리적 시계(Logical Clock)**의 사상을 배웁니다. 특히, 단일 숫자로 순서를 매기는 **램포트 타임스탬프(Lamport Timestamps)**와, 충돌 여부까지 물리적으로 판별하는 **벡터 클록(Vector Clocks)**의 수리 구조를 익힙니다. 이를 통해 '나중에 온 요청이 먼저 처리'되는 물리적 결함을 방지하고, 전역적으로 일관된 데이터 상태를 유지하는 하이엔드 순서 제어 역량을 확보합니다.

2. Scope & Boundaries

In-Scope

• Physical Clock Dynamics: NTP, PTP를 이용한 하드웨어 시각 동기화의 물리적 한계
• Logical Clock Foundations: Lamport Timestamps의 생성 및 전달 수리 규칙
• Causal Ordering Mechanics: 인과 관계를 보존하는 벡터 클록(Vector Clocks)의 연산 물리학
• Total Ordering Strategies: 전역적인 단일 순서 리스트를 만들기 위한 분산 기법
• Happened-before Relation: 사건 간의 선후 관계를 정의하는 수학적 모델 ($a \rightarrow b$)

Out-of-Scope

• CPU 내부의 하드웨어 타이머 회로 상세 (02-01-XX 영역에서 분담)
• 운영체제의 프로세스 스케줄링 시간 단위 (03-01-XX 영역에서 분담)

Boundaries

• TCS vs. Consensus Algorithms: 합의 알고리즘(07-02-02)이 '단일 상태 확정'에 집중한다면, TCS는 '상태 전이들의 선후 인과 관계 정의'에 집중하여 구분합니다.

3. Counterexample

• 단순히 "현재 시간(DateTime.now) 찍기"라 설명하는 것은 TCS 학습이 아닙니다. 왜 물리 시계를 이용한 데이터 업데이트(Last Write Wins)가 하드웨어 오차로 인해 멀쩡한 최신 데이터를 소리 소문 없이 지워버리는지 수리 증명할 수 있어야 하며, 벡터 클록이 노드 수가 수천 개로 늘어날 때 왜 메시지 헤더 크기를 물리적으로 폭발시켜 시스템을 마비시키는지 분석하지 못한다면 TCS의 딜레마를 이해하지 못한 것입니다.

4. Prerequisites

• Network Layers & Protocols (Basic): 네트워크 패킷 지연(Latency) 이해가 필수입니다. (08-01-02 기반 역량)
• Sets & Mathematical Logic (Recommended): 부분 순서(Partial Ordering) 수학적 이해가 권장됩니다. (04-01-01 기초 역량)

5. Learning Map

1. The Clock Mirage: 모든 컴퓨터의 시각이 완벽히 일치할 수 없다는 하드웨어적 불확실성을 인정합니다.
2. Order Without Numbers: '시간'을 버리고 '인과(Causality)'라는 새로운 물리 잣대를 도입합니다.
3. Causal Tracking: 누가 누구의 영향을 받았는지 꼬리표(Vector)를 붙여 추적합니다.
4. The Arrow of Time: 흩어진 노드들이 수리적으로 약속된 단 하나의 실행 순서에 동기화되게 만듭니다.

6. Learning Topics

Basic

Core: 물리적 시계와 NTP의 한계 (Physical Clock Limits)

• Why to Learn: 서버 간 수 밀리초의 시차만으로도 분산 데이터의 순서가 뒤바뀔 수 있음을 알기 위해서입니다.
• What to Learn:
  • Clock Drift: 수정 진동자의 물리적 차이로 발생하는 시각 어긋남
  • NTP (Network Time Protocol): 시각 동기화의 작동 원리와 잔여 오차 물리
  • Monotonic vs Wall-clock: 시간 측정용 시계와 시각 표시용 시계의 하드웨어적 구분
• How to Learn:
  • 두 대의 서버에서 NTP를 돌려도 발생하는 마이크로초 단위의 시각 차이를 수치로 측정 실습
  • 시계가 거꾸로 흐를 때(Clock Skew) 애플리케이션 로그 순서가 뒤틀리는 현상 관찰
• Implement: 현재 시각이 아닌, 프로세스 시작 시점부터 흐른 절대 시간을 반환하는 MonotonicTimer

Recommended

Core: 램포트 타임스탬프와 논리 시계 (Lamport Clocks)

• Why to Learn: '시간' 대신 '사건 발생 순서'라는 수리적 절대치를 도입하여 정합성을 보장하기 위함입니다.
• What to Learn:
  • Happened-before Relation: 사건 $A$가 사건 $B$에 영향을 주었음을 정의하는 수리 기호
  • Tick-and-Update Rule: 메시지를 주고받을 때마다 논리 시각을 갱신하는 물리 규칙
  • Tie-breaking: 동일한 논리 시각 발생 시 노드 ID로 순서를 강제하는 법
• How to Learn:
  • 세 개의 노드가 메시지를 주고받는 다이어그램에서 각 사건의 램포트 숫자를 직접 매겨보는 실습
  • 램포트 시계가 '인과 관계'는 보존하지만 '동시성(Concurrency)'은 구별 못 함을 수리 분석
• Implement: 메시지를 보낼 때 숫자를 키우고, 받을 때 최댓값으로 갱신하는 기초 LamportClock

Practical

Core: 벡터 클록과 인과성 추적 (Vector Clocks)

• Why to Learn: 두 데이터 변경이 서로를 모르는 상태에서 동시에 일어났는지(충돌) 물리적으로 판별하기 위해서입니다.
• What to Learn:
  • Multi-dimensional Counter: 각 노드별 시각을 배열(Vector)로 관리하는 구조
  • Causality Violation: 벡터 값을 비교하여 선후 관계가 명확한지, 아니면 충돌(Conflict)인지 판별하는 수리 모델
  • Version Vectors: 분산 저장소에서 데이터 버전을 관리하는 물리적 활용
• How to Learn:
  • 서로 다른 노드에서 발생한 두 이벤트의 벡터 값을 비교하여 '충돌' 발생 시점을 수리적으로 도출하는 실습
  • 벡터 클록의 크기가 노드 수에 비례하여 커지는 물리적 부담을 계산
• Implement: 두 벡터 클록을 입력받아 Ancestor, Descendant, Concurrent 중 하나를 반환하는 VectorComparisonEngine

Advanced

Core: 구글 스패너의 하이브리드 시계 (TrueTime Mechanics)

• Why to Learn: 물리 시계와 논리 시계를 결합하여 지구적 규모의 강력한 일관성을 달성하기 위함입니다.
• What to Learn:
  • TrueTime API: 오차 범위를 포함한 시간(Earliest, Latest)을 제공하는 물리 장치
  • Commit Wait: 시계 오차 범위만큼 하드웨어를 물리적으로 정지시켜 순서를 보장하는 법
  • HLC (Hybrid Logical Clocks): NTP의 정밀함과 논리 시계의 인과성을 융합한 수리 모델
• How to Learn:
  • 구글 스패너 논문을 분석하여 '시계 오차'가 쿼리 처리량($TPS$)에 미치는 물리적 영향 산출 실습
  • HLC가 갑작스러운 시계 점프(Time Jump) 상황에서 어떻게 시스템을 방어하는지 시뮬레이션
• Implement: NTP 시각 정보에 하이 인덱스를 붙여 논리적 순서를 강화한 기초 HybridClock

7. Terminology

8. References

Primary

• [P1] CS2023 - SF/Systems Fundamentals (Time and clocks in distributed systems) — Core requirements.
• [P1] CS2023 - PD/Parallel and Distributed Computing (Logical clocks) — Operational context.

Secondary

• [Time, Clocks, and the Ordering of Events in a Distributed System] Leslie Lamport — The seminal paper.
• [Designing Data-Intensive Applications (DDIA)] Martin Kleppmann — Chapter on Distributed Systems Challenges.

Industry

• [Google Spanner: TrueTime and External Consistency] — Precision timing at scale.
• [Basho: Why Vector Clocks are Easy] — Practical implementation guide for Riak.

9. Final Checklist

Primary

• '물리적 시계' 하나만으로 분산 시스템의 데이터 선후 관계를 판결할 때 왜 물리적 오류(Data Loss)가 발생하는지 설명 가능한가? (P1)
• '램포트 타임스탬프'가 보장하는 '부분 순서(Partial Ordering)'의 수리적 의미를 기술할 수 있는 가? (P1)

Secondary

• '벡터 클록'을 사용하여 두 사건이 '인과 관계'에 있는지 아니면 '동시 발생'인지 물리적 배열 값을 들어 논증 가능한가?
• NTP가 시각을 동기화하는 과정에서 발생하는 '네트워크 지터(Jitter)'가 시각 정확도의 물리적 한계점임을 소통 가능한가?

Industry

• 글로벌 데이터 복제 설계 시, 'Last Write Wins' 정책이 시계 오차($Clock Skew$) 하에서 유발하는 비즈니스 위기를 제안할 수 있는 가? (SFIA)
• 구글의 'TrueTime'이 제공하는 불확실성 구간($Interval$)이 분산 트랜잭션의 커밋 지연에 미치는 물리적 영향을 분석할 수 있는 가?