48. 카피-온-라이트(COW) 라우팅 테이블의 동시 갱신 (C#)

난이도 최상

내 리뷰 · C#

내 리뷰 · C++

해설 · C#

해설 — 카피-온-라이트(COW) 라우팅 테이블의 동시 갱신 (C#)

난이도: 최상

요약

SetRoute 는 현재 스냅샷을 읽고(read) 수정본을 만든 뒤(copy-modify) 무조건 대입한다(store). 이 read-modify-write 가 여러 스레드에서 원자적으로 직렬화되지 않아, 두 갱신이 같은 current 를 읽고 각자의 수정본으로 덮어쓰면 하나의 갱신이 유실된다(lost update). "원자적 포인터 교체"는 읽기를 안전하게 할 뿐, 갱신들 사이의 원자성을 주지 않는다.

문제점

(A) CAS 없는 무조건 교체 → 갱신 유실: 스레드 T1 이 SetRoute(1, "a"), T2 가 SetRoute(2, "b") 를 동시에 호출한다고 하자.
1. T1: current = _map(비어 있음) → updated = {1:"a"}
2. T2: current = _map(아직 비어 있음) → updated = {2:"b"}
3. T1: _map = {1:"a"}
4. T2: _map = {2:"b"} ← T1 의 {1:"a"} 가 사라짐 결과 테이블에 샤드 2 만 남고 샤드 1 라우트가 유실된다. volatile 은 가시성/재배열만 다루지 read-modify-write 를 원자화하지 않는다.
- 재현: 오토스케일러와 운영 API 가 서로 다른 샤드를 거의 동시에 추가.
- 근본 원인: "스냅샷 교체"가 이전에 읽은 스냅샷이 여전히 최신일 때만 유효해야 하는데 그 조건(compare)을 확인하지 않음.

수정안

Interlocked.CompareExchange 로 "내가 읽은 스냅샷이 그대로일 때만 교체"를 보장하고, 경합 시 재시도한다.

public void SetRoute(int shardId, string endpoint)
{
    while (true)
    {
        var current = _map;
        var updated = current.SetItem(shardId, endpoint);
        // current 가 그대로면 updated 로 교체, 아니면 실패한 이전 값 반환.
        if (Interlocked.CompareExchange(ref _map, updated, current) == current)
            return;
        // 다른 스레드가 먼저 바꿈 → 최신 스냅샷으로 재시도(수정을 다시 적용).
    }
}

(참고: Interlocked.CompareExchange(ref volatile T, ...) 사용을 위해 필드 선언에서 volatile 대신 접근 지점에서 Volatile.Read 를 쓰거나, CAS 자체가 가시성 배리어를 제공하므로 CAS 루프 모델에선 필드 volatile 없이도 안전하다.)

경합이 심하거나 갱신 로직이 복잡하면 쓰기만 락으로 직렬화(읽기는 여전히 무락)해도 된다:

private readonly object _writeGate = new();
public void SetRoute(int shardId, string endpoint)
{
    lock (_writeGate) { _map = _map.SetItem(shardId, endpoint); }
}

더 나은 설계

쓰기 직렬화 + 무락 읽기: COW 의 정석은 "읽기 무락 / 쓰기는 단일 직렬화(락 또는 CAS 루프)". 읽기 성능을 지키면서 갱신 유실을 없앤다.
배치 갱신: 여러 변경을 한 트랜잭션으로 모아 교체 횟수와 경합을 줄인다.
버전/세대 번호를 스냅샷에 넣어 관측·디버깅과 stale 판정을 쉽게.

면접 포인트

"원자적 참조 교체"와 "read-modify-write 원자성"은 다르다 — 후자는 CAS/락 필요.
CAS 루프의 재시도 의미(내가 본 값이 바뀌었으면 최신으로 다시 계산).
volatile 이 해결하는 것(가시성/순서)과 못 하는 것(복합 갱신 원자성).

해설 · C++

해설 — 카피-온-라이트(COW) 라우팅 테이블의 동시 갱신 (C++)

난이도: 최상

요약

setRoute 는 스냅샷을 로드(read)→복사·수정(copy-modify)→atomic_store 로 교체(store) 한다. 이 read-modify-write 가 원자적으로 직렬화되지 않아, 두 갱신이 같은 current 를 로드해 각자 덮어쓰면 하나가 유실된다(lost update). atomic_load/atomic_store 는 읽기의 수명·원자성만 보장할 뿐, 갱신들 사이의 원자성을 주지 않는다.

문제점

(A) compare-exchange 없는 무조건 교체 → 갱신 유실: T1 setRoute(1,"a"), T2 setRoute(2,"b") 가 동시에 실행되면 둘 다 빈 스냅샷을 로드 → 각각 {1:"a"}, {2:"b"} 를 만들고 → 나중에 store 한 쪽이 이긴다. 결과에 한 라우트만 남는다. 읽기는 atomic_load 라 UAF 는 없지만(참조 카운트가 옛 스냅샷 수명을 지킴), 논리적 갱신 유실이 남는다.
- 근본 원인: 교체가 "내가 로드한 스냅샷이 여전히 최신일 때만" 유효해야 하는데 그 조건을 검사하지 않음.
(참고) 만약 atomic_load/atomic_store 대신 평범한 shared_ptr 을 여러 스레드가 동시 대입/읽기 했다면 그건 별개의 데이터 레이스(UB) 다. 여기서는 원자 접근을 썼으므로 그 문제는 없고, 순수 lost-update 만 문제다.

수정안

atomic_compare_exchange_weak 로 CAS 루프를 돌려 경합 시 최신 스냅샷으로 재적용한다.

void setRoute(int shardId, std::string endpoint) {
    std::shared_ptr<const Map> current = std::atomic_load(&map_);
    for (;;) {
        auto updated = std::make_shared<Map>(*current);   // 최신 current 기준 복사
        (*updated)[shardId] = endpoint;                   // 수정
        std::shared_ptr<const Map> desired = updated;
        // current 가 그대로면 desired 로 교체; 아니면 current 를 최신값으로 갱신 후 재시도.
        if (std::atomic_compare_exchange_weak(&map_, &current, desired))
            return;
        // 실패 시 current 에는 최신 스냅샷이 담겨 있으므로 루프가 그것을 재사용한다.
    }
}

(C++20 이면 std::atomic<std::shared_ptr<const Map>> 로 더 깔끔하게 표현 가능하나, g++11/-std=c++17 에서는 프리 함수 atomic_* 오버로드를 사용한다.)

경합이 낮고 단순하면 쓰기 뮤텍스로 직렬화(읽기는 여전히 무락)해도 충분하다:

std::mutex writeMx_;
void setRoute(int shardId, std::string endpoint) {
    std::lock_guard lk(writeMx_);
    auto updated = std::make_shared<Map>(*std::atomic_load(&map_));
    (*updated)[shardId] = std::move(endpoint);
    std::atomic_store(&map_, std::shared_ptr<const Map>(updated));
}

더 나은 설계

무락 읽기 + 직렬화된 쓰기(락 또는 CAS 루프) 가 COW 의 정석.
배치 갱신으로 교체 횟수·복사 비용·경합 감소(큰 맵은 복사 비용이 크다).
RCU/persistent 자료구조로 부분 공유 복사(전체 복사 회피)를 고려.

면접 포인트

atomic_load/store 가 주는 것(수명·원자 읽기)과 안 주는 것(RMW 원자성)의 구분.
CAS 루프에서 compare_exchange 실패 시 기대값이 최신으로 갱신되는 메커니즘.
COW 의 복사 비용/경합 트레이드오프와 배치·persistent 자료구조 대안.

← 문제로 돌아가기