Hashed and Hierarchical Timing Wheels
이 포스트에는 타이머 구현을 위한 방법들에 대해 간략히 설명하고 각각에 대한 장단점을 제공한다.
Unordered Timer List
정렬되지 않은 타이머 목록을 보관하고 각 타이머의 남은 시간을 추적한다. 시작을 위해서는 새 타이머를 목록에 추가하기만 하면 된다. Per-tick bookkepping(PTK)는 매 틱마다 전체 목록을 확인하며 각 타이머의 남은 시간을 줄여야 한다. 타이머가 0에 도달하면 목록에서 제거되고 만료 처리가 호출된다. 따라서 타이머 시작은 O(1), 중지는 O(1), PTK작업은 O(n)이 된다.
Ordered Timer List
순서 없는 타이머 목록과 같이 목록을 유지하되, 남은 시간이 아닌 절대 만료 시간을 기준으로 동작하며, 이를 기준값으로 정렬된 목록을 유지한다. 매번 확인할 때 마다 타이머의 만료 시간을 현재 시간과 비교하고 만료 시간이 현재 시간인 경우 타이머를 제거하고 만료시킨다. 타이머를 삽입하기 위한 정확한 위치를 검색하고 삽입해야 하므로 O(n)이 걸리지만 PTK는 O(1)이다.
Timer Trees
n이 큰 경우 트리 기반 데이터 구조에 타이머를 유지함으로서 복잡도를 로그적으로 감소시킬 수 있다. 따라서 삽입에 O(logn), PTK는 O(1)이다.
Simple Timing Wheels
Simple timing wheel 접근 방식은 모든 타이머의 기간이 MaxInterval보다 작을 때 적용할 수 있으며 MaxInterval슬롯으로 구성된 원형 버퍼를 통해 만들 수 있다. 현재 시간은 버퍼에 인덱스로 표시되고, 향후 t 시간 이후에 만료되는 타이머를 삽입할 때는 링을 따라 t위치를 이동한 슬롯에 타이머를 추가한다. 매 틱마다 현재 시간 인덱스는 링에서 한 슬롯을 이동하고 새 슬롯에 보관된 모든 타이머에 대한 만료 처리를 수행한다. 시작, 중지 및 PTK는 O(1)이다.
Hashing Wheel with Ordered Timer Lists
MaxInterval이 비교적 큰 경우에 Simple timing wheel은 많은 메모리를 사용하게 된다. 시간 단위당 하나의 슬롯을 사용하는 대신 해싱의 한 형태를 사용할 수 있다. 효율성을 위해 2의 거듭제곱으로 고정된 수의 슬롯을 가진 원형 버퍼를 구성하고 현재 시간 인덱스가 틱에 따라 링에서 한 위치씩 전진하도록 한다. 앞으로 t 시간 뒤에 만료되는 타이머를 삽입하기 위해선 j % bucket의 공식을 사용하면 된다.
PTK는 현재 시간 인덱스를 증가시키고 발견된 타이머 목록에서 타이머를 처리한다. 타이머를 삽입할 때 최악의 대기 시간은 O(n)이지만 대부분의 평균에서는 O(1)이다. PTK는 O(1)이다.
Hashing Wheel with Unordered Timer Lists
이 방식은 앞서 소개한 방식과 유사하지만, 절대적인 만료 시간을 저장하는 대신 각 타이머가 앞으로 링 주위를 몇 바퀴 도는지에 대한 카운터를 저장한다. 카운터는 t / bucket 의 공식을 이용하고 슬롯은 t % bucket 을 통해 구한다. 타이머의 삽입과 중지는 O(1)이지만 PTK는 최악의 경우 O(n)이 된다. 하지만 평균적인 경우 O(1)이다.
Hierarchical Timing Wheels
Simple timing wheel 의 메모리 문제를 해결하는 다른 방법은 계층 구조에서 timing wheel을 사용하는 것이다. 향후 100일 까지 설정할 수 있는 초 단위 timing wheel을 만든다고 가정하자. 그렇다면 우리는 4개의 휠이 필요할 것이다.
- 100개의 날짜 단위용 휠
- 24개의 시간 단위용 휠
- 60개의 분 단위용 휠
- 60개의 초 단위용 휠
총 244개의 슬롯으로 864만개의 타이머 값을 처리할 수 있다. 휠에서 한바퀴를 돌 때 마다 다음 단위 휠이 한 슬롯씩 전진한다. 예를 들어 초 단위용 휠이 슬롯 0에 도달하면 분 단위 휠은 1로 움직여 해당 휠에 있는 정보를 가져와 초단위 휠을 재구성 한다.
Comparison
Hashing Wheel with Unordered Timer Lists이나 Hierarchical Timing Wheels는 모두 매력적인 선택지이다. 두 방식중 어떤 방식이 더 나은지는 매개변수에 따라 달라진다.
- : 타이머 수
- : 사용 가능한 총 슬롯 개수
- : 레벨 수(계층형 모델만을 위함)
- : 평균 타이머 시간
- : 하나의 항목에 대한 해싱 및 인덱스 비용
- : 타이머 항목을 다음 휠로 이동시키는 비용
해싱 방식의 경우는 대략 의 비용이다. 계층 형 구조에서는 가 된다.
