Better Rate Limiting With Redis Sorted Sets

요구사항

• 분산환경 : 다수 프로세스에 걸쳐 rate limiter가 공유되어야 함 → 외부 key-value store가 필요

• Rolling Window : 1분에 10개의 메시지 받기로 했다면 0:59초에 10개, 1:01 초에 10개 받을 수 있게 하면 안됨

• Minimum Distance Between Messages : 연속되는 메시지 사이에 최소 간격이 있어야 함

첫번째 시도 - token buckets

• 각 유저가 유저에 해당하는 버킷을 갖고 있고, 그 버킷에 토큰이 포함되어 있음 ⇒ 유저별로 버킷이 필요함

• 마찬가지로 해당 버킷에 토큰을 리필해주는 백그라운드 프로세스가 필요. 만약 유저가 몇백만명이라면 redis에 refill write operation이 계속적으로 일어날 것이고 Redis instance에 견딜수 없는 부담을 주게 됨

조금 더 나은방식(토큰 리필 프로세스 x)

• 각 유저가 두개의 키를 갖고 있음. token bucket과 bucket이 refill(요청한) 된 마지막 timestamp 값

• 유저가 액션을 수행하려고 시도할 때, 저장된 timestamp 값을 가지고옴

• 마지막으로 요청한 timestamp 로부터 해당 유저가 몇개의 토큰을 받았어야 했는지를 계산

• 이 토큰 계산 값으로 진행해도 되는지의 여부를 판단

• 몇개의 토큰을 유저에게 주어야 하는지를 계산해야 할 때, redis로 최소 2개의 연산을 수행해야 하는데(last time stamp 조회, new token count 설정), 이를 하나의 아토믹 연산으로 수행하기가 힘들었음(Lua script 를 쓰지 않고서는)

실패 시나리오 (race condition)

• 유저가 액션을 취하기에 충분한 토큰을 갖고 있음

• 액션을 취한 후 충분치 않은 시간이 지나고 토큰이 추가로 부여되지 않음

• Client1 이 stored timestamp와 token count 조회

• Client2 가 stored timestamp와 token count 조회

• Client1이 token add 필요 없다고 계산하고, action 허용 후 redis의 token count 를 0으로 조정

• Client2도 마찬가지로 token add 필요 없다고 계산하고, action 허용후 token count 0으로 조정

Sorted set 사용하기

• 각 유저가 sorted set을 갖고 있음

• 유저가 action 을 수행하려고 할 때, sorted set에서 이전 interval에서 남겨진 element들 제거(TTL로 가능하지 않을까?)

• 새 요청의 타임스탬프를 set에 추가

• set의 요소들을 fetch 하고 그 크기를 계산해서, 이 크기가 limit을 넘게 되면 요청을 block 함

• fetch 한 요소들 중 가장 큰 값과 현재 timestamp를 비교해서 너무 가까우면 block 할 수 있음