시계 제한 대기 (Clock-Bound Wait)

시계 제한 대기 (Clock-Bound Wait) — 시계 오차를 시간으로 지불하기

1. 문제: HLC로도 안 잡히는 순서가 있다

HLC의 인과율 보장에는 숨은 전제가 있다. 인과가 시스템이 볼 수 있는 메시지를 타고 흐를
때만 작동한다는 것이다. max 규칙이 시계를 당겨주는 것은 타임스탬프가 실려 다닐 때뿐이다.
그런데 현실의 인과는 시스템 밖으로도 흐른다.

10:00.000  클라이언트1 → 서버 A에 쓰기: X = 1
           A의 시계는 빠름 → 실제보다 미래의 타임스탬프 부여
10:00.001  클라이언트1이 클라이언트2에게 슬랙으로 알림: "X 썼어, 확인해봐"
10:00.002  클라이언트2 → 서버 B에 쓰기: Y = 1
           B의 시계는 느림 → X보다 작은 타임스탬프 부여

실제 세계에서는 X가 Y보다 명백히 먼저다(슬랙 메시지가 인과 사슬이다). 그러나 시스템 안에는
그 사슬의 흔적이 없다 — 클라이언트2는 A의 타임스탬프를 들고 오지 않았으므로 HLC가 당겨줄
것이 없다. 결과적으로 나중 사건 Y가 더 작은 타임스탬프를 받을 수 있다. 이제 누군가 그
사이 시점의 스냅샷을 읽으면 Y는 보이는데 X는 안 보인다. 인과적으로 뒤인 것이 보이면서 앞인
것이 안 보이는 이상한 스냅샷이다.

이것을 막는 성질을 외부 일관성(external consistency) 이라 한다. 실시간으로 먼저 커밋된
트랜잭션은 반드시 더 작은 타임스탬프를 가져야 한다는 요구다.

2. 열쇠: 시계를 "점"이 아니라 "구간"으로 읽는다

시계에 오차가 있다는 것을 인정한다면, 정직한 시계 API는 이렇게 생겨야 한다.

now() → [earliest, latest]    "진짜 현재 시각은 이 구간 안 어딘가에 있다"

동기화 오차의 상한이 ε이면, 서버가 시계에서 pt를 읽었을 때 구간은 [pt−ε, pt+ε]이고 폭은
2ε이다. Google Spanner의 TrueTime이 정확히 이 API이며, GPS 수신기와 원자시계를
데이터센터에 설치해 ε을 수 ms 이내로 눌러놓았다. 오차를 없앨 수는 없지만 오차의 크기를
보장할 수는 있다 — 이것이 이 패턴 전체의 토대다.

세 개의 시간축

이 패턴을 추론할 때는 시간축을 구분해야 길을 잃지 않는다.

• 진짜 시각(true time): 우주의 실제 시각. 아무도 직접 읽을 수 없다. 분석할 때 쓰는
  기준축이며, "실시간 순서(real-time order)"를 판정하는 심판용 축이다.
• 각 서버의 시계: 서버가 실제로 읽는 값. 진짜 시각에서 ±ε 이내로 어긋나 있지만, 서버
  자신은 얼마나·어느 방향으로 어긋났는지 모른다.

시계 동기화가 보장하는 것은 단 하나, |서버 시계 − 진짜 시각| ≤ ε 이다. 구간 시계는 이
보장을 이용해 "내 시계 읽기"로부터 "진짜 시각이 있을 수 있는 범위"를 역산한 것이다.

3. 해법: 불확실성 구간이 지나갈 때까지 기다린다 (commit-wait)

Spanner의 쓰기(커밋) 절차는 다음과 같다.

1. 커밋 시각 결정: ts = now().latest        (구간의 위쪽 끝)
2. 대기: now().earliest > ts 가 될 때까지    (≈ 2ε 만큼)
3. 그 후에야 커밋을 노출하고 클라이언트에 응답

2번의 대기가 끝난 시점에는 진짜 시각이 확실히 ts를 지났다 — earliest조차 ts보다 크므로,
구간 어디에 진실이 있든 ts는 과거다. 그 말은 곧 어느 노드의 시계로도 "지금"은 ts 이후
라는 뜻이다(모든 시계의 오차가 ε 이내라는 보장 덕분에). 따라서 이 응답을 받은 클라이언트가
어떤 경로로든(슬랙이든 전화든) 인과를 이어가 어느 서버에 쓰더라도, 그 쓰기는 반드시 ts보다
큰 타임스탬프를 받는다.

숫자로 돌려보기 (ε = 5ms)

서버 A(시계 5ms 빠름)와 서버 B(시계 4ms 느림)가 있다. A가 대기 없이 즉시 응답하는 경우:

진짜 시각   A의 시계(+5)   B의 시계(−4)   사건
─────────────────────────────────────────────────────────────
10:00.100   10:00.105     10:00.096     A: 시계에서 105를 읽음
                                        → 구간 [100, 110] 계산
                                        → ts = 110 부여, 대기 없이 즉시 응답
10:00.101   10:00.106     10:00.097     클라이언트1 → 클라이언트2 슬랙
10:00.103   10:00.108     10:00.099     B: 쓰기 요청 받음, 시계에서 099를 읽음
                                        → 구간 [094, 104] 계산
                                        → ts = 104 부여

X의 타임스탬프는 110, Y의 타임스탬프는 104. 진짜 시각 기준으로 X(100)가 Y(103)보다 명백히
먼저인데 타임스탬프는 역전됐다. 원인은 하나다. A는 자기 시계가 빠른 줄 모르고 구간의 위쪽
끝(110)을 찍었는데 그것은 진짜 시각보다 10ms 미래의 숫자였고, 그 미래가 오기 전에
응답해 버렸다.

commit-wait를 지키면: A의 대기 종료 조건은 "내 시계가 115를 넘을 때"(pt−5 > 110)이고, 그
순간 진짜 시각은 110이다. 즉 A는 자기 타임스탬프가 진짜로 과거가 된 뒤에야 응답한다. 이후 B가
쓰기를 받는 시점엔 진짜 시각이 110을 넘었으므로, B의 시계가 최대로 느려도(−5ms) 105 이상을
읽고 latest는 110 이상이 된다. 역전의 여지가 닫힌다.

몇 가지 관찰:

• 대기 시간은 정확히 2ε이다. "latest로 찍고, 그 latest가 earliest 밑으로 내려올 때까지"
  — 구간 폭만큼 기다린다.
• 위험 구간은 ts부터가 아니라 조기 응답의 순간부터 열린다. 위험의 본질은 "ts가 미래인
  채로 세상에 공개된 상태"이고, 그 상태는 응답 즉시 시작된다.
• 역전은 비대칭 문제다. 위 예에서 B의 시계가 느린 게 아니라 4ms 빨랐다면, 진짜 103에
  시계는 107을 읽고 latest = 112 > 110이라 역전이 나지 않는다. 역전은 "인과적으로 뒤에 쓰는
  쪽의 시계가 느릴 때"만 발생한다. 그러나 누구의 시계가 어느 방향으로 어긋났는지 아무도
  모르므로, 최악의 경우를 가정하고 기다리는 것이다.
• A는 진짜 시각을 한 번도 보지 못한 채, 자기 시계와 ε 보장만으로 "진짜 시각에 대한
  성질"을 확보했다. 이 패턴의 우아한 부분이다.

비용도 명확하다. 모든 쓰기가 2ε만큼 느려진다. Google이 원자시계에 투자한 이유다 — ε이
250ms면 모든 커밋이 0.5초씩 걸려 상용화가 불가능하지만, 7ms면 감당할 만하다. 하드웨어
투자가 소프트웨어 지연시간으로 직접 환산되는, 보기 드물게 정직한 트레이드오프다.

4. 변주: 쓰기 대신 읽기가 기다린다 — CockroachDB

원자시계가 없는 CockroachDB는 같은 문제를 반대쪽에서 푼다. 쓰기는 기다리지 않고 커밋한다.
대신 읽기가 불확실성을 떠안는다. 타임스탬프 ts로 읽는 트랜잭션은 (ts, ts + max_offset]
구간을 불확실 구간으로 취급하고, 이 구간에 있는 값을 만나면 — 시계 오차 때문에 실제로는 내
읽기보다 과거일 수 있는 값이므로 — 읽기를 더 높은 타임스탬프로 재시작한다(uncertainty
restart).

Spanner:     쓰기마다 2ε 대기 (항상, 예측 가능)  — 작은 ε을 하드웨어로 확보
CockroachDB: 걸린 읽기만 재시작 (가끔, 불규칙)   — 하드웨어 없이, max_offset은 크게

최근에는 AWS가 Time Sync Service로 마이크로초급 시계 동기화를 EC2에 제공하고
ClockBound라는 구간 시계 라이브러리를 공개하면서, "원자시계급 ε"이 클라우드 범용 인프라가
되어가고 있다. 10년 전엔 Google만 할 수 있던 설계가 보편화되는 중이다.

5. 정리 — 시간 3부작의 완성

이 패턴이 하는 일은 한 문장이다. "시계 오차가 유계(ε)라면, 그 오차만큼 기다리는 것으로
시계 오차를 없앤 것과 같은 효과를 산다." 불확실성을 제거할 수 없으니 시간으로 지불한다.
어디서 지불할지 — 쓰기에서 항상(commit-wait) vs 읽기에서 가끔(read restart) — 이 구현
선택의 갈림길이다.

시간 도구들의 지도를 완성하면:

도구	잡는 것	못 잡는 것
램포트 시계 / HLC	시스템 안 인과 (메시지를 탄 인과)	동시성 감지, 시스템 밖 인과
버전 벡터	동시성 감지	실시각, 시스템 밖 인과
시계 제한 대기	시스템 밖으로 흐른 인과 (외부 일관성)	— (비용: 쓰기 지연 or 읽기 재시작)

한 줄 요약: 미래의 타임스탬프를 달았으면, 그 미래가 올 때까지 입을 다물어라.

참고 자료

• 『30가지 패턴으로 배우는 분산 시스템 설계와 구현 기법』 — 시계 제한 대기