해설 — 업적 달성 판정과 동시 다발 이벤트 집계 (C++)

난이도: 중상

답변 프레임워크: 요약 → 문제 분류 → 원인 → 수정안 → 더 나은 설계

요약

onProgress 가 공유 Achievement(progress, unlocked)와 중첩 unordered_map 을 동기화 없이 동시 갱신한다. (A) ach.progress += amount 는 비원자 RMW → 증가 유실. (B) "unlocked 검사 → 증가 → >= threshold 검사 → 달성/보상" 이 원자 단위가 아니라 임계 근처 동시 이벤트가 둘 다 보상한다(이중 달성). (C) registerAch 의 byPlayer_[...] 삽입은 동시 onProgress 의 조회/참조와 경합한다 — rehash 가 일어나면 버킷 재배치로 진행 중인 순회/참조가 깨지고, Achievement& 참조 수명도 위태롭다(데이터 레이스 UB). 정답 한 줄: (플레이어,업적) 단위로 증가~달성 확정을 원자화하고, 달성 확정을 단 한 번만(락 또는 CAS) 일어나게 하며, 맵 동시 접근을 락 또는 안정적 자료구조로 보호한다.

변별: problem14(퀘스트 보상 중복 수령/멱등성)와 달리, 본 문제는 다중 스레드 누적 카운터 정확성 + 임계 도달 시 1회 달성 확정 + 맵 동시성(rehash/참조 수명) 이 핵심.

문제점

(A) 진행도 비원자 누적 — 증가 유실 (동시성) ★간판

• 분류 태그: lost update / data race.
• 증상: ach.progress += amount 는 read-add-write. 동시 실행 시 한쪽 증가가 사라진다. 표준상 동기화 없는 동시 R/W 는 정의되지 않은 동작(UB).
• 근본 원인: 복합 연산에 원자/락 없음.

(B) 달성 판정 TOCTOU — 이중 달성/보상 중복 (동시성·정합) ★간판

• 분류 태그: check-then-act.
• 증상: threshold=100, progress=99. 두 이벤트(+1) 동시:
  • T1: unlocked=false 통과, progress 증가
  • T2: unlocked=false 통과, progress 증가
  • 둘 다 progress>=100 을 보고 unlocked=true + grantReward 2회.
• 근본 원인: 증가와 "달성 확정"이 같은 임계구역이 아니고, unlocked 전이가 1회 보장 안 됨.

(C) 중첩 map 동시 삽입/조회 — rehash·참조 무효화 (메모리/동시성) ★C++ 핵심

• 증상: registerAch 의 byPlayer_[playerId] 와 내부 [...]=ach 는 삽입이라 로드팩터 초과 시 rehash 를 유발한다. unordered_map 은 rehash 시 모든 iterator 가 무효화되고(노드 자체는 살지만 버킷 배치가 바뀜), 동시에 onProgress 가 다른 키로 find/순회 중이면 자료구조 손상/크래시. 참조 Achievement& ach 도 외부(부모) 맵이 rehash 되면 부모 노드는 안정적이나 동시 수정과의 데이터 레이스로 UB.
• 근본 원인: 공유 컨테이너 동시 접근에 보호가 전혀 없다.

수정안

핵심: (플레이어,업적) 단위 락으로 증가~판정 원자화 + 맵 보호. (unordered_map 은 노드 기반이라 erase 되지 않는 한 원소 주소가 안정적 → 외부는 한 번 구성 후 읽기 위주로.)

#include <mutex>

struct Achievement {
    int     achievementId;
    int64_t threshold;
    int64_t progress = 0;
    bool    unlocked = false;
    std::mutex gate;          // 업적 단위 락 (이동/복사 불가 주의)
};

class AchievementService {
public:
    void onProgress(int64_t playerId, int achievementId, int64_t amount) {
        if (amount <= 0) return;
        Achievement* ach = nullptr;
        {
            std::lock_guard<std::mutex> g(mapMu_);     // 맵 조회 보호
            auto pit = byPlayer_.find(playerId);
            if (pit == byPlayer_.end()) return;
            auto ait = pit->second.find(achievementId);
            if (ait == pit->second.end()) return;
            ach = &ait->second;   // 노드 기반: erase 안 하면 주소 안정
        }

        bool justUnlocked = false;
        {
            std::lock_guard<std::mutex> g(ach->gate);  // 업적 단위 임계구역
            if (ach->unlocked) return;
            ach->progress += amount;
            if (ach->progress >= ach->threshold) {
                ach->unlocked = true;
                justUnlocked = true;
            }
        }
        if (justUnlocked) grantReward_(playerId, achievementId); // 락 밖, 단 한 번
    }

    // Achievement 가 std::mutex 를 가져 복사/이동 불가 → in-place 로만 생성.
    void registerAch(int64_t playerId, int achievementId, int64_t threshold) {
        std::lock_guard<std::mutex> g(mapMu_);
        auto& m = byPlayer_[playerId];               // 없으면 inner map 기본 생성
        auto [it, inserted] = m.try_emplace(achievementId); // 기본 생성 in place(이동 없음)
        it->second.achievementId = achievementId;    // 비-mutex 필드만 대입
        it->second.threshold     = threshold;
    }

private:
    std::unordered_map<int64_t, std::unordered_map<int, Achievement>> byPlayer_;
    std::mutex mapMu_;
    std::function<void(int64_t, int)> grantReward_;
};

포인트

• mapMu_ 로 조회/삽입을 보호 → rehash 와 조회의 경합 차단. 원소 포인터는 노드 기반이라 락을 풀고도 안전(단 같은 키를 erase 하지 않는 한).
• unlocked 검사 + 증가 + 확정이 같은 gate → 하나의 스레드만 justUnlocked.
• Achievement 가 std::mutex 를 멤버로 가지므로 복사/이동 불가 — 컨테이너에는 emplace/std::move 로 넣는다(값 복사 API 금지).

lock-free 대안

progress 를 std::atomic<int64_t> 로, fetch_add(amount) 의 반환값(=이전 값)을 이용해 "이전 < threshold && 이전+amount >= threshold" 인 그 스레드만 unlocked(std::atomic_flag 또는 atomic<bool> CAS) 를 0→1 로 바꿔 보상. 트레이드오프: 맵 동시성은 여전히 별도 보호 필요, 음수/리셋이 있으면 경계 판정 복잡.

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

1. (플레이어,업적) 파티션 단일 집계기(액터): 이벤트를 키별 큐로 보내 한 스레드가 순차 처리 → 락 없이 정확. 트레이드오프: 파티셔닝/지연.
2. 멱등 보상: grantReward_ 가 (플레이어,업적) 키로 멱등 → 판정 버그에도 이중 지급 방지.
3. 분산 원자 카운터(Redis INCR + 단조 unlock 플래그): 다중 게임서버 정확. 왕복 비용 ↑.
4. 고빈도 배치 집계: 스레드로컬 누적 후 주기적 원자 반영(경합 감소, 준실시간).

면접 포인트 (예상 질문)

1. unordered_map 에 동시 삽입이 일어날 때 rehash 가 왜 위험한가? "노드 기반 주소 안정성" 은 어디까지 보장되며 그 예외는?
2. threshold 근처 동시 이벤트가 둘 다 달성 분기에 들어가는 인터리빙을 설명하라. std::atomic + CAS 로 1회만 확정하는 코드를 써보라.
3. std::mutex 멤버를 가진 구조체를 unordered_map 에 넣을 때 무엇을 주의해야 하나 (복사/이동 불가, emplace)?