13. 리전 간 벽시계 타임스탬프로 이벤트 순서를 재구성하는 결함

난이도 상

내 리뷰 · C#

내 리뷰 · C++

해설 · C#

해설 — 리전 간 벽시계 타임스탬프로 이벤트 순서를 재구성하는 결함

난이도: 상

요약

GlobalEventAggregator(B)는 각 리전 서버가 보낸 이벤트의 WallClockTimestamp 만을 기준으로 정렬해 "일어난 순서"를 재구성한다. 그러나 벽시계는 리전마다 독립적인 물리 클록이며, NTP 로 동기화되어 있어도 수십~수백 밀리초의 드리프트가 항상 존재한다. 만약 리전 A 에서 발생한 이벤트가 실제로는 리전 B 에서 발생한 이벤트보다 먼저 일어났고 그로 인해(인과관계로) B 의 이벤트가 유발되었더라도, A 서버의 시계가 B 서버의 시계보다 조금이라도 뒤처져 있다면 A 의 타임스탬프가 B 의 타임스탬프보다 더 늦은 값으로 찍힐 수 있다. 그 결과 (A)에서 수신 순서와 무관하게 버퍼링된 이벤트들이 (B)의 정렬 단계에서 실제 인과관계와 반대로 재배열되어 처리되는 근본적인 결함이 발생한다.

문제점

분류: 인과적 순서(causal ordering) 위반 / 물리 시계(wall-clock) 기반 전역 순서 재구성의 근본적 한계
증상: 예를 들어 리전 A 의 경매 입찰 이벤트가 실제로는 리전 B 의 "입찰 거부(중복 낙찰 방지)" 이벤트를 유발했는데도, 시계 드리프트로 B 의 타임스탬프가 A 보다 더 이른 값으로 기록되면 집계 서버는 B 이벤트를 먼저 처리한 뒤 A 이벤트를 나중에 처리한다 — 인과관계상 원인이 결과보다 나중에 처리되는 모순이 발생한다.
재현 조건: 리전 A 와 리전 B 의 시스템 시각이 (NTP 동기화에도 불구하고) 예컨대 100ms 어긋나 있는 상태에서, 두 리전 사이에 100ms 이내의 시간차로 인과관계가 있는 이벤트 쌍이 발생하는 경우.
근본 원인:
- (A) 이벤트를 수신 순서대로만 버퍼에 쌓을 뿐, 각 리전이 이벤트 발생 시점에 다른 리전의 최신 이벤트를 "알고 있었는지"(인과적 선행 관계)에 대한 정보를 전혀 기록하지 않는다.
- (B) 정렬 기준이 순수 물리 시계(wall-clock) 뿐이다. 물리 시계는 서로 다른 머신 간 순서를 "인과관계 보장" 수준으로 비교할 수 있는 도구가 아니다 — 이는 분산 시스템에서 널리 알려진 한계이며, 이를 보완하기 위한 논리 시계(Lamport clock)나 벡터 시계(vector clock) 가 이 코드에는 전혀 도입되어 있지 않다.

수정안

각 리전 서버가 이벤트를 생성/전파할 때 Lamport 논리 시계 값을 함께 실어 보내고, 집계 서버는 이 논리 시계를 우선 기준으로, 동률일 때만 리전 ID 등의 보조 기준으로 전역 순서를 정한다. Lamport 시계는 "이벤트 A 가 이벤트 B 를 인과적으로 선행한다"는 관계를 절대 어기지 않는 순서를 보장한다(반대로 인과관계가 없는 이벤트끼리의 순서는 임의로 정해질 수 있다는 한계는 있다).

using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading;

public sealed class RegionEvent
{
    public string RegionId;
    public string EventId;
    public long   LamportClock;       // 발생 리전이 부여한 논리 시계 값
    public DateTime WallClockTimestamp; // 참고/로그용으로만 남기고 정렬 기준으로는 쓰지 않는다.
    public string Description;
}

// 리전 서버 측: 이벤트를 만들 때마다 호출해 논리 시계를 증가시키고,
// 다른 리전으로부터 이벤트를 수신하면 그 이벤트의 시계 값을 반영해
// 자신의 시계를 그보다 앞서도록 갱신한다(Lamport 규칙).
public sealed class LamportClockSource
{
    private long _counter;

    public long NextForLocalEvent()
    {
        return Interlocked.Increment(ref _counter);
    }

    // 다른 리전에서 수신한 이벤트의 시계 값을 반영한다.
    public long OnReceiveRemoteClock(long remoteClock)
    {
        long updated;
        long current;
        do
        {
            current = Interlocked.Read(ref _counter);
            updated = Math.Max(current, remoteClock) + 1;
        } while (Interlocked.CompareExchange(ref _counter, updated, current) != current);
        return updated;
    }
}

public sealed class GlobalEventAggregator
{
    private readonly List<RegionEvent> _buffer = new();

    public void OnEventReceived(RegionEvent evt)
    {
        _buffer.Add(evt);
    }

    public List<RegionEvent> DrainInOrder()
    {
        // Lamport 시계를 1차 기준으로 정렬한다: 인과관계가 있는 이벤트라면
        // 원인 이벤트의 시계 값이 결과 이벤트의 시계 값보다 항상 작으므로
        // 이 정렬은 실제 인과 순서를 절대 위반하지 않는다.
        // 시계 값이 같다면(동시성, 인과관계 없음) 리전 ID 로 결정적 타이브레이크.
        var ordered = _buffer
            .OrderBy(e => e.LamportClock)
            .ThenBy(e => e.RegionId, StringComparer.Ordinal)
            .ToList();
        _buffer.Clear();
        return ordered;
    }
}

리전 서버 측에서는 이벤트를 만들 때 LamportClockSource.NextForLocalEvent() 로 시계 값을 채우고, 다른 리전의 이벤트를 참조/응답하는 이벤트를 만들 때는 먼저 OnReceiveRemoteClock 으로 시계를 갱신한 뒤 그 값으로 새 이벤트의 시계를 채워야 한다 — 이 규칙을 지켜야 인과관계가 시계 값의 대소 관계로 정확히 표현된다.

더 나은 설계

Lamport 논리 시계(채택안): 구현이 간단(정수 카운터 하나)하고, "인과관계가 있으면 순서가 절대 뒤바뀌지 않는다"는 성질을 보장한다. 다만 두 이벤트의 시계 값만 보고는 그 둘이 실제로 인과관계가 있는지(happened-before) 없는지(concurrent) 구분할 수 없다는 한계가 있다 — 순서는 정해지지만 "왜 그 순서인지"는 알 수 없다.
벡터 시계(Vector Clock): 리전 수만큼의 카운터 벡터를 각 이벤트에 실어, 두 이벤트가 인과관계인지(happened-before) 아니면 동시(concurrent, 인과관계 없음)인지까지 정확히 판별할 수 있다. 동시 이벤트끼리는 순서를 강제하지 않아도 되므로(애초에 순서가 중요하지 않은 이벤트 쌍이므로) 더 정교한 처리가 가능하지만, 리전 수에 비례해 각 이벤트에 실어야 할 데이터 크기가 커지고 구현 복잡도가 높다.
하이브리드 논리 시계(HLC, Hybrid Logical Clock): 물리 시계와 논리 카운터를 결합해, 대부분의 경우 물리 시계에 가까운(사람이 읽기 쉬운, 대략적인 실제 시각과 상관관계가 있는) 값을 유지하면서도 Lamport 시계의 인과성 보장을 함께 얻는다. Google Spanner/CockroachDB 류의 분산 DB 에서 실제로 쓰이는 절충안이며, 로깅/디버깅 시 시계 값이 실제 시각과 크게 동떨어지지 않아 운영 편의성이 좋다.
트레이드오프: 인과관계 판별까지 필요하면 벡터 시계, 실무적으로 "순서만 어기지 않으면 충분"하고 구현 단순성이 중요하면 Lamport, 로깅/운영 편의성과 인과성 보장을 함께 원하면 HLC 가 적합하다. 리전 수가 매우 많아지면 벡터 시계의 크기 증가가 부담이 될 수 있어, 대규모 시스템일수록 HLC 나 Lamport + 별도 인과 태그(예: 원인 이벤트 ID 참조) 조합이 더 실용적이다.

면접 포인트

벽시계(physical/wall-clock)는 서로 다른 머신 간의 "동시에 발생했다/먼저 발생했다"를 인과관계 보장 수준으로 비교하는 도구가 아니다 — NTP 로 동기화해도 드리프트가 항상 존재한다는 사실 자체가 분산 시스템 설계의 기본 전제여야 한다.
Lamport 시계가 보장하는 것(a → b 이면 L(a) < L(b))과 보장하지 않는 것(L(a) < L(b) 라고 해서 a → b 인지는 알 수 없음, 즉 동시성 이벤트도 임의의 순서로 정렬될 뿐임)을 정확히 구분해서 설명할 수 있어야 한다.
벡터 시계 vs Lamport 시계 vs HLC 의 트레이드오프(정확성/판별력 vs 데이터 크기/구현 복잡도)를 실제 분산 게임 서버의 리전 수, 이벤트 빈도 같은 구체적 제약과 연결해 설명할 수 있어야 한다.

해설 · C++

해설 — 리전 간 벽시계 타임스탬프로 이벤트 순서를 재구성하는 결함

난이도: 상

요약

GlobalEventAggregator::DrainInOrder(B)는 각 리전 서버가 보낸 이벤트의 wallClockTimestamp 만을 기준으로 정렬해 "일어난 순서"를 재구성한다. 벽시계는 리전마다 독립적인 물리 클록이며 NTP 로 동기화되어 있어도 수십~수백 밀리초의 드리프트가 항상 존재한다. 리전 A 의 이벤트가 실제로는 리전 B 의 이벤트를 인과적으로 선행(그 이벤트가 있었기 때문에 B 가 발생)했더라도, A 서버의 시계가 B 서버보다 조금이라도 뒤처져 있다면 A 의 타임스탬프가 더 늦은 값으로 찍혀 정렬 결과가 실제 인과관계와 반대로 뒤집힌다. OnEventReceived(A)는 수신 순서 정보(적어도 집계 서버가 각 이벤트를 언제 받았는지)조차 보조 정렬 기준으로 남겨두지 않아, 결함을 완화할 여지도 없다.

문제점

분류: 인과적 순서(causal ordering) 위반 / 물리 시계 기반 전역 순서 재구성의 근본적 한계
증상: 리전 A 의 경매 입찰 이벤트가 실제로는 리전 B 의 "중복 낙찰 방지 거부" 이벤트를 유발했는데도, 시계 드리프트로 B 의 타임스탬프가 A 보다 이른 값으로 기록되면 집계 서버는 B 를 먼저 처리한 뒤 A 를 나중에 처리해 원인이 결과보다 나중에 처리되는 모순이 생긴다.
재현 조건: 리전 A 와 B 의 시스템 시각이 (NTP 동기화에도 불구하고) 예컨대 100ms 어긋난 상태에서, 두 리전 사이에 100ms 이내 시간차로 인과관계가 있는 이벤트 쌍이 발생하는 경우.
근본 원인:
- (A) 수신 시점에 각 리전이 이벤트 발생 시점에 다른 리전의 최신 이벤트를 "알고 있었는지"(인과적 선행 관계)를 전혀 기록하지 않는다.
- (B) 정렬 기준이 순수 물리 시계뿐이다. 서로 다른 머신의 물리 시계는 인과관계 보장 수준으로 순서를 비교할 수 있는 도구가 아니며, 이를 보완할 논리 시계(Lamport clock)가 전혀 도입되어 있지 않다.

수정안

각 리전 서버가 이벤트를 생성/전파할 때 Lamport 논리 시계 값을 함께 실어 보내고, 집계 서버는 이 논리 시계를 우선 기준으로, 동률일 때만 리전 ID 등의 보조 기준으로 전역 순서를 정한다.

#include <algorithm>
#include <atomic>
#include <chrono>
#include <cstdint>
#include <string>
#include <vector>

struct RegionEvent
{
    std::string regionId;
    std::string eventId;
    uint64_t    lamportClock;                              // 발생 리전이 부여한 논리 시계 값
    std::chrono::system_clock::time_point wallClockTimestamp; // 참고/로그용, 정렬 기준 아님
    std::string description;
};

// 리전 서버 측: 이벤트를 만들 때마다 호출해 논리 시계를 증가시키고,
// 다른 리전으로부터 이벤트를 수신하면 그 이벤트의 시계 값을 반영해
// 자신의 시계를 그보다 앞서도록 갱신한다(Lamport 규칙).
class LamportClockSource
{
public:
    uint64_t NextForLocalEvent()
    {
        return counter_.fetch_add(1, std::memory_order_relaxed) + 1;
    }

    // 다른 리전에서 수신한 이벤트의 시계 값을 반영한다.
    uint64_t OnReceiveRemoteClock(uint64_t remoteClock)
    {
        uint64_t current = counter_.load(std::memory_order_relaxed);
        uint64_t updated;
        do
        {
            updated = std::max(current, remoteClock) + 1;
        } while (!counter_.compare_exchange_weak(current, updated, std::memory_order_relaxed));
        return updated;
    }

private:
    std::atomic<uint64_t> counter_{0};
};

class GlobalEventAggregator
{
public:
    void OnEventReceived(const RegionEvent& evt)
    {
        buffer_.push_back(evt);
    }

    std::vector<RegionEvent> DrainInOrder()
    {
        // Lamport 시계를 1차 기준으로 정렬한다: 인과관계가 있는 이벤트라면
        // 원인 이벤트의 시계 값이 결과 이벤트의 시계 값보다 항상 작으므로
        // 이 정렬은 실제 인과 순서를 절대 위반하지 않는다.
        // 시계 값이 같다면(동시성, 인과관계 없음) 리전 ID 로 결정적 타이브레이크.
        std::vector<RegionEvent> ordered = buffer_;
        std::sort(ordered.begin(), ordered.end(),
            [](const RegionEvent& a, const RegionEvent& b) {
                if (a.lamportClock != b.lamportClock)
                    return a.lamportClock < b.lamportClock;
                return a.regionId < b.regionId;
            });
        buffer_.clear();
        return ordered;
    }

private:
    std::vector<RegionEvent> buffer_;
};

리전 서버 측에서는 이벤트를 만들 때 LamportClockSource::NextForLocalEvent() 로 시계 값을 채우고, 다른 리전의 이벤트를 참조/응답하는 이벤트를 만들 때는 먼저 OnReceiveRemoteClock 으로 시계를 갱신한 뒤 그 값으로 새 이벤트의 시계를 채워야 한다 — 이 규칙을 지켜야 인과관계가 시계 값의 대소 관계로 정확히 표현된다. LamportClockSource 는 여러 스레드(수신 콜백, 로컬 이벤트 생성 스레드)에서 동시에 호출될 수 있으므로 std::atomic 의 CAS 루프로 갱신을 원자화했다.

더 나은 설계

Lamport 논리 시계(채택안): 구현이 간단(원자적 정수 카운터 하나)하고, "인과관계가 있으면 순서가 절대 뒤바뀌지 않는다"는 성질을 보장한다. 다만 두 이벤트의 시계 값만으로는 그 둘이 실제로 인과관계인지(happened-before) 아니면 우연히 비슷한 시점에 독립적으로 발생한 것인지(concurrent) 구분할 수 없다.
벡터 시계(Vector Clock): 리전 수만큼의 카운터 벡터를 각 이벤트에 실어, 두 이벤트가 인과관계인지 동시(concurrent)인지까지 정확히 판별할 수 있다. 동시 이벤트끼리는 순서를 강제하지 않아도 되므로 더 정교하지만, 리전 수에 비례해 이벤트당 데이터 크기가 커지고(std::vector<uint64_t> 를 매 이벤트에 실어야 함) 직렬화/네트워크 비용이 증가한다.
하이브리드 논리 시계(HLC): 물리 시계와 논리 카운터를 결합해, 대부분의 경우 물리 시계에 가까운 값을 유지하면서도 Lamport 시계의 인과성 보장을 함께 얻는다. 분산 DB(Spanner, CockroachDB 류)에서 실제로 쓰이는 절충안이며, 로깅 시 시계 값이 실제 시각과 크게 동떨어지지 않아 운영/디버깅 편의성이 좋다.
트레이드오프: 인과관계 판별까지 필요하면 벡터 시계, 구현 단순성이 중요하면 Lamport, 운영 편의성과 인과성 보장을 함께 원하면 HLC 가 적합하다. C++ 서버 간 이벤트 전파는 대개 네트워크 대역폭에 민감하므로, 리전 수가 많아질수록 벡터 시계의 페이로드 증가 부담이 Lamport/HLC 대비 상대적으로 더 크게 작용한다.

면접 포인트

벽시계는 서로 다른 머신 간 "동시에 발생했다/먼저 발생했다"를 인과관계 보장 수준으로 비교하는 도구가 아니다 — NTP 로 동기화해도 드리프트가 항상 존재한다는 사실이 분산 시스템 설계의 기본 전제여야 한다.
Lamport 시계가 보장하는 것(a → b 이면 L(a) < L(b))과 보장하지 않는 것(L(a) < L(b) 이라고 해서 a → b 인지는 알 수 없음)을 정확히 구분해서 설명할 수 있어야 한다.
std::atomic 의 CAS 루프로 논리 시계 갱신을 구현할 때 memory_order 선택(여기서는 카운터 값 자체의 단조성만 필요하므로 relaxed 로 충분한 이유)을 설명할 수 있으면 좋다 — 다른 스레드 간 실제 발생-이전(happens-before) 관계를 강제해야 하는 데이터가 이 카운터에 얹혀 있다면 더 강한 메모리 순서가 필요해질 수 있다는 점까지 논할 수 있으면 심화 포인트가 된다.

← 문제로 돌아가기