[Rate Limit - 1] Rate Limit이란? (설계 시 주의사항)

728x90

사이드 프로젝트에서 AWS에 100달러 이상의 과금이 된 적이 있다. 이 때 처음으로 Rate Limit을 도입했고, A/B 테스트를 통해 적절한 임계치를 찾았던 기억이 있다. 최근, 가상 면접 사례로 배우는 대규모 시스템 설계 기초 를 다시 읽으면서, Rate Limit에 대해 깊이 있게 정리해놓지 않았다는 것을 깨닫고, 정리하는 글이 되시겠다(?)

[목차]

1. Rate Limit이란? 설계 시 주의사항

2. Token Bucket, Leaky Bucket 알고리즘

3. Fixed Window, Sliding Window Logging, Sliding Window Counter 알고리즘

Rate Limit

Rate Limit는 클라이언트 또는 서비스가 보내는 트래픽의 처리율(rate)을 제어하기 위한 방법이다.

보통의 웹 애플리케이션이나 모바일 애플리케이션에서 특정 기간 내에 전송되는 클라이언트의 요청 횟수를 제한한다.

API 요청 횟수가 제한 장치에 의해 정의된 임계치(threshold)를 넘어서면 추가로 도달한 모든 호출은 처리가 중단된다.

Rate Limit의 효과

요즘은 특히 AI 구독제 때문에, Rate Limit을 일상 생활에서 더 빈번하게 접할 수 있다.

Rate Limit을 설정하면 다음과 같은 이점이 있다.

서비스 안정성 및 성능의 보장: DoS 공격에 의한 자원 고갈을 방지할 수 있다.
비용 절감: 요청에 대한 처리를 제한하여 트래픽 비용을 절감할 수 있다.
서버 과부화를 막음: 봇의 무분별한 스크래핑, 사용자의 잘못된 이용 패턴으로부터 오는 과요청을 사전에 차단한다.

Rate Limiter의 설계

Rate Limiter는 일반적으로 클라이언트에 두지 않는다. 안정적으로 처리율을 제한할 수 없기 때문이다. 클라이언트 요청은 쉽게 위변조가 가능하기 때문이다.

그렇다면 서버 측에 제한 장치를 두어야 하는데 각자의 서버 환경에 따라 다르게 구성하는 것이 옳다. 소규모 애플리케이션이라면 단순히 API 서버에 단순하게 구성할 것이다.

아래 예시는 Nest에서 제공하는 Throttler 모듈을 사용한 예시다.

// 애플리케이션 전역에 1분에 10번의 요청만 허용한다.
@Module({
  imports: [
     ThrottlerModule.forRoot({
      throttlers: [
        {
          ttl: 60000,
          limit: 10,
        },
      ],
    }),
  ],
})
export class AppModule {}

만약, MSA 환경이라면 Rate Limiter은 보통 API Gateway에 구현된다. 클라우드 서비스의 API Gateway는 사용자 인증, whitelist 관리, SSL termination 등을 지원하기 때문에 추가하기만 하면 되고, 커스터마이징한 API Gateway일 경우에도, 기존의 다른 Gateway의 미들웨어들처럼 추가해서 운영하면 된다.

Rate Limiter을 서버에 두겠다고 선택했다면, 사용중인 프로그래밍 언어의 효율성을 따져보아야 한다.

우선, Rate Limit은 모든 요청마다 실시간으로 실행되기 때문에 극도로 빠르게 동작하여 즉시 consume될 수 있는지 따져야한다. 언어가 느리면 요청 하나하나에 병목이 발생되어 전체 시스템의 성능이 저하되기 쉽다.
수백만 개의 클라이언트 IP, 사용자별 카운터를 메모리에 유지해야하기 때문에 GC의 stop-the-world 시간이 긴 언어는 요청 지연이 생길 수 있다.
수천 개의 동시 요청을 처리하며 카운터를 원자적으로 업데이트해야 하는데, 이 때 효율적인 락 매커니즘과 동시성을 제어할 수 있어야 한다.

만약 위 내용에 적합하지 않은 인터프리터 기반의 싱글스레드 언어인 Python, Ruby등의 언어를 사용하고 있다면

Redis 등의 외부 인메모리 저장소를 활용한 분산 Rate Limiting 구조를 고려해야할 수도 있다.
Envoy, Nginx와 같은 리버스 프록시 기반 Throttling 방식이 더 적합할 수도 있다.

Race Condition에 주의하라

만약, 분산 환경에서 Rate Limiter을 구축했다면, 동시성을 제어하기 위해 Redis와 같은 외부 인메모리 저장소를 활용하여 처리율을 체크하고 있을 것이라 생각한다. Rate Limit도 마찬가지로 분산 환경에서 공통으로 유의해야 할 Race Condition을 고려해야한다. Redis를 사용한다고 가정하고, Race Condition 문제를 어떻게 해결해야할지 간단히 살펴보자.

Race Condition

Rate Limit은 보통 다음 흐름으로 동작한다.

Redis에서 현재 카운터 값을 조회한다.
요청이 임계값 이하인지 확인한다.
조건을 만족하면 카운터를 증가시킨다.

이 흐름은 매우 간단하지만, 분산 환경에서 동시 요청이 많아질수록 Race Condition은 더 자주 발생한다.예를 들어 동시에 두 요청이 Redis에서 카운터를 읽었을 때, 둘 다 조건을 통과하여 값을 증가시킨다면 실제 카운터는 limit을 초과하게 된다. 이는 Rate Limit이 무력화될 수 있다는 의미이다.

위 그림은, 요청 1이 처리되기 이전에 동시 요청된 요청 2가 같이 수행되었다. 여기에는 여러 문제가 있다.

counter은 11이 되어야한다.
max_count는 10이기 때문에 애초에 요청 2는 처리되었으면 안된다.

Race Condition을 해결하기 위해 일반적으로 Lock을 사용할 수 있다. 하지만 Lock이라는 매커니즘은 읽거나 쓰는 도중에 다른 요청은 대기하는 방식이기 때문에 시스템의 성능을 떨어뜨린다는 문제가 있다. 만약 위 예제처럼 Redis를 사용하는 상황이라면 Lua Script를 사용하거나, SortedSet 자료구조를 사용해서 해결할 수 있다.

Lua Script를 통한 Rate Limit 구현

const luaScript = `
  local current = redis.call("GET", KEYS[1])
  if current and tonumber(current) >= tonumber(ARGV[1]) then
    return 0
  else
    current = redis.call("INCR", KEYS[1])
    if tonumber(current) == 1 then
      redis.call("PEXPIRE", KEYS[1], ARGV[2])
    end
    return 1
  end
`

const result = await redis.eval(luaScript, 1, `rate_limit:user:${userId}`, maxCount, ttlMs);

if (result === 0) {
  throw new TooManyRequestsException();
}

Lua Script는 Redis에서 원자적으로 실행되기 때문에 여러 명령을 하나의 트랜잭션처럼 묶어서 실행할 수 있다. 이 때문에 Race Condition으로부터 안전하게 실행될 수 있다.

Lua Script는 실행 중 다른 Redis의 명령을 대기시킨다.
만약 스크립트가 너무 복잡하거나 오래 걸리는 경우, 무한 루프에 빠지는 경우 등을 조심해야한다.
간결하게 작성하여 Redis 처리 성능에 최대한 영향을 끼쳐서는 안된다.

SortedSet을 통한 Rate Limit 구현

Lua Script말고도, SotredSet(ZSET)을 활용한 방법도 있다. 보통 Sliding Window 방식을 ZSET으로 구현할 수 있다.

ZADD로 요청 추가
ZREMRANGEBYSCORE로 현재 시간에서 TTL만큼 지난 요청을 제거
ZCARD로 남아있는 요청 수 계산
limit보다 작으면 허용, 아니라면 차단

local key = KEYS[1]
local now = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local limit = tonumber(ARGV[3])

redis.call("ZREMRANGEBYSCORE", key, 0, now - window)

local count = redis.call("ZCARD", key)
if count >= limit then
  return 0
end

redis.call("ZADD", key, now, now .. "-" .. math.random())

redis.call("PEXPIRE", key, window)
return 1

const now = Date.now();
const result = await redis.eval(luaScript, 1, `rate_limit:user:${userId}`, now, 60000, 10);

ZSET을 이용한 방식의 장점으로는

score를 기록하기 때문에 정확한 시간 단위로 요청 개수를 제한할 수 있다.
시간 경계의 쏠림 문제가 없다. (Fixed Window의 단점을 보완)
Redis 연산이 원자적이기때문에 Race Condition에 안전하다. (Lua 사용 시)

하지만, 이 방식의 단점도 있다. TTL Window 내의 모든 요청 타임스탬프를 score에 저장하기 때문에 메모리 사용량이 높다. 그리고 기본적인 Redis 연산이 많기 때문에 요청이 많을수록 Redis 부하가 커질 수도 있겠다.

Rate Limiter가 사용하는 HTTP 헤더

Rate Limiter을 사용할 때, 다음의 HTTP 헤더를 클라이언트에게 보내야한다.

X-Ratelimit-Limit: 가능한 총 요청의 수
X-Ratelimit-Remaning: 남은 처리 가능 요청 수
X-Ratelimit-Retry-After: 몇 초 뒤에 다시 요청을 해야하는지

아직 규정되지는 않았기 때문에 헤더의 이름 자체를 조금 수정하는 것은 괜찮을지 모르겠으나, 헤더를 사용하여 클라이언트에게 Rate Limit 관련 정보를 보내는 것은 IETF의 권장사항이다. 또한 사용자가 너무 많은 요청을 보내면 429(Too Many Request) 오류를 X-Ratelimit-Retry-After 헤더와 함께 반환하여야 한다.

References.

알렉스 쉬 - 가상면접 사례로 배우는 대규모 시스템 설계 기초[1]

https://www.geeksforgeeks.org/system-design/rate-limiting-in-system-design/