Rate Limiter 란?
애플리케이션에 과도한 요청을 제한하고 제어하는 데 사용되는 기술을 의미한다. 과도한 요청을 차단하여 다음과 같은 부분들을 개선할 수 있다.
- 서비스 보호
- 트래픽 조절
- 안정성 확보
- 효율성 향상
핵심은 주어진 시간동안 처리할 수 있는 요청의 수를 제한하는 것이다. 허용 요청 이상으로 요청이 들어오게 되면 해당 요청을 단순히 거절하거나 대기열로 보내어서 일정 시간 후에 처리할 수 있도록 하는 등 다양한 방법을 적용할 수 있다.
Rate Limit 을 찾아보게 된 이유
쇼핑몰 빌더사와 연동하고 웹훅을 등록하면 고객이 회원가입, 상품 구매 등등의 다양한 행동을 취할때 거기에 대한 웹훅이 서버로 오도록 설정할 수 있다. 처음 빌더사와 연동을 하였을때는 웹훅에서 넘어오는 정보를 활용하면 충분하였다. 우리 쪽에서는 해당 웹훅을 통해서 어떤 이벤트가 발생하였는지에 대한 정보만 저장하였지만. 서비스가 커지면서 필요한 기능들을 추가하기 위해서는 더 많은 정보가 필요하였다. 웹훅에 많은 정보가 있다면 그 데이터를 통해 로직을 수행할 수 있지만 없는 경우가 더 많았다. 따라서 별도로 빌더사에 api를 사용하여 데이터를 조회하여 로직을 처리하도록 하였다.
빌더사에 별도로 api를 조회하여 처리하도록 하자 간헐적으로 429에러가 발생하기 시작하였다. 처음 429에러를 마주하였을때는 Too many requests 라고 에러 메세지까지 자세하게 내려주었지만 정확한 이유를 알지 못했었다. 429에러에 대해 좀 더 알아보기 위해 빌더사 개발문서를 찾아보았다.
Rate limit의 사용
자주보는 개발 문서중 하나로 shopify 문서를 보자.
rate limit 을 초과한 모든 요청에 대해서는 429 Too Many Requests 에러를 반환한다고 하였다. 그리고 shopify는 기본적으로 leaky bucket 알고리즘을 사용하고 bucket size는 40, leak rate 은 2/sec 이라고 하였다. 위 내용을 이해하기 위해서는 rate limiter에 사용되는 알고리즘을 이해할 필요가 있다.
rate limit 알고리즘
rate limit은 결국 과도한 요청을 막아 서비스의 안정성과 효율성을 높이기 위한 것이다. 목표는 하나이지만 이를 해결하기 위한 방법으로 여러가지 알고리즘이 있다. 앞서 소개한 leaky bucket 을 시작으로 여러가지 rate limit 알고리즘에 대해 알아보자.
Leaky Bucket
구멍이 난 양동이가 있다고 생각해보자. 여기에 물을 넣으면 구멍으로 물이 빠져나갈 것이다. 여기서 물이 빠져 나가는 곳은 요청을 처리하는 곳을 의미한다. 구멍이 난 양동이는 앞서 말한 bucket size를 의미할 것이다. 양동이에 빠져나가는 물의 양보다 들어오는 물의 양이 많다면 양동이에 물은 점점 차기 시작할 것이다. 이러한 상황이 지속되면 결국 양동이의 물이 넘쳐나게 된다. 이 상황을 알고리즘으로 표현하면 기본적으로 bucket size가 있고 물이 빠져나가는 leak rate 이 있다. 위 shopify 상황에서는 기본적으로 bucket size가 40, leak rate 이 2/sec 이라고 했다. 이 의미는 기본 제공되는 bucket은 40이고 1초에 2개의 요청을 처리할 수 있다는 의미다. 결국 처음 요청을 보낼때는 40의 요청을 동시에 보내도 처리할 수 있다. 이때 bucket size는 모두 다 차버리게 되고 이후 부터는 1초에 2개의 요청만 처리할 수 있다. 1초에 2개의 요청보다 더 많은 요청이 들어오게 되면 rate limit 에 걸려 429에러를 반환하게 되는 것이다.
rate limit 정보는 일반적으로 response의 header에서 볼 수 있다. 서비스를 제공하는 회사마다 다른 key값을 사용할 수 있지만 header에 정보가 있을 것이다. shopify의 경우는 header에 다음과 같이 rate limit 정보를 제공해준다.
X-Shopify-Shop-Api-Call-Limit: 32/40
Retry-After: 2.0경우에 따라 어느 시점에 재시도를 해야하는지에 대한 대기 시간 혹은 시점을 정확하게 알려주는 곳도 있을 수 있다. 서비스에 요청을 보내는 사람은 해당 정보를 고려하여 적절한 시간마다 request 하도록 해야한다.
Token Bucket
token bucket 알고리즘은 leaky bucket과 반대되는 관점을 가지고 있다. request 당 1개의 토큰이 필요하다. 처음에는 기본적으로 token bucket은 가득 차있다. requst가 올때마다 bucekt에서 토큰이 있는지를 체크하고 토큰이 있다면 토큰을 하나 빼고 해당 요청을 처리하게 된다. 만약 요청이 너무 많아져서 토큰이 bucket에 없어진다면 에러를 반환하게 된다. bucket 에는 일정 rate으로 token이 추가되게 된다. leaky bucket은 요청이 bucket을 채우는 것이고 token bucket은 요청이 bucket 내용을 빼가는 것으로 서로 반대의 관점이다.
Request throttling for the Amazon EC2 API - Amazon Elastic Compute Cloud
token bucket 알고리즘을 사용하는 곳은 대표적으로 aws 가 있다.
Fixed Window
고정된 시간마다 특정 요청 수를 처리할 수 있는 window가 만들어진다. 해당 시간동안 처리할 수 있는 요청보다 많은 요청이들어 오게되면 해당 요청은 처리가 거부된다. fixed window는 경계 시간대에 요청이 몰리면 두배의 부하를 받게 된다. 구현이 쉽다는 장점이 있지만 경계 시점에 트래픽이 편향될 수 있다는 문제점이 있는 것이다.
시간당 3번의 요청을 처리할 수 있다고 가정하면 2시 경에는 요청이 7번 째에 실패하게 된다.
fixed winodw 알고리즘을 사용하는 곳으로는 github 이 있다.
Resources in the REST API - GitHub Docs
Sliding window log
fixed window 에서 경계 시점에 트래픽이 편향되는 문제가 있다는 점을 알았다. 이 점을 대응하기 위해 개선한 알고리즘이다. 편향된 부분을 해결하기 위해 별도의 로그를 관리해야한다. 별도의 로그 때문에 메모리 비용이 높아지고 구현이 어렵다는 점이 단점이 될 수 있을것 같다.
sliding window counter
fixed window와 sliding window log의 문제점을 개선한 알고리즘이다. window의 경계 내에서 비율로 계산하여 처리하는 방식이다. 경계값 문제와 별도의 메모리를 필요로하는 문제를 개선하였지만 비율로 계산하다보니 정확성이 떨어지는 문제가 있다.
정리
rate limiter를 적용하는 이유와 rate limiter에 사용되는 알고리즘에 대해 알아보았다.
- leaky bucket
- token bucket
- fixed window
- sliding window log
- sliding window count
5가지의 알고리즘에 대해 간단하게 알아보았다. 이 알고리즘 모두 서비스로 오는 과도한 요청을 막고 좀 더 좋은 서비스를 제공하기 위해 사용되어지는 알고리즘이였다. 다음 내용에서는 rate limiter를 애플리케이션에서 처리해보고 애플리케이션 레벨에서 rate limit을 처리하였을때의 문제점을 알아볼 것이다.
