[Redis] Redis의 자료 형식과 기능(Sorted Set) - 2.3

Sorted Set

1. 특징

• unique string 데이터(member)를 score 정보로 정렬된 형태의 집합으로 저장할 때 씁니다.
• 같은 score 정보를 가진 member가 여러개 있다면, 문자열순(lexicograpically)으로 정렬합니다.
• Ranking: 높은 score 순으로 실시간 정렬을 가진 자료가 필요할 때 쓸 수 있습니다.
• Sliding-Window를 가진 Rate Limiter를 구현할 수 있습니다.

2. Commands

• ZADD 새로운 member를 score 값과 함께 추가한다. 이미 존재하는 member라면 score를 업데이트 한다.
• ZRANGE 주어진 Range에 해당하는 member들을 리턴한다.
• ZRANK 주어진 member의 rank를 리턴한다. Ranking은 0부터 시작하는 오름차순이다.
  (0 = lowest)
  
  • ZREVRANK 0이 가장 높은 Ranking (0=highest)
• ZCARD 주어진 key에 해당하는 memeber의 수(cardinality)를 구한다.
• ZREMRANGEBYSCORE 주어진 key에서 주어진 min, max 이내의 (inclusive) score를 가지는 member를 삭제하고, 삭제된 memeber의 수를 리턴한다.
  
  • 시간 복잡도 O(log(N)+M)
    
    • N: sorted set에 저장된 member의 수
    • M: 지워질 대상의 member의 수
  • 위 시간복잡도 때문에 대량의 데이터가 저장되어있는 자료구조일수록 성능문제가 발생할 수 있다. 따라서 적절한 수를 유지하도록 EXPIRE 또는 ZREMRANGEBYSCORE 로 관리할 필요가 있다.
    
    • 10만개를 넘지 않는 것이 defacto guide.

 

3. 실습

• Sorted set에 원소 및 score 추가
  ZADD myzset 1(score) one

• 원소, score 조회
  ZRANGE myzset 0 -1 WITHSCORES

• Rank 조회
  ZRANK myzset value

• RANK 내림차순 조회
  ZREVRANK myset value

• 주어진 key에 해당하는 member 수(cardinality) 조회
  ZCARD myzset

• 주어진 key의 특정 범위 내에 score를 가지는 member 삭제 후 삭제된 member수 리턴
  ZREMRANGEBYSCORE myzset 1(min) 2(max)

4. Sorted Set을 활용한 sliding-window rate limiter 구현

• Rate Limiter란?
  • 단위 시간당 요청/처리량을 제한을 두기 위한 소프트웨어적 기법
  • 악성 사용, 비정상적인 동작에 의한 시스템/로직의 문제 등을 사전 방지할 때 고려하는 가장 기초적인 방법
  • 대표 사례: 결제시스템, 로그인의 단위 시간당 시도 횟수 제한
• Sliding-Window란?
  • window: 판단을 위해 정해놓은 시간의 구간(1초, 1분, 1시간 등)
  • sliding_window: 판단의 대상이 되는 시간의 구간이 이동한다는 의미로, 고정적인 단위로 검증하는 것이 아니라, 현재 시간에 따라서 판단의 시간 구간이 정해지는 것을 sliding-window라고 합니다.
  • 대표적으로 TCP/IP 프로토콜에서 FLow Control할 때 sliding window에 기반한 판단을 합니다.
• pseudo code
  • 새로운 record가 들어올 때 마다 다음 로직을 수행

# 단위 시간당 요청/처리량 제한하기 pseudo code
# 서비스 이름, record가 들어온 시간, 설정한 window 시간 길이(단위는 ms), 요청 개수 제한
input: service, timestamp(of record), window(time, milliseconds), limit

# 0부터 timestamp - window 범위의 score를 가진 record 삭제
# 즉, record가 들어올때 시간기준에서 설정한 window시간 전까지의 record 삭제
# 함으로써 일정시간(window) 지난 요청들을 지움 => 오래된 요청 제거
redis.call('ZREMRANGEBYSCORE', service, 0, timestamp - window)
	
	if redis.call('ZCARD', service) < limit  
    then # record가 특정 개수 이하일 때
    
    	# service(sorted Set)에 timestamp로 된 score추가, value는 timestamp또는 record의 id로 저장
		redis.call('ZADD', service, timestamp, timestamp(or id of record))
		return 'pass'
        
	else # record가 특정 개수 이상일 때
		return 'exceeded limit' # 요청량 초과
	end