포스트

Redis Sorted Set

게시 업데이트
By Jeek Lee 15 분읽는 시간

I. Data structure

1. Zset

redis-zset-structure (그림 I-1-1) Redis Zset 예시

Redis에서 sorted set은 Zset이라 표현한다. Zset은 ZipList와 SkipList라는 두 가지 데이터 구조로 구성되어 있으며, Redis는 데이터에 따라 저장할 데이터 구조를 선택한다. Redis가 데이터 구조를 결정하는 조건은 다음과 같다.

  1. value의 멤버 수가 128개 이하인 경우 ZipList, 아닐 경우 SkipList 사용
  2. value의 멤버 중 값(value)이 64byte 미만인 경우만 존재할 경우 ZipList, 아닐 경우 SkipList

위 조건은 redis.conf의 ADVANCED CONFIG 부분에서 수정할 수 있다.

1
2

zset-max-ziplist-entries 128
zset-max-ziplist-value 64

1) ZipList

Redis는 인메모리 방식의 데이터 저장소이다. 메모리(RAM)는 디스크와 비교했을 때 매우 비싼 자원이며, 메모리 사용 시 그에 따른 최적화가 필수적이다. 데이터 타입 혹은 자료 구조에 따라 실질적인 데이터 외에 메모리 오버헤드가 발생하게 되는데, 경우에 따라 실 데이터의 몇 배에 달하는 자원이 필요하다. 사실 다른 DBMS에서 역시 메모리 오버헤드 문제는 동일하지만, 메모리(RAM)에서 발생하진 않기 때문에 상대적으로 중요도가 떨어지는 것에 가깝다.

ZipList는 이러한 메모리 오버헤드를 최소화하기 위해 도입되었으며, 구조는 다음과 같다.

redis-ziplist

(그림 I-1-2) Zip List 구조

  • Header
    • zlbytes: ZipList의 총 Byte 수, unsigned int 4 bytes, 0 ~ 4,294,967,295(4GB)
    • zllen: ZipList의 총 Entry 수, unsigned int 2 bytes, 0 ~ 65,535 (64KB)
    • zltail: 마지막 Entry의 시작 지점(offset), unsigned int 4 bytes, 0 ~ 4,294,967,295(4GB)
  • ZIP_END
    • zlend: ZipList의 끝을 나타내는 바이트(11111111), 1 byte

따라서 ZipList의 오버헤드는 총 11byte(Header + ZIP_END)이다.

ZipList 내부의 Entry는 다음과 같은 구조로 구성된다.

redis-ziplist-entry

(그림 I-1-3) Zip List Entry 구조

  • prevlen: 이전 Entry의 길이, 역방향 탐색에 사용(1 byte or 5 byte)
  • itselflen: 현재 Entry Value의 길이, 순방향 탐색 및 Value 조회에 사용(Value가 문자인 경우 1,2,5 byte, 숫자인 경우 1 byte)
  • value: 문자와 정수로 구분해 저장. 문자는 문자 그대로 저장하며 정수는 4, 8, 16, 24, 32, 64bit로 구분해 저장.
1. prevlen 구성

이전 Entry의 길이가 ZIP_BIGLEN(254)보다 작으면 1 byte를 할당해 다음과 같이 길이를 표현한다.

redis-ziplist-entry-prevlen-1

(그림 I-1-4) Zip List Entry prevlen(1byte)

이전 Entry의 길이가 ZIP_BIGLEN 이상일 경우 다음과 같이 첫 바이트에 ZIP_BIGLEN을 넣고 나머지 4 byte에 길이를 표현한다. redis-ziplist-entry-prevlen-2

(그림 I-1-5) Zip List Entry prevlen(5byte)

2. itselflen 구성

맨 앞 2개 비트가 00, 01, 10이면 문자, 11은 숫자를 표현한다.

문자열의 길이가 63byte 이하일 땐 1byte를 사용하며 아래 예시처럼 길이를 저장하는 데 6bit를 사용한다.

redis-ziplist-entry-itselflen-1 (그림 I-1-6) Zip List Entry itselflen string(1byte)

문자열의 길이가 64 ~ 16,383 byte일 경우, 길이를 저장하는데 14bit를 사용한다. redis-ziplist-entry-itselflen-2 (그림 I-1-7) Zip List Entry itselflen string(2byte)

문자열의 길이가 16,384 byte 이상일 경우, 길이를 지정하는데 4byte를 사용한다. redis-ziplist-entry-itselflen-3 (그림 I-1-8) Zip List Entry itselflen string(5byte)

숫자의 경우 1byte로 고정이지만, 2개의 sign bit가 추가된다. 숫자는 값의 길이를 표현할 필요가 없기 때문에, 수의 범위를 표현하는 데 itselflen을 사용한다. 다시말해 1byte 전체가 수의 범위를 표현하는 sign byte로 사용되며, 앞의 4bit를 사용한다.

  • ZIP_INT_16B(11000000), -32,768 ~ 32,767, value int 2 byte, 약 3만
  • ZIP_INT_32B(11010000), -2,147,483,648 ~ 2,147,483,647, value int 4 byte, 약 21억
  • ZIP_INT_64B(11100000), 약 900경, value int 8 byte
  • ZIP_INT_24B(11110000), 약 800만, value int 3 byte
  • ZIP_INT_8B(11111110), 약 150만, value int 1 byte

ZipList의 PUSH, POP Operation을 도식화하면 다음과 같다.

redis-ziplist-operation (그림 I-1-9) Zip List Operation Example

2) SkipList

SkipList는 정렬된 상태를 유지하면서 데이터를 삽입, 삭제, 조회할 수 있는 데이터 구조이다. SkipList는 LinkedList의 단점을 보완하기 위해 구현되었다. 정렬된 LinkedList가 존재한다고 가정할 때, 특정 값을 지니는 노드를 찾으려면 최악의 경우 모든 노드와 일치 여부를 확인해야 한다. 아래 예시에서 파란색으로 표시된 80이라는 값을 조회하기 위해선, 순서대로 확인할 경우 총 9번의 연산을 필요로 한다.

linked-list-example (그림 I-1-10) Linked List

절대적인 비교 횟수를 줄일 수 있다면, 탐색 시간을 단축할 수 있다. 비교 횟수를 줄이기 위해 등장한 방법이 Level의 적용이다. 아래 예시에서 각 List의 노드는 홀수 번째일 경우 한개, 짝수 번째일 경우 두 개의 포인터를 지닌다. 이 때, 각 노드의 레벨에 따라 2^n번째 앞에 존재하는 노드를 가르키는 포인터가 생성된다. 이처럼 구현할 경우 노드를 하나씩 생략하면서 비교할 수 있기 때문에, 비교 횟수가 1/2 수준으로 떨어지게 된다. 실제 파란색으로 표시된 80이라는 값을 조회하기 위해서 연산 횟수는 6번으로 감소한다.

linked=list-example-with-level (그림 I-1-11) Linked List with Level

이번엔 Level을 4개 적용해보자. 값이 70인 노드에 포인터 4개(Level 4)를 적용하면, 80이라는 값을 찾는 과정은 더욱 단순해진다. 하지만 단순 조회가 아닌 삽입 및 삭제 케이스를 고려해보자. 노드가 삽입 혹은 삭제되면, 해당 노드 이후에 존재하는 모든 노드의 순서가 변경된다. 순서가 변경됨에 따라 각 노드별 레벨을 수정해야하며, 레벨을 많이 사용할 수록 삽입/삭제 시 레벨 수정에 사용되는 비용이 증가한다.

linked-list-example-with-4-levels (그림 I-1-12) Linked List with 4 Levels

각 노드의 순서(위치)에 레벨이 의존적인 현재 형태에선 삽입/삭제 시 발생하는 비용을 핸들링할 방법이 없다. 다시 말해, 각 노드의 레벨을 독립적으로 설정할 수 있는 방법이 필요하다. 이에 대해 Redis는 확률에 따른 노드별 레벨 설정 방식을 사용한다. 노드가 생성될 때, 레벨은 1로 고정된다. 25% 확률로 레벨은 증가될 수 있으며, 레벨이 증가되지 않은 경우 노드의 레벨은 해당 레벨로 픽스된다. 문장으로 표현하면 복잡하지만 간단한 예시를 통해 쉽게 이해할 수 있다.

정사면체 주사위가 존재한다고 가정하자. 정사면체 주사위를 던져 나온 값에 따라 레벨의 수치가 정해진다.

  1. 첫 번째 주사위를 던질 때 레벨은 1이다. \(1\)
  2. 두 번째 주사위를 던져 같은 레벨이 나오면 레벨 2가되고, 아닐 경우 레벨 1로 마무리한다. \(1/4\)
  3. 세 번째 주사위를 던져 같은 레벨이 나오면 레벨 3이되고, 아닐 경우 레벨 2로 마무리한다. \(1/4^2\)
  4. 위 과정을 레벨이 고정될 때까지 반복한다. \(1/4^{n-1}\)

확률에 따른 레벨 설정 방식을 통해 순서에 대한 의존성을 제거했지만, 정작 SkipList의 목적 중 하나인 빠른 순서 확인은 불가능해졌다. 때문에 Redis는 레벨에 포인터와 순서를 지니는 필드를 만들어 저장하고, 해당 필드명을 SPAN으로 지정한다. 이를 Indexed SkipList라 한다. 아래 예시처럼, 탐색 중 지나친 레벨의 SPAN 값을 모두 더하면 해당 노드가 몇 번째에 위치해있는 지 알 수 있다.

indexed-skip-list (그림 I-1-13) Indexed Skip List

앞서 예시로 든 주사위의 형태(정사면체, 정육면체 등)에 따라 Indexed SkipList의 메모리 오버헤드와 탐색 시간이 달라진다. Redis는 \(1/4\) 확률을 사용하며, server.h 파일에 다음과 같이 정의되어 있다.

1

#define ZSKIPLIST_P   0.25       /* Skiplist P = 1/4 */

3) Redis SkipList

  • LEX(Lexicographic sorting, 사전순 정렬) 명령을 사용하기 위해 동일한 Score가 반복되는 것을 허용한다. 당연히 Value는 달라야 한다.
  • 역탐색을 위해 이전 노드를 가르키는 포인터(*backward)를 사용한다.
  • 최대 레벨을 32레벨로 제한한다.
  • SkipList를 정의하는 구조체(zskiplist)에 최대 레벨, 노드 수, 헤더 및 테일 노드의 포인터를 지니고 있다.

zskiplist-structure (그림 I-1-14) zsiplist structure

노드 삽입 과정을 도식화하면 다음과 같다.

zskiplist-node1 (그림 I-1-15) zsiplist node addition 1

두 번째 노드 삽입 과정을 도식화하면 다음과 같다.

zskiplist-node1 (그림 I-1-16) zsiplist node addition 2

II. Commands

1. ZADD: 생성 및 수정

1

jeeklee@ubuntu:/dir$ ZADD key score member

1
2
3

jeeklee@ubuntu:/dir$ ZADD fruit 2 apple
jeeklee@ubuntu:/dir$ ZADD fruit 10 strawberry
jeeklee@ubuntu:/dir$ ZADD fruit 8 melon 4 orange 15 pineapple 5 banana

2. ZSCORE: Value 조회

1

jeeklee@ubuntu:/dir$ ZSCORE key member

1
2

jeeklee@ubuntu:/dir$ ZSCORE fruit banana
"5"

3. ZRANK: 순위 조회

1

jeeklee@ubuntu:/dir$ ZRANK key member

1
2

jeeklee@ubuntu:/dir$ ZRANK fruit melon
(integer) 2

4. ZRANGE: 순위에 따른 범위 조회

1

jeeklee@ubuntu:/dir$ ZRANGE key start stop

첫 번째 원소가 0이며, 음수를 통해 끝에서 부터 세는 것 역시 가능하다.

1

jeeklee@ubuntu:/dir$ ZRANGE key start stop

1
2
3
4
5
6
7

jeeklee@ubuntu:/dir$ ZRANGE fruit 0 -1  
1) "orange"  
2) "banana"  
3) "melon"  
4) "strawberry"  
5) "pineapple"  
6) "apple"

1
2

jeeklee@ubuntu:/dir$ ZRANGE fruit 0 0  
1) "orange"  

1
2

jeeklee@ubuntu:/dir$ ZRANGE fruit -1 -1  
1) "apple"

Value를 함께 표시할 경우, WITHSCORE 옵션을 사용한다.

1
2
3
4
5
6
7
8
9
10
11
12
13

jeeklee@ubuntu:/dir$ ZRANGE fruit 0 -1 WITHSCORES  
 1) "orange"
 2) "4"
 3) "banana"
 4) "5"
 5) "melon"
 6) "8"
 7) "strawberry"
 8) "10"
 9) "pineapple"
10) "15"  
11) "apple"  
12) "20"

ZREVRANGE를 통해 역순으로 출력할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13

jeeklee@ubuntu:/dir$ ZREVRANGE fruit 0 -1 WITHSCORES  
 1) "apple"
 2) "20"
 3) "pineapple"
 4) "15"
 5) "strawberry"
 6) "10"
 7) "melon"
 8) "8"
 9) "banana"
10) "5"  
11) "orange"  
12) "4"

5. ZRANGEBYSCORE: 값에 따른 범위 조회

1

jeeklee@ubuntu:/dir$ ZRANGEBYSCORE key min max  

1
2
3
4
5
6
7

jeeklee@ubuntu:/dir$ ZRANGEBYSCORE fruit 6 15 WITHSCORES  
1) "melon"  
2) "8"  
3) "strawberry"  
4) "10"  
5) "pineapple"  
6) "15"

6. ZREM: 특정 멤버 삭제

1

jeeklee@ubuntu:/dir$ ZREM key member  

1

jeeklee@ubuntu:/dir$ ZREM fruit pineapple

III. References

  1. Redis Docs
  2. Redis Zip List
  3. Redis Commands
DataSource
redis sorted_set
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.