## 编程知识 cdmana.com

### Find out the principle | the article takes you to understand the realization of the underlying redis list

Last time we shared  Redis The underlying principle of strings  , Today, let's take a look at Redis `List`  The underlying principle of lists .

### Redis List command

Redis `List`  The list supports more related instructions , For example, a single element is added 、 Delete operation , Multiple element range operations are also supported .

Redis `List`  List supports the insertion of list header elements / eject ( LPUSH/LPOP ), It also supports the insertion of tail elements / eject ( RPUSH/RPOP ).

in addition Redis `List`  The list also supports indexing ( LINDEX ) Get elements , It also supports covering elements according to their subscripts ( LSET ).

besides ,Redis `List`  List also supports range operations , For example, get all the elements in the specified range ( LRANGE ), Remove all elements in the specified range ( LTRIM ).

That's all Redis Related instructions , Let's see Redis `List`  How to implement the list at the bottom , Two data structures are used ：

• Compressed list (ziplist)

Above we know  `List`  Lists support headers / Insertion of tail elements / eject , This kind of operation uses linked list, which is very efficient , The time complexity is O(1).

Redis Two way list (linkedlist) It consists of two structures ：

• list
• listnode

The structure is as follows ：

`list`  The header node is saved in the structure , The number of tail nodes and the number of nodes in the linked list , Because of this, the operation of the header / Insertion of tail elements / eject , The calculation of list length will be very efficient , The time complexity is  O(1) .

`listnode`  In addition to saving the value of the node in the structure , It also saves pointers to the front and back nodes , In this way, if you need to get the front node and post node of a node, it will be very efficient , The time complexity is  O(1) .

In addition, if you need to specify the position to insert / Remove elements , Then you just need to change the front and back pointers of the current position node , This insertion / The complexity of delete operation is  O(1) .

But be careful , Insert / Delete action premise we need to find the specified location , We can only traverse the linked list , The complexity is  O(N) , So insert / The complexity of deletion is  O(N) .

Two way list (linkedlist) Besides being used as a key in the list , It's also widely used for publishing / subscribe , Slow query and other internal operations .

Since the two-way list (linkedlist) Can satisfy the list key operation , What then? Redis The list also uses other data structures ？

In fact, it is mainly because of the memory consumption problem , Double linked lists use two structures , And both of these structures need to hold some necessary information , This is bound to take up part of the memory .

And when there are very few elements , If you use a double linked list directly , Memory is still a waste . therefore Redis Introduce compressed list .

### Compressed list

The compressed list is Redis Developed to save memory , It's made up of a series of specially coded   Continuous memory block   Sequential data structure composed of , The overall structure is as follows ：

You can see from the above structure that , Compressed lists are actually similar to the arrays we use , Each element in the array holds one data .

But unlike arrays , There are three fields in the header of the compressed list

zlbytes
zltail
zllen

In addition, there is a field at the end of the compressed list , `zlend`  A special value is stored in it , `OXFE` , Used to mark the end of a compressed list .

A compressed list can be made up of multiple nodes , Each node can hold integer values or byte arrays , The structure is as follows ：

Use compressed lists , If you look for and locate the header element , We just need to compress the length of the header field with three starting points , Search is very fast , Complexity is O(1).

And the last element of the compressed list , It's also very easy to find , We use the compressed list starting address plus  `zltail`  The included length can be directly pointed to , Search is also very fast , Complexity is O(1).

As for the other elements in the list , It's not so good luck , We can only start with the first element or the last element , Traverse the list to find , The complexity here is O(N) 了 .

In addition, the addition of compressed list 、 Remove elements , Will result in reallocation of memory , The efficiency is not high , The average complexity is O(N), The worst-case complexity is O(N^2).

### Encoding conversion

When we create a Redis List key , If the following two conditions are satisfied at the same time , The list object will use the compressed list as the underlying data structure

• The length of all string elements saved by the list object is less than 64 byte
• The number of elements saved in the list object is less than 512 individual

If these two conditions cannot be met at the same time , By default, the bidirectional list will be used as the underlying data structure .

### Summary

Redis Two data structures are used at the bottom of the list , Compressed list and double linked list .

Compressed list due to the use of contiguous blocks of memory , Less memory usage , And memory utilization is high , But new 、 Delete because it involves reallocation of memory , The efficiency is not high .

Two way list , newly added 、 It's very convenient to delete elements , But because each node is independent, the memory is fast , High memory footprint , And memory fragmentation is serious .

These two data structures are in the header / Inserting and deleting elements at the end of a table , It's very efficient . But other operations , Maybe it's inefficient .

So we use Redis list , We must adjust measures to local conditions , Think of it as FIFO queue , This only uses POP/PUSH , It's going to be very efficient .

original text ：www.tuicool.com/articles/N7nQ73r

## Reference material

1. Redis Design and implementation

=====

The design pattern of byte skipping summary PDF became angry , Full version open to download

brush Github When I found a notebook of Ali's algorithm ！ Star sign 70.5K

About 【 Brute force recursive algorithm 】 Ideas you don't know

Open up Hongmeng , Who does the system , Talk about Huawei's microkernel

=

## After reading three things ️

If you think this is helpful for you , I'd like to invite you to do me three little favors ：

give the thumbs-up , forward , There's your 『 Praise and comment 』, That's what motivates me to create .

Official account 『 Java Doudi 』, Share original knowledge from time to time .

At the same time, we can look forward to the following articles ing

https://cdmana.com/2020/12/20201224162859567H.html

Scroll to Top