Redis STRINGS Data Structure

내부 데이터 구조

레디스에서는 문자열 처리를 위해 문자열 관리 라이브러리를 만들었고, 이것을 SDS(Simple Dynamic Strings)라고 합니다. SDS를 만든 이유는 바이너리 데이터를 처리하기 위해서 입니다.   그래서 키나 값을 구성하는 문자열에 특수문자 포함할 수 있습니다.   바이너리 데이터는 널 문자를 포함해서 특수문자를 포함할 수 있기 때문에 널 문자(null term) 만으로 문자열을 구분할 수가 없어서 길이 정보를 가진 헤더를 만들었습니다.   SDS 문자열은 SDS 헤더 + 문자열 + 널 문자(null term)으로 구성됩니다.  
값이 정수의 경우는 문자열로 저장하지 않고 long형(8 바이트)으로 저장합니다.   클라이언트에서 받을 때는 키, 값 모두 일단 문자열로 받습니다.   그런 후 값(value)이 정수로 변환 가능하면 정수로 변환합니다.   '1.1' 처럼 실수이거나, 앞에 0을 포함한 수 '01', 컴마를 포함한 수 '1,234' 는 정수로 변환되지 않고 그대로 문자열로 저장됩니다.  

스트링은 아래 그림처럼 정수와 문자열로 나누어지고, 세분하면 네 가지로 나누어 집니다.  
이렇게 구분하는 중요한 이유는 메모리 절약과 성능 향상입니다.   이제 하나씩 풀어 나가겠습니다.




• 정수는 공유 정수와 독립 정수로 구분합니다. redis.io 문서에는 독립 정수라는 말을 사용하지 않지만, 공유 정수와 구분하기 위해서 이름 지었습니다.
• 공유 정수는 0 ~ 9999까지의 정수로 레디스 서버 시작 시 미리 만들어 놓습니다.   그래서 SET 명령으로 이 사이의 값을 입력하면 값을 새로 만들지 않고(malloc으로 메모리를 할당하지 않고) 이미 만들어 놓은 값을 참조하게 합니다.   이것은 이 범위의 값이 많이 사용되기 때문에 메모리를 절약하기 위해서 입니다.
• 독립 정수는 공유 정수가 아닌 정수로 메모리를 할당해서 수를 저장합니다.  
• 이제 문자열을 설명하겠습니다.   문자열을 저장하는데 SDS 문자열을 사용합니다.   SDS 문자열은 embstr(embedded string)과 raw로 구분합니다.   우선 SDS 스트링이 어떻게 괸리되는 알아보기 위해서 레디스에서 대부분의 오브젝트를 관리하는 redisObject(robj)에 대해서 알아 봅시다.



• type은 4 비트로, 데이터 타입을 저장합니다.   데이터 타입이란 레디스의 다섯 가지 데이터 타입( STRING, LIST, SET, SORTED SET, HASH )를 의미합니다.   아래에 설명할 내부 데이터 타입과 구분하기 위해서 외부 데이터 타입이라고 했습니다.
  TYPE 명령으로 확인할 수 있습니다.   이 TYPE 명령은 robj의 이 type 필드의 값을 조회하는 것입니다.
• encoding은 내부 데이터 타입으로 외부 데이터 타입은 STRING 한 가지지만 이 글에서 설명하는 것처럼 내부적으로 정수(int), 같이 할당 문자열(embstr), 따로 할당 문자열(raw) 이렇게 세 가지로 저장 방식(encoding)이 나누어지기 때문에 어떤 방식으로 저장되어 있는지 구분하기 위해 필요합니다.
  OBJECT encoding 명령으로 확인할 수 있습니다.   이 명령은 robj의 encoding 필드의 값을 조회하는 것입니다.
• lru는 시간을 저장합니다.
  OBJECT idletime 명령으로 확인할 수 있습니다.   이 명령은 robj의 lru 필드의 값으로 계산해서 보여주는 것입니다.
• refcount는 참조 횟수를 저장합니다.
  OBJECT refcount 명령으로 확인할 수 있습니다.   OBJECT refcount 페이지로 가서 애니메이션을 보면 이해하기 더 쉬울 것입니다.   이 명령은 robj의 refcount 필드의 값을 조회하는 것입니다.
• 마지막 필드는 ptr입니다.   Ptr은 정수나 SDS 헤더를 포함한 문자열(value)을 가리킵니다.   그러면 이제 위에서 잠깐 언급했던, SDS 헤더의 구조에 대해서 설명하겠습니다.   아래는 sdshdr(sds header)의 구조입니다.
  
  
  Len은 문자열 길이를 저장하고, Free는 문자열 뒤에 남은 공간의 길이를 나타냅니다.   이어서 문자열(value)과 null term(1 byte)이 저장됩니다.   예를 들면, 값으로 'Hello'를 입력했으면, len(4 bytes) + free(4 bytes) + 'Hello'(5 bytes) + null term(1 byte) = 14 bytes 를 차지합니다.   이때 robj의 ptr은 sdshdr를 시작 주소를 가지고 있지 않고, 문자열이 있은 buf 주소를 가지고 있습니다.   그래서 robj->ptr가 문자열을 바로 가리키게 됩니다.
  
  여기서 잠깐 free에 대해서 설명하면, 처음에는 0이지만, SET 명령 후 APPEND을 실행하면 레디스는 추가 메모리를 좀 여유 있게 할당합니다.   또 추가로 데이터가 들어올 수 있기 때문입니다.   예를 들어 SET key Hello를 하면 len = 5, free = 0 이 저장되지만, APPEND key redisgate.com을 하면 len = 18, free = 18이 됩니다.   (5 바이트(value)+13 바이트(redisgate.com)) * 2 = 36 바이트를 할당하다. 확인은 debug sdslen key로 할 수 있습니다.   val_sds_len이 len을 나타내고, val_sds_avail이 free를 나타냅니다.   STRLEN 명령도 len 필드 값을 리턴합니다.


• EMBSTR을 '같이 할당'이라고 했는데, 문자열의 길이가 39 바이트 이하이면, 한 번에 redisObject와 sdshdr을 위한 메모리를 할당하는 것입니다.   이와 같이 할당을 수행합니다.
  레디스 버전 3.2.0 부터 EMBSTR '같이 할당' 길이가 44 바이트로 변경되었습니다.
  jemalloc(sizeof(redisObject) + sizeof(sdshdr) + strlen(value) + 1)  
  
  아래 그림은 '같이 할당' 후 ptr이 'redisgate.com'을 가리키고 있는 모습입니다.   참고로 EMBSTR은 Embedded String의 약자입니다.
  
  
  
• RAW String은 문자열의 길이가 40 바이트 이상이면 redisObject와 sdshdr를 '각각 할당'합니다.  
  jemalloc(sizeof(redisObject))
  jemalloc(sizeof(sdshdr) + strlen(value) + 1)
  
  아래 그림은 '각각 할당' 후 ptr이 'Hello ... redisgate.com'을 가리키고 있는 모습입니다.  

'같이 할당'과  '각각 할당' 그리고 39 바이트

이제 '같이 할당'과 '각각 할당'의 의미와, 구분 기준을 왜 39 바이트로 했는지 알아봅시다.   같은 길이의 데이터를 저장하는데, 메모리 할당을 한 번 하느냐, 두 번 하느냐는 당연히 성능에 차이가 납니다.   그래서 39 바이트 이하의 데이터는 '같이 할당' 방식으로 구현했습니다.

'같이 할당'은 SET 명령뿐만 아니라 GET 명령의 성능도 같이 향상되었습니다.   아래 그림에서 보는 것처럼, Processor가 테이터를 처리하기 위해서는 메인 메모리에 있는 데이터를 CPU 케시로 불러들여야 합니다.  




• 디스트와 메모리의 속도 차이가 큰 것처럼, 메인 메모리와 CPU 케시의 속도 차이도 큽니다.   따라서 데이터를 한 번에 불러들이느냐, 두 번 불러들이느냐는 당연히 처리 속도에 차이가 납니다.   '각각 할당'이 되면 데이터를 처리하기 위해서 redisObject를 CPU 케시로 불러들이고, redisObject에서 가리키는 메모리 주소로 sdshdr+value를 불러들입니다.   이때 다행히 sdshdr+value가 CPU 케시에 있으면 바로 처리되는데, 없으면 아래 그림에서와 같이 두 번 메인 메모리에서 불어와야 합니다.




• '같이 할당'은 아래 그림에서와 같이 한 번에 redisOjbect와 sdshdr+value를 CPU 케시로 읽어들입니다.   왜냐하면 한 번에 할당되어기 때문에 할당된 단위로 CPU 케시에 읽어들입니다.   그래서 '각각 할당'보다 더 빠르게 처리됩니다.
  
  
• 그럼 왜 39일까요? 그건 jemalloc()의 메모리 할당 단위와 관련이 있습니다.   jemalloc는 요청한 만큼만 할당하는 것이 아니고, 32, 64, 128 과같이 미리 정해놓은 단위로 할당합니다.   이유는 메모리 할당 속도 향상과 메모리 페이지 단편화 문제를 개선하고자 하는 것입니다.   예를 들어, 커널에 25 바이트를 요청하면 32 바이트를 할당해 줍니다.   7 바이트는 사용되지 않고 낭비되지만, 요청한 만큼만 할당하려면 커널이 해당하는 메모리를 찾는데, 시간이 오래 걸려 성능이 떨어지고, 요청받아 할당한 크기가 각각 다르기 때문에 메모리 단편화율이 높아서 결국에 메모리 낭비가 더 심하게 되는 것입니다.
  jemalloc 자료 (Jason Evans 작성)
  
  앞에서 문자열을 저장하려면, redisObject와 sdshdr이 필요하다고 했습니다.   redisObject가 16 바이트이고, sdshdr이 8 바이트, null term이 1 바이트이므로, 총 25 바이트가 필요합니다.   일반적으로 많이 사용되는 메모리 할당 단위인 64 바이트를 맞추기 위해 문자열 길이를 39 바이트로 했습니다.  
  25(16 + 8 + 1) + 39 = 64 바이트
  레디스 버전 3.2.0에서는 SDS header가 데이터 길이에 따라 4 가지 Type(3,5,9,17 바이트)이 생겼다.   데이터 길이가 짧기 때문에 3 바이트 sds header가 적용되어, 데이터 길이는 44바이트가된다.
  20(16 + 3 + 1) + 44 = 64 바이트

같이 할당(EMBSTR)과  각각 할당(RAW) 성능 테스트

EMBSTR은 레디스 버전 3.0부터 적용되었습니다.   살바토르는 적용 후 redis-benchmark로 테스트했습니다.   과연 성능이 얼마나 향상되었을까요?

Before:
src : redis-benchmark -q -P 32 -n 1000000 -t set,get -r 1000000
SET: 358294.53 requests per second
GET: 519210.81 requests per second

After EMBSTR patch:
src : redis-benchmark -q -P 32 -n 1000000 -t set,get -r 1000000
SET: 402738.62 requests per second
GET: 606796.12 requests per second


테스트의 문자열은 "xxx"로 3 바이트입니다.
EMBSTR 적용 후 SET은 12%, GET은 17% 처리 속도가 향상되었습니다.

저도 살바토르와 같은 방법으로 테스트해 보겠습니다.

Before(RAW):
src : redis-benchmark -p 6002 -q -P 32 -n 1000000 -t set,get -r 1000000
SET:     992,063.50 requests per second
GET: 1,422,475.12 requests per second

After(EMBSTR):
src : redis-benchmark -p 6002 -q -P 32 -n 1000000 -t set,get -r 1000000
SET: 1,135,073.75 requests per second
GET: 1,538,461.62 requests per second

EMBSTR 적용 후 SET은 14%, GET은 8% 처리 속도가 향상되었습니다.
EMBSTR을 적용하는 문자열 길이는 redis.conf에 있지 않고 object.c 소스에 있습니다.
#define REDIS_ENCODING_EMBSTR_SIZE_LIMIT 39

버전 3.2.0 부터
#define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44

문자열 길이를 39 바이트로 해서 테스트 보았습니다.

Before(RAW):
src : redis-benchmark -d 39 -q -P 32 -n 1000000 -t set,get -r 1000000
SET:     956937.81 requests per second
GET: 1259445.75 requests per second

After(EMBSTR):
src : redis-benchmark -d 39 -q -P 32 -n 1000000 -t set,get -r 1000000
SET: 1088139.25 requests per second
GET: 1550387.62 requests per second

EMBSTR 적용 후 SET은 14%, GET은 23% 처리 속도가 향상되었습니다.
아래는 마지막 테스트 결과를 그래프로 보여주고 있습니다.


세로축은 초당 처리 건수입니다.   GET의 경우 155만 건을 처리합니다.
테스트 서버는 아래와 같습니다.
Redis Server : Version 3.0.6
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

APPEND 명령과 메모리 사용량

Append 명령은 현재 문자열 길이에 추가한 문자열의 길이를 합한 것에 곱하기 2를 해서 메모리를 재 할당합니다.   예를 들면, 현재 문자열 길이가 100이고 추가한 문자열의 길이가 1이면, (100+1)*2 = 202 바이트의 메모리를 새로 할당합니다.   실제 필요한 크기의 2배를 할당합니다.   이렇게 하는 이유는 데이터가 추가로 들어올것에 대비해서 메모리를 여유있게 할당하는 것입니다.   그리고 encoding 방식도 append 후에는 데이터 사이즈에 관계없이 raw로 변경됩니다.   예를 들면, 원래 문자열 길이가 10바이트이고 1바이트를 추가해서 총 11바이트로 embstr(44바이트) 사이즈에 미치지 못하지만 메모리를 재 할당하면서 raw로 변경됩니다.   따라서 append 명령 사용후에는 메모리 사용 측면이나 성능에서 불리해 집니다.


• Append 명령 메모리 사용량 테스트
값의 길이가 100바이트인 데이터를 1백만건 넣고, 추가로 1바이트 문자를 append 명령으로 추가한 후 메모리 사용량을 비교해보았습니다.
1백만건 set 후: used_memory_human:170.35M
1백만건 append 후: used_memory_human:277.24M
논리적으로는 1바이트 * 1백만건이므로 1메가 바이트가 늘어야 되지만, append 후에 107메가 바이트가 늘었다.
메모리 사용량을 줄이려면 append 명령을 사용하지 말고, 기존 값에 새 값을 붙여서 SET 명령을 사용한다.

다음은 테스트 코드이다. >>> test.set100(conn,'key',1,1000000) === STRING : set100 test === Start time: 1474508869.38 End time: 1474509013.53 Elapsed time(sec): 144.146787167 >>> >>> test.append(conn,'key',1,1000000) === STRING : append test === Start time: 1474509074.82 End time: 1474509217.27 Elapsed time(sec): 142.446191072
Python 소스 코드 def set100(conn,key,start_index,end_index): print '=== STRING : set100 test ===' start_time=time.time() print 'Start time:',start_time msg = "X" i = start_index while i <= end_index: conn.set(key+str(i),msg*100) i = i+1 end_time = time.time() print 'End time:', end_time print 'Elapsed time(sec):', end_time-start_time def append(conn,key,start_index,end_index): print '=== STRING : append test ===' start_time=time.time() print 'Start time:',start_time msg = "Y" i = start_index while i <= end_index: conn.append(key+str(i),msg) i = i+1 end_time = time.time() print 'End time:', end_time print 'Elapsed time(sec):', end_time-start_time

SDS(Simple Dynamic Strings) functions

• SDS 문자열 생성과 메모리 해제
• sds sdsnew(char *): 일반 문자열을 SDS 문자열로 변환해서 문자열 포인터를 리턴
sds mystring = sdsnew("Hello World!");
• sds sdsnewlen(char *, size_t len): 길이 지정 가능
char *s = "Hello World!";
sds mystring = sdsnewlen(s, strlen(s);
sds mystring = sdsnewlen(s, 5);
• sds sdsempty(): 빈 SDS 문자열 생성
sds mystring = sdsempty();
mystring = sdscat(mystring, "Hello ");
mystring = sdscat(mystring, "World!");
• sds sdsdup(sds s): SDS 문자열 복제
sds s1 = sdsnew("Hello World!");
sds s2 = sdsdup(s1);
• void sdsfree(sds s): SDS 문자열 메모리 해제
sdsfree(string);
• void sdsclear(sds s): SDS 문자열 메모리는 그대로 두고 길이을 0으로 세팅한다.   할당된 메모리를 재사용할 때 이용한다.
• SDS 문자열 길이
• size_t sdslen(sds s): SDS 문자열 길이를 리턴, sdshdr->len을 바로 리턴하므로 속도가 빠르다.
int i = sdslen(s);
• SDS 문자열 비교
• int sdscmp(const sds s1, const sds s2): SDS 문자열을 비교한다.   길이를 먼저 비교하기 때문에 문자열 길이가 다른 경우에는 비교 속도가 빠르다.
s1 == s2: 결과 영(0)
s1 > s2: 결과 양수(positive)
s1 < s2: 결과 음수(negative)
• SDS 문자열 대,소문자로 변환
• void sdstoupper(sds s): 대문자로 변환
• void sdstolower(sds s): 소문자로 변환
• SDS 문자열 붙임
• sds sdscat(sds s, char *): SDS 문자열과 일반 문자열을 붙인다.
sds mystring = sdsnew("Hello ");
mystring = sdscat(mystring, "World!");
• sds sdscatlen(sds s, char *, size_t len): 길이를 지정해서 문자열을 붙인다.
sds mystring = sdsnew("Hello ");
mystring = sdscatlen(mystring, "World!", 6);
• sds sdscatsds(sds s, const sds t): SDS 문자열과 SDS 문자열을 붙인다.
• SDS 문자열 포멧팅(formatting)
• sds sdscatprintf(sds s, char *fmt, ...): 포멧을 지정한다. printf()와 같은 포멧을 사용할 수 있다.
sds s;
int a = 10, b = 20;
s = sdsnew("The sum is: ");
s = sdscatprintf(s,"%d+%d = %d",a,b,a+b);
• sds sdscatfmt(sds s, char const *fmt, ...): 속도는 sdscatprintf 보다 빠르고 기능은 제한적이다.
사용할 수 있는 포멧
%s - C String
%S - SDS string
%i - signed int
%I - 64 bit signed integer (long long, int64_t)
%u - unsigned int
%U - 64 bit unsigned integer (unsigned long long, uint64_t)
%% - 퍼센트 문자 자신("%")을 출력할 때
• 숫자를 SDS 문자열로 변환
• sds sdsfromlonglong(long long): 숫자를 SDS 문자열로 변환한다.
sds s = sdsfromlonglong(10000);
• SDS 문자열 트림(trim)
• void sdstrim(sds s, char *cset): 지정한 문자로 앞, 뒤 문자를 제거한다.
sds s = sdsnew("       SDS string\n\n    ");
sdstrim(s," \n");
결과: "SDS string"
• SDS 문자열 범위 지정
• void sdsrange(sds s, int start, int end): 시작과 끝 범위를 지정할 수 있다. 음수도 가능하다.
  결과를 다시 s에 저장한다.
sds s = sdsnew("Hello World!");
sdsrange(s,1,4):   => 결과: "ello"
sdsrange(s,1,-1):   => 결과: "ello World!",   end가 -1이면 문자열 끝을 나타낸다.
sdsrange(s,0,-2):   => 결과: "Hello World"
sdsrange(s,-6,-2):   => 결과: "World"
• SDS 문자열 복사
• sds sdscpy(sds s, char *): 문자열 복사
s = sdsnew("Hello World!");
s = sdscpy(s,"Hello Redis!");
결과: "Hello Redis!"
• sds sdscpylen(sds s, char *, size_t len): 길이를 지정해서 문자열 복사
s = sdsnew("Hello World!");
s = sdscpylen(s,"Hello Redis!", 12);
결과: "Hello Redis!"
• SDS 문자열을 주어진 문자로 대치
• sds sdsmapchars(sds s, const char *from, const char *to, size_t setlen)
sds s = sdsnew("Hello");
s = sdsmapchars(s, "ho", "xy", 2);
결과: "xelly"
• 특수문자 또는 프린트 불가능한 문자를 프린트 가능한 문자로 바꾸어 준다.
• sds sdscatrepr(sds s, char *, size_t len): 특수 문자를 프린트 가능한 문자로 변경
sds s1 = sdsnew("abcd");
sds s2 = sdsempty();
s[1] = 1;
s[2] = 2;
s[3] = '\n';
s2 = sdscatrepr(s2,s1,sdslen(s1));
결과: "a\x01\x02\n"
• SDS 문자열을 특정 문자 또는 특정 문자열로 구분해 준다.
• sds *sdssplitlen(const char *s, int len, const char *sep, int seplen, int *count);   문자열 구분
• void sdsfreesplitres(sds *tokens, int count);   구분 문자열 메모리 해제
• 공백 문자로 분리한 경우
sds *tokens;
int count, j;
sds line = sdsnew("Hello World!");
tokens = sdssplitlen(line,sdslen(line)," ",1,&count);
for (j = 0; j < count; j++)
  printf("%s\n", tokens[j]);
sdsfreesplitres(tokens,count);

output> Hello
output> World!
• "::" 문자열로 분리한 경우
sds *tokens;
int count, j;
sds line = sdsnew("Hello::World!");
tokens = sdssplitlen(line,sdslen(line),"::",2,&count);
for (j = 0; j < count; j++)
  printf("%s\n", tokens[j]);
sdsfreesplitres(tokens,count);

output> Hello
output> World!
• 명령행을 단어 단위로 구분해 준다.
• sds *sdssplitargs(const char *line, int *argc)
명령행: call "Sabrina" and "Mark Smith\n"
구분된 결과:
"call"
"Sabrina"
"and"
"Mark Smith\n"
• 분리된 문자열을 이어 붙여준다.
• sds sdsjoin(char **argv, int argc, char *sep): 일반 문자열 이어 붙이기,   내부적으로 sdscat()을 사용한다.
char *tokens[3] = {"foo","bar","zap"};
sds s = sdsjoin(tokens,3,"|",1);
결과: foo|bar|zap
• sds sdsjoinsds(sds *argv, int argc, const char *sep, size_t seplen): SDS 문자열 이어 붙이기,   내부적으로 sdscatsds()를 사용한다.

Low level functions

• sds sdsMakeRoomFor(sds s, size_t addlen): 메모리를 추가로 확보한다.   추가 요구량(addlen) 이상으로 메모리가 이미 확보되어 있다면 바로 리턴한다.   부족하면 현재 문자열 길이(len)과 추가 요구량(addlen)을 더한 것이 1메가 바이트보다 적으면 2배를 해서 메모리를 할당하고, 1메가 바이트 이상이면 현재 문자열 길이(len) + 추가 요구량(addlen) + 1메가 바이트의 합 만큼 메모리를 할당한다.
  sdscatlen(), sdscpylen() 등 에서 사용된다.
• sds sdsgrowzero(sds s, size_t len): 주어진 길이 만큼 메모리를 확보하고 추가된 메모리를 '\0'으로 채운다.   예를 들면, 현재 문자열이 20 바이트인데, len이 30이라면 10 바이트 메모리를 더 확보하고 이 10 바이트에 '\0'를 채워넣는다.
• void sdsIncrLen(sds s, int incr): 길이(len) 필드의 값을 incr 만큼 증가 시킨다.   이것은 SDS 함수를 사용하지 않고 문자열을 늘렸을 경우, 정상 길이를 세팅하기 위해 사용한다.
• sds sdsRemoveFreeSpace(sds s): 사용되지 않는 메모리를 해제한다.
• size_t sdsAllocSize(sds s): SDS 문자열에 할당된 총 메모리 바이트수를 리턴한다.
  Total bytes = SDS header + string + free space + null term