SortedSet (ZSET)

보통 집합(Set) 자료구조는 원소들의 중복을 허용하지 않는다. 또한, 원소의 순서를 보장하지 않기 때문에, 특정한 순서로 데이터를 다루어야 하는 경우에는 적합하지 않을 수 있다.

Redis는 이러한 집합의 한계를 극복하고 집합 데이터의 정렬을 수행하는 SortedSet 데이터 구조를 제공한다.

SortedSet

Redis에서 데이터 구조 자체를 가르키는 key가 존재하는데, 이것이 SortedSet이다.

해시처럼 보이는 컬렉션이 존재하며, 이를 key-value 쌍으로 부르지 않고 member-score 라고 부른다.

• 모든 member는 score를 가지며, score는 항상 숫자이다.

zip list vs listpack

ZSET의 초기 버전에서는 작은 크기의 데이터를 저장할 때 zip list를 사용했다. 하지만 Redis 7.0 이후부터는 더 이상 zip list를 사용하지 않고 listpack이라는 새로운 데이터 구조로 대체되었다.

listpack은 zip list의 단점을 보완하기 위해 등장했다. 여기서 단점은, 데이터 변경(증가) 시 prevlen이 1 → 5로 바이트로 연속적으로 증가되어 zip list 안의 모든 엔트리를 수정해야 하는 경우라고 한다.

listpack은 이러한 단점을 개선해서 prevlen 필드를 제거하고 backlen을 사용해서 현재 엔트의 시작까지의 거리를 저장한다.

ZSET 구조

• skip list

  • score를 기준으로 정렬되어 있으며 member들이 링크되어 있다.

• hash table

  • member를 key로, score를 value로 저장한다.

  • O(1) 시간 복잡도로 특정 member의 score를 바로 찾을 수 있다.

이러한 구조적 특징으로 삽입, 삭제, 및 검색 연산이 평균 O(log N)의 시간 복잡도를 갖는다.

구성요소

• Key는 ZSET을 식별한다.

• Score는 member의 점수로 설정된다.

• member는 고유한 값이며 중복으로 저장될 수 없다.

주요 특징

1. 고유한 멤버

ZSET에 저장되는 각 member는 집합 내에서 유일하며 중복 값을 허용하지 않는다.

1. 자동 정렬

member는 score에 따라 자동으로 정렬된다. 동일한 score인 경우 member를 기준으로 사전 정렬이 이루어진다.

1. 효율적인 조회

특정 점위의 score를 가진 member를 효율적으로 검색할 수 있는 기능을 제공한다. 상위 10개의 member나 특정 score 범위 내의 member를 쉽게 조회할 수 있다.

key, member prefix 네이밍

ZSET의 key 또는 member를 prefix로 구분할 수 있다.

1. key prefix 방식

1. member prefix 방식

일반적으로 key에 prefix 방식을 더 많이 사용하는 것 같다.

ZADD 동작 과정

zip list 기준

ZADD myset 1 "one"
// zip list 내부: [one][1.0]

ZADD myset 2 "two"
// zip list 내부: [one][1.0][two][2.0]

ZADD myset 1.5 "mid"
// zip list 내부: [one][1.0][mid][1.5][two][2.0]

1. 새로운 member 추가

   • score를 비교하며 적절한 삽입 위치를 탐색한다.

   • 해당 위치 이후의 모든 데이터를 뒤로 이동

   • 새로운 <member, score> 삽입

2. 기존 member 수정

   • 선형 탐색으로 member 찾기

   • score 변경 시 삭제 후 재삽입

skip list 기준

아래 명령어를 실행한다고 가정해보자.

ZADD myset 10 "member1"

1. 가장 먼저 새로운 노드를 생성한다. (score: 10, ele: “member1”)

2. 노드의 레벨을 무작위로 결정한다. (1~32 사이)

3. score(10)을 기준으로 삽입할 위치를 찾는다.

   • 가장 높은 레벨부터 낮은 레벨로 수평으로 이동하면서 삽입하기 적절한 위치를 탐색한다.

4. 탐색한 위치에 노드를 연결

   • 모든 level에서 이전/다음 노드 포인터를 업데이트하고 span 값을 조정한다.

5. Hash Table 업데이트 한다.

   • member:score를 해시 테이블에 매핑한다. O(1) 시간 복잡도로 관리하기 때문에 특정 member의 score를 빠르게 조회하거나 업데이트 할 수 있다.