처리율 제한 장치의 목적, 활용, 설계 고려사항, 알고리즘
Rate Limiter
= 클라이언트 또는 서비스가 보내는 트래픽의 처리율을 제어하기 위한 장치.
= 아예 트래픽을 받지 않는게 아니라, 트래픽을 받은 후 처리를 할 지 말지를 결정하는 장치.
활용
- DoS 공격으로 인한 피해 방지
- 비용 절감
- 서버 과부하 방지
Rate Limiter 설계 시 고려사항
어디에 둘까
처리율 제한 기능을 설계할 때 중요하게 따져야 하는 것 하나는 이것이다. 처리율 제한 장치는 어디 두어야 하나?
클라이언트-서버 모델에서, 처리율 제한 장치는 양쪽 모두에 둘 수 있다. 하지만 클라이언트에 두지는 않는다. 왜냐하면
- 클라이언트 요청은 쉽게 위변조할 수 있고
- 모든 클라이언트의 요청을 통제하기 어려울 수 있기 때문이다.
따라서 rate limiter는 서버측에 두거나, 아니면 클라이언트와 서버 가운데에 미들웨어를 만들어 둘 수 있다. 이런 미들웨어의 가장 대표적인 예시로 게이트웨이가 있다. 게이트웨이의 여러가지 역할(사용자 인증, SSL termination, whitelist 관리 등) 중 하나로 처리율 제한 기능을 만드는 것이다.
기타
- 낮은 응답 시간 latency: HTTP 응답 시간에 나쁜 영향을 주면 안된다.
- 적은 메모리 사용량
- 분산형 처리율 제한: 하나의 처리율 제한 장치를 여러 서버, 프로세스에서 공유할 수 있어야 한다.
- 예외 처리: 요청이 제한되었을 때 사용자에게 이를 알려줘야 한다.
- 높은 내결함성 fault to tolerance: 처리율 제한 장치가 뻗어도 전체 시스템에 영향을 주어서는 안된다.
처리율 제한 알고리즘 훑어보기
토큰 버킷 token bucket
요청을 처리할 수 있는 토큰을 버킷에 담아서 사용한다.
- 사용자는 토큰을 담는 버킷을 갖는다. 토큰 1개당 요청 1개를 처리할 수 있다.
- 이 때 처리율 제한의 대상과 방식에 따라 '사용자'가 의미하는게 달라질 수 있다. 예를 들어 '한 사람이 1분동안 1000개의 요청을 보낼 수 있다'를 구현하려면 사람 1명당 버킷 1개를 가질 것이고, '한 사람이 1분동안 각 API마다 100개의 요청을 보낼 수 있다'를 구현한다면 한 사람당 갖는 버킷의 개수는 API 개수와 같을 것이다.
- 토큰은 일정 시간 간격을 두고 특정 개수만큼 채워진다. 시간 단위당 토큰을 채우는 비율을 refill rate 이라고 한다.
- 버킷에 저장된 토큰은 버킷에 저장할 수 있는 최대 토큰 개수를 넘어갈 수 없다. 즉, 시간이 아무리 오래 지나더라도 bucket size를 넘는만큼 토큰을 가질 수 없다.
- 이 알고리즘에서는 2가지 값을 튜닝해야 한다: refill rate과 bucket size.
- 아마존과 스트라이프가 이 알고리즘을 사용한다고 한다.
누출 버킷 leaky bucket
버킷에 요청을 담고, 이 요청이 밖으로 빠져나가면서 처리된다. 토큰 버킷과 비슷하게 버킷이 있지만, 요청 처리율이 고정되어있다는 점이 다르다.
- 사용자는 고정된 사이즈의 큐를 갖는다. 큐에는 사용자가 보낸 요청이 저장된다.
- 보통 FIFO 큐로 구현한다.
- 큐에 빈 자리가 있으면 요청을 넣고, 그렇지 않으면 요청을 버린다.
- 지정된 시간만큼 요청을 꺼내어 처리한다. 이 때 특정 시간당 처리할 요청의 개수의 비율을 outflow rate이라고 한다.
- 이 알고리즘에서도 2가지 값을 튜닝해야 한다: outflow rate과 bucket size.
- 쇼피파이가 이 알고리즘을 사용한다고 한다.
고정 윈도 카운터 fixed window counter
시간을 고정된 간격으로 자르는 윈도를 사용한다.
- 각 윈도마다 카운터를 붙인다. 요청이 접수될 때마다 카운터는 1씩 증가한다.
- 카운터 값이 사전에 설정한 임계치 threshold에 도달하면, 새 윈도가 시작되기 전까지 모든 요청을 버린다.
- 하지만 이 알고리즘은 치명적인 문제가 있다.
- 윈도의 경계 부근에 순간적으로 많은 트래픽이 몰렸을 경우, 임계치를 넘는 요청을 처리하게 된다. 각 윈도 하나씩만 놓고 보면 임계치를 넘지 않지만 윈도의 위치를 조금 옮겨보면 특정 시간동안 너무 많은 요청을 처리하게 된다.
이동 윈도 로그 sliding window log
고정 윈도 카운터 알고리즘의 문제를 해결한다. 윈도가 시간을 고정된 간격으로 나누는게 아니라 계속 움직이면서 요청을 처리한다.
- 요청의 타임스탬프를 추적한다.
- 타임스탬프 데이터는 보통 레디스의 sorted set 같은 캐시에 보관한다.
- 새 요청이 오면 만료된 타임스탬프를 제거하고, 새 요청의 타임스탬프를 로그에 추가한다.
- 만료된 타임스탬프: 현재 윈도의 시작 지점보다 오래된 타임스탬프.
- 로그의 크기가 허용치 이하라면 요청을 처리한다.
이동 윈도 카운터 sliding window counter
고정 윈도 카운터와 이동 윈도 로깅 알고리즘을 결합한 것이다. 이를 구현하기 위해서는 2가지 접근법이 있는데 책에서는 한가지만 소개하고 있다.
- 이동 윈도 로깅 알고리즘과 마찬가지로, 윈도가 움직인다.
- 특정 시점에 들어온 요청을 처리할 때, 현재 윈도만 보는게 아니라 그동안 처리한 요청의 개수도 함께 확인한다. 이전 시간대의 평균 처리율에 따라 현재 윈도의 상태를 계산한다.
- 이 2가지 정보를 바탕으로 현재 1분동안 처리할 요청 수를 결정한다.
- 즉, '현재 윈도'에 해당하는 시간이 '현재 1분'일 수도, 아닐 수도 있다.
- 예를 들어, 직전 1분동안 너무 많은 요청을 처리했다면 현재 1분동안 처리할 요청 개수는 줄어들 것이고 이를 통해 윈도 1개에서 처리하는 요청의 양을 조절한다.
요약
| 알고리즘 | 구현 난이도 | 메모리 사용 | Burst of traffic 대처 | 까다로운 parameter 개수 |
|---|---|---|---|---|
| 토큰 버킷 | 👍 쉬움 | 👍 적음 | 👍 가능 | 👎🏾 2개 |
| 누출 버킷 | 👍 쉬움 | 👍 적음 | 👎🏾 고정된 처리율 | 👎🏾 2개 |
| 고정 윈도 카운터 | 👍 쉬움 | 👍 적음 | 👎🏾 임계치를 넘길 수 있음 | |
| 이동 윈도 로그 | 보통? | 👎🏾 많음 | 👍 가능 | |
| 이동 윈도 카운터 | 👎🏾 복잡 | 👍 적음 | 👍 가능 |
분산 환경에서 Rate Limiter 구현
경쟁 조건 race condition
병렬성이 높은 환경에서 카운터, 임계값 등 처리율을 제한하기 위해 저장하고 있는 값을 '동시에' 읽게 되는 경우, 경쟁 조건 이슈가 발생할 수 있다. 이를 해결할 수 있는 몇가지 해결책이 있다.
- 락 lock 구현하기: 경쟁 조건을 막을 수 있는 강력한 방법이지만, 시스템의 성능을 상당히 떨어뜨릴 수 있다.
- 루아 스크립트 Lua script 사용하기
- 레디스의 정렬 집합 sorted set 사용하기
동기화 synchronization
수백만 사용자를 지원하려면, 처리율 제한 장치 1대로는 부족해질 수 있다. 그러면 처리율 제한 장치가 여러개가 되어야 하는데 이 때 동기화가 잘 이루어져야 한다. 이를 해결하기 위해서는 아래 해결책이 있다.
- 고정 세션 sticky session 활용: 같은 클라이언트가 보낸 요청은 항상 같은 처리율 제한 장치로 보내는 방식
- 하지만 이는 비추천한다. 확장 가능하지도 않고 유연하지도 않다. 고정 세션에 대해서는 이전 장에서도 같은 단점이 언급되었다.
- 레디스와 같은 중앙 집중형 데이터 저장소 사용: 처리율 제한 장치는 여러개로 두되, 이들이 사용할 정보(카운터, 임계값 등)는 하나의 데이터 저장소에 저장하고 사용하는 방식.
기타 고려사항
성능 최적화
처리율 제한 장치의 성능을 최적화 하기 위해서 사용할 수 있는 방법이 몇가지 있다.
-
사용자와 지리적으로 가까운 곳에 물리적 서버를 두는 것
-
처리율 제한 장치 간 동기화를 할 때, 최종적 일관성 모델을 사용하는 것
-
최종적 일관성: 데이터베이스에 쓰기를 멈추고 불특정 시간 동안 기다리면 결국 모든 읽기 요청이 같은 값을 반환한다. 이를 보장하는 데이터베이스는 최종적 일관성을 보장한다고 표현한다. (데이터 중심 애플리케이션 설계, 9장) (이 책에서는 6장에서 소개할 예정이다.)
-
즉, 불특정 시간 동안은 일관성이 보장되지 않을 수 있다는 뜻이다. 이렇게 하는 이유는 성능과의 trade off 때문이다.
-
모니터링
처리율 제한 장치에서 모니터링의 목적은 다음 2가지다.
- 선택한 처리율 제한 알고리즘이 효과적이다.
- 정의한 처리율 제한 규칙이 효과적이다.
즉, 한 번 설계한 처리율 제한 장치의 알고리즘과 규칙이 효과적인지 계속 모니터링하면서 조정할 값은 조정해야 한다.
