처리율 제한 장치
처리율 제한 장치(rate limter)는 클라이언트 또는 서비스가 보내는 트래픽의 처리율(rate)을 제어하기 위한 장치이다. HTTP에서는 특정 기간 내에 전송되는 클라이언트의 요청 횟수를 제어한다. API 요청 쵯수가 제한 장치의 임계치(threshold)를 넘어서면, 추가로 도달한 모든 호출은 처리가 중단된다.
다음은 처리율 제한 장치를 적용한 예시들이다.
•
사용자는 초당 2회 이상 새 글을 올릴 수 없다.
•
같은 IP 주소로는 하루에 10개 이상의 계정을 생성할 수 없다.
•
같은 디바이스로는 주당 5회 이상 리워드를 요청할 수 없다.
우리는 처리율 제한 장치를 통해 몇 가지 이득을 얻을 수 있다.
•
처리율 제한 장치는 추가 요청에 해단 처리를 중단하므로, DoS(Denial of Service) 공격에 의한 자원 고갈(resource starvation)을 방지할 수 있다. 때문에 대형 IT 기업의 공개 API는 어떤 형태로든 처리율 제한 장치를 두고 있다.
•
추가 요청에 대한 처리를 제한하여 서버를 많이 둘 필요가 없고, 우선 순위가 높은 API에 더 많은 자원을 할당할 수 있어 비용을 절감할 수 있다.
•
봇(bot)에서 오늘 트래픽이나 사용자의 잘못된 이용 패턴으로 유발된 트래픽을 걸러내, 서버 과부하를 막을 수 있다.
1단계 : 문제 이해 및 설계 범위 확정
처리율 제한 장치는 여러 알고리즘으로 구현할 수 있는데, 각각의 장단점을 살리기 위해 면접관과 소통하여 어떤 제한 장치를 구현해야할 지 분명히 할 수 있다.
지원자: 이번 종류의 처리를 제한 장치를 설계해야 하나요? 클라이언트 측 제한 장치입니까, 아니면 서버 측 제한 장치입니까?
면접관: 좋은 질문이에요. 서버측 API를 위한 장치를 설계한다고 가정합시다.
지원자: 어떤 기준을 사용해서 API 호출을 제어해야 할까요? IP 주소를 사용해야 하나요? 아니면 사용자 ID? 아니면 생각하는 다른 어떤 기준이 있습니까?
면접관: 다양한 형태의 제어 규칙(throttling rules)을 정의할 수 있도록 하는, 유연한 시스템이어야 합니다.
지원자: 시스템 규모는 어느 정도여야 할까요? 스타트업 정도 회사를 위한 시스템입니까, 아니면 사용자가 많은 큰 기업을 위한 제품입니까?
면접관: 설계할 시스템은 대규모 요청을 처리할 수 있어야 합니다.
지원자: 시스템이 분산 환경에서 동작해야 하나요?
면접관: 그렇습니다.
지원자: 이 처리를 제한 장치는 독립된 서비스입니까 아니면 애플리케이션 코드에 포함될 수도 있습니까?
면접관: 그 결정은 본인이 내려주시면 됩니다.
지원자: 사용자의 요청이 처리를 제한 장치에 의해 걸러진 경우 사용자에게 그 사실을 알려야 하나요?
면접관: 그렇습니다.
Plain Text
복사
이러한 대화를 통해 우리는 요구서항을 다음과 같이 정리할 수 있다.
•
설정된 처리율을 초과하는 요청은 정확하게 제한한다.
•
처리율 제한 장치는 HTTP 응답 시간에 나쁜 영향을 주면 안된다.
•
가능한 적은 메모리를 사용해야 한다.
•
하나의 처리율 제한 장치를 여러 서버나 프로세스에서 공유할 수 있어야한다.(분산형 처리율 제한)
•
요청이 제한되었을 때는 사용자에게 분명하게 해당 사실을 전달해야한다.
•
제한 장치에 장애가 생기더라도 전체 시스템에 영향을 주어서는 안된다.
2단계 : 개략적 설계안 제시 및 동의 구하기
처리율 제한 장치를 어디에 둘 것인가
처리율 제한 장치는 클라이언트 측에 둘 수도 있고, 서버 측에 둘 수도 있다.
•
클라이언트 측에 두기 : 클라이언트 요청은 쉽게 위변조 가능하기 때문에 안정적이지 못하고, 모든 클라이언트의 구현을 통제하는 것도 어려울 수 있다.
•
서버 측에 두기 : 서버 측에 처리율 제한 장치를 두어 처리할 수 있다.
•
미들웨어로 두기 : 처리율 제한 장치를 미들웨어로 만들어 서버로 가는 API를 통제하도록 만들 수 있다.
클라우드 마이크로서비스의 경우, 처리율 제한 장치는 보통 API 게이트웨이(gateway)라 불리는 컴포넌트에 구현된다. API 게이트 웨이는 처리율 제한 외에도, SSL 종단(termination), 사용자 인증, IP 허용 목록 관리 등을 지원하는 완전 위탁관리형 서비스(클라우드 업체가 유지보수 담당)이다. API 게이트웨이에 구현된 처리율 제한장치는 미들웨어라는 것을 기억하자.
처리율 제한장치를 어디에 둘 지에 대한 정답은 없다. 회사의 기술 스택이나 엔지니어링 인력, 우선순위, 목표에 따라 달라질 수 있다. 그럼에도 일반적으로 적용되는 지침을 살펴보자.
•
프로그래밍 언어, 캐시 서비스 등 사용하고 있는 기술 스택을 점검하고, 현재 사용하고 있는 프로그래밍 언어가 서버 측 구현을 지원할 정도로 효율이 높은지 확인하기
•
비즈니스에 맞는 처리율 제한 알고리즘 찾기
•
아키텍처 확인하기(마이크로서비스에 기반하고 API 게이트웨이가 이미 존재하는지 확인)
•
처리율 제한 장치를 구현할 인력이 없다면 상용 API 게이트웨이를 사용하기
처리율 제한 알고리즘
처리율을 제한하는 여러 알고리즘의 특성을 개략적으로 살펴보자.
토큰 버킷 알고리즘(token bucket)
토큰 버킷 알고리즘은 처리율 제한에 보편적으로 사용되고 있고, 아마존과 스트라이프에서 사용 중인 알고리즘이다. 동작 원리는 다음과 같다.
•
지정된 용량을 갖는 컨테이너인 토큰 버킷을 두고, 사전 설정된 양의 토큰이 주기적으로 채워진다. 버킷에 토큰이 꽉 차있다면 더 이상 토큰이 추가되지 않는다.
•
요청이 도착했을 때 버킷에 토큰이 충분하다면 하나의 토큰을 사용하며 처리하고, 버킷에 토큰이 없다면 해당 요청을 버린다.
•
토큰 버킷의 크기가 4이고 토큰 공급률(refil rate)가 분당 4인 예시는 다음과 같다.
위의 예시처럼 토큰 버킷 알고리즘은 버킷의 크기와 토큰 공급률 두 개의 인자를 갖는다. 두 인자의 크기를 결정하는 것은 공급 제한 규칙에 따라 달라진다.
•
통상적으로 API 엔드포인트마다 별도의 버킷을 둔다.
•
IP 주소별로 처리율 제한을 적용한다면 IP 주소마다 버킷을 할당한다.
•
시스템 처리율을 제한하고 싶다면, 모든 요청이 하나의 버킷을 공유한다.
이러한 토큰 버킷 알고리즘의 장단점은 다음과 같다.
•
장점
◦
구현이 쉽다
◦
메모리 사용이 효율적이다
◦
짧은 시간에 집중되는 트래픽(burst of traffic)도 처리 가능하다
•
단점
◦
두 개의 인자인 버킷 크기와 토큰 공급률을 적절히 튜닝하는 것이 까다롭다.
누출 버킷 알고리즘(leaky bucket)
누출 버킷 알고리즘은 토큰 버킷 알고리즘과 비슷하지만 FIFO 큐를 통해 요청 처리율을 고정했다는 점이 다르다. 전자상거래 기업인 쇼피파이(Shopify)가 이 알고리즘을 사용하여 처리율을 제한하고 있다. 동작원리는 다음과 같다.
•
요청을 받으면 큐를 확인하고, 큐가 비어있다면 요청을 추가하고 빈자리가 없다면 요청을 버린다.
•
지정된 시간마다 큐에서 요청을 꺼내어 처리한다.
누출 버킷 알고리즘에서는 큐 사이즈와 같은 값인 버킷 크기와, 지정된 시간마다 큐에서 몇 개의 요청을 처리할 지를 결정하는 처리율(outflow rate) 두 개의 인자를 사용한다.
누출 버킷 알고리즘의 장단점은 다음과 같다.
•
장점
◦
큐의 크기가 제한되어 있어 메모리 사용량 측면에서 효율적이다.
◦
고정된 처리율을 갖고 있어 안정적인 출력(stable outflow rate)을 가진다.
•
단점
◦
단시간에 많은 트래픽이 몰리고 이를 제때 처리하지 못하면 최신 요청들이 버려진다.
◦
버킷 크기와 처리율 두 개의 인자를 올바르게 튜닝하기 까다로울 수 있다.
고정 윈도 카운터 알고리즘(fixed window counter)
고정 윈도우 카운터 알고리즘은 다음과 같이 동작한다.
•
타임라인을 고정된 간격(window)로 나누고, 각 윈도우마다 카운터를 붙인다.
•
요청이 들어오면 요청 시간에 맞는 윈도우의 카운터를 1 증가시키고, 윈도우의 임계치의 도달하면 다음 윈도우까지 모든 요청을 버린다.
1초의 윈도우를 가지고 초당 3개의 요청만을 허용하는 시스템 예시를 통해 살펴보면,
매초다마 3개의 요청만 처리하고 같은 초에 들어온 남은 요청은 버린다.
이 알고리즘의 가장 큰 문제는 윈도우 경계 부근에 순간적으로 많은 트래픽이 몰리면, 윈도우에 할당된 양보다 더 많은 요청이 처리될 수 있다는 것이다.
분당 5개의 요청만 처리할 수 있도록 설정했지만, 위의 예시처럼 윈도우 경계 부근에 각각 5개씩 처리하여 총 10개의 요청이 몰리게 될 수 있다.
고정 윈도우 알고리즘의 장단점은 다음과 같다.
•
장점
◦
메모리 효율이 좋다.
◦
이해하기 쉽다.
◦
윈도우가 닫히는 시점에 카운터를 초기화 하는 방식으로 특정한 트래픽 패턴을 처리하기에 적합하다.
•
단점
◦
윈도우 경계 부근에서 일시적으로 트래픽이 몰리면, 기대했던 시스템 처리 한도보다 많은 양의 요청을 처리하게 된다.
이동 윈도 로그 알고리즘(sliding window log)
고정 윈도우 알고리즘의 단점을 해결한 이동 윈도 로그 알고리즘의 동작 원리는 다음과 같다.
•
레디스의 Sorted Set과 같은 캐시를 통해 요청의 타임스탬프를 보관한다.
•
새 요청이 오면 현재 윈도우의 시작 지점보다 이전의 요청 타임스탬프를 제거한다.
•
새 요청의 타임스탬프를 로그에 추가하고, 로그에 크기가 허용치 이내라면 요청을 전달하고 아니면 처리를 거부한다.
이동 윈도우 로그 알고리즘의 장단점은 다음과 같다.
•
장점
◦
아주 정교한 메커니즘으로 처리율 제한을 구현할 수 있어, 어느 순간에도 시스템의 처리율 한도를 넘지 않게 요청이 허용된다.
•
단점
◦
거부된 요청의 타임스탬프도 보관하기 때문에 다량의 메모리를 사용한다.
이동 윈도 카운터 알고리즘(sliding window counter)
이동 윈도우 카운터 알고리즘은 고정 윈도우 카운터 알고리즘과 이동 윈도우 로그 알고리즘을 결합한 방식이다. 이동 윈도우 카운터 알고리즘은 두 가지 방식으로 구현할 수 있다.
•
SUB Window 방식
Sub window 방식은 이동하는 윈도우를 여러 개의 sub 윈도우로 쪼개고, 전체 윈도우와 윈도우 내 각각의 sub 윈도우에서 처리율을 제한하는 방식이다.
•
비율 산정 방식
비율 산정 방식은 고정 윈도우 카운터처럼 요청 수를 세고, 현재의 윈도우가 이전 고정 윈도우와 얼마나 겹치는 지를 계산하는 방식이다. 구체적인 공식은 이전 고정 윈도우 요청 수 × 이동 윈도와 겹치는 비율 + 현재 고정 윈도우 요청 수이다.
예를 들어 윈도우 크기가 1분이고 처리율이 5일 때, 고정 윈도우 13:00~13:01에 요청 5개 현재 13:01:15에 요청이 2개 들어온 상황이라면, 5 * 45/60 + 2 = 3.75 + 2 = 5.75로 새로운 요청은 버려진다. 하지만 13:01:30였다면, 5 * 30/60 + 2 = 2.5 + 2 = 4.5로 새로운 요청은 처리된다. 여기서 소수점은 올리거나 내리거나 자유롭게 정할 수 있다.
이런 이동 윈도우 카운터 알고리즘의 장단점은 다음과 같다.
•
장점
◦
이전 시간대의 평균 처리율에 따라 현재 윈도우의 상태를 계산하므로 짧은 시간에 몰리는 트래픽에도 잘 대응한다.
◦
메모리 효율이 좋다.
•
단점
◦
직전 시간대 도착한 요청이 균등하게 분포되어 있다고 가정하기 때문에 다소 느슨하다.(하지만 클라우드플레어 실험 결과 상태와 맞지 않게 처리되는 요청은 0.003%에 불과했다)
개략적인 아키텍처
처리율 제한 알고리즘의 기본 아이디어는 얼마나 많은 요청을, 어떻게(사용자별, IP 주소별, API별, 서비스별) 제한할 지를 결정하여 한도를 넘으면 요청을 거부하는 것이다.
여기서 사용되는 카운터는 빠르고 시간 기반 만료 정책을 쓸 수 있는 메모리상에서 동작하는 캐시가 바람직할 것이다. 자주 사용되는 저장소는 Redis로 INCR와 EXPIRE 두 가지 명령어를 지원하기 때문에, 이 명령어들을 통해 구현한다.
처리율 제한장치는 요청을 받으면 레디스에서 카운터 혹은 토큰 등을 가져와서 한도를 확인하고, 요청을 처리할지 거부할지 결정한다. 요청을 처리한다면 레디스에 카운터 값을 증가시킨다.
3단계 : 상세 설계
3단계에서는 처리율 제한 규칙에 대한 구체적인 사항과 처리 전략을 살펴보고, 분산 환경에서의 처리율 제한 기법과 설계, 최적화 방안, 모니터링 방안을 살펴보자.
처리율 제한 규칙
처리율 제한 규칙은 보통 설정 파일(configuration file) 형태로 디스크에 저장된다.
위는 리프트(Lyft)의 처리율 제한 예시로 마케팅 메세지를 하루 최대 5개로 제한하고 있다.
처리율 한도 초과 트래픽의 처리
한도 제한에 걸리면 어떤 요청이 오더라도 HTTP 429 Too many requests 응답을 클라이언트에 보낸다. 주문이나 결제 시스템 같이 경우에 따라 큐에 보관하여 나중에 처리하도록 할 수 있다.
처리율 제한 장치가 사용하는 HTTP 헤더
클라이언트에서는 처리율 제한에 걸리는지, 제한까지 얼마나 남았는지를 HTTP 헤더를 통해 알 수 있다.
•
X-Ratelimit-Remaining : 윈도우 내 남은 처리 가능 요청 수
•
X-Ratelimit-Limit : 매 윈도우마다 처리 가능한 한도 요청 수
•
X-Ratelimit-Retry-After : 한도 제한에 걸리지 않으려면 몇 초 뒤에 요청을 보내야하는지
상세 설계
•
처리율 제한 규칙은 디스크에 보관하고, 작업 프로세스에서 수시로 캐싱하여 읽는다.
•
클라이언트가 요청을 서버에 보내면, 처리율 제한 미들웨어서 레디스를 통해 카운터나 타임스탬프를 가져오고 규칙에 따라 요청을 처리하거나 거부한다.
분산 환경에서의 처리율 제한 장치 구현
분산 환경에서의 처리율 제한 장치는 병렬 스레드를 지원하도록 확장해야하는데, 경쟁 조건과 동기화 두 가지 문제를 풀어야 한다.
경쟁 조건(race condition)
처리율 제한 장치는 다음의 순서로 동작하는데,
•
레디스에서 카운터 값 읽기
•
counter + 1이 임계값을 넘는지 확인
•
넘지 않는다면 레디스에 보관된 카운터 1 증가
이러한 동작은 병렬 스레드 환경에서 다음처럼 경쟁 조건 이슈가 발생할 수 있다.
이러한 경쟁 조건을 해결하는 가장 널리 알려진 해결책은 락(lock)이지만, 락은 시스템의 성능을 상당히 떨어뜨리게 된다. 위 설계의 경우 루아 스크립트(Lua script)나 레디스의 자료구조 정렬 집합(sorted set)을 통해 해결할 수 있다.
동기화(synchronization)
수백만 사용자를 한 대의 처리율 제한 장치 서버로 처리하는 것은 충분하지 않을 수 있다. 때문에 여러 대의 처리율 제한 장치를 둔다면 동기화가 필요해진다.
위처럼 두 대의 처리율 제한 장치를 둔다면, 각각의 클라이언트가 요청을 보냈을 떄 해당 클라이언트의 정보를 처리율 제한 장치에서 알 수 없는 경우가 생긴다.
이를 해결하는 방법으로는 고정 세션(sticky session)을 활용하여 항상 같은 처리율 제한 장치로 보내는 방법이 있는데 이는 확장에도 불리하고 유연하지 않아 추천하지 않는다.
다른 해결 방법은 위처럼 레디스와 같은 중앙 집중형 데이터 저장소를 사용하는 것이다.
성능 최적화
여태까지의 설계에서는 두 가지 지점에서 개선이 가능하다.
첫 번째는 데이터 센터를 지원할 경우 에지 서버를 두도록 하는 것이다. 멀리 떨어진 사용자는 지연 시간이 증가할 수 밖에 없는데, 대부분 클라우드 서비스는 세계 곳곳에 에지 서버(edge server)를 두어 사용자 트래픽을 가까운 에지 서버로 보내 지연시간을 줄인다.
두 번째는 처리율 제한 장치 간 데이터를 동기화 할 떄는 최종 일관성 모델(eventual consistency model)을 사용하는 것이다. 이 내용은 이후 6장에서 자세히 다룬다.
모니터링
처리율 제한 장치를 추가했다면 효과적으로 적용되는지 확인하기 위해 모니터링을 통해 데이터를 모을 필요가 있다. 이를 통해 채택한 처리율 제한 알고리즘이 효율적인지와 정의한 처리율 제한 규칙(인자)가 효과적인지를 파악해야한다.
제한 규칙이 너무 빡빡하다면 많은 유효 요청이 버려질 것이기 때문에 완화할 필요가 있다. 트래픽이 급증할 때 처리율 제한 장치가 비효율적이라면 토큰 버킷과 같이 상황에 더 적합한 알고리즘으로 바꾸는 것도 고려할 수 있다.
4단계 : 마무리
우리는 처리율 제한 장치의 5가지의 알고리즘과 아키텍처, 분산환경에서의 처리율 제한, 성능 최적화와 모니터링 등을 살펴보았다. 추가적으로 면접 때 다음과 같은 내용을 언급하면 도움이 될 것이다.
•
경성(hard, 임계치를 절대 넘을 수 없음) 처리율 제한 혹은 연성(soft, 잠깐동안 임계치를 넘을수도 있음) 처리율 제한
•
다양한 계층에서의 처리율 제한
◦
위 내용은 OSI 7계층 중 애플리케이션 계층에서의 처리율 제한 위주
◦
Iptables를 사용하면 3계층에서의 처리율 제한을 적용 가능
•
클리언트 설계 시 처리율 제한을 회피하는 방법
◦
클라이언트 측 캐시를 사용해 API 호출 줄이기
◦
처리율 제한의 임계치를 이해하고 짧은 시간동안 너무 많은 요청 보내지 않기
◦
예외나 에러를 처리하는 코드를 도입해, 클라이언트가 예외 상황에서 gracefully하게 복구될 수 있도록 하기
◦
재시도 로직 구현 시 충분한 백오프(back-off) 시간 두기