"1분에 100번"이라는 동일한 요구사항을 두고, 누군가는 유저당 8바이트를 할당하고 누군가는 800바이트를 낭비합니다. 서버가 죽어도 끄떡없는 구조가 있는가 하면, 스레드 두 개만 겹쳐도 정합성이 깨지는 구조도 존재합니다. 이 차이는 어디에서 오는 걸까요?

우리는 분산 환경에서 트래픽을 제어해야 할 때 자연스럽게 레이트 리미터(Rate Limiter)를 떠올립니다. 요구사항은 대개 단순합니다. 특정 유저나 IP가 정해진 시간 동안 호출할 수 있는 API 횟수를 제한하는 것입니다.

하지만 이 단순한 규칙을 대규모 트래픽이 몰아치는 서버와 인메모리 데이터베이스(주로 Redis) 위에 올리는 순간, 이야기는 완전히 달라집니다. 같은 문제를 푸는 다섯 가지 알고리즘은 각기 다른 방식으로 메모리를 소모하고 정합성을 방어합니다. 이 알고리즘들이 추상적인 개념을 넘어 물리적인 인프라 위에서 어떻게 동작하고 한계를 맞이하는지, 그 치열한 트레이드오프의 과정을 추적해 봅니다.

1. 준비물: Redis 자료구조 네 가지

알고리즘을 뜯기 전에 재료부터 잠깐 보고 가겠습니다. Redis 자료구조가 이미 손에 익은 분이라면 이 장은 건너뛰고 2장 고정 윈도우 카운터부터 읽으셔도 됩니다.

레이트 리미터 알고리즘은 겉보기에 복잡하지만, 내부를 들여다보면 결국 String, Hash, ZSET, TTL이라는 Redis 기능의 조합으로 작동합니다. 각 자료구조의 고유한 성격이 특정 알고리즘의 동작 방식과 한계를 결정합니다.

1.1. String: 단순 카운터

String은 키와 값을 1:1로 매핑하는 가장 단순한 구조입니다. 하나의 키에 숫자를 저장하고 이를 원자적으로 더하거나 빼는 연산에 특화되어 있습니다.

> SET rate_limit:userA 5
OK
> GET rate_limit:userA
"5"
> INCR rate_limit:userA        # 숫자면 원자적으로 1 증가
(integer) 6

메모리 안에서는 유저 한 명당 독립적인 키가 하나씩 할당됩니다. 복잡한 시간 계산 없이 들어온 요청 횟수만 빠르게 세고 버리는 카운터 기반 알고리즘과 가장 잘 맞습니다.

1.2. Hash: 다중 상태 저장소

키 하나 아래에 여러 개의 필드와 값 쌍을 가질 수 있는 구조입니다.

이름 때문에 오해하기 쉬운데, 여기서 말하는 Hash는 자료구조 수업에서 배우는 해시 테이블과는 다릅니다. Redis의 키 공간 전체가 이미 거대한 해시 테이블이고, Hash 타입은 그 안에 작은 맵을 하나 더 중첩시키는 것에 가깝습니다. Map<String, Map<String, String>>의 안쪽 맵이라고 보면 정확합니다.

이 중첩 구조 때문에 제약도 따라옵니다. 필드의 값으로는 문자열만 들어가므로 안쪽에 또 다른 Hash나 리스트를 넣을 수 없죠. 만료 시간도 필드 단위로는 걸 수 없고 바깥 키 단위로만 걸립니다. 이 제약은 뒤에서 대기열을 다룰 때 ZSET 멤버에 개별 TTL을 걸 수 없다는 문제로 다시 나타납니다.

> HSET rate_limit:userA tokens 9 last_refill 0
(integer) 2
> HMGET rate_limit:userA tokens last_refill
1) "9"
2) "0"

rate_limit:userA라는 키 안에 tokens와 last_refill이라는 두 개의 독립적인 공간이 생깁니다. 잔여 토큰 수와 마지막 보충 시간처럼, 연관된 여러 상태를 동시에 추적하고 갱신해야 하는 알고리즘에서 핵심 상태 저장소 역할을 합니다.

1.3. ZSET (Sorted Set): 시간순 명부

ZSET은 점수를 기준으로 데이터를 오름차순 정렬해 저장하는 집합입니다. 데이터에 순서를 부여하고 특정 구간을 잘라내거나 개수를 세는 작업에 뛰어납니다. 요청이 들어온 시간 자체를 기록하고 다루는 정밀한 윈도우 기반 알고리즘의 뼈대가 됩니다.

명령어 구조를 해부해 보면 활용 방식을 명확히 알 수 있습니다.

ZADD rate_limit:userA 1000 "1000-uuid1"

이 명령어는 네 블록으로 나뉩니다.

ZADD: ZSET에 데이터를 추가하라는 명령입니다.
rate_limit:userA: 대상이 되는 키입니다. 키가 없으면 새로 생성합니다.
1000: 정렬 기준이 되는 점수입니다. 레이트 리미터에서는 보통 요청이 도달한 타임스탬프를 사용합니다. 과거 요청이 앞에, 최신 요청이 뒤로 자연스럽게 정렬됩니다.
"1000-uuid1": 저장되는 실제 값입니다.

즉, 이 명령어 한 줄을 던지면 Redis 키 공간에 rate_limit:userA라는 키가 하나 생기고, 그 안에 점수 1000과 값 "1000-uuid1"이 한 쌍으로 들어갑니다. 다음 요청이 오면 같은 키 안에 또 한 쌍이 붙고, 점수 순서대로 알아서 정렬됩니다.

네 번째 블록에서 값에 단순히 1000을 쓰지 않고 뒤에 uuid를 붙인 이유는 무엇일까요? ZSET은 중복된 값을 허용하지 않는 집합입니다. 만약 유저 A가 1000밀리초에 API를 두 번 호출했고 값에 "1000"만 넣었다면, 두 번째 요청은 중복으로 간주되어 버려집니다. 뒤에 무작위 uuid를 붙여 고유한 문자열로 만들어야 같은 시간에 들어온 요청도 누락 없이 모두 기록됩니다.

즉, rate_limit:userA에 "1000-uuid1"이라는 고유 값을 추가하되 시간순 정렬을 위해 1000이라는 점수를 부여하라는 의미입니다. 타임스탬프를 점수로 활용하면, 과거 일정 시간 이전의 데이터를 순식간에 찾아 삭제하는 연산이 가능해집니다.

1.4. TTL: 자동 만료 메커니즘

TTL은 데이터에 수명을 부여하는 기능입니다. 트래픽이 몰릴 때 무한정 늘어나는 메모리를 통제하기 위해 거의 모든 레이트 리미터 알고리즘이 이 기능에 의존합니다.

> SETEX alive:userA 10 "1"
OK
> TTL alive:userA
(integer) 8

SETEX는 값을 저장하는 동시에 만료 시간을 설정합니다. alive:userA에 "1"을 저장하고 10초 뒤에 삭제하도록 지시하며, 같은 명령어를 다시 보내면 만료 시간은 다시 10초로 연장됩니다.

시간이 만료되면 애플리케이션의 개입 없이 메모리에서 데이터가 삭제됩니다. 이후 조회 시 (nil)이 반환되므로, 시스템은 이를 통해 데이터의 유효 기간이 끝났음을 판단합니다.

키 이름 규칙.
단일 공간을 사용하는 Redis에서는 키 이름 충돌을 막기 위해 콜론을 조합한 도메인:목적:식별자 형태로 이름을 짓습니다.

재료는 여기까지입니다. 이제 이 넷을 조합해 만든 알고리즘 다섯 가지를 차례로 뜯어보겠습니다.

고정 윈도우 카운터, 이동 윈도우 로그, 이동 윈도우 카운터, 토큰 버킷, 누출 버킷 순서입니다. 앞의 알고리즘이 남긴 문제를 다음 알고리즘이 받아서 푸는 흐름이라, 이 순서대로 읽으면 각 방식이 왜 이렇게 생겼는지가 자연스럽게 이어집니다. 그리고 맨 마지막에 GCRA를 봅니다. 앞의 다섯이 저마다 따로 들고 있던 값을 시각 하나로 대신하는 알고리즘입니다.

첫 번째는 가장 단순한 고정 윈도우 카운터입니다.

2. 고정 윈도우 카운터: 카페 쿠폰

2.1. 개념

앞서 Redis의 String 자료구조가 복잡한 시간 계산 없이 요청 횟수만 빠르게 세는 카운터 기반 알고리즘과 가장 잘 맞는다고 이야기했습니다. 그 첫 번째 사례인 고정 윈도우 카운터(Fixed Window Counter)의 작동 방식은 단순합니다. "1분에 10번 호출 가능"이라는 규칙이 있다면, 매 분 정각에 초기화되는 카페 쿠폰을 발급하는 원리와 같습니다. 도장을 열 개 다 찍으면 그 분 안에는 더 이상 도장을 찍을 수 없고, 다음 분으로 넘어갈 때 기존 쿠폰을 버리고 새 쿠폰을 내어주는 식입니다.

2.2. Redis에서 실제로 어떻게 돌아가는가

백엔드 서버가 Redis와 통신하며 트래픽을 제어하는 흐름은 세 단계로 나뉩니다.

1단계: 시간에 종속된 키 설계

유저 ID만으로 키를 생성해서는 안 됩니다. '1분'이라는 고정된 시간 창을 키 자체에 포함해야 합니다. 보통 유닉스 타임스탬프를 60으로 나눈 값을 키에 조합합니다. 현재 시각이 10시 25분이라면 서버는 다음과 같은 키를 만드는 것이죠.

rate_limit:userA:1025

2단계: 단일 INCR 명령어 호출

유저 A의 API 요청이 도달하면 서버는 해당 키의 값을 1 올리라고 명령합니다. 여기서 주의 깊게 볼 지점은 GET으로 현재 값을 읽어온 뒤 애플리케이션에서 더해 SET으로 덮어쓰는 구조가 아니라, 원자적 명령어인 INCR 단 하나만 호출한다는 점입니다.

> INCR rate_limit:userA:1025
(integer) 1

Redis는 해당하는 키가 존재하지 않으면 스스로 값을 0으로 초기화한 뒤 1을 더해 그 결과를 서버로 반환합니다.

3단계: 최초 요청 시점의 EXPIRE 설정

INCR의 결과로 1을 반환받았다는 것은 현재 시간 창(10시 25분)에 들어온 첫 번째 요청임을 의미합니다. 메모리 낭비를 막기 위해 이 키에 수명을 부여합니다.

> EXPIRE rate_limit:userA:1025 60
(integer) 1

이후 10시 25분 내에 유저 A의 요청이 계속 유입되면 서버는 INCR 명령어만 반복해서 전송합니다. 반환값이 10이 될 때까지는 정상 응답을 내려주고, 11번째 요청에서 11을 반환받으면 한도 초과로 판단해 429 Too Many Requests 응답을 보냅니다. 10시 26분으로 넘어가면 서버는 새로운 키인 rate_limit:userA:1026에 INCR을 호출하기 시작하며, 이전의 1025 키는 60초가 경과하여 Redis가 자체적으로 지워냅니다.

2.3. 시간 경계선의 취약점

키에 userA를 명시했으니 유저별 트래픽 제어는 의도대로 동작할까요? 문제는 '누구'를 제어하느냐가 아니라 '언제' 한도가 초기화되느냐에 있습니다.

왜냐하면 이 설계에서 유저의 한도는 시간이 흐르면서 조금씩 회복되지 않기 때문입니다. 59초까지 꽉 채워 쓴 유저도 분이 바뀌는 순간 카운터가 0으로 통째로 리셋됩니다.

시스템이 유저에게 허락한 자원은 '1분당 최대 10번'입니다. 트래픽이 아무리 몰려도 한 유저가 백엔드에 가할 수 있는 최대 부하는 10이어야 정상입니다. 하지만 현실에서는 다음과 같은 상황이 발생합니다.

10시 25분 59초에 10번 요청 → rate_limit:userA:1025 키의 값이 10이 되며 전부 통과
10시 26분 00초에 10번 요청 → 새로운 rate_limit:userA:1026 키에 INCR이 실행되며 역시 전부 통과

서버는 불과 2초 사이에 단일 유저로부터 20번의 요청을 고스란히 받아냅니다. 유저 한 명일 때는 버틸 만하지만, 선착순 이벤트 오픈 시점에 1만 명의 유저가 동시에 경계선에 트래픽을 쏟아내면 순간적으로 20만 건의 부하가 데이터베이스를 강타합니다.

Redis 데이터 구조의 특성을 살펴보면 원인이 뚜렷하게 드러납니다. Redis는 1025 키와 1026 키를 완전히 남남으로 취급합니다. 두 키 사이에 어떠한 관계도 없기 때문에 경계선에서 트래픽이 두 배로 새어 나갑니다.

이 문제를 해결하는 핵심은 시간을 어떻게 자르느냐에 있습니다. 어떻게 할까요? 바로 시간을 미리 구획해두지 않고, 요청이 들어온 시각 자체를 하나씩 적어두는 방식입니다. 그러면 검사 구간이 요청 시점을 따라 계속 움직이니, 넘어가는 순간을 노릴 경계선이라는 것 자체가 없어집니다.

2.4. INCR 명령어와 동시성 안전

여기서, 애플리케이션이 판단 주체인데 어째서 Race Condition이 발생하지 않는지 의문이 들 수 있습니다. 값을 올리고 비교하는 일을 서버 여러 대가 동시에 하고 있으니, 어디선가 숫자가 어긋나는 게 오히려 자연스러워 보입니다. 그런데 고정 윈도우 카운터 설계에서는 동시성 문제가 발생하지 않습니다. 그 이유는 바로 애플리케이션 스레드가 직접 값을 읽어와서 연산하지 않기 때문입니다.

동시성 버그에 취약한 구조는 Redis에서 GET으로 값을 읽고, 애플리케이션 메모리에서 1을 더한 뒤, 다시 SET으로 덮어쓰는 방식입니다. 스레드 두 개가 동시에 1을 읽어가서 둘 다 2로 덮어쓰는 데이터 유실 사고가 일어납니다. 반면 지금 설계는 데이터를 먼저 읽어오지 않고 INCR 명령어 단 하나만 전송합니다.

Redis는 명령어를 한 번에 하나씩 직렬로 처리하는 싱글 스레드 기반 인프라입니다. 애플리케이션 스레드 100개가 동시에 INCR을 호출해도, Redis 내부에서는 큐에 요청을 세워 1, 2, 3, 4 순서대로 숫자를 안전하게 올립니다. 애플리케이션은 각자 반환받은 고유한 결과값만 확인하고 한도 초과 여부를 판별하면 그만입니다.

수치 연산을 애플리케이션 런타임이 아닌 Redis 내부에서 원자적으로 처리하므로 경쟁 상태가 개입할 틈이 차단됩니다. 고정 윈도우 카운터는 이처럼 INCR 하나로 완료되어 구조가 빠르고 동시성 제어에 있어 자유롭습니다. 단지 앞서 다룬 시간 경계선의 트래픽 폭주 문제가 크리티컬 단점으로 부각되는 것이죠.

2.5. EXPIRE 타이밍과 좀비 키 사고

그렇다면 만료 시간(EXPIRE)은 누가, 언제 설정해야 하나요? 이 질문도 짚고가 봅시다.

가장 직관적인 구현은 애플리케이션 서버가 담당하는 것입니다. INCR의 결과값이 1을 가리킬 때 딱 한 번 전송하는 방식입니다. 하지만 이 코드를 그대로 올리면 필연적으로 인프라 장애를 마주합니다.

바로 다음과 같은 상황입니다.

좀비 키(Zombie Key)의 탄생

서버가 INCR rate_limit:userA:1025를 호출
Redis가 1을 반환
서버가 첫 요청임을 인지하고 EXPIRE 60을 전송하려고 준비
바로 이 찰나에 애플리케이션 서버가 메모리 부족(OOM)으로 다운되거나 일시적인 네트워크 단절 발생

EXPIRE 명령어는 영원히 Redis에 도달하지 못합니다. 결과적으로 rate_limit:userA:1025 키는 만료 시간이 설정되지 않은 채 메모리에 영구적으로 방치됩니다. 이런 예외 상황이 누적되면 트래픽을 제어하려고 고안한 로직 탓에 비싼 인메모리 데이터베이스 용량이 가득 차 시스템 전체가 멈추는 비극이 일어납니다.

해결책: 네트워크를 두 번 타지 않는다

따라서,

트래픽 규모가 커질수록 INCR과 EXPIRE를 물리적으로 분리하면 안 됩니다. 두 번의 네트워크 통신 사이에 사고가 발생할 확률을 원천 차단하고자 명령어를 한 덩어리로 묶어서 전송해야 합니다.

첫 번째 대안은 Redis 트랜잭션(MULTI/EXEC)을 활용하는 방법입니다.

MULTI
INCR rate_limit:userA:1025
EXPIRE rate_limit:userA:1025 60
EXEC

두 명령어가 논리적으로 묶여서 실행되므로 중간에 서버가 죽어도 데이터 무결성이 지켜집니다. 다만 매 요청마다 EXPIRE를 불필요하게 덮어쓰는 연산 오버헤드가 발생합니다.

그래서 이 부분에서 우리는 Lua 스크립트를 생각하게 됩니다.

local current = redis.call('INCR', KEYS[1])
if current == 1 then
    redis.call('EXPIRE', KEYS[1], ARGV[1])
end
return current

이 스크립트를 EVALSHA 명령어로 한 번에 전송합니다. Redis는 스크립트 실행을 독립된 원자적 작업으로 취급하며, 코드가 실행되는 동안 다른 명령어가 끼어들지 못하도록 보장합니다. INCR 처리와 EXPIRE 설정 사이에 시스템 장애나 외부 요인이 개입할 확률 자체가 소멸합니다. 사소해 보이는 EXPIRE 타이밍 하나를 통제하기 위해 대규모 시스템의 로직이 결국 Redis Lua 스크립트로 귀결됩니다. 결국 핵심은 원자성이죠.

2.6. Lua 스크립트의 리스크 통제와 트레이드오프

그런데 Lua 스크립트로 넘어가는 순간 다른 문제가 생깁니다. 원자성을 얻은 대가로 개발 환경의 안전망을 잃습니다.

Java나 Node.js 코드 내부에 Lua 스크립트를 단순 문자열로 삽입하면 컴파일러가 문법을 검사해주지 못합니다. 띄어쓰기 오류나 오타 하나만 발생해도 배포 이후 런타임 에러로 발현됩니다. 디버깅도 까다롭습니다. 개발자 경험 관점에서 명백한 안티 패턴처럼 느껴지나요?

자동화된 검사식을 잃는 점은 안정성 면에서 크리티컬한 것이 맞습니다. 그런데,

그럼에도 이 방식이 널리 쓰이는 이유가 있다고 생각합니다. 리스크는 통제될 수 있으니까요. 안전장치를 구축하고 나면, 인프라에서 얻어내는 성능적 이점이 압도적이기 때문이죠. 안전장치는 다음 체계로 구성해 생각해볼 수 있겠습니다.

.lua 파일 분리: 문자열로 하드코딩하지 않고 src/main/resources 등의 경로에 rate_limiter.lua 같은 독립 파일로 분리합니다. IDE의 문법 하이라이팅과 정적 분석의 도움을 받아 기초적인 오타를 예방합니다.
기동 시점 검증(SCRIPT LOAD): 애플리케이션 서버가 실행되며 외부 트래픽을 받기 직전, 초기화 단계에서 미리 .lua 파일을 Redis로 로드합니다. 문법 에러가 존재한다면 서버 기동이 실패하여 배포를 즉각 차단합니다. 유저가 런타임 에러를 겪기 전에 시스템이 먼저 감지합니다.
Testcontainers 통합 테스트: CI 파이프라인에서 실제 Redis 컨테이너를 구동하고 Lua 스크립트를 전송해 예상대로 값이 차감되는지 검증합니다. 이 테스트를 통과해야만 코드를 머지하도록 강제합니다.

이러한 방어 체계를 갖추고 나면 다른 대안들에 비해 Lua 스크립트 방법은 압도적으로 탁월하다는 생각이 듭니다.

분산 락 기법은 락 획득, 데이터 조회, 갱신, 락 해제에 이르는 네트워크 왕복 횟수가 과도해 초당 수만 건의 트래픽을 감당하는 레이트 리미터에서는 그 자체가 병목으로 작용합니다. 앞서 살펴본 Redis 트랜잭션(MULTI/EXEC)은 "A를 읽고 결과가 B라면 C를 수행하라"는 조건 분기를 구현하기 매우 까다로우며, 낙관적 락(WATCH) 기반이므로 동시성 경합이 심할 때 재시도 폭풍을 유발합니다.

그래서 레이트 리미터는 유지보수의 불편함을 일부 내주고 인프라 성능과 동시성 정합성을 사오는 트레이드오프의 산물이라고 생각합니다.

Redis 공식 문서의 INCR 페이지에는 "Pattern: rate limiter" 항목이 따로 실려 있는데, INCR 뒤에 EXPIRE가 붙지 않으면 키가 새어 나간다는 경쟁 상태를 그대로 지적하면서 "이 문제는 INCR과 EXPIRE를 Lua 스크립트로 묶어 EVAL로 보내면 쉽게 고칠 수 있다"고 안내합니다. 방금 우리가 손으로 짚어온 경로가 공식 문서에 그대로 적혀 있는 것을 볼 수 있네요.

Spring 진영도 같은 결론을 내렸습니다. Spring Cloud Gateway의 RequestRateLimiter 필터는 request_rate_limiter.lua라는 스크립트 파일을 리소스 디렉토리에 넣어두고, 이를 RedisScript로 로드해서 씁니다. 앞서 이야기한 .lua 파일 분리와 기동 시점 로드가 프레임워크 안에 이미 그 형태로 들어가 있습니다.

3. 이동 윈도우 로그: 타임라인의 기록

다시 알고리즘 디테일로 돌아와보겠습니다.

이동 윈도우 로그는 시간을 임의로 구획하다 경계선 폭주를 맞은 앞선 알고리즘의 한계를 넘기 위해 고안된 방식입니다. 시간을 네모 반듯하게 자르는 대신, 요청이 들어온 바로 그 순간을 기준으로 정확히 뒤로 1분 동안의 기록만 살핍니다.

25분 59초든 26분 00초든 상관없이 무조건 현재 시점부터 과거 60초의 윈도우만 검사하므로 경계선에 트래픽이 몰리는 문제를 원천 차단합니다.

요청이 들어온 정확한 타임스탬프를 모두 기록하고 다루기 위해 Redis의 ZSET을 활용합니다. "1분에 3번 제한" 규칙을 초 단위 타임스탬프로 시뮬레이션하며 작동 방식을 따라갑니다.

상황 1: 타임스탬프 1000에 첫 요청

> ZADD rate_limit:userA 1000 "1000-uuid1"
(integer) 1

장부에 첫 기록이 적혔습니다. 한도를 넘지 않았으니 통과합니다. 1장에서 살펴본 대로 ZADD 명령어는 네 블록으로 구성되며, 동일한 시각에 들어온 요청이 덮어씌워지는 것을 막기 위해 멤버 값에 고유한 uuid를 붙여 저장합니다.

상황 2: 타임스탬프 1030에 두 번째 요청

> ZADD rate_limit:userA 1030 "1030-uuid2"
(integer) 1

장부에 [1000, 1030] 두 줄이 쌓입니다. 역시 통과합니다.

상황 3: 타임스탬프 1070에 세 번째 요청

이때부터 작동 방식이 달라집니다. 새로운 요청을 장부에 적기 전, 유효기간이 지난 과거 기록부터 청소합니다. 현재 시각 1070에서 허용 기간 60초를 뺀 1010 이전의 타임스탬프는 삭제 대상입니다.

> ZREMRANGEBYSCORE rate_limit:userA 0 1009
(integer) 1

이 명령으로 1000 타임스탬프 기록이 지워집니다. 이제 장부에 남은 기록의 개수를 셉니다.

> ZCARD rate_limit:userA
(integer) 1

남은 기록이 하나뿐이므로, 세 번째 요청 역시 장부에 적고 통과시킵니다.

미리 정해둔 시간표에 맞춰 창문을 짜지 않습니다. 요청이 들어오는 시점마다 뒤로 60초를 계산해 낡은 로그를 지웁니다. 시간이 흐를수록 검사하는 60초의 윈도우가 현재 시간에 맞춰 자연스럽게 이동하므로, 특정 시점의 폭주가 통하지 않습니다.

이 과정을 애플리케이션과 Redis의 관점에서 초 단위 타임라인으로 펼쳐 확인합니다. "60초에 3번" 제한 규칙은 동일합니다.

T = 100초, 첫 번째 요청 (통과)

App → Redis (청소): ZREMRANGEBYSCORE userA 0 40 (100초 기준 60초 전인 40초 이전 삭제. 장부는 비어 있음)
App → Redis (확인): ZCARD userA (0개 반환)
App (판단): 3개 미만이므로 통과
App → Redis (기록): ZADD userA 100 "100-uuid1"
App → Redis (만료): EXPIRE userA 60 (메모리 관리를 위한 TTL 연장)

T = 130초, 두 번째 요청 (통과)

App → Redis (청소): ZREMRANGEBYSCORE userA 0 70 (100초 기록 유지)
App → Redis (확인): ZCARD userA (1개 반환)
App (판단): 3개 미만이므로 통과
App → Redis (기록): ZADD userA 130 "130-uuid2"

T = 150초, 세 번째 요청 (통과)

App → Redis (청소): ZREMRANGEBYSCORE userA 0 90 (지울 기록 없음)
App → Redis (확인): ZCARD userA ([100, 130] 2개 반환)
App (판단): 3개 미만이므로 통과
App → Redis (기록): ZADD userA 150 "150-uuid3"

T = 155초, 네 번째 요청 (차단)

App → Redis (청소): ZREMRANGEBYSCORE userA 0 95 ([100, 130, 150] 모두 유지)
App → Redis (확인): ZCARD userA (3개 반환)
App (판단): 한도를 채웠으므로 429 응답 반환 후 차단
주의: 한도를 넘었으므로 ZADD로 기록하지 않고 요청을 버립니다.

T = 170초, 다섯 번째 요청 (다시 통과)

App → Redis (청소): ZREMRANGEBYSCORE userA 0 110 (100초 기록 삭제)
App → Redis (확인): ZCARD userA ([130, 150] 2개 반환)
App (판단): 과거 기록이 지워져 여유가 생겼으므로 통과
App → Redis (기록): ZADD userA 170 "170-uuid5"

이 타임라인에는 성능과 관련된 중요한 단점이 숨어 있습니다.

요청 한 건을 처리할 때마다 네트워크를 타고 청소, 확인, 기록, 만료 시간 연장까지 3~4개의 명령어가 오갑니다. 트래픽이 몰리면 응답 속도가 무너지고, 청소와 확인 사이에 다른 프로세스가 끼어들어 장부의 개수가 어긋나는 경쟁 상태가 발생합니다.

이 왕복 횟수를 한 번으로 압축하기 위해 전체 명령어를 Lua 스크립트로 묶거나 파이프라인으로 처리해야 하겠죠.

그러나 통신 과정을 묶어 압축하더라도 인프라 차원의 한계는 남습니다. 고정 윈도우는 유저가 1분에 1만 번을 호출해도 숫자 하나만 갱신하면 충분했습니다. 반면 이동 윈도우 로그는 트래픽이 쏟아지면 1030-uuid2, 1031-uuid3 같은 문자열 데이터 1만 줄이 고스란히 ZSET에 쌓입니다.

특히 앞선 T=155초 예제에서는 차단된 요청을 장부에 적지 않았지만, 실제 환경에서 악의적인 어뷰징 시도를 방어하려면 통과된 요청뿐만 아니라 차단된 요청의 타임스탬프까지 장부에 모두 기록해 '시도 자체'를 윈도우에 포함시켜야 합니다. 활성 유저가 수십만 명인 서비스에서 차단된 내역까지 일일이 타임스탬프 문자열로 저장하는 구조는 필연적으로 메모리 폭발을 일으킵니다.

이동 윈도우 로그는 윈도우의 기준을 현재 시각으로 설정해 경계선 폭주를 막는 우아한 논리를 갖췄습니다.

하지만 정확도를 얻기 위해 과거의 모든 기록을 쥐고 있어야 하는 대가로 공간 효율을 크게 잃었습니다. 이 알고리즘은 무거운 타임스탬프를 개별적으로 저장하지 않으면서도 시간의 흐름을 부드럽게 다뤄야 한다는 과제를 남깁니다. 공간을 아끼면서 시간을 다루기 위한 이 치열한 고민은 다음 장의 이동 윈도우 카운터와 토큰 버킷으로 이어집니다.

4. 이동 윈도우 카운터: 수학적 타협

이동 윈도우 로그는 무거운 타임스탬프를 개별적으로 저장하지 않으면서도 시간의 흐름을 부드럽게 다뤄야 한다는 과제를 남겼습니다. 공간을 아끼면서 시간을 다루기 위한 이 고민이 이동 윈도우 카운터에서 하나의 수학적 타협점을 찾습니다.

과거의 정확한 타임스탬프를 모두 버리는 대신, 비율로 과거의 요청 건수를 추정하는 방식입니다. 그래서 Redis에는 오직 두 개의 숫자, 이전 윈도우의 카운트와 현재 윈도우의 카운트만 저장합니다.

4.1. 공식과 타임라인

"1분에 100번 허용"이라는 규칙으로 동작 방식을 따라갑니다.

10:00:00 ~ 10:00:59 (이전 윈도우)

Redis 상태: rate_limit:userA:1000 = 80
10시 00분에는 총 80번의 요청이 통과되었습니다.

10:01:00 ~ 10:01:14 (현재 윈도우 시작)

이전 키: rate_limit:userA:1000 = 80
현재 키: rate_limit:userA:1001 = 20 (요청이 올 때마다 INCR 처리 중)

10:01:15, 운명의 요청

서버는 21번째 카운트를 올리기 전에 비율을 계산합니다.

현재 윈도우의 진행률: 60초 중 15초 경과 → 25%
이전 윈도우의 영향력: 100% - 25% = 75%
과거 1분간의 총 요청 수 추정: (이전 80 × 0.75) + 현재 20 = 60 + 20 = 80번

비율로 계산한 지난 60초간의 추정 요청 수는 80번입니다. 한도인 100번을 넘지 않았으므로 이 요청은 통과되며, INCR rate_limit:userA:1001을 호출해 현재 카운트를 21로 올립니다.

10:01:45, 스파이크 도달

시간이 흘러 현재 윈도우의 카운트가 85까지 올랐을 때 다시 요청이 들어옵니다.

진행률: 60초 중 45초 경과 → 75%
이전 윈도우 영향력 → 25%
과거 1분 추정: (이전 80 × 0.25) + 현재 85 = 20 + 85 = 105번

추정치가 105번이 되어 한도를 초과했습니다. 이 요청은 버려지고, 카운트도 올라가지 않습니다.

이 과정을 관통하는 공식은 다음과 같습니다.

추정치 = (이전 윈도우 카운트 × 이전 윈도우가 겹치는 비율) + 현재 윈도우 카운트

4.2. 장점과 맹점

이 알고리즘은 극도의 메모리 효율을 자랑합니다. 트래픽이 수만 건 몰려와도 Redis에는 숫자 두 개만 기록하면 됩니다. 로그 방식의 메모리 부담을 해결하는 동시에, 고정 윈도우의 경계선 폭주 문제도 매끄럽게 방어합니다. 글로벌 CDN 기업인 Cloudflare 역시 자사의 엣지 서버에서 이 알고리즘을 사용한다고 밝힌 바 있습니다.

하지만 이 방식에는 순진한 가정이 하나 숨어 있습니다. "이전 윈도우의 트래픽이 1분 동안 균일하게 들어왔을 것이다"라는 균등 분포 가정입니다.

만약 이전 윈도우(10시 00분)의 트래픽 80건이 10시 00분 59초 경계에 몰려서 들어왔다면 어떨까요? 실제로는 현재 시점과 아주 가까운 과거에 트래픽이 집중되었으니 강하게 막아야 마땅합니다. 그러나 비율 공식은 "전체의 75% 비율이니 60건 정도 발생했겠군"이라며 실제보다 과소평가해서 요청을 통과시킵니다. 트래픽이 경계 직전에 쏠리면 허용치 이상의 요청이 뚫리는 맹점이 존재합니다.

그렇다면 이 오차는 얼마나 클까요? 다행히 실측된 숫자가 공개되어 있습니다. Cloudflare가 자사 레이트 리미터 구현을 공개하면서 밝힌 바에 따르면, 27만 개 소스에서 발생한 4억 건의 요청을 분석했을 때 잘못 허용되거나 잘못 차단된 요청은 0.003%였습니다.

실제 요청률과 근사치 사이의 평균 차이는 6%였고, 한도를 넘겼는데도 통과한 소스는 3개뿐이었으며 그 초과폭조차 한도의 15% 이내였습니다. 반대로 한도 아래인데 차단당한 소스는 하나도 없었습니다. (How we built rate limiting capable of scaling to millions of domains, Cloudflare)

타임스탬프를 전부 저장하는 대신 숫자 두 개만 들고도 이 정도 정확도가 나온다면, 대부분의 서비스에서는 충분히 감내할 만한 오차 같습니다.

4.3. 이것도 결국 Lua입니다

통신 관점에서 뜯어보면 구조가 제법 까다롭습니다.

GET 이전_키
GET 현재_키
애플리케이션에서 비율 계산
조건 통과 시 INCR 현재_키

이 4단계가 네트워크를 오가며 실행되는 동안 트래픽이 몰리면 필연적으로 경쟁 상태가 발생합니다. 결국 비율 계산 공식 자체를 통째로 Lua 스크립트에 담아 Redis 내부에서 원자적으로 처리해야 합니다. 세 번째입니다.

5. 토큰 버킷: 마법의 옹달샘

시간을 다루면서도 공간을 압축하려던 이동 윈도우 카운터의 고민은 토큰 버킷으로 이어집니다. 토큰 버킷은 허용량이라는 개념을 바구니 속 토큰으로 옮겨놓아, 네트워크 트래픽 제어의 표준으로 굳어진 알고리즘입니다.

5.1. 토큰은 누가 채우나

토큰 버킷의 교과서적 설명은 이렇습니다.

"바구니에 최대 10개의 토큰이 들어갈 수 있고, 1초에 1개씩 토큰이 리필됩니다. 요청이 올 때마다 토큰을 1개씩 꺼내 쓰고, 토큰이 없으면 차단됩니다."

그렇다면 여기서 의문이 생깁니다.

토큰은 누가 채워주는가?

사실 가장 흔하게 생각할 수 있는 방식은 백그라운드에 스케줄러를 띄워 매초 Redis에 INCR을 날려 토큰을 채우는 아키텍처일 것입니다. 그런데 문제가 없을까요? 활성 유저가 100만 명이라면 어떨까요? 매초 100만 번의 쓰기 연산이 발생합니다. 트래픽을 제어하기도 전에 토큰을 채우다가 시스템이 무너지는 구조입니다.

어떻게 해야할까요?

스마트한 방법이 있습니다. 지연 평가(Lazy Evaluation)라는 방식입니다.

평소에는 아무 연산도 하지 않고 버려두다가, 유저의 요청이 들어온 바로 그 시점에 과거 시간을 소급해서 토큰을 한 번에 채워 넣습니다. 토큰 버킷을 "누군가 채워주는 것"으로 이해하면 구현이 되지 않고, "요청 시점에 소급해서 계산하는 것"으로 이해해야 물리적으로 구현됩니다.

5.2. Redis 관점의 타임라인

1장에서 잔여 토큰 수와 마지막 보충 시간처럼 연관된 여러 상태를 동시에 추적해야 하는 알고리즘에서는 Hash가 핵심 상태 저장소 역할을 한다고 이야기했습니다. 토큰 버킷이 바로 그 Hash를 쓰는 알고리즘입니다. 유저마다 다음 두 개의 값을 함께 저장합니다.

tokens: 현재 남은 토큰 개수
last_refill: 마지막으로 토큰을 계산했던 타임스탬프

최대 용량 10개, 1초에 1개씩 리필되는 규칙으로 시간을 따라갑니다.

T = 0초, 첫 요청

App 계산: 첫 요청이므로 토큰 10개를 꽉 채우고 시작합니다.
1개를 소모하여 9개가 남습니다.
Redis 상태: tokens: 9, last_refill: 0

T = 3초, 두 번째 요청 (지연 평가 리필)

App → Redis: HMGET userA tokens last_refill (결과: 9, 0 반환)
App 계산(리필): 마지막 갱신 시점인 0초로부터 3초가 지났으니 토큰 3개를 추가합니다.
9 + 3 = 12개. 하지만 최대 용량이 10개이므로 10개로 컷됩니다.
App 계산(소모): 10개에서 1개를 소모하여 9개가 남고, 요청은 통과됩니다.
App → Redis: HSET userA tokens 9 last_refill 3

T = 3.1초 ~ 3.9초, 트래픽 스파이크

이후 0.9초 동안 9번의 요청이 쏟아집니다.

아직 1초가 채 지나지 않아 새로 리필되는 토큰은 0개입니다.
하지만 바구니 안에는 앞서 남겨둔 9개의 토큰이 고스란히 있습니다. 이를 하나씩 빼서 요청을 모두 처리합니다.
9건 모두 정상 통과되며, Redis 상태는 tokens: 0, last_refill: 3이 됩니다. 이것이 토큰 버킷의 가장 큰 특징인 의도된 폭주 허용입니다.

T = 4초, 바닥난 버킷

마지막 갱신인 3초 시점에서 1초가 지나 토큰 1개가 리필됩니다(현재 1개).
요청 1건을 소모하여 남은 토큰은 0개가 되고 통과됩니다.
만약 0.1초 뒤(T = 4.1초) 또 요청이 온다면? 리필 시간이 지나지 않아 토큰이 0개이므로 이 요청은 차단(429)됩니다.

5.3. 그 두 값은 어디에 저장하나요

Redis에 저장할 때는 아래와 같이 Hash 명령어를 씁니다.

# 저장할 때
> HSET rate_limit:userA tokens 9 last_refill 0
(integer) 2

# 읽어올 때
> HMGET rate_limit:userA tokens last_refill
1) "9"
2) "0"

물론 String 키 두 개로 쪼개서 저장할 수도 있습니다.

SET rate_limit:userA:tokens 9
SET rate_limit:userA:last_refill 0

그럼에도 굳이 Hash로 묶는 데는 명확한 이유가 있습니다.

원자성과 네트워크 효율: 키를 분리하면 네트워크를 두 번 왕복해야 하지만, Hash를 쓰면 HMGET 한 번으로 토큰 개수와 갱신 시간을 오차 없이 동시에 가져옵니다.
깔끔한 메모리 청소: 유저 접속이 뜸해져 데이터를 만료시킬 때, 키가 나뉘어 있으면 EXPIRE도 각각 날려야 해 관리가 꼬입니다. Hash 구조는 EXPIRE rate_limit:userA 60 한 번이면 두 개의 상태가 통째로 날아가 찌꺼기가 남지 않습니다.

"하나의 트랜잭션으로 다뤄져야 하는 연관 데이터는 하나의 Redis 키로 묶는다"는 클래식한 NoSQL 설계 패턴을 따른 것입니다.

5.4. 장단점

토큰 버킷은 로그 방식처럼 수만 개의 타임스탬프를 보관할 필요가 없어 메모리 비용이 극단적으로 가볍습니다. 숫자 두 개만 갱신하면 끝입니다.

순간적인 트래픽 폭주를 유연하게 받아내기도 합니다. 고정 윈도우에서 발생하는 경계선 폭주는 시스템을 위협하는 취약점이지만, 토큰 버킷이 허용하는 폭주는 우리가 설정한 최대 용량 안에서만 통과되는 의도된 폭주입니다.

하지만 이 유연함 이면에는 소급 계산이 부르는 경쟁 상태라는 과제가 남습니다. Redis에서 두 값을 읽어오고(HMGET), 애플리케이션에서 시간차 리필을 계산한 뒤, 다시 쓰는(HSET) 구조이기 때문입니다. 이 과정에 다른 스레드가 개입하면 토큰 개수의 정합성이 즉각 무너집니다. 결국 이 시간차 리필 및 차감 로직 전체를 하나의 Lua 스크립트로 감싸서 동시성 문제를 막아야 합니다. 또 한번 루아스크립트가 등장하네요.

토큰 버킷이 모아둔 토큰으로 순간적인 폭주를 너그럽게 열어준다면, 정반대로 일정하고 엄격한 속도로만 트래픽을 내보내야 하는 상황도 있습니다. 쏟아지는 요청을 통제된 속도로 배출하며 흐름을 쥐는 이 고민은 다음 장의 누출 버킷으로 이어집니다.

6. 누출 버킷: 사실은 대기열

누출 버킷은 토큰 버킷의 완벽한 대척점입니다. 토큰 버킷이 폭주를 수용하는 유연성을 제공했다면, 누출 버킷은 철저하게 고정된 처리 속도를 강제하여 시스템의 예측 가능성을 높입니다.

6.1. 토큰 버킷과 정반대

토큰 버킷이 입장권을 모아뒀다가 한 번에 터뜨리는 방식이라면, 누출 버킷은 아무리 요청이 쏟아져 들어와도 무조건 일정한 속도로만 내보내는 방식입니다.

가장 큰 차이는 바구니 안에 들어가는 내용물입니다. 토큰 버킷의 바구니에는 입장권이 담깁니다. 입장권만 넉넉하다면 유저 10명이 동시에 와도 즉시 통과시킵니다. 반면 누출 버킷의 바구니에는 유저의 요청 그 자체가 담깁니다. 백엔드 시스템 관점에서 이 바구니의 정체는 FIFO 큐입니다.

토큰 버킷은 잔고를 확인하고 차감하여 즉시 처리 여부를 결정하지만, 누출 버킷은 일단 큐에 요청을 넣고 지정된 속도에 맞춰 순차적으로 지연 처리합니다.

6.2. 동작

버킷 크기가 10이고 처리 속도가 초당 1개인 상황을 상정합니다.

평상시 유저가 1초에 1명씩 들어오면 큐에 들어가자마자 바로 처리됩니다. 하지만 1초 만에 7명이 쏟아지는 트래픽 스파이크가 발생하면, 누출 버킷은 7명을 전부 큐에 가둡니다. 서버는 정해진 규칙대로 1초에 1명씩만 꺼내 처리하므로, 7번째 유저는 7초를 기다려야 응답을 받습니다.

만약 큐에 10명이 꽉 차 있는 상태에서 11번째 요청이 오면, 버킷을 넘친 요청은 큐에 진입하지 못하고 곧바로 HTTP 429(Too Many Requests) 오류와 함께 버려집니다.

6.3. 어디에 쓰이나

누출 버킷은 백엔드 서버를 보호하는 데 탁월한 효과를 발휘합니다. 외부 트래픽이 요동쳐도 서버 입장에서는 항상 1초에 1개씩 평온하게 유입되기 때문입니다. 인프라 분야에서는 이렇게 트래픽의 흐름을 다듬는 기법을 트래픽 셰이핑(Traffic Shaping)이라고 부릅니다.

명절 기차표 예매나 한정판 상품 드로우에서 나타나는 "현재 대기 인원은 1,234명입니다"라는 안내 창이 정확히 이 원리로 동작합니다.

6.4. 그럼 이거 그냥 대기열 아닌가요

그냥 대기열 아닌가요?

맞습니다.

누출 버킷의 본질은 비동기 대기열입니다. 물을 담는 바구니가 메모리상의 큐이고, 밑 빠진 독에서 물이 떨어지는 구멍이 바로 서버가 큐에서 데이터를 꺼내 처리하는 고정된 속도입니다.

어떤면에서 보면, 시스템 간 트래픽 완충을 위해 중간에 배치하는 RabbitMQ나 Apache Kafka 같은 메시지 브로커가 누출 버킷의 완벽한 실사판일 수도 있겠습니다.

API 게이트웨이로 초당 1만 건의 요청이 쏟아져도 DB로 바로 전달하지 않고 일단 Kafka에 적재합니다. 뒤에 위치한 컨슈머나 DB는 자신이 소화할 수 있는 속도(예: 초당 100건)로만 메시지를 가져와 처리하며 안정성을 유지합니다.

6.5. 그런데 왜 API 리미터로는 잘 안 쓰나

서버 보호에 탁월함에도 API 리미터로 잘 쓰이지 않는 이유는 최신 유저의 경험을 심각하게 훼손하기 때문입니다.

유저가 새로고침을 연타하는 상황에서, 토큰 버킷은 허용치 내에서 즉시 응답을 반환합니다. 반면 누출 버킷은 앞선 요청들이 큐를 채우고 있을 경우 유저가 긴 시간 동안 로딩 창을 마주해야 하거나 최신 요청이 계속 거절당합니다.

API를 호출한 유저 입장에서는 한도 초과 시 "지금 요청이 많으니 나중에 다시 시도해 주세요"라는 응답을 즉시 받고 상황을 종료하는 편이 낫습니다. 언제 처리될지도 모른 채 무한 로딩을 지켜보고 싶은 유저는 없습니다.

토큰 버킷: 잔고를 확인하고 차감하는 지갑 (즉시 처리 또는 즉시 거절)
누출 버킷: 차례가 올 때까지 기다려야 하는 놀이공원 줄서기 (지연 처리)

실제 제품들이 어느 쪽을 골랐는지 보면 이 차이가 뚜렷해지는 것 같습니다.

AWS API Gateway는 공식 문서에 스로틀링 알고리즘으로 토큰 버킷을 쓴다고 명시해두었습니다. 더 흥미로운 쪽은 Nginx입니다.

limit_req 모듈은 공식 문서에 "the leaky bucket method"라고 적혀 있는 누출 버킷 구현인데, 초과 요청을 지연시키는 기본 동작을 원하지 않으면 쓰라며 nodelay 옵션을 나란히 제공합니다. 누출 버킷을 API 앞단에 세우려면 기다리게 만드는 성질부터 꺼야 한다는 뜻입니다.

6.6. 구현은 두 갈래로 나뉩니다

누출 버킷을 실무에 적용할 때는 처리 대상 API가 동기 방식인지 비동기 방식인지에 따라 구현 형태가 갈립니다.

방식 1: 메시지 브로커를 활용한 대기열 (비동기)

Kafka나 RabbitMQ를 사용하는 구조입니다. 대량 이메일 발송, 동영상 인코딩, 결제 승인 후 포인트 적립 등 유저가 즉각적인 응답을 기다리지 않아도 되는 작업에 적합합니다.

요청이 들어오면 서버는 Redis의 List 구조에 LPUSH leaky_bucket:userA payload 명령어로 데이터를 밀어 넣습니다. 큐 크기를 초과하면 거절합니다.
반대편 워커 서버는 무한 루프를 돌며 지정된 속도로 RPOP을 실행해 데이터를 꺼내 처리합니다.
단, HTTP 응답을 기다리는 유저에게 이 방식을 적용하면 브라우저 타임아웃이 발생할 위험이 큽니다.

방식 2: 시간차를 활용한 수학적 시뮬레이션 (동기)

방금 이야기한 nodelay를 켠 Nginx나 API 게이트웨이가 여기에 해당합니다. 요청을 실제 큐에 가두지 않고, 토큰 버킷에서 썼던 지연 평가 기법을 응용합니다. Redis Hash에는 딱 두 가지 값만 저장합니다.

water: 현재 바구니에 차 있는 물의 양 (현재 큐의 길이)
last_updated: 마지막으로 물 높이를 계산한 시간

처리 속도가 초당 1방울, 버킷 크기가 10방울이라고 할 때 Lua 스크립트는 다음 순서로 실행됩니다.

과거 데이터 조회: Redis에서 water와 last_updated를 가져옵니다.
빠져나간 물의 양 계산: 현재 시간과 last_updated의 시간차를 구한 뒤 초당 누출 속도를 곱합니다. 마지막 요청 이후 5초가 지났다면 5방울이 빠져나간 것으로 계산합니다.
수위 보정: 과거 water에서 빠져나간 양을 차감합니다. 물이 마이너스가 될 수는 없으니 최소값은 0으로 보정합니다.
오버플로우 검사: 방금 들어온 1방울의 요청을 수용할 수 있는지 확인합니다. 수위 + 1 <= 10이면 water를 1 증가시키고 last_updated를 현재 시간으로 갱신하여 덮어쓴 뒤 요청을 통과시킵니다. 수위 + 1 > 10이면 값을 그대로 두고 요청을 429로 거절합니다.

6.7. 잠깐, 큐라면서 왜 안 기다리나요

"분명히 큐라고 정의했는데, 동기 방식에서는 왜 유저를 기다리게 하지 않고 바로 통과시키나요?"라는 모순적인 의문이 생길 수 있습니다.

동기 방식에서 수학으로 흉내 낸 누출 버킷은 실제 대기열을 구축하지 않습니다. 대기열의 포화도를 장부에 숫자로만 기록해 두고, 남은 정원이 없으면 입구에서 즉시 차단하는 방식입니다. 정원이 10명이고 1초에 1명씩만 퇴장할 수 있는 놀이공원을 떠올리면 이해가 쉽습니다.

진짜 큐 (메시지 큐 방식)

손님 15명이 동시에 입구로 도착합니다.
10명은 바로 입장합니다.
나머지 5명은 놀이공원 앞 벤치(메모리 큐)에 앉아서 기다립니다.
1초 뒤에 1명이 퇴장하면 벤치에 있던 1명이 새롭게 입장합니다. 유저 입장에서는 무한 로딩 상태가 됩니다.

수학적 시뮬레이션 (Redis 장부 방식)

손님 15명이 동시에 입구로 도착합니다.
10명은 바로 입장하고 장부에 현재 인원: 10이라고 기록합니다.
나머지 5명은 벤치에 앉히지 않고 직원이 입구에서 429 오류와 함께 곧바로 돌려보냅니다. 대기열 자체를 형성하지 않습니다.

서버는 내부 인원을 일일이 세지 않고 시간차 수학을 활용해 인원을 파악합니다.

[12시 00분 00초] 장부: 사람 10명, 시간 00초
[12시 00분 05초] 새 손님 A가 도착합니다.
서버의 계산: 마지막 기록 이후 5초가 경과했고 1초에 1명씩 퇴장하므로 5명이 나갔다고 추정합니다. 기존 10명에서 현재는 5명이 남아 있다고 판단합니다.
행동: 정원 10명 중 5명이 있으므로 손님 A를 입장시킵니다.
[12시 00분 05초] 갱신된 장부: 사람 6명, 시간 05초

실제 빠져나간 인원을 추적하는 대신, 흐른 시간을 바탕으로 수학적으로 차감 양을 추정하여 장부 숫자만 갱신하는 원리입니다. 큐 없이 누출 버킷을 구현하는 이 로직 역시, Redis에서 두 값을 읽고 시간차를 계산해 덮어쓰는 Lua 스크립트로 귀결됩니다. 이로써 루아 스크립트가 벌써 다섯 번째입니다.

이 장부 기록 방식이 극단적으로 진화하여 진짜 큐처럼 정교해진 아키텍처가 바로 다음 장에서 다룰 Redis ZSET 기반의 가상 대기열입니다.

6.8. ZSET으로 만드는 가상 대기열

대규모 트래픽이 발생하는 수강신청, 기차표, 콘서트 예매 시스템에는 가상 대기열 패턴이 빈번하게 쓰입니다.

List의 LPUSH와 RPOP으로 진짜 큐를 구현하면, 응답을 기다리는 유저는 무한 로딩 화면만 마주하게 됩니다. 이를 극복하기 위해 List 대신 ZSET을 대기열로 활용합니다.

내 앞의 대기자 수 파악 (ZRANK): ZRANK 명령어로 유저 앞의 대기자 수를 파악해 화면에 안내할 수 있습니다.
중복 줄서기 방지: 집합의 특성을 가지므로 새로고침을 반복해도 유저 ID가 중복 등록되지 않고 기존 순서가 유지됩니다.

핵심은 ZSET의 점수를 '요청 인입 타임스탬프'로 설정하는 데 있습니다.

1. 대기열 진입 (ZADD)

ZADD waiting_queue 1718000000000 userA

2. 순위 확인 (ZRANK)

유저의 브라우저가 일정 주기마다 자신의 순위를 폴링합니다. ZRANK의 O(log N) 시간 복잡도 덕분에 대량의 요청에도 신속하게 응답합니다.

ZRANK waiting_queue userA   # → 1234

3. 입장 처리 (ZPOPMIN)

워커가 시스템 수용량을 판단하여 점수가 가장 낮은(가장 먼저 진입한) 인원을 일정량 꺼냅니다.

ZPOPMIN waiting_queue 100

이때 waiting_queue에서 추출된 유저는 active_queue로 이동하여 실제 비즈니스 로직을 타게 됩니다.

시스템 설계 관점에서 이 구조는 UX를 대폭 개선한 누출 버킷과 같습니다. 요청을 즉시 거절하지 않고 큐에 보관한 뒤 서버가 감당 가능한 속도로 꺼내 처리하므로, 백엔드를 보호하는 트래픽 셰이핑 역할을 충실히 수행합니다.

6.9. 브라우저를 꺼버린 좀비 유저

그런데 문제가 없을까요?

대기열 설계 시 운영 환경에서 주로 뒤늦게 발견되는 엣지 케이스가 있습니다.

1장 Redis 자료구조 편에서 Hash는 필드 단위로 TTL을 걸 수 없고 바깥 키 단위로만 걸린다고 언급했습니다. 이 제약은 ZSET 기반 대기열에서도 동일한 문제로 다시 나타납니다. ZSET 내부의 개별 멤버에는 각각 TTL을 부여할 수 없습니다. 유저가 대기 중 브라우저를 종료해도 ZSET 안에는 데이터가 영구히 남습니다. 이로 인해 대기열에 거품이 생기고, 뒤따르는 유저들의 대기 순위가 줄어들지 않는 현상이 발생합니다.

이 문제는 하트비트와 지연 평가를 결합하여 해결할 수 있을 것 같습니다.

하트비트: "나 아직 안 나갔어요"

대기 중인 유저의 브라우저가 주기적으로 폴링할 때 순위 응답과 함께 활성 상태를 나타내는 별도의 키를 갱신합니다.

SETEX alive:userA 10 "1"

이는 userA가 활성 상태이며, 10초 내에 새로운 폴링이 없으면 해당 키를 만료시킨다는 의미입니다. 브라우저가 종료되면 명령어가 멈추고 10초 후 키가 자연스럽게 삭제됩니다.

좀비 퇴치 (지연 평가)

대기열에서 추출: ZPOPMIN waiting_queue 1 → userA가 나옴
생존 검증: GET alive:userA
좀비 판정: 브라우저 종료 후 10초가 지나 키가 만료되었다면 반환값은 NULL입니다. 워커는 해당 유저를 좀비로 판정해 폐기하고, 즉시 다음 유저를 추출하여 검증을 반복합니다.
정상 입장: alive:userB 키가 존재하면 정상 유저로 판정하여 active_queue로 이동시키고 진입 권한을 발급합니다.

어째서 배치 작업으로 사전에 청소하지 않고 추출 시점에 검사하나요?

주기적으로 ZSET을 순회하며 좀비 데이터를 삭제하는 배치 방식은 논리적으로 타당해 보이지만, 앞에서 이야기한 것처럼 실제 운영 환경에서는 금기시되는 패턴으로 분류하고 싶습니다.

대량의 데이터가 적재된 ZSET을 반복 스캔하는 작업은 Redis에 막대한 CPU 부하를 유발할 것이니까요. 트래픽이 폭증하는 상황에서 무거운 스캔 작업이 더해지면 인프라 전체의 장애로 이어질 위험이 큽니다.

따라서 대기 순위의 거품을 일부 허용하더라도, 실제 입장 처리가 일어나는 찰나에 생존 여부를 검증하는 지연 평가 방식이 가장 부하가 적고 안정적입니다.

6.10. active_queue는 무엇이고 어떤 자료구조인가

waiting_queue가 진입을 위해 대기하는 공간이라면, active_queue는 대기열을 통과해 실제 비즈니스 로직에 진입한 유저들의 목록을 의미합니다.

두 큐를 분리하는 데는 명확한 이유가 있습니다.

대기열(waiting_queue, ZSET): 요청의 순서 정렬이 주된 목적입니다. 서비스에 진입하기 전의 대규모 트래픽을 담아두며 DB 접근을 원천 차단합니다.
활성 큐(active_queue): 진입 허가 및 세션 관리가 목적입니다. 실제 트랜잭션을 발생시키고 DB와 상호작용하는 유저들을 통제합니다.

통과된 인원을 제한 없이 뒷단으로 보내면 DB 과부하가 발생합니다. active_queue는 시스템이 안정적으로 처리할 수 있는 최대 수용 인원을 유지하는 안전판 역할을 합니다.

대기열(줄 서기) → 활성 큐(입장 허가) → 실제 서버와 DB 접근. 이 3단계 파이프라인 구조가 대규모 트래픽을 방어하는 핵심 뼈대가 됩니다.

그렇다면 이제 active_queue 구현은 어떻게 해볼까요?

다음 두 가지 자료구조를 고려할 수 있겠습니다.

방식 1: String을 활용한 개별 토큰 발급

단일 자료구조에 데이터를 모으는 대신, 유저별로 일정 시간 동안 유효한 개별 접근 권한을 부여하는 형태입니다.

SETEX active_ticket:userA 300 "1"

userA에게 300초간 서비스에 접근할 수 있는 토큰을 발급했습니다.

장점: 관리가 직관적입니다. 지정된 시간이 지나면 Redis가 토큰을 자동 만료시키며, API 서버는 요청 인입 시 GET 명령어로 토큰 존재 여부만 검증하면 됩니다.
단점: 현재 active_queue에 몇 명의 유저가 남아있는지 전체 규모를 즉시 파악하기 어렵습니다.

방식 2: ZSET을 활용한 활성 풀 관리

현재 진입 인원을 정확히 파악하고 동시 접속 정원을 엄격히 제어해야 한다면 ZSET을 사용합니다. 이때 부여하는 점수의 의미는 대기열과 정반대입니다.

대기열의 점수: 대기열 진입 시간 (과거 타임스탬프)
활성 큐의 점수: 진입 권한 만료 시간 (미래 타임스탬프)

진입 시점 기준으로 5분의 권한을 부여한다면 다음과 같이 저장합니다.

ZADD active_queue <현재시간+300초> userA

이렇게 하면 백엔드 시스템은 다음과 같은 제어력을 얻습니다.

현재 진입객 수 파악(ZCARD active_queue): ZCARD 명령어로 실시간 진입 인원을 파악합니다. 최대 정원 대비 현재 활성 인원을 확인하고, 추가 진입 허용 규모를 동적으로 판단합니다.
시간 초과 유저 일괄 청소(ZREMRANGEBYSCORE): ZREMRANGEBYSCORE 명령어를 활용해 만료 시간이 지난 유저들을 한 번에 정리합니다.

개별 권한 확인만으로 충분하다면 String을, 실시간 인원 모니터링과 엄격한 정원 통제가 필요하다면 ZSET을 선택합니다. 자료구조의 선택이 전체 아키텍처의 성격을 결정짓습니다.

6.11. 대기열 전체 플로우: App, Worker, Redis

전체 구성 요소가 어떻게 맞물려 돌아가는지 시계열 흐름에 따라 추적합니다. 유저 요청을 처리하는 API 서버와 백그라운드에서 대기열 상태를 갱신하는 스케줄러가 중심 역할을 합니다.

T=00:00, 예매 오픈 및 줄서기

[App] 활성 큐 여유 공간 확인 후 유저A를 대기열로 이동, 현재 시간 계산
[Redis] ZADD waiting_queue 1718000000 userA
[Redis] SETEX alive:userA 10 "1" (10초 수명의 생존 확인 키 생성)
[App] 브라우저에 대기열 진입 응답

T=00:03, 순위 확인 폴링

[App] 생존 키 수명 연장
[Redis] SETEX alive:userA 10 "1"
[Redis] ZRANK waiting_queue userA
[App] 반환값 기반으로 현재 대기 순위 응답

T=00:10, 워커의 정원 확보와 퇴장 청소

[Worker] 권한 만료 유저 정리 스케줄링
[Redis] ZREMRANGEBYSCORE active_queue 0 <현재시간>
[Redis] ZCARD active_queue (잔류 인원 파악)
[Worker] 가용 정원 확보량 계산 (예: 100명 추가 진입 허용)

T=00:10.1, 대기열 팝업과 좀비 컷

[Redis] ZPOPMIN waiting_queue 100
[Worker] 추출된 각 유저의 GET alive:userX 생존 검증
[Worker] 키가 만료된 유저는 진입 취소 처리 (좀비 컷)
[Redis] 정상 유저만 입장 처리. ZADD active_queue <현재시간+5분> userA

T=00:12, 예매창 리다이렉트

[Redis] ZRANK waiting_queue userA → NULL (대기열에서 이미 추출됨)
[Redis] ZSCORE active_queue userA → 만료 시간 정상 반환
[App] 활성 큐 진입 확인 후 실제 서비스 화면으로 리다이렉트

이러한 역할 분담을 통해 시스템은 거대한 트래픽 스파이크를 견뎌냅니다. DB는 active_queue에 들어온 제한된 인원의 트랜잭션만 처리하므로 부하를 안정적으로 통제할 수 있습니다.

6.12. ZSET 안에서 실제로 무슨 일이 벌어지는가

ZREMRANGEBYSCORE와 ZADD 명령어가 자료구조 안에서 어떻게 동작하는지 단계별로 확인합니다. 랭킹 시스템에 익숙한 상태에서 '미래의 만료 시간'을 점수로 사용한다는 개념은 직관적으로 와닿지 않을 수 있습니다.

현재 타임스탬프를 1000초로 가정합니다.

ZADD: 만료 시간 기록

유저A 퇴출 시간: 1000 + 300 = 1300초
유저B 퇴출 시간 (20초 뒤 입장): 1020 + 300 = 1320초

ZADD active_queue 1300 userA
ZADD active_queue 1320 userB

명령어 실행 후 Redis 내부의 active_queue는 점수가 낮은 순서, 즉 만료 시점이 가장 가까운 순서대로 정렬됩니다.

순서	유저	점수	의미
1	userA	1300	1300초 시점에 만료
2	userB	1320	1320초 시점에 만료

ZREMRANGEBYSCORE: 만료 데이터 일괄 정리

시간이 지나 현재 시점이 1310초가 되었을 때 워커가 정리를 수행합니다.

ZREMRANGEBYSCORE active_queue 0 1310

이 명령어의 의도는 다음과 같습니다.

"active_queue 내에서 만료 시간(점수)이 0부터 1310 이하인 데이터를 모두 찾아 삭제하라."

데이터베이스는 점수를 순서대로 탐색합니다.

userA (점수 1300): 현재 시간 1310 이하이므로 만료 처리 및 삭제.
userB (점수 1320): 현재 시간보다 크므로 상태 유지.

실행 직후 데이터는 이렇게 변합니다.

순서	유저	점수	의미
1	userB	1320	아직 만료되지 않아 상태 유지

전체 데이터를 순회하며 만료 여부를 검증한다면 심각한 성능 저하가 발생합니다. 하지만 ZSET은 이미 점수 기준으로 오름차순 정렬이 보장된 상태입니다. 앞에서부터 순차적으로 탐색하다가 1310보다 큰 점수가 등장하는 즉시 탐색을 종료하면 됩니다.

불필요한 전체 스캔 없이 O(log N)의 시간 복잡도만으로 대량의 만료 데이터를 신속하게 정리하는 것이 이 구조의 핵심 강점입니다.

지금까지 살펴본 알고리즘들은 저마다 고유한 상태(카운터, 로그, 대기 순위, 만료 시간 등)를 메모리에 쥐고 트래픽을 제어했습니다.

이제 마지막 한 가지 알고리즘을 마지막으로 다뤄보려고 합니다.

이 모든 개별 상태 관리를 시각 하나로 대체하는 GCRA(Generic Cell Rate Algorithm)입니다. GCRA는 각 요청이 도달해야 할 이론적인 도착 시간(TAT, Theoretical Arrival Time)을 계산하여 통제하는 방식으로, 자원 소모를 최소화하면서도 정교하게 트래픽을 다듬어내는 알고리즘입니다.

7. GCRA: 상태 하나로 전부 대체하기

앞서 2장부터 6장까지 여러 알고리즘을 살펴보며 우리는 계속 같은 자리를 맴돌았습니다. 고정 윈도우부터 누출 버킷까지, 어떤 알고리즘이든 현재 상태를 읽고 연산한 뒤 덮어쓰는 과정에서 생기는 Race Condition를 막기 위해 항상 Lua 스크립트를 동원해야 했습니다. 카운터, 타임스탬프 로그, 토큰 잔량 등 저장하고 꺼내야 할 상태 값이 여러 개였기 때문입니다.

이 장에서 다룰 GCRA(Generic Cell Rate Algorithm)는 다섯 번이나 반복된 이 교착 상태를 끊어냅니다. 앞선 알고리즘들이 저마다 쥐고 있던 복잡한 상태를 전부 버리고, 오직 시각 하나만을 기록하여 문제를 돌파합니다.

무엇을 저장하고 무엇을 버릴 것인가, 연산을 지금 할 것인가 미룰 것인가, 공간을 사용할 것인가 시간을 다룰 것인가. GCRA는 이 세 가지 판단 렌즈가 한 점에서 만나는 흥미로운 설계 사례입니다.

7.1. 핵심 철학

GCRA는 원래 ATM(Asynchronous Transfer Mode) 네트워크 환경에서 셀 트래픽을 제어하기 위해 탄생한 알고리즘입니다. 웹 API 레이트 리미터로서의 가능성은 Brandur Leach의 개인 블로그와 throttled 라이브러리를 통해 널리 알려졌습니다. (참고로 Stripe가 공식 기술 블로그를 통해 도입했다고 밝힌 알고리즘은 토큰 버킷입니다. GCRA와 자주 혼동되지만 명확히 구분해야 할 것 같습니다.)

핵심 발상은 아주 단순합니다. "바구니에 토큰이 몇 개 남았는지 일일이 세는 대신, 이 유저가 다음번에 호출해도 되는 미래의 시각 딱 하나만 기록해 두면 어떨까?"

GCRA에서는 이 미래의 시각을 TAT(Theoretical Arrival Time, 이론적 도착 시간)라고 부릅니다.

필요한 설정값은 두 가지뿐입니다.

T (Emission Interval): 1건 처리 간격 (초당 1건이면 T = 1초)
τ (Tolerance): 트래픽 스파이크 허용 오차 (토큰 5개 분량이면 τ = 5초)

7.2. 타임라인

T = 1초, τ = 5초로 설정한 환경의 동작 타임라인입니다.

1. 첫 요청 (t = 10초)

Redis에 기록이 없으므로 요청을 통과시키고, 다음 요청 허용 시각을 1초 뒤인 11초로 지정합니다.
Redis 저장: userA:TAT = 11 (토큰 잔량 같은 상태는 없습니다.)

2. 평화로운 요청 (t = 11초)

Redis에서 읽어온 TAT 값 11에 정확히 맞춰 요청이 도착했습니다. 요청을 통과시키고 다음 TAT를 현재 시각에 T를 더해 12로 갱신합니다.

3. 트래픽 스파이크 (t = 12초에 4번 연속 요청)

토큰 버킷은 모아둔 토큰을 차감하지만, GCRA는 TAT를 미래로 밀어내는 방식을 사용합니다.

1번째 처리 → 새 TAT = 13
2번째 처리 → 새 TAT = 14
3번째 처리 → 새 TAT = 15
4번째 처리 → 새 TAT = 16
검증: 가장 멀리 밀려난 TAT(16)에서 현재 시간(12)을 빼면 4초가 나옵니다. 허용 오차 τ(5초) 이내에 있으므로 4건 모두 통과합니다.

4. 한도 초과 (t = 12.1초)

이번 요청을 받으면 새 TAT는 16 + 1 = 17이 됩니다.
검증: 17 - 12.1 = 4.9초로 여전히 τ(5초) 안쪽에 위치하여 통과합니다.
하지만 직후에 또 요청이 와서 새 TAT가 18이 된다면, 18 - 12.1 > 5가 되어 차단(429) 응답을 내립니다. 차단된 요청은 TAT를 갱신하지 않고 그대로 버려집니다.

7.3. 수식 한 줄

위의 모든 과정은 복잡한 시간차 계산 없이 다음 수식 한 줄로 압축됩니다.

TAT_new = max(t_now, TAT) + T
차단 조건: TAT_new - t_now > τ

이 단순한 수식은 앞선 알고리즘들의 한계를 훌륭하게 극복합니다. 토큰 버킷처럼 여러 필드를 Hash로 유지할 필요 없이 단일 String 키 하나에 숫자 하나만 저장하면 되어 메모리 효율이 극대화됩니다. 원자성을 위해 여전히 Lua를 사용하지만, 내부 연산이 극적으로 단순해져 Redis CPU 부하도 현저히 낮아집니다.

또한 대기열 없이 즉시 응답하는 토큰 버킷의 장점과 트래픽을 일정 속도로 평탄화하는 누출 버킷의 장점을 동시에 달성합니다.

7.4. Lua 구현

이 알고리즘의 실제 루아 스크립트 구현도 한번 살펴보겠습니다.

토큰 버킷이 HMGET으로 여러 필드를 가져와 리필을 계산하고 다시 HSET으로 덮어쓰는 구조였다면, GCRA 스크립트는 매우 짧죠.

-- KEYS[1] : rate_limit:TAT:userA (TAT를 저장할 단일 키)
-- ARGV[1] : now (현재 시간, 밀리초)
-- ARGV[2] : T (1건 처리 간격, 밀리초)
-- ARGV[3] : tau (Burst 허용 오차, 밀리초)

local tat_key = KEYS[1]
local now = tonumber(ARGV[1])
local T = tonumber(ARGV[2])
local tau = tonumber(ARGV[3])

-- 1. 기존 TAT 읽어오기 (없으면 0으로 초기화)
local current_tat = tonumber(redis.call('GET', tat_key) or 0)

-- 2. 새 TAT 계산: max(현재 시간, 기존 TAT) + 간격
local new_tat = math.max(now, current_tat) + T

-- 3. 차단 조건 검사
if new_tat - now > tau then
    -- 허용치 초과! 값은 건드리지 않고 즉시 0 반환 (429)
    return 0
end

-- 4. 통과 처리 및 저장 (TTL은 새 TAT가 지나는 순간까지)
local ttl = new_tat - now
redis.call('PSETEX', tat_key, ttl, new_tat)

return 1

이 코드는 복잡한 Hash 연산 없이 GET과 PSETEX 단 두 번의 I/O만 발생시킵니다. 조건문도 math.max와 뺄셈 연산 후 단일 분기를 타는 구조라 논리적 오류가 발생할 가능성이 매우 작습니다. 계산된 new_tat 시점에 맞춰 수명을 지정하므로 별도의 배치 작업 없이 스스로 데이터를 정리하는 이점도 큽니다.

7.5. Redis 메모리 안에서 실제로 일어나는 일

GCRA는 ZSET 같은 복잡한 자료구조 대신 단일 String 키 하나만 사용합니다. Redis 안에는 오직 세 가지 정보만 기록됩니다.

Key: rate_limit:TAT:userA
Value: 17000 (다음번 허용 시간, 밀리초)
TTL: 4900 (현재부터 저 허용 시간까지 남은 시간)

데이터는 누적되지 않으며 오직 Value와 TTL 두 숫자만 최신화됩니다. (설정: T = 1초, τ = 5초)

시점	유저 행동	Redis 상태 (Value / TTL)	서버 판단
10.0초	첫 요청	11.0초 / 1.0초	통과 (200)
12.0초	4연속 요청	16.0초 / 4.0초	4건 모두 통과
12.1초	또 1건	17.0초 / 4.9초	통과 (200)
12.1초 직후	1건 더 (한도 초과)	상태 변화 없음	차단 (429)
17.0초	유저가 쉼	데이터 소멸 (nil)	-

요청이 1만 건 들어와도 키 하나에 숫자 하나만 덮어씌워집니다. 특히 한도를 넘겨 차단당하는 시점에는 쓰기 작업 자체가 일어나지 않아 악성 트래픽 공격에도 Redis 부하가 안정적으로 유지됩니다. 유저가 멈추고 17.0초가 되면 TTL이 0이 되어 키는 메모리에서 자연스럽게 사라집니다.

7.6. 그런데 TTL은 왜 거는 건가요

수식만 보면 TAT 값 하나로 모든 연산이 가능한데 굳이 TTL을 설정하는 이유에 의문이 들 수 있습니다. TTL은 연산을 위한 값이 아니라 메모리 고갈을 막는 자동 청소 장치입니다.

한 번 방문하고 이탈한 유저의 키를 무한정 방치하면 메모리 누적으로 이어집니다. 삭제의 기준점은 현재 시간이 유저의 TAT를 추월하는 시점입니다. 이때 유저는 그동안 쌓인 패널티를 모두 소진하고 완전히 깨끗한 초기 상태로 돌아옵니다.

유저의 TAT가 17.0초이고 현재 시간이 12.0초라면, 서버는 값을 기록할 때 TAT - 현재 시간에 해당하는 5초를 TTL로 부여합니다. 5초 뒤 키가 삭제되고 유저가 20.0초에 다시 요청을 보내면, Redis에는 데이터가 없고 Lua 스크립트는 이를 초기 상태로 간주하여 처음부터 새로 연산합니다. 메모리 공간을 회수하면서도 알고리즘의 동작은 동일하게 유지됩니다.

7.7. 그래서 단점은 없나요

그렇다면 이 알고리즘이라고 완벽할까요? 당연히 아니겠죠.

이론적으로 훌륭한 알고리즘도 트래픽이 몰아치는 비즈니스 환경에서는 예기치 않은 문제를 일으킵니다. GCRA 도입 시 고려해야 할 세 가지 제약 사항이 있습니다.

1. 잔여 호출 횟수 전달의 까다로움

오픈 API 환경에서는 응답 헤더에 X-RateLimit-Remaining을 포함하는 것이 관례입니다. 토큰 버킷은 남은 토큰 개수를 그대로 넘기면 되지만, GCRA는 미래의 타임스탬프만 보관하므로 잔여 횟수를 구하려면 매번 역산을 수행해야 합니다.

Remaining = floor( (τ - (TAT - t_now)) / T )

고부하 상태에서 이 연산을 매번 수행하는 것도 부담이며, 바구니에 담긴 토큰이라는 직관적인 개념과 1:1로 대응하지 않아 외부 클라이언트에게 동작 방식을 설명하기 어렵습니다.

2. 요금제 변경 시 발생하는 유령 패널티

유저가 초당 1건(T=1000ms) 무료 플랜을 사용하다 한도를 소진하여 TAT가 미래 50초 뒤로 밀려난 상태라고 가정합니다. 유저가 방금 프리미엄 플랜(T=100ms) 결제를 마쳤더라도, Redis에 기록된 TAT는 과거 룰 기준으로 계산된 과거의 값입니다. 유저는 업그레이드를 완료했음에도 50초가 지날 때까지 계속 429 차단 응답을 받게 됩니다.

이를 해결하려면 요금제 변경 트랜잭션이 발생할 때 이벤트 브로커를 활용해 Redis에 저장된 해당 유저의 TAT 키를 강제로 삭제(DEL)하는 파이프라인을 두어야 합니다.

3. 분산 환경의 시계 드리프트(Clock Drift)

앞의 스크립트에서는 앱 서버가 측정한 현재 시간(now)을 인자로 넘겼습니다. 하지만 여러 대의 서버가 동작하는 분산 환경에서는 시스템 시각이 미세하게 엇갈립니다. A 서버는 10.00초, B 서버는 10.05초를 가리킬 때 로드밸런서가 요청을 분산시키면 기준 시각이 튀어 동시성 제어가 꼬이게 됩니다.

이 문제는 앱 서버의 시계를 신뢰하는 대신, Lua 스크립트 내부에서 Redis 내장 시각을 직접 호출하여 방지할 수 있습니다.

-- 앱 서버가 던져준 시간 대신 Redis 메인 스레드의 시간을 사용
local redis_time = redis.call('TIME')
local now = tonumber(redis_time[1]) * 1000 + math.floor(tonumber(redis_time[2]) / 1000)

이렇게 수정하면 모든 연산이 단일 Redis 노드의 시계를 기준으로 정렬되어 서버 간 시간 오차를 원천 차단합니다.

GCRA는 직관성과 동적 룰 변경의 유연성을 조금 덜어내는 대신, 메모리와 성능을 극한으로 끌어올리는 선택입니다. 엣지 케이스를 보완하는 아키텍처가 결합된다면 매우 단단하고 신뢰할 수 있는 리미터로 작동합니다.

8. 마치며

여섯 가지 알고리즘의 형태를 모으면 이렇습니다.

알고리즘	Redis 자료구조	저장하는 상태	핵심 명령어	한계점
고정 윈도우 카운터	String	카운터 하나	`INCR`, `EXPIRE`	경계 구간에서 한도의 2배 통과
이동 윈도우 로그	ZSET	허용 구간 내 모든 요청 시각	`ZREMRANGEBYSCORE`, `ZCARD`, `ZADD`	트래픽에 비례해 메모리 폭증
이동 윈도우 카운터	String 2개	현재와 직전 구간의 카운터	`GET`, `INCR`	직전 구간 트래픽의 균등 분포 가정이 깨지면 오차 발생
토큰 버킷	Hash	잔량과 마지막 갱신 시각	`HMGET`, `HSET`	요청 시점의 소급 계산으로 인한 경쟁 상태
누출 버킷	List 또는 Hash	대기열 큐 또는 수위 값	`LPUSH`, `RPOP`	트래픽을 지연 처리하므로 동기 API에 부적합
GCRA	String	다음 허용 시각 하나	`GET`, `PSETEX`	남은 횟수 직관적 역산 불가, 시계 드리프트에 취약

여섯 개의 알고리즘을 뜯어보며 도입부의 문제의식으로 돌아갑니다. "1분에 100번"이라는 동일한 요구사항을 두고 어떤 알고리즘은 유저당 800바이트를 낭비했고 어떤 알고리즘은 8바이트만 썼습니다. 그 극적인 차이는 시스템을 바라보는 관점에 따라 갈렸습니다.

무엇을 저장하고 무엇을 버릴 것인가. 이동 윈도우 로그는 100번의 타임스탬프를 모두 쥐고 있으려다 메모리 폭증을 맞았습니다. 반면 GCRA는 과거의 기록을 전부 버리고 오직 '다음 허용 시각' 하나만 남겼습니다.

계산을 지금 할 것인가 미룰 것인가. 토큰 버킷은 주기적으로 토큰을 채우지 않습니다. 요청이 도착한 순간에야 과거부터 지금까지 쌓였어야 할 잔량을 소급해 계산합니다. 백그라운드 타이머가 져야 할 갱신 부담을 요청 시점의 연산으로 미뤘습니다.

공간을 다룰 것인가 시간을 다룰 것인가. 고정 윈도우 카운터가 허용된 횟수라는 공간을 차감할 때, 누출 버킷과 GCRA는 요청과 요청 사이의 시간 간격을 통제했습니다. 횟수 제한을 시간의 문제로 치환하면서 경계 오차를 극복했습니다.

설계의 출발점은 달라도 Lua 스크립트가 알고리즘의 핵심 자원으로 사용된 점도 특이합니다. 초당 수만 번 '읽고, 판단하고, 쓴다'는 동작의 원자성을 락 없이 보장하려면 분산 환경에서는 결국 Lua 스크립트로 수렴한 것 말이죠.

다음 편

다음 편은 이 알고리즘들을 고르기 전에 끝냈어야 할 결정을 다루보려고 합니다.

무엇을 왜 막을 것인가, 규모를 어떻게 추정할 것인가, 방어선을 어디에 칠 것인가, 그리고 "그래서 한도는 몇으로 정할 것인가".

알고리즘을 여섯 개를 다 안다면 모든 문제가 풀릴까? 이에 대한 답을 찾아가보겠습니다.

참고 자료

알렉스 쉬 지음, 이병준 옮김, 《가상 면접 사례로 배우는 대규모 시스템 설계 기초》, 인사이트, 2021. 4장 처리율 제한 장치의 설계. (원서: Alex Xu, System Design Interview: An Insider's Guide)
Redis 공식 문서, Commands
Redis 공식 문서, Scripting with Lua
Redis 공식 문서, INCR - Pattern: rate limiter
Spring Cloud Gateway, request_rate_limiter.lua
Cloudflare Blog, How we built rate limiting capable of scaling to millions of domains
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).
Brandur Leach, Rate Limiting, Cells, and GCRA
redis-cell (GCRA를 구현한 Redis 모듈)
throttled (GCRA 기반 Go 레이트 리밋 라이브러리)
Stripe Engineering Blog, Scaling your API with rate limiters
르네의 영속성 컨텍스트, 대기열 시스템 다양한 설계 방법 탐구

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

이 글에 대해서항해 플러스 백엔드 5기 과정을 수료하며 대기열 기반의 예약 시스템을 구현했습니다. 본 글은 해당 프로젝트를 진행하며 고민하고 결정했던 내용을 다룹니다. 주요 내용으로는

upcurvewave.tistory.com

A Note on Graphics

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

저작자표시 비영리 변경금지 (새창열림)

'시스템 디자인' 카테고리의 다른 글

[시스템 설계 - DynamoDB] Ep.3 지운 물건이 되살아납니다: 다이나모 아키텍처 15년과 복잡성 보존의 법칙 (0)	2026.07.29
[시스템 설계 - 레이트 리미터] Ep.2 방패의 설계도: 트래픽 폭주 속에서 무엇을, 어디서 막을 것인가 (0)	2026.07.28

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