TimingWheel을 이용한 타이머 구현

NHN Business Platform 웹플랫폼개발랩 최동순

애플리케이션을 개발할 때 타이머를 사용해야 하는 일이 자주 있습니다. 특히 세션에 대한 타임아웃 처리를 하는 것과 같은 작업에서 말이지요. 일반적인 타이머의 구현은 타임아웃 작업의 등록이나 만료(expire) 여부의 검사 및 처리 시에 시간 복잡도 O(n)을 가집니다. 하지만, 이 글에서 설명할 TimingWheel 자료구조를 사용하면 타임아웃 작업의 만료 여부에 대한 검사가 필요 없는 등록과 실행의 두 작업만을 모두 O(1)의 시간 복잡도로 처리할 수 있는 타이머를 구현할 수 있습니다.

더 효율적인 타이머에 대한 고민

애플리케이션을 개발할 때 타이머를 사용해야 하는 경우는 흔하게 발생한다. Java로 개발할 때는 JDK에서 제공하는 java.util.Timer 클래스를 사용해 쉽게 타이머를 구현할 수 있다. 그러나 타이머를 매우 빈번하게 사용해야 한다면 java.util.Timer 클래스로는 좋은 성능을 낼 수 없는 경우가 많다. TimerTask 객체를 추가하고 제거할 때 동기화가 발생하기 때문이다.

2010년에 Comet 기반의 통신 서버 개발 프로젝트를 진행하면서 TimingWheel이라는 자료구조를 적용한 적이 있다. 이 TimingWheel은 타이머 구현 방법의 하나로, 경우에 따라 java.util.Timer 클래스보다 훨씬 더 좋은 성능을 낼 수 있다. 하지만 모든 타이머 요구사항에 TimingWheel을 사용할 수 있는 것은 아니다. 이 글에서는 TimingWheel의 제약 사항에 대해서도 간략하게 언급할 것이다.

TimingWheel은 본래 네트워크 프로토콜 레벨에서 데이터 재전송과 프로토콜 리커버리 등을 처리할 때 필요한 타이머를 구현하기 위한 자료구조지만, 응용하기에 따라 다양한 목적으로 사용할 수도 있다.

TimingWheel의 사용을 고려하게 된 계기는, Comet 기반의 통신 서버를 개발하면서 각 세션(커넥션)마다 ping/pong이나 타임아웃처럼 일정한 시간 간격을 두고 실행돼야 하는 작업을 효율적으로 처리하는 방식에 대한 고민이었다. 당시 요구사항에 따르면, 생성할 수 있는 최대 세션의 개수는 1만 개였는데 각 세션에 대하여 ping/pong, 재연결, 세션 만료 등 다양한 종류의 타임아웃을 지체 없이 처리해야 했기 때문에, java.util.Timer 클래스나 Quartz 등으로는 요구사항을 만족할 수 없었다.

그래서 더 나은 타임아웃 처리를 위해 TimingWheel을 적용했다. TimingWheel은 타이머 처리를 O(1) 시간 복잡도로 처리할 수 있는 자료구조다.

TimingWheel의 기본 구조와 용어

TimingWheel의 기본 구조는 <그림 1>에서 보는 것처럼 고정된 크기의 순환 배열(circular array)이다.

그림 1 TimingWheel 기본 구조(참조한 이미지 출처: http://www.transitmagazine.com/lib0071.html)

배열의 각 버킷을 타임슬롯(time slot)이라고 부르는데, 타임아웃이 발생할 때 처리해야 할 작업에 대한 리스트를 담고 있다. TimingWheel의 기본적인 동작 과정은 슬롯 시간 간격(slot interval)마다 타임슬롯을 순회하면서, 해당 타임슬롯에 담긴 내용을 처리하는 방식으로 이뤄진다.

<그림 2>는 슬롯 시간 간격이 50ms인 상황에서 현재로부터 200ms 이후에 발생할 타임아웃 작업(timeout job)이 등록되는 상황을 설명한 그림이다(time interval이 200ms인 타입아웃 작업 등록).

그림 2 타임아웃 작업 등록 과정(참조한 이미지 출처: http://www.transitmagazine.com/lib0071.html)

슬롯 간격 시간이 50ms이기 때문에, 200ms 이후에 발생할 타이머에 대해서는 현재 커서 위치에서 4칸 이후의 슬롯에 타임아웃 작업을 저장하기만 하면 된다. 저장 시에 별도로 정렬(sorting) 등의 작업이 필요하지 않기 때문에 O(1)으로 처리할 수 있다.

다음으로 등록된 타이머가 만료되어 타임아웃 작업이 처리되는 과정을 살펴보자.

TimingWheel은 50ms마다 슬롯을 순회하기 때문에, 현재 시각 기준으로 200ms 이후에 커서는 자연스럽게 네 칸 뒤의 타임슬롯으로 이동하게 된다. 커서가 이동한 타임슬롯에 저장되어 있는 타임아웃 작업들은 각 작업의 시간 간격(time interval)은 다를지 모르지만 모두 지금 만료되는 작업들이 된다. 즉, 타임슬롯이 가지고 있는 리스트의 타임아웃 작업을 처리하는 로직에서는 타이머 만료 여부에 대한 추가적인 검사 없이 단순히 타임아웃 작업들을 실행시키면 되기 때문에 타임아웃 작업을 저장할 때와 마찬가지로 O(1)이라는 시간 복잡도 안에 처리할 수 있다. 단순한 아이디어지만 타임아웃 작업의 등록 및 실행 시에 만료 여부를 확인하는 로직이 필요 없기 때문에 O(1)이라는 시간 복잡도로 처리할 수 있는 것이다.

타임아웃 작업을 저장할 타임슬롯(targetSlot)은 <예제 1>과 같은 계산 방식으로 얻을 수 있다. 순환 배열이기 때문에 모듈러(%) 연산자가 사용되었고 <그림 2>처럼 최대 타이머 시간(max interval)의 제약 사항이 생기게 된다. TimingWheel을 적용한 프로젝트를 진행할 때도 <예제 1>과 같은 방식으로 TimingWheel을 구현했다.

예제 1 targetSlot 계산 방식

targetSlot = ( currentSlot + (timeInterval / slotInterval)) % timeSlotCount 

<그림 3>은 순환 배열을 좀더 직관적으로 표현한 것이다. 실제 프로젝트에서 TimingWheel을 구현할 때는 타임아웃 작업 처리에 소요되는 시간이 TimingWheel의 커서(cursor) 동작에 끼치는 영향을 최소화하기 위해 타임아웃 작업을 처리하는 스레드는 별도의 스레드 풀에서 동작할 수 있도록 했다.

그림 3 Simple TimingWheel의 동작 방식

하지만 타이머가 필요한 모든 경우에 TimingWheel을 사용할 수 있는 것은 아니다. <그림 2>에서 보는 것처럼 TimingWheel에는 최대 타이머 시간에 대한 제한이 있다. <그림 2> 처럼 타임슬롯의 개수가 7개고, 주기가 50ms일 때는 350ms를 넘어서는 값을 등록할 수 없다.

만약 슬롯 시간 간격이 1초일 때는, 1시간 23분 15초 주기의 시간 간격을 오버플로(overflow) 없이 처리하려면 4,995개(60×60 + 23×60 + 15)의 타임슬롯이 필요해 많은 메모리를 사용하게 된다. 이 부분에 대해서 좀 더 정확히 말하면 슬롯 시간 간격이 작을수록 정밀한 처리가 가능하고 타임슬롯의 개수가 클수록 큰 주기의 작업을 처리할 수 있게 되는데, 이 두 경우를 하나의 TimingWheel에서 처리하면 메모리 낭비가 심해진다는 말이다. 만약 O(1)의 시간 복잡도가 중요한 요소이고 앞의 두 경우를 모두 만족해야 하는 경우에는 슬롯 시간 간격과 주기에 따라 여러 개의 TimingWheel을 사용하면 될 것이다. O(1) 시간 복잡도가 그리 중요한 요소가 아니고 여러 개의 TimingWheel을 유지하는 것이 번거롭다면 Hashed TimingWheel이나 Hierarchical TimingWheel의 사용을 고려해 볼 수도 있다. 그러나 모든 타이머 요구사항에 TimingWheel을 사용할 수 있는 것은 아니므로, 적합한지 여부를 판단한 후 TimingWheel을 구현하는 것이 좋을 것이다.

TimingWheel 적용 효과

2010년 진행한 Comet 프로젝트 이외에도 구현한 TimingWheel을 다른 프로젝트에 적용해 본 경험이 두 번 있다.

첫 번째로, 타임아웃 작업의 처리 로직이 O(n) 시간 복잡도를 가지고 있어서, 평상시에는 CPU 사용률이 1~2%이지만 타임아웃 작업을 처리할 때에는 CPU 사용률이 100%에 이르는 문제가 있던 프로젝트에 적용했다. 처음 방식은 매번 타임아웃 검사 시마다 등록된 타임아웃 작업 전체에 대해서 만료 여부를 검사하고 만료된 것들만 실행시키는 방식이었다. 그래서 한 번에 검사 및 처리해야 하는 타임아웃 작업이 너무 많아 높은 CPU 사용률이 발생했다. TimingWheel을 적용함으로써 타임아웃 작업들이 타임슬롯 전체에 고르게 분산되어 타임아웃 작업의 처리 시에도 안정적인 CPU 사용률을 보일수 있었다.

두 번째로, HTML5 기반 게임 개발에도 적용한 사례가 있다. 브라우저의 JavaScript는 싱글 스레드 기반에서 동작하기 때문에 HTML5 게임 개발 시에 타이머를 너무 많이 사용하면 서로 영향을 주어 시간 지연이 발생되게 되고 전체적인 게임 렌더링 성능이 떨어지게 된다. 또한 게임 개발 시에 사용하는 HTML5 게임 엔진들은 <그림 4>처럼 프레임(frame) 기반으로 동작하는 방식을 제공하는데, 이런 방식을 애니메이션 효과 이외의 부분에서 타이머의 용도로 사용하면 필요 이상의 리소스를 사용하게 되어 역시 게임 렌더링 성능이 떨어지게 된다(<그림 4> 참고).

그림 4 HTML5 게임 엔진의 frame 처리 방식

<그림 5>의 C처럼 1분 주기로 동작하는 타이머의 경우, OnAction을 사용하면 3,599번의 불필요한 호출이 일어난다.

그림 5 불필요한 리소스 낭비의 예

이런 문제점을 해결하기 위해서 TimingWheel을 적용했다. 단 한 개의 TimingWheel 타이머만으로도 요구사항을 충분히 만족시킬 수 있었으며, 전체적으로 일정하게 안정된 프레임 수(fps)를 유지할 수 있었다.

마치며

지금까지 TimingWheel을 활용한 타임아웃 작업의 등록과 처리 과정에 대해서 간단히 살펴보았다.

간단한 아이디어로 타이머의 만료 여부를 확인할 필요가 없기 때문에 타임아웃 작업의 등록과 처리를 O(1)에 처리할 수 있는 장점이 있었고, 경우에 따라 메모리가 많이 낭비되는 단점도 있었다.

실제 서비스에 적용하는 과정에서는 좀 더 세밀한 부분에 대한 고민이 필요하다. 타임슬롯이 가지고 있는 리스트라는 자료 구조의 특성상 메모리릭(memory leak)이 발생할 가능성이라든지, 등록되는 작업의 처리에 시간이 오래 걸리는 경우는 지연 시의 대책에 대한 고민도 필요하다.

스로틀 밸브(Throttle valve) 성격의 옵션을 잘 활용하여 위의 문제점들을 해결한다면 요즘과 같은 대용량 처리가 필요한 환경에서 TimingWheel은 좋은 선택일 것이다.

참고 자료

• Implement lower timer granularity for retransmission of TCP: http://www.ibm.com/developerworks/aix/library/au-lowertime/index.html
• Hashed and hierarchical timing wheels: efficient data structures for implementing a timer facility: http://dl.acm.org/citation.cfm?id=270876
• Hashed and Hierarchical Timing Wheels: http://ebookbrowse.com/timingwheels-ppt-d195376642
• Real-Time Concepts for Embedded Systems – 11.4 Timer Interrupt Service Routines: http://www.transitmagazine.com/lib0069.html