가상 면접 사례로 배우는 대규모 시스템 설계 기초 4장 - 처리율 제한 장치의 설계
가상 면접 사례로 배우는 대규모 시스템 설계 기초 책 정리 글입니다.
개요
이 장에서는 클라이언트가 보내는 트래픽을 제한하는 방법을 설명한다.
클라이언트의 요청 횟수를 제한하는것이 대표적이며, 처리율을 제한함으로써 얻는 이점은 다음과 같은게 있다.
- Dos(Denial of Service) 공격에 의한 자원고갈을 방지할 수 있다.
- 비용절감. 만약 써드 파티API에의해 서비스를 제공하고 있다면 처리율을 제한함으로써 비용절감 효과를 볼 수 있다.
- 서버 과부하 제어. Dos 방지와 비슷하게 사용자의 잘못된 패턴으로 유발된 트래픽을 걸러내거나 봇(bot)을 이용한 유발된 트래픽을 걸러낼 수 있다.
✏️ 1단계: 문제 이해 및 설계 범위 확정
처리율 제한 장치를 구현하는 데는 여러 알고리즘을 사용할 수 있는데, 질문을 통해서 어떤 제한 장치를 구현해야할 지 명확히 할 필요가 있다.
- 서버측 제한장치 or 클라이언트 제한장치인지?(서버측 제한 장치라 가정)
- IP주소를 기준으로? 사용자ID를 기준으로 API호출을 제한해야할지? 또 다른 기준이 있는지?
- 시스템 규모는 스타트업 정도인지? 사용자가 많은 큰 기업인지?
- 분산 환경에서도 작동해야하는지?
- 처리율 제한 장치는 독립된 서비스인지? 애플리케이션 코드에 포함 되는지?
- 처리율 제한에 걸리면 사용자에게 알려야하는지?
✏️ 2단계: 개략적 설계안 제시 및 동의 구하기
기본적인 클라이언트-서버 통신 모델을 사용하도록 하자.
처리율 제한 장치는 어디에 둘 것인가?
클라이언트에 둘 수도 있고 서버에 둘 수도 있다.
- 클라이언트에 둔다: 클라이언트 요청은 쉽게 위/변조가 가능해서 모든 클라이언트를 통제하기가 어렵다. 클라이언트에 두는 선택이 좋은 선택이 될 수 없다.
- 서버에 둔다: 서버측에 제한 장치를 두거나, 처리율 제한 미들웨어(middleware)를 만들어 해당 미들웨어로 하여금 API 서버로 가는 요청을 제한한다.
만약 미들웨어를 두고 초당 2번씩 요청을 받는 제한을 걸었다고 치자.
만약 3번째 요청이 오면 다음과 같이 reject할 것이다.
클라우드 마이크로서비스의 경우, 처리율 제한 장치는 보통 API 게이트웨이라 불리는 컴포넌트에 의해 구현된다.
API 게이트웨이는 처리율 제한, SSL종단, 사용자 인증, IP 목록 관리 등을 지원하는 클라우드 업체가 유지 보수를 담당하는 서비스이다.
그래서 API 게이트웨이를 둬서 중간에 요청을 막는게 좋은지, 서버에 둬서 요청을 막는게 좋은지는 회사의 기술스택이나 인력, 우선순위, 목표에 따라 달라진다고 한다.
고려해야할 사항은 다음과 같다.
- 프로그래밍 언어, 캐시 서비스 등 현재 사용하고 있는 기술스택이 서버에서 처리율 제한을 구현할 정도로 효율이 좋은지 확인해야 한다.
- 처리율 제한 알고리즘을 정하고, 제 3사업자가 제공하는 게이트웨이가 해당 알고리즘을 지원하는지 확인해야한다. 서버측에서 모든걸 구현하기로 했다면 알고리즘은 자유롭게 선택할 수 있다.
처리율 제한 알고리즘
- 토큰 버킷(token bucket)
- 누출 버킷(leaky bucket)
- 고정 윈도 카운터(fixed window counter)
- 이동 윈도 로그(sliding window log)
- 이동 윈도 카운터(sliding window counter)
토큰 버킷 알고리즘
아마존과 스트아리프가 API 요청을 통제하기 위해 이 알고리즘을 사용한다. 폭넓게 이용되어, 개발자들의 이해도가 높은 편이다.
동작 원리
토큰 버킷은 지정된 용량을 가지는 컨테이너다.
이 버킷에는 사전에 설정된 양의 토큰이 주기적으로 채워지는데, 토큰이 꽉 차면 더 이상의 토큰은 추가되지 않고, 추가로 공급된 토큰들은 버려진다.
그림은 용량이 4인 버킷이고 매초 2개의 토큰을 추가한다. 그리고 더 추가되는 토큰들은 버려진다.
각 요청은 처리될 때마다 하나의 토큰을 사용한다. 요청이 도착하면 토큰이 있는지 검사하고 토큰이 있으면 버킷에서 토큰 하나를 꺼내, 요청을 처리하고 토큰이 없는 경우 해당 요청은 버려진다.
토큰 버킷은 2개의 인자를 받는다.
- 버킷 크기: 버킷에 담을 수 있는 최대 토큰의 수
- 토큰 공급률: 초당 몇 개의 토큰이 버킷에 공급되는지
버킷을 몇 개나 사용해야하는지는 공급 제한 규칙에 따라 달라진다.
- 통상적으로, API 엔드포인트마다 별도의 버킷을 둔다. 사용자마자 하루에 한 번 포스팅을 할 수 있고, 하루에 한 번 댓글을 달 수 있고, 150명의 친구를 추가할 수 있다고 하면 사용자마다 3개의 버킷을 두어야할 것이다.(포스팅API, 댓글API, 친구추가API)
- IP 주소별로 처리율을 제한해야한다면 IP 주소마다 하나의 버킷을 둬야할 것이다.
- 시스템 처리율을 초당 10,000개 요청으로 제한하고 싶다면, 모든 요청이 하나의 버킷을 공유해야 할 것이다.
장점
- 구현이 쉽다.
- 메모리 사용 측면에서도 효율적이다.
- 짧은 시간에 집중되는 트래픽도 처리 가능하다.
단점
- 버킷 크기와 토큰 공급률을 적절하게 튜닝하는 것은 까다로운 일이다.
누출 버킷 알고리즘
토큰 버킷 알고리즘과 비슷하지만 요청 처리율이 고정되어 있다는것이 다르다. 보통 FIFO 큐로 구현된다.
동작 원리
- 요청이 도착하면 큐가 가득 차 있는지 확인한 뒤, 빈 자리가 있으면 큐에 요청을 추가
- 큐가 가득 차 있는 경우에는 새 요청은 버린다.
- 지정된 시간마다 큐에서 요청을 꺼내서 처리.
누출 버킷 알고리즘은 두 개의 인자를 갖는다.
- 버킷 크기: 큐 사이즈와 같은 값.
- 처리율: 지정된 시간당 몇 개의 항목을 처리할지 지정하는 값. 보통 초 단위
장점
- 큐의 크기가 제한되어 메모리 사용량 측면에서 효율적
- 고정된 처리율을 갖고 있어서 안정된 출력(stable outflow rate)가 필요한 경우에 적합.
단점
- 단시간에 많은 트래픽이 몰리면 큐에 요청들이 쌓이고, 요청을 제때 처리하지 못하면 최신 요청들이 버려진다.
- 토큰 버킷과 마찬가지로 두 개의 인자를 튜닝하는것이 까다롭다.
고정 윈도 카운터 알고리즘
동작방식
- 타임라인을 고정된 간격의 윈도(window)로 나누고, 각 윈도마다 카운터를 붙인다.
- 요청이 접수될 때마다 카운터의 값은 1씩 증가한다.
- 이 카운터의 값이 사전에 설정된 임계치에 도달하면 새로운 요청은 새 윈도가 열릴때까지 버려진다.
위의 예제를 해석하자면 타임라인은 1초이고, 시스템은 초당 3개까지의 요청을 허용한다. 만약 3개 이상의 요청이 밀려오면 초과분은 버려진다.
이 알고리즘은 문제는 경계 부근에 순간적으로 많은 트래픽이 집중된 경우 할당된 양보다 더 많은 요청이 처리될 수 있다는 것이다.
위 예제는 분당 최대 5개의 요청을 허용하는 시스템이다.
분마다 카운터가 초기화 되는데, 2:00:30초부터 2:01:30초까지 10개의 요청이 몰려 처리해버리게 된다. 이는 2:01:00초에 카운터가 초기화되서 이런 현상이 벌어진 것이고, 분당 최대 5개 처리하는 허용 한도의 2배를 처리해버리게 되는 것이다.
장점
- 메모리 효율이 좋다.
단점
- 위와같이 윈도 경계 부근에서 일시적으로 많은 트래픽이 몰리는 경우, 설정했던 처리 한도보다 많은 양의 요청을 처리하게 된다.
이동 윈도 로깅 알고리즘
고정 윈도 카운터 알고리즘의 문제를 해결하기 위해 나타난 알고리즘이다.
동작원리
- 요청의 타임스탬프(timestamp)를 추적한다. 타임스탬프 데이터는 보통 레디스(Redis)의 정렬 집합(sorted set)와 같은 캐시에 보관한다.
- 새 요청이 오면 만료된 타임스탬프는 제거한다.
- 새 요청의 타임스탬프를 로그에 추가한다.
- 로그의 크기가 허용치보다 같거나 작으면 요청을 시스템에 전달하고 그렇지 않은 경우 처리를 거부한다.
위의 예시는 그림을 보면 간단히 이해가 되기에 추가적으로 해석하지는 않겠습니다.
장점
- 처리율 제한 매커니즘은 아주 정교하다. 어느 순간 윈도를 보더라도, 허용되는 요청의 개수는 시스템의 처리율 한도를 넘지 않는다.
단점
- 다량의 메모리를 사용한다. 거부된 요청의 타임스탬프도 보관되기 때문이다.
이동 윈도 카운터 알고리즘
고정 윈도 카운터 알고리즘 + 이동 윈도 로깅 알고리즘을 결합한 것이다.
두 가지 접근법이 있지만 여기서는 하나만 다루었다.
처리율 한도가 분당 5개인데, 이전 1분에서 5개 현재 1분동안 3개의 요청이 왔다. 현재 1분의 30%시점(1분 18초정도?)에 요청이 도착한 경우 현재 윈도에 몇 개의 요청이 온 것으로 보고 처리해야할까?
- 현재 1분간의 요청 수 + 직전 1분간의 요청 수 * 이동 윈도와 직전 1분이 겹치는 비율
=> 이 공식에 따라 현재 윈도에 들어 있는 요청은 3+5 * 70% = 6.5개다. 올림하거나 내림할 수 있는데 예제에서는 내림해서 6개로 계산하였다.
처리율 한도가 분당 7개라하면 현재 1분의 30%시점에 도착한 신규 요청은 시스템으로 전달되지만 처리율 한도가 분당 5개라면 요청을 받을 수 없을 것이다.
장점
- 메모리 효율이 좋다.
- 이전 시간대의 평균 처리율에 따라 현재 윈도의 상태를 계산하므로 짧은 시간에 몰리는 트래픽에도 잘 대응한다.
단점
- 직전 시간대에 도착한 요청이 균등하게 분포되어 있다고 가정한 상태에서 추정치를 계산하기에 다소 느슨하지만, 그렇게 심각하지는 않다.
개략적인 아키텍처
위에서 설명한 카운터는 어디에 보관할 것인가? 데이터베이스는 디스크접근을 해야하므로 느려서 안된다. 빠른데다가 시간 만료 정책을 지원하는 캐시가 적절하다. 레디스(Redis)는 처리율 제한 장치를 구현할 때 자주 사용되는 메모리 기반 저장장치다. 카운터에 관한 명령어도 지원한다.(INCR, EXPIRE)
✏️ 3단계: 상세 설계
- 처리율 제한 규칙은 어떻게 만들어지고 어디에 저장되는가?
- 처리가 제한된 요청들은 어떻게 처리되는가?
에 대한 이야기다.
처리율 제한 규칙
리프트라는 회사는 처리율 제한에 오픈소스를 사용하고 있다.
1
2
3
4
5
6
7
domain: messaging
descriptiors:
- key: message_type
Value: marketing
rate_limit:
unit: day
requests_per_unit: 5
마케팅 메시지의 최대치를 하루 5개로 제한하는 예제
이런 규칙들은 보통 설정 파일 형태로 디스크에 저장된다.(.env같은거 말하는듯)
처리율 한도 초과 트래픽의 처리
어떤 요청이 한도 제한에 걸리면 HTTP 상태코드는 429(too many requests)를 클라이언트에 보낸다.
경우에 따라 요청을 처리하기 위해 큐에 보관하여 처리할 수도 있을 것이다.
처리율 제한 장치가 사용하는 HTTP헤더
클라이언트가 자기 요청이 처리율 제한이 걸리고 있는지, 자기 요청이 처리율 제한에 걸리기까지 얼마나 많은 요청을 보낼 수 있는지를 알 수 있을까?
HTTP 응답헤더에는 이러한 정보를 담고 있다.
- X-Ratelimit-Remaining: 윈도 내에 남은 처리 가능 요청의 수
- X-Ratelimit-Limit: 매 윈도마다 클라이언트가 전송할 수 있는 요청의 수
- X-Ratelimit-Retry-After: 한도 제한에 걸리지 않으려면 몇 초 뒤에 요청을 다시 보내야하는지에 대한 정보
정리
- 처리율 제한 규칙은 디스크에 저장하고 작업 프로세스가 수시로 디스크에서 읽어서 캐시에 저장.
- 클라이언트가 요청을 보내면 처리율 제한 미들웨어에 도착.
- 처리율 제한 미들웨어는 캐시에서 규칙을 가져오고 카운터 및 마지막 요청의 타임스탬프를 레디스 캐시에서 가져온 뒤, 가져온 값에 근거하여 결정을 내린다.
- 해당 요청이 처리율 제한에 걸리지 않으면 API서버로 보냄.
- 처리율 제한에 걸리면 Http Status는 429를 보냄. 요청은 폐기하거나 큐에 보관.
분산 환경에서의 처리율 제한 장치의 구현
여러 대의 서버와 병렬 스레드를 지원하도록 시스템을 확장하는 것은 또 다른 문제다.
경쟁 조건과 동기화라는 어려운 문제를 해결해야하기 떄문이다.
경쟁 조건
처리율 제한 장치는 대략 다음과 같이 동작한다.
- 레디스에서 카운터의 값을 읽는다.
- counter+1이 임계치를 넘는지 본다.
- 넘지 않는다면 레디스에 보관된 카운터 값을 1 증가시킨다.
여기서 문제는 counter+1에 있는데
요청들이 counter를 증가시키기 전에 캐시에서 꺼내버리면 다음과 같은 일이 벌어진다.
사실상 요청이 2개가 끝난 뒤 counter값은 5가되어야하지만 병렬로 읽어버려서 counter값은 5가 안 될수도 있다는 것이다.
이를 해결하기 위해서 락(lock)을 걸 수도 있지만 성능이 떨어진다는 문제가 있다.
그래서 루아 스크립트(Lua script)나 정렬 집합(sorted set)이라 불리는 레디스 자료구조를 사용하여 해결할 수 있다.
동기화 이슈
수백만의 사용자를 지원하려면 하나의 처리율 제한 서버로는 부족할 것이다. 그래서 처리율 제한 장치 서버를 여러 대 두게 되는데, 이 경우 동기화가 필요해진다.
저번에 설명한 고정 세션을 통해서 같은 클라이언트로부터의 요청은 항상 같은 처리율 제한 장치로 보낼 수 있지만 확실히 유연하지 않다.
더 나은 해결책은 레디스와 같이 중앙 집중형 데이터 저장소를 사용하는 것이다.
성능 최적화
서버와 멀어지면 사용자에게 응답을 주는 지연시간(latency)가 증가할 수 밖에 없다. 이를 고려해야한다.
또한, 제한 장치간에 데이터를 동기화할 때 최종 일관성 모델을 사용해야하는데 이것도 고려해야할 점이다.
모니터링
요약하자면 채택된 처리율 제한 알고리즘이 효과적인지, 정의한 처리율 제한 규칙(파라미터)등이 효과적인지를 확인해야 한다.
✏️ 4단계: 마무리
책에서는 다음과 같은 부분을 추가적으로 생각해보면 좋다고 한다.
- 경성(hard) 또는 연성(soft) 처리율 제한
- 경성: 요청의 개수는 임계치를 절대 넘어설 수 없다.
- 연성: 요청 개수는 잠시 동안은 임계치를 넘을 수 있다.
- 다양한 계층의 처리율 제한
- 이 장에서는 OSI7계층 기준 7번째인 어플리케이션 계층에서 처리율을 제한한 것이다. 다양한 계층에서 처리율을 제한할 수 있다고 한다.
- 처리율 제한을 회피하는 방법. 최대한 클라이언트쪽에서 해결하는방법에 대한 고민
- 클라이언트 측 캐시를 사용하여 API호출을 줄인다.
- 예외나 에러를 처리하는 코드를 도입하여 클라이언트가 예외적 상황으로부터 우아하게 복구될 수 있도록 한다.
- 재시도(retry)로직을 구현할 때 충분한 백오프(back-off) 시간을 둔다.
🤔 정리
1단계에서는 처리율 제한 장치가 왜 필요한지, 어떻게 설계해야할지 질문을 통해 찾아갔다.
2단계에서는 처리율 제한장치를 어디에 둘지를 정하고(거의 서버쪽) 미들웨어를 둘지 서버에 둘지도 선택하였다. 이를 선택하는 요인들은 있었다. 알고리즘에 따라 기술스택에 따라
처리율 제한 알고리즘은 토큰 버킷, 누출 버킷, 고정 윈도 카운터, 이동 윈도 로그, 이동 윈도 카운터가 있었다.
카운터는 보통 동작이 빠르고 만료 정책을 지원하는 캐시에 저장하고 이를 도와주는 도구로는 레디스가 있었다.
3단계에서는 처리 제한 규칙과 제한된 요청들은 어떻게 처리할 지에 대한 이야기를 했다.
처리 제한 규칙은 설정 파일에, 캐시에 저장하여 처리율 제한 미들웨어가 요청이 들어올때마다 캐시에 저장된 설정 파일을 근거해 처리하였다.
분산 처리환경에서는 동시성 문제와 일관성 문제를 해결하기 위해 정렬 집합이고 중앙 집중형 데이터 저장소라 불리는 레디스 자료구조를 추천하였다.
성능 최적화와 모니터링할 때는 응답지연시간과 알고리즘 처리율에 대해 지켜봐야하는것도 알아봤다.
이번장은 면접에서 몇 번 나온적이 있다.
중요한 내용이므로 복기가 필수적으로 필요할 것 같다.