대규모 시스템 설계 기초 - 4. 처리율 제한 장치의 설계

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

API 요청 횟수가 제한 장치에 정의된 임계치를 넘어서면 추가로 도달한 모든 호출은 처리가 중단된다.

몇 가지 예시

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

 

예시 요구사항

• 설정된 처리율을 초과하는 요청은 정확하게 제한한다.
• 낮은 응답시간 : 이 처리율 제한 장치는 HTTP 응답시간에 나쁜 영향을 주어서는 곤란하다.
• 가능한 한 적은 메모리를 사용해야 한다.
• 분산형 처리율 제한 - 하나의 처리율 제한 장치를 여러 서버나 프로세스에서 공유할 수 있어야 한다.
• 예외 처리 : 요청이 제한되었을 때는 그 사실을 사용자에게 분명히 보여주어야 한다.
• 높은 결합 감내성 : 제한 장치에 장애가 생기더라도 전체 시스템에 영향을 주어서는 안 된다.

 

생각해 볼 포인트 1)

처리율 제한 장치는 어디에 두어야 하나? 서버에 두어야 하나 아니면 GateWay에 두어야 하나?

 

생각해 볼 포인트 2)

처리율 제한 알고리즘은 여러 가지이고, 각각 장단점이 존재한다.

1. 토큰 버킷 알고리즘

동작 원리 : 토큰 버킷은 지정된 용량을 갖는 컨테이너이다. 이 버킷에는 사전 설정된 양의 토큰이 주기적으로 채워진다. 토큰이 꽉 찬 버킷에는 더 이상의 토큰은 추가되지 않는다. 토큰 공급기는 이 버킷에 매초 N개의 토큰을 추가한다. 버킷이 가득 차면 추가로 공급된 토큰은 버려진다.

 

2개의 파라미터가 존재

• 버킷 크기 : 버킷에 담을 수 있는 토큰의 최대 개수
• 토큰 공급률 : 초당 몇 개의 토큰이 버킷에 공급되는가

 

장점

• 구현이 쉽다. 메모리 사용 측면에서도 효율적이다.
• 짧은 시간에 집중되는 트래픽도 처리 가능하다. 버킷에 남아 있는 토큰이 있기만 하면 요청은 시스템에 전달될 것이다.

단점

• 2개의 파라미터를 튜닝하는 것이 까다로울 수 있다.

TMI

• AWS의 API GateWay가 사용하고 있다.
• https://docs.aws.amazon.com/apigateway/latest/developerguide/api-gateway-request-throttling.html

2. 누출 버킷 알고리즘

토큰 버킷 알고리즘과 비슷하지만 요청 처리율이 고정되어 있다는 점이 다르다. 동작 원리는 다음과 같다.

• 요청이 도착하면 큐가 가득 차 있는지 본다. 빈 자리가 있는 경우에는 큐에 요청을 추가한다.
• 큐가 가득 차 있는 경우에는 새 요청은 버린다.
• 지정된 시간마다 큐에서 요청을 꺼내어 처리한다.

일종의 FIFO Queue라고 생각하면 된다.

 

2개의 파라미터

• 버킷 크기
• 처리율 (시간당 몇 개의 항목을 차지하는가)

장점

• 큐의 크기가 제한되어 있어 메모리 사용량 측면에서 효율적이다.
• 고정된 처리율을 갖고 있기 때문에 안정적 출력이 필요한 경우에 적합하다.

단점

• 단시간에 많은 트래픽이 몰리는 경우 큐에는 오래된 요청들이 쌓이게 되고, 그 요청들을 제때 처리 못하면 최신 요청들은 버려지게 된다.
• 파라미터 튜닝이 까다로울 수 있다.

3. 고정 윈도 카운터 알고리즘

동작 원리

• Timeline을 고정된 간격의 윈도로 나누고, 각 윈도마다 카운터를 붙인다.
• 요청이 접수될 때마다 이 카운터의 값은 1씩 증가한다.
• 이 카운터의 값이 사전에 설정된 임계치에 도달하면 새로운 요청은 새 window가 열릴 때까지 버려진다.

이 알고리즘의 가장 큰 문제는 윈도의 경계 부근에 순간적으로 많은 트래픽이 집중될 경우 윈도에 할당된 양보다 더 많은 요청이 처리될 수 이다는 것이다.

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

동작 원리

• 요청의 Timestamp를 추적한다. 타임스탬프 데이터는 보통 redis의 sorted set 같은 캐시에 보관한다.
• 새 요청이 오면 만료된 timestamp는 제거한다. 만료된 timestamp는 그 값이 현재 윈도의 시작 시점보다 오래된 타임스탬프를 말한다.
• 새 요청의 타임스탬프를 로그에 추가한다.
• 로그의 크기가 허용치보다 같거나 작으면 요청을 시스템에 전달한다. 그렇지 않은 경우에는 처리를 거부한다.

장점

• 이 알고리즘이 구현하는 처리율 제한 메커니즘은 아주 정교하다. 어느 순간의 window를 보더라도, 허용되는 개수는 시스템의 처리율 한도를 넘지 않는다

단점

• 거부된 요청의 timestamp도 보관해야 하기 때문에 이 알고리즘은 다량의 메모리를 사용한다.

5. 이동 윈도 카운터 알고리즘 (sliding window counter)

고정 윈도 카운터 알고리즘과 이동 윈도 로깅 알고리즘을 결합한 것

 

이동 윈도 카운터 알고리즘에서 '현재 요청 개수'를 계산하는 방법 - 예시

이전 1분동안 5개의 요청이, 이후 1분동안 3개의 요청이 왔다고 해보자. 현재 1분의 30% 시점에 새 요청(즉 9번째 요청)이 도착한다면, 현재까지 몇 개가 들어온 것으로 간주해야 하는가?

• 현재 1분간의 요청 + 직전 1분가의 요청 * 이동 윈도와 직전 1분이 겹치는 비율
• 3 + 5 * 0.7 = 6.5 → 내림 → 6개

 

장점

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

단점

• 직전 시간대에 도착한 요청이 균등하게 분포되어 있다고 가정한 상태에서 추정치를 계산하기 때문에 다소 느슨하다. 다만 생각만큼 심각한 것은 아니다. (Cloudflare가 실시한 실험에 따르면 0.003% 정도만 실제 상태와 맞지 않게 허용되거나 버려졌다고..)

 

생각해 볼 포인트 3)

카운터를 어디에 저장할 것인가?

Redis는 처리율 제한 장치를 구현할 때 자주 사용되는 메모리 기반 저장장치로서, INCR과 EXPIRE의 두 가지 명령어를 지원한다.

• INCR : 메모리에 저장된 카운터의 값을 1만큼 증가시킨다.
• EXPIRE : 카운터에 타임아웃 값을 설정한다. 설정된 시간이 지나면 카운터는 자동으로 삭제된다.

 

생각해 볼 포인트 4)

처리율 한도 초과 트래픽을 Client에 알려주는 방법 - Header를 이용한다

• X-Ratelimit-Remaining : 윈도 내에 남은 처리 가능 요청의 수
• X-Ratelimit-Limit : 매 윈도마다 클라이언트가 전송할 수 있는 요청의 수
• X-Ratelimit-Retry-After : 한도 제한에 걸리지 않으려면 몇 초 뒤에 요청을 다시 보내야 하는지 알림

429 too many requests 를 res status로 사용하면 된다.

 

생각해 볼 포인트 5)

분산 환경의 1) 경쟁조건 2) 동기화 이슈

경쟁 조건 문제를 해결하는 가장 널리 알려진 해결책은 lock이다. 하지만 lock은 시스템의 성능을 상당히 떨어뜨린다는 문제가 있다. 본 예시에서 락 대신 쓸 수 있는 해결책은 두 가지 있다.

1. 루아 스크립트
2. 정렬 집합

 

처리율 제한 장치 서버를 여러 대 두게 되면 동기화가 필요해진다. (각기 다른 처리율 제한장치로 req가 갈 수 있기 때문) 이에 대한 한 가지 해결책은 고정 세션을 활용해 같은 클라이언트로부터 요청은 항상 같은 처리율 제한 장치로 보낼 수 있도록 하는 것이다.

더 나은 해결책은 redis와 같은 중앙 집중형 데이터 저장소를 사용하는 것이다.

 

추가적으로, 요청과 가까운 데이터 센터를 활용하면 응답 지연을 줄일 수 있다. 대부분의 클라우드 서비스 사업자는 세계 곳곳에 edge server를 심어놓고 있다. 또한 이때 데이터를 동기화 해야 한다면, 최종 일관성 모델을 사용하면 된다.

 

추가적으로 생각해 볼 포인트

• 경성 처리율 제한 - 요청의 개수는 임계치를 절대로 넘어설 수 없다.
• 연성 처리율 제한 - 요청 개수는 잠시 동안은 임계치를 넘어설 수 있다.

다양한 계층에서의 처리율 제한 - Iptables를 사용하면 IP 주소에 처리율 제한을 적용하는 것이 가능하다

• 처리율 제한을 회피하는 방법. 클라이언트를 어떻게 설계하는 것이 최선인가?
  • 캐시 사용, 적절한 throttle 처리, 클라이언트의 gracefully 복구, back-off 시간 등