https://engineering.classdojo.com/ Rate Limiter는 아래 요구 사항을 만족해야함
- 분산환경: 프로세스를 넘어서 공유될 수 있어야 함
- Rolling Window ex) 1분당 10개의 메세지를 보낼 수 잇음
- Minimum Distance Between Messages: 전체 Rate와 관계없이 메세지 사이의 최소 기간이 존재해야함
First Approach " Token Bucket"
- rate limit with rolling window에 대한 표준적인 방법은 Token Bucket임
- 유저는 토큰을 담고 있는 버킷을 가짐
- 어떤 행동을 하기 위해서 버킷안에 토큰 수를 세고 토큰 수가 충분하다면 토큰을 차감함
- 시간이 지나면 모든 버킷을 최대 capa까지 채워줌(일정한 rate로)
- 이러한 방법은 적은 공간을 사용하는 현명한 알고리즘
- 유저별로 single integer만 필요하기 때문에
- 하지만 naive한 구현에서는 어떤 프로세스가 지속적으로 버킷을 채워야하고 수백만 유저인 경우 각 refill operation이 레디스 인스턴스에 큰 부하를 줄 수 있음
- 이런 문제를 해결하기 위해 아래와 같은 방식이 사용될 수 있음
- 요청 시점에 지급하는 방식
- 각 유저는 2개의 키를 가짐
- 토큰 버킷, {user_id}_bucket: 3
- 가장 최근 token refilled timestamp {user_id}_latest_refilled_at: '2023-03-13'
- 유저가 특정 행동을 하려면 저장된 timestamp를 확인함
- 지난 요청과 비교했을 때 몇개의 토큰을 받아야하는지 계산하고 지급
- 이러한 알고리즘도 두개의 프로세스가 rate limiter를 필요로 할때 문제가 있음
- redis는 operation들을 하나의 atomic action으로 batch 처리 가능한데
- 유저에게 얼마나 많은 토큰을 줘야하는지 계산하려면 최소 2번의 요청이 필요함
- 마지막 timestamp와 토큰 수 가져오기
- 새로운 토큰수를 반영하기
- 제약 사항
- Lua scripting 없이는 한번의 atomic한 액션으로 만들 수 없음
- 따라서 만약 2개의 클라이언트가 동일한 rate limiter를 사용한다고 하면
- 아래와 같은 동시성 이슈가 생길 수 있음
- 유저가 1개의 토큰을 갖고 있음
- 마지막 행동이 후 추가 토큰을 받기위한 시간이 충분하지 않은 상태에서 아래 과정이 동시에 일어남
- client1이 저장된 timestamp 와 토큰 개수를 가져옴
- client2이 저장된 timestamp 와 토큰 개수를 가져옴
- 동시에 토큰 추가하지 않아도 되는 것을 확인 및 행동을 허용하고 token 수를 0으로 만듦
- 2번의 행동이 가능함
Better Approach - Sorted Sets
운이 좋게도 이런 race condition 문제를 해결 할 수 있는 자료구조가 있음 => sorted set
- hash table과 skip list의 구현이 합쳐져 있음
- 각 유저는 sorted set을 가짐 키와 값이 동일함(action이 시도된 시간 microseconds로 존재)
- user_1: sorted_set(1,23,453,565)
- user_2: sorted_set(1, 23,4 53, 565,)
- 알고리즘
- 유저가 특정 행동을 시도하면 모든 one interval(허용된 시간 범위) 이전 모든 항목을 제거함
ZREMRANGEBYSCORE: 지정한 score 범위에 해당하는 멤버를 삭제하는 명령어- 예를 들어 현재가 241024 9:45이고 interval이 10분이면 241024 9:35 이전 항목은 제거
ZRANGE(0,-1)로 set의 모든 element를 조회 할 수 있음- 지금 시간을 넣음 ZADD
- 키 전체에 공간을 아끼기 위해 TTL을 rate-limiting interval에 맞게 설정
- 현재 시간(가장 최근 요청) + interval
- 모든 operation이 종료후 fetched element를 세고 만약 limit를 넘으면 허용하지 않음
- 가장 큰 fetched element와 현재 시간을 비교해서 너무 가까우면 시도를 허락하지 않음
- 유저가 특정 행동을 시도하면 모든 one interval(허용된 시간 범위) 이전 모든 항목을 제거함
- 이 방식으로 구현했을 때 장점은 MULTI command를 이용해 모든 레디스 동작들이 atomic하게 동작할 수 있음
- 위의 코드에서도 가능하다고 생각할 수도 있지만, multi/exec 중간 상태를 읽고 조건 분기하는 로직은 지원하지 않음
- 제약 사항
- 모든 연산이 다 끝난 이후에 요청을 허용할 지 말지 판단하기 때문에, 차단된 요청도 행동 자체로 기록됨
더 나은 형태
https://engineering.classdojo.com/2021/08/25/even-better-rate-limiting
- 위 구현 식의 문제
- zrange, zadd 시간 복잡도 O(log(N))
- zremrangebyscore O(log(N) + M)
- M은 sorted_set에서 제거되는 항목의 수
- 요청이 많아지면 많아질 수록 느려짐