처리율 제한 장치의 설계

클라이언트/서비스가 보내는 트래픽 처리율(rate)를 제어하는 장치.

HTTP 이 장치가 특정 기간 내에 전송하는 클라이언트 요청 횟수를 제한한다. api 요청 횟수가 임계치를 넘어서면 추가로 도달한 모든 호출은 막힌다. 

- 초당 2회 이상 새 글을 올릴 수 없다. 같은 IP로는 하루 10개 이상 계정 생성이 안된다 등등

 

DoS(Denial of Service) 공격에 의한 자원 고갈(resource starvation)을 방지할 수 있다. 

처리율 제한 장치는 추가 요청에 대해서는 처리를 중단함으로써 DoS 공격을 방지한다. 

 

제3자(thrid-party) API에 사용료를 지불하는 회사들에게는 아주 중요하다. 

서버 부하를 막는다. 잘못된 이용 패턴으로 유발된 트래픽을 걸러내는 것에 처리율 제한 장치를 활용가능하다. 

 

ALPHA-HELIX 는  third-party를 사용, 분산 환경에서도 동작해야하는 대규모 요청을 처리할 수 있어야한다. 

 

1단계 : 문제 이해 및 요구사항 설계 범위 확정 

- 설정된 처리율을 초과하는 요청은 정확히 제한한다.

- 낮은 응답시간: 처리율 제한장치는 http 응답시간에 부정적인 영향을 주지 않는다. 

- 가능한 적은 메모리를 할당한다.

- 분산형 처리율 제한: 하나의 처리율 제한 장치를, 여러 서버/프로세스에서 공유한다.

- 예외 처리: 요청이 제한되었을 때 사실을 사용자에게 분명히 보여준다.

- 높은 결함 감내성(fault tolerance) : 제한 장치에 장애가 생겨도 전체 시스템에 영향 주어서는 안된다 

 

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

클라이언트 or 서버 측에도 이 장치를 둘 수 있다. 클라이언트 측은 통제가 어려우니 두지 않는다.

서버에 둔다면, 완전히 서버측에 처리율 제한 장치를 두거나

처리율 제한 장치를 API서버에 두는 대신에, 미들웨어를 만들어서, 해당 미들 웨어로 API 서버로 가는 요청을 통제하는 방법이다.

 

만약에 너무 많은 요청이 짧은 시간내에 API 서버로 요청이되면, HTTP 상태코드 429를 반환하며, 사용자가 너무 많은 요청을 보내려고 했다(Too many requests)를 알리는 것이다. 

 

일단 API 게이트 웨이=처리율 제한을 지원하는 미들웨어 라는걸 기억하자. 

1. 처리율 제한 장치는 어디에 두어야하나? 

2. 서버? 게이트웨이? 

상용 API 게이트 웨이를 쓰는게 효과적인 방법일 것이다. 

 

처리율 제한 알고리즘

1. 토큰 버킷 알고리즘(Token Bucket)

폭넓게 이용된다. 아마존 스트라이프가 api 요청을 통제(throttle) 하기 위해서 이 알고리즘을 쓴다. 

 

토큰 버킷은 지정된 용량을 갖는 그릇이다. 이 버킷에는 사전 설정된 양의 토큰이 주기적으로 채워진다. 

꽉찬 버킷에는 더이상 토큰은 추가되지 않는다. 버킷이 가득 차면 추가로 공급된 토큰은 버려진다(overflow) 

각 요청이 처리될 때마다 하나의 토큰을 사용한다 요청이 도착하면 버킷에 충분한 토큰이 있는지 검사한다.

- 충분한 토큰이 있나?  버킷에서 하나 토큰을 꺼내서 요청을 시스템에 전달

- 충분한 토큰이 없나? 해당 요청을 버린다. (dropped) 

 

 

토큰 버킷 알고리즘은 2개의 parameter를 받는다.

1. 버킷의 크기 : 버킷에 담기는 최대 토큰 수

2. 토큰 공급률(refill rate) : 초당 몇개의 토큰을 채우는가? 

 

통상적으로 api endpoint 마다 별도 버킷을 둔다. 예를 들어서, user는 하루에 한번 포스팅되고, 친구는 150명 추가까지만 되고, 좋아요는 하루에 5번만 누를 수 있다면, user 마다 3개의 토큰 버킷이 있어야 한다. 

 

IP 주소별로 처리율 제한 적용해야한다면, IP주소마다 버킷을 할당해야한다.

시스템 처리율 초당 10,000개 요청으로 제한하고 싶다면 모든 요청이 하나의 버킷을 공유해도록해야한다.

 

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

- 짧은 시간 집중되는 트래픽도 처리 가능하다. 

- 2개의 인자만으로, 적절한 튜닝은 가다롭다. 

 

누출 버킷 알고리즘(Leaky bucket) 

토큰 버킷 알고리즘과 비슷하지만 요청 처리율이 고정되어 있다. 보통 FIFO 큐로 구현한다. 

1. 요청이 도착하면 Queue가 가득차있나 확인한다. 빈자리가 있으면 큐에 요청을 추가한다.

2. 큐가 가득 차있으면 새 요청은 버린다.

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

 

누출 버킷 알고리즘은  2개의 parameter를 받는다.

- 버킷 크기 : 큐 사이즈

- 처리율(outflow rate) : 지정된 시간마다 몇개의 요청을 지정한다. 보통 초 단위이다. 

 

큐 크기가 제한되어 있으므로, 메모리 사용량 측면이 효율적이다. 고정된 처리율(outflow rate)을 갖고 있음으로 stable 출력에 적합하다. 단시간에 트래픽이 몰리면, 최신요청들이 버려지고, 오래된 요청들이 쌓이게된다. 2개 인자로 올바른 튜닝이 까다롭다. 

 

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

 

타임라인을 고정된 간격의 윈도(window)로 나누고, 각 윈도마다 카운터(counter)를 붙인다. 

요청이 접수되면 카운터 값은 1씩 증가한다. 

카운터 값이 사전에 설치된 임계치 도달하면 새로운 요청은 새 윈도가 열릴때 까지 버려진다. 

타임라인의 단위가 1초일때, 시스템은 1초당 3개 요청만 허용한다.

매초마다 열리는 윈도우에서 3개 이상에서 넘어가는 요청들은 처리율 제한에 걸려서 버려진다. 이 알고리즘의 가장 큰 문젠 윈도 경계에서 순간적으로 많은 트래픽이 집중되면, 윈도에 할당된 양보다 더 많은 요청이 처리될 수 있다는 것이다. 

 

윈도가 닫히는 시점에 카운터를 초기화하는 방식은 특정한 트래픽 패턴을 처리하기에 적합하다. 

윈도 경계에서 일시적으로 많은 트래픽이 몰리면, 기대한 처리한도보다 더 많은 요청을 처리하게 된다.

 

이동 윈도 로깅 알고리즘 

 

이 알고리즘은, 고정 윈도 카운터 알고리즘의 중대한 문제인 경계부근에 트래픽이 집중되면 기대한계치보다 많은 요청을 처리하게 된다는 문제를 해결한다. 

이 처리율 제한기는 분당 최대 2번의 요청을 처리한다. 보통 로그에 보관되는 값은 리눅스 타임 스탬프이다. 

새로운 요청이 1:00:30 에 도착하면, 해당 타임스탬프 로그에 추가된다.

추가 직후 로그 크기는 2며, 허용 한도보다 크지 않기 때문에 요청은 시스템에 전달한다.

새로운 요청이 1:00:50에 도착한다. 해당 타임스탬프가 로그에 추가된다.

로그 크기가 3이므로, 타임스탬프는 로그에 남지만 요청은 거부된다. 

1분 안에 있는 윈도우 이후에, 이전에 만료된 두개의 타임스탬프는 로그에서 삭제한다. 이후 1:01:40 의 신규요청까지 시스템에 전달된다. 

 

 

이동 윈도 카운터 알고리즘 (sliding window counter) 

 

고정 윈도 카운터 알고리즘 + 이동 윈도 로깅 알고리즘을 합한 것이다. 

처리율 제한 장치의 한도가 분당 7개 로 설정되어있다. 이전 1분동안 5개 요청, 현재 1분 동안 3개 요청이 들어왔다고 치자, 

현재 1분의 30% 시점에 도착한 새 요청은, 현재 윈도에 몇개 요청이 온것으로 보고 처리해야하나? 

 

 

개략적인 아키텍처 

처리율 제한 알고리즘의 기본 아이디어는, 결국 얼마나 많은 요청이 접수되었는지 추적하는 카운터를 추적 대상별로 두고 

(User별? IP별? API 엔드포인트별? 총 서비스 단위로?),  카운터 값이 허용 한도를 넘어서면, 넘어선 요청은 거부하는거다. 

 

카운터 값의 보관은 메모리 상에서 캐시가 바람직하다. 빠르고, 시간에 기반한 만료 정책을 지원하기 때문이다. 

Redis[11] 는 처리율 제한 장치 구현시 자주 사용하는 메모리 기반 저장 장치다. 

- INCR:  메모리에 저장된 카운터 값을 1씩 증가한다.

- EXPIRE: 카운터에 타임아웃 값을 설정한다. 설정된 시간이지나면 카운터는 자동 삭제된다. 

 

클라이언트가 Rate Limiting Middleware에 요청을 보낸다.

미들웨어는레디스 지정버킷에서 카운터를 가져와서 한도에 도달했는지 알고리즘기반 체킹한다. 

한도 이하면 요청을 api서버에 전달한다. 미들웨어는 카운터 값을 증가시키고 다시 레디스에 저장한다. 

 

3단계 : 상세 설계

처리율 제한 규칙

리프트(Lyft)는 처리율 제한에 오픈소스를 사용한다. [12]

이런 규칙들은 보통 설정파일(Configuration file)형태로 디스크에 저장된다. 

 

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

요청이 한도 제한에 걸리면 API 는 HTTP응답 429를 클라이언트한테 보낸다. 

 

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

사용자가 너무 많은 요청을 보내서 429 too many request 오류를 X-Ratelimit-Retry-After 헤더와 함께 반환하도록한다. 

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

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

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

 

처리율 제한 규칙은 디스크에 보관한다.

작업 프로세스(worker)는 수시로 규칙을 디스크에 읽어서 캐시에 저장한다. 

클라이언트가 요청을 서버에 보내면 요청은 먼저 처리율 제한 미들웨어에 도달한다.

제한 규칙을 캐시에서 가져온다. 카운터 및 타임스탬프를 레디스 캐시에서 가져온다. 

가져온 값들에 근거해서 해당 미들웨어는 아래 결정을 한다. 

- 제한에 걸리지 않으면 api 서버로 요청을 보낸다. - 제한에 걸리면, 429 에러를 클라이언트에게 보낸다.

- 요청은 그대로 버릴수도 있고, 메세지 큐에 보관할 수도 있다. (option 1,2)

 

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

단일 서버에서 지원하는 처리율 제한장치 구현은 쉽다. 

여러 대의 서버와 병렬 스레드를 지원하는 시스템을 확장하는건 2개 문제를 더 풀어야한다.

1. 경쟁 조건(race condition) 

- 레디스에서 카운터 값을 읽는다 

- 카운터가 임계치를 넘는지 본다.

- 안넘으면, 레디스에 보관된 카운터 값을 1 증가시킨다. 병행성이 심하면, 아래의 경쟁 조건 이슈가 발생한다.

가장 널리 알려진 해결은 락(lock)이지만, 시스템 성능을 매우 떨어뜨리는 문제가 있다.

루아 스크립트(Lua Script [13]), 정렬 집합(sorted set) 이라는 레디스 자료구조를 쓰는 것 이다.[8]

 

2. 동기화(synchronization)

웹 계층은 무상태(stateless)이므로, 클라이언트는 오른쪽 그림처럼, 각기 다른 제한장치로 요청을 보내게 될 수도 있다.

이때 처리율 제한장치1은 클라이언트2에 대해서 아무것도 모르면, 처리율 제한을 올바르게 수행할 수 없다. 

고정 세션(sticky session)을 활용해서, 클라이언트로부터 요청이 항상 같은 처리율 제한장치로 보내게 하는 방법이 있다. 

유연하지 않으므로 별로 추천되지는 않는다.

더 개선된 방법으로는, 레디스와 같은 중앙 집중형 데이터 저장소를 쓰는 것이다.

 

성능 최적화

데이터 센터에서 멀리 떨어진 사용자를 지원하려다 보면 지연시간이증가 할 수밖에 없다. 

대부분의 클라우드 사업자는 세계 곳곳에 edge server를 심는다. 

두번째로 제한 장치 간에 데이터를 동기화할 때 최종 일관성(eventual consistency model)을 사용하는 것이다. (6장 데이터일관성)

 

모니터링

효과적으로 동작하고 있는지 보기위해서 데이터를 모을 필요가 있다. 

- 채택한 처리율 제한 알고리즘이 효과적인가?

- 정의한 처리율 제한 규칙이 효과적인가?

 

ex) 깜짝 세일 이벤트로 트래픽이 급증하는 기간이면, 잠시 토큰 버킷알고리즘으로 바꾼다. 

 

4단계 : 마무리 

요청하신 두 이미지의 텍스트를 복사하여 붙여넣기 쉽게 정리해 드립니다.

• 경성(hard) 또는 연성(soft) 처리율 제한
  • 경성 처리율 제한: 요청의 개수는 임계치를 절대 넘어설 수 없다.
  • 연성 처리율 제한: 요청 개수는 잠시 동안은 임계치를 넘어설 수 있다.
• 다양한 계층에서의 처리율 제한
  • 이번 장에서는 애플리케이션 계층(HTTP: OSI 네트워크 계층도 기준으로 7번 계층)에서의 처리율 제한에 대해서만 살펴보았다. 하지만 다른 계층에서도 처리율 제한이 가능하다. 예를 들어, Iptables를 사용하면 IP 주소(IP는 OSI 기준으로 3번 계층)에 처리율 제한을 적용하는 것이 가능하다. [15] 참고로 OSI는 Open Systems Interconnection model의 약어로, 총 7개의 계층으로 구성된다. [16] 1번 계층은 물리(physical) 계층, 2번 계층은 데이터 링크(data link) 계층, 3번은 네트워크 계층, 4번은 전송(transport) 계층, 5번은 세션(session) 계층, 6번은 표현(presentation) 계층, 그리고 7번은 애플리케이션 계층이다.
• 처리율 제한을 회피하는 방법. 클라이언트를 어떻게 설계하는 것이 최선인가?
  • 클라이언트 측 캐시를 사용하여 API 호출 횟수를 줄인다.
  • 처리율 제한의 임계치를 이해하고, 짧은 시간 동안 너무 많은 메시지를 보내지 않도록 한다.
  • 예외나 에러를 처리하는 코드를 도입하여 클라이언트가 예외적 상황으로부터 우아하게(gracefully) 복구될 수 있도록 한다.
  • 재시도(retry) 로직을 구현할 때는 충분한 백오프(back-off) 시간을 둔다.

4장까지 성공적으로 마친 여러분, 축하한다. 멋지게 마무리한 스스로를 마음껏 격려하도록 하자!

참고문헌

[1] Rate-limiting strategies and techniques: https://cloud.google.com/solutions/rate-limiting-strategies-techniques

[2] Twitter rate limits: https://developer.twitter.com/en/docs/basics/rate-limits

[3] Google docs usage limits: https://developers.google.com/docs/api/limits

[4] IBM microservices: https://www.ibm.com/cloud/learn/microservices

[5] Throttle API requests for better throughput: https://docs.aws.amazon.com/apigateway/latest/developerguide/api-gateway-request-throttling.html

[6] Stripe rate limiters: https://stripe.com/blog/rate-limiters

[7] Shopify REST Admin API rate limits: https://help.shopify.com/en/api/reference/rest-admin-api-rate-limits

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

[9] System Design - Rate limiter and Data modelling: https://medium.com/@saisandeepmopuri/system-design-rate-limiter-and-data-modelling-9304b0d18250

[10] How we built rate limiting capable of scaling to millions of domains: https://blog.cloudflare.com/counting-things-a-lot-of-different-things/

[11] Redis website: https://redis.io/

[12] Lyft rate limiting: https://github.com/lyft/ratelimit

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

[14] What is edge computing: https://www.cloudflare.com/learning/serverless/glossary/what-is-edge-computing

[15] Rate Limit Requests with Iptables: https://blog.programster.org/rate-limit-requests-with-iptables

[16] OSI model: https://en.wikipedia.org/wiki/OSI_model#Layer_architecture

What Is Edge Computing?

 

 

Redis - Real-time data for agents & apps

 

 

Think Topics | IBM

 

 

사용량 한도  |  Google Docs  |  Google for Developers