50. 조회 경로에서의 비원자 삽입(무락 Dictionary 동시 변형)

난이도 상

내 리뷰 · C#

내 리뷰 · C++

해설 · C#

해설 — 조회 경로에서의 비원자 삽입(무락 Dictionary 동시 변형)

난이도: 상

요약

GetOrCreate는 이름은 "조회"지만 실제로는 (A) 확인 후 (B)에서 딕셔너리를 **변형(삽입)**한다. Dictionary<TKey,TValue>는 스레드 안전하지 않아, 여러 스레드가 동시에 GetOrCreate를 호출하면 (1) 동시 쓰기로 내부 버킷/엔트리가 깨져 InvalidOperationException·IndexOutOfRangeException·무한 루프 등이 발생하고, (2) check-then-act가 비원자라 두 스레드가 모두 "없음"을 관측해 서로 다른 PlayerStat를 각각 생성한다. 한쪽이 덮어써 다른 쪽의 Kills 증가가 유실된다. "읽기 위주"라는 인상 때문에 무락으로 방치되지만, 조회 경로가 사실은 쓰기 경로다.

문제점

분류태그: 조회 경로의 숨은 변형 + check-then-act 비원자 + 스레드 비안전 컨테이너 동시 접근
증상: 부하 시 간헐적 컬렉션 예외/크래시, 킬 카운트 유실·중복 엔트리. 저부하(직렬)에선 재현 안 됨.
재현조건: 같은/다른 키에 대해 여러 스레드가 동시에 GetOrCreate(또는 AddKill) 호출. 특히 첫 등록이 겹칠 때.
근본원인: "읽기"로 가정한 경로가 자료구조를 변형한다. 그리고 그 변형(확인+삽입)이 원자적이지도, 락으로 보호되지도 않는다.

수정안

조회와 삽입을 원자화하고, 동시성 지원 자료구조를 쓰거나 락으로 보호한다.

// 방법 1) ConcurrentDictionary + 원자적 GetOrAdd
private readonly ConcurrentDictionary<int, PlayerStat> _stats = new();

public PlayerStat GetOrCreate(int playerId)
    => _stats.GetOrAdd(playerId, _ => new PlayerStat());
// 주의: 팩토리는 경합 시 여러 번 호출될 수 있다(초과 생성은 버려짐). 부작용 있는
//       생성이면 Lazy<PlayerStat> 를 값으로 넣어 "정확히 한 번 초기화"를 보장한다.

// 방법 2) 명시적 락 (읽기도 같은 락으로 보호해야 함)
private readonly object _gate = new object();
public PlayerStat GetOrCreate(int playerId)
{
    lock (_gate)
    {
        if (!_stats.TryGetValue(playerId, out var s))
        {
            s = new PlayerStat();
            _stats[playerId] = s;
        }
        return s;
    }
}

그리고 s.Kills++도 여러 스레드가 같은 PlayerStat를 만지면 비원자다 — Interlocked.Increment(ref s.Kills) 또는 락으로 보호.

더 나은 설계

읽기/쓰기 경로 분리: 진짜 읽기 전용 조회와, 등록을 별도 API로. "조회가 자료구조를 바꾸지 않는다"를 불변식으로.
읽기 폭주·쓰기 드묾이면 ConcurrentDictionary(스트라이프 락) 또는 COW/샤딩. GetOrAdd 팩토리 중복 호출 특성을 이해하고, 무거운/부작용 초기화는 Lazy<T>로.
카운터는 Interlocked 또는 값 자체를 원자적으로.

면접 포인트

Dictionary(비안전) vs ConcurrentDictionary, GetOrAdd 팩토리가 왜 여러 번 호출될 수 있는가와 Lazy<T> 대응.
"조회처럼 보이는 변형"(get-or-create)이 만드는 동시성 버그.
check-then-act 비원자 + 카운터 증가 비원자의 이중 결함.

해설 · C++

해설 — 조회 경로의 operator[] 자동 삽입 + 무락 동시 변형 (C++)

난이도: 상

요약

GetOrCreate는 stats_[player_id]를 반환한다. std::unordered_map::operator[] (A)(B)는 키가 없으면 기본 생성해 삽입한다 — 즉 "조회"가 사실은 삽입(쓰기)이다. 여러 스레드가 동시에 GetOrCreate/AddKill을 호출하면 unordered_map은 스레드 안전하지 않아 동시 삽입 + 리해시(rehash) 중 노드/버킷 포인터가 무효화되어 데이터 레이스·UB(크래시, 손상)가 발생한다. 또한 반환된 PlayerStat&를 여러 스레드가 kills++ 하는 것도 비원자다. 단일 스레드 데모는 kills=2 size=1로 정상처럼 보이지만, 동시 접근에서 무너진다.

문제점

분류태그: operator[]의 숨은 삽입(조회≠읽기) + 스레드 비안전 맵 동시 변형(rehash 무효화) + 비원자 카운터
증상: 부하 시 간헐 크래시/손상, 유령 엔트리(없는 키 조회만 해도 삽입됨), 킬 카운트 유실. ASan/TSan에서 data race.
재현조건: 여러 스레드가 동시에 GetOrCreate(없는 키 포함). 리해시가 걸리는 순간 특히 위험.
근본원인: operator[]가 변형 연산인데 읽기로 오인. 그 변형이 무락이고, 반환 참조 갱신도 비원자.

수정안

조회 전용 경로는 find(삽입 없음)를 쓰고, 등록/증가는 락 또는 원자 연산으로 보호한다.

#include <mutex>
#include <atomic>

std::mutex mtx_;
std::unordered_map<int, PlayerStat> stats_;

// 진짜 읽기: 삽입하지 않음
PlayerStat* Find(int id) {
    std::lock_guard<std::mutex> lk(mtx_);
    auto it = stats_.find(id);
    return it == stats_.end() ? nullptr : &it->second;
}

void AddKill(int id) {
    std::lock_guard<std::mutex> lk(mtx_);
    stats_[id].kills++;   // 락 안에서 삽입+증가 원자화
}

읽기 폭주면 std::shared_mutex(읽기 공유/쓰기 배타)로 조회 병렬성을 살리되, 조회 경로에서는 절대 operator[]를 쓰지 않는다(공유 락 하에 삽입은 UB). 반환 참조를 오래 들고 있으면 rehash로 무효화되니, 값 복사나 안정적 핸들 사용. 스니펫은 g++ -std=c++17 -pthread -fsyntax-only로 검증.

더 나은 설계

읽기/쓰기 API 분리: Find(비변형) vs GetOrRegister(변형). "조회는 자료구조를 바꾸지 않는다"를 불변식으로.
동시 해시맵(락 스트라이핑) 또는 읽기-대부분이면 COW/샤딩.
카운터는 std::atomic<int> 또는 락으로.

면접 포인트

unordered_map::operator[]가 삽입을 한다는 점(vs find/at)과 그로 인한 무락 동시 변형·rehash 무효화.
shared_mutex로 읽기 병렬화 시 "조회 경로 무변형" 규율의 중요성.
반환 참조의 rehash 무효화, 비원자 카운터.

← 문제로 돌아가기