English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية
서론
압축된 목록(ziplist)은 일련의 특수 인코딩된 메모리 블록으로 구성된 목록입니다. 이는 Redis의 데이터 저장 최적화에 매우 중요한 역할을 합니다. 이 기사에서는 Redis에서 많이 사용되는 하나의 데이터 구조인 압축된 링크드 리스트 ziplist를 요약합니다. 이 데이터 구조는 Redis에서 거의 어디에나 존재하며, 링크드 리스트 외에도 많은 다른 데이터 구조에서 이를 중간 단계로 사용합니다. 예를 들어, 이전 기사에서 언급한 SortedSet과 같습니다. 더 이상 말하지 않고, 자세한 소개를 보겠습니다.
1. 압축된 링크드 리스트 ziplist 데이터 구조 개요
먼저 ziplist의 구조를 전반적으로 보면, 다음과 같습니다:
압축된 링크드 리스트 ziplist 구조도
필드가 많고 바이트 크기도 다르지만, 이것이 바로 압축된 링크드 리스트의 핵심입니다. 이를 차례대로 요약해 보겠습니다.
| 필드 | 의 의미 |
|---|---|
| zlbytes | 이 필드는 압축된 링크드 리스트의 첫 번째 필드로, 비소수 정형이며, 한 바이트를 차지합니다.4바이트를 차지합니다. 전체 압축된 링크드 리스트가 차지하는 바이트 수(자신을 포함)를 나타냅니다. |
| zltail | 비소수 정형, 한 바이트를 차지합니다.4바이트를 차지합니다. 압축된 링크드 리스트의 헤드에서 마지막 entry(zlend 요소가 아닌)까지의 오프셋을 저장합니다. 링크드 리스트의 끝으로 빠르게 이동하는 상황에서 사용됩니다. |
| zllen | 비소수 정형, 한 바이트를 차지합니다.2바이트입니다. 압축된 링크드 리스트에 포함된 entry 총 수를 저장합니다. |
| zlend | 특수 entry는 압축된 링크드 리스트의 끝을 나타냅니다. 한 바이트를 차지하고, 값은 항상255입니다. |
ziplist의 머리와 尾을 요약하면, 다음은 중요한 entry 필드의 요약입니다.
일반적으로 entry는 prevlen, encoding, entry로 구성됩니다.-data 필드로 구성되어 있지만, entry가 매우 작은 정수일 때는 인코딩을 통해 entry를 생략할 수 있습니다.-data 필드로 구성되어 있지만, entry가 매우 작은 정수일 때는 인코딩을 통해 entry를 생략할 수 있습니다.
처음에는 필드 prevlen: 이전 entry의 길이를 나타내며, 두 가지 인코딩 방식이 있습니다.
그런 다음 필드 encoding: 현재 요소 내용에 따라 다른 인코딩 방식을 사용합니다. 예를 들어:
1、요소 내용이 문자열이면, encoding의 값은 다음과 같습니다：
00xx xxxx ：00로 시작하면, 해당 문자열의 길이는6비트를 나타냅니다.
01xx xxxx | xxxx xxxx ：01처음에 오는 바이트는 문자열 길이가14비트를 나타냅니다. 이14비트는 리틀 엔딩 방식으로 저장됩니다.
1000 0000 | xxxx xxxx | xxxx xxxx | xxxx xxxx | xxxx xxxx ：10처음에 오는 바이트는 이후 네 바이트가 문자열 길이를 나타냅니다.32비트는 리틀 엔딩 방식으로 저장됩니다.
2、요소 내용이 숫자이면, encoding의 값은 다음과 같습니다：
1100 0000：숫자가 사용되는 바이트 이후2바이트.
1101 0000：숫자가 사용되는 바이트 이후4바이트.
1110 0000：숫자가 사용되는 바이트 이후8바이트.
1111 0000 : 숫자가 사용되는 바이트 이후3바이트.
1111 1110 : 숫자가 사용되는 바이트 이후1바이트.
1111 1111 : 압축 링크 목록의 마지막 요소(특수 인코딩)
1111 xxxx : 마지막 네 비트만 사용4비트는 0~12의 정수를 나타냅니다. 00001110과1111세 가지가 이미 사용되었으므로, 여기서 xxxx 네 비트는 000으로 표현될 수 있습니다.1로 사용하도록 규정합니다.1101，10진수로 변환하면 숫자1로 사용하도록 규정합니다.13，하지만 redis는 이를 0~12，따라서 이 인코딩을 만나면, 마지막 네 비트를 꺼내서 뺄 필요가 있습니다.1을 통해 올바른 값을 얻을 수 있습니다.
마지막은 필드 entry-data：요소의 값이 문자열이면, 요소 자체의 값을 저장합니다. 요소의 값이 매우 작은 수라면(위 인코딩 규칙에 따르면 0~12），그런 경우 해당 필드가 없습니다.
압축 링크 목록의 인코딩은 매우 복잡하지만, 이는 실제로 이 데이터 구조의 핵심입니다. 예제를 하나 보겠습니다:
주의:이 예제는 redis 소스 코드에서 언급된 것입니다
//요소2，5으로 구성된 압축 링크 목록 [0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff] | | | | | | zlbytes zltail entries "2" "5" end //문자열 "Hello World"를 인코딩한 내용 [02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64]
위는 16진수로 표현된 일부입니다2，5두 요소로 구성된 압축 링크 목록.
이제 우리는 이 콤프레스드 링크드 리스트의 마지막에 문자열 요소 'Hello World'를 추가합니다. 먼저 이 문자열을 어떻게 인코딩할지 보겠습니다. 약定的 인코딩 규칙에 따르면, 먼저 이전 요소의 길이를 바이트로 나타내야 합니다. 여기서 이전 요소는5입니다. 따라서 전체로서 두 바이트를 차지합니다. 따라서 먼저 이전 요소의 길이를 나타내는 바이트를 하나 사용합니다.2문자열의 인코딩을 다음은 문자열의 인코딩 규칙에 따라 사용합니다.11입니다.1011로 변환됩니다(공백도 포함됩니다). 이를 이진수로 변환하면 1011표시되며, 십육진수로 변환하면 0b입니다. 그런 다음 우리 문자열 본체의 ASCII 코드를 추가하여, 이 문자열의 인코딩을 결정합니다: [02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64]。
이제 전체 콤프레스드 링크드 리스트는 다음과 같이 됩니다:
[0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [02 0b 48 65 6c 6c 6f 20 57 6f 72 6c 64] [ff] | | | | | | | zlbytes zltail entries "2" "5" "Hello World" end
이二章: 콤프레스드 링크드 리스트 ziplist 명령 소스 코드 분석
위의 인코딩 규칙을 이해한 후, 우리는 콤프레스드 링크드 리스트 ziplist의 일부 작업 소스 코드를 보겠습니다. 이 글은 콤프레스드 링크드 리스트를 생성, 요소 추가, 요소 제거, 요소 검색 네 가지 작업을 통해 콤프레스드 링크드 리스트의 기본 원리를 요약합니다.
먼저 생성부터 시작해보겠습니다:
//zlbytes, zltail 및 zllen으로 구성된 콤프레스드 링크드 리스트의 헤더 크기를 정의합니다
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))
//콤프레스드 링크드 리스트를 생성하고 해당 링크드 리스트를 가리키는 포인터를 반환합니다
unsigned char *ziplistNew(void) {
//그 이유는+1끝 요소가 하나의 바이트를 차지하기 때문에, 이것이 압축 링크 목록의 최소 크기입니다
unsigned int bytes = ZIPLIST_HEADER_SIZE+1;
//메모리 할당
unsigned char *zl = zmalloc(bytes);
//링크 목록 크기 설정
ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
//마지막 요소의 위치 설정
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
//요소 개수 설정
ZIPLIST_LENGTH(zl) = 0;
//끝 요소 설정(위는 공간을 요청한 것에 불과합니다)
zl[bytes-1] = ZIP_END;
return zl;
}
압축 링크 목록을 생성하는 로직은 매우 간단합니다. 먼저, 헤더와 테이블의 마지막 요소를 포함한 고정 크기의 공간을 요청하고, 링크 목록 컨텍스트를 초기화합니다.
생성과 비교해보면, 요소를 추가하는 코드는 매우 길다. 이해하기 쉽게 하기 위해, 코드를 볼 전에 먼저 요소 추가 로직을 정리해 봅니다.
위 세 단계는 핵심 단계입니다. 나머지는 테이블의 마지막 요소 위치를 업데이트하거나, 링크 목록 요소 개수를 수정하는 등의 작업이 있습니다. 물론, 압축 링크 목록이 배열에 기반하고 있기 때문에, 요소를 삽입하거나 제거할 때는 반드시 메모리 복사가 필요합니다.
위의 단계를 요약한 후, 우리는 단계별로 원본 코드를 분석 시작합니다. 매우 길다. 차근차근 보겠습니다:
//네 가지 매개변수는 순차적으로 다음과 같습니다: 압축 링크 목록, 삽입 위치(새 요소가 p 요소 뒤에 삽입됨), 요소 값, 요소 길이
unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
//현재 링크 목록의 길이를 저장하는 곳입니다
size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen;
unsigned int prevlensize, prevlen = 0;
size_t offset;
int nextdiff = 0;
unsigned char encoding = 0;
long long value = 123456789;
zlentry tail;
//1. 이 로직의 목적은 전置 요소의 길이를 가져오는 것입니다
if (p[0] != ZIP_END) {
//만약 삽입 위치의 요소가 끝 요소가 아니라면, 해당 요소의 길이를 가져옵니다
//이후 사용하기 편리하게 분할하여, prevlensize는 encoding 필드의 길이를 저장하고, prevlen은 요소 자체의 길이를 저장합니다.
ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
} else {
//삽입 위치의 요소가 끝 요소라면, 새로운 요소를 링크드 리스트의 마지막 요소에 삽입해야 합니다.
//링크드 리스트의 마지막 요소를 가져옵니다. (주의: 마지막 요소는 끝 요소가 아닙니다.)
unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);
if (ptail[0] != ZIP_END) {
//만약 마지막 요소가 끝 요소가 아니라면, 이 요소가 새로운 요소의 이전 요소로, 이 요소의 길이를 가져옵니다.
prevlen = zipRawEntryLength(ptail);
}
//그렇지 않으면 링크드 리스트에 아무도 없다는 것을 의미합니다. 즉, 새로운 요소의 이전 요소의 길이가 0입니다.
}
//2. 새로운 요소를 인코딩하여 새로운 요소의 총 크기를 얻습니다.
if (zipTryEncoding(s,slen,&value,&encoding)) {
//숫자라면 숫자로 인코딩합니다.
reqlen = zipIntSize(encoding);
} else {
//요소 길이는 문자열 길이입니다.
reqlen = slen;
}
//새로운 요소의 총 길이는 값의 길이와 프리빗 요소와 encoding 요소의 길이를 더 합니다.
reqlen += zipStorePrevEntryLength(NULL,prevlen);
reqlen += zipStoreEntryEncoding(NULL,encoding,slen);
//삽입 위치가 링크드 리스트의 마지막 요소가 아니라면, 새로운 요소의 다음 요소의 prevlen 필드를 판단해야 합니다.
//위의 인코딩 규칙에 따라, 이 필드가 확장이 필요할 수 있습니다.
int forcelarge = 0;
nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
if (nextdiff == -4 && reqlen < 4) {}}
nextdiff = 0;
forcelarge = 1;
}
//새로 계산된 배열 크기에 맞게 확장합니다. 새로운 배열의 주소가 변경될 수 있으므로, 이곳에서 이전 오프셋을 기록합니다.
offset = p-zl;
zl = ziplistResize(zl,curlen+reqlen+nextdiff);
//새로운 배열에 삽입 위치를 계산합니다.
p = zl+offset;
//만약 새로 추가된 요소가 링크드 리스트의 마지막 요소가 아니라면
if (p[0] != ZIP_END) {
//새로운 요소와 그 다음 요소를 새로운 배열에 복사합니다.,-1위의 요소
memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);
//새 요소의 후속 요소의 prevlen 필드
if (forcelarge)
zipStorePrevEntryLengthLarge(p+reqlen,reqlen);
else
zipStorePrevEntryLength(p+reqlen,reqlen);
//마지막 요소의 오프셋 값을 업데이트합니다
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);
//새 요소의 후속 요소가 하나 이상이 있을 때, 새로운 끝 요소의 오프셋 값은 nextdiff를 더해야 합니다
zipEntry(p+reqlen, &tail);
if (p[reqlen+tail.headersize+tail.len] != ZIP_END) {
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
}
} else {
//새 요소가 연결리스트의 끝에 삽입되면, 끝 부분의 오프셋 값을 업데이트합니다
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);
}
//nextdiff != 0은 후속 요소의 길이가 변경되었음을 의미하므로, 후속 요소의 후속 요소를 캐시드 업데이트해야 합니다
if (nextdiff != 0) {
offset = p-zl;
zl = __ziplistCascadeUpdate(zl,p+reqlen);
p = zl+offset;
}
//새 요소를 연결리스트에 기록합니다
p += zipStorePrevEntryLength(p,prevlen);
p += zipStoreEntryEncoding(p,encoding,slen);
if (ZIP_IS_STR(encoding)) {
memcpy(p,s,slen);
} else {
zipSaveInteger(p,value,encoding);
}
//압축 연결리스트에 저장된 요소 수+1
ZIPLIST_INCR_LENGTH(zl,1;
return zl;
}
삽입 요소의 로직을 분석한 후, 깊은 숨을 쉬었습니다. 정말 길었고, 세부 사항도 많았습니다.
제거 요소의 과정을 다음에 보겠습니다. 추가와 비교하여, 제거는 상대적으로 간단합니다. 현재 요소를 비우고 나면, 후속 요소를 하나씩 복사해 올려야 합니다(이것이 배열과 연결리스트 두 데이터 구조의 차이점입니다), 그리고 필요한 경우 캐시드 업데이트를 주의하세요. 코드를 보겠습니다:
//매개변수는 차례로:zip 연결리스트, 제거할 요소의 초기 위치, 제거할 요소의 개수
unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsigned int num) {
unsigned int i, totlen, deleted = 0;
size_t offset;
int nextdiff = 0;
zlentry first, tail;
//p를 가리키는 요소를 first에 저장합니다
zipEntry(p, &first);
for (i = 0; p[0] != ZIP_END && i < num; i++) {}}
//삭제된 총 길이를 계산
p += zipRawEntryLength(p);
//실제로 삭제된 요소의 개수를 계산
deleted++;
}
//삭제해야 하는 요소의 바이트 수
totlen = p-first.p;
if (totlen > 0) {
if (p[0] != ZIP_END) {
//요소 크기가 변경되었는지�断
nextdiff = zipPrevLenByteDiff(p, first.prevrawlen);
//삭제된 요소 이후의 요소의 prevlen 필드 수정
p -= nextdiff;
zipStorePrevEntryLength(p, first.prevrawlen);
//끝 요소의 오프셋 업데이트
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen);
//삭제된 요소의 후속 요소가 하나 이상이면, 새로운 마지막 요소의 오프셋에 nextdiff를 추가해야 합니다
zipEntry(p, &tail);
if (p[tail.headersize+tail.len] != ZIP_END) {
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
}
//뒤에 남은 요소를 앞으로 이동
memmove(first.p, p,
intrev32ifbe(ZIPLIST_BYTES(zl))-(p-zl)-1;
} else {
//직접 링크 목록의 마지막에 삭제하여 메모리 복사가 필요하지 않으며, 마지막 요소의 오프셋만 수정하면 됩니다
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe((first.p-zl)-first.prevrawlen);
}
//배열 크기 조정
offset = first.p-zl;
zl = ziplistResize(zl, intrev32ifbe(ZIPLIST_BYTES(zl))-totlen+nextdiff);
//리스트 요소 개수 수정
ZIPLIST_INCR_LENGTH(zl,-deleted);
p = zl+offset;
//nextdiff != 0은 요소 크기가 변경되었음을 의미하고, 캐스케이드 업데이트가 필요합니다
if (nextdiff != 0)
zl = __ziplistCascadeUpdate(zl, p);
}
return zl;
}
마지막으로 요소 검색 작업을 보겠습니다:
//파라미터는 차례로:zip_list, 찾고자 하는 요소의 값, 찾고자 하는 요소의 길이, 비교 사이에 건너뛰는 요소 개수
unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int vlen, unsigned int skip) {
int skipcnt = 0;
unsigned char vencoding = 0;
long long vll = 0;
//끝 요소에 도달하지 않았다면 계속 반복합니다
while (p[0] != ZIP_END) {
unsigned int prevlensize, encoding, lensize, len;
unsigned char *q;
//링크드 리스트 현재 요소의 prevlen 필드를 쿼리합니다
ZIP_DECODE_PREVLENSIZE(p, prevlensize);
//링크드 리스트 현재 요소의 encoding 필드를 쿼리합니다
ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
q = p + prevlensize + lensize;
//비교해야 할 요소 위치에 도달했습니다
if (skipcnt == 0) {
//링크드 리스트의 현재 요소가 문자열인 경우
if (ZIP_IS_STR(encoding)) {
//찾으려는 문자열과 비교합니다
if (len == vlen && memcmp(q, vstr, vlen) == 0) {
//일치 성공하면 찾으려는 요소의 포인터
return p;
}
} else {
//현재 요소가 숫자이고 vencoding이 0인 경우
if (vencoding == 0) {
//찾으려는 값을 숫자로 encoding 시도합니다
if (!zipTryEncoding(vstr, vlen, &vll, &vencoding)) {
//encoding 실패한 경우, 찾으려는 요소가 숫자가 아니라는 의미입니다
//그런 다음 vencoding을 최대 값으로 설정하여 표시 역할을 합니다
//따라서 이후로 찾으려는 값을 숫자로 encoding 시도하지 않아도 됩니다
vencoding = UCHAR_MAX;
}
assert(vencoding);
}
//vencoding != UCHAR_MAX 인 경우, 찾으려는 요소가 성공적으로 숫자로编码되었습니다
if (vencoding != UCHAR_MAX) {
//숫자로 현재 링크드 리스트 요소를 꺼내십시오
long long ll = zipLoadInteger(q, encoding);
if (ll == vll) {
//두 숫자가 같으면 요소 포인터를 반환합니다;
return p;
}
}
}
//필요한 건너뜀 요소 개수를 재설정합니다;
skipcnt = skip;
} else {
//요소를 건너뜁니다;
skipcnt;--;
}
//다음 요소를 탐색합니다;
p = q; + len;
}
//전체 링크 구조를 탐색했지만 요소를 찾지 못했습니다.
return NULL;
}
이제 줄여진 링크 구조의 생성, 추가, 삭제, 검색 네 가지 기본 작업 원리를 요약했습니다.
제3장: 줄여진 링크 구조 ziplist 데이터 구조 정리
ziplist가 redis에서 널리 사용되고 있으며, 이는 redis에서 가장 독특한 데이터 구조 중 하나입니다. 이 데이터 구조의 핵심은 실제로는 첫 번째 부분에서 요약한编码 규칙입니다. 이 부분을 먼저 이해한 후, 그 이후의 소스 코드를 간단히 보고 이해를 돕을 수 있습니다.
소스 코드 부분은 진짜 길어서 조금 번거롭습니다. 실제로 읽는 동안 머리가 아팠습니다. 소스 코드에 관심이 있다면, 제 방법을 따라 먼저 특정 작업(예: 위에서 언급한 요소 추가)을 수행해야 할 일을 정리한 후에 코드를 보면 더 이해하기 쉬울 것입니다.
마지막으로 작은 질문을 남겨 둡니다. redis의 ziplist가内存利用率如此之高이지만, 왜 일반적인 링크 구조를 사용자에게 제공해야 하는지요?
이 문제에 대한 표준 답변이 없습니다. 각자의 의견이 다릅니다.
정리
이 글의 모든 내용이 끝납니다. 이 글의 내용이 여러분의 학습이나 업무에 도움이 되길 바랍니다. 의문이 있으면 댓글을 남겨 주세요. 감사합니다.呐喊 튜토리얼에 대한 여러분의 지원에 감사합니다.
언급: 본 내용은 인터넷에서 가져왔으며, 저작권자가 모두 소유하고 있으며, 인터넷 사용자가 자발적으로 기여하고 업로드한 내용입니다. 이 웹사이트는 소유권을 가지지 않으며, 인공 편집을하지 않았으며, 관련 법적 책임도 부담하지 않습니다. 저작권 문제가 의심되는 내용을 발견하면, notice#w로 이메일을 보내 주시기 바랍니다.3codebox.com（메일을 보내면, #을 @으로 변경하십시오. 신고를 해 주시고, 관련 증거를 제공하십시오. 사실이 확인되면,本站은 즉시 의심되는 저작권 내용을 삭제합니다.）