문제 17 — 대규모 타이머 스케줄링: 타임휠(Timing Wheel)과 지연 작업 큐

MMORPG 서버 한 대는 수십만~수백만 개의 "미래에 일어날 일" 을 동시에 관리한다: 버프/디버프 만료, 스킬 쿨다운, 몬스터 리스폰, 세션 유휴 타임아웃, 재전송 타이머, 지연 저장, 예약 이벤트 등. 이들을 효율적으로 스케줄링하지 못하면 틱 루프가 타이머 관리에만 시간을 쓴다. 다음을 설명하라.

1. 소박한 방법의 한계: (a) 타이머마다 스레드/sleep, (b) 정렬된 리스트, (c) 최소 힙(우선순위 큐) 각각으로 "가장 임박한 타이머 실행 + 삽입/취소" 를 구현할 때의 시간복잡도와 대규모(수백만 개)에서의 문제를 설명하라.

2. 타임휠(timing wheel): 단일 레벨 타임휠의 구조(버킷 배열, 틱 간격, 커서)와 삽입·만료의 복잡도를 설명하라. 왜 삽입/만료가 (평균) O(1) 이 되는가?

3. 계층형 타임휠(hierarchical): 단일 레벨의 한계(표현 가능한 최대 지연 vs 버킷 수의 트레이드오프)를 설명하고, 시/분/초처럼 여러 레벨을 쌓는 계층형 타임휠과 "캐스케이드(cascade)" 가 무엇인지 설명하라.

4. 정확도 vs 비용: 틱 간격(해상도)을 정하는 기준, 타이머 정확도와 CPU 오버헤드의 트레이드오프, 그리고 타이머가 실제로 "정시" 가 아니라 "틱 경계" 에 실행된다는 점의 함의를 설명하라.

5. 실무 이슈: 대량 타이머의 취소(예: 세션이 끊겨 관련 타이머 전부 무효화), 동시 다발 만료가 한 틱에 몰릴 때의 부하 평탄화, 그리고 타이머 콜백을 틱 스레드에서 직접 실행할지 워커로 넘길지의 고려사항을 논하라. (참고: 자바 DelayQueue, 넷티 HashedWheelTimer, 카프카/리눅스 커널 타이머 휠.)