[Rate Limiting] Token Bucket 알고리즘

 

 개발을 하다 보면 외부 API를 수없이 사용하게 되고 고려하지 않으면 요청한 API 서버로부터 `429 Too Many Request`라는 곤란한 응답을 받게 된다.

 Rate Limting은 API Client만 고민하는 것이 아닌 요청을 받고 응답을 내려주는 API Server로부터 고려된 것이고 API Server는 DoS 공격과 같은 공격에 대해 대비하고 서버의 응답 처리량을 관리하기 위해서는 Rate Limiting은 필수로 고려되어야 하는 부분이다.

 나는 얼마 전에 429 응답을 마주하게 되었고 요청을 받는 입장이 아닌 요청을 하는 입장에서 어떻게 요청량을 관리해야 될지에 대한 방법론을 몇 가지 알아보려고 한다. (Server와 Client의 방법론은 크게 다를 것 없다.)

 

429 Too Many Request

- https://developer.mozilla.org/ja/docs/Web/HTTP/Status/429

 

Rate Limiting?

Rate Liming은 요청을 보내거나 받는 요청의 속도를 제한하여 요청을 처리하는 주체를 보호하게 할 수 있다.

예를 들어 DoS 공격을 예방하고 웹 스크래핑 봇과 같은 알려지지 않은 요청자로부터 과도한 요청을 예방할 수 있다.

 

Rate Limiting의 구현하는 알고리즘은 여러 가지가 존재하지만 큰 주제는 "특정 시간 동안 특정량의 요청을 보내거나 받는다."이다.

 

오늘은 Rate Limiting 알고리즘 중 "Token Bucket" 알고리즘에 대해 작성하려고 한다.

Token Bucket 알고리즘

Token Bucket의 동작은 직역의 의미에서 알 수 있듯이 한정된 양의 토큰 수를 정의하여 바구니에 담아두고 요청이 이루어질 때마다 토큰을 소비하여 요청을 진행한다.

만약 바구니 내의 토큰이 모두 소비되면, 요청이 완전히 거부되거나 바구니 내에 토큰이 채워질 때까지 요청은 기다리게 된다.

- 특정 시간 내에 요청할 수 있는 수를 토큰 수로 정의

- 요청마다 토큰을 소비

- 토큰이 모두 소비되면 요청 거부 혹은 요청 대기

- 특정 시간이 지나면 토큰 수 초기화

https://giacomomaire.com/how-to-implement-rate-limiting-in-nodejs-express-token-bucket-sliding-log-algorithm-part-1-2/

 

Token Bucket 알고리즘의 장단점

장점

1. 버스트 트래픽 허용

  - 버킷에 토큰이 충분히 쌓여있다면, 짧은 시간 동안 평균 처리 속도를 초과하는 요청도 처리가 가능하다. 이는 갑작스러운 트래픽 증가에 유연하게 대응이 가능하게 한다.

2. 평균 처리 속도 제한

  - 토큰이 일정 속도록 버킷에 추가되기 때문에, 정기적으로 평균 처리 속도를 효과적으로 제한할 수 있다.

3. 메모리 효율성

  - 버킷의 크기와 현재 토큰 수만 관리하면 되므로, 구조가 단순하여 메모리 사용이 효율적이다.

단점

1. 동시성 문제

  - 분산 환경에서 여러 요청이 동시에 들어올 경우, race confition이 발생할 수 있다. 이는 정확한 속도 제한을 보장하기 어렵게 할 수 있다.

2. 정확한 시간 간격 보장의 어려움

  - 평균 처리 속도를 제한하지만, 정확한 시간 간격으로 요청을 처리하는 것을 보장하지 않는다.

 

Token Bucket 구현

아래 Tokenbucket 클래스는 토큰 버킷을 정의하며, ratelimitFunction에서 인자로 받은 함수의 사용을 제한하고 있다.

// 1. TokenBucket 클래스는 버킷의 용량, 현재 토큰 수, 마지막으로 채운 시간, 초당 채우는 토큰 수를 관리
class TokenBucket {
  constructor(capacity, fillPerSecond) {
    this.capacity = capacity;
    this.tokens = capacity;
    this.fillPerSecond = fillPerSecond;
    this.lastFilled = Date.now();
  }

  // 2. refill 메서드는 마지막으로 토큰을 채운 이후 경과한 시간에 따라 토큰을 추가
  refill() {
    const now = Date.now();
    const timePassed = (now - this.lastFilled) / 1000;
    const tokensToAdd = timePassed * this.fillPerSecond;
    this.tokens = Math.min(this.capacity, this.tokens + tokensToAdd);
    this.lastFilled = now;
  }

  // 3. take 메서드는 요청이 들어올 때마다 토큰을  사용하려고 시도, 토큰이 있으면 true를, 없으면 false를 반환
  take() {
    this.refill();
    if (this.tokens >= 1) {
      this.tokens -= 1;
      return true;
    }
    return false;
  }
}

// 4. rateLimitFunction 함수는 TokenBucket을 생성, 주어진 함수를 래핑하여 반환
function rateLimitFunction(fn, capacity, fillPerSecond) {
  const bucket = new TokenBucket(capacity, fillPerSecond);
  
  return function(...args) {
    if (bucket.take()) {
      return fn.apply(this, args);
    } else {
      console.log('Rate limit exceeded. Please try again later.');
      return null;
    }
  };
}

// 사용 예시
function expensiveOperation(x) {
  console.log(`Performing expensive operation with ${x}`);
  // 여기에 실제 비용이 많이 드는 작업을 수행합니다.
}

// 초당 2회, 최대 버스트 5회로 제한된 함수 생성
const limitedExpensiveOperation = rateLimitFunction(expensiveOperation, 5, 2);

// 테스트
function testRateLimit() {
  for (let i = 0; i < 10; i++) {
    setTimeout(() => {
      limitedExpensiveOperation(i);
    }, i * 200); // 0.2초 간격으로 10번 호출
  }
}

testRateLimit();

 

 

---

 

 

Rate Limiting은 운영 중인 서버의 혹은 요청하는 입장에서도 필수로 챙겨야 되는 장치이다. 이러한 기능은 rate limiting 관련된 npm 모듈도 다양하게 있고 nestjs 프레임워크에서도 간단하게 동작이 가능하도록 기능을 추가해 두었다. 그러나 구현 상 어려운 부분이 없으니 설계 중인 서비스 특성에 따라 직접 구현해 보는 것도 좋은 선택일 것 같다.

 

참고

429 Too Many Requests - HTTP | MDN

 

express-rate-limit

Documentation | NestJS - A progressive Node.js framework