Redis ZIP List of  ZSETS (SORTED SETS)

왜 WHY

레디스에 대한 질문 중에는 메모리 사이즈에 관한 것들이 종종 있다.   RDB 파일 사이즈는 얼마인데, 이것을 메모리로 올렸더니 몇 배 더 차지하더라.   왜 이렇게 많이 늘어나나요?

실제로도 RDB 파일 사이즈에 비해 메모리를 많이 차지한다.   사용된 데이터 타입이나 RDB 파일 압축률에 따라 차이가 있지만 10배 이상 차이나는 경우도 종종 있다.   거꾸로 생각해 보면, 레디스 서버가 차지하고 있던 메모리가 10GB였는데, RDB 파일을 만들고 보니 1GB로 줄어든 것이다.   그것은 레디스가 최대의 성능을 내기 위해 메모리에서 가지고 있던 포인터와 관리용 데이터를 파일에는 저장할 필요가 없는 것들이 있기 때문이다.   당연히 파일에는 메모리 주소를 가지고 있을 필요가 없다.   레디스 서버가 시작하면서 RDB 파일을 읽어서 메모리에 저장할 때 생기는 것이지 않는가?

그리고 이유가 한 가지 더 있다.   리눅스 커널의 메모리 할당 방식에 따라 실제 필요한 메모리 보다 더 할당하는 경우가 많이 때문이다.   특히 적은 양의 메모리를 요청할 경우에는 더 그러하다.   이에 대한 좀 자세한 얘기는 '스킵 리스트' 의 '두 번째 의문 : 메모리를 왜 이렇게 많이 쓰나요?' 부분에 있으니 참고하길 바랍니다.

어찌 되었건, 메모리를 덜 사용하면서 데이터를 관리할 필요는 분명 있는 것이다.   그렇다고 레디스의 최대 장점인 성능을 해쳐서는 안될 것이다.   하지만 어디 그런 방법이 있는가?  있다면 이미 사용했겠지.   그래서 살바토르는 성능을 많이 해치지 않으면서 메모리를 최대한 절약할 수 있는 데이터 타입을 고민했다.   레디스에서 주로 사용되는 데이터 타입 중에 실 데이터 외에 메모리를   가장 많이 차지하고 있는 것은 무엇인가?

그렇다.  포인터이다.   포인터만 제거해도 메모리 사용량을 많이 줄일 수 있을 것이다.   그럼 포인터를 갖지 않으려면 어떻게 해야 할까?   새 데이터가 생기면 메모리를 할당하고 거기를 가리키는 포인터를 저장하는 것이 일반적이지 않는가?   포인터를 가지지 않는다는 것은 데이터가 생길 때마다 별도의 메모리를 할당하지 않는다는 것이다.   기존에 할당받은 메모리를 필요한 만큼 늘려서(resize) 저장하는 것이다.   이 방식을 사용하면 위에서 잠깐 언급했던 커널의 메모리 할당 방식에 따른 오버헤드도 줄일 수 있다.   이런 데이터 저장 방식(data structure)을 짚 리스트(ZIP LIST)라고 했다.

이제 짚 리스트의 데이터 구조를 살펴보고, 이런 저장 방식이 성능에 어떤 영향을 미치는지 알아보자.

개요 Overview

짚 리스트는 다음과 같은 바이트열로 이루어져 있다.  
혹시 여기 설명을 보시다 칙칙하다 싶으면, 좀 더 컬러풀한 설명이 여기있으니 클릭해서 보시고 돌아오세요.
짚 리스트의 전체 구성은 아래와 같다.   빨간색 3개 항목이 헤더이다.   zl은 zip list의 약자이다.
<zlbytes><zltail><zllen><entry 1><entry 2>...<entry n><zlend>

짚 리스트의 헤더는 아래와 같이 구성되어 있다.
• zlbytes: 자신을 포함한 짚 리스트의 총 바이트 수이다. 4 bytes unsigned integer이다.
• zltail: 마지막 엔트리의 시작 바이트 수이다. 4 bytes unsigned integer이다.   포인터 대신 오프셋(offset)을 가지고 있는 것이다.
• zllen: 엔트리 개수이다.   2 bytes unsigned integer이다.
  엔트리 개수는 2^16-2(65534)까지 저장할 수 있다.   그렇다고 엔트리를 65,534 개까지만 저장할 수 있는 것은 아니다.   초과해서 저장할 수 있지만 그렇게 되면 총 엔트리 수를 가져올 때 zllen에서 바로 가져갈 수 없고, 바이트열 전체를 탐색해서 구해야 한다.   이렇게 많이 저장하는 것을 권하지도 않고, redis.conf에 짚 리스트를 사용할 수 있는 기본 값(default)도 최대 512이다.

헤더 바이트수를 모두 합하면, zlbytes:4 + zltail:4 + zllen:2 = 10 bytes 이다.
데이터 없이 빈 짚 리스트라면 헤더 10 바이트와 zlend 1 바이트를 더해서 11바이트이다.   그러므로 각 항목의 값은 zlbytes=11, zltail=10, zllen=0 이다.   zltail 이 10인 이유는 0부터 시작하므로 10이 엔트리가 시작하는 offset이기 때문이다.
마지막 항목은 zlend이다.   zlend는 짚 리스트의 마지막을 나타내는 항목으로 1 바이트이며 값은 255이다.
엔트리를 제외한 짚 리스트의 오버헤드는 11바이트이므로 다른 데이터 구조에 비해서 매우 적다.   포인터 하나만 저장해도 8바이트인데, 이 정도면 적지 않는가?

엔트리 데이터 구조 Entry data structure

이제부터 엔트리 항목을 분석해 보자.   엔트리는 세 항목으로 구성되어 있다.
<prev entry len><itself entry value len><data>
빨간색 앞 두 항목은 헤더이고, 세 번째 항목이 실 데이터이다.   헤더의 첫 번째 항목은 이전 엔트리의 길이를 가지고, 역 탐색에 이용된다.   두 번째 항목은 저장할 데이터의 길이이다.   길이를 저장하는데 데이터가 문자열인지 숫자인지에 따라서 다르다.
문자열인지 숫자인지는 레디스가 판단한다.   실제로 입력받은 데이터는 모두 문자열이지만, 이 문자열을 숫자로 변환할 수 있으면 숫자로 저장하고 그렇지 않으면 문자열로 저장한다.
데이터가 문자열일 때부터 살펴보자.

문자열 저장 방식

이제부터 조금 복잡하니 잘 살펴보자.

• <prev entry len>: 이전 항목의 길이가 254바이트 보다 적으면 한 바이트를 사용하고, 254바이트 이상이면 5바이트에 저장한다.   5바이트 중 앞 1바이트는 길이가 254보다 길다는 표시이고, 뒤 4바이트에 길이를 저장한다.
• <itself entry value len>: 데이터의 길이를 저장하는데, 3가지 형태를 사용한다.
  데이터의 길이가 63바이트 이하일 때는 1바이트를 사용하고, 저장 형태는 |00pppppp| 이와 같다.
  데이터의 길이가 64 이상 16,383 이하일 때는 2바이트를 사용하고, 저장 형태는 |01pppppp|qqqqqqqq| 이와 같다.
  데이터의 길이가 16,384 이상일 때는 5바이트를 사용하고, 저장 형태는 |10______|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| 이와 같다.

<prev entry len>과 <itself entry value len>의 바이트 수를 합치면 최소 1+1=2바이트, 최대 5+5=10바이트이다.
첫 엔트리의 데이터가 'A'이면, 이전 엔트리가 없으므로, prev entry len은 0이고 1바이트 차지하고, itself entry value len은 1이고 1바이트, 그리고 'A'를 저장한다.   그러므로 첫 엔트리에 총 3바이트가 필요하다.

이제 데이터 길이별로 prev entry len과 itself entry value len을 계산해보자.
경우의 수를 줄이기 위해서 이전 엔트리의 길이와 현 엔트리의 데이터 길이를 같다고 하자.


data length	prev entry len	itself entry value len
1 ~ 63	1	1
64 ~ 253	1	2
254 ~ 16383	5	2
16384 이상	5	5


이것을 따져본 이유는 redis.conf의 ADVANCED CONFIG 에 부분에 있는 파라미터의 기본 값과 관련이 있기 때문이다.
list-max-ziplist-value     64
hash-max-ziplist-value     64
zset-max-ziplist-value     64

이 파라미터의 의미는 리스트, 해시, Sorted Set 에서 짚 리스트 데이터 구조를 사용하는 기준이다.   즉 값(value) 데이터의 길이가 64바이트까지는 짚 리스트를 사용하고 65바이트부터 해당 데이터 타입의 메인 데이터 구조로 변환이 일어난다.   예를 들면 리스트는 링크드 리스트로, Sorted Set은 스킵 리스트로 변경된다.
기본 값 64는 itself entry value len이 2바이트로 prev entry len 1바이트와 합치면 3바이트이다.
63이면 itself entry value len 1바이트로 prev entry len 1바이트와 합치면 2바이트이다.   2바이트면 될 것을 왜 64로 해서 3바이트를 차지하게 하는가?
64부터 253까지 3바이트를 차지하므로, 어차피 3바이트를 쓸 것이면 253으로 하지.

이제 이 파라미터들의 값을 63으로 수정하자.
좀 더 긴 데이터도 짚 리스트로 저장할 목적이면 253으로 하자.   하지만 일반적인 기준으로 볼때 권장하지는 않는다.
그 이상 데이터를 짚 리스트에 저장할 이유는 없다고 본다.   왜냐하면 짚 리스트가 메모리 절약에는 최선이지만, 삽입, 삭제 시 realloc()와 memmove()를 수행해서 큰 데이터에 적용하기에는 성능이 많이 떨어지기 때문이다.

숫자 저장 방식

숫자는 최대 길이가 8바이트이므로 길이를 저장하는데 1바이트이면 충분하다.   그래서 pre entry len과 itself entry value len이 각각 1바이트이다.
1바이트의 구조를 살펴보자.

• |1111xxxx| : 0 ~ 12까지는 데이터를 저장하는 별도 메모리를 사용하지 않고, itself entry value len 뒤 4비트에 숫자를 저장한다.
• |11111110| : 1 바이트로 표현 가능한 숫자, 데이터 1바이트 차지.
• |11000000| : 2 바이트로 표현 가능한 숫자, 데이터 2바이트 차지.
• |11110000| : 3 바이트로 표현 가능한 숫자, 데이터 3바이트 차지.
• |11010000| : 4 바이트로 표현 가능한 숫자, 데이터 4바이트 차지.
• |11100000| : 8 바이트로 표현 가능한 숫자, 데이터 8바이트 차지.

앞 한 바이트의 표현 방식은 그다지 중요하지 않다.   여기 중요한 것은 숫자의 크기에 따라 차지하는 바이트 수가 다르다는 것이다.
몇 가지 예를 들어보자.
• 숫자 0 일 때: prev entry len 1바이트, itself entry value len 1바이트, 숫자는 별도 바이트를 차지하지 않고 itself entry value len 바이트에 들어가 있다.   총 2바이트.
• 숫자 15일 때 : prev entry len 1바이트, itself entry value len 1바이트, 숫자 데이터 1바이트.   총 3바이트.
• 숫자 300일 때 : prev entry len 1바이트, itself entry value len 1바이트, 숫자 데이터 2바이트.   총 4바이트.
이렇게 차지한다.

짚 리스트 데이터 삽입

우선 입력할 값이 기존 엔트리에 있는지 확인하고, 있으면 삭제하고 삽입하고, 없으면 바로 삽입한다.
삽입 시 기존 할당된 메모리에 추가로 필요한 만큼 크기를 늘리고(realloc), memmove()로 데이터를 옮긴다.   그러므로 데이터가 많이 질수록 성능은 떨어진다.

Sorted Set에서의 짚 리스트

Sorted Set은 스코어와 값(value)로 구성되어 있다.   그럼 이 두 데이터를 짚 리스트에 어떻게 저장할까?   일반 데이터와 같은 방식으로 먼저 값부터 저장하고, 다음에 스코어를 저장한다.
Sorted Set은 정렬된 형태를 유지해야 하기 때문에 데이터 저장시 값과 스코어를 비교해서 저장될 위치를 찾아서 넣는다.   같은 값이 이미 있으면 삭제하고 넣는다.
ZADD key score value를 수행했다면 짚 리스트에 아래와 같이 저장될 것이다.
<zlbytes><zltail><zllen><entry value><entry score><zlend>

메모리를 얼마나 절약할 수 있나?

아래와 같은 데이터 500건을 짚 리스트와 스킵 리스트로 저장하고 메모리, AOF, RDB 사이즈를 비교했다.
score : 1 ~ 500
value : 'val-1' ~ 'val-500', 평균 7 바이트


항목	Zip list	Skip list	비고
Memory	8,288	62,784	7.6
AOF	11,007	11,007	1
RDB	3,465	5,811	1.7


우선 짚 리스트 내에서 메모리와 AOF 비교해 보면, AOF 보다 메모리를 더 적게 사용한다.   짚 리스트가 메모리 절약에는 효과적인 것 같다.
이제 스킵 리스트와 비교해 보면 더욱 뚜렸해진다.
메모리: 스킵 리스트는 사용 메모리가 62,784 바이트로 짚 리스트 보다 7.6배 더 사용했다.   거꾸로 보면 짚 리스트가 스킵 리스트에 비해 13%만 메모리를 사용했다.
AOF: 명령을 저장하기 때문에 두 사이즈가 같다.
RDB: 저장 형태에 따라 다르게 저장되기 때문에 스킾 리스트가 좀 더 많이 사용한다.

이번에는 스코어는 같고 값(value)가 다른 데이터로 테스트해보자.
'A'가 50번 반복되는 값이다.   파이션 형태로 표시해 보았다.
value : 'A' * 50 + str(score), 평균 53 바이트


항목	Zip list	Skip list	비고
Memory	31,840	87,936	2.8
AOF	34,507	34,507	1
RDB	3,641	8,320	2.3


메로리 차이가 2.8배로 이전 테스트보다는 차이가 적게 난다.   즉, 값(value)의 길이에 따라 다르므로, 값이 길이를 고려해서 적용하면 될 것이다.   잠깐, 아래 성능 테스트도 보고 정하자.
RDB 크기가 앞 테스트와 비교해서 별 차이가 없는 것은 이번 테스트에서는 반복되는 'A'가 압축되어 RDB 파일에 저장되었기 때문이다.   사실 앞 테스트는 값의 길이가 작어서 압축될 여지가 없었다.

스코어 형태에 따른 짚 리스트 성능 비교

짚 리스트는 바이트 열이고 Sorted Set에서는 정렬된 상태로 저장되어야 하기 때문에 스코어가 지속적으로 증가하는 경우, 감소하는 경우, 랜덤일때 이렇게 세 가지 경우로 나누어서 테스트했다. 왜냐하면 스코어/값에 따라 비교하는 횟수가 달라지기 때문이다.

지속적으로 증가하는 스코어





지속적으로 감소하는 스코어





랜덤 스코어







항목	평균(us)	최대(us)	비고
증가	27	50
감소	17	30
랜덤	18	50



• 지속적으로 증가할 때 성능이 가장 좋지 않다.   512 엔트리까지 평균 27us(microsecond)이고 최대치가 약 50us이다.   이유는 데이터를 삽입하기 위해 탐색하는데 매번 처음부터 맨 뒤까지 탐색해야 하기 때문이다.   그것도 값(value) 한번, 스코어 한번 이렇게 두번씩이나.   그러므로 timestamp 같이 지속적으로 증가하는 스코어를 가진 데이터를 짚 리스트에 저장하는 것은 성능면에서 좋지 않다.
• 지속적으로 감소할 때 성능이 가장 좋다.   512 엔트리까지 평균 17us이고 최대치가 약 30us이다.   이유는 증가할 때와 반대로 데이터를 삽입하기 위해 탐색하는데 처음 한 번만 비교하면 되기 때문이다.   이때도 삽입 시간이 증가하는 이유는 비교 시간을 짧지만 전체 데이터가 많아질수록 memmove() 하는데 걸리는 시간 길기 때문이다.
• 랜덤은 위 그래프에서 보는 바와 같이 비교 시간은 값에 따라 달라지므로 불규칙하지만, 데이터가 많아질수록 memmove() 시간이 길어져 전체적으로는 증가한다.   평균은 감소할 때와 비슷하게 18us이고 최대치는 증가할 때와 같이 50us이다.

스킵 리스트와 성능 비교

위 그래프 세 개를 다시 보면, 그래프에는 511로 찍혀있지만, 정확히 513까지 짚 리스트에 저장된 후, 스킵 리스트로 데이터 타입 변경(conversion)된다.   514 엔트리부터 스킵 리스트에 삽입 시간이다.   스킵 리스트 삽입 시간은 증가, 감소, 랜덤 관계없이 평균 5us 이다.

짚 리스트는 스킵 리스트에 비해 성능이 1/3 ~ 1/10 정도로 떨어진다.   이는 짚 리스트의 맴버수가 많아질수록 더 나빠진다.

정리

이제 명확해졌다.

• 성능이 중요하다면 스킵 리스트를 사용하자.
• 성능보다 메모리 부족으로 어려움을 겪고 있다면 짚 리스트를 사용하자.

설정은 redis.conf에서 할 수 있다.
zset-max-ziplist-entries     128
위 그래프들은 성능 차이를 보이기 위해서 이 값을 512로 설정하고 테스트했다.
기본 값은 128이다. 선택하기 어렵다면 기본 값 그대로 사용하자.   그것도 좋은 선택이다.

잠깐!

여기서 한 가지만 짚고 갑시다.   다른 데이터 타입도 엔트리 개수가 적은 경우에는 짚 리스트를 사용합니다.   디폴트 값이 512입니다.

list-max-ziplist-entries 512
hash-max-ziplist-entries 512

그런데 왜 Sorted Set에서는 128 일까요?   간단히 계산해 볼 수 있습니다.   리스트는 짚 리스트에 저장할 값(value)이 하나인 반면, Sorted Set은 스코어도 짚 리스트에 저장하기 때문에 저장 오퍼레이션이 두 번 발생합니다.   그래서 512의 반 인 256으로 줄었고, 리스트에서는 엔트리에 대한 오퍼레이션이 주로 PUSH, POP이기 때문에 탐색이 필요 없습니다.   그런데 Sorted Set은 값이 들어오면 정렬된 상태를 유지해야 하기 때문에 탐색해서 해당 위치에 저장합니다.   그래서 탐색 시간이 필요하므로 엔트리 개수를 다시 반으로 줄여서, 128로 했습니다.
그래야 다른 데이터 타입에서 사용할 때와 비슷한 성능이 나옵니다.

위의 성능 그래프는 성능 차이를 보이기 위해 512로 설정하고 테스트한 것입니다.   그래프에서 가로축 128 이하를 보면 링크드 리스트보다 성능이 떨어지기는 합니다만, 큰 차이는 보이지 않습니다.

같이 보기

다음 페이지에 있는 스킵 리스트(SKIP LIST)는 레디스 데이터 타입에서 유일하게 소팅(정렬) 기능이 있는 중요한 데이터 구조이며, 최신 소팅 알고리즘입니다.   Sorted Set이 어떻게 소팅되는지 내부 구조에 관심있는 분이라면 꼭 보시길 권해드립니다.