목차
병렬로 처리할 수 없는 작업을 위한 Timestone 배타 큐 (2022-09)
원문 정보
- 원문: Timestone: Netflix’s High-Throughput, Low-Latency Priority Queueing System with Built-in Support for Non-Parallelizable Workloads
- 매체 · 게시일: Netflix TechBlog · 2022-09-28
- 저자: Kostas Christidis
- 원문 내용을 바탕으로 재구성한 요약입니다.
수천 개의 동작으로 번질 수 있는 중복 배정
2018년 Netflix는 기존 미디어 인코딩 시스템 Reloaded의 뒤를 이을 Cosmos를 설계하고 있었습니다. API 프레임워크 Optimus, 전방 추론 규칙 엔진 Plato, 서버리스 컴퓨팅 계층 Stratum 사이에는 우선순위 큐가 필요했습니다. 메시지를 빠르게 꺼내는 것만으로는 부족했습니다.
한 시점에 메시지 하나를 맡는 워커는 하나여야 했습니다. Cosmos의 작업은 자원을 많이 쓰고 수천 개의 동작으로 퍼질 수 있습니다. 저장소 복제본 사이에 지연이 있어 워커 A가 한 노드에서 꺼낸 메시지를 워커 B도 꺼낼 수 있다면, 컴퓨팅 자원을 크게 낭비하게 됩니다. Netflix가 최종 일관성 방식의 솔루션을 후보에서 제외한 이유입니다. 큐 단위로 선형화 가능한 일관성이 필요했습니다.
서로 다른 메시지라도 함께 처리해서는 안 되는 경우가 있었습니다. Plato는 모든 워크플로 큐를 계속 폴링합니다. 특정 서비스에 대한 작업 요청을 뜻하는 프로젝트의 워크플로를 실행하는 동안에는, 같은 프로젝트의 추가 요청을 같은 워크플로에서 꺼내면 안 됐습니다. 실행이 겹치면 추론 엔진이 워크플로를 너무 일찍 평가해 잘못된 상태로 옮길 수 있기 때문입니다. 이 제약을 큐가 직접 지원해야 했습니다.
메타데이터의 키-값 쌍으로 메시지를 골라 꺼내고 큐 깊이를 조회하는 기능도 필요했습니다. 메시지를 받을 때 큐를 자동으로 만들고, 메시지가 들어온 뒤 1초 안에 꺼낼 수 있어야 한다는 조건도 있었습니다. 이 요구를 모두 만족하는 기성 솔루션을 찾지 못한 Netflix는 Timestone을 직접 만들었습니다.
우선순위가 높아도 기다리는 메시지
Timestone의 기본 처리 순서는 사용자가 정한 마감이 이른 순서인 EDF(earliest-deadline-first)입니다. simple 큐는 이 순서대로 메시지를 꺼냅니다. 배타 큐(exclusive queue)에는 실행 제약이 하나 더 붙습니다. 같은 배타 값을 가진 메시지의 소비자는 어느 시점에도 최대 한 명입니다.
배타 값을 정하는 기준은 메타데이터입니다. 큐를 만들 때 project를 배타 키로 지정했다면, 그 큐에 넣는 모든 메시지는 메타데이터에 project 키를 가져야 합니다. project=foo인 메시지는 받아들이지만 project 키가 없으면 거부합니다. 여기서 foo가 배타 값입니다.
project=foo인 메시지가 둘 있고 하나를 워커가 이미 맡고 있다면, 다른 하나는 꺼낼 수 없습니다. 우선순위가 높아도 기다립니다. 원문 그림에서 worker_2가 우선순위가 더 높은 msg_1을 건너뛰고 msg_2를 가져가는 이유도 여기에 있습니다. msg_1의 배타 값 foo를 가진 메시지는 이미 다른 워커가 맡고 있었습니다.
워커가 별도 락을 잡거나 서로 조율하지 않아도 큐가 이 제약을 지킵니다. simple 큐에는 이런 배타 조건이 없으며, 메시지 메타데이터에 특정 키를 요구하지도 않습니다.
시각으로 표현하는 우선순위
우선순위는 정수이고 작은 값이 먼저입니다. 값의 범위는 애플리케이션이 정하지만, 보통 밀리초 단위 Unix 타임스탬프를 씁니다. 예를 들어 2022년 9월 1일 0시 UTC는 1661990400000으로 표현합니다.
시각을 쓴다고 모든 메시지를 도착 순서대로 처리하는 것은 아닙니다. Cosmos의 스트리밍 인코딩 파이프라인은 우편 서비스에서 등급을 나누듯 우선순위 클래스를 둡니다. 일반 클래스는 enqueue 시각을 우선순위로 쓰고, 다른 클래스는 그 값을 약 10년의 배수만큼 조정합니다. 같은 시각에 들어온 메시지라도 클래스에 따라 우선순위 값에 큰 차이가 생기는 방식입니다.
우선순위는 워크플로 규칙에서 정합니다. 요청에 DAY_OF_BROADCAST 같은 스튜디오 태그가 붙으면 그 값을 덮어쓸 수도 있습니다.
처리 중인 메시지에 주어지는 lease
큐에 넣은 메시지가 곧바로 처리 대상이 되는 것은 아닙니다. enqueue할 때 비가시 기간을 주면 invisible 상태로 들어가고, 그 기간이 지난 뒤 꺼낼 수 있는 pending 상태가 됩니다. 비가시 기간을 주지 않으면 처음부터 pending입니다.
워커는 dequeue 요청에서 메시지를 맡을 기간인 lease를 지정합니다. pending 메시지를 꺼내면 상태는 running으로 바뀌며, 여러 메시지를 배치로 가져올 수도 있습니다. 그 워커가 lease 안에 complete를 호출하면 completed가 됩니다. 시간이 더 필요하면 lease를 연장하고, 더는 처리할 필요가 없으면 running 메시지를 취소해 canceled로 바꿉니다.
lease 안에 아무 호출도 없으면 메시지는 다시 꺼낼 수 있게 됩니다. 재시도는 무한하지 않습니다. 메시지마다 꺼낼 수 있는 횟수인 attempts가 정해져 있고, dequeue할 때마다 남은 횟수가 하나씩 줄어듭니다. lease가 끝났을 때 남은 시도가 없으면 자동으로 errored 상태가 됩니다.
이 상태 전이는 워커의 API 호출이나 주기적인 백그라운드 처리로 일어납니다. 종료 상태인 completed, canceled, errored의 메시지는 백그라운드 프로세스가 주기적으로 가비지 컬렉션합니다.
사용자가 만들 수 있는 큐의 수에는 제한이 없습니다. 관리 API는 큐 설정 객체를 중심으로 동작하며, 이 객체에는 큐 유형, lease 기간, 비가시 기간, 허용되는 dequeue 횟수, enqueue나 dequeue의 일시 차단 여부가 들어갑니다. 프로듀서는 메시지를 넣을 때 해당 메시지의 lease나 비가시 기간을 따로 지정해 큐의 기본값을 덮어쓸 수 있습니다.
한 Redis 샤드에 모은 큐의 상태
Timestone은 gRPC 기반 서비스입니다. 인터페이스와 메시지 구조는 protocol buffers로 정의하고, 내구성을 갖춘 Redis 클러스터를 기록 시스템으로 사용합니다.
dequeue도 쓰기 요청입니다. 메시지를 꺼내면 큐 상태가 바뀌기 때문입니다. 이 Redis 클러스터는 dequeue를 포함한 모든 쓰기 요청을 트랜잭션 로그에 먼저 기록한 뒤 서버로 응답합니다.
Redis 안에서 큐는 메시지 ID를 우선순위로 정렬한 sorted set입니다. 메시지와 큐 설정은 Redis 해시에 저장합니다. 메시지에는 Timestone이 내용을 해석하지 않는 최대 32KiB의 페이로드와 우선순위, 선택적인 메타데이터 등이 들어갑니다. 메타데이터는 조건에 맞는 메시지를 골라 꺼내는 데 쓰며, 배타 큐에서는 필수입니다.
큐 하나에 속한 자료구조는 전부 같은 Redis 샤드에 둡니다. 메시지와 설정뿐 아니라 필터 기반 dequeue에 쓰는 인메모리 보조 인덱스도 함께 둡니다. 이를 위해 큐마다 고유한 공통 접두사를 붙이고 Redis 해시 태그로 사용합니다.
Redis와의 상호작용은 거의 모두 Lua 스크립트로 작성했습니다. 스크립트 하나가 여러 자료구조를 갱신하더라도 Redis가 이를 원자적으로 실행하므로, 성공한 실행은 시스템을 ACID 의미에서 일관된 상태로 남깁니다. 모든 API 동작의 범위는 큐 하나이며, 상태를 바꾸는 동작은 모두 멱등입니다.
메시지 경로를 추적하는 Elasticsearch
관측에 쓰는 정보는 Elasticsearch로 보냅니다. 서버가 Redis의 쓰기 응답을 받으면, 클라이언트에 응답을 돌려주는 작업과 그 응답을 이벤트로 바꿔 Kafka에 게시하는 작업을 병행합니다. 인덱스 종류마다 Flink 작업 하나가 이벤트를 소비해 Elasticsearch를 갱신합니다.
인덱스는 current와 historic으로 나뉩니다. current는 시스템의 현재 상태를, historic은 메시지가 Timestone 안에서 지나온 경로를 최선 노력(best-effort) 방식으로 보여 줍니다. 특정 상태에 얼마나 오래 머물렀는지, 처리 오류가 몇 번 났는지는 historic에서 추적할 수 있습니다.
메시지에는 쓰기마다 증가하는 버전 카운터가 있습니다. historic 인덱스는 이 카운터로 이벤트 순서를 정합니다. 이벤트를 계속 쌓아 두지는 않으며, 정해진 일수 동안만 보관합니다.
Cosmos 밖으로 넓어진 Timestone의 쓰임
Cosmos용으로 출발한 Timestone은 2년 반 동안 쓰임새가 넓어졌습니다. 원문이 나온 2022년 9월에는 범용 워크플로 오케스트레이션 엔진 Conductor의 우선순위 큐 엔진과 대규모 데이터 파이프라인용 BDP Scheduler에도 쓰였습니다. 매일 수백만 건의 핵심 워크플로가 Timestone을 지났습니다.
요청은 dequeue 쪽에 몰렸습니다. 초당 30K의 dequeue 요청을 P99 45ms에 처리했고, enqueue는 초당 1.2K 요청에 P99 25ms였습니다. enqueue가 초당 5K로 치솟는 버스트도 정기적으로 발생했으며, 이때 P99는 85ms였습니다.
그해 초부터 enqueue한 메시지는 150억 건, dequeue한 횟수는 4000억 회였습니다. 대기 메시지도 종종 1000만 건에 이르렀습니다. Netflix는 남은 Reloaded를 Cosmos로 옮기면 이듬해 사용량이 두 배로 늘 것으로 예상했습니다.
사용 규모 수치
| 항목 | 값 |
|---|---|
| dequeue | 초당 30K 요청, P99 45ms |
| enqueue | 초당 1.2K 요청, P99 25ms |
| enqueue 버스트 | 초당 5K 요청, P99 85ms |
| 올해 enqueue 누계 | 150억 건 |
| 올해 dequeue 누계 | 4000억 회 |
| 대기 메시지 | 종종 1000만 건 |
| 메시지 페이로드 | 최대 32KiB |
| 메시지 메타데이터 | 키-값 쌍 최대 4개 |
샤드 하나의 한계를 넘기 위한 작업
큐와 그 내용이 Redis 샤드 하나에 들어가야 한다는 제약은 남아 있었습니다. 특히 컴퓨팅 용량이 부족할 때 핫 큐가 크게 자랄 수 있었습니다. Netflix는 임의로 큰 큐를 지원하려고 큐 샤딩을 개발하고 있었습니다.
메타데이터에도 비용 문제가 있었습니다. 메시지에 넣을 수 있는 키-값 쌍은 최대 4개이고, 당시에는 이를 모두 필터 기반 dequeue용 보조 인덱스를 채우는 데 썼습니다. 이 연산의 시간과 공간 복잡도는 O(2^n)입니다. Netflix는 sorted set의 사전식 정렬로 전환하는 작업을 진행하고 있었습니다. 인덱스 수를 절반으로 줄이고 메타데이터를 더 적은 비용으로 다루려는 목적입니다.
Cosmos에서 사용이 늘면서 큐 깊이를 조회하는 조건도 다양해졌습니다. 이에 별도의 쿼리 모델을 쓰는 전용 쿼리 서비스를 만들고 있었습니다. 저자는 이런 작업들을 후속 글에서 다룰 수도 있다고 덧붙였습니다.