목차
Cinnamon의 거절 비율을 안정시킨 PID 컨트롤러 (2023-11)
원문 정보
- 원문: PID Controller for Cinnamon
- 매체 · 게시일: Uber Engineering Blog · 2023-11-30
- 저자: Jakob Holdgaard Thomsen(Principal Engineer), Vladimir Gavrilenko(Software Engineer, Inventory and Catalog), Jesper Lindstrom Nielsen(Staff Engineer, Inventory and Catalog), Timothy Smyth(Staff Engineer, Delivery Backend Platform)
- 원문 내용을 바탕으로 재구성한 요약입니다. Cinnamon 로드 셰더 시리즈의 두 번째 글입니다.
거절 비율과 함께 출렁이는 지연
과부하가 왔다고 요청을 거절하는 것만으로는 부족합니다. 거절 비율이 크게 오르내리면 지연도 출렁입니다. 시리즈 1편에서 전체 구성을 소개한 Cinnamon에서, 얼마나 많은 요청을 거절할지 정하는 장치가 거절기(rejector)입니다. Uber 팀은 AIMD와 CoDel로 얻지 못했던 안정적인 거절 비율을 PID 컨트롤러로 빠르게 찾았습니다.
어려운 부분은 여러 서비스에 그대로 쓸 목표 함수를 만드는 일이었습니다. 인스턴스 하나가 초당 수천 요청을 처리하는 서비스도 있고, 초당 10 요청 정도를 받는 서비스도 있습니다. 마이크로서비스가 너무 많아 각각 설정을 맞추기는 어려웠습니다. 거절기는 서비스마다 다른 트래픽 패턴을 따라가야 했고, 모든 요청이 거치는 만큼 추가 지연과 자원 사용도 작아야 했습니다.
PID는 피드백을 받아 계산한 오차를 0으로 줄여 가는 제어 루프입니다. 발상은 300년이 넘었고 수식은 1922년에 정리됐습니다. 오븐 온도부터 선박 조타까지 쓰이는 이 오래된 제어 방식을 Cinnamon의 거절 비율에 적용하려면, 먼저 요청 처리 상태를 어떤 오차로 표현할지 정해야 했습니다.
80km/h에서도 필요한 엔진의 힘
자동차의 크루즈 컨트롤을 떠올리면 PID의 동작을 이해하기 쉽습니다. 20km/h에서 80km/h로 속도를 올릴 때는 70km/h에서 출발할 때보다 엔진에 더 큰 힘을 줘야 합니다. 오르막과 내리막에서도 필요한 힘은 달라집니다. 목표 속도와 현재 속도의 차이가 비례 항 P이며, 차이가 클수록 P도 커집니다.
80km/h에 도달하면 P는 0입니다. 그렇다고 엔진에 주는 힘까지 없애면 속도를 유지하지 못합니다. 과거 P 값의 합인 적분 항 I가 이때도 남아 있어, 목표 속도에 도달한 뒤에도 필요한 힘을 계속 줍니다.
미분 항 D는 P의 변화율로 진동을 줄이지만, Cinnamon에서는 도움이 되지 않았습니다. PID 출력은 P, I, D에 각각 가중치 Kp, Ki, Kd를 곱한 값의 합입니다. Cinnamon에서는 요청 처리 상태로 오차를 계산하고, PID가 내놓은 거절 비율에 따라 요청을 거절합니다. 그 결과 바뀐 처리 상태가 다시 PID의 입력으로 돌아옵니다.
남는 처리 자리까지 세는 목표 함수
큐를 짧게 만드는 일 자체는 쉽습니다. 요청을 거의 다 거절하면 됩니다. 하지만 그러면 서비스가 처리할 수 있는 양까지 버립니다. Cinnamon이 원하는 상태는 대기 큐가 짧으면서도 실행 중인 요청 수가 인플라이트 제한에 차 있는 상태입니다. 큐 대기 시간을 줄이되 서비스의 처리 여력을 충분히 써야 합니다.
서비스 활용도는 거절이 지나칠 때 이를 되돌리는 신호가 됩니다. 크루즈 컨트롤이 힘을 너무 줘 목표 속도를 넘기면 초과한 속도가 가속을 줄이는 신호로 돌아오는 것과 같습니다. 인플라이트 제한은 실행 중인 요청 수의 상한이며, 이 값을 추정하는 일은 Auto-tuner가 담당합니다. PID는 주어진 제한 안에서 거절 비율을 조절합니다.
계산에는 보정 주기 t 동안 큐로 들어온 요청 수 in(t)와 큐에서 나가 서비스 코드로 넘어간 요청 수 out(t)를 씁니다. 보정 주기는 예를 들어 500ms입니다. in(t)에는 거절기가 받아들인 요청만 들어가고, 거절한 요청은 포함되지 않습니다. out(t)도 처리가 끝난 요청 수가 아니라 처리를 시작하도록 큐를 빠져나간 요청 수입니다.
처음에는 in(t) - out(t)만 봤습니다. 값이 양수면 들어오는 요청이 더 많아 큐가 자라므로 더 거절합니다. 음수면 큐가 비워지고 있으니 거절이 과할 가능성이 있습니다. 방향은 맞지만, 이 식만으로는 서비스가 얼마나 바쁜지 알 수 없습니다. 들어온 요청과 나간 요청이 모두 5라면 오차는 0입니다. 그런데 인플라이트 제한이 5인데 실행 중인 요청이 계속 1개뿐이라면 처리 여력이 놀고 있습니다.
그래서 남은 처리 자리도 셉니다. freeInflight(t)는 인플라이트 제한에서 현재 실행 중인 요청 수를 뺀 값입니다. 이를 앞의 차이에서 한 번 더 빼면, in(t)와 out(t)가 같아도 빈자리가 있을 때 오차가 음수가 되어 거절을 줄입니다. 들어오는 양과 나가는 양이 같고 빈자리도 없을 때가 서비스의 처리 여력을 채운 균형 상태입니다.
아직 서비스 사이의 규모 차이가 남습니다. 초당 1,000 요청을 처리하는 인스턴스에서 요청 1개의 차이는 초당 1 요청을 처리하는 인스턴스에서만큼 큰 문제가 아닙니다. 같은 차이에 같은 거절 비율로 반응하지 않도록, 앞에서 구한 값을 out(t)로 나눠 정규화했습니다.
최종 목표 함수는 P(t) = (in(t) - out(t) - freeInflight(t)) / out'(t)입니다. 여기서 out'(t)는 보통 out(t)와 같지만, 해당 주기에 큐에서 서비스로 넘어간 요청이 하나도 없으면 인플라이트 제한 값을 대신 씁니다.
큐에서 타임아웃이 난 요청을 별도로 식에 넣지는 않습니다. 그 영향은 들어온 요청과 서비스로 넘어간 요청의 차이에 이미 반영됩니다. 또 in(t)가 out(t)보다 큰데 빈자리도 있어 P가 0이 되는 경우가 있습니다. 이 경우에도 문제는 없습니다. 남은 자리로 대기 요청이 곧 들어가므로 다음 보정 주기에는 freeInflight(t)가 0이 됩니다.
요청 경로 밖의 500ms 보정 루프
이 계산을 요청마다 반복하지는 않습니다. 거절기는 보통 500ms마다 실행되는 오프라인 부분에서 과부하 여부를 판단하고 거절 비율을 계산한 뒤, 이를 우선순위 임계값으로 바꿉니다. 요청을 받는 온라인 부분의 판단은 짧습니다. 요청의 우선순위를 읽고 원자적 정수에 저장된 임계값보다 높으면 받아들이며, 그렇지 않으면 거절합니다.
목표 함수를 위한 계측도 가볍습니다. 요청이 큐에 들어갈 때와 큐에서 나가 서비스 코드로 넘어갈 때 증가하는 원자 카운터 두 개를 핫 패스에 둡니다. 백그라운드 보정 루프는 지난번 카운터 값을 기억했다가 그동안 늘어난 양을 구합니다. 이 차이로 P를 계산하고 이력에 추가해 PID에 넣습니다.
이력은 계속 쌓아 두지 않습니다. 일반적인 PID의 적분은 전체 이력을 쓰지만 Cinnamon은 보통 최근 30초만 남깁니다. 과부하가 발생할 때마다 요청 패턴이 다를 수 있기 때문입니다. 이력을 제한하면 앞선 과부하에서 쌓인 값이 다음 과부하에 미치는 영향을 줄이고, 달라지는 요청 패턴에 적응하기 쉬워집니다.
가중치는 부하 테스트로 정했습니다. Kp와 Ki를 조금씩 바꿔 가며 결과를 살피는 테스트를 며칠 동안 진행했고, Kp = 0.1과 Ki = 1.4에서 가장 좋은 결과를 얻었습니다. 다른 조정 방법도 있지만 Uber 팀에는 이 방식이 잘 동작했습니다.
최근 요청 1,000개에서 찾는 우선순위 경계
PID가 거절 비율을 10%로 정해도 요청 하나를 받거나 거절하려면 우선순위 임계값이 있어야 합니다. 거절기는 엔드포인트가 최근 본 요청 약 1,000개와 그 우선순위를 기록하고, 우선순위의 누적 분포에서 해당 비율에 맞는 경계를 찾습니다. 1,000개는 RPS가 높은 엔드포인트에서도 좋은 표본이 되는 크기입니다.
티어 1부터 티어 4까지 요청이 같은 양으로 들어온 서비스의 예에서는, 10%를 거절하는 임계값이 티어 4의 코호트 84에 해당합니다. 이 경계는 고정값이 아닙니다. 최근 요청의 우선순위를 계속 기록하므로 PID가 같은 거절 비율을 내놓더라도 요청 구성이 바뀌면 임계값은 그에 맞춰 움직입니다.
높은 거절률에서도 넓어지지 않은 변동 폭
1편에서는 Auto-tuner가 인플라이트 제한을 바꾸는 상황에서도 Cinnamon이 안정적인 거절률을 유지하는 모습을 확인했습니다. 이번 실험은 부하가 변할 때 PID가 거절률을 얼마나 빨리 올리고 내리는지에 초점을 맞췄습니다. Auto-tuner를 끄고 인플라이트 제한을 수동으로 정해 PID의 반응을 따로 봤습니다.
테스트 구성은 1편과 같습니다. 백엔드 노드 두 개에 걸친 서비스가 합쳐서 약 1,300 RPS를 처리합니다. 기본 부하로 1,000 RPS를 보내면서 여러 시점에 부하를 더했고, 실험은 약 25분 동안 이어졌습니다.
결과 그래프의 위쪽에는 들어온 RPS와 수용된 RPS인 goodput을, 아래쪽에는 거절률의 히스토그램을 그렸습니다. 각 인스턴스는 500ms마다 거절률을 내보내지만 시계열 DB인 M3의 최소 해상도는 10초입니다. 그래서 거절률 점들은 10초 단위로 모여 탑처럼 보입니다. 실제 제어 주기보다 관측 화면의 간격이 더 깁니다.
16:05에 부하가 약 3,000 RPS에서 약 6,500 RPS로 뛰었을 때도 수용된 처리량은 약 1,300 RPS였습니다. 거절률은 약 30%에서 약 75%로 10초 안에 올랐습니다. 실제로는 더 빨랐을 가능성이 높지만 M3의 해상도로는 확인할 수 없습니다. 이후 거절률은 70~80% 사이에서 빠르게 안정됐습니다.
팀은 거절률이 움직이는 이 폭을 거절 스팬(rejection span)이라 불렀습니다. 부하가 일정하게 유지되는 모든 구간에서 스팬은 약 10퍼센트 포인트(ppt)였습니다. 트래픽 대부분을 거절하는 상황에서도 폭이 넓어지지 않았습니다.
AIMD와 CoDel에서는 그렇지 않았습니다. 거절 비율이 낮을 때는 스팬이 좁았지만, 거절률이 큰 경우(예를 들어 50% 초과)에는 30ppt 정도로 크게 벌어지곤 했습니다. Uber 팀은 PID의 이력 성분에서 차이를 찾았습니다. 이미 얼마나 거절했는지 기억하기 때문에, CoDel이 빠지기 쉬운 전부 거절과 전혀 거절하지 않음 사이의 진동을 피한다는 설명입니다. 저트래픽과 고트래픽 서비스 모두에서 약 10ppt의 스팬을 얻은 결과는 이전 PID 버전에서도 달성하지 못했던 수준입니다.
이 실험에서는 인플라이트 제한을 고정했습니다. 다음 글은 그 제한을 추정하는 Auto-tuner를 다룹니다.
원문의 주요 수치와 설정값
| 항목 | 값 |
|---|---|
| 오프라인 보정 주기 | 보통 500ms |
| 임계값 산출용 요청 기록 | 최근 1,000개 |
| 적분 이력 한도 | 보통 30초 |
| PID 상수 | Kp = 0.1, Ki = 1.4 |
| 실험 서비스 처리 능력 | 백엔드 노드 2개, 합계 약 1,300 RPS |
| 실험 기본 부하 | 1,000 RPS |
| 부하 급증 사례 | 약 3,000에서 6,500 RPS, 거절률 약 30%에서 약 75%로 10초 이내 |
| 정상 상태 거절 스팬 | 약 10ppt(AIMD·CoDel은 큰 거절률, 예를 들어 50% 초과에서 30ppt 정도) |
| M3 최소 해상도 | 10초 |