[대규모 시스템 설계] 4. 처리율 제한 장치의 설계 - 1

처리율 제한 장치란?

클라이언트 또는 서비스가 보내는 트래픽의 처리율(rate)을 제한하기 위한 장치

예시
1. 사용자는 초당 2회 이상 새 글을 올릴 수 없다
2. 같은 IP 주소로는 하루에 10개 이상의 계정을 생성할 수 없다
3. 같은 디바이스로는 주당 5회 이상 리워드를 요청할 수 없다

 

처리율 제한 장치를 설치하면 좋은점은?

- DoS(Denial of Service) 공격에 의한 자원 고갈을 방지할 수 있다

- 비용을 절감한다. 적당한 서버 수, 서드 파티 요청하는 API 감소

- 서버 과부하를 막는다

 

처리율 제한 장치 구현

1단계: 문제 이해 및 설계 범위 확정

면접에서 처리율 제한 장치 설계에 관한 질문이 들어왔을 때, 지원자가 물어볼만한 사항

1. 어떤 종류의 처리율 제한 장치를 설치해야 하나요? 클라이언트 측? 또는 서버 측?
2. 어떤 기준을 사용해서 API 제한을 해야하나요? IP? UserID? 아니면 다른 기준?
3. 다양한 형태의 제어 규칙을 정의할 수 있어야 한다면, 시스템 규모는 어느정도인가요?
4. 대규모 분산 환경에서 동작해야 하나요?
5. 이 처리율 제한 장치는 독립된 서비스인가요? 아니면 애플리케이션 코드에 포함?
6. 사용자의 요청이 제한 장치에 의해 걸리진 경우, 사용자에게 알려줘야 하나요?

책의 내용을 바탕으로 요구사항을 요약한다면 다음과 같다

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

- 낮은 응답시간: HTTP 응답시간에 나쁜 영향을 주면 안된다

- 가능한 한 적은 메모리를 사용한다

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

- 예외 처리: 요청 제한시 사용자에게 보여줘야 한다

- 높은 결함 감내성: 제한 장치에 문제가 생기더라도 전체 시스템에 영향을 주면 안된다

 

2단계: 개략적 설계안 제시 및 동의 구하기

우선 기본적인 클라-서버 통신 모델을 사용하자

 

1. 처리율 제한 장치는 어디에 둘 것인가?

- 클라이언트 측: 클라 요청은 쉽게 위변조가 가능하고 모든 클라의 구현을 통제하는 것은 어려울 수 있으므로 안정적이지 않다

- 서버 측: 클라 --> [API 서버, 처리율 제한 장치] 와 같은 형태로 이뤄진다

- 클라와 서버 사이의 미들웨어(ex. API 게이트웨이): 클라 --> 처리율 제한 장치 --> API 서버. 이때, 너무 많은 요청이 들어온다면 미들웨어에서 캐치해서 HTTP 상태코드 429를 내려준다(Too many requests)

 

즉, 서버 혹은 API 게이트웨이 중에서 선택하면 되는데 이 부분은 프로젝트에 따라 다르다.

- 현재 사용중인 프로그래밍 언어가 서버 측 구현을 지원하기 충분한가?

- 서버 측에서 구현한다면 여러 알고리즘을 고려할 수 있지만, 서드 파티가 제공하는 게이트웨이를 사용한다면 선택지는 제한된다

- 마이크로서비스 기반의 설계고, 사용자 인증이나 IP 허용목록 관리등을 처리하는것이 API 게이트웨이에 이미 구현되어있다면 처리율 제한 기능 또한 게이트웨이에 포함해야 할 수 있다

- 처리율 제한 서비스 직접 구현은 쉽지 않으니 상용 API 게이트웨이도 고려해보아라

 

처리율 제한 알고리즘

1. 토큰 버킷(token bucket)

2. 누출 버킷(leaky bucket)

3. 고정 윈도 카운터(fixed window counter)

4. 이동 윈도 로그(sliding window log)

5. 이동 윈도 카운터(sliding window counter)

 

1. 토큰 버킷

2개의 인자를 받는다.

- 버킷 크기: 버킷에 담을 수 있는 토큰의 최대 개수

- 토큰 공급률(refill rate): 초당 몇 개의 토큰이 버킷에 공급되는가

 

토큰 버킷 동작 원리

동작 원리

Request와 토큰은 1:1 매칭이다

요청이 들어왔을 때, 토큰의 수가 충분하다면 토큰을 소비하여 요청을 처리한다.

토큰이 없다면, 토큰이 채워질 때까지 요청들은 전부 버려진다

 

그렇다면 버킷은 몇 개나 사용해야 하는가? 공급 제한 규칙에 따라 달라진다

- 통상적으로, API 엔드포인트마다 별도의 버킷을 둔다. 예로 사용자가 하루에 포스팅 1개, 좋아요 5개, 친구 추가 50명까지 할 수 있다면 총 3개의 버킷이 필요하다

- IP 주소별로 처리율 제한을 적용한다면 IP 주소마다 버킷이 필요하다

- 시스템의 처리율을 초당 10000개로 제한한다면, 모든 요청이 1개의 버킷을 공유하도록 한다

 

장점: 구현이 쉽고 메모리 사용 측면에서도 효율적이다. 버킷에 남은 토큰만 있다면 짧은 시간에 집중되는 트래픽 처리도 가능

단점: 버킷 크기와 토큰 공급률을 적절하게 설정하기 어렵다

 

2. 누출 버킷 알고리즘

이 알고리즘도 2개의 인자를 가진다.

- 버킷 크기: 큐 사이즈와 같은 값이다. 큐에는 처리될 항목들이 보관된다

- 처리율(outflow rate): 지정된 시간당 몇 개의 항목을 처리할지 지정하는 값이며 보통 초 단위로 표현

토큰 버킷과 다른 점은 요청 처리율이 고정되어 있고 보통 FIFO 큐로 구현한다

누출 버킷 동작원리

동작원리

Request이 들어왔을 때, 큐가 꽉차있다면 버려진다.

더 채울 수 있다면 큐에 넣는다.

일정시간마다 고정 개수만큼 요청을 처리한다.

 

장점: 큐의 크기가 제한되어 있어 메모리 사용량 측면에서 효율적이며 고정된 처리율을 가지고 있어서 안정적 출력이 필요한 경우에 적합

단점: 단시간에 많은 트래픽이 몰리면 큐에는 오래된 요청만 쌓여서 처리를 빨리 하지 못하면 최신 요청들은 전부 버려진다. 2개의 인자를 올바르게 튜닝하기 까다롭다

 

3. 고정 윈도 카운터

Threshold: 3, 흰색: 시스템에 전달되는 요청, 회색: 버려지는 요청

 

동작원리

타임라인을 고정된 간격의 윈도로 나누고, 각 윈도마다 카운터를 붙인다

요청이 접수될 때 마다 카운터의 값을 1 증가시키며, 기존에 설정한 임계치(threshold)에 도달하면 새로운 요청을 버려진다

다만, 아래 사진과 같이 윈도의 경계 부근에 순간적으로 많은 트래픽이 집중될 경우 윈도에 할당된 양보다 더 많은 요청이 처리될 수 있다. 

Threshold: 5, 윈도 경계부근에 많은 요청이 몰린 상태

위 사진의 경우 윈도 크기가 1분 단위, 임계치가 5로 설정된 알고리즘이다. 처리는 정상적으로 수행하지만 윈도 시작을 2:00:30~2:01:30로 움직인다면 이 시스템은 1분에 임계치를 넘어선 10개를 처리한것으로 보여진다

 

장점: 메모리 효율이 좋고 이해하기 쉽다. 윈도가 닫히는 시점에 카운터를 초기화하는 방식은 특정 트래픽 패턴을 처리하기 적합

단점: 윈도 경계 부근에서 일시적으로 많은 트래픽이 몰려드는 경우, 기대했던 시스템 처리 한도보다 많은 양의 요청을 처리한다

 

4. 이동 윈도 로깅 알고리즘

고정 윈도 카운터의 문제를 해결하기 위한 알고리즘이다.

 

이동 윈도 로깅 동작원리

동작원리

- 요청의 타임스탬프를 추적하며, 타임스탬프는 보통 레디스의 정렬 집합 같은 캐시에 보관한다.

- 윈도우 기간이 지나면 만료된 로그들은 삭제된다.

- 새 요청의 타임스탬프를 로그에 추가한다

- 로그의 크기가 허용치보다 같거나 작으면 시스템에 전달하고, 아니라면 로그에 쌓아만 둔다

 

장점: 정교하며 어느 순간의 윈도를 보더라도, 허용되는 요청의 개수는 시스템의 처리율 한도를 넘지 않는다

단점: 거부된 요청의 타임스탬프도 보관하기 때문에 다량의 메모리를 사용한다

 

5. 이동 윈도 카운터

이동 윈도 로깅 + 고정 윈도 카운터 알고리즘을 결합한 것이다. 하지만 이동 윈도 로깅과 같이 요청들을 저장하지 않고 임계치를 넘어선 요청들에 대해선 버린다. 2가지 접근법 중 1개만 다룰 예정이다.

이동 윈도우 카운터 동작원리

동작원리

윈도에서 처리할 수 있는 수가 정해져 있으며 이 윈도우가 이동한다는 점에서는 같다. 다만 아래와 같이 계산해야 하는 부분이 추가된다.

위 그림과 같은 경우, 현재 윈도에 몇 개의 요청이 온 것으로 보고 처리해야 하는가?

현재 1분간의 요청 수 + 직전 1분간의 요청 수 X 이동 윈도와 직전 1분이 겹치는 비율

= 3 + 5 X (5/8)*100%

= 3+5X70%

= 6.5

여기서 소수점은 반올림하거나 내릴 수 있지만 여기선 내려서 6으로 사용해보자

분당 처리율 한도가 7이므로  현재 1분의 30% 시점에 도착한 신규 요청은 시스템으로 전달된다. 하지만 그 직후에는 한도에 도달했으므로 더 이상의 요청은 받을 수 없다.

 

장점: 이전 시간대에 도착한 평균 처리율에 따라 현재 윈도의 상태를 계산하므로 짧은 시간에 몰리는 트래픽 대응 가능하며 메모리 효율이 좋다

단점: 직전 시간대에 도착한 요청이 균등하게 분포되어 있다고 가정한 상태에서 추정치를 계산하기 때문에 다소 느슨하나 이 문제가 심각하진 않다. 

 

개략적인 아키텍처

처리율 제한 알고리즘의 기본 아이디어는 얼마나 많은 요청이 접수되었는지를 추적할 수 있는 카운터를 추적 대상별(사용자, IP 주소, API 엔드포인트 등)로 둔다. 이 카운터는 메모리상에서 동작하는 캐시가 바람직한데 그 이유로는 빠른데다 시간에 기반한 만료 정책을 지원하기 때문. Ex) Redis는 INCR, EXPIRE 2가지 명령어를 지원

처리율 제한 장치의 개략적 구조

- 클라이언트가 처리율 제한 미들웨어에게 요청을 보낸다

- 처리율 제한 미들웨어는 레디스의 지정 버킷에서 카운터를 가져와서 한도에 도달했는지 검사. 한도에 도달했다면 요청 거부, 아니라면 API 서버로 요청 전달 + 미들웨어는 카운터 값을 증가시킨 후 레디스에 저장

 

참고 자료

- https://velog.io/@shinmj1207/%EC%B2%98%EB%A6%AC%EC%9C%A8-%EC%A0%9C%ED%95%9C-%EC%9E%A5%EC%B9%98%EC%9D%98-%EC%84%A4%EA%B3%84

- 가상 면접 사례로 배우는 대규모 시스템 설계 기초