대규모 타이머 스케줄링: 타임휠(Timing Wheel)과 지연 작업 큐 · 해설

난이도: 중상

1. 소박한 방법의 한계

(a) 타이머마다 스레드/sleep: 타이머 하나당 스레드는 수십만 개에서 메모리·컨텍스트 스위치 폭발로 불가능. 스레드풀+sleep 도 대기 스레드가 자원을 잡고, 취소·재조정이 어렵다.
(b) 정렬된 리스트: 다음 만료는 머리에서 O(1) 로 꺼내지만, 삽입이 O(n)(정렬 위치 탐색). 수백만 개에 매 삽입 O(n) 은 파탄.
(c) 최소 힙 / 우선순위 큐: 삽입·삭제 O(log n), 최소값 조회 O(1). 범용적이고 흔히 쓰지만, 수백만 개 규모에서 매 틱 다수 만료 처리 시 log n 상수·캐시 미스가 누적되고, 임의 타이머 취소가 O(n)(위치 탐색) 또는 별도 인덱스/지연 삭제(tombstone) 관리를 요구한다. "만료가 대부분 가까운 미래에 몰리는" 게임 타이머 분포에는 과한 정렬 비용.

구조: 크기 N 의 버킷 배열(원형), 각 버킷은 그 슬롯에 만료될 타이머들의 리스트. 틱 간격 (tick) 마다 커서가 한 칸 전진한다. 한 바퀴 = N × tick 시간을 표현.
삽입: 만료까지 남은 틱 수 d 를 계산해 bucket = (cursor + d) % N 에 리스트로 끝에 추가 → O(1). (단일 레벨에선 d < N 이어야 함.)
만료: 매 틱마다 커서가 가리키는 버킷 하나만 훑어 그 안의 타이머를 실행/재무장 → 버킷당 타이머 수에 비례. 전체적으로 타이머 하나는 삽입 O(1), 만료 시 O(1) 로 처리된다(정렬 비용 없음).
핵심: 힙과 달리 전역 정렬을 하지 않는다. "언제 만료되는가" 를 버킷 인덱스로 직접 계산(해싱) 하므로 삽입이 상수 시간. 리소스 만료가 가까운 미래에 몰리는 게임 워크로드에 특히 잘 맞는다.

단일 레벨 한계: 표현 가능한 최대 지연 = N × tick. 긴 지연(예: 24시간 리스폰)을 큰 N 으로 담으면 메모리 낭비, N 을 줄이면 먼 미래를 못 담는다. 트레이드오프.
계층형(hierarchical): 시계처럼 여러 레벨을 쌓는다. 예: 레벨0(초, 1틱=1초, 60버킷) → 레벨1(분, 1버킷=60초) → 레벨2(시). 먼 미래 타이머는 상위(굵은) 레벨에 담긴다.
캐스케이드(cascade): 상위 레벨의 한 버킷이 만료 시점에 도달하면, 그 안의 타이머들을 하위 레벨의 정확한 버킷들로 재분배(내려보냄) 한다. 즉 "1시간 뒤" 타이머는 처음엔 시 단위 버킷에 있다가, 그 시각이 가까워지면 분 → 초 버킷으로 내려온다. 이렇게 하면 각 레벨은 작은 N 으로도 아주 긴 지연을 표현하며, 삽입/만료는 여전히 (분할상환) 상수에 가깝다.

틱 간격(해상도): 작을수록(예: 1ms) 정확하지만 매 틱 처리·빈 버킷 순회 비용이 커진다. 클수록 싸지만 만료가 다음 틱 경계까지 지연된다. 게임 서버는 흔히 시뮬레이션 틱(예: 50~100ms) 과 타이머 해상도를 맞춘다.
"정시" 가 아니라 "틱 경계": 타임휠 타이머는 정확히 만료 시각이 아니라 그 시각을 포함하는 틱에 실행된다(항상 약간 늦음, 최대 1틱). 그래서 정밀 타이밍(밀리초 판정)이 필요한 로직은 타임휠에 의존하지 말고, 실제 경과 시간을 별도로 재서 보정해야 한다(예: 쿨다운 종료는 타이머로 깨우되 실제 판정은 타임스탬프 비교).
요약: 해상도 = 정확도 × CPU 의 균형. 대부분의 게임 타이머는 낮은 해상도로 충분하고, 정밀 판정은 타임스탬프로 따로 검증한다.

대량 취소: 세션 종료 시 관련 타이머 수백 개를 전부 지워야 한다. 타임휠에서 개별 노드 삭제를 O(1) 로 하려면 타이머를 버킷 리스트의 노드 핸들로 들고 있다가 unlink(양방향 리스트)하거나, **취소 플래그
- 만료 시 무시(지연 삭제)** 로 처리한다. 후자는 취소가 O(1) 이지만 죽은 항목이 만료까지 메모리에 남는다. 세션에 자기 타이머 목록을 달아 두면 일괄 취소가 쉽다(참고: 세션 타이머 수명 관리).
부하 평탄화: 리스폰·일일 초기화처럼 같은 틱에 대량 만료가 몰리면 그 틱이 스파이크가 된다. 만료 시각에 지터(±무작위) 를 주거나, 한 틱에서 처리할 타이머 수에 상한을 두고 초과분을 다음 틱으로 이월해 평탄화한다.
콜백 실행 위치: 타임휠 전진은 보통 틱 스레드가 한다. 콜백이 가볍고 게임 상태를 만지면 틱 스레드에서 직접 실행(락 불필요, 결정적). 콜백이 무겁거나 블로킹 I/O(저장/원격 호출)면 워커 큐로 넘겨 틱 루프가 막히지 않게 한다. 넘길 때 대상 객체 수명(취소된 세션 등) 재확인이 필요.
참고 구현: 넷티 HashedWheelTimer(단일 레벨 해시드 휠), 리눅스 커널 타이머 휠(계층형+캐스케이드), 카프카 지연 연산(계층형 휠 + DelayQueue 로 빈 버킷 건너뜀), 자바 DelayQueue(내부 우선순위 큐).