네트워크 시스템에서 처리율 제한 장치는 클라이언트 또는 서비스가 보내는 트래픽의 처리율을 제한하기 위한 것이다.

HTTP의 경우 API에 처리율 제한 장치를 뒀을 때의 이점은 뭐가 있을까?

• DoS공격에 의한 자원 고갈 방지
• 비용 절감 : 추가 요청에 대한 처리릊 제한하면 서버를 많이 두지 않아도 되고, 우선순위가 높은 API에 더 많은 자원을 할당할 수 있음. 또, 서드파티 API에 사용료를 지불하고 있는 회사들에게 아주 중요.
• 서버 과부하 방지 : bot에서 오는 트래픽이나 사용자의 잘못된 이용 패턴으로 유발된 트래픽을 걸러내는데 사용할 수 있음.

처리율 제한 장치의 설계

[1단계] 문제 이해 및 설계 범위 확정

처리율 제한 장치를 구현하는 데는 여러 알고리즘을 사용할 수 있음. 각각 고유한 장단점이 있다.
다음과 같은 조건을 가진 환경이라고 생각해보자.

요구사항

• 설정된 처리율을 초과하는 요청은 정확하게 제한한다.
• 낮은 응답시간 : HTTP 응답시간에 나쁜 영향을 주어서는 곤란.
• 가능한 한 적은 메모리 사용
• 분산형 처리율 제한 : 하나의 처리율 제한 장치를 여러 서버나 프로세스에서 공유할 수 있어야 함.
• 예외 처리 : 요청이 제한되었을 때는 그 사실을 사용자에게 분명히 보여주어야 함.
• 높은 결함 감내성 : 제한 장치에 장애가 생기더라도 전체 시스템에 영향을 주어서는 안됨.

[2단계] 개략적 설계안 제시 및 동의 구하기

처리율 제한 장치를 어디에 둘 것인가?

• 클라이언트 측에 두었을 때 : 클라이언트 요청은 쉽게 위변조가 가능하기 때문에 안정적인 제한이 어렵다.
• 서버 측에 두었을 때 :
  API 서버와 함께 두기
  미들 웨어 구축 후 설치하기
  
  만약 미들웨어를 가운데 두고 API 서버 처리율이 초당 2개의 요청이라고 가정했을 때
  앞선 두 요청은 API 서버로 전송되겠지만, 세 번째 요청은 처리율 제한 미들웨어에 의해 가로막혀 429(Too many requests)가 반환된다.
  클라우드 마이크로서비스의 경우 보통 처리율 제한 장치는 API gateway 컴포넌트에 구성된다. (여기서는 미들웨어로 볼 수 있다) 이는 처리율 제한, SSL 종단, 사용자 인증, IP 허용 목록 관리 등을 지원하는 완전 위탁관리형 서비스 즉, 클라우드 업체가 유지 보수를 담당하는 서비스이다.

일반적으로 적용될 수 있는 항목

보통 처리율 제한 기능을 설계할 때 가장 중요하게 따져야하는 것이 이를 어디에 설치할 것인가 라는 문제인데, 이는 기술 스택, 인력, 우선순위, 목표에 따라 달라질 수 있다. 하지만, 다음과 같은 항목들은 일반적으로 적용될 수 있는 항목이다.

• 프로그래밍 언어, 캐시 서비스 등 현재의 기술 스택을 점검해야 한다.
  -> 해당 스택이 서버 구현 지원에 효율이 높은지 확인해야 함.
• 사업 필요에 맞는 처리율 제한 알고리즘을 찾을 것
  -> 아래에서 상세 설명
• 만약 이미 MSA 기반환경에서 API gateway를 사용하도록 설계했다면 처리율 제한 기능 또한 gateway에 포함시켜야 할 수 있다.
• 상용 API gateway를 쓰면 시간을 절약할 수 있다.

처리율 제한 알고리즘

토큰 버킷(token bucket)

아마존과 스트라이프 같은 일반적 기업들이 사용

[동작 원리]

토킨 버킷은 지정된 용량을 갖는 컨테이너다. 이 버킷에는 사전 설정된 양의 토큰이 주기적으로 채워지는데 꽉차면 더 이상의 토큰은 추가되지 않는다.
아래 그림은 용량이 4인 버킷이고, 토큰 공급기는 버킷에 매초 2개의 토큰을 추가한다.

• 각 요청은 처리될 때마다 하나의 토큰을 사용한다. 요청이 도착하면 버킷에 충분한 토큰이 있는지 검사한다.
  충분한 토큰이 있으면 버킷에서 토큰을 하나 꺼내 요청을 시스템에게 전달한다.
  충분한 토큰이 없으면, 해당 요청은 버려진다.

[상세 설명]

아래 그림은 토큰을 버킷에서 어떻게 꺼내고, 어떻게 동작하는지, 처리 제한 로직의 작동은 어떻게 되는지를 자세히 보여준다. 이 예제의 토큰 버킷의 크기는 4이고 토큰 공급률(refill rate)는 분당 4이다.

• 4개의 토큰으로 시작
• 요청은 전달됨
• 1개의 토큰이 소비됨

• 3개의 토큰인 상태로 시작
• 3개의 요청 전부 전달됨
• 3개의 토큰이 모두 소진 됨

• 0 토큰인 상태로 시작
• 요청은 버려짐

• 1분이 지나서 4개의 토큰이 다시 공급됨

이 토큰 버킷 알고리즘은 2개의 인자를 받는다. 버킷 크기:버킷에 담을 수 있는 토큰의 최대 개수와 토큰 공급률:초당 몇 개의 토큰이 버킷에 공급되는가
그렇다면 버킷은 몇 개를 사용해야할까? -> 공급 제한 규칙에 따라 달라진다.

• 보통 API 엔드포인트마다 별도의 버킷을 둔다. (만약 사용자 api가 3개라면 각 사용자마다 3개의 버킷을 두어야 함)
• IP 주소별로 처리율 제한을 적용해야 한다면 IP 주소마다 버킷을 하나씩 할당.
• 시스템의 처리율을 초당 10,000개 요청으로 제한하고 싶다면, 모든 요청이 하나의 버킷을 공유하도록 해야 함.

[장점]

• 구현이 쉬움
• 메모리 사용 측면에서도 효율적
• 짧은 시간에 집중되는 트래픽도 처리 가능. 버킷에 남은 토큰이 있기만 하면 요청은 시스템에 전달 됨

[단점]

• 인자가 두 개이기 때문에 이 값을 적절하게 튜닝하는 것이 까다롭다.

누출 버킷(leaky bucket)

토큰 버킷 알고리즘과 비슷하지만 요청 처리율이 고정되어있다. 보통 FIFO큐로 구현한다. 현재 전자 상거래 기업인 쇼피파이가 이 알고리즘을 사용해 처리율 제한을 구현하고 있다.
[동작 원리]

1. 요청이 도착하면 큐가 가득차 있는지 확인. 빈자리가 있으면 큐(bucket)에 요청을 추가 함.
2. 큐가 가득 차 있는 경우 그 요청은 폐기
3. 지정된 시간마다 큐에서 요청을 꺼내어 처리.

누출 버킷 알고리즘은 두 개의 인자를 사용한다.
버킷 크기 : 큐 사이즈와 같음. 와 처리율 : 지정된 시간 당 몇 개의 항목을 처리할지 지정하는 값. 보통 초 단위로 표현

[장점]

• 큐의 크기가 제한되어있어 메모리 사용량 측면에서 효율적.
• 고정된 처리율을 갖고 있기 때문에 안정적 출력이 필요한 경우 적합.

[단점]

• 단시간에 많은 트래픽이 몰리는 경우 오래된 요청들이 큐에 쌓이게 되고, 제때 요청들을 처리하지 못하면 최신 요청들은 버려지게 됨.
• 인자가 두 개이기 때문에 이 값을 적절하게 튜닝하는 것이 까다롭다.

고정 윈도 카운터(fixed window counter)

[동작 방식]
1. 타임라인을 고정된 간격의 윈도로 나누고, 각 윈도마다 카운터를 붙인다.
2. 요청이 접수될 때마다 이 카운터의 값은 1씩 증가하고
3. 이 카운터의 값이 설정된 임계치에 도달하면 새로운 요청은 새 윈도가 열릴 때까지 버려진다.

아래 그림의 타임라인 시간 단위는 1초, 시스템은 초당 3개까지의 요청만을 허용한다고 가정하자. 매초마다 열리는 윈도에 3개 이상의 요청이 밀려오면 초과분은 버려진다.

[이슈]

이 알고리즘의 문제점은 윈도의 경계부근에 순간적으로 많은 트래픽이 집중되면 윈도에 할당된 양보다 더 많은 요청이 처리될 수 있다는 것이다.
만약 아래 그림처럼 분당 최대 5개의 요청을 허용하는 시스템(매분마다 카운터 초기화)에서 2:00:00과 2:01:00 사이에 5개의 요청이 들어왔고 2:01:00과 2:02:00 사이에 5개의 요청이 들어왔다면 알고리즘의 규칙대로 잘 처리된게 맞지만 2:00:30부터 2:01:30 사이를 기준으로 보면 총 10개이기 때문에 허용 한도의 2배가 처리 돼버린다.

[장점]

• 메모리 효율이 좋고, 이해하기 쉬움
• 윈도가 닫히는 시점에 카운터를 초기화하는 방식은 특정한 트래픽 패턴을 처리하기 적합 함.

[단점]

• 윈도 경계 부근에서 일시적으로 많은 트래픽이 몰리는 경우 기대했던 시스템의 처리한도볻ㄱ다 더 많은 양의 요청을 처리하게 됨.

이동 윈도 로그(sliding window log)

이동 윈도 로깅 알고리즘은 앞선 고정 윈도 카운터 알고리즘의 [이슈]를 해결할 수 있다.

[동작 원리]
1. 요청의 타임 스탬프를 추적한다. 타임스탬프 데이터는 보통 Redis의 정렬집합 같은 캐시에 보관 함.
2. 새 요청이 오면 만료된 타임스탬프(그 값이 현재 윈도의 시작 지점보다 오래된 타임스탬프를 말한다.)를 제거
3. 새 요청의 타임 스탬프를 로그에 추가 함.
4. 로그의 크기가 허용치보다 같거나 작으면 요청을 시스템에 전달. 그렇지 않은 경우는 처리를 거부.

[예제]
아래 그림의 처리율 제한기는 분당 최대 2회의 요청만을 처리하도록 설계되었다.

1. 요청이 1:00:01에 도착했을 때 로그는 비어있는 상태라 요청 허용.
2. 새로운 요청이 1:00:30에 도착. 해당 타임스탬프가 로그에 추가. 추가 직후 로그의 크기가 2이기 때문에 요청 허용.
3. 새로운 요청이 1:00:50에 도착.해당 타임스탬프가 로그에 추가되는데 추가 직후 크기가 3이 되기때문에 요청 거부
4. 새로운 요청이 1:01:40에 왔을 때 [1:00:40 ~ 1:01:40] 범위 안에 있는 요청은 1분 윈도 안에 있는 요청이지만, 1:00:40 이전의 타임스탬프는 전부 만료된 상태라. 두 개의 만료된 타임스탬프(1:00:01, 1:00:30)은 삭제 됨 -> 로그의 크기가 2이므로 신규 요청 허용

[장점]

• 정교하다.
• 어느 순간의 윈도를 보더라도 허용되는 요청의 개수는 시스템 처리율 한도를 넘지 않는다.

[단점]

• 다량의 메모리를 사용한다. (거부된 요청의 타임스탬프도 보관하기 때문에)

이동 윈도 카운터(sliding window counter)

고정 윈도 알고리즘과 이동 윈도 로깅 알고리즘을 결합한 것으로 구현 시 두 가지 접근법이 사용된다. (여기서는 하나만 설명하고 하나는 참고문헌)

아래 그림의 처리율 제한 장치의 한도가 분당 7개 요청으로 설정되어있다고 하고, 이전 1분동안에는 5개의 요청이 현재 1분 동안은 3개의 요청이 왔다고 해보자.

현재 1분의 30% 시점에 도착한 새 요청의 경우, 현재 윈도에 몇 개의 요청이 온 것으로 보고 처리해야할까?
-> 현재 1분 간의 요청 수 + 직전 1분 간의 요청 수 x 이동 윈도와 직전 1분이 겹치는 비율 = 3 + 5 x 0.7 = 6.5 = 약 6

그렇다면 이 처리율 제한 장치의 한도가 분당 7개 요청이니 현재 1분의 30% 시점에 도착한 신규 요청은 시스템으로 전달될 것이다. 하지만 그 직후에는 한도에 도달하였으므로 더 이상의 요청은 받을 수 없다.

[장점]

• 이전 시간대의 평균 처리율에 따라 현재 윈도의 상태를 계산하므로 짧은 시간에 몰리는 트래픽에도 잘 대응한다.
• 메모리 효율이 좋다.

[단점]

• 직전 시간대에 도착한 요청이 균등하게 분포되어있다고 가정한 상태에서 추정치를 계산하기 때문에 다소 느슨함.

개략적인 아키텍처

처리율 제한 알고리즘은 기본적으로 얼마나 많은 요청이 접수되었는지를 추적할 수 있는 카운터를 추적 대상별로 둔다. 그리고 사용자별로 추적할 것인가? 아니면 IP 주소별로? 아니면 API 엔드포인트나 서비스 단위로? 이 카운터의 값이 한도를 넘어서면 그 뒤에 도착한 요청은 거부되는 것이다.
카운터는 보통 캐시에 보관한다.(빠르고, 시간에 기반한 만료 정책을 지원하기 때문에)

Redis를 사용할 때, 지원하는 명령어

• INCR : 메모리에 저장된 카운터의 값을 1만큼 증가시킨다.
• EXPIRE : 카운터에 타임아웃 값을 설정한다. 설정된 시간이 지나면 카운터는 자동으로 삭제된다.

클라이언트가 처리율 제한 미들웨어에게 요청을 보내면 이는 지정 버킷에서 카운터를 가져와서 한도에 도달했는지 검사한다.

• 도달했다면 요청 거부, 도달하지 않았다면 API 서버로 전달
• 미들웨어는 카운터 값을 증가 시킨고 레디스에 저장한다.

[3단계] 상세 설계

지금까지의 과정으로는 처리율 제한 규칙은 어떻게 만들어지는 지, 저장 장소, 제한된 요청 처리 방법 등에 대해서는 알 수가 없다.

처리율 제한 규칙

리프트(Lyft)는 처리율 제한에 오픈소스를 쓰고 있다. 보통 이런 규칙들은 conf 파일의 형태로 디스크에 저장된다. 아래에서는 하루 마케팅 메세지 최대치를 5개로 두고 있다.

domain : messaging
descriptors:
  -key : message_type
   value : marketing
   rate_limit:
    unit: day
    requests_per_unit : 5

처리율 한도 초과 트래픽의 처리

보통 한도 제한에 걸린 메세지를 나중에 처리해주기 위해 큐에 보관한다.

처리율 제한 장치가 사용하는 HTTP 헤더**

• X-Ratelimit-Remaining : 윈도 내 남은 처리 가능 요청의 수
• X-Ratelimit-Limit : 매 윈도마다 클라이언트가 전송할 수 있는 요청의 수
• X-Ratelimit-Retry-After : 한도 제한에 걸리지 않으려면 몇 초 뒤에 요청을 다시 보내야 하는지 알림

사용자가 너무 많은 요청을 보내면 429 error와 X-Ratelimit-Retry-After 헤더와 함께 반환한다.

상세 설계

1. 처리율 제한 규칙은 디스크에 보관. 작업 프로세스는 수시로 규칙을 디스크에서 읽어 캐시에 저장
2. 클라이언트가 요청을 서버에 보내면 요청은 먼저 처리율 제한 미들웨어에 도달
3. 처리율 제한 미들웨어는 제한 규칙을 캐시에서 가져오고, 카운터 및 마지막 요청의 타임스탬프를 레디스 캐시에서 가져온다.
   1. 그리고 해당 요청이 처리율 제한에 걸리지 않는 경우 API 서버로 전송
   2. 해당 요청이 처리율 제한에 걸렸다면 429 에러를 클라이언트에 보낸다. 한편 요청은 버릴 수도 있고 메세지 큐에 저장할 수도 있다.

분산 환경에서의 처리율 제한 장치의 구현

만약 여러 대의 서버와 병렬 스레드를 지원하도록 처리율 제한 장치를 확장하려면 경쟁 조건, 동기화 문제를 해결해야한다.

경쟁 조건

병행성이 심한 환경에서는 다음과 같은 경쟁 조건 이슈가 발생할 수 있음.

처리율 제한 장치가 Redis에서 카운터 값을 읽어 임계치가 넘는지 확인하고 처리하는 작업을 할 때, Redis에 저장된 변수 counter의 값이 3이라고하고, 두 개 요청을 처리하는 스레드가 각각 병렬로 counter 값을 읽었으며 그 둘 가운데 어느 쪽도 아직 변경된 값을 저장하지 않은 상태라 했을 때,
각각 두 개의 요청들은 읽어온 3이라는 카운터 값을 기준으로 계산하게 될 것이다. 그렇다면 사실 counter의 값은 5여야 하는데 4로 기록 되는 것이다.
기본적인 스레드 병렬처리의 이슈와 닮아있다.
보통은 이를 락(lock)을 통해 해결하는데 성능이 떨어진다는 문제점이 있다.
이 경우 루아 스크립트와 Redis 자료구조인 정렬집합(sorted set) 를 통해 해결할 수 있다.

동기화 이슈

처리율 제한 장치를 분산처리 했다고 했을 때 이 각각의 장치를 서로 동기화해쥐지 않으면 이전 요청들에 대해서 서로 모르는 상태로 작업들을 수행하게 돼버린다.
보통은 Redis와 같은 중앙 집중형 데이터 저장소를 사용해 해결한다.

성능최적화

• 여러 지역에 데이터 센터 분산하기
• 최종 일관성 모델 사용하기 (6장 참고)

모니터링

처리율 제한 장치를 설치한 이후에는 효과적으로 동작하고 있는지 보기 위해 데이터를 모을 필요가 있다. 기본적으로는 다음과 같은 항목을 확인한다.

• 채택된 처리율 제한 알고리즘이 효과적인가?
  * 만약, 깜짝 세일 이벤트같은 트래픽이 급증할 때 장치가 효율적으로 동작하기 위해서는 토큰 버킷 알고리즘으로 바꾸는 것을 고려해봐야한다.
• 정의한 처리율 제한 규칙이 효과적인가?

Conclude

• 처리율 제한 장치 설계 시 고려해야 할 부분
  처리율 제한 알고리즘
  알고리즘 구현 아키텍처
  분산환경에서의 처리율 제한 장치
  성능 최적화
  * 모니터링

추가적으로 언급하면 좋은 것들

• 경성 또는 연성 처리율 제한
  경성 처리율 제한 : 요청의 개수는 임계치를 절대 넘어설 수 없다.
  연성 처리율 제한 : 요청 개수는 잠시 동안은 임계치를 넘어설 수 없다.
• 다양한 계층에서의 처리율 제한
  * HTTP(7계층) 뿐만 아니라 만약, Iptables를 사용하면 ip주소(3계층)에 처리율 제한을 적용하는 것이 좋을 것이다.
• 처리율 제한을 회피하는 방법
  클라이언트 측 캐시를 사용하여 API 호출 횟수를 줄인다.
  임계치를 인지하고, 짧은 시간 동안 너무 많은 메세지를 보내지 않도록 한다.
  예외나 에러처리 코드로 예외적 상황에서 우아하게(gracefully) 복구될 수 있또록 한다.
  재시도(retry) 로직을 구현할 때는 충분한 백오프(back off) 시간을 둔다.