# 처리율 제한 장치

## 개요

클라이언트 또는 서비스가 보내는 트래픽이 임계치를 넘어서면 추가 트래픽은 차단하는 장치

### 예시

- 사용자는 초당 2회 이상 새 글을 올릴 수 없다.

- 같은 IP 주소로는 하루에 10개 이상의 계정을 생성할 수 없다.

- 같은 디바이스로는 주당 5회 이상 리워드를 요청할 수 없다.

### 장점

- DoS 공격에 의한 자원 고갈을 방지한다.

- 추가적인 API 요청이나 서버 자원을 아껴 비용을 절감한다.

- 봇이나 잘못된 트래픽에서 오는 트래픽으로 인한 서버 과부화를 막는다.

## 처리율 제한 알고리즘

### 토큰 버킷 알고리즘

**동작 원리**

- 요청은 버킷에 있는 토큰을 하나 가져가 실행을 인가받는다.

- 버킷에 남아있는 토큰이 없다면 해당 요청은 폐기한다.

- 토큰 공급기(refiller)는 매초마다 n개씩 버킷에 토큰을 채워넣는다.

- 단, 버킷에 있는 토큰의 수가 최대치를 넘으면 더이상 담을 수 없다.

![Image](https://upload.cafenono.com/image/slashpageHome/20240820/134339_eydiaJo5qIK9NUjskQ?q=80&s=1280x180&t=outside&f=webp)

**인자(parameter)**

- **버킷 크기** : 버킷에 담을 수 있는 토큰의 최대 개수

- **토큰 공급률** : 초당 몇 개의 토큰이 버킷에 공급되는가

**사례**

- 통상적으로 API 엔드포인트마다 별도의 버킷을 둔다. ⇒ 즉, 사용자 혹은 IP 주소을 기준으로 둘 수 있다.

- 전체 시스템 처리율을 제한하고 싶다면 모든 요청이 하나의 버킷을 공유하도록 해야 할 것이다.

**장점**

- 구현이 쉽고 메모리 사용이 효율적이다.

- 트래픽 버스트를 처리할 수 있다. 

**단점**

- 버킷 크기와 토큰 공급률을 튜닝하기가 어렵다.

### 누출 버킷 알고리즘

 과 유사하지만 버킷 대신 FIFO 큐를 사용해 요청 처리율을 고정시킨다.

**동작 원리**

- 요청은 큐에 빈자리가 있는지 확인하고, 빈자리가 있으면 큐에 요청을 추가한다.

- 빈자리가 없으면 폐기한다.

- 지정된 시간마다 큐에서 요청을 꺼내 처리한다.

![Image](https://upload.cafenono.com/image/slashpageHome/20240820/134339_pqkTg530SmduHTO9iC?q=80&s=1280x180&t=outside&f=webp)

**인자(parameter)**

- **버킷 크기** : 버킷에 담을 수 있는 토큰의 최대 개수. 즉 큐의 사이즈

- **처리율(outflow rate)** : 일정 시간동안 몇 개의 요청을 처리할 것인가

**장점**

- 큐의 크기가 제한되어 있어 메모리 사용이 효율적이다.

- 처리율이 고정되어 있어 요청을 안정적으로 처리할 수 있다. 

**단점**

- 트래픽 버스트가 발생할 경우 최신 요청은 무더기로 버려질 수 있다.

### 고정 윈도우 카운터 알고리즘

**동작 원리**

- 시간(timeline)을 고정된 크기(window)로 나누고 윈도우마다 카운터(counter)를 0으로 초기화한다.

- 요청이 들어오면 윈도우의 카운터는 1씩 증가한다.

- 카운터의 값이 임계치에 도달하면 다음 윈도우가 열릴 때까지 새로운 요청을 폐기한다.

![Image](https://upload.cafenono.com/image/slashpageHome/20240820/134340_NbJO21K13zCQ9n7oHK?q=80&s=1280x180&t=outside&f=webp)

**장점**

- 메모리 효율이 좋다

- **특정한 트래픽 패턴을 처리하기에 적합하다.**

**단점**

- 윈도우 경계 부분에 요청이 몰린다면 실질적인 처리량은 임계치의 2배까지 올라갈 수 있다. 

### 이동 윈도우 로깅 알고리즘

**동작 원리**

- 모든 요청의 타임스탬프를 로그에 추가한다. 폐기한 요청도 로그에 남긴다.

- 로그를 살펴 일정 시간동안 들어온 요청이 임계치보다 높으면 앞으로 들어올 요청은 폐기한다.

- 로그는 레디스의 정렬 집합(sorted set)과 같은 캐시에 저장한다.

**장점**

- 매우 세밀하게 시스템 처리율을 조절한다.

**단점**

- 거부된 요청의 타임스탬프도 저장하기 때문에 메모리를 많이 쓴다.

### 이동 윈도우 카운터 알고리즘

![Image](https://upload.cafenono.com/image/slashpageHome/20240820/134340_ZjqoBBUZaGzO8tJNYe?q=80&s=1280x180&t=outside&f=webp)

- 현재 윈도우의 요청 수 = 현재 윈도우의 요청 수 + 직전 윈도우의 요청 수 x 직전 윈도우가 차지하는 비율

⇒ 위 그림에서 현재 윈도우의 요청 수 = 2 + 4 x 30% = 3.2

- 결과값을 내림해도 무방하다.

⇒ \left \lfloor 3.2 \right \rfloor= 3

**장점**

- 평균 처리율을 잘 계산하기 때문에 짧은 시간에 몰리는 트래픽도 잘 계산한다.

- 메모리 효율이 좋다.

**단점**

- 윈도우 내의 요청이 균등하다고 가정하기 때문에 느슨하다. 하지만 예측을 벗어나 허용되거나 버려진 요청은 0.003%에 불과하다.

## 의사결정

### 처리율 제한 장치의 위치

- 클라이언트 : 쉽게 위변조가 가능해서 부적절하다.

- **미들웨어** : 클라이언트와 서버 사이의 트래픽을 한 번 거르는 역할

**API Gateway**

- rate limit, SSL termination, authentication, IP whitelist 등을 지원하는 완전 관리형 서비스

- AWS는 **WAF**가 IP당 처리율을 제한한다!

- Untitled

### 한도 초과 트래픽 처리

- 어떤 요청이 한도 제한에 걸리면 HTTP 249 응답(too many requests)을 보낸다.

- 혹은 제한이 걸린 메시지를 큐에다 담고 나중에 처리할 수도 있다.

- 처리율 제한 장치는 아래 HTTP 헤드를 클라이언트에게 보낸다.

    - X-Ratelimit-Remaining : 윈도우 내에 남은 처리 가능 요청 수

    - X-Ratelimit-Limit : 매 윈도우마다 클라이언트가 전송할 수 있는 요청 수

    - X-Ratelimit-Retry-After : 한도 제한이 걸리지 않으려면 몇 초 뒤에 요청을 보내야 하는가

- 이중 한도 초과가 나면 429 응답과 X-Ratelimit-Retry-After 헤더를 함께 반환한다.

## 분산 환경에서의 이슈

### 경쟁 상황(Race condition)

하나의 클라이언트가 동시에 여러 요청을 보내면 프로세스 동기화에서 언급한 경쟁 상황이 발생해 카운터 값이 이상해질 수 있다. 해결 방법은 두 가지가 있다. 

- Lua script

- Redis의 sorted set

    - 별개로 Redis에서 `INCR` 등의 명령은 atomic하다.

### 동기화(Synchronization)

여러 대의 처리율 제한 장치를 둔다면 클라이언트는 요청을 분산해서 보낼 것이다. 그러면 클라이언트별로 정확한 윈도우 측정이 어려워진다. 해결 방법은 아래와 같다.

- **sticky session** : 추천하지 않는다.

- Redis 같은 DB를 중앙 집중형 데이터 저장소로 쓴다.

### 성능

- latency를 줄이기 여러 대의 edge server를 둔다.

- 제한 장치 간에 데이터를 동기화 할 때 최종 일관성 모델을 사용한다.

### 모니터링

- 처리율 제한 알고리즘과 정책들(파라미터)이 효과적인지 확인한다.

- 상황에 따라 대처한다. 트래픽 버스트가 발생한다면 토큰 버킷이 적합할 것이다.

## 발전하기

- hard/soft 처리율 제한

    - hard : 요청의 개수는 임계치를 절대 넘을 수 없다.

    - soft : 요청의 개수는 잠시 임계치를 넘을 수 있다.

- L7 뿐만 아니라, Iptables를 사용해 L3에서 IP 주소를 제한하는 등 다른 계층에서도 적용이 가능하다.

- 처리율 제한을 회피하는 방법

    - 클라이언트 측 캐시를 사용하여 API 호출 횟수를 줄인다.

    - 너무 짧은 시간 동안 많은 메시지를 보내지 않는다.

    - 예외나 에러를 처리하는 코드를 작성하여 우아하게 복구하도록 한다.

    - 재시도 로직을 구현한다면 충분한 백오프(back-off) 시간을 둔다.

## 설계

![책에 있는 방법](https://upload.cafenono.com/image/slashpageHome/20240820/134341_yTacUlMalVVm1MqM8w?q=80&s=1280x180&t=outside&f=webp)

![AWS에서 이렇게 하면 어떨까 생각한 방법](https://upload.cafenono.com/image/slashpageHome/20240820/134342_j4MJta4b3G8BqhS8Q1?q=80&s=1280x180&t=outside&f=webp)

## 출처

1. AWS API Gateway 처리량 향상을 위해 API 요청 조절 - [https://www.nclouds.com/blog/security-apps-aws-web-application-firewall](https://www.nclouds.com/blog/security-apps-aws-web-application-firewall/)

2. WAF로 웹앱 보안 적용하기 - [https://www.nclouds.com/blog/security-apps-aws-web-application-firewall](https://www.nclouds.com/blog/security-apps-aws-web-application-firewall/)

3. Rate limiting for distributed systems with Redis and Lua - [https://blog.callr.tech/rate-limiting-for-distributed-systems-with-redis-and-lua](https://blog.callr.tech/rate-limiting-for-distributed-systems-with-redis-and-lua/)

4. Better Rate Limiting With Redis Sorted Sets - [https://engineering.classdojo.com/blog/2015/02/06/rolling-rate-limiter/](https://engineering.classdojo.com/blog/2015/02/06/rolling-rate-limiter/)

5. Scaling your API with rate limiters - [https://stripe.com/blog/rate-limiters](https://stripe.com/blog/rate-limiters)

6. How to handle race condition and data synchronization for distributed rate limiter? - [https://leetcode.com/discuss/interview-question/system-design/1979879/How-to-handle-race-condition-and-data-synchronization-for-distributed-rate-limiter](https://leetcode.com/discuss/interview-question/system-design/1979879/How-to-handle-race-condition-and-data-synchronization-for-distributed-rate-limiter)

For the site tree, see the [root Markdown](https://slashpage.com/kaonmir.md).