1: 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.
2: Application scenario
Lpush + RPOP =Stack lPUSH + RPOP =Queue Lpush + Ltrim =Capped Collection lPUSH + BRPOP =Message Queue Data latest list and so on set expiration, can only be set for the entire collection, not a single element, there is no set expiration policy for individual elements
3: storage mode
The underlying storage is linkedList, zipList and quickList
1: linkedList
Similar to the LinkedList in Java, the LinkedList in Redis is a bidirectional LinkedList consisting of nodes. The structure of linked list node realized by C language in Redis is shown below
Pre points to the previous node, next points to the next node, and value holds the data object corresponding to the current node. The listNode diagram is shown below
The structure of the linked list is as follows:
The dup function is used to implement a copy of the value of a node in a list transfer copy. In general cases, the equal sign is sufficient, but in some special cases, the node transfer function may be used. By default, you can assign NULL to this function, which means node transfer using the equal sign. The free function frees the memory space occupied by a node. The match function is used to compare whether the value values of two linked list nodes are equal. If the value is equal, it returns 1, and if the value is not equal, it returns 0. Len indicates how many nodes there are in this linked list, so the length of the linked list can be obtained within the time complexity of O(1)
The structure of the linked list is as follows:
2: zipList type
The zipList structure of Redis is shown below
The zipList structure is shown below
Note the zltail_offffset parameter, which allows you to quickly locate the position of the last entry node and start traversal in reverse order, meaning zipList supports bidirectional traversal.
3: Comparison between linkList and zipList
1: When the length or number of elements in the list object is small, zipList is usually used for storage. When the length or number of elements in the list is large, the bidirectional linkedList is used instead. The length of all string elements in the list object is less than 64 bytes. The number of elements in the list element is less than 512. 2: The bidirectional linkedList is easy to push and pop on both ends of the table. First, it holds two Pointers on each node in addition to data; Secondly, each node of bidirectional linked list is a separate memory block, address is not continuous, easy to form memory fragments. 3: zipList is stored in a contiguous piece of memory, so storage efficiency is very high. However, it is not conducive to modification operations, as insert and delete operations require frequent memory requisition and freeing. Especially when the zipList is long, one realloc can result in a large number of data copies. 4: Why have linkedList and design a zipList? Like its name, zipList is a compressed list that was developed to save memory. The pre and Next Pointers are missing compared to linkedList. In Redis, the pre and Next Pointers take up 16 bytes (a pointer on 64-bit systems is 8 bytes). In addition, the memory of each node of linkedList is allocated separately, which aggravates the fragmentation of memory and affects the efficiency of memory management. In contrast, zipList is made up of contiguous memory, which saves a lot of memory fragmentation and pointer footprint because memory is contiguous.
4: quickList
1: the origin of
After the release of Redis3.2, there is an additional low-level implementation of lists, quickList. QucikList is a hybrid of zipList and bidirectional linkedList. It splits the linkedList into segments, each of which is stored compactly using a zipList, and connects multiple Ziplists using a bidirectional pointer.
The schematic diagram is as follows:
2: How many elements can each zipList store
Conf file, which is clearly documented under DVANCED CONFIG
If list-max-ziplist-szie is a positive number (n), the list max-ziplist-szie is a positive number (n). If list-max-ziplist-szie is a positive number (n), the list max-ziplist-szie is a positive number (n). Indicates that the zipList on each quickList node contains a maximum of N items.
4: summary
1: linkedList
1: linkedList is convenient for push and pop operations on both ends of the table, but it has a high memory overhead. 2: linkedList should store two Pointers on each node besides data. Each node of linkedList is a separate memory block, and the address is not continuous. If there are too many nodes, memory fragmentation may occur
2: ziplist
1: Ziplist is a whole block of continuous memory, so the storage efficiency is very high. 2: Ziplist is not conducive to modification operations, every data change will cause a realLOC of memory 3: When the Ziplist length is very long, one realloc may result in a large number of data copies, further degrading performance
3: quicklist
1: a compromise between space efficiency and time efficiency. 2: combining the advantages of double-endian linked lists and compressed lists