Redis SKIP List of  ZSETS (SORTED SETS)

이 글은 이런 의문에서 시작했습니다.

• Sorted Set은 데이터가 정렬되어 저장된다.   그래서 키에 저장되는 멤버수가 많아질수록 저장 속도가 느려질 것이다. 그래서 테스트를 해 보았다.   키 하나에 첫 번째 10만 건을 넣고, 두 번째 10만 건을 넣고, 이렇게 10만 단위로 100만 건을 넣으면서 시간을 재 보았는데, 그런데 거의 증가하지 않았다.   사실 증가하는 패턴을 보이지도 않았다.
  테스트 결과는 아래에 있다.
• 인터넷에 찾아보면 심심찮게 이런 질문을 볼 수 있다.   "AOF 또는 RDB 파일 크기는 얼마인데, 레디스에서 읽어 들이면 메모리는 그것보다 몇 배 더 차지해요.  어떻게 된 거죠?"
• 그리고 이런 질문이 있었습니다. "Sorted Set에 멤버수가 많으니, expire(del) 될 때 성능이 떨어진다. 피해 갈 수 있는 방법이 있는가?"   이 질문을 받으니, 이어서 의문이 생겼다.   Sorted Set에 멤버가 많으면 키가 삭제될 때 진짜로 성능이 떨어질까?   삭제 시간은 얼마나 걸릴까?   다른 데이터 타입은 어떤가?
  <사실 이 글을 쓰게 된 직접 동기는 이 마지막 질문에서 시작되었습니다. 질문 주신 분께 감사드립니다>
  

이 의문들을 풀 방법은 Sorted Set의 데이터 저장 구조를 알아보는 것입니다.

Sorted Set의 데이터 구조(data structure)

Sorted Set은 내부적으로 두 가지 데이터 구조로 저장된다.   레디스가 데이터 구조를 선택하는데, 두 가지 조건이 있다. 하나는 멤버 수가 128개 까지는 zip list라는 데이터 구조에 저장되고, 129개부터는 데이터 구조를 변환에서 skip list에 저장된다.   다른 하나는 값(value)의 길이가 64바이트까지는 zip list에 저장되고, 65바이트부터는 skip list에 저장된다.   여러 멤버 중에서 하나라도 값이 65바이트 이상이면 변환된다.   이 두 가지는 OR 조건이다. 둘 중 하나라도 만족하면 레디스 서버가 자동으로 데이터 구조를 변환해서 저장한다.
이 조건은 redis.conf의 ADVANCDE CONFIG 파트에 있으며 변경할 수 있다.

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

zset-max-ziplist-entries 는 Sorted Set에서 zip list로 저장할 수 있는 최대 엔트리(멤버) 수를 설정하는 파라미터이고, zset-max-ziplist-value 는 Sorted Set에서 zip list 로 저장할 수 있는 값(value)의 최대 길이다.
여기서 용어 정리를 하고 가자.   레디스는 Sorted Set을 내부적으로 Zset이라고 한다. 그래서 이 글에서도 줄여서 Zset이라고 한다.

두 가지 데이터 구조를 사용하는 이유

Zip list를 간단히 설명하면, 메모리 절약에 최적화된 구조이다.   레디스는 메모리 데이터베이스이고, 데이터 타입에 따라서 메모리 오버헤드가 많을 수 있다.   그래서 살바토르는 고민했고, 한 가지 데이터 타입임에도 불구하고 성능을 많이 해치지 않는 범위에서 메모리 절약할 수 있는 데이터 구조를 내부적으로 사용하게 되었다.   그것이 zip list이다. 그러므로 zip list는 한정적으로 사용된다.
- Zip list와 이어서 설명할 skip list의 ZADD(Insert) 성능 차이는 아래에 있다. -
Zset을 위한 메인 데이터 구조는 skip list이다.   그래서 여기서는 skip list에 대해서 알아보도록 한다.

스킵 리스트 이해하기

스킵 리스트는 정렬된 상태를 유지하면서 데이터를 삽입, 삭제하고 탐색할 수 있는 데이터 구조체(data structure)이다. 여기 설명은 윌리엄 퓨(William Pugh, Skip Lists: A Probabilistic Alternative to Balanced Tress) 의 논문(1990년 발표)에 근거해 설명한다.   살바토르도 이 논문을 바탕으로 Sorted Set에 사용되는 스킵 리스트를 구현했다.

스킵 리스트는 링크드 리스트의 단점을 개선하는 데서 시작한다.   여기서 설명하는 링크드 리스트는 정렬된 상태를 유지하는 리스트이다.   이런 링크드 리스트에서 n 번째 node를 찾으려면 n 번 비교를 해야 한다.
아래 그림에서 보는 것처럼 값이 '80' 인 노드를 찾으려면 비교를 9번 해야 한다.   최악의 경우 모든 노드를 비교해야 한다.

레벨을 갖는 스킵 리스트

탐색 시간을 단축하기 위해서는 비교 횟수를 줄여야 한다.   여기서 아이디어를 낸 것이 노드에 포인터를 두 개를 갖게 해서 두 번째 포인터는 하나 건너뛰어서 다음 노드를 가리키도록 한다.

위 그림에서 보는 것처럼 홀수 번째 노드는 포인터 하나만 갖고, 짝수 번째 노드는 포인터를 두 개 갖은 것이다.   이렇게 구현하면 하나씩 건너 뛰어 비교할 수 있기 때문에 n 번째 노드를 찾는데 n/2 + 1 번 비교하면 된다.   비교 횟수를 반으로 줄이는 획기적인 아이디어이다.   값이 '80' 인 노드를 찾는데 비교를 5번으로 줄었다.
하지만 노드 수가 수십만, 수백만 개라면 여전히 비교 횟수는 많고 따라서 탐색 속도도 느릴 것이다.

레벨 3 갖는 스킵 리스트

한 발 더 나가서 그림 1-c 처럼 포인터를 세 개 가지는 노드를 두면, 비교 횟수는 더 줄어들게 된다.

값 '80' 인 노드를 찾는 잠시 과정을 살펴보자.
이것이 스킵 리스트의 탐색 알고리즘을 설명한 것이므로 잘 기억해두자.   삽입, 삭제시에도 같은 방법으로 찾아간다.
• 맨 앞에 '레벨 3'이라고 쓰여있는 노드를 헤더라고 하자.  
• 출발은 헤더 노드의 레벨 3 포인터에서 시작한다.  
• 레벨 3이 가리키는 값이 '20'이다.  
• 찾고자 하는 '80'이 '20' 보다 크기 때문에 다음 포인터로 진행해서 '70'과 비교한다.  
• 역시 '80'이 크기 때문에 다음 포인터로 진행하려고 하지만 'Null' 이기 때문에 레벨을 하나 낮추어서(레벨 2) 비교한다.  
• '80'이 '90' 보다 작기 때문에 다시 레벨을 낮추어서(레벨 1) 비교한다.  
• '80'을 찾았다.
• 총 비교 횟수는 4회이다.

레벨 4 스킵 리스트

위 그림을 보자.   값이 '70'인 8번째 노드에 포인터 4개를 갖도록 하면 비교 횟수는 더 줄어들게 된다.   이와 같이 구현하면 포인터 하나씩 증가할 때마다 2^n 개의 노드를 건너뛰어 비교해서 비교 횟수가 획기적으로 줄어들게 된다.
자 이제 스킵 리스트는 이해되었다.   같은 방식으로 '80'을 찾는데, 비교 횟수는 총 3회로 줄었다.
이제 탐색 시간 단축은 해결되었다.   16개 포인터를 가지면 65,536 번째 노드와 바로 비교할 수 있으므로, 건너뛰기(스킵) 하기 위해서 포인터를 늘려주면 된다.

자 이제, 용어를 좀 정리해서 포인터를 몇 개 가지는냐를 레벨(level)이라고 하자.
다음 노드를 가리키는 포인터를 레벨 1,
하나 건너뛰어 다음 노드를 가리키는 포인터를 레벨 2,
노드 세 개를 건너뛰어 네 번째 노드를 가리키는 포인터를 레벨 3라고 하자.
레벨은 계속 늘려나가면 된다.

2의 거듭제곱으로 표시하면,   (위 그림을 보면서)
레벨 1은 2^0=1 : 바로 다음 노드를 가리킨다.
레벨 2는 2^1=2 : 하나 건너뛴 다음 노드, 2 번째 노드를 가리킨다.
레벨 3은 2^2=4 : 4 번째 노드를 가리킨다.
레벨 4는 2^3=8 : 8 번째 노드를 가리킨다.
 ...
레벨 16은 2^15=32,768: 32,768번째 노드를 가리킨다.
 ...
레벨 32는 2^31=2,147,483,648: 대략 이십억 번째 노드를 가리킨다.

미리 정해진 레벨 문제

이제까지 살펴본 스킵 리스트는 위의 그림처럼 노드 순서마다 레벨이 정해져 있다.   이렇게 미리 정해진 레벨을 사용하게 되면 무슨 문제가 생길까?   그렇다. 노드 삽입과 삭제 시에 이후 모든 노드의 순서가 바뀌므로 모두 레벨을 수정해주어야 한다.   이렇게 되면 삽입/삭제 시간이 굉장히 많이 걸릴 것이다.   레벨을 가지는 노드라는 매우 좋은 아이디어를 냈지만, 이 삽입/삭제 부하를 해결하지 못하면 스킵 리스트는 쓸 수 없을 것이다.

동전 던지기

레벨을 정하는 방법을 새로 생각해야 했다.   새로운 방법은 각 노드의 레벨은 독립적으로 정해져야 할 것이다.   즉, 스킵 리스트의 총 노드 수 또는 순서와 같은 스킵 리스트의 어떤 값과 관계없이 정해져야 하고, 한 번 정해지면 바뀌지 않아야 한다.   어떻게 해야 할까?
윌리엄은 이 문제를 동전 던지기로 풀었다.   즉, 새로운 노드가 생길 때(삽입)마다, 동전을 던져서 같은 면이 연속해서 나온 횟수로 레벨을 정하는 것이다.





첫 번째 던지면 일단 레벨 1,
두 번째 던져서 다른 면이 나오면 레벨 1로 정해지고, 같은 면이 나오면 레벨 2로 올리고, 다시 던진다.
세 번째 던져서 다른 면이 나오면 레벨 2로 정해지고, 같은 면이 나오면 레벨 3로 올리고, 다시 던진다.
이렇게 계속해서 레벨을 정한다.

이런 생각을 할 수도 있다.   동전 던지기를 하면 낮은 레벨만 계속 나오는 것이 아닌가?   적당한 수준에서 높은 레벨도 나와야 비교 횟수를 줄일 수 있는데, 레벨 10이 나오려면 같은 면이 연속해서 10번 나와야 하는데, 나올 수 있을까?
나온다. 동전 던지기는 1/2 확률을 곱해나가는 것이므로 레벨 1의 확률은 50%, 레벨 2의 확률은 25%, 레벨 3의 확률은 12.5%, 이렇게 된다.   그러므로 천 번쯤 던지면 레벨 10이 나온다. 백만 번 던지면 레벨 20이 나온다. 레벨 20(2^19)이면 524,288 번째 노드를 가리키는 것이므로 비교 횟수가 확실히 준다.
오히려, 높은 레벨이 너무 많이 나올 것을 걱정해야 한다.
왜 이것을 걱정해야 할까?   레벨이 높다는 것은 포인터를 그만큼 많이 가지고 있는 것이므로, 실제 저장되는 값에 비해서 관리용 메모리를 너무 많이 사용하게 되는 것이다.   메모리 오버헤드 문제는 잠시 후에 나온다.

이제 독립된 레벨을 갖는 문제는 해결되었다.   노드 삽입 시 삽입되는 노드를 가리키도록 관련된 앞 노드의 포인터를 수정해 주어야 하고, 삽입되는 노드는 레벨에 맞게 다음 노드를 가리키는 포인터를 넣어주면 된다.   이제 노드 삽입 시마다 이후 모든 노드의 레벨과 포인터를 조정해야 하는 큰 부담이 없어졌다.   하지만 문제가 다 해결된 것은 아니다.

순서 SPAN

이렇게 확률로 레벨을 정하면 한 가지 문제가 생긴다.   고정된 레벨 일 때는 레벨로 몇 번째 노드를 가리키는지 알았으나, 확률로 바뀌면서 노드는 정렬된 상태를 유지하지만, 몇 번째인지는 알 수 없어졌다.   ZRANGE, ZRANK 같은 Sorted Set의 많은 명령은 노드가 몇 번째인지를 바로 알아야 한다.   그래서 레디스에서는 레벨에 포인터와 순서를 가지는 필드를 만들어 저장하고, 필드명을 SPAN으로 했다.   이것을 인덱스 스킵 리스트(indexed skip list)라고 한다.

탐색하면서 각 스팬이 갖는 숫자를 더하면 순서를 알 수 있다.   하늘색 사각형을 보라.   '20'은 3 + 1 = 4번째이다.

주사위 던지기

이제 문제 해결됐다.   하지만 윌리엄은 레벨마다 포인터와 순서(span)을 저장해야 하므로 메모리 오버헤드를 줄이는 방법을 생각해야 했다.   방법은 레벨을 낮추는 것이다.   레벨을 낮추기 위해서는 같은 면이 나오는 확률을 낮추어야 하는데, 동전은 면이 두 개로 정해져 있다.

그럼 동전 말고 무엇을 사용해야 할까?   그렇다.   주사위를 사용하는 것이다.   그런데 일반 주사위는 6개의 수를 가지고 있어서, 같은 수가 나올 확률이 동전의 1/2에서 1/6으로 줄어드는 것이다.   레벨 4가 나올 확률이 동전은 1/16 인 반면 주사위는 1/1296으로 너무 줄었다.   6면체 주사위는 레벨이 낮아져 관리용 메모리는 적게 사용하는 반면, 비교 횟수가 많아져 탐색 시간은 늘어나는 것이다.

다음 표는 윌리엄 논문에 나와있는 확률(동전 또는 주사위 면수)에 따른 상대적 탐색 시간과 노드 당 평균 레벨 수이다.

어떤 확률을 선택할지 첫 번째 조건은 탐색 시간이다.   탐색 시간이 가장 빠른 것은 1/e 지만, 1/4과 거의 차이가 없고, 노드 당 평균 포인터 수를 보면 상위 3개 중 1/4가 가장 적으므로 윌리엄의 논문에서도 1/4 확률을 추천했고, 레디스에서도 1/4를 사용했다.
레디스에서는 server.h에 다음과 같이 정의했다.

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

레디스에서 수정 내용

레디스에서는 원래 스킵 리스트에 몇 가지 수정을 해서 구현했다.
• 같은 스코어가 반복되는 것을 허용한다.   그래서 LEX 명령을 사용할 수 있게 했다.   LEX 명령을 사용하려면 스코어는 모두 같아야 한다.   값(value)는 달라야 한다.
• 위와 같이 LEX를 구현하기 위해서 스코어가 같으면 값(value)을 비교한다.  
• 역 탐색을 위해서 이전 노드를 가리키는 포인터(back pointer)를 둔다.
• 최대 레벨을 32로 했다.
• 스킵 리스트 자체를 저장하는 구조체에 최대 레벨과, 노드 수(length), 헤더 노드, 마지막(tail) 노드의 포인터를 가지고 있다.

레디스 스킵 리스트 data structure

아래 그림은 레디스 스킵 리스트 data structure이다.   zskiplist는 skip list 자체이고, 각 필드당 8 bytes 씩 모두 32 bytes이다.   zskiplistNode는 노드이고, 아래 하늘색 부분이 필드 당 8 bytes 씩 24 bytes이고, 레벨 하나당 forward 8 bytes, span 8 bytes 해서 16 bytes이다.
헤더 노드는 값을 갖지 않고 레벨 32까지 모두 만들어 놓는다.
zskiplistNode의 마지막 field가 3.x까지는 robj *obj이었고, 4.0부터는 sds ele이다.

노드 1 삽입

"ZADD key 70 value-A" 이와 같은 명령이 수행되었다고 가정하면, 아래와 같이 zskiplist와 header 가 만들어지고, node 1이 만들어 진다.   Node 1은 첫 번째 노드임에도 불구하고 우연히 레벨 2를 가지게 되었다.
그럼 zskiplist->length(총 노드 수)는 1, zskiplist->level(최대 레벨)은 2 가 저장되고,
C 언어의 배열로 구현되었으므로 레벨 1을 level[0], 레벨 2를 level[1] 로 표현한다.
header->level[0].forward와 header->level[1].forward 는 같이 node 1의 포인터를 가진다.
header->level[0].span과 header->level[1].span 도 같이 1을 가진다.
변경되는 값들은 빨간색으로 굵게 표시했다.

노드 1의 레벨 1, 2의 forward는 다음 노드가 없으므로 Null을 가지고, span 도 역시 다음 노드가 없으므로 0이다.   backward는 header를 가리키지 않고 Null을 갖는다.   스코어는 노드에 저장된다.  그림에는 생략했지만 값(value)는 별도 구조체에 저장되고, obj는 포인터를 가진다.

노드 2 삽입

노드를 삽입할 때는 우선 해당 키에 값(value)이 있는지 확인한다.   값이 있으면 노드를 삭제(delete) 하고 삽입(insert)하고, 없으면 바로 삽입(insert) 한다.
아래 그림은 "ZADD key 90 value-B" 가 수행된 예이다.   스코어가 70보다 크므로 뒤로 들어갔다. 스킵 리스트에서 탐색, 삽입, 삭제는 알고리즘은 위 '레벨 3 갖는 스킵 리스트'의 탐색 과정과 같다.

zskiplist->legnth가 2로 증가했고, 레벨은 그대로이다.   Node 1의 레벨 1 forward가 새로 입력된 노드 2를 가리키고, span 이 1로 변경되었다.   Node 2의 backward는 노드 1를 가리키게 되었다.

레디스 스킵 리스트의 최대 멤버 수는

레디스 스킵 리스트는 멤버를 몇 개까지 가질 수 있을까?
레디스 데이터 타입 문서 에 보면 리스트(Lists), 셋(Set), 해시(Hashes) 모두 2^32 - 1 (4,294,967,295) 약 43억 개를 저장할 수 있다고 나와있다.   그런데 Sorted Set 만 정확한 숫자가 나와있지 않다.   왜 일까?   지금까지 레디스 스킵 리스트를 살펴보았으니 알 것이다.   최대 레벨은 32로 정해져 있지만 스코어 비교 시 레벨을 그대로 두고 다음 포인터로 계속 진행할 수 있으므로 최대 레벨과 관계없이 계속 저장할 수 있다.
제한이 있다면 길이(length) 저장에 unsigned long를 사용했으므로 2^64 = 18,446,744,073,709,600,000 약 일천팔백 경(조 다음 단위가 경이다) 만큼 저장할 수 있다.   사실상 메모리 제한만 있는 것이다.

테스트 서버 스팩

Redis Server : Version 3.0.5
OS : CentOS 7
H/W Model: HP DL320e Gen8 v2
Processor : Intel(R) Xeon(R) CPU E3-1231 v3 @3.4GHz, 8 Cores
Main Memory: DDR3 8GB RAM

첫 번째 의문 : 입력시간이 늘지 않아요.

ZADD로 10만 건 단위로 저장하면서 시간을 측정했다.   시간은 순수 처리 시간만 계산하기 위해서 info commandstats 명령에서 나오는 시간으로 했다.
테스트 코드는 Python으로 했다. 아래 소스가 있다.   start_index 에서 end_index까지 while loop 돌면서 저장한다.
def zaddinc(conn,key,start_index,end_index):
      i = start_index
      while i <= end_index:
          conn.zadd(key,  'val-'+str(i),  i)
          i = i+1


다음 표는 10만건 단위로 수행하는데 걸린 시간이다.

순서	스코어	시간(ms)	1건 시간(us)
1번째 10만 건	1~100,000	120	1.20
2번째 10만 건	100,001~200,000	133	1.33
3번째 10만 건	200,001~300,000	136	1.36
4번째 10만 건	300,001~400,000	142	1.42
5번째 10만 건	400,001~500,000	115	1.15
6번째 10만 건	500,001~600,000	176	1.76
7번째 10만 건	600,001~700,000	183	1.83
8번째 10만 건	700,001~800,000	109	1.09
9번째 10만 건	800,001~900,000	111	1.11
10번째 10만 건	900,001~1,000,000	121	1.21
평균		135	1.35


1건 평균 입력시간이 1.35us(microsecond)이다.
이것을 그래프로 보면 아래와 같다.   보는 바와 같이 6,7회때 많이 늘었으나, 8,9,10회 때 다시 줄어든 것을 보면 지속적으로 증가한다고 보기 어렵다.

다음은 지속적으로 감소하는 스코어 테스트 결과이다.
1건 평균 입력시간이 1.25us이다.

다음은 랜덤 스코어 테스트 결과이다.
1건 평균 입력시간이 앞의 두 테스트 결과 보다 많아서 1.99us이다. 약 50% 정도 증가했다.
지속적으로 증가 또는 감소하거나 랜덤이거나 비교하는 횟수는 같다.   그런데 왜 시간 차이가 날까?
원인을 추정해보면 증가나 감소는 계속 증가하거나 감소하기 때문에 비교할 값들이 이미 CPU cache에 있어서 빠르게 처리할 수 있었고, 랜덤은 비교할 값들을 거의 메인 메모리에서 읽어오기 때문에 처리시간이 더 걸렸을 것이다.
이것은 마치 디스크와 메모리(RAM)의 속도 차이와 비교될 수 있다.

이런 종류의 다른 Balanced Tree 알고리즘들은 보통 지속적으로 증가하거나 감소하는 값에 대해서 성능이 나빠지는 면이 있는데, 스킵 리스트는 전혀 그렇지 않다.   오히려 H/W 아키텍처의 영향으로 스코어가 지속적으로 증가/감소할 때 더 빠르게 처리된다.  

짚 리스트 ZIP LIST

위에서 Sorted Set은 두 가지 데이터 구조체로 저장된다고 설명했다.   Sorted Set의 메인 데이터 구조체는 스킵 리스트이지만, 메모리 절약을 위해서 짚 리스트(zip list)를 사용한다고 했다.
언제 짚 리스트(zip list)를 사용하고, 언제 스킵 리스트를 사용하는지는 redis.conf의 ADVANCDE CONFIG 파트에서 변경할 수 있다.

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


앞에서 한 테스트들은 zset-max-ziplist-entries를 0으로 설정하고 했다.   그래야 처음부터 스킵 리스트에 저장되어 스킵 리스트의 성능을 좀 더 정확히 파악할 수 있다.

위의 기본값(default)를 그대로 놓고 테스트해보자.

zip list는 entry가 많아질수록 위 그래프에서 보는 것처럼 속도가 처리 시간이 늘어난다.
처음에 약 8~10us였던 것이 갈수록 늘어 18us가 되었다.
가로축 126 즈음에 막대그래프가 올라간 것은 129번째 입력 시 짚 리스트에서 스킵 리스트로 변환된 것이고, 변환 시간은 123us가 걸렸다.   이후는 스킵 리스트에 입력되는 시간이다.   짚 리스트보다 스킵 리스트의 성능이 훨씬 나은 것을 알 수 있다.
짚 리스트의 처리 시간 증가를 좀 더 확실히 파악하기 위해 max-ziplist-entries를 512로 설정하고 테스트해보자.

500번째 쯤은 1건 입력 시간이 50us 걸렸다.   데이터 변환 시간은 470us가 걸렸다.
짚 리스트는 데이터 구조상 데이터가 늘어날수록 처리 시간이 길어진다.

두 번째 의문 : 메모리를 왜 이렇게 많이 쓰나요?

ZADD로 입력하면서 메모리 사용량을 체크해 보았다.
방법은 info memory 명령으로 초기 사용량을 확인하고, 1건 입력하고 메모리 확인, 다시 1건 입력하고 메모리 사용량을 확인했다.     * 필요한 내용으로 간추렸다.
redis> info memory
    used_memory: 815080
redis> zadd key 100 value100
redis> info memory
    used_memory: 816120
redis> zadd key 101 value101
redis> info memory
    used_memory: 816248


처음 입력 후 메모리 사용량은 816120 - 815080 = 1040 bytes이다.   처음에는 key, skiplist, header, node, robj, value 등이 있으니 그렇다고 치자.   두 번째부터는 node, robj, value 만 있으니 계산하기 쉽다.
아래 그림은 node, robj(redisObject), value의 data structure이다.
마지막 field: 3.x까지는 robj이었고, 4.0부터는 sds이다.

zskiplistNode 가 32레벨 모두 할당되면 536 바이트이다.
두 번째 입력에서는 레벨 1이므로,
node : 32 bytes(base) + 16 bytes(level 1) = 40 bytes
redisObject : 24 bytes
value : 8 bytes
합계 : 72 bytes
그런데 816,248 - 816,120 하면 128 바이트가 할당되었다.   어찌된 일인가?

이 문제를 이해하기 위해서는 OS의 메모리 할당 단위를 알아야 한다.
리눅스의 메모리 할당 기본 단위는 페이지이고, 한 페이지는 4k(4096)이다.   그럼 1 바이트를 요구해도 4k 바이트를 할당할 것이가?   그렇게 한다면, 얼마나 낭비겠는가?   이런 일이 자주 발생하면 리눅스는 곧 메모리가 부족하다고 할 것이다.   이런 일을 방지하기 위해서 그리고 페이지 내 단편화(fragmentation)를 막기 위해서 리눅스는 아래 표에 보는 것처럼, 할당 단위를 미리 정해놓았다.

Linux OS의 메모리 할당 단위
vmstat -m 또는 cat /proc/slabinfo 로 확인할 수 있고, 페이지 사이즈는 getconf PAGESIZE 명령으로 확인할 수 있다.


Cache Name	Bytes
kmalloc-8192	8192
kmalloc-4096	4096
kmalloc-2048	2048
kmalloc-1024	1024
kmalloc-512	512
kmalloc-256	256
kmalloc-192	192
kmalloc-128	96
kmalloc-96	96
kmalloc-64	64
kmalloc-32	32
kmalloc-16	16
kmalloc-8	8


그럼 이제 다시 계산해 보자.

• 두 번째 노드에 40 바이트가 필요해서 OS에 요청하면, OS는 40 바이트 단위가 없으므로, 이보다 큰 64 바이트를 할당한다.
• redisObject에 24 바이트를 요청받았지만, OS는 32 바이트를 할당한다.   이 경우 OS가 16 바이트 짜리 와 8 바이트 짜리를 합해서 24 바이트를 할당 할 수도 있지만 보통은 32 바이트를 할당한다.
• Value에 8바이트를 요청받았지만, OS은 32 바이트를 할당했다.

이렇게 해서 합계 128 바이트가 되었다.
레디스가 실제 값보다 메모리를 더 많이 사용하는 경우는, 레벨에 저장되는 forward 포인터, Span, backward 포인터 등 관리용 메모리의 오버헤드와 리눅스의 메모리 할당 방식에 따른 오버헤드도 있는 것이다.   저장할 값이 작은 경우 오버헤드 비율은 더 커지게 된다.

AOF와 RDB 파일 크기

레디스의 데이터 사이즈는 메모리에 있을 때가 가장 크고, AOF, RDB 파일 순으로 적어진다.
메모리는 위에서 설명했으므로, AOF 파일을 설명한다.
우선 아래 예를 보자.

ZADD
$3
key
$4
1566
$8
val-1566

명령과 키, 값 앞 라인에 길이가 들어간다. 명령과 키가 매번 들어가는 것은 아니다.

아래는 dump.rdb 파일에 바이너리 형태로 저장된 일부이다.   vi -b dump.rdb 로 열어서 복사한 것이다.
REDIS0006^@^C^CkeyC^Hval-1566^D1566

스코어를 1001 ~ 2000까지 했고 값(value)를 'val-1001' ~ 'val-2000'으로 하고, BGREWRITEAOF, BGSAVE 명령으로 저장했다.
• 메모리: 142,064 bytes
• AOF:       24,422 bytes
• RDB:       14,027 bytes
• 실제 사이즈: 12,000 bytes
• 메모리는 AOF에 비해 약 6배, RDB와 비교하면 10배 커졌다.

스코어를 20001 ~ 30000으로 하고, 값을 55 바이트 'AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA20001 ~ 30000'으로 했을 경우, 비교해 보면

• 메모리: 1,851,152 bytes
• AOF:       735,831 bytes
• RDB:       210,038 bytes
• 실제 사이즈: 600,000 bytes
• 메모리는 AOF에 비해 약 2.5배, RDB와 비교하면 약 9배 커졌다.   이 경우 RDB는 반복된 'A'를 압축해서 실제 사이즈보다도 적어졌다.

정리하면 Sorted Set의 skip list의 경우 관리용 메모리 오버헤드와 리눅스 커널 메모리 할당 방식에 따른 오버헤드를 합쳐서 실제 값의 몇 배를 사용할 수 있다는 것을 인지하고 사용해야 한다.

세 번째 질문: 삭제 부하는 큰가?

키에 멤버가 많을수록 삭제 시간은 더 오래 걸린다.   스킵 리스트는 그림 6-a에서 본 것처럼 노드, robj, value 이렇게 구성되어 있으므로 멤버 하나 삭제하는데 free()가 3번 수행된다.   그러므로 멤버가 10만 개면 free()는 30만 번 수행된다.
멤버가 10만 개이고 14MB 메모리를 차지하는 Sorted Set 키를 삭제하는데, 38ms가 걸렸다.   이 값은 20번 수행해서 얻은 평균이다.   멤버가 백만 개이면 약 400ms(0.4sec)가 걸린다.
10만 개 키 5개를 연속해서 del 하는데 CPU는 약 2~3% 정도 사용했다.   우려할 만한 수준은 아니라고 본다.
EXPIRE로 시간을 걸어놓으면 레디스 서버는 100ms마다 expire 시간을 체크해서 지났으면 del 명령을 실행한다.  그러므로 expire 나 del은 같은 것으로 보아도 된다.
그럼 다른 데이터 타입은 어떤가?
같은 방식으로 LIST를 테스트 했을 때 19ms가 걸렸고, SET은 skip list와 비슷하게 37ms가 걸렸다.

여기까지 읽어 주셔서 고맙습니다.

질문 받은 다음, 스킵 리스트 정리하고, 짚 리스트(zip list) 약간 맛보고, ZADD로 삽입 테스트하고, 메모리 계산하고, 커널 메모리 할단 단위 확인하고, 삭제 테스트하고, 이 글을 작성하느데 시간이 좀 걸렸습니다.   스킵 리스트를 이해하셨다면 큰 수확입니다.

윌리엄은 코넬대학에서 컴퓨터공학으로 박사학위를 받았고, 23년 간 메릴랜드대학에서 교수로 있었습니다.
스킵 리스트를 발표해준 윌리엄에게 고마움을 표합니다.