해설 — tombstone·anti-entropy 부재로 인한 삭제 데이터 부활 + LWW 역전 · C#

난이도: 상

요약

Delete 는 항목을 삭제 흔적(tombstone) 없이 그냥 제거한다(A). 그래서 "삭제됨"과 "애초에 없음"이 저장소에서 구별되지 않는다. Reconcile 은 "내게 없으면 peer 값을 채택"하므로(B), 그 삭제를 못 받은 peer 와 병합하면 삭제된 값이 그대로 되살아난다. 게다가 삭제는 버전을 남기지 않아, 늦게 도착한 오래된 쓰기도 삭제를 덮을 수 있다.

문제점

삭제를 tombstone 으로 기록하지 않음 / anti-entropy가 부재를 "미보유"로만 해석 — 삭제 부활

• 증상: 지웠던 아이템·우편·차단 목록이 재동기화 후 되살아난다. 복제 지연이 클수록, 리전이 많을수록 자주 난다.
• 재현 조건(부활):
  1. R1, R2 가 key item42(version 100) 를 보유.
  2. R1 이 Delete("item42") → R1 _data 에서 제거. 전파가 R2 로 가는 도중 유실(분단).
  3. 나중에 R1 이 R2 스냅샷으로 Reconcile. R2 는 여전히 item42(version 100) 보유. R1 은 !_data.TryGetValue → 없음 → peer 값 채택 → item42 부활.
  4. 이제 R1 이 다시 R2 로 전파하면 삭제가 영구히 무효화된다.
• 재현 조건(LWW 역전 — 삭제에 버전이 없어 생기는 문제):
  1. R2 가 T=150 에 item42(version 150) 를 씀.
  2. R1 이 T=200 에 Delete("item42") → tombstone 없이 제거.
  3. R1 이 R2 스냅샷으로 Reconcile. R2 의 item42(version 150) 가 R1 엔 없으니 채택 → 부활. 삭제(200)가 쓰기(150)보다 최신인데도, 삭제에 버전이 없어 병합이 "삭제가 더 최신"임을 판정할 수 없다. tombstone(version 200) 이 있었다면 150 을 눌러 억제했을 것이다.
• 근본 원인: 삭제를 "상태의 부재"로 표현했다. 분산 병합에서 부재는 "삭제됨"과 "아직 못 받음"을 구별하지 못한다. 삭제도 버전이 달린 명시적 상태(tombstone) 여야 병합에서 값과 경쟁해 이길 수 있다.

수정안

삭제를 버전 있는 tombstone 으로 기록하고, 병합·읽기·GC 모두 tombstone 을 값과 동등하게 다룬다.

public struct Entry
{
    public string Value;
    public long Version;
    public bool Deleted;    // tombstone 여부
}

public void Delete(string key)
{
    long v = NowMs();
    if (!_data.TryGetValue(key, out var cur) || v >= cur.Version)
        _data[key] = new Entry { Deleted = true, Version = v };   // tombstone
    Replicate();
}

public void Put(string key, string value)
{
    long v = NowMs();
    if (!_data.TryGetValue(key, out var cur) || v > cur.Version)  // 동률은 결정론적 타이브레이커로
        _data[key] = new Entry { Value = value, Version = v, Deleted = false };
    Replicate();
}

public void Reconcile(IReadOnlyDictionary<string, Entry> peer)
{
    foreach (var kv in peer)
    {
        // tombstone 도 값과 똑같이 버전으로 경쟁 — 더 높은 버전이 이긴다
        if (!_data.TryGetValue(kv.Key, out var cur) || kv.Value.Version > cur.Version)
            _data[kv.Key] = kv.Value;
    }
}

// 읽기: tombstone 은 "없음"으로 보이되 저장소에는 남는다
public bool TryRead(string key, out string value)
{
    value = null;
    if (_data.TryGetValue(key, out var e) && !e.Deleted) { value = e.Value; return true; }
    return false;
}

tombstone 은 최대 복제 지연을 넘는 안전 기간이 지난 뒤에만 GC 한다(그 전에 지우면 부활 창이 다시 열린다). 벽시계 LWW 는 시계 스큐로 인과성을 잘못 판정할 수 있으므로, 정확성이 중요하면 버전을 논리 시계/벡터 시계로 바꾸고 동시 갱신은 병합(또는 CRDT)으로 해소한다.

더 나은 설계

• 삭제는 1급 시민: Dynamo/Cassandra 계열이 tombstone 을 쓰는 이유가 이것이다. 삭제도 버전 있는 상태로 복제·병합돼야 "부재"가 "삭제"를 이기지 못한다.
• tombstone GC 는 지연 상한 이후: gc_grace_seconds 처럼, 모든 복제본이 삭제를 봤다고 확신할 수 있는 시간이 지난 뒤에 청소한다.
• 인과성은 논리 시계로: 벽시계 LWW 는 구현이 쉽지만 시계 스큐에 취약하다. 버전 벡터/Lamport 시계로 "진짜 최신"과 "동시 충돌"을 구분하면 오래된 쓰기의 역전을 막는다.
• 트레이드오프: tombstone 은 저장 공간과 GC 복잡성을 늘리지만, 삭제 부활은 게임에서 심각(복구된 재화·부활한 밴·되살아난 우편)하므로 필수 비용이다.

면접 포인트

• 분산 복제에서 "삭제"의 정석은 값을 지우는 게 아니라 tombstone 을 쓰는 것. 안 그러면 stale 복제본과의 anti-entropy 가 삭제를 되돌린다.
• LWW 병합은 삭제에도 버전이 있어야 성립한다. 삭제에 버전이 없으면 삭제는 "가장 약한 상태"가 되어 어떤 쓰기에도 진다.