Apache Kafka, Purgatory, and Hierarchical Timing Wheels

해당 포스트는 아래 링크의 원문을 바탕으로 번역 및 요약한 내용입니다.
https://www.confluent.io/blog/apache-kafka-purgatory-hierarchical-timing-wheels/

• 카프카는 "request purgatory" 라는 이름의 구조체를 가지고 있음
  • purgatory는 아직 성공하지도, 실패하지도 않은 요청을 유지(hold)함

• The problem is..

  How can we efficiently keep track of tens of thousands of requests that are being asynchronously satisfied by other activity in the cluster?

• 카프카는 다음의 예와 같은 즉시 응답을 하지 못하는 몇 가지의 요청 유형을 구현함

  • 프로듀서가 acks=all 설정으로 요청 시 모든 ISR이 쓰여졌다고 응답하기 전까지는 완료가 되지 않음
  • min.bytes=1 의 읽기 요청에 대해선 새로운 데이터가 1바이트 생기기 전까지는 응답을 하지 않음. 이를 통해 컨슈머는 새 데이터가 도착할 때까지 괜히 바빠지지 않도록 "긴 폴링(long poll)"을 허용함
• 이러한 요청은 요청한 기준이 완료되거나 timeout이 발생했을 때 완료된 것으로 간주함
• 이런 비동기 요청 작업의 수는 연결 수에 따라 확장될 수 있고 카프카의 경우 수만 개가 되는 경우도 있음
• 퍼커토리는 이러한 대규모 요청 처리를 위해 설계되었는데, 이전 구현에는 여러 가지 결함이 존재하였음

Old Purgatory Design

• 요청 퍼거토리(The request purgatory)는 타임아웃 타이머와 이벤트 기반 처리를 위한 watcher 목록을 관리하는 해시 맵으로 구성됨
• 즉시 응답할 수 없는 요청은 퍼거토리에 들어가며, 이러한 요청은 요청 작업이 모두 수행되거나, 타임아웃이 발생했을 때 완료 처리 됨
  • 이전 구현(old design)에서는 자바의 DelayQueue를 활용하여 구현되었음

• 요청이 완료되면 타이머나 watcher 목록에서 해당 요청이 즉시 삭제되지는 않고, 대신에 요청에 대한 조건 확인하는 과정에서 완료된 요청은 삭제됨

  Instead, completed requests are deleted as they were found during condition checking.

• 퍼거토리 안에 있는 요청들이 삭제되지 않으면, 서버는 JVM heap 메모리를 소진하게 되고 결국 OutOfMemeryError 가 발생됨

• 이러한 상황을 줄이기 위해 reaper라는 이름의 별도 스레드가 동작하면서 퍼거토리 내 존재하는 (완료되었거나 보류 중인) 요청의 수가 임의의 설정된 수를 초과할 때 완료된 요청을 제거함
  • 제거 작업(the purge operation)은 완료된 요청을 찾기 위해 타이머 큐와 watcher의 전체 목록을 검색함
• 이 설정 값(퍼거토리 내 존재할 수 있는 요청 수)을 작게 설정하면 메모리 문제를 피할 수는 있겠지만, 반면에, 너무 잦은 메모리 검색으로 성능 저하를 일으킬 수 있음

New Purgatory Design

• 퍼거토리의 새로운 디자인의 목표는 완료된 요청을 즉시 삭제하고, 비용이 많이 드는 제거 프로세스의 부하를 크게 줄이는 것으로 다음과 같은 요구 사항이 존재함
  • 타이머와 요청의 엔트리들은 상호 참조해야 함
  • 각 요청/완료 작업 마다 삽입/삭제 동작이 발생하므로 삽입/삭제 동작의 비용이 O(1)이 되는 것이 좋음
• 위 요구 사항을 만족하기 위해 새로운 퍼거토리는 Hierarchical Timing Wheels를 기반으로 디자인 됨

Hierarchical Timing Wheel

• 심플 타이밍 휠은 타이머 태스크 버킷의 circular list 임
  • 참고(https://d2.naver.com/helloworld/267396)
• u를 타임 유닛이라고 가정, 타이밍 휠 사이즈가 n(n개의 버킷을 가짐)이라고 하면, 타이머 태스크들은 n * u만큼의 전체 타임 인터벌을 가질 수 있음.
• 각 버킷에는 해당 시간 범위에 속하는 타이머 작업이 포함됨
  • 첫 번째 버킷은 [0, u)에 대한 작업을 가지며, 두 번째 버킷은 [u, 2u)에 대한 작업을 가지며.. n번째 버킷은 [u * (n-1), u * n) 에 대한 작업을 가짐
• 타임 유닛 u 간격마다 타이머는 다음 버킷으로 이동하고, 해당하는 버킷 내에 존재하는 모든 타이머 작업을 만료 처리함

• 타이머는 현재 가리키고 있는 버킷은 만료된 버킷이기 때문에, 이 버킷으로 태스크 삽입 작업은 절대 하지 않음.
• 모두 비워진 버킷은 다음 라운드(next round)에서 사용될 수 있음
  • 예를 들어, 현재 버킷이 시간 t 에 대한 것이라면, [t+u*n, t+(n+1)*u) 에 대한 버킷이 됨
• 타이밍 휠은 삽입/삭제 작업에 O(1) 복잡도를 가짐
  • 우선 순위 큐에 기반한 java.util.concurrent.DelayQueue와 java.util.Time은 O(logn) 복잡도를 가짐
• 심플 타이밍 휠의 주요 단점은 타이머 요청이 현재 시간으로부터 n * u의 시간 간격 내에 있다고 가정하는 것
  • 다른 말로 하자면, 타임아웃의 크기를 n * u미만으로만 설정할 수 있음
• 계층적 타이밍 휠(hierarchical timing wheel)은 이러한 단점을 보완한 방법으로 타임 overflow를 상위 레벨의 휠로 넘기는 방식
• 가장 낮은 단계의 휠이 가장 촘촘한 시간 간격(time resolution)을 처리하고, 단계가 올라갈 수록 시간 간격은 커짐
  • 1단계의 타임 유닛이 u 라고 하면, 2단계의 타임 유닛은 n * u 이고, 3단계의 타임 유닛은 n^2 * u
  • 상위 단계의 휠은 overflow가 발생할 때 on-demand 로 생성함
• 상위 단계 휠에서 tick이 발생하면(해당 휠에서의 타임 유닛만큼의 시간이 지나 다음 버킷으로 포인터가 이동할 때) 해당 버킷에 있는 타이머 태스크를 하위 단계의 휠으로 이동시킴
  • 타이머 태스크는 바로 처리되거나(아래 그림 Time: 8에서 8번 작업) 하위 휠로 재삽입 됨

* 계층적 타이밍 휠에서... * 삽입(insert) 비용은 O(m) (여기서 m은 휠의 갯수(단계의 수)) * 삭제 비용은 여전히 O(1)

Doubly Linked List for Buckets in Timing Wheels

• 새로운 퍼거토리 디자인에서는 타이밍 버킷을 위해 자체 개발한 이중 연결 리스트를 사용함
• 이 이중 연결리스트의 장점은 access link cells을 알고 있는 경우 O(1)의 비용으로 목록 아이템의 삽입/삭제 가능
• 타이머 태스크 인스턴스는 타이머 큐에 삽입(enqueue)될 때 자신의 link cell을 저장함
  • 태스크가 완료되거나 취소될 때 해당 link cell을 이용하여 목록을 업데이트 함

Driving Clock using DelayQueue

• Java DelayQueue
• 간단히 구현하자면, 매 단위 시간마다 버킷에 태스크가 있는지 확인하는 작업을 수행하는 스레드를 활용할 수 있음
  • 퍼거토리의 단위 시간(unit time)은 1ms이고, 이는 가장 낮은 수준의 요청이 많지 않은 경우엔 리소스의 낭비로 이어짐
  • 일반적으로 대부분의 요청들은 낮은 수준의 휠에 삽입되기 전에 완료되기 때문에 합리적인 고민임.
• 만료되어야 할 버킷에 태스크가 있는 경우에만 쓰레드가 깨어나 작업을 수행하는게 이상적임
• 새로운 퍼거토리에서도 기존처럼 java.util.concurrent.DelayQueue를 사용함
  • 기존에는 개별 태스크를 큐에 넣었다면, 새로운 디자인에서는 버킷 단위로 큐에 집어 넣기 때문에 성능 측면에서 이점을 가짐
  • 큐에 들어가는 항목의 갯수가 휠의 버킷 수와 같으므로 개별 태스크의 갯수보다 훨씬 적고, 이는 큐의 필요한 작업 수(offer/poll operations)가 훨씬 적어진다는 것을 의미

Purging Watcher Lists

• 이전 구현에서는 와처 목록에서의 제거 작업(purge operation)이 와처 목록의 전체 크기에 의해 트리거됨
  • 이러한 경우 문제는 purge 작업이 많지 않은 경우에도 와처 목록의 threshold가 초과할 수 있고, 이는 CPU의 로드를 키움
• purge 작업은 와처 목록의 성공한 요청(completed request) 수에 의해 트리거되는 것이 이상적임
• 새로운 디자인에서 성공한 요청은 O(1)의 비용으로 타이머 큐에서 바로 삭제됨
  • 결국, 이는 타이머 큐에 존재하는 요청의 수가 곧 대기중인 요청(pending request) 수임
• 따라서, 대기 중인 요청 수와 완료된 요청 수의 합을 포함하는 퍼거토리에 존재하는 전체 요청 수를 알면 불필요한 purge 작업을 피할 수 있음
• 요청이 발견(watch)될 수도 있고, 그렇지 않을 수도 있기 때문에 퍼거토리에 있는 정확한 요청 수를 추적하는 것은 쉬지 않음
• 새로운 디자인에서는 정확한 숫자를 유지하려고 하기 보다 퍼거토리의 전체 요청 수를 추정하려고 함
• 예상 요청 수는 다음과 같이 유지됨
  1. 추정 전체 요청 수는 E라고 하고, 이는 새로운 요청이 발견(watched)될 때마다 1씩 증가함
  2. purge 작업 전에 E를 타이머 큐의 사이즈로 초기화 함.
     • 이는 현재 대기중인 요청 수를 의미
     • purge 작업 중에 새로운 요청이 추가되지 않으면 E는 purge 작업 완료 후 와처 목록의 수가 올바른(correct) 수일 것임
  3. purge 작업 중 새로운 요청이 발견된다면, E 는 E + 새로 발견된 요청 수로 증가되는데, 이는 실제보다 과하게 측정된 숫자일 수 있음.
     • 새 요청 중 일부는 purge 작업 중에 완료 처리가 되어 와처 목록에서 삭제될 수 있기 때문
     • 하지만, 과대평가될 가능성과 그 정도(amount of overestimation)는 작을 것으로 예상함

Benchmark

• 기존 퍼거토리 구현과 신규 퍼거토리 구현에 대한 성능 비교 수행
  • 오직 enqueue에 대한 성능만 측정
  • 다른 나머지 시스템들과는 분리를 시키고, 가상의 요청(fake request)에 대해 처리하도록 구성
  • 실제 시스템에서의 처리량보다 테스트에서의 처리량이 높을거임
• 테스트 조건
  • tick size = 1ms, wheel size = 20
  • timeout 설정은 200ms
  • 요청의 데이터 사이즈는 100bytes
  • low timeout rate 에서의 75 백분위(percentile) = 60ms, 50 백분위 = 20ms
  • high timeout rate 에서의 75 백분위 = 400ms, 50 백분위 = 200ms
  • 전체 요청 수는 100만건
  • JVM 힙 사이즈는 200메가 - 메모리가 부족한 상황을 연출하기 위함
• Enqueue Performance
  • 드라마틱한 차이점을 보인건 enqueue 비율(enqueue rate)이 높은 구간에서 나타남
  • target rate가 증가함에 따라 초기엔 두 구현 모두 처리율이 올라감
  • low timeout 시나리오에서는
    • 기존 구현의 경우 40000 RPS(request per second)로 수렴
    • 새 구현의 경우 심각한 성능 저하를 보이지 않음
  • high timeout 시나리오에서는
    • 기존 구현의 경우 25000 RPS로 수렴
    • 새 구현의 경우 105000 RPS로 수렴
  • CPU 사용에 있어서도 신규 구현이 훨씬 좋은 성능을 보여주었음
    • 기존 구현의 경우 40000 RPS보다 높은 포인트가 없는 반면 신규 구현은 RPS 가 꾸준히 올라가는 동안 CPU time 은 1.2로 수렴하였음
• GC time 측정
  • ParNew와 CMS에 대해 측정
  • 이전 구현에서 보여준 처리 영역대에서는 두 구현 모두 비슷한 GC Time 을 보여줌

Summary

• 새로운 퍼거토리 디자인에서는 타임아웃 타임을 위해 계층적 타이밍 휠을 사용하였으며, 타이머 버킷을 위해 DelayQueue를 활용하였음
• 완료된 요청은 타이머 큐에서 O(1)의 비용으로 즉시 삭제됨
• 버킷은 delay queue 에 존재하지만 그 수는 이전 버전에 비해 훨씬 적은 수로 제한됨
• 정상적인 시스템에서는 대부분의 요청이 타임아웃이 발생하기 전에 완료되고, 많은 버킷들은 delay queuq에서 빠져나오기 전에 이미 비어있는 상태가 됨
• 따라서, 낮은 interval 의 타이머 휠에는 버킷이 거의 없어야 함.
• 새로운 디자인의 장점은 어느 시점에서의 대기 요청 수는 타이머 큐에 존재하는 요청 수와 같다는 것임
  • 이를 통해 제거해야 하는 요청 수를 추정할 수 있고, 와처 목록의 불필요한 제거 작업을 피할 수 있음
• 결과적으로 훨씬 더 나은 CPU 사용량으로 더 많은 요청을 처리할 수 있었음

참고 아티클

• Kafka purgatory
• Kafka purgatory2
• Apache Kafka and it's Request Purgatory