# 4. 처리율 제한 장치

## 💬 처리율 제한 장치

### 개념

* 클라이언트가 보내는 트래픽의 처리율을 제어하기 위한 장치
* 특정 기간 내 전송되는 요청 횟수를 제한하고, 제한 임계치를 넘어서면 요청 처리가 중단된다.
* 제한 임계치가 넘은 상황에서 요청에 대한 응답으로는 보통 `HTTP 429 Too many requests` 를 보낸다.
* 같은 IP로 최대 10개까지 계정 생성, 초당 n회 이상 카톡 전송 불가 등의 조건을 처리율 제한 장치를 이용해 구현할 수 있다.&#x20;

### 장점

* 제한 범위를 넘어서는 요청에 대해 처리를 중단하므로 DoS 공격에 의한 자원 고갈 방지 가능
* 비용 절감 - 서버를 많이 두지 않고 우선순위가 높은 API에 더 많은 자원 할당 가능
* 서버 과부하 방지 - 봇이나 잘못된 이용 패턴에 의한 트래픽을 걸러낼 수 있음

### 미들웨어

* 처리율 제한 장치를 API 서버에 임베드할 수도 있고, 아래와 같이 처리율 제한 미들웨어를 별도 프로세스로 둘 수도 있다.

<figure><img src="https://946524419-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FZqOTWctN1y9hEXEl4sKd%2Fuploads%2FSvYoYOQEdJPvHO0xS9DK%2Fimage.png?alt=media&#x26;token=2a68831d-7aef-45e6-ab73-567c27de75de" alt=""><figcaption></figcaption></figure>

* API 게이트웨이
  * 마이크로 서비스의 경우 API 게이트웨이 컴포넌트에 처리율 제한 장치가 구현된다.
  * 처리율 제한, SSL 종단, 사용자 인증, IP 허용 목록 관리 등을 지원하는 완전 위탁관리형 서비스
  * 처리율 제한 장치는 보통 이 컴포넌트에 구현한다.

## 💬 처리율 제한 알고리즘

### 토큰 버킷

<figure><img src="https://946524419-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FZqOTWctN1y9hEXEl4sKd%2Fuploads%2FxGsSraU88SBbV4mmtxh2%2Fimage.png?alt=media&#x26;token=a716fda7-f4d3-43b0-a67c-ac2e94831786" alt=""><figcaption></figcaption></figure>

* 동작 방식
  * 토큰 버킷에 미리 설정해둔 양의 토큰을 주기적으로 추가한다.
  * 요청이 들어오면 토큰 하나를 꺼낸 후 시스템에 요청을 전달한다.
  * 남아있는 토큰이 없는 경우 요청은 버려진다. (drop)
* 예시
  * 사용자가 하루에 한 번 포스팅할 수 있고, 하루에 좋아요는 1000번까지만 누를 수 있다면, 사용자마다 2개의 버킷을 두고 하루마다 토큰을 갱신하도록 한다.
* 장점
  * 구현이 쉽고 메모리 사용 측면에서 효율적이다.
  * 버킷에 토큰이 남아있기만 한다면 짧은 시간에 집중되는 트래픽 처리도 가능하다.
* 단점
  * 버킷 크기(버킷에 담을 수 있는 최대 토큰 개수), 토큰 공급률(초당 공급하는 토큰의 개수) 인자를 적절히 튜닝하기 어렵다.

### 누출(leaky) 버킷

<figure><img src="https://946524419-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FZqOTWctN1y9hEXEl4sKd%2Fuploads%2FlebwrZhMtWrDxTAcfBt1%2Fimage.png?alt=media&#x26;token=3cfc9b04-ad66-4c28-b5d7-09e107dd91d4" alt=""><figcaption></figcaption></figure>

* 동작 방식
  * 요청이 도착하면 큐에 공간이 남아있는 지 확인 후 큐에 요청을 추가한다.
  * 큐가 가득 차있을 때 요청이 들어온 경우 해당 요청은 버려진다.
  * 일정 시간마다 큐에서 요청을 꺼내 처리한다.
* 장점
  * 큐의 크기가 제한되어 메모리 사용량 측면에서 효율적이다.
  * 늘 고정적인 처리율을 가지므로 안정적인 outflow rate가 필요한 경우 적합하다.
* 단점
  * 단시간에 요청이 많이 들어왔을 경우 오래된 요청들이 큐에 쌓이고, 새로운 요청들은 처리되지 않을 수 있다.
  * 버킷 크기와 처리율(일정 시간 동안 처리할 요청량) 인자를 적절히 튜닝하기 어려울 수 있다.

### 고정 윈도우 카운터

<figure><img src="https://946524419-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FZqOTWctN1y9hEXEl4sKd%2Fuploads%2FGlbGwe5hFeYcdRpNWkrU%2Fimage.png?alt=media&#x26;token=c5935c5a-61ef-4e0b-819f-4d8b091069af" alt=""><figcaption></figcaption></figure>

* 동작 방식
  * 타임라인을 고정된 시간 간격으로 나누어 윈도우를 만든다.
  * 윈도우마다 카운터 값을 두어 요청이 추가될 때 마다 증가시킨다. 카운터 값이 사전에 설정된 임계치에 도달하면 새로운 요청은 새 윈도우가 열릴 때까지 버려진다.
* 장점
  * 메모리 효율이 좋다.
  * 이해하기 쉽다.
  * 윈도우가 닫히는 시점에 카운터가 초기화되므로 특정한 트래픽 패턴을 처리하기에 적합하다.
*   단점

    * 윈도우 경계 부근에서 트래픽이 몰릴 경우 여러 윈도우에 분산되어 일시적으로 많은 요청을 처리할 수 있게 된다. 이는 시스템 처리 한도를 넘어설 수 있으므로 위험하다.
    * 아래 그림과 같이 윈도우의 경계 부근에서 10개의 요청이 들어왔지만, 서버는 1분에 5개의 요청만을 처리할 수 있다면 `2:00:30 ~ 2:01:30` 간의 요청이 전부 정상 처리되지 않을 수 있다.

    <figure><img src="https://946524419-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FZqOTWctN1y9hEXEl4sKd%2Fuploads%2FMw5VjhM91I3OLtcvpVli%2Fimage.png?alt=media&#x26;token=e81bd830-d64e-4a73-bbfc-089b05d7c6ac" alt=""><figcaption></figcaption></figure>

### 이동 윈도우 로깅

* 동작 방식
  * 요청이 들어온 시점의 타임스탬프를 Sorted Set과 같은 정렬 집합 자료구조에 저장해두며 이를 로그라고 한다.
  * 새로운 요청이 들어오면 현재 윈도우의 시작 시점 이전의 만료된 타임스탬프를 가진 요청을 제거하고, 새 요청의 타임스탬프를 로그에 추가한다.
  * 로그의 크기가 허용치보다 같거나 작은 경우에만 요청을 처리한다. 이외의 요청은 버린다.
  * 10초에 3개의 요청을 처리하고 time window를 10초 간격으로 설정하는 경우 아래와 같이 동작한다.
    *   &#x20;14초에 요청이 들어왔다면, 4\~14초 간에 요청량이 3개를 넘어가는지 확인 후 넘지 않으면 요청을 처리한다.

        <figure><img src="https://946524419-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FZqOTWctN1y9hEXEl4sKd%2Fuploads%2Fsmuxd3wHr3zMfKOz4hcm%2Fimage.png?alt=media&#x26;token=b60980f8-f6ad-4ed5-9ac9-322e34bf2773" alt=""><figcaption></figcaption></figure>
    *   15초에 요청이 들어왔다면, 5\~15초 간에 요청량이 3개를 넘어가는 지 확인 후 넘었다면 해당 요청을 버린다.

        <figure><img src="https://946524419-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FZqOTWctN1y9hEXEl4sKd%2Fuploads%2F8vXaxguwrMeGa1laM3b8%2Fimage.png?alt=media&#x26;token=837566c8-d0c7-4cb6-9f98-0cab27a40bbd" alt=""><figcaption></figcaption></figure>
  *   아래는 가장 마지막에 들어온 타임스탬프를 기준으로 이전 1분간의 데이터를 확인해 로그 크기가 2개보다 작거나 같다면 요청을 보내는 예시이다. `[1:00:01]`, `[1:00:30]` ,`[1:01:40]` 요청들만 처리된다.

      <figure><img src="https://946524419-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FZqOTWctN1y9hEXEl4sKd%2Fuploads%2FJwKOg3mfkWPpXaZ2bBcL%2Fimage.png?alt=media&#x26;token=f7c35c25-8afa-4d5b-8f7c-8eaed8ac8e5e" alt=""><figcaption></figcaption></figure>
* 장점
  * 어느 순간의 윈도우를 보더라도 항상 일정한 만큼의 요청을 처리한다.
  * 고정 윈도우 카운터 알고리즘의 문제를 해결한다.
* 단점
  * 거부된 요청의 타임스탬프도 보관해두므로 메모리를 많이 차지한다.
  * 현재 시간과 비교해 만료된 타임스탬프들을 제거하는 데에 리소스가 소요된다.

### 이동 윈도우 카운터

*   동작 방식

    * 고정 윈도우 카운터 알고리즘과 이동 윈도우 로깅 알고리즘을 결합한 방식이다.
    *   이동 윈도우라고는 하지만, 사실상 윈도우는 특정 간격으로 고정되어 있다. 예를 들어 1분당 요청량을 제한한다면, 1분 단위로 윈도우가 존재한다고 보면 된다.

        > 책에서는 윈도우가 움직인다고 표현하였지만, 윈도우를 기준으로 무언가 로직을 처리하지 않으므로 이해하기 쉽게 윈도우가 고정되어 있다고 표현하였다.
    * 최근 1분 간 유효한 요청의 개수를 weight라고 부르며, 이는 다음 공식으로 구할 수 있다.
      * `현재 윈도우(1~2분)의 요청량 + 이전 윈도우(0~1분)의 요청량 * 최근 1분 구간과 이전 윈도우가 겹치는 비율`
    * 새로운 요청이 들어왔을 때에는 `1분당 최대 요청량 - weight` 만큼의 요청을 처리할 수 있게 된다.
    * 예를 들어 1분 당 7개의 요청만 처리 가능하고 직전 1분 동안 5개, 현재 1분의 30% 동안 3개의 요청이 들어왔다면, 현재 윈도우에 들어있는 유효한 요청을 `3 + (5 * 0.7) = 6.5` 라고 볼 수 있다. 이를 내림 처리하면 6개이고 최대 처리량이 7개이므로, 앞으로 새로운 요청은 1개만 처리할 수 있게 된다.

    <figure><img src="https://946524419-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FZqOTWctN1y9hEXEl4sKd%2Fuploads%2FbgyvP3Y2ncXv8JpcHLIY%2Fimage.png?alt=media&#x26;token=32fd3f33-024e-46f9-a184-c69ac788cbac" alt=""><figcaption></figcaption></figure>
* 5초 동안 3개의 요청을 처리할 수 있는 경우 다음과 같이 동작한다.
  *   0\~5초 동안 3개의 요청이 들어왔고, 이는 모두 처리된다.

      <figure><img src="https://946524419-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FZqOTWctN1y9hEXEl4sKd%2Fuploads%2F943yLVatkTGv3AhdPKQN%2Fimage.png?alt=media&#x26;token=34f48858-cd3f-4b20-85bc-cae48d33ebac" alt=""><figcaption></figcaption></figure>
  *   1\~6초 동안 4개의 요청이 들어왔고, 이미 3개의 요청이 보내진 상태이다. 따라서 현재 가중치를 계산하면 2.4이다. 새로운 요청을 하나 추가하면 최대 요청 가능한 3개가 넘어가므로, 새로운 요청을 보내지 않는다.

      <figure><img src="https://946524419-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FZqOTWctN1y9hEXEl4sKd%2Fuploads%2FIps6FPmqixO6N9VkCaZr%2Fimage.png?alt=media&#x26;token=3feb03d8-0bc6-441e-8605-48f01c3aec7b" alt=""><figcaption></figcaption></figure>
  *   3\~7초 동안 5개의 요청이 들어왔고, 3개의 요청은 이미 보내졌고 1개의 요청은 버려진 상태이다. 현재 가중치를 계산하면 1.8이다. 새로운 요청을 하나 추가해도 3개를 넘기지 않으므로, 새로운 요청을 하나 보낸다.

      <figure><img src="https://946524419-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FZqOTWctN1y9hEXEl4sKd%2Fuploads%2FmLbqXqeaBIP3ko5qYtsg%2Fimage.png?alt=media&#x26;token=c09d7098-d837-4396-b3fd-a946227be23a" alt=""><figcaption></figcaption></figure>
* 장점
  * 이전 시간대의 평균 처리율에 따라 현재 윈도우의 상태를 계산하므로, 짧은 시간에 몰리는 트래픽에 잘 대응한다.
  * 메모리 효율이 좋다.
* 단점
  * 직전 시간대에 발생한 요청이 균등하게 발생했다고 가정하여 현재 윈도우에 존재하는 요청 개수의 추정이 낮게 측정될 수 있다.

## 💬 처리율 제한 장치 구현

<figure><img src="https://946524419-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FZqOTWctN1y9hEXEl4sKd%2Fuploads%2FNAivyME1yg7xn68IoEdP%2Fimage.png?alt=media&#x26;token=df751554-c12c-4918-9dd8-a65ff7d96c22" alt=""><figcaption></figcaption></figure>

* 처리율 제한 규칙
  * 보통 서버 측에서 설정 파일 형태로 디스크에 저장해두고 사용한다.
  * 설정 파일은 수시로 캐싱하여 처리율 제한 미들웨어가 빠르게 접근할 수 있도록 한다.
  * 처리율 제한 규칙은 마케팅 메시지의 최대치를 하루 5개로 제한하는 yaml 파일 형태가 될 수 있다.
* HTTP 응답 헤더
  * 클라이언트가 현재 얼마나 요청을 보낼 수 있는지를 확인할 수 있는 헤더를 서버측에서 보내주기도 한다.
  * X-Ratelimit-Remaining: 윈도 내에 남은 처리 가능 요청 수
  * X-Ratelimit-Limit: 매 윈도 마다 클라이언트가 전송 가능한 요청 수
  * X-Ratelimit-Retry-After: 몇 초 뒤 요청을 다시 보내야하는지 알림
* 처리 제한된 요청은 다음과 같이 핸들링될 수 있다.
  * 429 (too many requests) 상태 코드와 X-Ratelimit-Retry-After 헤더를 클라이언트에 응답으로 보낸다.
  * 요청을 그대로 버릴 수도 있고 메시지 큐에 보관할 수도 있다.

## 💬 분산 환경의 처리율 제한 장치

#### 경쟁 조건

* 락이 걸려있지 않은 상태에서 요청 counter 개수를 여러 요청이 비슷한 시각에 읽고 저장할 경우 올바른 값이 저장되지 않는다.
* 락을 사용하면 시스템 성능이 떨어지므로, redis의 루아 스크립트나 sorted set 자료구조를 사용하면 된다.

#### 동기화

* 처리율 제한 장치 서버를 여러대 둘 경우 동기화가 필요
* 고정 세션을 활용해 같은 클라이언트로부터 요청은 같은 처리율 제한 장치로 보낼 수도 있다(비추)
* redis 같은 중앙 집중형 데이터 저장소를 사용하면 해결 가능

#### 성능 최적화

* 지역적으로 분산된 위치에 에지 서버를 설치해 사용자의 트래픽을 가까운 에지 서버로 전달하여 지연 시간을 절감할 수 있다.
* eventual consistency model을 사용해 데이터 모델 동기화하면 좋다.

#### 모니터링

* 채택된 처리율 제한 알고리즘이나 처리율 제한 규칙이 효과적인지 확인하기 위해 필요하다.
* 버려진 요청들이 얼마나 되는지 확인하고, 트래픽을 급증시키는 테스트를 통해 지표들이 정상 상태를 유지하는지 확인하면 좋다.

## 💬 마무리

* 다양한 계층에서 처리율 제한을 수행할 수 있다.
  * ip tables 사용 시 IP 주소 기준으로 처리율 제한 적용 가능
* 처리율 제한과 함께 클라이언트 설계도 함께 개선되어야 한다.
  * 처리율 제한의 임계치를 이해하고, 짧은 시간에 여러 요청이 보내지지 않도록 함
  * 예외, 에러 처리 코드를 도입
