Server

Redis STRINGS Data Structure

Redis Internel Course	Redis Technical Support	Redis Enterprise Server

Redis STRINGS Data Structure

내부 데이터 구조

중요한 이유는 메모리 절약과 성능 향상

정수는 공유 정수와 독립 정수로 구분합니다. 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 바이트

디스트와 메모리의 속도 차이가 큰 것처럼, 메인 메모리와 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) 성능 테스트

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

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% 처리 속도가 향상되었습니다.

#define REDIS_ENCODING_EMBSTR_SIZE_LIMIT 39

버전 3.2.0 부터

#define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44

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% 처리 속도가 향상되었습니다.

redis STRING-EMBSTR vs RAW performance test

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 명령 메모리 사용량 테스트

1백만건 set 후: used_memory_human:170.35M
1백만건 append 후: used_memory_human:277.24M

>>> 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

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

<< Command Process	ZIP List of LISTS >>

Email 답글이 올라오면 이메일로 알려드리겠습니다.