Redis Listpack

기본 데이터 구조

Listpack은 Ziplist의 단점을 보완하기 위해서 나왔다. Ziplist의 단점이란, 데이터 변경(증가) 시 prevlen이 1에서 5로 바이트로 연속적으로 증가되어 짚리스트 안의 모든 엔트리를 수정해야 되는 경우가 발생하는 것을 말한다.
Listpack은 이 단점을 개선해서 prevlen 필드를 없애고 순방향, 역방향 탐색이 가능한 데이터 구조이다. 스트림(Stream)에서 사용된다.

Listpack

Header (6 bytes)		Data			end-byte
tot-bytes	num-entries	entry-1	...	entry-N	FF
4 bytes	2 bytes	?	...	?	1 byte

Ziplist

Header (10 bytes)			Data			zlend
zlbytes	zltail last entry ptr	zllen num-entries	entry-1	...	entry-N	FF
4 bytes	4 bytes	2 bytes	?	...	?	1 byte

Listpack Entry

encoding	value	tot-len
1~4 bytes	0~4GB	1~5 bytes

Ziplist Entry

prevlen	itself len	value
1,5 bytes	1,2,5 bytes	0~4GB

정수 Integer: 정수 데이터 포함 길이

• 1 byte(6 bits): 0 ~ 127
• 2 byte(13 bits): -4096 ~ +4095
• 3 byte(16 bits): -32,768 ~ +32,767
• 4 byte(24 bits): -8,388,608 ~ +8,388,607
• 5 byte(32 bits): -2,147,483,648 ~ +2,147,483,647
• 7 byte(64 bits): -9,223,372,036,854,775,808 ~ +9,223,372,036,854,775,807

문자열 String: encoding 바이트만, 실수는 문자열로 저장

• 1 byte(6 bits): 0 ~ 63
• 2 byte(12 bits): 64 ~ 4095
• 5 byte(32 bits): 4096 ~ 4,294,967,296

API

• lpInsert(): 저장, lpAppend(), lpDelete()에서 이 function을 사용한다.
• lpAppend(): 추가
• lpDelete(): 삭제
• lpFirst(): 처음
• lpLast(): 마지막
• lpNext(): 다음
• lpPrev(): 이전
• lpSeek(): 찾기

출처: https://github.com/antirez/listpack/blob/master/listpack.md

Since the early stage of Redis development, to optimize for low memory usage was an important concern. Scalable data structures are often composed of nodes (heap allocated chunks of memory) containing references (pointers) to other nodes. This representation, while able to scale well with the number of elements in a data structure, is extremely wasteful: meta data easily account for 50% of the space in memory if the average element size is small. However when a data structure is used to hold a very small number of elements, it is possible to switch to a different, more compact representation. Because the number of elements for which the alternating representation is used is constant and small, the time complexity of the data structure is the same. Moreover, the constant times of working with such compact representation of a small number of elements, even when a full scan of the elements is needed in order to access or modify the data structure, are well compensated by the cache locality of sequentially accessing a linear array of bytes. This allows to save memory, while transparently switching to a linked representation once a given maximum size is reached.

Redis 개발 초기 단계부터 낮은 메모리 사용을 최적화하는 것이 중요한 관심사였습니다. 확장 가능한 데이터 구조는 종종 다른 노드에 대한 참조(포인터)를 포함하는 노드(힙 할당 메모리)로 구성됩니다. 이 표현(representation)은 데이터 구조의 요소 수에 맞게 확장 할 수 있지만 매우 낭비입니다. 평균 요소 크기가 작으면 메타 데이터가 메모리 공간의 50%를 쉽게 차지합니다. 그러나 데이터 구조를 사용하여 매우 적은 수의 요소를 보유하는 경우보다 콤팩트한 표현으로 전환할 수 있습니다. 대체 표현이 사용되는 요소의 수는 일정하고 작기 때문에 데이터 구조의 시간 복잡도는 동일합니다. 게다가, 데이터 구조에 액세스하거나 수정하기 위해 요소의 전체 스캔이 필요한 경우에도 적은 수의 요소를 콤팩트하게 표현하는 일정한 시간은 바이트 선형 배열에 순차적으로 액세스하는 캐시 위치에 의해 잘 보상됩니다. 이를 통해 주어진 최대 크기에 도달하면 연결된 표현으로 투명하게 전환하면서 메모리를 절약할 수 있습니다.

Traditionally Redis, as compact representation of hashes, lists, and sorted sets having few elements, used a data structure called ziplist. A ziplist is basically a single heap allocated chunk of memory containing a list of string elements. It can be used to represent maps by alternating keys and values, or ordered lists of elements. The ziplist data structure served us very well for years, however recently an user signaled a crash in the context of accessing ziplists. The bug happened with error corrected memory modules of the latest generation, and RDB files are protected by a CRC64 checksum. So we started an investigation in order to discover for bugs in the ziplist.c file.

전통적으로 레디스는 Hash, List, ZSet에서 데이터 수가 적을 경우에는 콤펙트한 짚리스트(ziplist)라는 데이터 구조체를 사용합니다. ziplist는 기본적으로 문자열 요소 목록을 포함하는 단일 힙 할당 메모리입니다. 키와 값을 번갈아 표시(hash)하거나 순서가 지정된 요소 목록을 사용하여 맵(list)을 나타내는데 사용할 수 있습니다. Ziplist 데이터 구조는 수년 동안 우리에게 매우 도움이되었지만 최근에는 사용자가 ziplist에 액세스할 때 충돌이 발생했음을 표시했습니다. 이 버그는 최신 세대의 오류 수정 메모리 모듈에서 발생했으며 RDB 파일은 CRC64 체크섬으로 보호됩니다. 그래서 ziplist.c 파일에서 버그를 발견하기 위해 조사를 시작했습니다 .

After weeks of work, I (Salvatore) analytically discovered a bug that is not related to the user crash. Oran Agra and Yuval Inbar, that are also contributors of this specification, joined the effort of auditing the code. Salvatore also wrote several fuzz testers modeling the layout of the user data. Even if the fuzzing techniques used could easily find the very complex to replicate bug that was found analytically, no crash was ever seen using the Hash data type, the one used during the crash reported by the user.

몇 주 동안 작업한 결과, 나(Salvatore)는 사용자 충돌과 관련이 없는 버그를 분석적으로 발견했습니다. 이 기여자(contributor)인 Oran Agra와 Yuval Inbar는 코드 감사 노력에 동참했습니다. Salvatore는 또한 사용자 데이터의 레이아웃을 모델링하는 여러 퍼즈(fuzz) 테스터를 작성했습니다. 사용된 퍼징(fuzzing) 기술이 분석적으로 발견된 버그를 복제하기 매우 복잡한 것을 쉽게 찾을 수 있더라도 사용자가 보고한 충돌중에 사용된 해시 데이터 유형을 사용하여 충돌이 발견되지 않았습니다.

Even if apparently ziplist.c does not contain bugs, or at least we cannot find them, nor there are often reports of crashes related to a potential bug in this part of the code, during the review all the programmers involved agreed that the ziplist code was so complex and had such non trivial side effects that it was a wise idea to switch to something else. The reason why it was hard to audit was that a ziplist has the following layout:

분명히 ziplist.c는 버그를 포함하지 않거나 최소한 버그를 찾을 수 없거나, 코드의 이 부분에서 잠재적인 버그와 관련된 충돌이 보고되는 경우가 많지만, 검토하는 동안 관련된 모든 프로그래머는 ziplist 코드가 너무 복잡하다는데 동의했습니다. 사소한 부작용이 있어서 다른 것으로 바꾸는 것이 현명한 생각이었습니다. 감사(audit)가 어려운 이유는 ziplist의 레이아웃이 다음과 같기 때문입니다.
However it is important for Redis that a ziplist can be accessed backward, from the latest element to the first, in order to model commands such as LRANGE in a way to avoid scanning the whole ziplist to just fetch a few elements from the tail. So each entry, was actually composed of the following two parts:
그러나 Redis에게는 LRANGE 전체 요소를 스캔하여 꼬리에서 몇 개의 요소만 가져오는 것을 피하는 방법과 같은 명령을 모델링하기 위해 최신 요소에서 첫 번째 요소까지 ziplist에 뒤로 액세스할 수 있어야합니다. 따라서 각 항목은 실제로 다음 두 부분으로 구성되었습니다.
The previous entry length could change in size from 1 to 5 bytes, in order to use little space to encode small previous entries lengths. However inserting or deleting elements in the middle, while using this particular encoding, may have a cascading effect, where the previous length and even the number of bytes the previous length is encoded, may change and may cascade to the next elements. This was the main source of complexity of ziplist. However other alternatives implementations exist that can prevent this problem and only use local information for each entry.

작은 공간을 사용하여 작은 이전 항목 길이를 인코딩하기 위해 이전 항목 길이의 크기가 1에서 5 바이트로 변경될 수 있습니다. 그러나 중간에 요소를 삽입하거나 삭제하면 이 특정 인코딩을 사용하는 경우 계단식 효과가 있을 수 있으며, 이 경우 이전 길이와 심지어 이전 길이가 인코딩된 바이트 수는 변경되어 다음 요소에 종속될 수 있습니다 . 이것이 ziplist의 복잡성의 주요 원인이었습니다. 그러나 이 문제점을 방지하고 각 항목에 대해 로컬 정보만 사용하는 다른 대체 구현이 존재합니다.

Listpack takes the good ideas of ziplists and reimplement it in order to create a more compact, faster to parse implementation, that maps directly to simple to audit and understand code. Moreover the single entries representation in listpack were redesigned in order to better exploit the kind of data Redis users normally store in lists and hashes. This document describes the new format.

Listpack은 ziplists의 좋은 아이디어를 취해 재 구현하여 보다 간결하고 구문 분석이 빠른 구현을 작성하고 코드를 감사하고 이해하기 위해 단순하게 직접 맵핑합니다. 또한 listpack의 단일 항목 표현은 Redis 사용자가 일반적으로 목록 및 해시에 저장하는 데이터 종류를 더 잘 활용하기 위해 재 설계되었습니다. 이 문서는 새로운 형식을 설명합니다.

A listpack is encoded into a single linear chunk of memory. It has a fixed length header of six bytes (instead of ten bytes of ziplist, since we no longer need a pointer to the start of the last element). The header is followed by the listpack elements. In theory the data structure does not need any terminator, however for certain concerns, a special entry marking the end of the listpack is provided, in the form of a single byte with value FF (255). The main advantages of the terminator are the ability to scan the listpack without holding (and comparing at each iteration) the address of the end of the listpack, and to recognize easily if a listpack is well formed or truncated. These advantages are, in the idea of the writer, worth the additional byte needed in the representation.

Listpack은 단일 선형 청크 메모리로 인코딩됩니다. 더 이상 마지막 요소의 시작에 대한 포인터(zltail)가 필요하지 않기 때문에 10 바이트의 ziplist 대신 6 바이트의 고정 길이 헤더가 있습니다. 헤더 다음에는 listpack 요소(entry)가 옵니다. 이론적으로 데이터 구조에는 터미네이터가 필요하지 않지만 특정 문제의 경우 값이 FF(255)인 단일 바이트 형식으로 listpack의 끝을 표시하는 특수 항목이 제공됩니다. 터미네이터의 주요 장점은 listpack 끝의 주소를 유지하지 않고 listpack을 스캔하고 listpack이 잘 형성되거나 잘린 경우 쉽게 인식할 수 있다는 것입니다. 이러한 장점은 작가의 아이디어에서 표현에 필요한 추가 바이트 가치가 있습니다.
The six byte header, composed of the tot-bytes and num-elements fields is encoded in the following way:
tot-bytes 및 num-elements 필드로 구성된 6 바이트 헤더는 다음과 같은 방식으로 인코딩됩니다.

• tot-bytes: 32 bit unsigned integer holding the total amount of bytes representing the listpack. Including the header itself and the terminator. This basically is the total size of the allocation needed to hold the listpack and allows to jump at the end in order to scan the listpack in reverse order, from the last to the first element, when needed.
  Listpack을 나타내는 총 바이트 수를 보유하는 32 비트 부호없는 정수. 헤더 자체와 종결자를 포함합니다. 이것은 기본적으로 listpack을 유지하는데 필요한 할당의 총 크기이며, 필요할 때 마지막에서 첫 번째 요소까지 listpack을 역순으로 스캔하기 위해 끝에서 점프할 수 있습니다.
• num-elements: 16 bit unsigned integer holding the total number of elements the listpack holds. However if this field is set to 65535, which is the greatest unsigned integer representable in 16 bit, it means that the number of listpack elements is not known, so a LIST-LENGTH operation will require to fully scan the listpack. This happens when, at some point, the listpack has a number of elements equal or greater than 65535. The num-elements field will be set again to a lower number the first time a LIST-LENGTH operation detects the elements count returned in the representable range.
  16 비트 부호없는 정수는 listpack이 보유하는 총 요소 수를 보유합니다. 그러나 이 필드를 16 비트로 표현할 수 있는 가장 큰 부호없는 정수인 65535로 설정하면 listpack 요소의 수를 알 수 없으므로 LIST-LENGTH 조작에서 listpack을 완전히 스캔해야합니다. 이것은 어떤 시점에서 listpack에 65535보다 많은 수의 요소가 있을 때 발생합니다. num-elements 필드는 LIST-LENGTH 조작이 처음으로 범위 표시 가능에 리턴된 요소 수를 감지할 때 더 낮은 숫자로 설정됩니다.

All integers in the listpack are stored in little endian format, if not otherwise specified (certain special encodings are in big endian because it is more natural to represent them in this way for the way the specification maps to C code).

Listpack의 모든 정수는 달리 지정되지 않은 경우 리틀 엔디안 형식으로 저장됩니다 (특정 인코딩은 스펙이 C 코드에 매핑되는 방식으로 이러한 방식으로 표현하는 것이 더 자연스럽기 때문에 빅 엔디안(big endian) 임).

Each element in a listpack has the following structure:
Listpack의 각 요소는 다음 구조를 갖습니다. The element type and element total length are always present. The element data itself sometimes is missing, since certain small elements are directly represented inside the spare bits of the encoding type.

요소 유형과 요소 총 길이는 항상 존재합니다. 특정 작은 요소가 인코딩 유형의 스페어 비트 내에 직접 표시되므로 요소 데이터 자체가 누락되는 경우가 있습니다.

The encoding type is basically useful to understand what kind of data follows since strings can be encoded as little endian integers, and strings can have multiple string length fields bits in order to reduce space usage. The element data is the data itself, like an integer or an array of bytes representing a string. Finally the element total length, is used in order to traverse the list backward from the end of the listpack to its head, and is needed since otherwise there is no unique way to parse the entry from right to left, so we need to be able to jump to the left of the specified amount of bytes.

문자열은 작은 엔디안(little endian) 정수로 인코딩 될 수 있고 공간 사용량을 줄이기 위해 문자열에 여러 문자열 길이 필드 비트가 있을 수 있으므로 인코딩 유형은 기본적으로 어떤 종류의 데이터가 뒤에 오는지 이해하는데 유용합니다. 요소 데이터는 정수 또는 문자열을 나타내는 바이트 배열과 같은 데이터 자체입니다. 마지막으로 요소 총 길이는 listpack의 끝에서 머리로 목록을 앞으로 이동하는데 사용되며 그렇지 않으면 항목을 오른쪽에서 왼쪽으로 구문 분석하는 고유한 방법이 없으므로 필요합니다. 지정된 바이트 수만큼 왼쪽으로 이동합니다.

Each element can always be parsed left-to-right. The first two bits of the first byte select the encoding. There are a total of 3 possibilities. The first two encodings represents small strings. The third encoding instead is used in order to specify other sub-encodings.

각 요소는 항상 왼쪽에서 오른쪽으로 구문 분석할 수 있습니다. 첫 번째 바이트의 처음 두 비트는 인코딩을 선택합니다. 총 3 가지 가능성이 있습니다. 처음 두 인코딩은 작은 문자열을 나타냅니다. 대신 세 번째 인코딩은 다른 하위 인코딩을 지정하기 위해 사용됩니다.

Small numbers: 0~127까지 정수 표현

Strings that can be represented as small numbers, such as "65" or "1" are a very common, so they have a special encoding that allows to specify such strings representing numbers from 0 to 127 as a single byte:

"65"또는 "1"과 같이 작은 숫자로 표현할 수 있는 문자열은 매우 일반적이므로 0에서 127까지의 숫자를 나타내는 문자열을 단일 바이트로 지정할 수 있는 특수 인코딩이 있습니다. Where xxxxxxx is a 7 bit unsigned integer. We can test for this encoding just checking that the most significant bit of the first byte of the entry is zero.

xxxxxxx 부호없는 7 비트 정수는 어디에 있습니까? 엔트리의 첫 바이트의 최상위 비트가 0인지 확인하는 것만으로 이 인코딩을 테스트 할 수 있습니다.

A few examples: 몇 가지 예

Tiny strings: 0~63까지 문자열 표현

Small strings are also very common elements inside objects represented inside Redis collections, so the overhead to specify their length is just a single byte:

작은 문자열은 Redis 컬렉션 내에 표현된 객체 내에서 매우 일반적인 요소이므로 길이를 지정하는 오버 헤드는 단일 바이트입니다.
This encoding represents strings up to 63 characters in length, since xxxxxx is a 6 bit unsigned integer. The string data is the byte by byte string itself, and may be missing in the special case of the empty string.

이 인코딩은 xxxxxx 6 비트 부호없는 정수이므로 최대 63 자의 문자열을 나타냅니다. 문자열 데이터는 바이트별 문자열 자체이며 빈 문자열의 특수한 경우에는 누락될 수 있습니다.

A few examples: 몇 가지 예

Multi byte encodings

If the most significant two bits of the first byte are both set, then the remaining bits select one of the following sub encodings.
첫 번째 바이트의 최상위 2 비트가 모두 설정되면 나머지 비트는 다음 하위 인코딩 중 하나를 선택합니다.

The first three sub encodings happen when the first two bits are both "11" but the following bits are never "11".
처음 세 개의 서브 인코딩은 처음 두 비트가 모두 "11"이지만 다음 비트가 "11"이 아닐 때 발생합니다. In this encoding, xxxx|yyyyyyyy represent an unsigned integer where xxxx are the most significant bits and yyyyyyyy are the least significant bits.
이 인코딩에서, xxxx|yyyyyyyy인 부호없는 정수를 나타냅니다 . xxxx 최상위 비트이고, yyyyyyyy 최하위 비트.

Finally, when the first four bits are all set, the following sub encodings represented by the remaining four bits are defined:
마지막으로 처음 4 비트가 모두 설정되면 나머지 4 비트로 표시되는 다음과 같은 하위 인코딩이 정의됩니다.

Element total length field

As already specified, the last part of an entry is a representation of its own size, so that the listpack can be traversed from right to left. This field has a variable length, so that we use just a single byte for it if the length of the field is small, and progressively use more bytes for bigger entries. The total length field is designed to be parsed from right to left, since this is how we use it, and cannot be parsed the other way around, from left to right. However, when we parse the entry from left to right, we already know its length at the time we need to parse the total length field, so we can also compute how much bytes are needed in order to represent its total length field using the variable encoding. This allows to just skip this amount of bytes without attempting to parse it. We'll make it more clear with examples later in this section.

이미 지정한대로 항목의 마지막 부분은 자체 크기를 나타내므로 listpack을 오른쪽에서 왼쪽으로 순회할 수 있습니다. 이 필드는 가변 길이를 가지므로 필드 길이가 작은 경우 단일 바이트만 사용하고 더 큰 항목에 대해서는 더 많은 바이트를 점진적으로 사용합니다. 전체 길이 필드는 오른쪽에서 왼쪽으로 구문 분석되도록 설계되었습니다. 이것이 우리가 그것을 사용하는 방식이므로 다른 방향으로 왼쪽에서 오른쪽으로 구문 분석할 수 없습니다. 그러나 왼쪽에서 오른쪽으로 항목을 구문 분석할 때 전체 길이 필드를 구문 분석해야 할 때의 길이를 이미 알고 있으므로 변수를 사용하여 전체 길이 필드를 나타내는데 필요한 바이트 수를 계산할 수도 있습니다. 이를 통해 구문 분석하지 않고 이 양의 바이트를 건너 뛸 수 있습니다.

The variable length is stored from right to left, and the most significant bit of each byte is used in order to signal if there are more bytes. This means that we use only 7 bits in every byte. A entry length smaller than 128 can just be encoded as an 8-bit unsigned integer having the entry value.

가변 길이는 오른쪽에서 왼쪽으로 저장되며 더 많은 바이트가 있으면 신호를 보내기 위해 각 바이트의 최상위 비트가 사용됩니다. 이것은 우리가 모든 바이트에서 7 비트만을 사용한다는 것을 의미합니다. 128보다 작은 엔트리 길이는 엔트리 값을 갖는 8 비트 부호없는 정수로 인코딩될 수있다. However if I want to encode a entry length with the value of, for example, 500, two bytes will be required. The binary representation of 500 is the following:
그러나 500과 같은 값으로 항목 길이를 인코딩하려면 2 바이트가 필요합니다. 500의 이진 표현은 다음과 같습니다.
We can split the representation in two 7-bit halves:
표현을 두 개의 7 비트로 나눌 수 있습니다. Note that, since we parse the entry length from right to left, the entry is stored in big endian (but it's not vanilla big endian since only 7 bits are used and the 8th bit is used to signal the more bytes condition).
입력 길이를 오른쪽에서 왼쪽으로 구문 분석하므로 항목은 빅 엔디안으로 저장됩니다 (하지만 7 비트만 사용하고 8 비트는 더 많은 바이트 조건을 신호하는 데 사용되므로 바닐라 빅 엔디안은 아닙니다).

However we need to also add the bit to signal if there are more bytes, so the final representation will be:
그러나 더 많은 바이트가 있으면 신호에 비트를 추가해야하므로 최종 표현은 다음과 같습니다. The actual encoding will be: 실제 인코딩은 다음과 같습니다. Let's take for example a very simple entry encoding the string "hello":
문자열 "hello"를 인코딩하는 매우 간단한 항목을 예로 들어 보겠습니다. The raw entry is 6 bytes: the encoding byte followed by the raw data. In order for the entry to be complete, we need to add the entry length field at the end, that in this case is just the byte "06". So the final complete entry will be:
원시 항목은 6 바이트입니다. 인코딩 바이트 다음에 원시 데이터가옵니다. 입력이 완료 되려면 마지막에 입력 길이 필드를 추가해야합니다. 이 경우에는 바이트 "06"입니다. 따라서 최종 완성 항목은 다음과 같습니다. Note that we can easily parse the entry from right to left, by reading the length of 6, and jumping 6 bytes on the left to reach the start of the entry, but we can also parse the entry from left to right, since after we parsed the entry data of six bytes, we know how much bytes are used in order to encode its length by using the following table:

6의 길이를 읽고 왼쪽에서 6 바이트를 점프하여 항목의 시작 부분에 도달하면 항목을 오른쪽에서 왼쪽으로 쉽게 구문 분석할 수 있지만 항목을 왼쪽에서 오른쪽으로 구문 분석할 수도 있습니다. 6 바이트의 입력 데이터를 구문 분석하면 다음 표를 사용하여 길이를 인코딩하기 위해 사용되는 바이트 수를 알고 있습니다. No entry can be longer than 34359738367 bytes.
항목은 34359738367 바이트를 초과 할 수 없습니다.

The wish list about the implementation is, with points in decreasing order of importance, the following:
구현에 대한 희망 사항 목록은 다음과 같습니다.

• Crash resistant against wrong encodings. This was not the case with ziplist implementation.
  잘못된 인코딩에 대한 충돌 방지. Ziplist 구현의 경우가 아닙니다.
• Understandable and easily auditable. Well commented code.
  이해하기 쉽고 쉽게 감사(auditable)할 수 있어야 합니다. 설명이 잘 달린 코드.
• Fast. Avoid unnecessary copying. For instance, when adding to head, detect if realloc() is a non-OP (when advanced malloc functionalities are available) and instead use malloc() and avoid a copy of the data by copying directly at the right offset.
  빠른. 불필요한 복사를 피하십시오. 예를 들어 head에 추가할 때 realloc()이 비 OP인지(고급 malloc 기능을 사용할 수 있는 경우) 감지하고 대신 malloc()을 사용하고, 오른쪽 오프셋에서 직접 복사하여 데이터 복사를 피하십시오.
• Availability of an update-element operation, so that if an element is updated with one of the same size (very common with Hashes, think HINCRBY) there is no memory copying involved.
  요소가 동일한 크기(Hashes의 HINCRBY를 생각해보라)로 업데이트되는 경우 메모리 복사가 필요하지 않도록 요소 업데이트 작업의 가용성.

Notes about understandability: 이해에 대한 참고 사항:

Note that understandability cannot be obtained without simplicity of the design, however the design outlined in this document is thought to have a straightforward translation to a simple and robust implementation.
디자인의 단순성 없이는 이해를 얻을 수 없지만 이 문서에 요약된 디자인은 단순하고 강력한 구현으로 간단하게 변환된 것으로 생각됩니다.

Notes about crash resistance: 충돌 저항에 대한 참고 사항:

It is worth noting that crash resistance has limitations: for example a corrupted listpack header may make the program jump to invalid addresses. In this context for crash resistance we mean that as long as the corruption does not force the program to jump to illegal addresses, wrong encodings are detected when possible (that is, when the corruption does not happen to map to valid entries). For instance a wrong string length will be detected every time the amount of remaining bytes in the listpack is not compatible with the announced string length. The API should always be able to report such errors instead of crashing the program.

충돌 저항에는 제한이 있습니다. 예를 들어 손상된 listpack 헤더는 프로그램이 유효하지 않은 주소로 점프하게 만들 수 있습니다. 충돌 내성에 대한 이러한 맥락에서 우리는 손상으로 인해 프로그램이 잘못된 주소로 이동하지 않는한 가능한 경우 (즉, 손상이 유효한 항목에 매핑되지 않는 경우) 잘못된 인코딩이 감지됨을 의미합니다. 예를 들어, listpack에 남아있는 바이트의 양이 발표된 문자열 길이와 호환되지 않을 때마다 잘못된 문자열 길이가 감지됩니다. API는 프로그램을 중단시키는 대신 항상 이러한 오류를 보고할 수 있어야합니다.

This specification was written by Salvatore Sanfilippo. Oran Agra and Yuval Inbar, together with the author of this spec analyzed the ziplist implementation in order to search for bugs and to understand how the specification could be improved.

이 사양은 Salvatore Sanfilippo에 의해 작성되었습니다. Oran Agra와 Yuval Inbar는 이 스펙의 저자와 함께 ziplist 구현을 분석하여 버그를 검색하고 스펙을 개선할 수있는 방법을 이해했습니다.

Yuval provided the idea of allowing backward traversal by using only information which is local to the entry (the entry length at the end of the entry itself) instead of global informations (such as the length of the previous entry, as it was in ziplist).

Yuval은 전역 정보(예: ziplist에 있는 이전 항목의 길이) 대신 항목에 로컬인 정보 (항목 끝의 항목 길이)만 사용하여 역방향 순회를 허용한다는 아이디어를 제공했습니다.

Yuval also suggested to use a progressive length integer for the back length.
Yuval은 백 길이에 점진적 정수를 사용할 것을 제안했습니다.

Oran provided ideas about the optimization of the implementation.
Oran은 구현 최적화에 대한 아이디어를 제공했습니다.

There are certain improvements that we left out of this specification in order to enhance the simplicity of this data structure.

이 데이터 구조의 단순성을 향상시키기 위해 이 사양에서 제외된 특정 개선 사항이 있습니다.

Different encodings for positive and negative integers.
양의 정수와 음의 정수에 대한 다른 인코딩.

In theory it is possible to better exploit the fact we have free additional encoding type bits, in order to distinguish between positive and negative integers and always represent them as unsigned. In this way we could improve the range of the integers we can represent with a given number of bytes. A former version of this specification used an encoding like the following:

이론적으로 양의 정수와 음의 정수를 구별하고 항상 부호없는 것으로 표시하기 위해 추가 인코딩 유형 비트가 있다는 사실을 더 잘 활용할 수 있습니다. 이런 식으로 주어진 바이트 수로 표현할 수 있는 정수의 범위를 향상시킬 수 있습니다. 이 사양의 이전 버전은 다음과 같은 인코딩을 사용했습니다. However at a second thought this was believed to make the implementation more complex and potentially slower, so the slightly less efficient representation of storing signed integers was chosen instead.

그러나 두 번째 생각으로 이것은 구현을보다 복잡하고 잠재적으로 느리게 만드는 것으로 생각되었으므로 부호있는 정수 저장의 약간 덜 효율적인 표현이 대신 선택되었습니다.

Packed characters

Many element in a listpack, notably hash field names representing objects inside Redis, are going to use a subset of characters in the range A-z. Examples are strings such as name, suername and so forth.

Listpack의 많은 요소, 특히 Redis 내부의 객체를 나타내는 해시 필드 이름은 A-z 범위의 문자 하위 집합을 사용합니다. 예로는 다음과 같은 문자열 name, surname 등.

Using six bits per character it is possible to represent the alphabet consisting of all the lower and upper case letters, the numbers from 0 to 9, and a few more chars like -, _, .. So an additional encoding representing strings using six bits per character could be added in order to improve the space efficiency of strings considerably.

모든 하부 및 대문자로 이루어진 알파벳을 표현하는 것이 가능하다 문자당 6 비트를 사용하여, 0 내지 9의 숫자 -, _, .. 같은 몇 개 문자 따라서 문자열의 공간 효율성을 크게 향상시키기 위해 문자당 6 비트를 사용하는 문자열을 나타내는 추가 인코딩을 추가 할 수 있습니다.

This was not added mainly for performance considerations, since the complexity added is believed to be manageable and not a likely source of potential bugs.

추가된 복잡성이 관리 가능하고 잠재적인 버그의 원인이 아닌 것으로 여겨지기 때문에 이는 주로 성능 고려 사항으로 추가되지 않았습니다.

Skip index

Accessing far elements in a long listpack is O(N), so it looks natural to add some way in order to speedup this kind of lookups with skip tables. While this is usually a great idea for rarely changing packed representations of data, listpacks are going to be used in situations where data is often changed in the middle (Redis Hash and List data types both stress this usage pattern).

긴 listpack에서 원거리 요소에 액세스하는 것은 O(N)이므로 건너뛰기 테이블로 이러한 종류의 조회 속도를 높이기 위해 어떤 방법을 추가하는 것이 자연스럽게 보입니다. 일반적으로 압축된 데이터 표현을 거의 변경하지 않는 것이 좋은 생각이지만, 데이터가 중간에 자주 변경되는 상황에서 listpack이 사용됩니다 (Redis Hash 및 List 데이터 유형 모두이 사용 패턴을 강조합니다).

Updating the skip indexes could be error prone and even costly, and with the default settings Redis only uses relatively small listpacks where the access locality well compensates the need for scanning.

건너 뛰기 인덱스를 업데이트하면 오류가 발생하기 쉬우며 비용이 많이들 수 있으며 기본 설정을 사용하면 Redis는 비교적 작은 목록 팩만 사용하므로 액세스 위치가 스캔의 필요성을 잘 보상합니다.

When a memory saving representation is needed, with the ability to scale to many elements, the author believes that a linked data structure where listpacks are used as nodes is the preferred approach: it improves separation of concerns between the two representations and may be simpler to manage. In this regard listpacks are very friendly because they can be split and merged easily with linear copies without offsets adjustments.

많은 요소로 확장할 수 있는 메모리 절약 표현이 필요한 경우 저자는 listpack이 노드로 사용되는 링크된 데이터 구조가 선호되는 접근 방식이라고 생각합니다. 두 표현 간의 우려 분리를 개선하고 더 간단할 수 있습니다. 이와 관련하여 목록 팩은 오프셋 조정없이 선형 사본으로 쉽게 분할 및 병합할 수 있기 때문에 매우 친숙합니다.