들어가며: 시간이 깨진 세계에서 순서를 찾다

분산 시스템의 근본 문제

당신이 세 대의 서버로 분산 채팅 서비스를 운영한다. 사용자 Alice가 "안녕"이라고 보내고, Bob이 "잘 있어"라고 답한다. 세 서버는 이 메시지들을 각자 다른 순서로 받을 수 있다:

Server 1: [Alice "안녕", Bob "잘 있어"]

Server 2: [Bob "잘 있어", Alice "안녕"]

Server 3: [Alice "안녕", Bob "잘 있어"]

누가 봐도 Server 2는 이상하다. **"안녕"이 "잘 있어"보다 먼저**였으므로. 그런데 어떻게 이걸 컴퓨터가 알 수 있을까?

시계를 쓰면 되지 않을까?

각 서버가 wall clock(물리 시계)으로 타임스탬프를 찍으면 되지 않을까?

**안 된다.** 분산 시스템에서 시계는 **절대 정확히 동기화되지 않는다**:

- **Clock Drift**: 수정 발진기 정확도는 10^-6 ~ 10^-5 수준. 하루에 수백 ms 편차.

- **NTP 동기화**: 보통 ±수 ms ~ 수십 ms 오차.

- **VM 시계 점프**: 가상화 환경에서 시계가 갑자기 앞뒤로 튀는 현상.

- **Leap Second**: 1초가 삽입/삭제되면서 시계가 뒤로 감.

2012년 Cloudflare는 leap second 때문에 일부 서버가 무한 루프에 빠져 대규모 장애를 겪었다. 물리 시계는 **믿을 수 없다**.

Leslie Lamport의 통찰

1978년 Leslie Lamport가 발표한 "Time, Clocks, and the Ordering of Events in a Distributed System" 논문은 컴퓨터 과학 역사상 가장 영향력 있는 논문 중 하나다. Lamport는 이렇게 질문했다:

> **"시계 없이도 '먼저 일어났다'를 정의할 수 있을까?"**

답은 "예"였고, 이 아이디어에서 Lamport Clock, Vector Clock, Paxos, Causal Consistency 등 수많은 개념이 탄생했다.

이 글에서는 분산 시스템의 시간과 순서 문제를 **세 가지 논리 시계**와 **다섯 가지 일관성 모델**로 나눠 다룬다.

1. Happens-Before 관계

정의

Lamport가 제안한 **happens-before** 관계(`→`)는 세 가지 규칙으로 정의된다:

1. **같은 프로세스 내**: 이벤트 a가 b보다 먼저 발생하면 `a → b`.

2. **메시지 전달**: 프로세스 P가 메시지를 보내고(이벤트 a), 다른 프로세스 Q가 그 메시지를 받으면(이벤트 b), `a → b`.

3. **이행성**: `a → b` 이고 `b → c`이면 `a → c`.

이 관계로부터 **정의되지 않는** 것은 **동시성(concurrent)** 이다:

> **a, b가 서로 happens-before 관계가 아니면 a || b (concurrent).**

물리 시계와의 차이

- **물리 시계**: a의 타임스탬프가 b보다 작으면 "먼저"라고 주장. 하지만 부정확.

- **Happens-before**: 인과 관계가 있을 때만 "먼저". 인과 관계가 없으면 동시.

인과성 예시

Process P: [send M1]───────────────[receive M3]

Process Q: [receive M1][send M2]

Process R: [receive M2][send M3]

- `send M1 → receive M1` (P → Q)

- `receive M1 → send M2` (Q 내부)

- `send M2 → receive M2 → send M3 → receive M3`

- 결국 `send M1 → receive M3` (이행성)

하지만:

- P에서 `send M1` 직후 일어난 이벤트 X와 Q에서 `receive M1` 직전 일어난 이벤트 Y는 **concurrent**. 어느 것이 "먼저"인지 말할 수 없다.

이 철학적 입장이 분산 시스템의 **가장 정직한 시간 정의**다.

2. Lamport Clock: 최소한의 논리 시계

알고리즘

각 프로세스 P는 정수 `L_P`를 유지한다:

1. **이벤트 발생 시**: `L_P := L_P + 1`

2. **메시지 송신 시**: `L_P := L_P + 1`, 메시지에 `L_P` 첨부.

3. **메시지 수신 시**: `L_P := max(L_P, 메시지의 timestamp) + 1`

구현

class LamportClock:

def __init__(self):

self.time = 0

def local_event(self):

self.time += 1

return self.time

def send_event(self):

self.time += 1

return self.time # 메시지에 첨부

def receive_event(self, msg_timestamp):

self.time = max(self.time, msg_timestamp) + 1

return self.time

사용 예시

p = LamportClock()

q = LamportClock()

t1 = p.send_event() # P time = 1

t2 = q.receive_event(t1) # Q time = 2

t3 = q.local_event() # Q time = 3

Lamport Clock의 보장

핵심 성질: **`a → b` 이면 `L(a) < L(b)`**.

즉, a가 b보다 happens-before라면, Lamport timestamp도 반드시 더 작다.

중요한 한계

**역이 성립하지 않는다**: `L(a) < L(b)` 라고 해서 `a → b` 인 것은 아니다. 그냥 동시성(concurrent)일 수도 있다.

예시:

P: [a, L=1] [b, L=2]

Q: [c, L=1] [d, L=2]

P와 Q 사이에 메시지가 없으면 a와 c는 동시성이지만 둘 다 L=1이다. 그리고 b(L=2) vs c(L=1)는 Lamport상 b가 커 보이지만 사실은 concurrent다.

결론: Lamport Clock의 쓸모

Lamport Clock은:

- **전체 순서 부여**: 타임스탬프가 같을 때 프로세스 ID로 tie-break하면 모든 이벤트에 고유 전체 순서 가능.

- **인과 관계 감지는 불가**: 두 이벤트가 인과 관계인지 concurrent인지 구분 못함.

- **용도**: 분산 뮤텍스, 순서가 있는 큐 구현.

인과 관계를 알고 싶으면 다음 단계, **Vector Clock**이 필요하다.

3. Vector Clock: 인과 관계를 정확히 추적

알고리즘

N개 프로세스가 있으면, 각 프로세스는 **길이 N의 벡터**를 유지한다:

1. **초기**: `V_P = [0, 0, ..., 0]`

2. **이벤트 발생 시**: `V_P[P] := V_P[P] + 1`

3. **메시지 송신 시**: `V_P[P] := V_P[P] + 1`, 메시지에 `V_P` 첨부.

4. **메시지 수신 시**:

- `V_P[i] := max(V_P[i], 받은 V[i])` (모든 i)

- `V_P[P] := V_P[P] + 1`

비교 규칙

두 벡터 V1, V2에 대해:

- **V1 < V2**: 모든 i에 대해 `V1[i] <= V2[i]`, 그리고 최소 하나의 i에 대해 `V1[i] < V2[i]`.

- **V1 = V2**: 모든 i에 대해 `V1[i] = V2[i]`.

- **V1 || V2 (concurrent)**: 위 두 경우가 아닐 때.

그리고 **핵심 성질**:

> **a → b ⟺ V(a) < V(b)**

즉, vector clock은 인과 관계를 **완벽하게** 표현한다. iff(양방향)이다.

구현

class VectorClock:

def __init__(self, process_id, num_processes):

self.id = process_id

self.vector = [0] * num_processes

def local_event(self):

self.vector[self.id] += 1

return list(self.vector)

def send_event(self):

self.vector[self.id] += 1

return list(self.vector)

def receive_event(self, msg_vector):

for i in range(len(self.vector)):

self.vector[i] = max(self.vector[i], msg_vector[i])

self.vector[self.id] += 1

return list(self.vector)

def compare(v1, v2):

less = all(v1[i] <= v2[i] for i in range(len(v1)))

greater = all(v1[i] >= v2[i] for i in range(len(v1)))

if less and greater:

return "equal"

elif less:

return "before"

elif greater:

return "after"

else:

return "concurrent"

사용 예시

p = VectorClock(0, 3)

q = VectorClock(1, 3)

r = VectorClock(2, 3)

va = p.local_event() # P: [1,0,0]

vb = p.send_event() # P: [2,0,0]

vc = q.receive_event(vb) # Q: [2,1,0]

vd = r.local_event() # R: [0,0,1]

print(compare(va, vc)) # "before" (a → c)

print(compare(va, vd)) # "concurrent"

Vector Clock의 실전: DynamoDB와 Riak

Amazon Dynamo 논문(2007)은 vector clock을 **conflict 감지**에 사용했다:

1. 클라이언트가 키를 쓸 때 vector clock 첨부.

2. 여러 replica에 복제 → 네트워크 파티션으로 분기.

3. 다른 클라이언트가 두 버전을 읽을 때 vector clock을 비교.

4. `V1 < V2` → V2가 최신. V1은 폐기.

5. `V1 || V2` → **충돌**. 애플리케이션이 병합해야 함.

**Riak**도 이 방식을 계승했다. 실전에선 vector clock의 크기가 문제다: 수십 개 replica면 벡터가 매우 커진다. Dynamo는 **pruning**으로 오래된 엔트리를 정리한다.

Version Vector

Vector clock과 비슷하지만 미묘하게 다른 **Version Vector**도 있다. 데이터 아이템별로 유지하며, 복제 간 버전 관계를 추적하는 데 쓰인다. Dynamo, CRDT 등에서 사용.

4. Hybrid Logical Clock (HLC): 이론과 실전의 결혼

동기

Vector clock은 크기가 N(프로세스 수)에 비례한다. 수천 개 노드에서는 부담스럽다. 반대로 wall clock은 작지만 부정확하다.

2014년 Kulkarni 등이 발표한 **Hybrid Logical Clock (HLC)** 은 이 둘을 절묘하게 결합한다:

> **"Wall clock을 기반으로 하되, happens-before를 보장하는 논리 시계."**

HLC 알고리즘

각 프로세스는 두 필드를 가진 타임스탬프를 관리한다:

- **l** (logical component): wall clock의 최대값 저장.

- **c** (counter): 같은 l에서 순서 부여.

class HybridLogicalClock:

def __init__(self):

self.l = 0

self.c = 0

def now(self):

물리 시계 (마이크로초)

return int(time.time() * 1_000_000)

def local_event(self):

pt = self.now()

l_old = self.l

self.l = max(l_old, pt)

if self.l == l_old:

self.c += 1

else:

self.c = 0

return (self.l, self.c)

def send_event(self):

return self.local_event()

def receive_event(self, msg_l, msg_c):

pt = self.now()

l_old = self.l

self.l = max(l_old, msg_l, pt)

if self.l == l_old == msg_l:

self.c = max(self.c, msg_c) + 1

elif self.l == l_old:

self.c += 1

elif self.l == msg_l:

self.c = msg_c + 1

else:

self.c = 0

return (self.l, self.c)

HLC의 특성

1. **공간**: O(1). 프로세스 수와 무관하게 (l, c) 두 개.

2. **근사 wall clock**: `l` 필드는 실제 wall clock과 크게 벗어나지 않는다.

3. **Happens-before 보장**: `a → b` 이면 HLC(a) < HLC(b).

4. **역은 성립 안 함**: Lamport clock과 같은 한계.

HLC의 매력

HLC는 **"대략적인 실제 시간"**을 제공하면서도 **인과성**을 보장한다. 그래서:

- **로그 정렬이 편하다**: 사람이 읽을 때 시간이 그럴듯하게 흐른다.

- **TTL 관리 가능**: 실제 시간과 연결되니 expiration 구현 가능.

- **Wall clock이 부정확해도 안전**: 그냥 논리 시계로 퇴화할 뿐.

실전: CockroachDB와 MongoDB

**CockroachDB**는 HLC를 핵심에 둔다:

- 모든 트랜잭션에 HLC 타임스탬프 부여.

- Snapshot isolation의 스냅샷 시점으로 사용.

- 실제 wall clock 오차가 `max_offset` (기본 500ms) 이하라고 가정.

- 오차가 이를 초과하면 트랜잭션 재시도 또는 서버 종료.

**MongoDB 3.6+**도 HLC를 쓴다. `clusterTime`이 바로 HLC다. 다중 문서 트랜잭션과 change stream의 순서 보장에 사용.

**YugabyteDB, TiDB** 등 대부분의 현대 NewSQL이 HLC를 채택했다. 사실상의 표준이 되었다.

5. 극단의 정밀함: Google Spanner의 TrueTime

왜 TrueTime인가

HLC는 훌륭하지만 **외부 일관성(external consistency)** 을 완전히 보장하진 않는다. 외부 일관성이란:

> **"실제 시간상 T2가 T1 이후에 시작되면, 시스템에서도 T2는 T1 이후로 보여야 한다."**

HLC는 wall clock을 근사할 뿐 정확하지 않아서, 이 보장을 제공하지 못한다.

Google Spanner는 이를 위해 **TrueTime API**를 도입했다. 원리:

1. **GPS + 원자시계**를 데이터센터마다 설치.

2. 여러 개를 voting으로 검증.

3. TrueTime API는 `TT.now()` 대신 **`TT.now(): [earliest, latest]`** 를 반환. 즉, "지금은 이 구간 어딘가"라는 **불확실성 구간**을 명시.

4. 보통 구간 크기 `ε`는 1~7ms.

Commit-wait

Spanner는 트랜잭션 커밋 전에 **commit-wait**를 수행한다:

1. 트랜잭션 T가 commit timestamp s를 정함.

2. TT.now() 의 latest가 s를 넘을 때까지 대기.

3. 이 시점에서 s는 "진짜로 과거"가 되었음이 보장됨.

4. 이제 commit을 완료하고 클라이언트에 응답.

이 대기 덕분에, 다른 노드들은 `s` 이후의 타임스탬프로 트랜잭션을 시작하면 확실히 T 이후로 보인다.

대가

TrueTime은 정확도만큼의 **지연**을 트랜잭션에 추가한다. `ε = 7ms`이면 평균 3.5ms의 대기. 이는 Google이 하드웨어에 투자할 가치가 있다고 판단한 비용이다.

일반 시스템은?

Google처럼 원자시계를 못 살 뿐이라면, HLC가 가장 현실적인 타협이다. AWS는 **Time Sync Service**로 NTP를 고정밀 수준(~1ms)으로 제공한다. Amazon은 이를 위해 PTP + 원자시계 조합의 하드웨어를 배포했다.

6. 일관성 모델 개관

지금까지는 "시간과 순서"를 다뤘다. 이제 그 위에서 정의되는 **일관성 모델**을 살펴보자.

일관성 모델의 계층

강함 ─────────────────────────────────── 약함

┌────────────────────────────────────────────┐

│ Strict Consistency │

│ Linearizability │

│ Sequential Consistency │

│ Causal Consistency │

│ Eventual Consistency │

│ Weak / FIFO / PRAM │

└────────────────────────────────────────────┘

각 모델은 **"클라이언트가 관찰할 수 있는 동작"** 을 정의한다. 강할수록 프로그래밍 쉽고 성능 나쁘다.

7. Linearizability: "진짜 원자성"

정의

**Linearizability**는 가장 직관적인 강한 일관성이다:

> **"모든 연산이 즉시, 원자적으로, 어떤 순간에 발생한 것처럼 보인다."**

보다 형식적으로:

1. 각 연산이 호출(invocation)과 응답(response) 사이의 어떤 **선형화 시점(linearization point)** 에 발생한 것으로 간주.

2. 실제 시간상 T1이 T2보다 먼저 끝났다면, 선형화 순서도 T1이 T2보다 먼저.

3. 이 순서가 **마치 단일 스레드가 실행한 것처럼** 일관되어야 한다.

예시

Client A: W(x=1) [t=10]──────[t=20]

Client B: R(x) [t=15]──────[t=25]

**Linearizable이면**: B의 읽기는 반드시 `x=1`을 반환해야 한다. 왜? B의 읽기 호출이 t=15이고 A의 쓰기가 t=20에 완료되었는데, B는 그 뒤까지(t=25) 기다리므로 t=20~25 사이에 A의 쓰기가 완료됨을 관찰할 수 있다.

단, B의 읽기가 A의 쓰기 완료 **전에** 끝났다면 (예: B의 응답 t=18), B는 0 또는 1 어느 것이나 반환 가능.

Strict Consistency와의 차이

**Strict Consistency**는 "쓰기가 즉시 모든 곳에서 보여야 한다"로, **물리적으로 불가능**하다 (빛의 속도). 그래서 이론적 이상형이고, Linearizability가 실질적 최강이다.

구현 방법

Linearizability는 다음 중 하나로 달성된다:

1. **단일 Leader + 동기식 복제**: 모든 쓰기가 Leader를 거치고, 읽기도 Leader에서 (또는 확인된 replica에서).

2. **Consensus 기반**: Raft, Paxos로 로그를 전역적으로 정렬.

3. **Quorum + Strict Read**: `R + W > N` + 모든 replica의 동기화.

etcd, ZooKeeper, Spanner는 linearizable하다.

비용

- 네트워크 왕복 비용

- CAP에서 **CP**: 파티션 발생 시 가용성 포기.

- Latency가 높음.

8. Sequential Consistency: 약간의 양보

정의

Leslie Lamport가 1979년 정의한 **Sequential Consistency**는 Linearizability보다 약간 약하다:

> **"모든 연산이 어떤 순차 순서로 실행된 것처럼 보인다. 이 순서는 각 프로세스의 프로그램 순서를 존중한다."**

핵심 차이: **실제 시간 순서는 무시**. 각 프로세스 내부의 순서만 유지하면 된다.

예시

Client A: W(x=1) [t=10, 완료 t=20]

Client B: R(x) [t=25, 완료 t=30]

Sequential consistency에서 B가 `x=0`을 반환하는 것이 허용될 수 있다. 왜? 전체 순서가 `[B의 R(x=0), A의 W(x=1)]` 이라고 해석될 수 있기 때문이다. 실제 시간상 A가 먼저 끝났지만, 이 사실은 무시된다.

언제 쓰이나

- **멀티코어 CPU 메모리 모델**: 대부분의 현대 CPU(ARM, POWER)는 sequential consistency보다 약한 모델을 쓰지만, x86은 거의 sequential에 가깝다.

- **분산 캐시의 기본 모드**: 약한 쪽으로 양보해서 성능 추구.

Linearizability와의 차이 요약

| 항목 | Linearizability | Sequential |

|---|---|---|

| **프로세스 내부 순서** | 유지 | 유지 |

| **실제 시간 순서** | 유지 | 무시 |

| **성능** | 낮음 | 약간 높음 |

| **예시 시스템** | etcd, Spanner | ZooKeeper local read |

9. Causal Consistency: 인과성만 보장

정의

**Causal Consistency**는 happens-before 관계를 존중한다:

> **"인과 관계가 있는 연산들은 모든 노드에서 같은 순서로 보인다. 인과 관계가 없는 연산들은 다르게 보일 수 있다."**

즉, `a → b` 이면 모든 노드가 a를 먼저 본 후 b를 봐야 한다. 하지만 `a || b` (concurrent)이면 노드마다 순서가 다를 수 있다.

예시: 소셜 미디어

Alice: "오늘 프로포즈 받았어!" (t=10)

Bob: [Alice의 글 본 후] "축하해요!" (t=11)

Carol: [Alice의 글 본 적 없음] "날씨 좋네요" (t=10.5)

Causal consistency는:

- Alice의 글과 Bob의 댓글은 **모든 사람이 이 순서로** 봐야 한다 (인과 관계).

- Alice의 글과 Carol의 글은 **어떤 순서로도** 보일 수 있다 (인과 관계 없음).

이는 Sequential보다 훨씬 약하지만 **실용적으로 충분**한 경우가 많다.

구현

Vector Clock이 직접적인 구현 도구다. Riak, COPS 등의 시스템이 사용.

Causal+ Consistency

**Causal Consistency**는 concurrent 연산들의 순서가 노드마다 달라도 된다고 한다. 하지만 이는 이상하게 느껴질 수 있다. **Causal+ Consistency**는 추가로 **convergence**를 요구한다:

> **"모든 concurrent 연산은 모든 노드에서 동일한 (임의의) 순서로 결정된다."**

이는 CRDT와 함께 자주 등장한다.

장점

- **파티션 견딤**: CAP에서 AP 선택 가능.

- **성능**: 동기화 최소화.

- **직관적**: 대부분의 개발자가 "인과성"은 이해한다.

10. Eventual Consistency: 결국은 수렴한다

정의

가장 약한(하지만 가장 실용적인) 모델:

> **"업데이트가 더 이상 없다면, 결국 모든 노드가 같은 값을 갖는다."**

형식적 보장은 이게 전부다. 중간 상태에 대한 제약이 없다.

예시와 주의점

Client writes x=1 on replica A.

Client reads x from replica B (복제 전) → 0 반환.

Client reads x from replica B (복제 후) → 1 반환.

일시적으로 stale한 값이 보이지만, 결국엔 일관된다. "결국"이 언제인지는 **보장되지 않는다**.

Read-your-writes 위반

Eventual consistency의 악명 높은 문제:

A가 프로필 업데이트 (W to replica X).

A가 즉시 자기 프로필 조회 (R from replica Y).

Replica Y는 아직 복제 받지 못함 → 옛 값 반환.

A: "어? 내가 방금 업데이트 했는데?"

이를 막으려면 **Session Guarantees**:

- **Read-your-writes**: 자신의 쓰기는 항상 보임.

- **Monotonic reads**: 한 번 본 것보다 최신 값만 봄.

- **Monotonic writes**: 자신의 쓰기들은 순서대로.

- **Writes-follow-reads**: 읽은 것에 기반한 쓰기는 순서대로.

이 네 개를 합치면 **Session Consistency**가 된다. 실전 시스템(DynamoDB, MongoDB)이 제공하는 중간 수준이다.

어디에 쓰이나

- **DNS**: 변경이 전 세계 전파되는 데 시간 걸림.

- **CDN**: 캐시 무효화는 eventual.

- **DynamoDB**: 기본 모드.

- **Cassandra**: 기본 모드.

- **Git**: 여러 클론의 변경이 결국 merge.

트레이드오프

- **장점**: 고가용성, 낮은 지연, 파티션 내성.

- **단점**: 프로그래머가 중간 상태를 처리해야 함. 충돌 해결 로직 필요.

11. 실전 시스템 비교

| 시스템 | 일관성 모델 | 시계 |

|---|---|---|

| **etcd** | Linearizable | Raft 로그 |

| **ZooKeeper** | Sequential (Linearizable writes) | Zab |

| **Spanner** | External Consistency (Linearizable+) | TrueTime |

| **CockroachDB** | Serializable Snapshot | HLC |

| **YugabyteDB** | Serializable | HLC |

| **TiDB** | Snapshot / Serializable | TSO (중앙 타임스탬프) |

| **MongoDB** | Linearizable (writeConcern majority) | HLC (clusterTime) |

| **DynamoDB** | Eventual or Strong | Vector clock (legacy) |

| **Cassandra** | Tunable (QUORUM/ONE/ALL) | Timestamp (client) |

| **Riak** | Eventual | Vector clock |

클라이언트의 선택권

많은 시스템이 **연산별로 일관성 수준을 선택**할 수 있게 한다:

Cassandra

session.execute(query, consistency_level=ConsistencyLevel.QUORUM)

DynamoDB

client.get_item(Key=..., ConsistentRead=True)

MongoDB

db.collection.find(...).readConcern({ level: "linearizable" })

이는 **"비싼 일관성은 필요할 때만 지불"** 하는 실용적 접근이다.

12. CAP와 PACELC

CAP 정리

Eric Brewer의 CAP 정리 (2000):

> **Consistency, Availability, Partition tolerance 중 2개만 택할 수 있다.**

정확히는 **"파티션이 발생했을 때 C와 A 중 하나를 포기해야 한다"** 이다. 파티션은 선택이 아니라 현실이므로 실제 선택은 **CP vs AP**:

- **CP**: 파티션 중 일관성 유지, 일부 요청 실패. (etcd, ZooKeeper, HBase)

- **AP**: 파티션 중 가용성 유지, 일관성 타협. (Cassandra, DynamoDB, Riak)

PACELC: 더 완전한 그림

Daniel Abadi의 PACELC:

> **Partitioned → A vs C. Else → Latency vs Consistency.**

즉, 파티션이 **없을 때도** 선택이 있다: 강한 일관성을 위해 latency를 지불하거나, 빠른 응답을 위해 약한 일관성을 택하거나.

| 시스템 | PAC | ELC |

|---|---|---|

| **Spanner** | PC | EC (지연 감수) |

| **Cassandra** | PA | EL (빠름) |

| **MongoDB** | PC | EL (기본) / EC (majority) |

| **DynamoDB** | PA | EL (기본) / EC (strong read) |

13. 실전 팁: 어떤 일관성을 언제?

강한 일관성이 꼭 필요한 경우

- **금융 거래**: 잔고 업데이트.

- **재고 관리**: 판매 가능 수량.

- **경매/예약**: 단일 승자.

- **인증/권한**: 로그인 세션.

- **락/리더 선출**: Consensus 필수.

Causal이면 충분한 경우

- **댓글/답글**: 원글 순서만 유지.

- **메시징**: 한 대화 내 순서.

- **뉴스피드**: 인과성만 유지하면 OK.

Eventual로 충분한 경우

- **조회수 카운터**: 정확성 낮아도 됨.

- **좋아요 수**: 약간의 오차 허용.

- **추천 점수**: 실시간이 아님.

- **로그/메트릭**: 약간 늦게 도착해도 됨.

혼합 전략

현실에선 **한 시스템 안에서도 연산마다 다른 일관성**을 쓴다:

- 돈 계산 → linearizable

- 사용자 이름 조회 → eventual

- 프로필 수정 후 조회 → read-your-writes

모든 것을 강한 일관성으로 만드는 건 **비싸고 느리다**. 꼭 필요한 곳만.

퀴즈로 복습하기

**A.** **알 수 없다.** Lamport clock은 `a → b` 이면 `L(a) < L(b)` 를 보장하지만, 역은 성립하지 않는다. 즉, `L(a) < L(b)` 라도 a와 b가 concurrent일 수 있다. Vector clock만이 `a → b ⟺ V(a) < V(b)` 의 **양방향 관계**를 제공한다. 인과 관계 감지가 필요하면 vector clock을 써야 한다.

**A.** **벡터 크기가 프로세스 수에 비례**한다는 점이다. 수천 개 노드에서는 메시지 오버헤드가 커진다. 해결책: (1) **Pruning**: 오래된 엔트리 제거. (2) **Version Vector**: 복제본(한정된 수)에만 대응. (3) **Dotted Version Vector**: 클라이언트별이 아닌 서버별 카운터. (4) **HLC**: 완전히 다른 접근으로 O(1) 공간에 대략적인 인과성 제공.

**A.** **Linearizability**는 **단일 객체에 대한 동시 연산**의 순서를 다룬다. "실제 시간 순서를 존중하는 원자적 원소 연산"이 핵심. **Serializability**는 **트랜잭션(여러 연산의 그룹)의 동시성**을 다룬다. "어떤 순차 실행과 동일한 결과"가 핵심. 둘은 독립적이라 조합 가능하다: **Strict Serializability** = Linearizable + Serializable. 예시: PostgreSQL의 SERIALIZABLE은 linearizable하지 않을 수 있다 (단일 노드라 주로 문제 안 됨). Spanner의 external consistency는 strict serializable이다.

**A.** HLC는 (l, c) 쌍을 사용한다. `l`은 wall clock을 따라가며 **실제 시간과 근사**한 값을 유지한다. `c`는 같은 l 내에서 순서를 부여하는 논리 카운터다. 메시지 수신 시 `l = max(local_wall, local_l, msg_l)`로 갱신해서 **happens-before를 보장**한다. 결과: (1) O(1) 공간, (2) 실제 시간과 가까운 값 (로그 정렬 가능), (3) 인과성 유지, (4) wall clock 오차가 커도 논리 시계로 안전하게 퇴화. CockroachDB, MongoDB, YugabyteDB가 이 방식을 쓴다.

**A.** 여러 방법이 있다: (1) **Sticky session**: 사용자를 항상 같은 replica로 라우팅. (2) **Timestamp tracking**: 클라이언트가 마지막으로 본 타임스탬프를 기억하고, 읽을 때 그 이상을 요구. (3) **Read from primary**: 자신의 최근 쓰기는 primary(또는 master) replica에서 읽기. (4) **Versioned reads**: 쓰기 후 받은 version을 세션에 저장, 이후 읽기에 해당 version 이상 요구. DynamoDB의 `ConsistentRead=True`나 MongoDB의 `readConcern: "majority"`가 이런 접근이다. 단, 이는 대부분 **성능 비용**을 동반한다.

마치며: 시간과 순서, 그리고 겸손함

핵심 정리

1. **물리 시계는 믿을 수 없다**. 분산 시스템에서 "언제"는 근본적으로 불분명하다.

2. **Lamport clock**: 전체 순서는 주지만, concurrent 여부는 알 수 없다.

3. **Vector clock**: 인과 관계를 완벽히 표현. 대신 공간 비용.

4. **HLC**: 실전의 타협. O(1) + 근사 wall clock + 인과성.

5. **TrueTime**: Google이 하드웨어로 푼 궁극의 답.

6. **일관성 모델**: 강하면 프로그래밍 쉽고 성능 나쁘다.

7. **Linearizability**: 가장 직관적인 강한 보장.

8. **Causal Consistency**: 인과성만 유지하는 실용적 중간.

9. **Eventual Consistency**: 고가용성의 대가.

시스템 설계자에게

분산 시스템을 설계할 때 스스로에게 물어야 할 질문들:

1. **정말 strong consistency가 필요한가?** 대부분의 답은 "아니오"다.

2. **인과성만으로 충분한가?** 대부분의 소셜/협업 앱에서 충분하다.

3. **어떤 데이터는 linearizable이고 어떤 데이터는 eventual일 수 있는가?** 정답은 거의 항상 "다르다".

4. **시계 오차가 얼마나 허용되는가?** HLC의 max_offset을 결정한다.

5. **파티션 중에 읽기/쓰기 중 어느 것을 포기할 것인가?** CAP 선택.

겸손함

Leslie Lamport는 2013년 튜링상 수상 연설에서 이렇게 말했다:

> **"Distributed systems are weird. Very weird."**

30년 넘게 이 분야를 만들어 온 사람이 한 말이다. 우리가 분산 시스템을 설계할 때 느끼는 혼란은 당연한 것이다. 이론을 알면 적어도 **무엇이 불가능한지**를 알 수 있다. 그것만으로도 많은 버그를 막을 수 있다.

참고 자료

- [Time, Clocks, and the Ordering of Events in a Distributed System (Lamport, 1978)](https://lamport.azurewebsites.net/pubs/time-clocks.pdf) - 고전 중의 고전

- [Logical Physical Clocks (Kulkarni et al., 2014)](https://cse.buffalo.edu/tech-reports/2014-04.pdf) - HLC 원 논문

- [Spanner: Google's Globally-Distributed Database (2012)](https://research.google/pubs/pub39966/) - TrueTime

- [Dynamo: Amazon's Highly Available Key-value Store (2007)](https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf) - Vector clock in practice

- [Consistency in Non-Transactional Distributed Storage Systems (Viotti & Vukolic, 2016)](https://arxiv.org/abs/1512.00168) - 일관성 모델 서베이

- [Jepsen: Distributed Systems Safety Analysis](https://jepsen.io/) - 실제 시스템의 일관성 검증

- [Designing Data-Intensive Applications, Ch.5, 8, 9](https://dataintensive.net/) - Martin Kleppmann

- [CMU 15-721 Advanced Database Systems: Time](https://15721.courses.cs.cmu.edu/spring2023/)