분산 Rate Limiting 아키텍처

설계를 가르는 변수는 알고리즘이 아니라 카운터를 어디에 두고 어긋남을 얼마나 허용하느냐입니다.

전역 카운트가 비싼 이유

단일 노드에서 요청 수를 세는 일은 어렵지 않습니다. 카운터를 올리고 임계값과 비교하는 두 연산을 원자적으로 묶으면 끝납니다. 여러 노드와 리전에 걸치는 순간부터 같은 작업의 비용이 달라집니다.

정확한 전역 카운트를 유지하려면 모든 노드가 매 요청마다 공유 저장소를 봐야 합니다. 요청 하나에 네트워크 왕복이 하나씩 붙고, 그 저장소가 곧 전체 처리량의 상한이 됩니다. 지연과 병목이 정확도의 대가로 따라옵니다.

Guan(2026, arXiv:2602.11741)은 이 문제를 CAP 정리 관점에서 정리합니다. Redis Cluster 기반 배포에서는 데이터 샤딩과 복제를 통해 가용성과 분할 허용성(AP)을 택하는 것이 일반적이라고 설명합니다. 완벽한 전역 일관성을 포기하고 근사치를 받는 대신 확장성과 가용성을 얻는 선택입니다.

그래서 실무의 첫 질문은 어떻게 정확히 셀 것인가가 아닙니다. 어긋남을 어디까지 허용할 수 있는지, 그 어긋남이 서비스에서 어떤 형태로 드러나는지를 먼저 정합니다. 결제 한도와 공개 API 남용 방지는 허용 오차가 같을 수 없습니다.

알고리즘이 정하는 정확도와 메모리

알고리즘 선택은 정확도, 키당 메모리, 버스트 허용 폭의 교환입니다. 앞에서 정한 허용 오차가 후보를 좁혀 줍니다.

Fixed Window의 경계 문제는 구조적입니다. 분당 100개 제한에서 59초에 100개, 61초에 100개를 보내면 2초 사이에 200개가 통과합니다. 윈도를 리셋 시점 기준으로만 세기 때문에 생기는 결함입니다.

Sliding Window Log는 요청마다 타임스탬프를 남겨 이 결함을 없애지만, 키당 메모리가 요청 수에 비례합니다. Guan(2026)에 따르면 Redis Sorted Set 기반 Rolling Window는 ZADD와 ZREMRANGEBYSCORE로 O(log N)에 동작합니다. 같은 논문은 Token Bucket·Fixed Window와 비교해 정확도와 메모리 비용의 교환을 정량화했습니다.

여기서 중요한 것은 자료구조가 아니라 원자성입니다. 만료 항목 정리, 남은 개수 계산, 새 항목 삽입을 각각 다른 명령으로 보내면 그 사이에 다른 노드가 끼어듭니다. 서버측 Lua 스크립트로 세 연산을 하나로 묶어야 경쟁 조건(race condition)이 사라집니다.

규칙 변경도 같은 자리에서 처리됩니다. 제한 규칙 파라미터를 해싱해 키로 쓰면 캐시된 스크립트를 건드리지 않고도 한도나 윈도 길이를 바꿀 수 있습니다.

GCRA(Generic Cell Rate Algorithm)는 Token Bucket과 같은 동작을 타임스탬프 하나로 표현합니다. 상태가 작아 게이트웨이와 프록시 계층에서 주로 쓰입니다.

카운터를 어디에 둘 것인가

알고리즘을 정해도 절반만 정해진 것입니다. 카운터가 중앙 저장소에 있는지, 각 지역에 흩어져 있는지, 아예 클라이언트에 있는지에 따라 같은 알고리즘의 정확도와 지연이 달라집니다.

• 중앙 저장소는 카운트가 하나뿐이라 정확하지만, 요청마다 붙는 왕복과 저장소 자체의 처리량이 상한을 만듭니다.
• 지역 근사는 판정을 로컬에서 끝내 왕복을 없애는 대신, 지역 수만큼 실효 한도가 늘어나는 오차를 받아들입니다.
• 클라이언트 협력은 서버 상태를 아예 쓰지 않으므로 비용이 가장 낮지만, 클라이언트가 규칙을 지킨다는 전제가 필요합니다.
• 세 배치는 배타적이지 않습니다. 뒤에서 볼 Stripe는 중앙 Redis 위에 여러 계층을 얹고, Cloudflare는 로컬 메모리와 PoP 공유 카운터를 함께 씁니다.

Cloudflare는 근사 쪽을 택했습니다. 이전 구간의 요청 수에 그 구간이 아직 윈도에 겹쳐 있는 비율을 곱하고, 현재 구간의 요청 수를 더해 rate를 추정합니다. 분당 50개 제한에서 이전 구간이 42개였고, 현재 구간이 15초 지난 시점에 18개가 발생했다고 가정합니다. 이전 구간의 남은 45초가 윈도에 걸리므로 42 × (45/60) + 18 = 49.5가 됩니다.

실측 오차는 크지 않았습니다. 약 400만 요청 표본에서 부정확하게 허용되거나 제한된 비율은 0.003%였고, 추정 rate 값의 평균 오차는 실제 값 대비 약 6%였습니다. 임계값을 15%까지 넘겼는데도 통과한 위음성은 3건, 정상 트래픽을 잘못 막은 위양성은 0건이었습니다.

이 근사가 성립하는 이유는 라우팅에 있습니다. Anycast가 같은 IP의 트래픽을 가장 가까운 PoP(Point of Presence, 데이터센터)로 보내므로, 중앙 집계 없이 PoP 단위 독립 카운트가 의미를 갖습니다. PoP 안에서는 Twemproxy가 consistent hashing으로 여러 Memcache 서버에 부하를 나눠, 클러스터 크기가 바뀌어도 키 재분배가 최소화됩니다.

판정 경로는 두 단계입니다. 요청이 오면 로컬 메모리 캐시를 먼저 보고, Memcache 카운터는 백그라운드에서 비동기로 올립니다. 임계값을 넘으면 PoP 안 모든 서버에 완화 신호를 전파해 이후 요청은 Memcache를 보지 않습니다. 이 구조로 초당 40만 건 규모의 공격도 정상 사용자의 서비스 저하 없이 완화했다고 보고합니다.

세 번째 배치는 클라이언트입니다. Farkiani 외(2025, arXiv:2510.04516, IEEE CCNC 2026 채택)는 공유 쿼터 문제를 다룹니다. 여러 독립 클라이언트가 서로의 부하를 모른 채 재시도해 반복 실패하는 상황입니다. 제안된 ATB는 오프라인으로 동작해 서비스 워커로 배포할 수 있고, AATB는 집계된 원격측정 데이터를 활용합니다.

두 알고리즘 모두 시스템 혼잡도를 추론해 재시도 시점을 스케줄링하며, 지수 백오프 대비 HTTP 429(Too Many Requests) 응답을 최대 97.3% 줄였습니다. 완료 시간이 조금 늘지만 에러 감소가 이를 상쇄한다고 밝힙니다. 저자들은 서버 중심 제어가 보안성은 높되 비효율적이고, 클라이언트 사이드는 최소한의 피드백으로 작동하되 클라이언트 간 협력 가능성에 의존한다고 지적합니다. 악의적 클라이언트를 상정해야 하는 자리에는 이 배치를 쓸 수 없다는 뜻입니다.

한 겹으로 막을 수 없는 실패 모드

Stripe는 알고리즘 하나를 고르는 대신 limiter 네 개를 순서대로 둡니다. 요청 폭주, 느린 요청 누적, 인프라 포화, 워커 고갈이 서로 다른 방식으로 서비스를 무너뜨리기 때문입니다.

상태 공유는 Redis 클러스터가 맡아 유형별 요청 수를 중앙에서 셉니다. 여기서 갈리는 결정이 저장소 장애 시 동작입니다. Stripe는 Redis가 죽어도 API가 계속 동작하도록 fail-open으로 미들웨어에 통합했습니다.

fail-open과 fail-closed의 선택은 취향이 아니라 위험 비교입니다. fail-open은 저장소가 죽는 동안 제한이 풀려 뒤쪽 시스템이 부하를 그대로 받습니다. fail-closed는 제한 계층 하나가 죽으면 정상 트래픽까지 막혀 장애 범위가 오히려 넓어집니다.

기준은 rate limiter가 무엇을 막고 있느냐입니다. 남용 방지와 비용 통제가 목적이면 fail-open이 맞습니다. 한도를 넘긴 요청 자체가 정합성이나 과금을 깨뜨리는 자리라면 fail-closed로 가고, 그 대신 저장소를 이중화해 장애 확률을 낮춥니다.

운영 장치도 함께 봐야 합니다. Stripe의 각 limiter는 기능 플래그로 즉시 끌 수 있고, 다크 런칭으로 실제 트래픽에 판정만 돌려 본 뒤 점진 도입됩니다. 제한 규칙을 잘못 걸면 그 자체가 장애이므로, 되돌릴 수 있는 경로가 알고리즘 선택만큼 중요합니다.

적응형 정책과 바깥으로 향하는 제한

고정된 파라미터는 트래픽 패턴이 바뀌면 곧 어긋납니다. Lyu 외(2025, arXiv:2511.03279)는 마이크로서비스 상태를 마르코프 결정 프로세스(Markov Decision Process, MDP)로 모델링했습니다. 그 위에서 DQN(Deep Q-Network)과 A3C(Asynchronous Advantage Actor-Critic)를 결합해 제한 정책을 학습시켰습니다.

쿠버네티스 클러스터에서 90일간 일일 5억 건 요청 규모로 프로덕션 배포한 결과를 보고합니다. 처리량 23.7% 향상, P99 지연시간 31.4% 감소, 서비스 저하 사건 82% 감소, 수동 개입 68% 감소입니다. 사람이 규칙을 튜닝하는 대신 정책을 데이터에서 얻는다는 점이 앞의 패턴들과 다릅니다.

지금까지는 바깥에서 들어오는 요청을 막는 inbound 방향이었습니다. 자사 시스템이 외부나 다운스트림에 가하는 부하를 스스로 줄이는 outbound 방향에도 같은 문제 구조가 있습니다.

토스증권은 정규장 개장 시 100만 건 이상의 예약 주문이 한꺼번에 외부 브로커로 몰리는 문제를 겪었습니다. 해법은 resilience4j의 RateLimiter였습니다. 배치 파라미터로 받은 초당 처리 건수(Transactions Per Second, TPS)로 RateLimiter를 동적으로 만들고, 그 한도 안에서만 요청을 내보냅니다.

정규장 초반 TPS가 평상시의 20배 이상 오르는 구간에서 이 제어가 브로커 응답 지연을 완화했습니다. 뒤이어 발생한 브로커 이슈에 자동 failover가 정상 동작할 기반도 여기서 나왔습니다.

우아한형제들은 Kafka 컨슈머를 수평 확장해도 처리량이 결국 의존 시스템의 한계로 결정되는 문제를 다뤘습니다. 마스터 DB의 CPU 사용률이 80% 이상으로 치솟으면 컨슈머를 더 붙여도 소용이 없습니다. 세 가지 쓰로틀링 방식을 비교한 기록이 남아 있어 선택 근거를 그대로 읽을 수 있습니다.

Thread.sleep()은 heartbeat는 유지되지만 poll()이 멈춰 리밸런싱 위험이 있습니다. pause()/resume()은 poll을 계속 실행하며 빈 레코드를 반환해 리밸런싱을 피합니다. ConsumerInterceptor는 커밋 시점에 지연을 적용합니다. 최종 선택은 CPU 사용률을 모니터링해 2차함수 형태의 지연시간을 파티션 단위 컨테이너에 동적으로 계산·적용하는 방식이었습니다.

조합을 고르는 기준

한 알고리즘이나 한 패턴으로 끝나는 경우는 드뭅니다. 요구사항에서 시작해 알고리즘, 카운터 배치, 장애 시 동작을 한 묶음으로 정합니다.

표의 수치는 각 조직의 트래픽 분포에서 나온 값이라 그대로 옮겨 쓸 수 없습니다. Cloudflare의 0.003%는 약 400만 요청 표본에서 나온 값이고, 요청 분포가 다르면 오차율도 달라집니다. 남의 벤치마크를 근거로 자기 서비스의 허용 오차를 정하면 첫 사고에서 그 차이를 확인하게 됩니다.

적응형 정책의 수치에는 더 무거운 전제가 붙습니다. 90일간 일일 5억 건이라는 학습 데이터와 그만큼의 운영 규모가 있어야 나오는 결과이며, 트래픽이 적은 서비스에서는 학습이 성립하기 어렵습니다. 정책이 왜 그렇게 판정했는지 사후에 설명하기 어렵다는 점도 남습니다.

근사 자체의 한계도 분명합니다. 지역 단위 근사는 지역 수만큼 실효 한도를 늘리는데, 한 사용자의 트래픽이 여러 지역에 걸치면 각 지역이 독립적으로 세기 때문입니다. Anycast로 같은 IP가 한 PoP에 모인다는 전제가 성립할 때만 이 오차가 통제 범위 안에 머뭅니다.

정리

분산 Rate Limiting에서 정확한 전역 카운트와 낮은 지연은 함께 얻기 어렵고, Guan(2026)이 정리했듯 실무는 대체로 가용성 쪽을 택합니다. 알고리즘 선택은 정확도와 키당 메모리, 버스트 폭의 교환입니다. Sliding Window Log의 O(N) 메모리와 Sliding Window Counter의 0.003% 오차가 그 양 끝입니다.

그다음 결정은 카운터의 위치입니다. 중앙 Redis는 정확한 대신 왕복 지연과 단일 병목을 지고, Cloudflare식 지역 근사는 PoP 단위 독립 카운트를 전제로 초당 40만 건 규모까지 흡수합니다. Stripe의 네 계층과 fail-open은 저장소가 죽었을 때 무엇을 잃을지를 먼저 정하라고 말합니다. 정확도가 곧 돈이나 정합성인 자리는 중앙 저장소와 fail-closed로, 남용 방지가 목적인 자리는 근사와 fail-open으로 가는 것이 기본선입니다.