수십만 개 타이머를 관리할 때 최소 힙과 타이밍 휠을 정밀도·취소·만료 집중으로 어떻게 비교하나요?

정밀한 만료 순서와 다양한 시간 간격이 중요하면 최소 힙을, 수십만 개 타이머가 비슷한 시간 해상도에서 몰리고 약간의 오차를 허용하면 타이밍 휠을 우선 검토하겠습니다. 힙은 가장 이른 시각을 루트에서 얻고 삽입·삭제를 보통 O(log n)에 처리합니다. 휠은 시간을 버킷에 배치하고 시계 바늘을 이동해 만료를 처리하므로 관리 비용을 낮출 수 있지만 해상도·회전·긴 타이머 규칙이 필요합니다.

만료 감지와 실행을 분리합니다

최소 힙은 만료 시각이 서로 멀거나 밀리초 단위 순서가 중요할 때 유연합니다. 취소된 타이머를 힙에서 즉시 제거하면 위치 찾기 비용이 필요하고, 지연 삭제하면 만료 때 취소 상태를 확인하면서 죽은 항목이 쌓일 수 있습니다. 타이밍 휠은 한 칸이 10ms라면 같은 버킷의 타이머를 그 해상도 안에서 처리할 수 있습니다. 긴 만료는 다음 회전으로 넘기거나 상위 계층 휠에 보관해야 합니다. 이를 시간 버킷 기반 스케줄링(time-bucket scheduling)이라고 부릅니다.

세션 만료처럼 수 밀리초 오차가 허용되고 등록률이 높은 작업은 휠이 유리할 수 있습니다. 반대로 정확한 재전송 deadline, 짧은 타임아웃, 넓은 만료 범위는 힙이나 계층형 휠을 비교합니다. 시간 자료는 벽시계가 조정될 수 있으므로 경과 시간에는 단조 시계를 사용하고, 프로세스가 오래 멈춘 뒤 돌아왔을 때 만료를 모두 즉시 실행할지 일부 합칠지 정합니다.

만료 감지와 콜백 실행을 분리합니다

자료구조가 만료 항목을 빠르게 찾아도 같은 시각에 수십만 콜백을 실행하면 이벤트 루프가 막힙니다. 만료 큐에 넣고 tick별 실행 예산이나 별도 워커로 나눌지, 작업 큐 상한과 부하 시 지연 정책을 둘지 결정하겠습니다. 취소 플래그를 읽고 곧바로 콜백을 호출하면 확인과 실행 사이에 취소가 끼어 취소 성공 뒤에도 콜백이 실행되는 경쟁이 생길 수 있습니다. Pending에서 Cancelled 또는 Running으로 한 번만 CAS 전이하고, Running을 얻은 쪽만 콜백을 실행하는 실행권 경쟁(claiming execution right)으로 계약을 만들겠습니다.

검증은 등록·취소 경합, 동일 시각 집중, 긴 타이머, 시간 점프, 중단 후 복귀, 콜백 중복을 포함합니다. 측정값은 등록·취소 비용뿐 아니라 만료 폭주 시 p99, 콜백 대기, 메모리, 늦은 타이머의 허용 오차입니다.

타이밍 휠의 한 칸이 10ms라면 같은 버킷의 타이머를 그 해상도 안에서 처리하므로, 일찍 실행할지 늦게 실행할지 정책을 정해야 합니다. 긴 타이머는 남은 회전 수나 상위 계층에 보관하지 않으면 현재 회전의 항목과 섞입니다. 힙은 가장 이른 시각을 정확히 비교하고 보통 삽입·삭제가 O(log n)이지만, 힙 배열 자체의 확장에서는 O(n) 복사가 발생할 수 있습니다.

취소 플래그를 읽은 뒤 콜백을 호출하는 사이에 취소가 완료될 수 있으므로, CAS로 Pending에서 Cancelled 또는 Running 중 하나의 실행권을 경쟁시키겠습니다. 취소가 Pending에서 성공하면 실행하지 않지만, 이미 Running이 된 콜백은 취소 뒤에도 실행될 수 있습니다. 이 경쟁을 넣었다고 콜백의 중복 실행이 자동으로 해결되는 것은 아니므로 타이머 ID·세대와 실행 상태를 함께 확인하겠습니다. 권한 만료나 세션 만료에서는 타이머 청소가 늦어도 요청 시각의 권한 검사를 별도로 수행해야 합니다.

10ms 해상도의 휠에서 조기 실행을 금지하면 deadline을 다음 경계로 올림해 배치하거나 버킷을 꺼낸 뒤 실제 시각을 다시 비교해야 합니다. 정상 구동 시 양자화 지연이 한 슬롯 미만일 수 있어도 OS 스케줄링과 콜백 큐 지연은 그보다 길 수 있습니다. 타이머 자료구조의 해상도를 콜백 실행의 절대 지연 상한으로 말하지 않겠습니다.