[시스템 설계 - 레이트 리미터] Ep.2 방패의 설계도: 트래픽 폭주 속에서 무엇을, 어디서 막을 것인가

알고리즘 여섯 개를 다 외우고 나면 실전 서비스에 바로 적용할 수 있을까요?

지난 Ep.1 알고리즘 해부에서는 여섯 알고리즘을 Redis 명령어 수준까지 내려가서 뜯어봤습니다. 이번 편은 그 알고리즘을 고르기 전에 끝냈어야 할 결정들을 다룹니다.

 

서버를 띄우고 API를 외부로 여는 순간, 시스템은 끊임없는 시험대에 오릅니다.

 

어느 날 갑자기 터진 마케팅 이벤트로 인한 정상적인 트래픽 폭주일 수도 있고, 악의적인 크롤링 봇의 공격일 수도 있습니다. 혹은 유저가 결제창에서 초조한 마음에 '결제하기' 버튼을 0.1초 만에 세 번 연속 누르는(일명 '따닥') 흔한 실수일 수도 있죠.

 

이 모든 상황은 백엔드 시스템에 즉각적인 위협으로 다가옵니다. 적절한 제어 장치가 없는 시스템은 DB 커넥션 풀을 순식간에 고갈시키고, 결국 전체 서비스 장애로 이어집니다.

 

이때 생각해볼 수 있는 것이 바로 Rate Limiter(처리율 제한 장치)입니다. 그런데 Rate Limiter란 무엇일까요?

 

위키백과에서는 이렇게 말하고 있네요.

"컴퓨터 네트워크에서 처리율 제한(Rate limiting)은
네트워크 인터페이스 컨트롤러가 보내거나 받는
트래픽의 속도를 제어하는 데 사용된다." (위키백과: Rate limiting)

 

즉, 시스템을 보호하기 위해 클라이언트가 일정 시간 동안 보낼 수 있는 요청의 총량을 제한하는 기술을 뜻합니다.

 

솔직히 고백하자면, 저는 이 주제를 오랫동안 '초당 호출 횟수를 튕겨내는 if문' 정도로 이해하고 있었습니다. 토큰 버킷을 검색해서 붙여넣으면 끝나는 일이라고 생각했어요. 그러다 제가 만들어 둔 제한 장치 하나가 한동안 아무도 막지 못하고 있었다는 걸 뒤늦게 알았습니다. 알고리즘이 틀린 게 아니었습니다. 알고리즘은 교과서 그대로였어요. 틀린 건 그보다 훨씬 앞, 무엇을 왜 막을지 정하는 단계에 있었습니다.

 

진짜 견고한 방패를 벼려내려면 코드를 짜기 전에 '무엇을, 왜 막아야 하며, 방어선을 어디에 구축할 것인가'를 먼저 치열하게 정의해야 합니다.

 

이 글에서는 트래픽 제어의 목적을 세분화하는 것부터 시작해, 알고리즘 선택, 동시성 제어, 그리고 장애 대처 전략까지 Rate Limiter 설계의 모든 것을 파헤쳐 보겠습니다.

 

예상 독자 및 다루는 범위

• 예상 독자: 단순 CRUD를 넘어, 대규모 분산 환경의 시스템 설계와 동시성 트레이드오프를 고민하는 주니어에서 미들급 백엔드 엔지니어
• 다루는 범위: 특정 언어의 구현 코드보다는 시스템 디자인 관점의 핵심 의사결정에 집중합니다. (아키텍처 배치 전략, 비용 가중치 설계, GCRA 알고리즘, Redis Lua 원자적 동시성 제어, Fail-Open과 Fail-Closed 생존 전략)

1. 진짜 문제는 무엇인가? (방패의 용도 세분화)

"트래픽 몰리는데 일단 서버 좀 늘리죠."

 

부하가 올라갈 때 가장 먼저 나오는 말이고, 대부분의 경우 이게 맞을 겁니다. Stateless 한 웹 서버는 인스턴스를 늘리면 더 높은 처리량을 감당할 수 있게 되죠.

 

그런데 그렇다면 서버를 무한히만 늘리면 다 되는 걸까요?

 

문제는 스케일아웃이 듣지 않는 구간이 있다는 점입니다.

 

첫째, 늘려도 병목이 그대로인 경우입니다. 웹 서버를 두 배로 늘려도 그 뒤의 DB는 한 대입니다. 커넥션 풀이 병목이라면 앞단을 늘리는 순간 DB로 가는 동시 요청만 두 배가 되어 더 빨리 무너집니다.

 

둘째, 늘리는 데 시간이 걸리는 경우입니다. 오토스케일링이 새 인스턴스를 띄우고 헬스체크를 통과시키기까지 보통 수십 초에서 수 분이 걸립니다. 트래픽 스파이크는 그보다 훨씬 빨리 옵니다.

 

셋째, 늘려주면 안 되는 경우입니다. 크롤링 봇이 초당 수천 건을 긁어가고 있다면, 서버를 늘리는 건 봇에게 더 많은 자원을 내주는 것과 같습니다. 여기서 필요한 건 용량이 아니라 판단입니다.

 

그래서 실무에서는 스케일아웃과 트래픽 제어를 양자택일로 두지 않습니다. 용량으로 풀 수 있는 것은 용량으로 풀고, 용량으로 풀리지 않는 것만 제어로 막습니다. 그리고 밀려오는 트래픽을 무작정 버리는 것은 방어가 아니라 서비스 포기입니다. '누구를, 왜, 어떻게' 막을지 그 목적을 뾰족하게 세분화해야 합니다.

 

즉, 애초에 설계에서부터 다뤄야 하는 영역이 있을 수 있습니다. 그리고 이 지점이 레이트 리미터를 생각해볼 수 있는 지점일 겁니다.

 

그런데 Rate Limiting과 유사한 서로 다른 개념들이 있습니다. 이들을 먼저 함께 살펴보고 개념을 정의하고 가겠습니다. 

 

• 처리율 제한 (Rate Limiting): "한 명이 독식하는 것을 막는다"
  • 무엇을: 특정 IP나 유저가 정해진 시간 동안 호출할 수 있는 API 총량을 제한합니다. (예: User A는 1분에 100회만)
  • 왜: 크롤링 봇이나 특정 헤비 유저가 서버 커넥션을 독점하여 다른 유저들이 피해 보는 것을 막습니다. "무료 티어는 하루 1,000건까지만" 같은 비즈니스 과금 모델을 구현하는 핵심 뼈대이기도 합니다.

• 동시성 제어 (Concurrency Control): "찰나의 겹침을 통제한다"
  • 무엇을: Rate Limit이 '시간당 누적 횟수'를 본다면, 동시성 제어는 지금 당장 동시에 실행 중인 작업(In-flight)의 겹침 자체를 제한합니다.
  • 왜: 데이터의 정합성, 즉 '돈'과 직결된 문제를 막기 위해서입니다. 결제 버튼을 0.1초 만에 3번 '따닥' 눌렀을 때, 3개의 스레드가 동시에 DB 트랜잭션을 물고 늘어지는 것을 막아야 합니다. 

 

• 부하 차단 (Load Shedding): "배가 가라앉기 전에 화물을 버린다"
  • 무엇을: 클라이언트가 누구인지, 할당량이 남았는지는 묻지도 따지지도 않습니다. 우리 시스템의 CPU가 85%를 넘거나 대기 큐가 꽉 차면, 들어오는 요청을 즉시 503 에러와 함께 반환합니다.
  • 왜: 전체 시스템의 연쇄적인 셧다운(Cascading Failure)을 막는 최후의 보루입니다. 서버 10대 중 1대가 과부하로 멈췄을 때, 갈 곳 잃은 트래픽이 나머지 9대로 쏠려 줄줄이 무너지는 상황을 막기 위해 반드시 필요합니다.

세 가지를 가르는 기준은 한 단어로 정리됩니다. 무엇을 세느냐입니다.

 

처리율 제한은 시간을 세고, 동시성 제어는 겹침을 세고, 부하 차단은 아무것도 세지 않고 자기 상태만 봅니다. 요청 하나하나의 처리 비용이 균일한 API라면 처리율 제한으로 충분하지만, 요청마다 무게가 들쭉날쭉하다면 시간만 세는 방패는 뚫립니다. 초당 열 건이어도 건당 30초가 걸리면 300개의 요청이 동시에 살아 있게 되고, 스레드 풀이 먼저 바닥나니까요.

 

이번 연재에서는 이 중에서도 Rate Limiting의 본질적인 설계 원리와, 이를 분산 환경에서 구현할 때 필연적으로 마주치게 되는 동시성 이슈를 융합하여 다룹니다. 

2. 숫자로 증명하라 (규모 추정)

어떤 기술 스택을 선택할지 결정하기 전에, 우리가 감당해야 할 숫자를 먼저 뽑아보아야 합니다. 아키텍처는 트래픽 규모에 따라 완전히 달라지기 때문이죠.

 

예를 들어, 글로벌 서비스의 API Rate Limiter를 설계한다고 가정해 봅시다.

• 트래픽: DAU 100만 명, 피크 타임 API 요청 초당 10,000건(10k TPS).
• 메모리 비용 계산: 각 유저별로 한도 상태를 추적하려면 저장 공간이 필요합니다. 만약 유저 ID(8바이트), 카운트(4바이트), 타임스탬프(4바이트)로 구성된 데이터를 유지한다면, 유저 1명당 대략 20바이트 내외의 오버헤드가 발생합니다. (Redis 해시 기준으로는 메타데이터 포함 더 커집니다.)
• 100만 명의 상태를 동시에 유지하려면 수십 MB에서 수백 MB의 메모리가 필요합니다.

숫자만 나열하면 아무래도 감이 잘 안옵니다. 하나씩 풀어봅시다.

 

DAU 100만 명은 배달 앱이나 중고거래 앱 같은 국내 상위권 서비스의 규모입니다. 하루에 백만 명이 앱을 켠다는 뜻이지, 동시에 백만 명이 접속해 있다는 뜻은 아닙니다.

 

초당 1만 건은 그중 피크 시간대 수치입니다. 점심시간 주문이 몰리거나 티켓 예매가 열리는 순간 같은 때죠. 참고로 1편에서 다룬 것처럼 이 정도면 초당 1만 번의 판정이 돌아가야 한다는 의미입니다.

 

유저 1명당 20바이트는 "이 사람이 몇 번 호출했고 언제부터 셌는지"를 적어두는 메모지 한 장의 크기입니다. 유저 ID 8바이트, 호출 횟수 4바이트, 시작 시각 4바이트를 더한 값이고요. 한글 열 글자가 대략 30바이트니, 그보다도 작습니다.

 

100만 명이면 수십 MB입니다. 사진 한 장이 3MB 남짓이니, 유저 백만 명의 상태 전체가 사진 열 장 정도의 공간에 들어간다는 얘기입니다. 이 정도면 서버 메모리에서 부담 없이 감당할 수 있는 크기입니다.

 

 

 

여기까지는 편안한 숫자입니다. 그런데 이 계산에는 함정이 하나 숨어 있습니다. 방금 잡은 20바이트는 카운터 하나만 들고 있을 때의 이야기라는 점입니다. 뒤에서 다룰 이동 윈도우 로그 방식으로 가면 요청 시각을 전부 기록해야 하므로, 한도가 100일 때 유저 한 명이 800바이트 가까이 쓰게 됩니다. 같은 요구사항인데 알고리즘 선택 하나로 필요한 메모리가 수십 배 차이 납니다.

 

그래서 규모 추정은 알고리즘 선택보다 먼저 와야 합니다. 순서를 뒤집으면 나중에 메모리 앞에서 설계를 되돌리게 됩니다.

 

한편 저장소도 이 숫자를 기반으로 생각해보아야 합니다.

 

단일 서버의 로컬 메모리로 처리하기엔 인스턴스 간 상태 동기화가 불가능하고, RDBMS에 저장하기엔 초당 1만 번의 Write를 디스크 기반 스토리지가 버텨내기 어렵습니다. 자연스럽게 분산 인메모리 캐시(Redis, Memcached) 도입이라는 아키텍처적 결론에 도달하게 됩니다.

 

왜 그런 결론에 도달하는지는 초당 1만 건이라는 숫자를 각 저장소에 그대로 대입해보면 분명해집니다.

 

로컬 메모리는 속도로는 압도적입니다. 문제는 정확성입니다. 서버를 10대로 늘리는 순간 각 인스턴스가 자기가 받은 요청만 세게 되므로, 유저 한 명이 실제로는 한도의 10배까지 호출할 수 있습니다. 트래픽이 늘어서 서버를 늘렸더니 방어선은 오히려 느슨해지는 구조입니다.

 

RDBMS는 정확성은 지킵니다. 대신 같은 로우 하나에 초당 1만 번의 UPDATE가 몰립니다. 행 잠금 경합이 그대로 쌓이고 커밋마다 디스크 fsync가 따라붙습니다. 지키려던 DB 커넥션 풀을 레이트 리미터가 먼저 잡아먹는 셈이죠.

 

Redis는 이 숫자를 여유 있게 받아냅니다. 공식 문서에 실린 redis-benchmark 예시를 보면 파이프라이닝 없이도 SET이 초당 18만 건, p50 지연이 0.143ms로 측정됩니다. 우리가 필요한 1만 건의 열여덟 배입니다. (Redis 공식 문서, Benchmarks)

 

 

그렇다면 Memcached도 같은 인메모리인데 왜 보통 Redis 쪽으로 기울까요?

 

속도 때문은 아닙니다. 같은 문서가 조건을 맞추고 보면 두 저장소의 GET/SET 성능 차이는 그렇게 크지 않다고 적고 있습니다. 갈리는 지점은 다른 데 있습니다. 레이트 리미터는 "읽고, 판단하고, 쓴다"를 하나의 원자적 단위로 묶어야 하는데, Memcached는 incr이나 decr 같은 단순 원자 연산만 제공하고 서버 안에서 조건 분기를 실행할 방법이 없습니다. Redis는 Lua 스크립트를 서버에서 그대로 돌립니다. 이 차이가 왜 결정적인지는 5장에서 다룹니다.

 

3. 방어선은 어디에 쳐야 하는가? (위치 선정)

규모와 스택의 윤곽이 잡혔다면, 이 모듈을 아키텍처의 어디에 배치할 것인지 결정해야 합니다. 방어선은 크게 세 군데에 구축할 수 있습니다.

3.1. 엣지 레이어 (CDN, WAF)

AWS CloudFront나 Cloudflare 같은 엣지 단에서 처리합니다.

• 장점: 트래픽이 우리 서비스의 인프라로 들어오기 전에 앞단에서 잘라냅니다. 비용이 가장 저렴하고 DDoS 방어에 탁월합니다.
• 단점: 유저의 등급에 따라 한도를 다르게 주거나, 특정 API 도메인 로직과 결합된 복잡한 제어를 하기엔 한계가 있습니다. 주로 IP 기반의 단순 차단에 쓰입니다.

엣지의 본질은 "우리 집 대문 앞에서 거르는 것"입니다. 대문 밖에서 돌려보낸 사람은 마당을 밟지도 않았으니 전기세도 안 나가죠. 대신 대문 앞에서는 그 사람이 우리 집 VIP 회원인지 아닌지 알 방법이 없습니다. 인증은 대문 안쪽에서 일어나니까요. 엣지에 유저 등급별 한도를 걸고 싶다는 요구가 나오면, 그때부터는 인증 정보를 엣지까지 끌어올려야 하고 구조가 복잡해집니다.

 

 

3.2. API 게이트웨이 (API Gateway)

마이크로서비스 아키텍처에서 가장 널리 쓰이는 표준적인 위치입니다.

• 장점: 모든 서비스로 향하는 트래픽의 중앙 관문이므로, 중앙 집중식 모니터링과 제어가 가능합니다. 비즈니스 로직까지 트래픽이 도달하지 않으므로 백엔드 리소스를 아낄 수 있습니다.
• 단점: API 게이트웨이 자체가 시스템의 단일 장애점이 될 수 있으며, 게이트웨이의 성능이 전체 시스템의 병목이 될 수 있습니다.

게이트웨이가 표준 위치가 된 이유는 단순합니다. 인증이 이미 끝난 지점이면서 아직 비즈니스 로직에는 닿지 않은, 유일한 구간이기 때문입니다. 유저가 누구인지 알면서도 비싼 자원은 아직 안 쓴 상태죠. 다만 모든 트래픽이 이 한 곳을 지나간다는 말은, 이 한 곳이 느려지면 전부 느려진다는 말이기도 합니다. 편의를 얻는 대신 위험을 한 곳에 모으는 거래인 셈입니다.

 

 

 

3.3. 마이크로서비스 내부 (애플리케이션 계층)

Spring의 Interceptor나 Filter 단, 혹은 비즈니스 로직 내부에서 직접 제어합니다.

• 장점: 가장 세밀한 제어가 가능합니다. "조회 API는 1건 차감, 무거운 통계 생성 API는 5건 차감"과 같은 동적인 비용 가중치 처리를 도메인 로직과 매끄럽게 결합할 수 있습니다.
• 단점: 서비스가 늘어날 때마다 중복 구현이 발생하기 쉽고, 차단 처리로 인해 이미 애플리케이션 스레드가 소비된다는 단점이 있습니다.

서비스 안쪽은 제일 많이 아는 곳입니다. 이 요청이 어떤 도메인 행위인지, 얼마나 무거운지, 이 유저가 이번 달에 뭘 했는지까지 알고 있죠. 아는 만큼 정교하게 막을 수 있습니다. 문제는 여기까지 왔다는 건 이미 커넥션을 하나 잡고 스레드를 하나 쓴 뒤라는 겁니다. 가장 똑똑하게 거절하지만 가장 비싸게 거절하는 셈입니다.

 

 

 

그렇다면 정답은 어디일까요?

 

위에서 보듯 각 계층은 명확한 한계를 지닙니다. 엣지 단에만 두면 유저 등급별 제어 같은 비즈니스 요구사항을 맞출 수 없고, 반대로 애플리케이션 내부에만 두면 단순한 봇의 공격에도 비싼 백엔드 스레드를 낭비하게 됩니다.

 

따라서 현대적인 엔지니어링 실무에서는 단일 계층에 의존하지 않고, 각 위치의 장점을 조립한 '다층 방어(Defense in Depth)' 전략을 채택합니다.

 

비단 트래픽 제어에만 해당하는 이야기는 아닙니다. AWS가 클라우드 아키텍처 설계 지침으로 정리한 Well-Architected Framework의 보안 기둥을 보면, 일곱 개 설계 원칙 중 하나로 이렇게 이야기합니다.

"Apply security at all layers: Apply a defense in depth approach with multiple security controls. Apply to all layers (for example, edge of network, VPC, load balancing, every instance and compute service, operating system, application, and code)."

"모든 계층에 보안을 적용하라. 여러 겹의 통제 수단으로 심층 방어 방식을 적용한다. 네트워크 엣지, VPC, 로드 밸런싱, 모든 인스턴스와 컴퓨팅 서비스, 운영체제, 애플리케이션, 코드까지 전 계층에 적용한다."

출처: AWS Well-Architected Framework, Security Pillar 설계 원칙

 

이러한 클라우드 아키텍처 철학을 트래픽 제어에 그대로 차용하면, 다음과 같은 견고한 하이브리드 방어선이 구축됩니다.

 

• 1차 방어선 (Edge): AWS WAF 등을 활용해 IP 기반의 단순 크롤링이나 L4/L7 수준의 무차별적 공격을 인프라 진입 전 앞단에서 저렴하게 걷어냅니다.
• 2차 방어선 (API Gateway): 유저의 Tier 별 API 할당량 관리 등 비즈니스 규칙이 가미된 중앙 집중식 제어를 전담하여 백엔드 서버의 부하를 원천 차단합니다.
• 3차 방어선 (Microservice): 결제 정합성이나 무거운 도메인 로직과 강하게 결합된 크리티컬한 제어만 서비스 내부 애플리케이션 코드 레벨로 끌고 들어와 세밀하게 방어합니다.

배치의 판단 기준은 하나로 압축됩니다. 막으려는 대상을 식별할 수 있는 가장 바깥에 두는 것입니다. IP만 알면 되는 공격은 엣지에서, 유저를 알아야 하는 할당량은 게이트웨이에서, 도메인 의미가 필요한 제어는 서비스 안에서 처리합니다.

4. 측정의 기술: 트래픽을 세는 완벽한 알고리즘과 GCRA

방어선을 구축했다면 성벽 위에 서서 다가오는 적들을 어떻게 '카운팅' 할 것인지 알고리즘을 설계할 차례입니다. 단순히 "1분에 100개씩"이라고 생각할 수 있지만, 분산 환경에서 이를 정확하고 효율적으로 구현하는 것은 까다로운 문제입니다.

4.1. 무엇을 셀 것인가? (1요청 = 1비용의 함정)

흔히 Rate Limiter를 처음 구현할 때 가장 많이 하는 실수가 모든 API 요청을 공평하게 '1회'로 퉁쳐서 카운트하는 것입니다. IP 주소나 User ID를 키로 삼고, "이 유저는 1분에 100번까지만 API를 호출할 수 있어"라고 룰을 정하는 식이죠.

 

하지만 실무의 전장으로 오면 이야기가 완전히 달라집니다. 우리 시스템이 제공하는 API들은 저마다 잡아먹는 리소스의 체급이 천차만별이기 때문입니다.

• GET /users/me: Redis에 캐싱된 유저 정보만 0.01초 만에 읽어오고 끝나는 가벼운 API
• POST /reports/export: 지난 5년간의 결제 내역 수백만 건을 RDBMS에서 긁어모아, 메모리에서 엑셀 파일로 눌러 담아내는 매우 무거운 통계 API

만약 이 두 API를 똑같이 '1회'로 취급한다면 어떤 일이 벌어질까요?

 

 

 

정상적인 유저가 가벼운 조회 API를 1분에 100번 호출하는 것은 서버 입장에서 산들바람에 불과합니다. 하지만 악의적인 유저, 혹은 로직을 잘못 짠 사내 어드민 클라이언트가 저 무거운 통계 엑셀 다운로드 API를 1분에 100번 연속으로 호출한다면 상황은 달라집니다.

 

Rate Limiter는 "아직 분당 100회 한도가 안 넘었네? 통과!"라며 문을 열어줄 것입니다. 방어막을 무사통과한 100개의 무거운 요청은 백엔드로 쏟아져 들어와 순식간에 DB 커넥션 풀을 모조리 점유해 버립니다. CPU 사용률이 치솟고 메모리는 OOM을 뱉어내며, 결국 이 통계 API와는 아무 상관도 없는 메인 결제 시스템까지 도미노처럼 무너져 내리게 됩니다. '1요청 = 1비용'이라는 가정 하나가 만든 결과입니다.

 

해결책: 비용 가중치 설계

 

이런 상황을 막기 위한 한 가지 방법으로 단순한 호출 횟수가 아니라, 토큰이라는 과금 개념을 도입할 수 있겠습니다. 유저에게 '분당 100개의 토큰'을 부여하되, API가 시스템에 가하는 부하량에 따라 차감하는 토큰의 양을 다르게 책정하는 것이죠.

• 가벼운 캐시 조회 API 호출 시: 토큰 1개 차감
• 무거운 통계 생성 API 호출 시: 토큰 50개 차감

이렇게 설계하면 무거운 통계 API는 단 2번만 호출해도 100개의 토큰이 모두 소진되어 즉각 차단(429 Too Many Requests)됩니다. 각 API가 시스템에 미치는 실제 물리적 부하량을 기준으로, 훨씬 더 촘촘하고 논리적인 방어선을 구축할 수 있게 됩니다.

 

즉 한도는 요청의 개수가 아니라 요청이 만들어내는 비용에 걸어야 합니다.

4.2. 어떻게 셀 것인가? (전통 알고리즘의 명암)

아마 백엔드 엔지니어라면 한 번쯤 필독서로 꼽히는 바이블, 《가상 면접 사례로 배우는 대규모 시스템 설계 기초》(알렉스 쉬 지음, 이병준 옮김, 인사이트, 2021)라는 책을 읽어보셨을 겁니다. 이 책 4장을 보면 처리율 제한을 구현하는 알고리즘으로 토큰 버킷, 누출 버킷, 고정 윈도우 카운터, 이동 윈도우 로그, 이동 윈도우 카운터 등 무려 5가지를 상세히 제시합니다.

 

그런데 실제 대규모 트래픽이 몰리는 분산 서버에 이 알고리즘들을 교과서처럼 그대로 구현하려고 들면, 책에서는 미처 체감하지 못했던 인프라적 한계에 부딪히게 됩니다.

 

이 다섯 알고리즘이 Redis 안에서 실제로 어떻게 돌아가는지, 어떤 명령어로 무엇이 저장되고 지워지는지는 Ep.1 알고리즘 해부에서 전부 다뤘습니다. 이 글은 설계 결정에 집중하는 편이라 여기서는 결론만 요약하고 넘어가겠습니다.

명령어 단위의 해부가 궁금하시다면 Ep.1 알고리즘 해부를 참고해주세요.
ZADD로 쌓인 타임스탬프가 어떤 명령어로 지워지는지,
토큰 버킷의 소급 계산이 HMGET과 HSET 사이 어디서 깨지는지,
GCRA의 수식 한 줄이 그 모두를 어떻게 대신하는지를 전부 다뤘습니다.

알고리즘	상태로 무엇을 들고 있나	실전에서 무너지는 지점
고정 윈도우 카운터	카운터 하나	윈도우 경계에서 한도의 2배 통과
이동 윈도우 로그	요청 시각 전부	메모리가 한도에 비례해 폭증
이동 윈도우 카운터	카운터 둘	직전 구간이 균등 분포라는 가정이 깨지면 오차
토큰 버킷	잔량과 마지막 갱신 시각	소급 계산이 경쟁 상태를 부른다
누출 버킷	큐 또는 그 근사	요청을 기다리게 만들어 동기 API에 부적합

 

한 줄로 줄이면 이렇습니다. 다섯 알고리즘의 차이는 "상태로 무엇을 들고 있느냐"이고, 그 선택이 메모리와 정확도와 동시성 비용을 한꺼번에 결정합니다.

 

그래서 이 5가지 알고리즘의 개념을 백과사전처럼 다 외우는 것보다는, 가장 대표적인 알고리즘들이 실전에서 어떤 방식으로 우리를 배신하는지 그 명암과 트레이드오프를 짚어보는 것이 훨씬 실무적입니다. 제 생각에 시스템을 직접 설계하는 엔지니어라면, 최소한 다음 세 가지 전통적 알고리즘의 맹점만큼은 뼈저리게 이해하고 있어야 합니다.

• 고정 윈도우 카운터 (Fixed Window Counter): 경계 시간대의 사각지대
  가장 직관적이고 구현하기 쉬운 방법입니다. 1분 단위로 윈도우(시간 구간)를 쪼개고 요청이 올 때마다 Redis의 카운터를 1씩 증가시킵니다. 카운터가 100이 되면 다음 분이 올 때까지 막는 식이죠.
  • 치명적 단점: 실전에서는 경계선에서 사각지대가 발생합니다. 만약 밤 11시 59분 59초에 봇이 100개의 요청을 쏟아내면, 윈도우 상으론 정상이니 모두 통과됩니다. 그리고 불과 1초 뒤인 12시 00분 00초, 윈도우가 초기화되자마자 봇이 다시 100개의 요청을 쏟아냅니다. 이 역시 통과됩니다. 결과적으로 백엔드 서버는 불과 2초라는 찰나의 시간에 한도의 2배인 200개의 트래픽을 정통으로 받아내게 됩니다. 트래픽 스파이크에 무력한 방패입니다.

• 이동 윈도우 로그 (Sliding Window Log): 배보다 배꼽이 큰 청구서
  고정 윈도우의 경계 문제를 완벽하게 해결하기 위해 등장한 대안입니다. 요청이 들어올 때마다 타임스탬프를 Redis 같은 저장소에 차곡차곡 로그로 기록하고, '현재 시간으로부터 정확히 1분 전까지'의 기록만 세어서 한도를 넘는지 확인합니다.
  • 치명적 단점: 논리적으로는 무결하지만, 이번엔 인프라 비용(메모리) 청구서가 우리를 덮칩니다. 수십만 명의 활성 유저가 발생시키는 모든 API 요청의 타임스탬프를 (심지어 차단된 요청의 타임스탬프까지도) 분산 캐시 메모리에 들고 있어야 합니다. 앞서 규모 추정에서 잡았던 유저당 20바이트가 여기서는 수백 바이트로 불어납니다. 비싼 Redis 메모리가 순식간에 고갈되는 구조가 되어버려 대규모 시스템에서는 사실상 폐기되는 방식입니다.
• 토큰 버킷 (Token Bucket): 구현의 복잡성과 동시성 병목
  아마존 API 게이트웨이나 스트라이프(Stripe) 같은 글로벌 IT 기업들이 사실상 표준으로 사용하는 알고리즘입니다. 양동이에 일정 시간마다 토큰을 채워두고, 요청이 올 때마다 토큰을 하나씩 꺼내 씁니다. 짧은 시간에 몰아치는 트래픽도 유연하게 방어할 수 있죠.
  • 단점: 개념은 아름답지만 코드로 구현하려고 하면 머리가 아파집니다. "1초마다 토큰을 채운다"는 것을 물리적으로 구현하려면, 유저 수백만 명의 양동이를 매초마다 채워주는 백그라운드 프로세스를 띄워야 할까요? 불가능합니다. 결국 요청이 들어오는 순간, '마지막으로 토큰을 채운 시간'과 '현재 시간'을 비교해 소급해서 토큰을 채워 넣는 계산이 따라붙게 됩니다. 이는 이후 다룰 분산 환경의 Race Condition에서 병목을 유발하는 원인이 됩니다.

4.3. 우아한 해결책, GCRA (Generic Cell Rate Algorithm)

앞서 살펴본 토큰 버킷의 장점(버스트 트래픽 처리)을 그대로 가져가면서도, 인프라의 복잡성과 메모리 낭비를 극적으로 줄여낸 알고리즘이 있습니다. 바로 GCRA(Generic Cell Rate Algorithm)입니다.

 

이 알고리즘은 블로그 글에서 누가 지어낸 것이 아니라, 정식 통신 규격에 문서로 정의되어 있는 기술입니다. 출처가 두 곳입니다. ITU-T 권고안 I.371(광대역 종합정보통신망의 트래픽 제어와 혼잡 제어)과 ATM 포럼의 트래픽 관리 규격 4.0(AF-TM-0056.00)입니다. 1990년대 ATM 네트워크에서 셀 단위 트래픽을 감시하려고 만든 것이죠.

"GCRA는 ATM 네트워크의 네트워크 스케줄러에 쓰이는
누출 버킷 계열 스케줄링 알고리즘이다.
가상 채널이나 가상 경로를 흐르는 셀의 타이밍을,
해당 채널의 트래픽 계약에 명시된 대역폭 및 지터 한계와 대조해 측정한다.
규격을 지키지 않는 셀은 트래픽 셰이핑에서 지연되거나, 트래픽 폴리싱에서 폐기되거나 우선순위가 강등된다."

출처: Wikipedia, Generic cell rate algorithm (원 규격: ITU-T I.371 및 ATM Forum AF-TM-0056.00)

 

쉽게 말해, 과거 통신망에서 거대한 데이터 패킷들이 네트워크를 터뜨리지 않도록 라우터에서 트래픽을 셰이핑(Shaping)하던 근본 있는 기술을 소프트웨어 레벨로 끌고 온 것입니다.

 

여기서 한 번 더 들어가 볼 만한 대목이 있습니다. 규격은 GCRA를 서로 동등한 두 가지 방식으로 정의합니다. 하나는 '가상 스케줄링 알고리즘(virtual scheduling algorithm)'이고, 다른 하나는 '연속 상태 누출 버킷(continuous state leaky bucket)'입니다. 그리고 규격은 이 둘이 같은 결과를 낸다고 명시합니다.

 

이게 왜 중요할까요. 흔히 이렇게 생각할 수도 있죠. "누출 버킷은 큐고, 토큰 버킷은 잔량이고, GCRA는 시간이다"라고 셋을 나란히 놓고 외우는 식으로 말입니다. 규격의 입장에서 보면 셋은 같은 것을 다른 각도에서 본 것입니다. 버킷에 물이 얼마나 남았는지 보는 관점(연속 상태 누출 버킷)과, 다음 셀이 언제 도착해야 하는지 보는 관점(가상 스케줄링)은 서로 변환 가능합니다.

 

그래서 GCRA를 "새로운 알고리즘"으로 외울 필요는 없다는 생각입니다. 버킷의 물높이를 매번 계산하는 대신, 그 물높이가 0이 되는 시각 하나만 저장해 두는 것. 이게 전부입니다. 상태를 공간에서 시간으로 옮겨 적었을 뿐이고, 그 한 번의 좌표 변환이 뒤에 나올 모든 인프라 이득을 만들어냅니다.

 

공간에서 '시간'으로의 발상의 전환

 

토큰 버킷이 양동이 속 '토큰의 남은 개수(공간)'에 집착했다면, GCRA는 발상을 완전히 전환합니다. 복잡한 계산이나 백그라운드 프로세스를 버리고, 오직 '시간' 단 하나만을 추적합니다.

 

GCRA의 핵심은 TAT(Theoretical Arrival Time, 다음 요청이 허용되는 이론적 시간)입니다. 클라이언트가 요청을 보낼 때마다 "너 방금 요청했지? 너의 다음 요청은 무조건 특정 시점 이후에나 가능해"라고 미래의 데드라인을 못 박아버리는 셈입니다.

 

 

 

GCRA의 동작 원리 (예: 1초에 1개씩 허용하는 API)

1. 첫 요청 (0초): 유저 A가 첫 결제 API 요청을 보냅니다. 서버는 이를 통과시키고, Redis에 유저 A의 TAT = 1초 (현재 시간 0초 + 간격 1초)라고 기록합니다. "다음 요청은 1초 뒤에나 받아주겠다"는 선언입니다.
2. 성급한 두 번째 요청 (0.5초): 유저 A가 참지 못하고 0.5초 만에 다시 버튼을 '따닥' 누릅니다. 서버는 Redis에 저장된 TAT(1초)를 확인합니다. 현재 시간(0.5초)이 TAT(1초)에 도달하지 못했으므로 이 요청은 거절(Drop)합니다.
3. 정상적인 세 번째 요청 (1.2초): 시간이 흘러 1.2초에 유저 A가 다시 요청을 보냅니다. 이번엔 현재 시간(1.2초)이 TAT(1초)를 지났으므로 통과시킵니다. 그리고 새로운 TAT를 어떻게 갱신할까요? 방금 요청이 허용된 시점부터 다시 1초 뒤인 현재 시간(1.2초) + 1초 = 2.2초로 덮어씁니다.

이 방식의 압도적인 장점은 수백만 명의 유저가 접속해도, 각 유저마다 Redis에 단 하나의 타임스탬프 숫자(TAT, 8바이트 정수)만 저장하면 끝난다는 것입니다. 1초마다 토큰을 채워줄 필요도, 남은 토큰 개수를 계산할 필요도 없습니다.

 

여기까지 읽으면 한 가지가 걸립니다. 이렇게 시간을 엄격하게 재면 트래픽 스파이크는 어떻게 감당할까요. 토큰 버킷은 안 쓰고 모아둔 토큰으로 순간 폭주를 흡수하는데, GCRA에는 모아둘 토큰이 없어 보입니다.

 

제가 처음 GCRA를 봤을 때 막혔던 부분이 정확히 여기였습니다. 위 예시처럼 TAT만 엄격하게 적용하면 요청이 조금만 밀려도 에러가 나는 너무 뻣뻣한 방패가 됩니다.

 

이를 해결하기 위해 GCRA는 실제 구현 시 '버스트 허용치(Tolerance, τ)'라는 개념을 추가로 사용합니다. 단순히 TAT와 현재 시간을 비교하는 것이 아니라, TAT - 현재 시간의 차이가 우리가 설정한 허용치(관용의 범위) 이내라면 트래픽을 통과시켜 줍니다.

 

즉, TAT가 미래의 시간을 가리키고 있더라도 그 갭이 허용치 안이라면, 시스템이 유저에게 일종의 '시간적 빚'을 지게 만들고 당장 통과시켜 주는 원리입니다. 결과적으로 복잡한 양동이 모델을 쓰지 않고도 토큰 버킷과 수학적으로 완벽하게 동일한 버스트 허용 효과를 냅니다.

 

그럼 실제로 이걸 쓰는 곳이 있을까요? 이 대목은 자료를 찾아보다가 제 오해를 하나 바로잡게 된 부분이라 그대로 적어둡니다.

 

저는 처음에 "글로벌 결제사 Stripe가 GCRA를 쓴다"고 알고 있었습니다. 그런데 Stripe 공식 기술 블로그의 Scaling your API with rate limiters(2017)를 직접 열어보니 GCRA라는 단어가 한 번도 나오지 않습니다. 그 글이 말하는 건 토큰 버킷이고, 네 종류의 제한 장치를 겹쳐 쓴다는 이야기입니다. 요청 속도 제한, 동시 요청 제한, 전체 사용량 기반 부하 차단, 워커 사용률 기반 부하 차단이죠. 앞서 1장에서 나눈 세 가지 방어막이 실제 회사에서 어떻게 조합되는지 보여주는 좋은 사례이기도 합니다.

 

그럼 GCRA와 Stripe를 엮는 이야기는 어디서 나왔을까 해서 찾아봤더니, Stripe 엔지니어였던 Brandur Leach가 개인 블로그에 쓴 Rate Limiting, Cells, and GCRA 에 있었습니다. 그는 GCRA를 Redis 모듈로 구현한 redis-cell을 만들었고, 같은 글에서 동료 Andrew Metcalf가 Go 라이브러리 throttled를 GCRA 기반으로 개선했으며 그것이 이미 Stripe의 프로덕션 트래픽을 받고 있다고 적었습니다.

 

Brandur의 글에 실린 허용 요청과 거절 요청 도식을 같은 구조로 다시 그렸습니다.

 

 

정리하면 이렇습니다. 회사의 공식 문서는 토큰 버킷을 말하고, 그 회사의 엔지니어는 개인 블로그에서 GCRA로 갈아탄 이야기를 합니다.

 

둘 다 사실이고, 모순도 아닙니다. 조직의 공식 아키텍처 문서는 보통 가장 오래 검증된 것을 적고, 실제 코드는 그보다 앞서가니까요. 기술 선택의 근거를 찾을 때 회사 이름만 보고 넘어가면 안 되는 이유이기도 합니다.

 

"공간(남은 토큰)을 계산하는 것보다, 시간(미래의 데드라인)을 계산하는 것이 분산 환경에서 훨씬 값싸고 빠르다." 이것이 GCRA가 시스템 설계자들에게 주는 가장 강력한 인사이트입니다.

5. 분산 환경의 벽: 찰나의 동시성을 제어하는 원자적 처리의 기술

비용 가중치도 정교하게 설계했고, 트래픽 스파이크와 메모리 효율을 모두 잡은 우아한 GCRA 알고리즘까지 선택했습니다. 상태 저장소로는 훌륭한 인메모리 DB인 Redis까지 배치했습니다.

 

자, 이제 모든 게 완벽할까요?

 

한번 상상해 봅시다. 금요일 저녁 8시, 선착순 1,000명에게만 주어지는 할인 쿠폰 이벤트가 시작되었습니다. 오픈과 동시에 수만 명의 유저가 '쿠폰 발급' 버튼을 연타합니다. 혹은 클라이언트 측의 버그로 인해 특정 유저의 앱에서 1초에 5,000번의 재시도가 서버로 쏟아져 들어왔습니다.

 

이때 우리의 Rate Limiter는 초당 수천 건의 요청이 '동일한 유저 Key'를 향해 동시다발적으로 읽기와 쓰기를 시도하는 상황을 맞게 됩니다. 바로 이 지점에서, 로컬 환경에서는 절대 보이지 않던 Race Condition이 발생하며 방어막이 뚫리기 시작합니다.

 

 

 

5.1. 찰나의 틈: Read-Modify-Write의 비극

🙋‍♂️ "잠깐만요, Redis는 싱글 스레드로 동작하잖아요? 그럼 동시에 접근해도 알아서 순서대로 처리되니까 안전한 것 아닌가요?"

 

반은 맞고 반은 틀린 질문입니다. Redis 서버 자체가 명령어를 하나씩 순차 처리하는 것은 맞습니다. 하지만 문제는 Redis가 아니라, 데이터를 꺼내와서 계산하는 우리 애플리케이션(Spring, Node.js 등)의 멀티 스레드 환경에 있습니다.

 

Rate Limiter의 기본적인 로직은 다음 3단계로 이루어집니다.

1. Read: Redis에서 유저의 남은 한도(또는 TAT)를 읽어옵니다.
2. Modify: 애플리케이션 메모리상에서 한도를 초과했는지 계산하고 차감합니다.
3. Write: 계산된 새로운 결과값을 Redis에 덮어씁니다.

이른바 Read-Modify-Write (R-M-W) 패턴입니다. 문제는 Read와 Write 사이의 '찰나의 시간'에 발생합니다.

 

 

 

유저 A의 남은 API 호출 횟수가 딱 1번 남았다고 가정해 봅시다.

• 스레드 1이 Redis에서 '1'을 읽어옵니다.
• (이 찰나의 순간) 스레드 2가 동시에 접근하여 Redis에서 똑같이 '1'을 읽어옵니다.
• 스레드 1이 애플리케이션에서 "1 > 0 이니까 통과!"라고 판단하고 Redis에 '0'을 덮어씁니다.
• 스레드 2 역시 애플리케이션에서 "어? 나도 아까 1 읽어왔는데? 1 > 0 이니까 통과!"라고 판단하고 이미 '0'이 된 Redis에 또다시 '0'을 덮어씁니다.

분명 1번밖에 안 남았는데, 두 개의 요청이 모두 방어선을 통과해 버렸습니다. 정합성이 완전히 붕괴되는 순간입니다.

 

이 문제를 분산 환경에서 어떻게 다루는지는 예전에 대기열 시스템 다양한 설계 방법 탐구에서 한 번 정리한 적이 있습니다.

 

같은 카운팅 문제를 상태 기반, HashSet과 스케줄링, Counter와 keyspace notification, Counter와 Kafka 이렇게 네 가지 방식으로 구현하면서 각 방식이 어디서 무너지는지 비교한 글입니다. 이 글에서 다루는 경쟁 상태의 더 구체적인 변주들이 궁금하시면 함께 보시면 좋습니다.

5.2. 분산 락(Distributed Lock)의 함정

🙋‍♂️ "아하, 전형적인 동시성 문제군요! 그럼 Redisson 같은 걸 써서 SETNX로 Redis에 분산 락을 걸어버리면 되는 거 아닌가요? 락을 쥐고 있는 스레드만 계산하게 만들면 되잖아요."

 

결제나 정산 도메인이라면 훌륭한 정답입니다. 하지만 Rate Limiter 도메인에서 분산 락은 시스템 전체를 위태롭게 만드는 선택이 될 수 있습니다.

 

Rate Limiter의 존재 이유는 '모든 트래픽의 맨 앞단에서 가장 빠르고 가볍게 검문'하는 것입니다. 그런데 분산 락을 도입하는 순간 다음과 같은 문제가 발생합니다.

1. 지연 시간(Latency) 폭증: 락을 획득하고, 실패하면 재시도(Spin Lock 등)하고, 로직을 수행한 뒤 락을 해제하는 과정에서 수많은 네트워크 I/O가 추가로 발생합니다.
2. 스레드 병목: 동일한 Key에 트래픽이 몰릴 때, 락을 얻지 못한 수백 개의 애플리케이션 스레드들이 대기 상태에 빠집니다. 결국 톰캣의 스레드 풀이 고갈되어, Rate Limiter와는 상관없는 다른 정상적인 API들까지 모두 멈춰버립니다.

1초에 수만 건이 스쳐 지나가야 할 최전선 초병에게 너무나 무거운 강철 갑옷을 입히는 셈입니다.

5.3. 원자적 처리의 은탄환: Redis Lua 스크립트

빠르면서도 동시성 문제를 완벽하게 해결하는 가장 우아한 방법이자, Rate Limiter 설계의 사실상 표준은 바로 Redis 내장 Lua 스크립트를 활용하는 것입니다.

 

🙋‍♂️ "분산 락도 안 걸고 대체 어떻게 동시성을 보장한다는 건가요?"

 

애플리케이션과 Redis 사이를 여러 번 왔다 갔다 하는 R-M-W 과정을, 아예 스크립트 하나로 묶어서 Redis 내부로 던져버리는 것입니다.

 

네 번 왕복하던 것을 한 번에 끝내기

 

 

• 절대적인 원자성 (Atomicity): Redis 내부에서 Lua 스크립트가 실행되는 순간, Redis는 해당 스크립트 전체를 단일 명령어처럼 취급합니다. 즉, Lua 스크립트가 실행되는 0.001초 동안에는 외부에서 들어온 다른 어떤 명령어(GET, SET 등)나 스크립트도 절대 중간에 끼어들 수 없습니다. 락을 걸지 않고도 Read-Modify-Write 연산 전체가 완벽한 원자성을 보장받습니다.
• 네트워크 I/O 최적화: Read 요청 -> 응답 -> Write 요청 -> 응답으로 이어지던 네트워크 왕복을 단 한 번의 스크립트 전송으로 끝냅니다. 네트워크 지연 시간을 절반 이하로 떨어뜨립니다.

실무적인 최적화 포인트 (SCRIPT LOAD & EVALSHA)

매번 긴 Lua 스크립트 코드를 네트워크로 전송하는 것도 낭비입니다. 따라서 애플리케이션 기동 시점에 스크립트를 Redis에 미리 밀어 넣어 해시 값으로 캐싱(SCRIPT LOAD)해 둡니다.

이후 런타임에는 유저 식별자와 파라미터(현재 시간, 차감할 비용 등)와 함께 이 해시값만 던져서 호출(EVALSHA)합니다.

 

이 방식을 채택하면, 무거운 분산 락 없이도 찰나의 동시성 붕괴를 완벽하게 틀어막으며 초당 수만 건의 트래픽을 가뿐하게 제어하는 진정한 '견고한 방패'를 완성할 수 있습니다.

 

다만 은탄환에도 대가는 있습니다. Lua 스크립트는 Redis의 단일 스레드를 점유한 채 실행되므로, 스크립트가 길어지면 그 시간만큼 다른 모든 클라이언트가 대기합니다. 그래서 스크립트는 짧게 유지해야 하고, 반복문이 들어가는 순간 한 번 더 의심해야 합니다. 그 외에도 Lua 스크립트 자체가 컴파일 시점에 검증이 안된다는 단점도 있겠구요.

6. 장애는 상수다: 우아하게 실패하고, 똑똑하게 회복하는 법

이제 강력한 Rate Limiter를 가지게 되었지만, 인프라 세계에 '절대 고장 나지 않는 시스템'이란 존재하지 않습니다. 전용 Redis 클러스터 자체가 네트워크 단절로 다운된다면 어떻게 대처해야 할까요?

 

이 장은 앞의 내용보다 조금 낯설게 느껴질 수 있습니다. 알고리즘은 정답이 있지만 여기서부터는 정답이 없고 선택만 있기 때문입니다. 그래서 먼저 익숙한 그림 하나를 깔고 가겠습니다.

 

건물 입구의 자동문을 떠올려 봅시다. 정전이 나면 자동문은 둘 중 하나로 동작하도록 미리 설계되어 있습니다. 활짝 열린 채로 멈추거나(그래야 사람이 대피할 수 있으니까), 잠긴 채로 멈추거나(그래야 아무나 못 들어오니까). 소방법이 요구하는 쪽과 보안이 요구하는 쪽이 정반대죠. 중요한 건 둘 중 무엇으로 멈출지를 정전이 나기 전에 정해둔다는 사실입니다. 정전이 난 뒤에 정할 수는 없으니까요.

 

이 장에서 다룰 것이 정확히 그 이야기입니다. 우리 리미터가 고장 났을 때 문을 열 것인가 닫을 것인가, 문이 닫혔다는 사실을 밖의 사람에게 어떻게 알릴 것인가, 그리고 애초에 그 문의 정원을 몇 명으로 정했어야 하는가.

6.1. 최악의 상황, 어떻게 무너질 것인가? (Fail-Open vs Fail-Closed)

• Fail-Closed (방어 최우선): "방패가 깨졌으니, 모든 트래픽을 차단한다." 단 한 건의 오작동도 금전적 손실로 직결되는 크리티컬한 도메인에서 선택합니다.
• Fail-Open (가용성 최우선): "방패가 깨졌더라도, 일단 본진으로 통과시킨다." 대부분의 상용 서비스가 채택하는 방식입니다. 방어막 장애로 멀쩡한 메인 비즈니스까지 셧다운 시킬 수는 없기 때문입니다.

저장소가 죽었을 때 갈라지는 두 갈래

 

 

💡 실무 적용 팁: Fail-Open을 선택하더라도, Redis를 호출할 때 엄격한 Timeout(20ms에서 50ms)과 Circuit Breaker를 설정해야 Rate Limiter가 전체 장애를 유발하는 사태를 막을 수 있습니다.

 

여기서 한 가지만 강조하고 싶습니다. 둘 중 무엇인지는 선택하는 것이지 정해진 정답은 아니라는 점입니다. 따라서 명시적인 정책으로 관리되어야 하겠죠.

6.2. 클라이언트와의 약속 (HTTP 429와 Thundering Herd)

트래픽을 차단하기로 결정했다면, 명확한 시그널을 주어야 합니다. HTTP 상태 코드 429 (Too Many Requests)와 함께 Retry-After 헤더를 반환해야 합니다.

 

단 이때 주의할 점이 있습니다. 

 

수많은 클라이언트가 Retry-After: 5를 지키기 위해 정확히 5초 뒤 일제히 재요청을 보내면 Thundering Herd 현상이 발생합니다. 이를 막기 위해 클라이언트 측에서는 지시받은 시간에 무작위 난수 Jitter를 더해(예: 5.1초, 5.7초) 요청을 분산시키는 로직을 사용할 수 있을 것입니다.

 

거절은 응답이 아니라 계약입니다. 언제 다시 오라고 말해주지 않는 거절은 두 번째 트래픽 파도를 스스로 예약하는 것과 같습니다.

6.3. 숫자는 얼마로 해야 하는가? (임계치 설정의 과학)

임계치는 감이 아니라 시스템의 물리적 한계를 기반으로 도출해야 합니다. 이때 큐 이론의 기본이 되는 리틀의 법칙(Little's Law)을 활용합니다.

 

시스템 내부에 동시에 머물 수 있는 요청의 수(동시성)는 다음과 같이 정의됩니다.

 

L = λ × W

 

( L: 시스템이 동시에 처리 중인 요청 수, λ: 초당 도착하는 트래픽(TPS), W: 요청 하나를 처리하는 데 걸리는 평균 시간(Latency) )

 

안에 머물 수 있는 수와 머무는 시간이 받아들일 수 있는 속도를 정한다

 

 

우리의 메인 DB 커넥션 풀이 100개(L=100)이고, 쿼리 평균 응답 시간이 50ms(W=0.05초)라면, 시스템이 버틸 수 있는 최대 한계 트래픽(λ)은 100 ÷ 0.05 = 2000 TPS가 됩니다.

 

이 임계치를 기준으로 부하 테스트를 거쳐 여유 버퍼를 둔 뒤 한도를 설정하는 것이 정석입니다. 최근에는 백엔드 서버 상태에 따라 실시간으로 한도를 유동 조절하는 적응형 제어 기술로 진화하는 추세로 보입니다.

마치며

솔직히 이 글에서 다룬 것들을 제가 처음부터 알고 설계했던 것은 아닙니다. 오히려 순서를 거꾸로 밟았습니다. 알고리즘부터 골랐고, 그다음에 무엇을 셀지 고민했고, 한도의 숫자는 마지막까지도 감으로 정해져 있었습니다.

 

단일 기능처럼 보이는 Rate Limiter 하나를 설계할 때도 "무엇을 지킬 것인가, 한계점은 어디인가, 실패했을 때는 어떻게 대처할 것인가"를 끊임없이 묻고 답해야 합니다. 제가 경험한 부분은 알고리즘을 마지막에 고르는 편이 처음에 고르는 것보다 훨씬 덜 되돌리게 된다는 점이었습니다.

 

돌아보면 이 글의 순서는 제가 되돌렸던 순서를 그대로 뒤집어 놓은 것에 가깝습니다. 무엇을 막을지 정하고, 숫자를 뽑고, 어디에 둘지 고르고 나면 알고리즘 선택은 거의 자동으로 좁혀집니다. 남는 후보가 몇 개 안 되니까요. 반대로 알고리즘부터 고르면 그 뒤의 모든 결정이 그 선택을 정당화하는 쪽으로 끌려갑니다. 제가 밟았던 길이 정확히 그랬습니다.

 

그리고 뒤의 두 장은 앞의 결정이 전부 맞았다고 해도 여전히 남는 문제였습니다. 읽고 판단하고 쓰는 사이의 찰나를 무엇으로 막을 것인가, 그리고 방패 자신이 쓰러졌을 때 문을 열 것인가 닫을 것인가. 앞의 넷은 설계로 정하는 것이고 뒤의 둘은 각오로 정하는 것에 가깝다는 생각이 듭니다. 열어둘지 닫아둘지에는 기술적 정답이 없고, 우리 서비스가 무엇을 더 무서워하는지가 그 답을 대신 정해주니까요.

 

결국 Rate Limiter를 구현하고 운영한다는 것은 "우리는 무엇을 지키기로 했는가"에 대한 답을 숫자로 환산하는 일일 것입니다. 

이전 글

이 글에서 개념만 짚고 넘어간 다섯 알고리즘의 내부 동작은 이전 편에서 전부 다뤘습니다. 왜 이동 윈도우 로그가 메모리를 터뜨리는지, 토큰 버킷의 소급 계산이 Redis 명령어로는 어떤 모양인지, GCRA의 수식 한 줄이 어떻게 그 모든 것을 대체하는지 궁금하시다면 아래 글을 확인해주세요.

• Ep.1 알고리즘 해부

[시스템 설계 - 레이트 리미터] Ep.1 여섯 개 알고리즘 해부: Redis 명령어까지 내려가서 다 뜯어보

 

시스템 설계 시리즈는 다음 주제로 이어집니다.

참고 자료

• 알렉스 쉬 지음, 이병준 옮김, 《가상 면접 사례로 배우는 대규모 시스템 설계 기초》, 인사이트, 2021. 4장 처리율 제한 장치의 설계. (원서: Alex Xu, System Design Interview: An Insider's Guide)
• AWS Well-Architected Framework, Security Pillar 설계 원칙
• Wikipedia, Rate limiting
• Wikipedia, Generic cell rate algorithm
• ITU-T Recommendation I.371, Traffic control and congestion control in B-ISDN, International Telecommunication Union.
• ATM Forum, Traffic Management Specification Version 4.0 (AF-TM-0056.00).
• Stripe Engineering Blog, Scaling your API with rate limiters (2017)
• Brandur Leach, Rate Limiting, Cells, and GCRA
• redis-cell (GCRA를 구현한 Redis 모듈)
• throttled (GCRA 기반 Go 레이트 리밋 라이브러리)
• 르네의 영속성 컨텍스트, 대기열 시스템 다양한 설계 방법 탐구

대기열 시스템 다양한 설계 방법 탐구 (feat. 레디스와 카프카를 이용한 O(1) 최적화)

 

 

 

 

 

 

A Note on Graphics

이 글에 사용된 모든 다이어그램과 일러스트 이미지는 개념의 시각화를 위해 생성형 AI 도구를 활용해 제작되었습니다.