규모가 있는 시스템을 맡게 되면서 더 필요한 지식이라 느끼게 되어서 새롭게 공부해보는 내용이다.
처리율 제한 장치의 설계 (1)
처리율 제한 장치란?
네트워크 시스템에서 처리율 제한 장치란 서비스가 보내는 트래픽의 처리율 (rate) 를 제어하는 장치다.
예를 들어, 클라이언트가 보내는 HTTP 요청 수를 제한해서 서버에 부하르 막을 수 있다.
- 사용자는 초당 2회 이상 새 글을 올릴 수 없다
- 같은 IP 주소로는 하루에 10개 이상의 계정을 생성할 수 없다.
처리율 제한 장치의 범위는 어디까지인가?
처리율 제한 장치를 설계할 때는 어디에 적용할지를 생각해볼 수 있다.
-
클라이언트 측 제한 장치인가? 혹은 서버 측 제한 장치인가?
-
API 호출은 어떤 기준으로 제어해야 하는가? IP 주소? 사용자의 ID? 혹은 다양한 형태의 제어 규칙 (throttling rules) 이 될 수 있다.
-
분산 환경에서 동작하는 처리율 제한 장치인가?
-
처리율 제한 장치는 독립된 서비스인가? 혹은 애플리케이션 코드에 포함될 수 있는가?
처리율 제한 장치의 설계 (2)
처리율 제한 장치 위치
-
클라이언트에 처리율 제한장치를 두는것은 안정적이지 않을 수 있따. 왜냐면 클라이언트 요청은 쉽게 위변조가 가능해서다. 모든 클라이언트의 구현을 통제하는 것은 어려울 수 있다.
-
서버측에 두는 방법도 가능하다.
-
처리율 제한 장치를 API 서버가 아닌 미들웨어를 만들어서 API 서버로 가는 요청을 통제할 수 있다 (예시 : API Gateway)
만약에 클라이언트에서의 요청이 정해진 rate limit 보다 높다면은 429 too many request 를 알려서 제어해줄 수 있다. 이런 대표적인 미들웨어 rate limit 은 API Gateway 가 존재한다.
처리율 제한 기능을 설계할 떄 중요하게 따져야 하는 한가지는 어디에 둘것인가? 의 질문이다. 그리고 이 질문에 답은 기술 스택이나 목표에 따라 달라질 수 있다.
처리율 제한 알고리즘
처리율 제한을 실현하는 알고리즘으로 다양한 형태가 존재한다. 대표적인 알고리즘 몇개를 요약한다.
토큰 버킷 알고리즘
가장 폭 넓게 사용되는 알고리즘이다. 해당 원리는 다음과 같다.
-
토큰 버킷은 지정한 용량을 갖는 컨테이너다. 이 버킷에는 사전에 설정된 양의 토큰이 '주기적' 으로 채워진다. 토큰이 꽉 차게되면 추가적인 토큰은 생성되지 않고, 토큰 공급기 (refiller) 은 이 버킷에 매초 n개의 토큰을 추가한다. 버킷이 가득차면 추가로 공급된 토큰은 버려진다 (overflow)
-
각 요청은 처리될 때마다 하나의 토큰을 사용한다. 가장 먼저 요청이 도착하면 충분한 토큰이 있는지 검사한다.
-
충분하다? -> 버킷에서 토큰을 하나 꺼내서 요청을 처리
-
충분하지 않다? -> 해당 요청은 버려진다 (dropped)
토큰 버킷 알고리즘 규칙은 심플하다. 처리할 수 있는 양만큼 토큰이 있다면 해당 토큰을 사용해 요청을 처리하고, 토큰이 없다면 버린다. 그리고 공급기 (refiller) 을 통해서 토큰은 다시 채워진다 (특정 시간이 지나서)
그래서 토큰 버킷 알고리즘은 버킷 크기와 토큰 공급률 (refill rate) 를 받아서 초당 몇개의 토큰이 버킷에 공급되는가를 정할 수 있다. 예시로 다음과 같이 사용 가능하다.
- IP 주소별로 처리율 제한을 건다면, 각 IP 주소마다 버킷을 하나씩 할당할 수 있다.
- 시스템 자체의 처리율을 10,000 개 요청으로 제한하고 싶다면 모든 요청이 하나의 버킷을 공유하도록 할 수 있다.
단점으로는 버킷 크기와 공급률을 적절하게 튜닝하기 까다롭다고 한다.
누출 버킷 알고리즘
토큰 버킷 알고리즘과 유사하다. 누출 버킷 알고리즘은 보통 FIFO 로 큐로 구현되어있다.
-
요청이 도착하면 큐가 가득 차 있는지 본다, 빈자리가 있는 경우에는 큐에 넣고 가득 차 있으면 버린다.
-
지정된 시간마다 큐에서 요청을 꺼내어 처리한다.
토큰버킷 알고리즘에서는 공급률 (refill rate) 가 존재했다면 누출 버킷 알고리즘에서는 처리율 (outflow rate) 지정된 시간당 몇개의 항목을 처리할지 지정하는 값이 있다.
단점으로는 단기간에 많은 트래픽이 쌓이게 되면 오래된 요청들이 많이 쌓이게 되고 최신 요청이 버려질 확률이 높다.
고정 윈도 카운터 알고리즘
타임라인 안에서 고정된 간격의 윈도(window) 를 나누고 각 윈도우마다 카운터를 붙힌다
요청이 접수될때마다 카운터의 값을 1 증가하고, 이 카운터의 값이 설정된 임계치 (threshold) 에 도달하면 새로운 요청은 새 윈도우가 열릴 때 까지 버려진다.
- 이 알고리즘의 단점은 순간적으로 많은 트래픽이 집중될 경우 윈도우 할당된 양보다 더 많은 요청이 처리될 수 있따. 즉, 처리율 제한이 원하는데로 되지 않을 수 있다.
이동 윈도 로깅 알고리즘
앞서 설명한 고정 윈도 카운터 알고리즘의 한계는 많은 트래픽이 집중될 경우 기대했던 처리 한도보다 더 많은 양의 요청을 처리할 수 있다. 이동 윈도 로깅 알고리즘은 이 문제를 요청의 timestamp 를 추적하는 방식으로 극복한다.
timestamp 값은 주로 Redis 의 Sorted set 과 같은 캐시에 보관한다. 동작 방식은 아래와 같다.
- 새 요청이 오면만료된 timestamp 는 제거한다.
- 새 요청의 timestamp log 를 추가한다.
- log 의 크기가 허용치보다 같거나 작으면 요청을 시스템에 전달한다. 그렇지 않은 경우에는 처리를 거부한다.
이 알고리즘의 단점으로는 거부된 요청의 타임스탬프도 보관하기 때문에 다량의 메모리를 사용한다.
개략적인 아키텍처
처리율 제한 알고리즘 간단 요약
처리율 제한 알고리즘의 아이디어는, 얼마나 많은 요청이 접수되었는지 확인할 수 있는 카운터를 대상 별로 두고 (사용자별 or IP 별 등) 이 카운터의 값이 어떤 한도를 넘어가면 도착한 요청을 버리는 것이다.
그렇다면 이 카운터는 어디에 보관할 것인가? 에 대한 질문으로 책에서는 메모리상에서 동작하는 캐시가 바람직하다고 정의했다.
- 메모리상에서 도착하기 때문에 빠름
- 시간에 기반한 만료 정책을 지원한다
레디스를 두게 되었을때 개략적인 도작방식은 아래와 같다.
- 클라이언트가 처리율 제한 미들웨어에 요청을 보낸다
- 처리율 제한 미들웨어는 레디스의 지정 버킷에서 카운터를 가져와서 한도에 도달했는지 확인한다. 한도에 도달했으면 요청은 버린다.
- 한도에 도달하지 않았다면 API 서버로 전송된다. 미들웨어는 카운터의 값을 증가한후 다시 레디스에 저장한다.
해당 조건은 단일 서버를 대상으로 적용했을 때 구현은 어렵지 않다. 하지만 분산 서버라면? 레디스에서 카운터의 값을 증가하는 방식을 사용하게 된다면 Race Condition 은 피하지 못하는 숙제다. 이런 경쟁 조건을 Lock 방식 외에 해결할 수 있는건 뭐가 있을까? 레디스 자료구조의 Sorted Set 을 이용할 수 있지만 이건 나중에 추가로 작성하는것으로 마무리하겠다.
