One, foreword

Redis provides five data types: String, Hash, List, Set, and Zset. Understanding the characteristics of each data type is important for the development and operation of Redis.

The original resolution

The list in Redis is a data type that we often use. It can be applied to many scenarios depending on how it is used.

2. Operation commands

List data types in Redis:

The command describe usage
LPUSH 1. Insert one or more values into the key header of the list

2. If there are multiple values, insert each value into the table header from left to right

3. If the key does not exist, an empty list will be created and LPUSH will be performed

4. The key exists but is not a list type		 LPUSH key value [value …]
LPUSHX 1. Insert the value value into the head of the list key if and only if the key exists and is a list

2. LPUSHX does nothing if key does not exist		 LPUSHX key value
LPOP 1. Remove and return the header element of the list key LPOP key
LRANGE 1. Return the element in the list key within the range specified by the offsets start and stop

2. Start and stop both start and stop with 0 bits

3. Use a negative subscript, -1 for the last element in the list, -2 for the next-to-last element, and so on

4. If start is greater than the maximum index of the list, an empty list is returned

5. Stop is greater than the maximum list subscript, stop= the maximum list subscript		 LRANGE key start stop
LREM 1. Remove elements equal to value from the list based on the value of count

2. If count>0 is searched from beginning to end, the number of elements equal to value is count

3. If count<0, remove elements equal to value from the end of the search

4. Count =0 removes all elements equal to value in the table		 LREM key count value
LSET 1. Set the value of the element whose key subscript is index to value

2. An error is returned when the index parameter is out of range or an empty list is LSET		 LSET key index value
LINDEX 1. Return the index element in the key list LINDEX key index
LINSERT 1. Insert the value value into the list key, either before or after pivot

2. When pivot does not exist in the list key, no operation is performed

3. If the key does not exist, no operation is performed		 LINSERT key BEFORE
LLEN 1. Return the length of the list key

2. If the key does not exist, 0 is returned		 LLEN key
LTRIM 1. Prune a list so that only elements within the specified range are returned LTRIM key start stop
RPOP 1. Remove and return the last element of the list key RPOP key
RPOPLPUSH In one atomic time, two actions are performed:

1. Pop up the last element in the list source and return it to the client

2. Insert the source popup element to desination as the head element of the destination list		 RPOPLPUSH source destination
RPUSH 1. Insert one or more values value to the end of the key list RPUSH key value [value …]
RPUSHX 1. Insert value at the end of the list key if and only if the key exists and is a list

2. Key does not exist, RPUSHX does nothing		 RPUSHX key value

Practice: Don’t be lazy. Try it out

Three, application scenarios

  • 1, lpush+lpop=Stack
  • Lpush +rpop=Queue
  • 3, LPUSH + Ltrim =Capped Collection
  • Lpush + brPOP =Message Queue
  • 5. Leaderboards, latest data lists, etc

Fourth, the underlying analysis

As the structure diagram shows, there are two implementations of the List type: for example, create the List object numbers

1. List objects implemented using ziplist

The structure is as follows:

A list object implemented using a linkedList

The structure is as follows:

Five, question thinking

What is the structure of a compressed list and a double-entailed list?

1. Ziplist

Ziplist is developed by Redis to save memory. It is a sequential data structure composed of a series of consecutively encoded memory blocks. A ziplist can contain any number of entries, and each node can hold a byte array or an integer value.

The structure is as follows:

The structure of each node in the compressed list is as follows:

1) previous_entry_ength: Records the length of the previous byte in the compressed list, in bytes. The length of previous_entry_ength can be 1 byte or 5 bytes: if the length of the previous node is less than 254 bytes, the previous_entry_ength attribute is 1 byte, and the length of the previous node is stored in that one byte. If the length of the previous node is greater than or equal to 254, the previous_entry_ength attribute is 5 bytes long, where the first byte of the attribute is set to 0xFE (decimal 254) and the next four bytes are used to hold the length of the previous node. Using this principle, the starting position of the previous node can be obtained by subtracting the length of the current node. The compressed list can be traversed from the tail to the head, which effectively reduces the waste of memory. Encoding: Records the type and length of data stored in the content property of the node. 3) Content: 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.

2. Linkedlist

Linked list is a commonly used data structure. There is no built-in implementation of such data structure in C language, so Redis builds the implementation of linked list by itself. List node definitions:

typedef  struct listNode{
       // The front node
       struct listNode *prev;
       // back node
       struct listNode *next;
       // Node value
       void *value;  
}listNode
Copy the code

Multiple ListNodes can form a double-ended list using prev and next Pointers. The structure is as follows:

Redis also provides data structures for manipulating linked lists:

typedef struct list{
     // Table header node
     listNode *head;
     // Table end node
     listNode *tail;
     // The number of nodes in the linked list
     unsigned long len;
     // Node value copy function
     void (*free) (void *ptr);
     // Node value release function
     void (*free) (void *ptr);
     // Node value comparison function
     int (*match) (void *ptr,void *key);
}list;
Copy the code

The list structure provides the head pointer, tail pointer, and len length counter for the list. The dUP, free, and match members are the type specific functions needed to implement polymorphic lists.

Redis linked list implementation features:

  • Double-ended: Linked list nodes have prev and next Pointers, and the complexity of obtaining a node’s pre-node and post-node is O(1).
  • Acyclic: The prev pointer on the head node and the next pointer on the tail node point to NULL, and access to the linked list ends at NULL.
  • With head and tail Pointers: With the head and tail Pointers of the list structure, the complexity of obtaining the head and tail of the list is O(1).
  • List length counter: The program uses the len attribute of the list structure to count the list nodes held by the list. The complexity of obtaining the number of nodes in the list is O(1).
  • Polymorphic: Linked list nodes use void* Pointers to hold node values, and use the dUP, free, and match attributes of the list structure to set type-specific functions for node values, so linked lists can be used to hold various types of values.

Question: When will Redis lists be ziplist encoded and when will LinkedList encoded?

More on that in the next section…