해설 — 동점자 타이브레이커와 동시 점수 갱신 (C++)

난이도: 상

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

요약

Entry 가 bestScore 와 reachedAtMs 를 별개 atomic 으로 둔다. 각각은 원자지만 둘의 조합은 원자가 아니다. (A) submit 이 점수를 store 한 뒤 시각을 따로 store 하므로, 그 사이를 읽는 higher 는 새 점수 + 옛 시각(또는 그 반대)의 찢어진 쌍을 본다. (B) load → 비교 → store 가 RMW 인데 CAS 가 아니라, 두 스레드가 같은 cur 를 읽고 둘 다 갱신하면 더 높은 점수가 유실된다. (C) 조건이 newScore >= cur 라 동점인데도 reachedAtMs 를 현재 시각으로 덮어써 "더 이른 도달이 우선" 이라는 타이브레이커를 깬다(늦게 같은 점수를 낸 사람이 도달 시각을 최신으로 갱신 → 영원히 동점 1등 다툼에서 밀리거나 뒤바뀜). 정답 한 줄: (score, ts) 를 하나의 원자 단위로 묶어 CAS 루프(또는 엔트리 락)로 갱신하고, 점수가 "엄격히 클 때만" 갱신해 동점 시 도달 시각을 보존한다.

변별: problem1(zone 통계 단순 lost update), content13(시즌 마감 점수 갱신)과 달리, 본 문제는 (점수+도달시각) 복합 키의 원자적 갱신 + 타이브레이커 비교 정확성 이 핵심이다.

문제점

(A) (score, ts) 비원자 복합 갱신 / 찢어진 읽기 — 정합 (동시성) ★간판

• 분류 태그: non-atomic compound update / torn read.
• 증상: submit 은 bestScore.store(...) 와 reachedAtMs.store(...) 를 두 번에 나눠 쓴다. 두 store 사이에 higher 가 읽으면 "새 점수 + 옛 시각" 같은 존재한 적 없는 조합으로 순위를 매긴다. 두 submit 이 동시에 끼면 A 의 점수 + B 의 시각이 섞일 수도 있다.
• 재현조건: 갱신 중 다른 스레드의 비교/갱신.
• 근본 원인: 함께 바뀌어야 할 두 값을 독립 원자로 쪼갰다(원자성의 단위 오류).

(B) RMW 비 CAS — 갱신 유실 (동시성) ★간판

• 분류 태그: lost update / check-then-act.
• 증상: cur = load() 후 if (newScore >= cur) store(newScore). T1(80)·T2(90)가 같은 cur=70 을 읽고 둘 다 통과 → 인터리빙에 따라 80 이 90 을 덮어 최고점 90 이 사라진다.
• 근본 원인: "현재값을 보고 더 크면 쓴다" 를 단일 원자 비교-교환(CAS)으로 하지 않음.

(C) >= 경계 — 타이브레이커 파괴 (정확성/정합)

• 분류 태그: boundary / semantic.
• 증상: 동점(newScore == cur)에도 분기에 들어가 reachedAtMs = nowMs 로 도달 시각을 최신으로 덮는다. "그 점수에 처음 도달한 시각" 이어야 하는데 늦은 제출이 시각을 늦춰, 먼저 도달한 사람이 동점 우선권을 잃거나 순위가 출렁인다. 점수도 같은 값을 또 store 해 불필요.
• 근본 원인: 갱신은 엄격히 클 때만(>) 해야 하며, 동점이면 아무것도 건드리면 안 된다.

(참고) memory_order_relaxed — 가시성/순서

• 모두 relaxed 라 다른 스레드의 갱신 가시성/순서 보장이 약하다. 단일 원자로 묶더라도 최소 acq_rel(CAS)·acquire(load) 가 적절.

수정안

방법 1 — 엔트리 단위 락 (가장 명확)

#include <mutex>
struct Entry {
    int32_t bestScore = 0;
    int64_t reachedAtMs = 0;
    std::mutex mu;          // 복사/이동 불가 → emplace 로만 삽입
};

void submit(int64_t playerId, int32_t newScore, int64_t nowMs) {
    Entry& e = table_.at(playerId);            // 사전 등록(아래 주: 맵 동시성)
    std::lock_guard<std::mutex> g(e.mu);
    if (newScore > e.bestScore) {              // 엄격히 클 때만
        e.bestScore   = newScore;
        e.reachedAtMs = nowMs;                 // 점수와 시각을 함께(원자 단위)
    }
    // 동점/이하면 아무것도 안 함 → 도달 시각 보존
}

static bool higher(Entry& a, Entry& b) {       // 읽기도 락으로 일관된 쌍 확보
    std::scoped_lock lk(a.mu, b.mu);           // 데드락 회피(동시 락)
    if (a.bestScore != b.bestScore) return a.bestScore > b.bestScore;
    return a.reachedAtMs < b.reachedAtMs;      // 동점: 더 이른 도달 우선
}

방법 2 — 단일 원자로 묶어 CAS (lock-free)

점수와 시각을 한 구조체에 담아 하나의 std::atomic 으로 CAS:

struct Snap { int32_t score; int32_t _pad; int64_t reachedAtMs; }; // 패딩 명시 초기화

class Leaderboard {
    std::unordered_map<int64_t, std::atomic<Snap>> table_;
public:
    void submit(int64_t playerId, int32_t newScore, int64_t nowMs) {
        std::atomic<Snap>& slot = table_.at(playerId);
        Snap cur = slot.load(std::memory_order_acquire);
        for (;;) {
            if (newScore <= cur.score) return;            // 엄격히 클 때만, 동점은 보존
            Snap next{ newScore, 0, nowMs };              // _pad=0 으로 비교 안정화
            if (slot.compare_exchange_weak(cur, next,
                    std::memory_order_acq_rel, std::memory_order_acquire))
                return;
            // 실패 시 cur 가 최신값으로 갱신됨 → 루프 재평가
        }
    }
};

포인트

• Snap 한 번의 load/CAS 로 (score, ts) 가 항상 일관된 쌍 → 찢어진 읽기 없음.
• compare_exchange_weak 루프가 lost update 를 막는다(누가 더 큰 값을 썼으면 <= 로 종료).
• newScore <= cur.score 로 엄격히 클 때만 갱신 → 동점 시 reachedAtMs 보존(타이브레이커).
• 16바이트 std::atomic<Snap> 는 플랫폼에 따라 DWCAS(cmpxchg16b) 또는 라이브러리 락 사용 → is_lock_free() 확인. 패딩 바이트는 0 으로 초기화해야 비교가 스퍼리어스 실패하지 않음. (gcc/clang 에선 16바이트 atomic 이 -latomic 링크를 요구하거나 라이브러리 락으로 폴백될 수 있다 — "lock-free 인 줄 알았는데 실은 락" 함정. 빌드 시 is_lock_free() 로 검증할 것.)

맵 동시성: table_ 자체에 동시 삽입이 있으면 별도 보호(사전 등록/락/concurrent map)가 필요하다. 위는 엔트리는 사전 등록되어 구조는 읽기 전용이라고 가정한다.

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

1. 64비트 단일 키로 패킹: 점수(상위)+(시각을 "이를수록 큰 값" 으로 인코딩, 하위)로 묶어 단일 atomic<uint64_t> max-CAS. 단 ms epoch 는 32비트를 넘으므로 상대 epoch/초 단위 등으로 비트 예산을 맞춰야 함(정밀도 트레이드오프). 비트가 맞으면 가장 빠르고 ABA 없음.
2. 불변 스냅샷 교체(RCU 류): 엔트리를 불변 객체로 만들고 포인터만 CAS 교체 → 읽기 무락. 트레이드오프: 메모리 재활용/수명(에포크 기반 회수).
3. 권위는 DB/Redis 원자 연산: 다중 게임서버라면 ZADD/Lua 스크립트로 점수+타이브레이크 키를 원자 갱신. 트레이드오프: 왕복 비용, 인메모리 캐시와의 일관성(problem13 연계).
4. 타이브레이커를 점수에 내장: "점수×K − 도달정규화시각" 같은 단일 정렬 키로 환원하면 비교가 단순해짐. 트레이드오프: 오버플로/정밀도 설계.

면접 포인트 (예상 질문)

1. bestScore 와 reachedAtMs 를 각각 atomic 으로 두면 왜 "둘 다 atomic 인데도" 틀리는가? 원자성의 단위를 어떻게 잡아야 하나?
2. load-비교-store 대신 compare_exchange_weak 루프가 lost update 를 막는 원리를 인터리빙으로 설명하라.
3. >= 와 > 한 글자 차이가 타이브레이커를 어떻게 깨는가? 16바이트 std::atomic 의 lock-free 여부와 패딩 주의점은?