“This is the 34th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”
A compressed list is a sequential integer structure consisting of a series of specially encoded contiguous memory blocks. A compressed list can contain any number of nodes, and each node can hold either a byte array or an integer. Suitable for storing small objects and data of limited length.
Compressed lists are one of the underlying implementations of list keys and hash keys. When a list key contains only a small number of list items, and each item is either a small integer value or a short string length, Redis uses compressed lists for the underlying implementation of list keys.
For example, when a hash table contains only a small number of key-value pairs, and the keys and values of each pair are either small integer values or short strings, Redis uses a compressed list for the underlying implementation of the hash key.
The data structure
Here is the definition of ziplistEntry:
/* Each entry in the ziplist is either a string or an integer. */
typedef struct {
/* When string is used, it is provided with the length (slen). */
unsigned char *sval;
unsigned int slen;
/* When integer is used, 'sval' is NULL, and lval holds the value. */
long long lval;
} ziplistEntry;
Copy the codeHere are the components of each part of the compressed list (logical structure)
- Zlbytes records the number of bytes for the entire compressed list and is used when the compressed list is used for memory reallocation or when calculating zlend
- Ztail records the number of bytes between the end node of the compressed list and the start address of the compressed list. This offset can be used to determine the end node of the table without traversing the entire compressed list
- Zllen Records the number of nodes in the compressed list. When the value is less than 65535, the number of nodes in the list is recorded. Otherwise, if the value is equal to 65535, traversal is required to obtain the number of nodes.
- The zlend special value 0xFF (decimal 255) is used to mark the end of the compressed list.
Here’s an example (below) :
Description of each section:
1) The zlBytes attribute of the list is 0x50 (decimal 80), which means that the total length of the compressed list is 80 bytes
2) The zltail property of the list is 0x3c (decimal 60), which means that if we have a starting pointer p to the compressed list, we can calculate entry3 by adding the offset 60 to the pointer. The address.
3) The value of the list zllen attribute is 0x3 (decimal 3), which means there are three nodes.
nodes
/* We use this function to receive information about a ziplist entry.
* Note that this is not how the data is actually encoded, is just what we
* get filled by a function in order to operate more easily. */
typedef struct zlentry {
unsigned int prevrawlensize; /* Bytes used to encode the previous entry len*/
unsigned int prevrawlen; /* Previous entry len. */
unsigned int lensize; /* Bytes used to encode this entry type/len.
For example strings have a 1, 2 or 5 bytes
header. Integers always use a single byte.*/
unsigned int len; /* Bytes used to represent the actual entry.
For strings this is just the string length
while for integers it is 1, 2, 3, 4, 8 or
0 (for 4 bit immediate) depending on the
number range. */
unsigned int headersize; /* prevrawlensize + lensize. */
unsigned char encoding; /* Set to ZIP_STR_* or ZIP_INT_* depending on
the entry encoding. However for 4 bits
immediate integers this can assume a range
of values and must be range-checked. */
unsigned char *p; /* Pointer to the very start of the entry, that
is, this points to prev-entry-len field. */
} zlentry;
Copy the codeThe corresponding relationship is as follows:
The conversion function is as follows:
static inline void zipEntry(unsigned char *p, zlentry *e) { ZIP_DECODE_PREVLEN(p, e->prevrawlensize, e->prevrawlen); ZIP_ENTRY_ENCODING(p + e->prevrawlensize, e->encoding); ZIP_DECODE_LENGTH(p + e->prevrawlensize, e->encoding, e->lensize, e->len); assert(e->lensize ! = 0); /* check that encoding was valid. */ e->headersize = e->prevrawlensize + e->lensize; e->p = p; }Copy the code
Prevlen: Records the length of the current node, in bytes. Prevlen takes one byte if the length of a node is less than 254. Otherwise prevlen takes 5 bytes to store, with the first byte fixed at 0xfe (254) and the last 4 bytes Tina storing the length of the previous node. Function: With this attribute, you can quickly locate the start position of the previous node and support ziplist reverse traversal.
1. Data is a string
| coding | String length | The Content property holds the value |
|---|---|---|
| 00bbbbbb | 1 byte | An array of less than 63 bytes |
| 01bbbbbb xxxxxxxx | 2 – | An array of 16 383 bytes or less |
| 10_ _ _ _ _ _ aaaaaaaa bbbbbbbb cccccccc dddddddd | 5 bytes | The length is less than or equal to 4 294 967 295 bytes |
2. If the data is an integer
| coding | String length | The Content property holds the value |
|---|---|---|
| 11000000 | 1 byte | An integer of type Int16_t |
| 11010000 | 1 byte | The value is an integer of type Int32_t |
| 11100000 | 1 byte | An integer of type Int64_t |
| 11110000 | 1 byte | 24 – bit signed integer |
| 11111110 | 1 byte | An 8-bit signed integer |
| 1111xxxx | 1 byte | Nodes that use this encoding have no corresponding content attribute, because the encoding itself of the XXXX four bits already holds a value between 0 and 12, 1 = 11110001> 13 = 11111111> Avoid collisions with 8 bits so it is [0, 12] so it does not need the content attribute |
The code is as follows:
Chain update
Prevlen keeps the length of the previous byte in entry:
-
If the previous dictionary is less than 256 bytes, the prevlen attribute requires one word
-
If the length of the previous byte is greater than or equal to 256 bytes, the prevlen attribute takes 5 bytes to hold the length
Therefore, the insertion or deletion operation will break the ziplist feature, and nodes need to be updated. Redis only deals with the expansion of a set or a single byte into 5 points, no shrinkage (in order to prevent repeated narrowing – enlargement)
Worst-case scenario: Continuous updates perform N space allocations to ziplist, and each reallocation is O(N) at worst, so the worst-case scenario for cascading updates is O(N ^2).
Pay attention to the point
1. Search time complexity is O(N)
2. When the length of the list exceeds the UINT16_MAX, zllen no longer represents the number of nodes
3. Chain update related content