타이밍 휠은 대량의 타이머를 O(1)로 삽입·삭제·만료 처리하기 위한 자료구조다. 원형 버퍼(circular buffer) 형태의 슬롯 배열을 시계처럼 회전시키며, cursor가 도달한 슬롯의 타이머를 일괄 만료 처리한다.
핵심 아이디어는 단순하다:
(현재 cursor + delay/tick) % slotCount 위치에 삽입이로써 **삽입 O(1), 삭제 O(1), tick당 처리 O(만료 수)**를 달성한다.
Varghese의 논문은 7가지 타이머 구현 방식(Scheme 1~7)을 체계적으로 비교했다.
| 방식 | Start Timer | Stop Timer | Per-Tick | 비고 |
|---|---|---|---|---|
| Scheme 1: 비정렬 리스트 | O(1) | O(1) | O(n) | 매 tick마다 전체 스캔 |
| Scheme 2: 정렬 리스트 | O(n) | O(1) | O(1) | 삽입 시 정렬 위치 탐색 |
| Scheme 3: 트리 기반 (Tree-based) | O(log n) | O(log n) | O(1) | 트리 구조로 삽입 개선 |
| Scheme 4: 기본 타이밍 휠 (Basic Timing Wheel) | O(1) | O(1) | O(1) | 슬롯 수 = 최대 interval |
| Scheme 5: 해시 휠 + 정렬 리스트 | O(n) worst / O(1) avg | O(1) | O(1) | 슬롯 축소, 정렬 리스트로 충돌 해소 |
| Scheme 6: 해시 휠 + 비정렬 리스트 | O(1) | O(1) | O(n) worst / O(1) avg | 삽입 O(1)이나 tick 시 순회 필요 |
| Scheme 7: 계층 타이밍 휠 | O(1) | O(1) | O(1) amortized | 다단계 휠로 범위 확장 |
핵심 인사이트: 트리 기반(Scheme 3)은 범용적이지만, 수만~수십만 타이머 환경에서는 O(log n) 삽입/삭제가 병목이 된다. 타이밍 휠(Scheme 4~7)은 이 비용을 O(1)로 줄인다.
슬롯 배열: [0] [1] [2] ... [N-1] (원형 버퍼)
↑ cursor
각 슬롯: sentinel ↔ Timer A ↔ Timer B ↔ sentinel (이중 연결 리스트)
slot = (cursor + delay) % N에 노드 삽입 → O(1)