해설 — 타이머 휠의 동시성: 비원자 cursor, 비동기 취소, 무보호 슬롯 리스트

난이도: 최상

요약

"tick은 단일 스레드라 안전하다"는 전제가 틀렸다. 워커들이 동시에 같은 슬롯에 Schedule하고, tick 스레드가 같은 슬롯을 순회한다 — 슬롯 리스트는 다중 스레드가 만지는 공유 자료구조다. 결함이 네 갈래로 겹친다. (A) cursor_가 일반 uint64_t 라 tick의 쓰기와 워커의 읽기 사이에 원자성·가시성·순서 보장이 없다(찢김·stale). (B) Cancel이 비원자 bool 플래그만 세워 tick 스레드에 가시성 보장 없이 전달되고, 게다가 tick이 노드를 delete한 뒤 워커가 그 노드를 Cancel하면 use-after-free. (C) 슬롯 리스트 head 삽입이 락도 atomic도 없어 Schedule끼리, Schedule과 Tick의 슬롯 떼어내기(buckets_[idx]=nullptr)가 레이스 → 노드 유실/리스트 손상. (D) 콜백 실행 중/후 즉시 delete가 동시 취소·재참조와 충돌해 use-after-free / 이중 해제. 핵심은 "단일 tick 스레드"라는 가정이 삽입/취소가 다른 스레드라는 사실을 무시한 것.

문제점

(A) std::uint64_t cursor_ — 비원자 공유 (분류: 동시성, 핵심)

• 증상: 워커의 Cursor()/Schedule이 stale하거나 찢긴 cursor를 봐서 만료 슬롯을 잘못 계산 → 타이머가 한 바퀴 늦게 또는 영영 안 터짐. "곧 터지는지" 판단 로직 오류.
• 재현조건: 32비트 타깃에선 64비트 store/load가 찢어질 수 있고(torn), 64비트에서도 가시성·순서 보장이 없어 워커가 옛 cursor를 본다.
• 근본원인: 일반 변수에 대한 동시 읽기/쓰기는 C++에서 데이터 레이스 = 정의되지 않은 동작(UB). Tick의 cursor_ = cur+1과 워커의 cursor_ 읽기 사이에 happens-before가 없다. std::atomic<uint64_t> + 적절한 memory_order가 필요하다(slot 리스트 발행과 묶으려면 release/acquire).

(B) bool canceled 비원자 + 수명 미보호 (분류: 동시성/메모리)

• 증상: (1) 워커가 Cancel로 세운 플래그가 tick 스레드에 안 보여 취소된 타이머가 그대로 실행(취소 누락). (2) 더 심각: tick이 노드를 delete한 뒤 워커가 그 포인터로 Cancel을 호출 → use-after-free. (3) tick이 콜백 실행 직전 !canceled를 봤는데 그 직후 워커가 취소 → "막 취소했는데 실행됨".
• 근본원인: 비원자 bool은 가시성·순서 보장이 없다. 그리고 취소와 노드 수명이 분리돼 있어, tick이 노드를 회수하는 순간 워커가 들고 있는 TimerNode*가 댕글링이 된다. 취소는 "플래그 + 안전한 수명(소유권/세대 토큰)"으로 설계해야 한다.

(C) 슬롯 리스트 head 삽입/탈착 무보호 (분류: 동시성, 매우 심각)

• 증상: 두 워커가 같은 슬롯에 동시에 Schedule하면 n->next = buckets_[idx]; buckets_[idx] = n; 가 인터리브돼 한 노드가 유실된다(lost update). tick의 buckets_[idx] = nullptr(슬롯 떼기)와 워커의 삽입이 겹치면 방금 넣은 노드가 사라지거나 리스트가 끊긴다.
• 재현조건: 같은 슬롯에 동시 삽입, 또는 tick 처리 중 그 슬롯에 삽입. 슬롯 수가 적고 부하가 높을수록 충돌↑.
• 근본원인: buckets_[idx]는 여러 스레드가 쓰는 공유 포인터인데 락도 atomic CAS도 없다. "tick이 단일 스레드"여도 삽입은 워커(다중) 이므로 슬롯은 공유 자원이다.

(D) delete node 즉시 해제 — use-after-free / 이중 해제 (분류: 메모리/동시성)

• 증상: tick이 노드를 delete했는데 같은 노드 포인터를 들고 있던 워커가 Cancel(n) 또는 재스케줄로 접근 → use-after-free. 두 경로가 같은 노드를 회수하면 double free.
• 근본원인: 락프리/동시 환경에서 즉시 해제는 안전하지 않다. 다른 스레드가 그 노드를 참조 중일 수 있어, 안전한 회수(소유권 명확화, 또는 hazard pointer/epoch)가 필요하다.

메모리 순서만의 문제가 아니라 공유 자료구조 동기화 + 안전한 회수 + 취소 수명이 전부 얽힌 복합 결함이다. atomic 한두 개를 끼워서는 안 풀린다.

수정안

핵심 결정: 게임서버 타이머 휠에서 각 슬롯을 락(또는 슬롯별 lock-free 큐)으로 보호하고, cursor를 atomic으로, 취소는 노드를 owning한 채 atomic flag로, 회수는 tick 스레드가 단독 소유권을 확보한 뒤에만 한다. 가장 견고하고 단순한 길은 슬롯별 뮤텍스 + 취소 플래그 atomic + tick이 콜백을 슬롯 락 밖에서 실행.

#include <atomic>
#include <mutex>
#include <memory>
#include <vector>

struct TimerNode
{
    std::uint64_t expireTick;
    std::function<void()> callback;
    std::atomic<bool> canceled{false};   // (B) atomic flag
    // 수명은 shared_ptr로 관리 → 댕글링/이중해제 차단
};

class TimingWheel
{
public:
    explicit TimingWheel(int slots)
        : slots_(slots), buckets_(slots), locks_(slots) {}

    // 핸들을 돌려주어 Cancel이 안전하게 노드를 잡게 함
    using Handle = std::shared_ptr<TimerNode>;

    Handle Schedule(std::uint64_t delayTicks, std::function<void()> cb)
    {
        // (A) atomic load (acquire): cursor의 최신값을 본다
        std::uint64_t cur = cursor_.load(std::memory_order_acquire);
        std::uint64_t expire = cur + delayTicks;
        int idx = static_cast<int>(expire % slots_);

        auto n = std::make_shared<TimerNode>();
        n->expireTick = expire;
        n->callback = std::move(cb);

        std::lock_guard<std::mutex> lk(locks_[idx]);   // (C) 슬롯 락
        buckets_[idx].push_back(n);
        return n;   // 워커는 이 핸들로만 Cancel
    }

    // (B) 노드를 shared_ptr로 잡고 있으므로 use-after-free 불가
    void Cancel(const Handle& n)
    {
        if (n) n->canceled.store(true, std::memory_order_release);
    }

    // tick 스레드 단독
    void Tick()
    {
        std::uint64_t cur = cursor_.load(std::memory_order_relaxed); // 자기만 씀
        int idx = static_cast<int>(cur % slots_);

        std::vector<Handle> due;
        {
            std::lock_guard<std::mutex> lk(locks_[idx]);   // (C) 슬롯 락
            auto& bucket = buckets_[idx];
            std::vector<Handle> keep;
            keep.reserve(bucket.size());
            for (auto& n : bucket)
            {
                if (n->canceled.load(std::memory_order_acquire))
                    continue;                       // 그냥 버림(회수는 shared_ptr가)
                if (n->expireTick <= cur)
                    due.push_back(n);               // 실행 대상
                else
                    keep.push_back(n);              // 다음 바퀴
            }
            bucket.swap(keep);
        }

        // (D) 콜백은 슬롯 락 밖에서 실행 (재진입/장시간 콜백 안전)
        for (auto& n : due)
            if (!n->canceled.load(std::memory_order_acquire))
                n->callback();
        // 노드 메모리는 shared_ptr가 마지막 참조 소멸 시 자동 회수 → double free 없음

        // (A) cursor 전진을 release로 발행: 위 슬롯 변경이 워커에게 보이도록
        cursor_.store(cur + 1, std::memory_order_release);
    }

    std::uint64_t Cursor() const { return cursor_.load(std::memory_order_acquire); }

private:
    int slots_;
    std::vector<std::vector<Handle>> buckets_;
    std::vector<std::mutex> locks_;            // 슬롯별 락(경합 분산)
    std::atomic<std::uint64_t> cursor_{0};     // (A)
};

핵심 변경 요약:

• (A) cursor_를 std::atomic<uint64_t>로. tick은 자기 쓰기라 relaxed load + release store(슬롯 변경 발행), 워커는 acquire load.
• (B) canceled를 std::atomic<bool>(release/acquire)로 가시성 확보. 노드를 shared_ptr로 소유해 워커의 Cancel이 살아있는 노드만 만지게 → use-after-free 제거.
• (C) 슬롯별 std::mutex로 삽입/순회를 보호. 슬롯 단위라 경합이 분산된다.
• (D) delete 제거. shared_ptr 참조 카운트가 0이 될 때 자동 회수 → 이중 해제/댕글링 없음. 콜백은 락 밖에서 실행해 재진입(콜백이 다시 Schedule) 데드락 회피.

더 나은 설계

1. 슬롯별 lock-free 삽입 큐(MPSC): 워커=다중 생산자, tick=단일 소비자이므로 슬롯마다 MPSC 큐를 두면 Schedule이 락 없이 push, tick이 단독 drain. 뮤텍스보다 확장성↑. 트레이드오프: 구현 복잡도 + 안전 회수(epoch) 필요.

2. 취소를 "토큰 무효화"로: 노드 안의 std::atomic<uint64_t> generation을 두고, Cancel은 generation을 증가시켜 핸들과 불일치하면 무효 처리. shared_ptr 비용을 줄이면서 ABA류 재사용도 방어. 트레이드오프: 핸들 비교 로직 추가.

3. 계층형 타이밍 휠(hierarchical timing wheel): 큰 delay를 여러 단계 휠로 캐스케이드(리눅스 커널 방식). 슬롯 수를 작게 유지하면서 넓은 범위를 O(1)에 가깝게. 동시성 설계는 위 원칙 동일.

4. 취소 비용 vs 즉시 제거: 여기처럼 "플래그 후 tick에서 스킵(lazy delete)"은 Cancel이 O(1)이지만 만료 시점까지 노드가 살아있다. 즉시 제거가 필요하면 슬롯 락 잡고 리스트에서 unlink(O(n) 또는 intrusive doubly-linked로 O(1)). 트레이드오프: Cancel 지연 vs 메모리 점유.

5. 콜백 실행 정책: 콜백을 tick 스레드에서 직접 실행하면 긴 콜백이 휠을 막는다. 만료 노드를 잡 큐로 넘겨 워커 풀에서 실행하면 tick이 가벼워진다. 트레이드오프: 지연/순서.

면접 포인트

1. "tick이 단일 스레드라 슬롯이 안전하다"는 주장의 허점은? 어떤 접근이 다중 스레드라서 슬롯이 공유 자원이 되는가?
2. cursor_를 단순 uint64_t로 두면 64비트 플랫폼에서도 왜 문제인가? 데이터 레이스 UB, 그리고 release/acquire로 cursor 전진과 슬롯 변경 발행을 묶는 이유를 설명하라.
3. 동시 환경에서 "취소"를 비원자 bool 플래그 + 즉시 delete로 구현하면 어떤 use-after-free/이중해제가 생기나? shared_ptr/세대 토큰/hazard pointer 중 무엇으로 안전한 회수를 보장할지와 트레이드오프를 논하라.