[가상 면접 사례로 배우는 대규모 시스템 설계 기초]4. 처리율 제한 장치의 설계

레https://product.kyobobook.co.kr/detail/S000001033116

가상 면접 사례로 배우는 대규모 시스템 설계 기초 | 알렉스 쉬 - 교보문고

1장 사용자 수에 따른 규모 확장성 : https://inhyeok-blog.tistory.com/40
2장 개략적인규모추정 : https://inhyeok-blog.tistory.com/41
3장 시스템 설계 면접 공략법 : https://inhyeok-blog.tistory.com/42
4장 처리율제한장치의설계 : https://inhyeok-blog.tistory.com/43
5장 안정해시설계 : https://inhyeok-blog.tistory.com/44
6장 키-값저장소설계 : https://inhyeok-blog.tistory.com/45
7장 분산시스템을위한유일 ID 생성기설계 : https://inhyeok-blog.tistory.com/46
8장 URL 단축기설계 : https://inhyeok-blog.tistory.com/47
9장 웹크롤러설계 : https://inhyeok-blog.tistory.com/48
10장알림시스템설계 : https://inhyeok-blog.tistory.com/49
11장뉴스피드시스템설계 : https://inhyeok-blog.tistory.com/50
12장채팅시스템설계 : https://inhyeok-blog.tistory.com/51
13장검색어자동완성시스템 : https://inhyeok-blog.tistory.com/52
14장유튜브설계 : https://inhyeok-blog.tistory.com/53
15장구글드라이브설계 : https://inhyeok-blog.tistory.com/54

 

처리율 제한 장치는 클라이언트 또는 서비스가 보내는 트래픽의 처리율을 제어하는 장치를 의미한다. 처리율 제한 장치를 두면 DoS 공격을 막고, 비용을 절감하며, 서버 과부하를 막을 수 있다.

 

이 장에서 작가는 지원자와 면접관의 대화를 통해 문제 이해 및 설계 범위를 확정하는 과정을 보여준다. 우리도 실제 설계를 할 때 면접관이 있다는 생각으로 문제를 명확하게 정의하고 한정할 필요가 있지만, 이 과정은 이 글에서는 제외한다.

 

요구사항

- 설정된 처리율을 초과하는 요청은 정확하게 제한한다.

- 낮은 응답시간: 처리율 제한 장치는 HTTP 응답시간에 영향을 주지 않아야 한다.

- 가능한 적은 메모리 사용

- 분산형 처리율 제한:하나의 처리율 제한 장치를 여러 서버나 프로세스에서 공유할 수 있어야 한다.

- 예외 처리: 요청이 제한되었을 때는 그 사실을 사용자에게 분명하게 보여줘야 한다.

- 높은 결함 남내성: 제한 장치에 장애가 생기더라도 전체 시스템에 영향을 주어서는 안된다.

 

처리율 제한장치는 서버와 클라이언트 사이에서 요청을 제한해야한다. 이는 서버측에 둬야한다. 클라우드 마이크로 서비스의 경우 처리율 제한 장치는 보통 API 게트트웨이에 구현한다. API 게이트웨이는 다양한 기능을 제공하는 완전 위탁관리형 서비스이다. 하지만 일단  API는 처리율 제한을 지원하는 미들웨어라는 점에만 주목하자.

 

 

처리율 제한은 5가지의 알고리즘이 유명하다.

- 토큰 버킷

토큰 버킷은 일정한 시간마다 토큰이 채워지는 버킷(양동이)에서 요청이 발생할 때마다 토큰을 소비해서 요청을 처리하는 것이다. 만약 토큰이 부족하다면 요청은 버려진다. 일반적으로 API 엔드포인트마다 별도의 버킷을 둔다.

장점 : 이 방식은 구현이 쉽고, 메모리 사용이 효율적이며, 짧은 시간에 집중되는 트레픽을 처리할 수 있다.

단점 : 버킷 크기와 토큰 공급률을 조정하기 까다롭다. 

 

- 누출 버킷

요청을 큐에 넣고 고정 속도로 서버에서 읽어와서 처리하는 방식이다. 

장점 : 큐의 크기가 제한되어있어서 메모리 사용이 효율적이며, 고정처리율때문에 안정적 출력이 필요한 경우 적합하다.

단점 : 단시간에 트래픽이 몰리는 경우 큐에 요청이 쌓이고, 최신 요청이 버려질 수 있다.(큐 오버플로) 또한 버킷 크기와 처리율을 조정하기 어렵다.

 

- 고정 윈도 카운터

타임라인을 고정된 간격의 윈도로 나누고(예컨데 1초마다 새로운 윈도가 기다리고 있다), 각 윈도마다 카운터를 붙인다. 요청이 들어올 때마다 윈도 카운터를 증가시키고, 임계치가 넘으면 다음 윈도우가 열릴때까지 요청은 대기한다. 이 알고리즘은 예상한 요청보다 많은 요청을 받을 수 있는 위험이 존재한다. 예컨데 5초마다 임계치가 10인 윈도우가 있는데, 4초에 10개가 들어오고 6초에 10개가 들어오면 3초에서 8초 사이에 20개의 요청을 받게 되는 것이다. 

장점 : 메모리 효율이 좋다. 이해가 쉽다. 특정한 트래픽 패턴을 처리하기 좋다.(매 분마다 요청이 발생하는 경우 등)

단점 : 기대보다 많은 요청을 받을 수 있다(앞서 언급한 사례 참조)

 

- 이동 원도 로그

고정 윈도 카운터 방식의 단점을 보안한 방식으로, 요청은 들어올 때마다 log에 담긴다. 이때 윈도 크기에 해당하는 시간(예컨데 5초)보다 오래된 요청 log는 삭제한다. 오래된 요청을 삭제한 이후에 남아있는 요청의 크기가 임계값보다 작으면 요청을 처리한다.

장점 : 정확하게 처리율 한도를 제한한다.

단점: 다량의 메모리를 사용한다.

 

- 이동 윈도 카운터

이동 윈도 카운터는 고정 윈도 카운터와 이동 윈도 로그 방식을 결합한 방식이다. 고정 윈도와 동일하게 요청이 윈도우마다 카운터를 증가시키는데, 현재 시간을 끝으로 하는 윈도우가 걸치고 있는 2개의 윈도우(정확히 윈도우가 끝나는 지점에 있으면 1개)를 현재 윈도우가 몇 퍼센트씩 걸치고 있냐에 따라서 처리율을 계산한다. 예컨데 윈도우 크기가 1분이고, 현재 시간은 1분 20초라면 앞의 윈도우의 67%, 뒤의 윈도우의 33%를 걸치고 있다. 따라서 (직전 윈도에서 요청의 수) * 67% + (이번 윈도에서 쌓인 요청의 수) > (윈도 카운터 크기) 라면 요청을 버린다.

장점 : 짧은 시간에 몰리는 트래픽에도 잘 대응한다. 또한 메모리 효율도 좋다.

단점: 직전 시간대에 도착한 요청이 균동하게 분포되어 있다고 가정하므로 다소 느슨하다.(하지만 치명적이지 않음)

 

처리율 한도 초과 트래픽 처리

요청을 메시지 큐에 보관할 수도 있을 것이고, 사용자에게 429응답(too many requests)를 반환할 수도 있을 것이다.

 

 

분산 환경에서 처리율 제한 장치의 구현

Redis에서 카운터의 값을 읽고, counter+1의 값이 임계치를 넘는지 본 후에 넘지 않는다면 레디스에 보관된 카운터 값을 1만큼 증가시키는 방식은 경쟁 조건과 동기화 문제를 해결해야한다. 작가는 경쟁조건을 해결하는 2개의 블로그를 보여준다.

1. https://medium.com/@saisandeepmopuri/system-design-rate-limiter-and-data-modelling-9304b0d18250 (Redis)

System Design — Rate limiter and Data modelling

2. https://stripe.com/blog/rate-limiters(Lua Script)

Scaling your API with rate limiters

동기화 문제는 중앙 집중형 데이터 저장소를 사용하는 것인데, 이는 처리율 제한장치의 토큰과 같은 상태를 유지해야하는 요소를 외부에 두는 것이다. 이는 앞선 1장에서 무상태 서버를 설명한 내용을 참조하길 바란다.