[대규모 시스템 설계] 처리율 제한 장치

처리율 제한 장치는 클라이언트 또는 서비스가 보내는 트래픽의 처리율을 제어하는 장치이다.
HTTP를 예로 들면 특정 기간 내에 전송되는 클라이언트의 요청 횟수를 제한하는 식이다.
API 요청 횟수가 임계치를 넘어서면 이후 모든 호출은 중단된다.

구체적인 사례를 보면 다음과 같다.

• 사용자는 초당 2회 이상 새 글을 올릴 수 없다.
• 같은 IP로 하루에 10개 이상의 계정을 생성할 수 없다.
• 같은 디바이로 주 5회 이상 리워드를 요청할 수 없다.

 

거의 대부분의 대형 IT 서비스 기업들은 처리율 제한 장치를 가지고 있다.
그렇다면 처리율 제한 장치를 둠으로써 얻는 이점은 어떤 것들이 있을까?

크게 3가지의 이점을 말할 수 있다.

1. DoS 공격에 의한 서버 자원 고갈을 방지할 수 있다.
2. 비용을 절감할 수 있다.
3. 서버 과부하를 방지할 수 있다.

 

단일 호스트로부터 들어오는 DoS 공격을 방지할 수 있고, 요청 제한을 통해 서드 파티 API 호출 비용을 절감할 수 있으며, 봇이나 잘못된 이용 패턴으로 발생하는 트래픽을 걸러내므로 서버 과부하를 방지할 수 있다.

 

처리율 제한 장치 구축 위치

직관적으로 보자면 처리율 제한 장치는 클라이언트 측에 둘 수도 있고, 서버 측에 둘 수도 있다.

클라이언트의 요청은 쉽게 위변조가 가능하다.
해당 클라이언트의 구현을 통제하는 것을 고려해볼 수 있지만, 일반적으로 클라이언트는 서버와 N:1의 관계를 가지기 때문에 모든 클라이언트의 구현을 통제하는 것이 어려울 수 있다.

그렇기 때문에 처리율 제한 장치를 클라이언트 측에 두는 것은 적절하지 않다.

우리는 API 서버 측에 제한 장치를 두는 방법을 선택할 수 있지만, 다른 방법도 있다.
바로 처리율 제한 미들웨어를 만들어 클라이언트와 서버 사이에 두고 API 서버로 가는 요청을 통제하도록 하는 것이다.

처리율 제한 미들웨어는 정해진 규칙에 의해 API 요청 횟수가 임계치를 넘어서면 이후 HTTP Status Code 429를 반환한다.

마이크로서비스의 경우 API 게이트웨이에 처리율 제한 장치를 구축한다.
API 게이트웨이는 처리율 제한, SSL 종단, 사용자 인증, IP 허용 목록 관리 등을 지원한다.

 

처리율 제한 알고리즘

처리율 제한을 실현하는 알고리즘에는 어떤 것들이 있고 각각 어떤 장단점을 가지고 있는지 개략적으로 알아보자.

토큰 버킷 알고리즘

토큰 버킷 알고리즘은 간단하고 이해하기 쉬운 처리율 제한 알고리즘이다.
버킷 크기, 토큰 공급률 2개의 인자를 받아 처리율을 제한한다.

각 요청은 하나의 토큰을 소비하며 버킷에 주기적으로 공급되는 토큰의 존재 여부에 따라 요청을 전달할지, 버릴지를 결정한다.
다음은 버킷 크기가 4이고 토큰 공급률이 분당 4인 토큰 버킷 알고리즘의 예시이다.

• 장점
  • 구현이 쉽다.
  • 메모리 사용 측면에서 효율적이다.
  • 버킷에 토큰이 충분하기만 하면 시스템에 전달되기 때문에 짧은 시간에 집중되는 트래픽 처리도 가능하다.
• 단점
  • 2개의 인자에 대한 최적화 튜닝이 까다롭다.

 

누출 버킷 알고리즘

토큰 버킷 알고리즘과 비슷하지만 요청 처리율이 고정되어있다는 차이점이 존재한다.
누출 버킷 알고리즘은 버킷 크기, 처리율 2개의 인자를 받고 큐(Queue)로 구현한다.
이때 처리율이란 지정된 시간에 몇 개의 항목을 처리할지를 나타내는 값이다.

• 장점
  • 큐의 크기가 제한되어 있어 메모리 사용량 측면에서 효율적이다.
  • 고정된 처리율을 가지고 있어 안정적 출력이 가능하다.
• 단점
  • 단시간에 몰리는 트래픽의 경우 큐에는 오래된 요청들이 쌓이게 되고, 제때 처리되지 못하면 최신 요청들이 버려지게 된다.
  • 2개의 인자에 대한 최적화 튜닝이 까다롭다.

 

고정 윈도 카운터 알고리즘

타임라인을 고정된 간격의 윈도로 나누고 카운터 임계치를 통해 처리율을 제한하는 알고리즘이다.

동작 방식은 다음과 같다.

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

초당 3개의 요청을 허용한 고정 윈도 카운터 알고리즘

 

• 장점
  • 메모리 효율이 좋다.
  • 이해하기 쉽다.
  • 특정 트래픽 패턴을 처리하기에 좋다.
• 단점
  • 윈도 경계 부근에 일시적으로 많은 트래픽이 몰릴 경우, 시스템의 처리한도보다 많은 양의 요청을 처리하게 된다.

  • 

     

이동 윈도 로깅 알고리즘

고정 윈도 카운터 알고리즘의 단점을 해결한 알고리즘이다.
동작 원리는 다음과 같다.

1. 요청의 타임스탬프를 추적한다. 타임스탬프 데이터는 redis의 sorted set 같은 캐시에 보관한다.
2. 새 요청이 들어오면 만료된 타임스탬프를 제거한다.
3. 새 요청의 타임스탬프를 로그에 추가한다.
4. 로그의 크기가 허용치보다 같거나 작으면 요청을 전달하고, 그렇지 않다면 처리를 거부한다.

• 장점
  • 처리율 제한 메커니즘이 정교하다. 즉, 허용되는 요청의 개수는 시스템의 처리율 한도를 넘지 않고 정교하게 지켜진다.
• 단점
  • 거부된 요청의 타임스탬프도 보관하므로 메모리를 많이 사용한다.

 

이동 윈도 카운터 알고리즘

고정 윈도 카운터 알고리즘과 이동 윈도 로깅 알고리즘을 결합한 알고리즘이다.
다음과 같이 현재 윈도의 요청 수를 계산하고 처리할 수 있다.
현재 1분간의 요청 수 + 직전 1분간의 요청수 * 이동 윈도와 직전 1분이 겹치는 비율

• 장점
  • 이전 시간대의 평균 처리율에 따라 현재 윈도의 상태를 계산하므로 짧은 시간에 몰리는 트래픽에도 잘 대응한다.
  • 메모리 효율이 좋다.
• 단점
  • 굳이 뽑자면 직전 시간대에 도착한 요청이 균등하게 분포되어 있다고 가정한 상태에서 추정치를 계산하기 때문에 다소 느슨하다. 다만 심각한 단점은 아니다. 실험에 따르면 40억 개의 요청 중 실제 상태와 맞지 않게 허용되거나 버려진 요청의 비율은 0.003%에 불과했다.

 

처리율 제한 장치의 구조

처리율 제한 장치의 기본 아이디어는 얼마나 많은 요청이 접수되었는지 추적하는 카운터를 두고 한도를 넘어서면 이후 요청은 거부하는 것이다.

그렇다면 카운터는 어디에 저장해야 할까?
데이터베이스는 디스크 접근 때문에 느려서 적합하지 않고 메모리상에서 동작하는 캐시가 바람직하다.
따라서 처리율 제한 장치를 구현할 때 자주 사용되는 메모리 기반 저장장치로 Redis를 많이 사용한다.

처리율 제한 장치는 다음과 같이 동작한다.

1. 클라이언트가 처리율 제한 미들웨어에 요청을 보낸다.
2. 미들웨어는 redis의 버킷에서 카운터를 가져와 한도를 검사한다.
3. 한도에 도달했다면 해당 요청은 거부된다.
4. 한도에 도달하지 않았다면 API 서버로 요청을 전달하고 카운터 값을 증가시킨 후 redis에 저장한다.

이렇게 동작하는 처리율 제한 장치에 의해 한도 초과된 트래픽의 요청은 버려지게 된다.
하지만 클라이언트 입장에서는 자신이 보낸 요청이 한도 초과되었다는 사실을 알 수 없다.

따라서 처리된 한도 초과 트래픽을 클라이언트에게 전달하는 방법도 필요하다.
일반적으로 처리율 제한 장치는 Header를 이용해 해당 정보를 클라이언트에게 전달한다.

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

처리율 제한 장치의 상세 구조를 살펴보면 다음과 같다.

 

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

단일 서버 환경에서의 처리율 제한 장치 구현은 어렵지 않다.
하지만 여러 대의 서버와 병렬 스레드를 지원해야 하는 분산 환경이라면 경쟁 조건과 동기화 이슈를 고려해야 한다.

경쟁 조건

경쟁 조건은 처리율 제한 장치의 카운터 값을 읽어올 때 발생할 수 있다.
레디스의 저장된 카운터가 증가하기 전에 다른 요청이 들어온다면 동시성 문제가 생긴다.

이러한 문제를 해결하는 가장 널리 알려진 방법은 락(Lock)을 이용하는 것이다.
하지만 락은 시스템 성능을 상당히 떨어트린다는 단점이 있다.

분산 환경에서는 락을 사용하기보다는 루아 스크립트나 redis의 sorted set 자료구조를 사용하는 게 좋은 해법이 된다.

 

동기화 이슈

처리율 제한 장치를 여러 대 두게 되면 각각 다른 처리율 제한 장치로 요청이 들어갈 수 있다.

이때 동기화가 수행되지 않으면 제한 장치는 처리율 제한을 올바르게 수행할 수 없게 된다.
고정 세션(sticky session)을 활용하면 해결 가능하지만 이 방법은 규모 확장면에서 좋은 방법은 아니다.

이 문제를 해결하기 위한 가장 좋은 방법은 중앙 집중형 데이터 저장소를 사용하는 것이다.

추가적으로 요청과 가까운 데이터 센터를 활용해 응답 지연 시간을 줄여 성능 최적화를 생각해볼 수 있다.
이때, 데이터 동기화를 수행한다면 최종 일관성 모델을 사용하면 된다.