This is the fifth day of my participation in Gwen Challenge

1. Introduction to list objects

Redis lists are simple lists of strings, sorted by insertion order, with support for adding elements from the head or tail, so list objects are often used as queues. A list key can contain up to 232−12^{32-1}232−1 elements.

Common commands for list objects are as follows:

lpush key value1[value2] // Inserts one or more values into the list header and returns the list length, creates the key if it does not exist, and returns an error message if the key does exist but is not a list type
lpushsx key value1[value2] // Inserts one or more values into the head of an existing list and returns the length of the list
lindex key index // Get the element of the specified position
lrange key start stop // Gets the elements in the specified range of the list
lpop key // Remove and return the first element in the list, nil if key does not exist
lrem key count value If count<0, remove the absolute value of count from the end of the table. If count=0, remove all elements with value
lset key index value // Set the value of the list element by index
llen key // Get the list length
ltrim key start stop // Prune a list so that only elements within the specified range are kept. All elements outside the specified range are deleted.
blpop key1 [key2 ] timeout // Remove and get the first element of the list. If there are no elements in the list, the list will be blocked until the wait times out or a popup element is found.
linsert key BEFORE|AFTER pivot value // Insert an element before or after the element in 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 an existing list
rpop key // Remove and get the last element of the list
brpop key1 [key2 ] timeout // Removes and retrieves the last element of the list. If there are no elements in the list, the list will be blocked until the wait times out or an eject element is found.
rpoplpush source destination // Remove the last element of the list, add that element to another list and return
brpoplpush source destination timeout // Pop a value from the list, insert the popup element into another list and return it; If the list has no elements, it blocks until the wait times out or a popup element is found.
Copy the code

2. List object coding

Redis list objects can be encoded as Ziplist or LinkedList. The underlying structure of Ziplist coding is compressed list. The underlying linkedlist encoding is the data structure of a double-endian linkedlist.

The ziplist-encoded list object diagram is shown below

Here is a diagram of the list object encoded for LinkedList

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

2.1 Coding Conversion

Ziplist encoding is used when a list object can satisfy both of the following conditions:

  • List objects hold all string elements that are less than 64 bytes long;

  • The list object holds less than 512 elements.

List objects that do not meet these two criteria need to be encoded using LinkedList.

Note: The upper limits of the above two conditions can be modified. See the description of the list-max-ziplist-value and list-max-ziplist-entries options in the configuration file.

3. Ziplist

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

3.1 Compressed list Composition

A compressed list can contain any number of entries, each of which can hold either a byte array or an integer value. The following shows the components of the compressed list.

attribute type The length of the use
zlbytes uint32_t 4byte Record the number of bytes of memory used by the compressed list: during memory reallocation of the compressed list, or calculationzlendIs used in the position of.
zltail uint32_t 4byte Records the number of bytes from the end of the compression list to the start of the compression list: With this offset, the program can determine the end of the table without traversing the entire compression list.
zllen uint16_t 2byte Records the number of nodes that the compressed list contains: when the value of this property is less thanUINT16_MAX （65535), the value of this property is the number of nodes in the compressed list; When this value is equal toUINT16_MAX, the real number of nodes needs to be calculated by traversing the whole compressed list.
entryX List node indefinite The length of each node contained in the compressed list is determined by the contents stored in the node.
zlend uint8_t 1byte Special values0xFF(decimal255) to mark the end of the compressed list.

3.2 Composition of compressed list nodes

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

There are three types of byte array lengths

  • Length less than or equal to63(
    2 6 – 1 2 ^ {6} – 1     ) byte array of bytes;
  • Length less than or equal to16383 （
    2 14 – 1 2 ^ {14} – 1     ) byte array of bytes;
  • Length less than or equal to4294967295 （
    2 32 – 1 2 ^ {32} – 1     ) byte array of bytes;

Integer values can have any of the following six lengths

  • 4Bit length, between0 至 12An unsigned integer between;
  • 1Signed integer long in bytes;
  • 3Signed integer long in bytes;
  • int16_tType integer;
  • int32_tType integer;
  • int64_tType integer.

Each compressed list node consists of previous_entry_LENGTH, Encoding, and Content.

3.2.1 previos_entry_lengthattribute

Previos_entry_length Records the length of the previous node in the compression list in bytes. The length of the previOS_entry_length property can be 1 or 5 bytes

  • If the previous node is less than 254 bytes,previos_entry_lengthThe length is 1 byte
  • If the previous node is 254 bytes or longer,previos_entry_lengthThe length is 5 bytes

The previOS_entry_length attribute enables ziplist traversal from the end of a table to the beginning of a table.

3.2.2 encodingattribute

The encoding property of the node records the type and length of the data held by the node’s Content property:

  • The byte array encoding is one, two, or five bytes long, with the highest bit being 00, 01, or 10. This encoding means that the node’s Content property holds an array of bytes, and the length of the array is recorded by the encoding excluding the highest two bits.

  • A byte long, with the highest bit of the value beginning with 11, is an integer encoding: this encoding means that the node’s Content property holds an integer value, whose type and length are recorded by encoding other bits after the highest two bits;

    coding The length of the code contentProperty to hold
    11000000 1byte int16_tType is an integer.
    11010000 1byte int32_tType is an integer.
    11100000 1byte int64_tType is an integer.
    11110000 1byte 24Bit signed integer.
    11111110 1byte 8Bit signed integer.
    1111xxxx 1byte Nodes that use this encoding have no correspondingcontentProperties,xxxxsavecontentvalue

3.2.3 contentattribute

The content property of a node holds the value of the node, which can be a byte array or an integer. The type and length of the value are determined by the encoding property of the node.

3.3 Cascading Updates

In a compressed list, there are multiple contiguous nodes e1 to eN between 250 and 253 bytes in length. Because all nodes e1 to eN are less than 254 bytes long, recording the length of these nodes requires only the 1-byte previous_entry_length attribute, in other words, The previous_entry_length attribute of all nodes from E1 to eN is 1 byte long.

If we set a new node new, 254 bytes or more long, as the head of the compressed list, then new will be the front node of E1, because e1’s previous_entry_length property is only 1 byte long, There is no way to store the length of the new node, so the program will redistribute the compressed list and expand the e1 node’s previous_entry_length property from 1 byte to 5 bytes.

Now, here’s the trouble — E1 was between 250 and 253 bytes long, but after adding four bytes of space to the previous_entry_length property, E1 was between 254 and 257 bytes long. This length cannot be saved using the 1-byte previous_entry_length attribute.

So, in order for e2’s previous_entry_length property to record E1’s length, the program needs to redistribute the compressed list again. The previous_entry_length attribute of e2 node is extended from 1 byte to 5 bytes.

Just as extending E1 caused an extension to E2, extending e2 caused an extension to E3, which in turn caused an extension to E4… In order for the previous_entry_length attribute of each node to meet the requirements of the compressed list for the node, the program needs to continuously perform space reallocation operations on the compressed list until eN.

This is called a chained update, where a single operation results in multiple consecutive space expansion operations. In addition to adding nodes can cause cascading updates, deleting nodes can also cause cascading updates. Because chained updates require N space reallocations of the compressed list in the worst case, and the worst complexity of each space reallocation is O(N), the worst complexity of chained updates is O(N^2).

Note that despite the complexity of chained updates, the chances of them actually causing performance problems are very low:

  • First, the compressed list should have exactly multiple contiguous entries of length between250Bytes to253Cascading updates can only be triggered on nodes between bytes, which is rare in practice.
  • Second, even if there are cascading updates, there is no impact on performance as long as the number of nodes being updated is small: for example, cascading updates to three or five nodes have absolutely no impact on performance;

4. Linkedlist

Each node in a double-ended list has two Pointers to its precursor and successor. ** The first node of the table points to NULL, and the next node of the last node points to NULL. ** Lists and list nodes are structured as follows.

// List node structure, double - ended list structure
typedef struct listNode {
  // The front node
  struct listNode *prev;

  // back node
  struct listNode *next;

  // Node value
  void *value;
}listNode;

// List structure
typedef struct list {
  // Table header node
  listNode *head;

  // Table end node
  listNode *tail;

  // Number of nodes
  unsigned long len;

  // The node value copy function copies the value stored by the linked list node
  void *(*dup)(void *ptr);

  // The node value release function releases the value saved by the linked list node
  void (*free) (void *ptr)

  // Node value comparison function to compare the value stored by a linked list node with another input value
  int (*match)(void *ptr,void *key)
}list;
Copy the code

Redis’ linked list implementation features

  • Double-ended, each node has prev and next Pointers, and the node complexity before and after acquiring a node is O(1).
  • There is no loop, and the prev pointer on the head node and the next pointer on the tail node point to NULL.
  • With a pointer to the head node and a pointer to the tail node, the complexity of obtaining the head node and the tail node is O(1).
  • With a list length counter, the complexity of obtaining the list length is O(1).
  • Polymorphic, the node uses the void* pointer to store the node value, and can set the type specific function for the node value through dUP, free, match three attributes, so the linked list can be used to store a variety of different types of values.