[Rate Limiter] 트래픽 제어를 위한 처리율 제한 기능 (이론편)

 Untitled 서비스에서는 request마다 요금을 내야 하는 외부 api를 사용하고 있어서, 이 경우 유저의 무분별한 api 호출 때문에 예상 비용을 초과할 수 있으므로 어느 정도의 제한이 필수적이다.

 또한 동일한 짧은 시간 동안 서버에 부하를 가하는 DDos 공격등을 막기 위해서라도 api 호출에 제한을 걸어야만 한다.

 이를 위한 방법으로 api 호출에 대한 요청 빈도를 제어하는 Rate Limiter에 대해 알아보자

 

 

 

 

 

 

Rate Limiter

 

 

 Rate Limitting은 '서버가 특정 임계치까지만 클라이언트의 요청을 허용하는 정책' 으로, Rate Limiter는 유저의 요청이 Rate Limit 값을 초과하면 API 호출을 제한시키는 역할을 한다.

 이렇게 API 호출을 우리가 원하는 수준으로 제어함으로써 서버의 부하를 조절할 수 있고, 이를 통해 DDos 공격 및 brute force attack 예방, 서버 안정성을 확보할 수 있다.

 

 

 

 

 

 

 

Algorithm

 

 

Rate Limiter는 Request를 필터링하는 방법에 따라서 'Token Bucket', 'Leaky Bucket', 'Fixed Window Counter', 'Sliding Window Log', 'Sliding Window Counter'로 분류할 수 있다. 내 서비스에 알맞은 방법을 찾기 위해 각 알고리즘의 장단점에 대해 알아보자.

 

 

Token Bucket

• 요청마다 토큰을 소비하여 bucket안의 토큰이 모두 소진되면 요청을 제한하는 방식 
• 동작
  1. 특정 시간마다 bucket에 설정한 rate Limit만큼의 토큰을 생성해서 담음
  2. api 요청이 들어올 때마다 bucket에서 token을 하나씩 사용
  3. token을 모두 사용해서 bucket이 비었다면, 다시 bucket에 토큰이 찰 때까지 새로운 요청은 버려진다 (overflow)
• 장점
  • 구현이 간단하고 메모리를 효율적으로 사용한다
  • 짧은 시간에 집중되는 트래픽을 커버할 수 있다
• 단점
  • 분산 환경에서 작동 시에 동시성 문제가 발생할 수 있음(race condition)
  • 버킷의 크기와 토큰 공급률을 정하기 까다롭다 (IP 주소마다 제한할 것인지, 초당 요청을 제한할 것인지에 따라 달라짐)

 

 

Leaky Bucket

• FIFO 형식의 Bucket(Queue)에 request를 차례대로 담아서 관리하는 방식 
• 동작
  1. bucket이 비어있다면 request들이 FIFO 형태로 저장된다
  2. bucket이 가득 차있다면 새로운 요청은 버려진다 (overflow)
  3. 특정 시간이 지나면 bucket에 가장 먼저 들어온 요청을 처리하고, 새로운 요청을 받아들인다
• 장점
  • Queue 크기가 제한적이라서 메모리를 효율적으로 사용
  • requeest 처리율이 고정되어 있어서 안정적인 출력이 가능
• 단점
  • 단시간에 트래픽이 몰리는 경우 '입력 속도 > 출력 속도'가 되므로 계속해서 요청이 누적되고, 이로 인해 오버플로가 발생하여 데이터 패킷 손실이 발생할 수 있다
  • 버킷의 크기와 처리율을 관리하기 힘들다

 

 

 

Fixed Window Counter

• 고정된 크기의 Window(시간)동안, 특정 개수만큼의 요청만을 허용하는 방식
• 동작
  1. 타임라인을 고정된 크기의 window로 나눈다
  2. 요청이 들어오면 해당 시간의 window에서 요청 수를 카운트한다
  3. 요청 수가 임계값에 도달하면, 다음 window까지 새로운 요청은 버려진다
• 장점
  • 구현이 간단하고 메모리를 효율적으로 사용할 수 있다
• 단점
  • window 경계 시간대에 요청이 몰리면, 두 배의 부하를 받게 된다
    ex) 0.9초에 2개의 요청, 1.1초에 2개의 요청 -> 0.2초에 4개의 요청이 들어온다
  • 분산 환경에서 race condition이 발생할 수 있다

 

 

 

 

Sliding Window Log

• 모든 요청을 TimeStamp로 기록하고, 현재 시점을 기준으로 시간 범위를 정하여 rate limit에 따라 요청을 제한시키는 방법
• 동작
  1. 타임 라인에서 현재 시간을 기준으로 고정된 크기의 window를 생성한다
     (size = 1m, 현재 시간 = 1m인 경우: window는 30s ~ 1:30s) 
  2. 요청이 들어오면 window에 TimeStamp를 저장한다
  3. window 내부의 TimeStamp 개수가 rate limit을 넘었다면 요청을 거부하고, 그렇지 않다면 허용한다.
     단, TimeStamp 개수는 거부되었던 요청도 포함해서 카운트한다
  4. 현재 시간에 따라서 window를 움직이고, window를 벗어난 TimeStamp를 제거한다
• 장점
  • Fixed Window Counter 알고리즘에서, 경계 시간대에 트래픽이 몰리는 현상을 방지할 수 있다
    따라서 어떤 시간대에서든, rate limit을 지킬 수 있다
• 단점
  • Denied 된 요청의 TimeStamp도 보관해야 하므로 메모리 비용이 많이 든다
  • Denied 된 요청을 같이 계산하므로 데이터 패킷 손실률이 높다

 

 

 

 

Sliding Window Counter

 

• Fixed Window와 Sliding Log를 합친 방법으로, 직전 시간대와 현재 시간대가 window와 겹치는 비율을 계산하여서 count 한다
• 동작
  1. 현재 시간대에 요청이 들어오면 counter를 계산한다
     current counter = (이전 시간대 window와 sliding window가 겹치는 비율) * (이전 시간대 window의 counter)
                                     + (현재 시간대 window와 window가 겹치는 비율) * (현재 시간대 window의 counter)
  2. current counter와 rate limit을 비교하여 요청을 수락하거나 거부한다
  3. 이때 요청이 수락된다면 현재 시간대 window의 counter를 증가시킨다
• 장점
  • 경계 시간대에 트래픽이 몰리는 경우 대응하기 좋다
  • 거부된 요청의 time stamp를 기록하지 않아서 메모리를 좀 더 효율적으로 사용할 수 있다
• 단점
  • 직전 시간대 요청이 균등하게 들어왔다고 가정하기에, 비교적 느슨하게 계산한다

 

 

 

 

 

 

다음 시간에는 Spring에서 사용할 수 있는, rate limiter를 구현해 놓은 라이브러리를 알아보고 실제로 적용시켜 보겠다

 

 

그럼 안녕~~

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Reference

• Rate Limiter, 제대로 이해하기: https://gngsn.tistory.com/224

Rate Limiter, 제대로 이해하기

• 자바 스프링에서 처리율 제한 기능을 구현하는 4가지 방법: https://hogwart-scholars.tistory.com/entry/Spring-Boot-%EC%9E%90%EB%B0%94-%EC%8A%A4%ED%94%84%EB%A7%81%EC%97%90%EC%84%9C-%EC%B2%98%EB%A6%AC%EC%9C%A8-%EC%A0%9C%ED%95%9C-%EA%B8%B0%EB%8A%A5%EC%9D%84-%EA%B5%AC%ED%98%84%ED%95%98%EB%8A%94-4%EA%B0%80%EC%A7%80-%EB%B0%A9%EB%B2%95#Bucket4j-1

[Spring Boot] 자바 스프링에서 처리율 제한 기능을 구현하는 4가지 방법

• Rate Limit이란?: https://etloveguitar.tistory.com/126

[Rate Limit - step 1] Rate Limit이란? (소개, Throttling, 구현시 주의사항 등)