[Kotlin&Spring] 5기 Redis sorted sets 자료구조와 명령어 이해하기

sorted sets - ZRANK

Redis sorted sets

unique 한 Strings를 연관된 score에 의해 정렬한 자료구조
string이 하나 이상의 같은 score 를 가질 경우 String은 사전 순에 따라 정렬된다

 

sorted sets를 사용하는 예시

순위표

ex) 대용량 온라인 게임의 최고 점수들의 정렬된 리스트를 쉽게 유지할 수 있다

요금 제한기

ex) 특히 과도한 API 요청을 방지하기 위해 sliding window 속도 제한기를 구축할 때 사용할 수 있다

 

set과 Hash를 섞은 자료구조라고 생각할 수 있다
set와 같이 sorted sets은 unique한 반복되지 않는 문자열 요소들로 구성된다
따라서 어떤 부분에서 sorted set은 set과 동일하다

그러나 set의 요소들이 정렬되지 않는 반면에
sorted set 의 모든 요소들은 부동소수점 값(score)에 따라 정렬된다
위의 이유 때문에 이 자료구조와 hash가 유사하다/왜냐하면 모든 요소가 값으로 매핑되어있다

 

더욱이 sorted set의 요소들은 명령에 따른다
따라서 그들은 요청에 따라 정렬되어있지 않다
명령은 sorted sets를 나타내는데 사용되는 데이터 구조의 특수성이다

 

그 값들은 다음의 규칙에 따라 정렬된다

- 만약 A 와 B가 다른 score 의 두 요소일 때, 두 score이 A>B 이면 두 값은 A > B이다
- 만약 A와 B가 정확히 같은 score일 때, A의 문자열이 사전적으로 더 큰 값이면 두 값은 A> B 이다
sorted sets 는 항상 unique한 요소값만 가지기 때문에 A와 B의 값은 같을 수 없다

> ZADD racer_scores 10 "Norem"
(integer) 1
> ZADD racer_scores 12 "Castilla"
(integer) 1
> ZADD racer_scores 8 "Sam-Bodden" 10 "Royce" 6 "Ford" 14 "Prickett"
(integer) 4

 

ZADD 와 SADD 명령어가 비슷해보일 수 있다
그러나 하나 추가적인 인수(인자)를 갖는다(요소의 앞에 위치하는 바로 score값이다)
ZADD는 또한 많은 가변 변수(인자)를 갖는다
따라서 위와 같이 자유롭게 복수의 score 값 쌍을 구체화할 수 있다

 

sorted sets는 실제로 이미 정렬되어 있기 떄문에 score 에 따라 정렬된 경쟁 값 목록을 반환하는 것이 간단하다
sorted sets 는 skip 리스트와 hash table 을 모두 포함하는 이중 포트의 자료 구조가 이식되어있다
따라서 매 순간 우리가 Redis에 요소를 넣을 떄마다 Redis는 모두에 어떤 작업도 할 필요 없이 이 요소는 이미 정렬되어있다

 

ZRANGE 순서는 낮은 순서부터 높은 순이다
그러나 ZREVRANGE 순서는 높은 순서부터 낮은 순이다

> ZRANGE racer_scores 0 -1
1) "Ford"
2) "Sam-Bodden"
3) "Norem"
4) "Royce"
5) "Castilla"
6) "Prickett"
> ZREVRANGE racer_scores 0 -1
1) "Prickett"
2) "Castilla"
3) "Royce"
4) "Norem"
5) "Sam-Bodden"
6) "Ford"

 

0과 -1 은 인덱스 0부터 마지막 요소임을 의미한다
-1은 LRANGE 명령어의 경우를 위해서만 작동한다

WITHSCORES 인자와 함께 score 또한 반환하게 할 수 있다

 

범위를 운영하기

sorted sets는 범위에 따라 운영할 수 있다
10 또는 더 적은 점수의 경쟁자들을 조회해보자

  > ZRANGEBYSCORE racer_scores -inf 10
1) "Ford"
2) "Sam-Bodden"
3) "Norem"
4) "Royce"

 

Redis 에게 음의 무한과 10 사이(두 극단 모두 포함) 값을 가진 요소들을 반환하도록 명령했다

요소를 삭제하기 위해 우리는 간단히 ZERM을 호출했다
또한 이는 요소들의 범위를 삭제할 수 있다
정확히 10보다 적은 경쟁자 와 경쟁자 Castilla 를 제거해보자

\> ZREM racer\_scores "Castilla"  
(integer) 1  
\> ZREMRANGEBYSCORE racer\_scores -inf 9  
(integer) 2  
\> ZRANGE racer\_scores 0 -1  
1) "Norem"  
2) "Royce"  
3) "Prickett"  

 

ZREMRANGEBYSCORE 는 아마 최고의 명령어의 이름은 아닐 것이다
그러나 그것은 굉장히 유용할 수 있다
또한 삭제된 요소들의 수를 반환한다

 

sorted sets를 위해 정의된 또 다른 극단적으로 유용한 운영은 순위를 조회하는 운영이다
정렬된 요소들 안에서 요소의 위치가 무엇인지 요구하는 것이 가능하다
ZREVRANK 명령어는 또한 내림차수으로 정렬된 요소들을 고려한 순위를 가져올 수 있다

  \> ZRANK racer\_scores "Norem"  
(integer) 0  
\> ZREVRANK racer\_scores "Norem"  
(integer) 3  

 

사전 순서의 score들

 

Redis 2.8버전에서 새로운 기능이 소개되었다
이 기능은 사전순으로 범위를 조회하는 것을 가능하게 했다
sorted set의 요소들을 측정하는 것은 동일한 score 로 삽입되었다
요소들은 C memcmp 기능으로 비교되며 그에 따라 대조(기록된 정보를 표준 순서로 조합하는 것)가 이루어지지 않는다
그리고 모든 Redis 인스턴스는 같은 결과를 응답할 것이다

 

사전순의 범위들을 운영하는 중심 명령어들은 ZRANGEBYLEX, ZREVERANGEBYLEX, ZREMRANGEBYLEX, ZLEXCOUNT가 있다

에를 들어, 경쟁자들을 다시 리스트에 추가하자
하지만 이번에는 모든 요소들에 socre 값에 0 값을 사용할 것이다
우리는 규칙들을 명령하는데 sorted sets 때문에 그들이 이미 사전되어잇는 것을 확인할 수 있다

 

ZRANGEBYLEX 를 사용함으로써 요청할 수 있는 사전 순의 범위 목록:

  \> ZADD racer\_scores 0 "Norem" 0 "Sam-Bodden" 0 "Royce" 0 "Castilla" 0 "Prickett" 0 "Ford"  
(integer) 3  
\> ZRANGE racer\_scores 0 -1  
1) "Castilla"  
2) "Ford"  
3) "Norem"  
4) "Prickett"  
5) "Royce"  
6) "Sam-Bodden"  
\> ZRANGEBYLEX racer\_scores \[A \[L  
1) "Castilla"  
2) "Ford"  

 

범위들은 첫 글자에 따라 포괄적 또는 배타적일 수 있다
또한 무한대와 음의 무한대는 각각 + 와 - 문자열들로 각각 구체화된다
추가 정보는 documentaion을 보자

 

이 특징은 중요하다
왜냐하면 이 특징은 우리가 sorted sets를 보편적 인덱스로써 사용할 수 있게 하기 때문이다
예를 들면 만약 단신이 128비트의 기호없는 integer 인자 값으로 요소들을 인덱싱 하고싶다면 당신에게 필요한 것은 같은 score값을 갖지만 128 비트의 빅 엔디안 수로 구성된 16 바이트의 접두사를 가진 요소들을 sorted sets에 추가하는 것이다
* 빅 엔디안(big endian): 낮은 주소에 데이터의 높은 바이트 부터 저장하는 방식
수들이 빅 엔디안 방식이기 때문에 사전순으로 정렬(raw byte 순)되었을 경우는 수치적으로도 역시 정렬되어있으며 개발자는 128 비트 공간에 범위를 요청할 수 있으며 접두사를 버린 요소의 값들만 조회할 수 있다

score들을 update하기: 순위표

sorted set score 들은 언제나 update될 수 있다
ZADD를 sorted set에 이미 포함된 요소에 ZADD를 호출하는 것은 그 요소의 score를 O(log(N))의 복잡성으로 update할 것이다
그와 같이 sorted set은 수많은 업데이트가 있을 때 적합하다

이 특성 때문에 흔한 사용 예시는 순위표이다
고전적인 어플리케이션은 페이스북 게임으로 상위 N명의 사용자와 리더보드의 사용자 순위를 보여주기 위해 높은 점수에 따라 정렬된 사용자를 조회하는 기능과 순위 획득 작업을 결합한 것이다
(예: "당신은 여기서 #4932 최고 점수입니다")

예시

순위표를 대표하는 sorted set을 사용할 수 있는 두 가지 방법이 있다
경쟁자의 새로운 score를 알 때 우리는 그것을 직접 ZADD 명령어를 통해 업데이트할 수 있다
그러나 민약 우리가 존재하는 score에 점수를 더하고 싶다면 우리는 ZINCRBY 명령어를 사용할 수 있다

  \> ZADD racer\_scores 100 "Wood"  
(integer) 1  
\> ZADD racer\_scores 100 "Henshaw"  
(integer) 1  
\> ZADD racer\_scores 150 "Henshaw"  
(integer) 0  
\> ZINCRBY racer\_scores 50 "Wood"  
"150"  
\> ZINCRBY racer\_scores 50 "Henshaw"  
"200" 

 

score이 업데이트되면 멤버가 이미 존재할 때 , ZADD 가 O 으로 변하는 것을 확인할 수 있다

반면에 ZINCRBY는 새로운 score로 변한다
100부터 온 경쟁자 Henshaw를 위한 score는이전에 어떤 score 를 가졌는지와 상관없이 150으로 변했고, 50에서 200으로 증가했다

기본 명령어

ZADD는 새로운 멤버와 연관된 score를 sorted set로 추가한다
멤버가 이미 존재한다면, score가 업데이트된다
ZRANGE 는 주어진 범위로 정렬된 sorted set의 멤버를 리턴한다
ZRANK는 오름차순으로 정렬된 제공된 멤버의 순위를 리턴한다
ZREVRANK는 내림차순으로 정렬된 제공된 순위를 리턴한다
이 외에도 완성된 명령어 리스트가 있다

수행

대부분의 sorted set 운영은 O(log(n))이다 - n은 멤버들의 숫자이다
큰 리턴 값(예 수만 명 이상)을 가진 ZRANGE 명령어를 실행할 때 몇몇의 주의점이 있다
이 명령어의 시간 복잡도는 O(log(n) + m) - m은 결과가 리턴된 숫자이다

대안

Redis sorted set은 Redis 자료 구조보다 인덱싱 목적으로 종종 사용된다
만약 데이터를 인덱싱하고 query해야하면 JSON 자료 구조와 Redis Query Engine 기능을 고려해보자