17. 분산 락 lease 만료와 fencing token 부재 (C#)

난이도 상

내 리뷰 · C#

내 리뷰 · C++

해설 · C#

해설 — 분산 락 lease 만료와 fencing token 부재 (C#)

난이도: 상

요약

분산 락으로 상호배제를 하지만 lease 가 만료됐는데도 그 사실을 모른 채 쓰기를 수행하고, 저장소가 오래된 소유자의 쓰기를 거부할 fencing token 이 없다. 워커 A 가 락을 잡고 (C)의 무거운 시뮬레이션 중 GC 정지·네트워크 지연으로 5초 lease 를 넘기면, 락은 자동 만료되고 워커 B 가 획득해 (D)를 수행한다. 그 뒤 깨어난 A 도 자기가 여전히 소유자라 믿고 (D)를 수행 → 두 노드가 같은 인스턴스 상태를 동시에 덮어써 보스 HP 롤백·페이즈 꼬임 등이 발생한다(split-brain write).

문제점

1) [lease 만료 무인지] 정지 후 만료된 락으로 쓰기 (증상: 이중 writer)

증상: (A)에서 5초 TTL 로 락을 얻지만, (B)~(D) 사이 경과 시간이 TTL 을 넘을 수 있다(GC stop-the-world, 스와핑, 네트워크 지연). lease 가 만료된 뒤 (D)의 Write가 실행되어도 코드는 만료를 검사하지 않는다. 그 사이 다른 노드가 락을 얻어 이미 쓰기를 했다면, A 의 (D)는 B 의 갱신을 덮어쓴다.
재현조건: 시뮬레이션/IO 지연 > lease TTL.
근본원인: "락 획득 시점"의 소유권을 "쓰기 시점"까지 유효하다고 가정. 락 만료와 실제 임계구역 실행 사이에 시간 간극이 있다.

2) [fencing token 부재] 저장소가 stale writer 를 거부 못 함 (증상: 늦은 쓰기 성공)

증상: (D)의 Write에 소유권을 증명할 토큰이 없다. 저장소는 누가 쓰든 그냥 받는다. Kleppmann 이 지적한 대로, 분산 락만으로는 이 문제를 못 막고 저장소가 단조 증가 토큰(fencing token)으로 늦은 쓰기를 거부해야 한다.
근본원인: 락 서비스와 저장소가 분리돼 있고, 저장소가 소유권 순서를 강제하지 않음.

3) [해제 경합] (E)에서 남의 락 해제 가능 (부수)

증상: A 의 lease 가 만료돼 B 가 락을 얻은 상태에서, A 가 (E) Release(lockKey)를 호출하면 B 의 락을 해제해버릴 수 있다(락에 소유자 식별/토큰 확인 없음). 이는 상호배제를 더 무너뜨린다.

수정안

락 획득 시 단조 증가 fencing token 을 받고, 저장소가 그 토큰으로 늦은 쓰기를 거부한다.

public interface IDistributedLock
{
    // 성공 시 단조 증가하는 fencing token 반환(획득 순서 보장), 실패 시 null
    Task<long?> TryAcquire(string key, int ttlMs);
    Task Release(string key, long token);          // 자기 토큰일 때만 해제
}

public interface IStateStore
{
    // token 이 이 키에 대해 지금까지 본 최대값 이상일 때만 쓰기 허용
    Task<bool> WriteFenced(string key, byte[] state, long token);
}

public async Task ProcessTick(string instanceId)
{
    string lockKey = $"lock:dungeon:{instanceId}";
    long? token = await _lock.TryAcquire(lockKey, ttlMs: 5000);
    if (token is null) return;

    try
    {
        byte[] state = await _store.Read(instanceId);
        byte[] next = Simulate(state);
        bool ok = await _store.WriteFenced(instanceId, next, token.Value); // (D')
        if (!ok)
        {
            // 더 큰 토큰(더 최근 소유자)이 이미 썼다 → 나는 stale, 쓰기 폐기
            return;
        }
    }
    finally
    {
        await _lock.Release(lockKey, token.Value);   // 내 토큰일 때만
    }
}

저장소는 키별로 "지금까지 승인한 최대 토큰"을 기록하고, 그보다 작은 토큰의 쓰기를 거부한다(WriteFenced). A 가 늦게 도착해도 B 가 더 큰 토큰으로 이미 썼으면 A 의 쓰기는 거부된다.
Release는 토큰 일치 시에만(원자적 compare-and-del) 해제해 남의 락 해제를 막는다.

더 나은 설계 (트레이드오프)

락 대신 저장소 자체의 조건부 쓰기: 상태에 버전을 두고 낙관적 동시성(compare-and-set)으로 쓰면 락 없이도 늦은 쓰기를 거부. 분산 락의 lease 문제를 우회. 트레이드오프: 충돌 재시도.
단일 소유권 파티셔닝: 인스턴스ID → 노드 매핑을 일관 해싱/리더십으로 고정해 애초에 한 노드만 처리(락 불필요). 트레이드오프: 리밸런싱·failover 복잡도(이 저장소 distributed failover 문제와 연결).
lease 하트비트 + 작업 취소: 임계구역이 길면 주기적으로 lease 갱신하고, 갱신 실패 시 진행 중 작업을 즉시 취소해 만료 후 쓰기를 원천 차단. 트레이드오프: 취소 지점 설계 필요.

면접 포인트

"분산 락만으로 상호배제가 안 되는 이유"(프로세스 정지/GC/네트워크 지연으로 lease 만료 후에도 실행)를 설명할 수 있는가.
fencing token(단조 증가)과 저장소의 토큰 거부가 왜 필요한지(Kleppmann 논지).
조건부 쓰기(CAS)/파티셔닝/lease 하트비트 등 대안과 트레이드오프.

해설 · C++

해설 — 분산 락 lease 만료·로컬 시계 검증의 함정과 fencing token 부재 (C++)

난이도: 상

요약

분산 락으로 상호배제를 하지만, (1) 쓰기 직전 "만료 여부"를 로컬 벽시계(system_clock)로 자체 판단한다 — 이는 락 서버의 실제 만료와 무관하고 NTP 보정·시계 드리프트로 어긋난다, (2) 그 로컬 검사(E)와 실제 쓰기(F) 사이에도 시간 간극이 있어 TOCTOU, (3) 무엇보다 저장소에 fencing token 이 없어 lease 가 실제로 만료돼 다른 노드가 소유권을 얻은 뒤에도 이 노드의 늦은 쓰기를 거부하지 못한다. 결과는 이중 writer split-brain.

문제점

1) [로컬 시계로 lease 판정] system_clock 신뢰 (증상: 잘못된 유효 판정)

증상: (B)에서 로컬 system_clock::now()+5s로 만료 시각을 만들고 (E)에서 로컬 시계로 검사한다. 하지만 (i) 락 서버의 TTL 카운트다운은 네트워크 왕복·서버 부하로 이 로컬 5초와 다르게 흐르고, (ii) system_clock은 벽시계라 NTP 보정으로 뒤로 점프하면 이미 만료됐는데도 (E)가 "아직 유효"로 오판한다. 경과 시간 측정에는 단조 시계(steady_clock)를 써야 하지만 그마저도 락 서버의 만료와 동기화되지 않는다.
근본원인: 소유권 만료는 락 서버가 권위인데 클라이언트가 로컬에서 추정.

2) [TOCTOU] 검사(E)와 쓰기(F) 사이 간극 (증상: 검사 후 만료)

증상: (E)에서 유효로 판정한 직후, (F) Write가 실행되기 전 스케줄링/GC 유사 정지·IO 지연으로 실제 lease 가 만료되고 다른 노드가 획득·쓰기를 할 수 있다. 검사와 행위가 원자적이지 않다.

3) [fencing token 부재] 저장소가 stale writer 거부 못 함 (증상: 이중 writer)

증상: (F) Write에 소유권 증명 토큰이 없다. lease 가 실제 만료돼 노드 B 가 락을 얻어 이미 썼더라도, 늦게 도착한 A 의 Write가 그대로 성공해 B 의 갱신을 덮어쓴다.
근본원인: 락 서비스와 저장소가 분리, 저장소가 소유 순서를 강제하지 않음.

4) [해제 경합] (G)에서 남의 락 해제 (부수)

A 의 lease 만료 후 B 가 소유 중일 때 A 가 Release하면 B 의 락을 풀 수 있다(소유자 토큰 확인 없음).

수정안

락 획득 시 단조 증가 fencing token 을 받고, 저장소가 그 토큰으로 늦은 쓰기를 거부. 로컬 시계 자체 판정 제거.

struct IDistributedLock {
    // 성공 시 단조 증가 fencing token(>0), 실패 시 0
    virtual uint64_t TryAcquire(const std::string& key, int ttlMs) = 0;
    virtual void Release(const std::string& key, uint64_t token) = 0; // 내 토큰만
    virtual ~IDistributedLock() = default;
};
struct IStateStore {
    // 키별 최대 승인 토큰 이상일 때만 쓰기 성공
    virtual bool WriteFenced(const std::string& key,
                             const std::vector<uint8_t>& s, uint64_t token) = 0;
    virtual std::vector<uint8_t> Read(const std::string& key) = 0;
    virtual ~IStateStore() = default;
};

void DungeonWorker::ProcessTick(const std::string& instanceId) {
    std::string lockKey = "lock:dungeon:" + instanceId;
    uint64_t token = lock_.TryAcquire(lockKey, 5000);
    if (token == 0) return;

    std::vector<uint8_t> next = Simulate(store_.Read(instanceId));
    // 로컬 시계로 만료를 추정하지 않는다. 저장소가 토큰으로 판정.
    bool ok = store_.WriteFenced(instanceId, next, token);   // 늦으면 거부됨
    // ok == false 면 더 최근 소유자가 이미 썼다 → 내 쓰기 폐기
    lock_.Release(lockKey, token);                            // 내 토큰일 때만
}

저장소가 "지금까지 본 최대 토큰"보다 작은 토큰의 쓰기를 거부(WriteFenced) → 늦은 A 는 자동 거부.
경과 시간이 필요하면 steady_clock을 쓰되, 소유권 판정은 저장소 토큰에 위임.

더 나은 설계 (트레이드오프)

상태 버전 CAS: 상태에 버전을 두고 compare-and-set 으로 쓰면 락 lease 문제를 우회. 트레이드오프: 충돌 재시도.
소유권 파티셔닝: instanceId → 노드 매핑을 리더십/일관 해싱으로 고정해 한 노드만 처리(락 불필요). 트레이드오프: failover·리밸런싱.
lease 하트비트 + 협조적 취소: 긴 임계구역은 주기적 갱신, 갱신 실패 시 즉시 중단. 트레이드오프: 취소 지점 설계.

면접 포인트

왜 로컬 시계(특히 벽시계 system_clock)로 분산 lease 만료를 판정하면 안 되는지(권위·NTP 점프·TOCTOU).
분산 락만으로 상호배제가 안 되는 이유와 fencing token 의 역할.
steady_clock vs system_clock, 그리고 CAS/파티셔닝/하트비트 대안.

← 문제로 돌아가기