처리율 제한 장치의 설계 (대시설기)

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

사례

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

장점

• Dos(Denial of Service) 공격에 의한 자원 고갈 방지
• 요청에 대한 비용 절감
• 서버 과부화 방지

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

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

처리율 제한 알고리즘

토큰 버킷 (버킷 크기, 토큰 공급률)

• 장점
  • 구현이 쉽다.
  • 메모리 사용 측면에서 효율적이다.
  • 짧은 시간에 집중되는 트래픽도 처리 가능
• 단점
  • 버킷 크기와 토큰 공급률이라는 두 개 인자를 갖고 있는데 적절하게 튜닝하기 까다롭다.

누출 버킷 (버킷 크기, 처리율)

• 토큰 버킷 알고리즘과 비슷하지만 요청 처리율이 고정되어 있다, FIFO
• 장점
  • 큐의 크기가 제한되어 있어 메모리 사용량 측면에서 효율적이다.
  • 고정된 처리율을 갖고 있기 때문에 안정적 출력이 필요한 경우 적합하다.
• 단점
  • 단시간에 많은 트래픽이 몰리는 경우 최신 요청들은 버려지게 된다.
  • 두 개 인자를 적절하게 튜닝하기 어렵다.

고정 윈도 카운터

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

• 장점
  • 메모리 효율이 좋다.
  • 이해하기 쉽다.
  • 윈도가 닫히는 시점에 카운터를 초기화하는 방식은 특정한 트래픽 패턴을 처리하기 적합하다.
• 단점
  • 윈도 경계 부근에 순간적으로 많은 트래픽이 집중될 경우 윈도에 할당된 양보다 더 많은 요청이 처리될 수 있다.

이동 윈도 로그

고정 윈도 카운터 알고리즘 단점을 해결함.

1. 요청의 타임스탬프를 추적한다. 타임스탬프 데이터는 보통 레디스의 정렬 집합 캐시에 보관한다.
2. 새 요청이 오면 만료된 타임스탬프는 제거한다. 만료된 타임 스탬프는 그 값이 현재 윈도의 시작 시점보다 오래된 타임스탬프를 말한다.
3. 새 요청의 타임스탬프를 로그에 추가한다.
4. 로그의 크기가 허용치보다 같거나 작으면 요청을 시스템에 전달한다.

• 장점
  • 처리율 제한 메커니즘이 정교하다. 어느 순간의 윈도를 보더라도, 허용되는 요청의 개수는 시스템의 처리율 한도를 넘지 않는다.
• 단점
  • 다량의 메모리를 사용하는데, 거부된 요청의 타임스탬프로 보관하기 때문

이동 윈도 카운터

고정 윈도 카운터알고리즘과 이동 윈도 로깅 알고리즘을 결합한 것. 두 가지 방법이 있지만 하나만 설명하겠다.

• 장점
  • 이전 시간대의 평균 처리율에 따라 현재 윈도의 상태를 계산하므로 짧은 시간에 몰리는 트래픽에도 잘 대응한다.
  • 메모리 효율이 좋다.
• 단점
  • 직전 시간대에 도착한 요청이 균등하기 분포되어 있다고 가정한 상태에서 추정치를 계산하기 때문에 다소 느슨하다.

3단계. 상세 설계

처리율 제한 규칙

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

• 처리율 제한 장치가 사용하는 HTTP 헤더
  • X-Ratelimit-Remaining: 윈도 내에 남은 처리 가능 요청의 수
  • X-Ratelimit-Limit: 매 윈도마다 클라이언트가 전송할 수 있는 요청의 수
  • X-Ratelimit-Retry-After: 한도 제한에 걸리지 않으려면 몇 초 뒤에 요청을 다시 보내야 하는지 알림
• 사용자가 너무 많은 요청을 보내면 429 too many requests 오류를 X-Ratelimit-Retry-After 헤더와 함께 반환하도록 한다.

상세 설계

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

문제 2가지

1. 경쟁 조건
2. 동기화

경쟁 조건

가장 유명한 해결책은 lock 이지만 시스템의 성능을 상당히 떨어뜨린다.

다른 해결책 2가지

1. 루아 스크립트
2. 정렬 집합 (레디스 자료구조)

동기화 이슈

해결책

1. 고정 세션
2. 레디스와 같은 중앙 집중형 데이터 저장소 사용

성능 최적화

모니터링

확인하려는 것

• 채택된 처리율 제한 알고리즘이 효과적이다.
• 정의한 처리율 제한 규칙이 효과적이다.

4단계. 마무리

• 경성(hard) 또는 연성(Soft) 처리율 제한
• 다양한 계층에서 처리율 제한 (OSI 7계층)
• 처리율 제한을 회피하는 방법. 클라이언트를 어떻게 설계하는 것이 최선인가?