Sliding window rate limiter 구현
레디스의 sorted set 자료구조를 이용해서
sliding window rate limiter를 구현할 수 있다.
우선 Rate Llimiter란,
단위 시간당 요청 및 처리량에 제한을 두기 위한 소프트웨어적 기법이다.
악성 사용이나 비정상적인 동작에 의한 시스템 및 로직의 문제 등을 사전에 방지하고자 할 때 가장 기초적인 방법이다.
대표적인 사례들로는 결제시스템이나 로그인의 단위 시간당 시도 횟수 제한 등이 있다.
Sliding Window는
window 즉 창문과 같은 직사각형이 슬라이딩하듯 움직이는 거라고 생각하면 된다.
정확히는 현재 처리하고자 하는 양을 window로 제한하ㅏ고 이를 시간의 구간을 연속적으로 이동하는 것이다.
대표적인 사례로 TCP/IP 프로토콜에서 Flow Control 할 때 Sliding window에 기반한 판단을 한다.
아래의 Pseudo Code대로 구현하면 된다.
input: service, timestamp(of record), window(time, milliseconds), limit
redis.call('ZREMRANGEBYSCORE', service, 0, timestamp - window)
if redis.call('ZCARD', service) < limit
then
redis.call('ZADD', service, timestamp, timestamp(or id of record))
return 'pass'
else
return 'exceeded limit'
end
HyperLogLog
HyperLogLog는
하나의 set에서 cardinality를 추정하기 위한 데이터 구조이다.
HyperLogLog를 이용하면 작은 데이터 공간으로 많은 수의 데이터 cardinality를 추정치로 계산할 수 있다.
레디스는 이러한 HyperLogLog를 지원하는 커맨드들이 있다.
Command
- PFADD 주어진 Key의 HyperLogLog 자료구조에 데이터를 추가한다.
- PFCOUNT 주어진 Key들의 HyperLogLog count의 합을 리턴한다.
- 이 합은 각각의 cardinality의 합이 아니라 주어진 key에 넣은 모든 데이터에 대한 cardinality 값의 합이다.
- PFMERGE 여러개의 HyperLogLog를 하나로 합친다. 합집합.
- 이 합은 각각의 cardinality의 합이 아니라 주어진 key에 넣은 모든 데이터에 대한 cardinality 값의 합이다.
* 참고로 같은 키에 대해 처리할 수 있는 요청량에는 한계가 있기 때문에,
너무 큰 경우 키를 분산하다 count가 필요할 때 PFCOUNT나 PFMERGE로 최종 값을 구하는 것이 좋다.
Key Eviction
키가 너무 많아 설정한 Maxmermory를 넘을 수도 있다.(maxmermory 설정은 redis.conf 파일에서)
Conf 파일에 eviction policy를 설정할 수도 있다.
maxmemory-policy 키로 설정할 수 있다.
- noeviction: memory limit에 다다르면, 새로운 값을 저장할 수 없다. (client의 command는 error를 리턴받는다.) replication을 적용하는 경우, 이 설정은 primary database에만 적용 가능하다.
- allkeys-lru: 최근에 사용된 key를 유지한다. 사용한지 오래된 key(LRU, least recently used)를 제거한다.
- allkeys-lfu: 자주 사용하는 key를 유지한다. 자주 사용되지 않은 key(LFU, least frequently used)를 제거한다.
- volatile-lru: 정책은 LRU이지만, expire 가 설정된(true) key에 대해서만 지운다.
- volatile-lfu: 정책은 LFU이지만, expire 가 설정된(true) key에 대해서만 지운다.
- allkeys-random: Random하게 지운다.
- volatile-random: Random이지만, expire 가 설정된(true) key에 대해서만 지운다.
- volatile-ttl: expire가 설정된(true) key 중에서 TTL(time-to-live)이 짧은 순으로 지운다.
*** 웬만하면 Key에 항상 expire를 설정하고 volatile-ttl을 선택하는 것이 베스트이다.
