← 문제로

34. 공유 사전 압축 프로토콜의 DictAdd 유실·순서 역전 (C#)

난이도 상
내 리뷰 · C#
해설 · C#

해설 — 공유 사전 압축 프로토콜의 DictAdd 유실·순서 역전 (C#)

난이도: 상

요약

클라이언트는 (A)에서 DictAdd 통지를 받는 즉시 무조건 _entries[index] = value 로 덮어써 반영하고, (B)의 Resolve 는 "인덱스가 존재하는지"만 확인할 뿐 "그 인덱스가 지금 이 DictRef 가 기대하는 항목과 같은 버전인지"는 전혀 검증하지 않는다. DictAdd가 신뢰할 수 없는 경로로 전달되어 유실되거나 다른 큐의 DictRef보다 늦게 도착할 수 있는 상황에서, 클라이언트 사전은 서버 사전과 조용히 어긋나고(desync) 같은 인덱스가 실제로는 다른 문자열을 가리키는데도 감지되지 않은 채 엉뚱한 문자열로 해석된다.

문제점

(A) DictAdd 유실 시 감지·복구 메커니즘 부재

  • 증상: 서버가 인덱스 7에 "긴급 공지: 서버 점검"을 등록했지만 그 DictAdd 패킷이 유실되면, 클라의 _entries에는 인덱스 7이 아예 없다. 이후 다른 문자열이 인덱스 7을 재사용(사전이 순환/재사용 정책을 가질 경우)하거나, 그냥 [UNKNOWN]으로 표시되어 사용자에게 아무 정보도 전달되지 않는다. 더 심각한 경우는 유실된 인덱스가 나중에 "다른" DictAdd로 같은 번호를 다시 쓰게 되면(사전 슬롯 재활용), 클라가 그 뒤늦은 통지를 마치 최초 등록인 것처럼 받아들여 이후 조용히 잘못된 매핑으로 굳어진다.
  • 재현 조건:
    1. 서버가 인덱스 7 = "A"를 DictAdd로 전송하지만 네트워크 구간에서 유실.
    2. 서버는 성공적으로 전송됐다고 가정하고 DictRef(7)을 여러 번 전송.
    3. 클라는 인덱스 7이 없으므로 매번 [UNKNOWN]을 반환 — 사용자에게 의미 있는 메시지가 전혀 전달되지 않는다.
    4. 이후 서버가 사전 슬롯을 재사용하는 정책이라면(예: LRU 축출 후 인덱스 7을 "B"로 재할당), 클라는 뒤늦게 도착한 이 DictAdd를 정상 갱신으로 착각해 받아들이고, 과거에 캐시했을 수도 있는 문맥과 뒤섞여 완전히 다른 문자열을 노출한다.
  • 근본 원인: (A)가 "받은 것을 그대로 신뢰해 반영"하는 fire-and-forget 구조라 유실을 감지할 방법이 없다. 사전 갱신에 신뢰성 있는 전달(ack/재전송)이나 버전 확인 절차가 없다.

(B) Resolve 가 값의 "버전"을 확인하지 않음

  • 증상: DictRef 메시지에 서버가 그 문자열을 등록한 시점의 버전(또는 그 문자열 자체의 체크섬)이 함께 실리지 않으므로, 클라는 자신이 들고 있는 인덱스 7의 값이 서버가 지금 이 DictRef를 만들 때 참조한 그 값과 같은지 검증할 방법이 없다. 사전이 한 번이라도 어긋나면 이후 영구히 조용히 잘못된 문자열을 노출한다.
  • 재현 조건: 위 시나리오에서 클라가 우연히 다른 경로로 인덱스 7에 "C"라는 값을 먼저 채워놓은 상태(예: 순서 역전으로 더 나중에 등록된 DictAdd가 먼저 도착)라면, Resolve(7)은 아무 오류 없이 "C"를 반환하지만 서버가 실제로 의도한 것은 "A"다.
  • 근본 원인: 인덱스만으로 값의 동일성을 보장하려면 등록·참조 양쪽에 같은 버전 식별자가 있어야 하는데 프로토콜에 그 필드가 없다.

수정안 (정확한 코드)

DictRef에 그 문자열의 짧은 검증 토큰(버전/체크섬)을 함께 실어, 클라가 자신의 사전 항목과 일치하는지 검증하고 불일치 시 안전하게 재동기화를 요청하도록 한다.

using System.Collections.Generic;

public sealed class DictEntry
{
    public string Value;
    public uint Version;   // 서버가 이 문자열을 등록할 때 부여한 버전(단조 증가 또는 해시)
}

public sealed class ClientDictionary
{
    private readonly Dictionary<int, DictEntry> _entries = new Dictionary<int, DictEntry>();

    // 재동기화가 필요할 때 서버에 알리기 위한 콜백(전송 계층에 위임)
    public System.Action<int> RequestResync;

    public void OnDictAdd(int index, string value, uint version)
    {
        // 더 오래된(순서가 뒤바뀐) 통지는 무시 — 최신 버전만 반영
        if (_entries.TryGetValue(index, out var existing) && existing.Version >= version)
            return;

        _entries[index] = new DictEntry { Value = value, Version = version };
    }

    // DictRef 에도 서버가 참조 시점에 알고 있던 버전을 함께 보낸다.
    public string Resolve(int index, uint expectedVersion)
    {
        if (_entries.TryGetValue(index, out var entry) && entry.Version == expectedVersion)
            return entry.Value;

        // 인덱스가 없거나 버전이 다르면(=desync) 절대 엉뚱한 값을 노출하지 않고
        // 재동기화를 요청한다.
        RequestResync?.Invoke(index);
        return "[SYNCING]";
    }
}

public sealed class ServerDictionary
{
    private readonly Dictionary<string, (int index, uint version)> _stringToEntry
        = new Dictionary<string, (int, uint)>();
    private readonly List<string> _indexToString = new List<string>();
    private uint _nextVersion = 1;

    public (int index, uint version, bool isNew) Intern(string value)
    {
        if (_stringToEntry.TryGetValue(value, out var existing))
            return (existing.index, existing.version, false);

        int newIndex = _indexToString.Count;
        uint version = _nextVersion++;
        _indexToString.Add(value);
        _stringToEntry[value] = (newIndex, version);
        return (newIndex, version, true);
    }

    // 클라의 재동기화 요청에 응답: 해당 인덱스의 현재 값을 다시 신뢰성 채널로 재전송한다.
    public bool TryGetForResync(int index, out string value, out uint version)
    {
        if (index >= 0 && index < _indexToString.Count)
        {
            value = _indexToString[index];
            version = _stringToEntry[value].version;
            return true;
        }
        value = null;
        version = 0;
        return false;
    }
}

핵심 변경:

  • DictAdd/DictRef 양쪽에 version을 실어, 클라가 "이 인덱스가 지금 내가 아는 것과 같은 등록인지"를 검증할 수 있게 했다.
  • 버전 불일치나 미등록 인덱스를 만나면 절대 추측하지 않고 RequestResync로 서버에 재전송을 요청한다 — "모르면 안전하게 실패"하는 원칙.
  • OnDictAdd는 더 낮은 버전의 뒤늦은 통지(순서 역전)를 무시해 과거 상태로 되돌아가지 않게 한다.

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

  • DictAdd를 신뢰성 채널(ack+재전송)로만 전송: 애초에 유실이 없도록 사전 갱신 메시지는 반드시 순서 보장·신뢰성 채널로 보내고, DictRef만 비신뢰 채널을 써도 되게 분리한다. 다만 채널을 분리하면 여전히 두 채널 간 도착 순서는 보장되지 않으므로 버전 검증은 그대로 필요하다.
  • 사전 슬롯 재사용 금지(또는 세대 구분): 인덱스를 재활용하지 않거나, 재활용 시 세대(generation) 번호를 인덱스에 포함시켜 오래된 세대의 참조가 새 세대 값으로 절대 오인되지 않게 한다.
  • 주기적 풀 스냅샷 동기화: 델타(DictAdd)만으로 영구히 정합성을 유지하기보다, 주기적으로 "현재 사전 전체"를 체크섬과 함께 보내 클라가 스스로 어긋남을 감지·복구하게 한다.
  • 트레이드오프: 버전/체크섬을 매 참조에 실으면 패킷 크기가 약간 늘고(원래 목적인 대역폭 절약을 일부 상쇄), 재동기화 왕복 지연 동안 해당 문자열은 [SYNCING]으로 잠깐 노출된다. 하지만 엉뚱한 문자열이 영구히 노출되는 것보다는 훨씬 안전하다.

면접 포인트

  1. "인덱스로 참조하는 압축 사전"은 송수신 양측의 상태가 암묵적으로 동기화되어 있다는 가정에 의존한다 — 신뢰할 수 없는 전송 위에서는 그 가정이 깨질 수 있으므로 반드시 검증 수단(버전/체크섬)이 필요하다.
  2. 유실은 "감지하지 못하면 존재하지 않는 것"이 아니라 "조용히 잘못된 상태로 이어지는 것"이다 — fire-and-forget 갱신은 항상 desync 위험을 내포한다.
  3. 신뢰할 수 없는 채널 위의 상태 동기화 문제는 로컬 스레드 동시성 문제와 본질이 같다(공유 상태 + 비원자적 갱신) — 여기선 스레드 대신 네트워크 지연/유실이 인터리빙을 만든다.
← 문제로 돌아가기