Redis basic series (three)-list object

Redis basic series (three)-list object

This is the 5th day I participated in the Wenwen Challenge. For details of the event, please view: Wenwen Challenge

1. Introduction to list objects

The Redis list is a simple list of strings, sorted according to the insertion order, and supports adding elements from the head or tail, so the list object is often used as a queue. A list key can contain at most232 12^{32-1} element.

Commonly used commands for list objects are as follows:

lpush key value1[value2] //Insert one or more values into the header of the list and return the length of the list. If the key does not exist, insert it after creating the key. If the key exists but is not a list type, an error message will be returned. lpushsx key value1[value2 ] //Insert one or more values into the head of the existing list and return the length of the list. If the list does not exist, the operation will be invalid. lindex key index //get the element at the specified position lrange key start stop //get the element within the specified range of the list lpop key //Remove and return the first element of the list. If the key does not exist, return nil. lrem key count value //Remove the element whose value is value. If count>0, remove count elements from the header, count< 0 then remove count absolute value elements from the end of the table, count=0 remove all elements with value lset key index value //set the value of the list element by index llen key //get the length of the list ltrim key start stop //Prune a list so that the list only retains the elements in the specified interval, and the elements not in the specified interval will be deleted. blpop key1 [key2] timeout // Move out and get the first element of the list. If there are no elements in the list, the list will be blocked until the waiting timeout or an element that can be popped is found. linsert key BEFORE|AFTER pivot value //Insert an element before or after the elements of the list rpush key value1 [value2] //Add one or more values to the end of the list rpush key value //Add a value to the end of the existing list rpop key //Remove and get the last element of the list brpop key1 [key2] timeout //Remove and get the last element of the list. If there are no elements in the list, the list will be blocked until the waiting timeout or an element that can be popped is found. rpoplpush source destination //Remove the last element of the list and add the element to another list and return brpoplpush source destination timeout //Pop a value from the list, insert the popped element into another list and return it ; If there are no elements in the list, the list will be blocked until the waiting timeout or the pop-up element is found. Copy code

2. List object coding

The encoding of the Redis list object can be

ziplist
or
linkedlist
.
ziplist
The underlying structure of the encoding is a compressed list ;
linkedlist
The bottom layer of the encoding is the data structure of the double-ended linked list .

The following is a schematic diagram of the list object encoded by ziplist

The following is a schematic diagram of the list object encoded by the linkedlist

Note: Each node in the linked list is a string object, not a simple string.

2.1 Encoding conversion

When the list object can meet the following two conditions at the same time, the list object uses

ziplist
coding:

  • The length of all string elements stored in the list object is less than

    64
    byte;

  • The number of elements stored in the list object is less than

    512
    A

List objects that cannot meet these two conditions need to be used

linkedlist
coding.

Note: The upper limit of the above two conditions can be modified, please refer to the configuration file for details

list-max-ziplist-value
Options and
list-max-ziplist-entries
The description of the option.

3. Compressed list (ziplist)

The compressed list is developed by Redis to save memory. It is a sequential data structure composed of a series of specially coded contiguous memory blocks.

3.1 Compression list composition

A compressed list can contain any number of entries, and each node can store a byte array or an integer value. The following shows the various components of the compressed list.

AttributesTypes oflengthuse
zlbytes
uint32_t
4
byte
Record the number of bytes of memory occupied by the entire compressed list: when the compressed list is redistributed or calculated
zlend
When using the location.
zltail
uint32_t
4
byte
Record the number of bytes between the end node of the compressed list and the start address of the compressed list: With this offset, the program can determine the address of the end node of the list without traversing the entire compressed list.
zllen
uint16_t
2
byte
The number of nodes included in the compressed list is recorded: When the value of this attribute is less than
UINT16_MAX
(
65535
), the value of this attribute is the number of nodes in the compressed list; when this value is equal to
UINT16_MAX
When, the actual number of nodes can be calculated by traversing the entire compressed list.
entryX
List nodeindefiniteEach node contained in the compressed list, the length of the node is determined by the content saved by the node.
zlend
uint8_t
1
byte
Special value
0xFF
(Decimal
255
), used to mark the end of the compressed list.

3.2 The composition of compressed list nodes

Each compressed list node can store a byte array or an integer value

The byte array length can have the following 3 types

  • Length is less than or equal to
    63
    ( 26 12^{6}-1 ) Byte array of bytes;
  • Length is less than or equal to
    16383
    (214 12^{14}-1 ) Byte array of bytes;
  • Length is less than or equal to
    4294967295
    (232 12^{32}-1 ) Byte array of bytes;

Integer values can have the following 6 lengths

  • 4
    Bit length, between
    0
    to
    12
    Unsigned integer between;
  • 1
    Signed integer with byte length;
  • 3
    Signed integer with byte length;
  • int16_t
    Type integer;
  • int32_t
    Type integer;
  • int64_t
    Type integer.

Each compressed list node is composed of

previous_entry_length
,
encoding
,
content
It consists of three parts.

3.2.1
previos_entry_length
Attributes

previos_entry_length
In bytes, record the length of the previous node in the compressed list,
previos_entry_length
The attribute length can be 1 byte or 5 bytes

  • If the length of the previous node is less than 254 bytes,
    previos_entry_length
    Length is 1 byte
  • If the length of the previous node is greater than or equal to 254 bytes,
    previos_entry_length
    Length is 5 bytes

by

previos_entry_length
Properties can be achieved
ziplist
Traverse from the end of the table to the head of the table.

3.2.2
encoding
Attributes

Nodal

encoding
The attribute records the node's
content
The type and length of the data stored in the attribute:

  • One byte, two bytes or five bytes long, the highest bit of the value is

    00
    ,
    01
    or
    10
    Is the byte array encoding: this encoding represents the node s
    content
    The attribute stores the byte array, and the length of the array is recorded by the other bits after the most significant two digits are removed from the code;

  • One byte long, the highest bit of the value is

    11
    At the beginning is the integer code: this code represents the node
    content
    The attribute holds the integer value, and the type and length of the integer value are recorded by the code after removing the most significant two bits;

    codingEncoding length
    content
    The value saved by the attribute
    11000000
    1
    byte
    int16_t
    Type of integer.
    11010000
    1
    byte
    int32_t
    Type of integer.
    11100000
    1
    byte
    int64_t
    Type of integer.
    11110000
    1
    byte
    24
    Bit signed integer.
    11111110
    1
    byte
    8
    Bit signed integer.
    1111xxxx
    1
    byte
    The node using this code has no corresponding
    content
    Attributes,
    xxxx
    save
    content
    value

3.2.3
content
Attributes

Nodal

content
The attribute is responsible for storing the value of the node. The node value can be a byte array or an integer. The type and length of the value are determined by the node's
encoding
Property decision.

3.3 Chain update

In a compressed list, there are multiple consecutive lengths between

250
Byte to
253
Node between bytes
e1
to
eN
. because
e1
to
eN
The length of all nodes is less than
254
Bytes, so you only need to record the length of these nodes
1
Byte long
previous_entry_length
Attribute, in other words,
e1
to
eN
Of all nodes
previous_entry_length
Attributes are
1
Bytes long.

If we set a length greater than or equal to

254
New node
new
Set as the header node of the compressed list, then
new
will be
e1
Pre-nodes because
e1
of
previous_entry_length
Property only long
1
Bytes, it can t save the new node
new
Length, so the program will perform a space reallocation operation on the compressed list, and will
e1
Nodal
previous_entry_length
Attributes from the original
1
The byte length is expanded to
5
Byte length.

Now, the trouble is coming

e1
The original length is between
250
Byte to
253
Between bytes,
previous_entry_length
After adding four bytes of space to the attribute,
e1
The length becomes between
254
Byte to
257
Between bytes, and this length uses
1
Byte long
previous_entry_length
There is no way to save properties.

Therefore, in order to

e2
of
previous_entry_length
Attributes can be recorded
e1
The program needs to re-allocate the space of the compressed list again, and change
e2
Nodal
previous_entry_length
Attributes from the original
1
The byte length is expanded to
5
Byte length.

As extended

e1
Triggered right
e2
The extension is the same as the extension
e2
Will also lead to
e3
Expansion, while expansion
e3
Will cause the right
e4
Extension... in order to make each node s
previous_entry_length
The attributes meet the requirements of the compressed list for nodes, and the program needs to continuously perform space reallocation operations on the compressed list until
eN
until.

This is a chain update, because one operation leads to multiple consecutive space expansion operations. In addition to adding nodes will cause chain updates, deleting nodes may also cause chain updates. Because the chain update needs to be performed on the compressed list in the worst case

N
Secondary space reallocation operations, and the worst complexity of each space reallocation is O(N), so the worst complexity of chain update is O(N^2).

It should be noted that despite the high complexity of chain update, the probability of it actually causing performance problems is very low:

  • First of all, there must be exactly multiple consecutive, lengths between
    250
    Byte to
    253
    For nodes between bytes, chain updates may be triggered. In practice, this situation is rare;
  • Secondly, even if there is a chain update, as long as the number of updated nodes is small, it will not have any impact on performance: For example, performing chain updates on three to five nodes will never affect performance;

4. Double-ended list (linkedlist)

Each node in the double-ended linked list has two pointers to its predecessor and successor nodes. **The predecessor node of the table head node points to NULL, and the successor node of the table tail node points to NULL. **The structure of linked list and linked list nodes is as follows.

//Linked list node structure, double-ended linked list structure typedef struct listNode { //pre-node struct listNode * prev ; //Post node struct listNode * next ; //The value of the node void *value; }listNode; //Linked list structure typedef struct list { //head node listNode *head; //The end node of the table listNode *tail; //Number of nodes unsigned long len; //Node value copy function, copy the value saved by the linked list node void *(*dup)( void *ptr); //Node value release function, release the value saved by the linked list node void (* free )( void *ptr) //Node value comparison function, compare whether the value saved by the linked list node is equal to another input value int (*match)( void *ptr, void *key) } list ; copy code

Redis's linked list implementation features

  • Double-ended, each node has prev and next pointers, and the complexity of obtaining a node before and after the node is O(1).
  • Acyclic, the prev pointer of the head node and the next pointer of the tail node both point to NULL.
  • With the head node pointer and the tail pointer, the complexity of obtaining the head and tail nodes is O(1).
  • With a linked list length counter, the complexity of obtaining the linked list length is O(1).
  • Polymorphism, the node uses the void* pointer to save the node value, and can set the type-specific function for the node value through the three attributes of dup, free, and match, so the linked list can be used to save various types of values.