编程知识 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)
  • Two way list (linkedlist)

ps: This article is based on Redis 3.2 Start to explain

Two way list (linkedlist)

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

Recommended reading

=====

** How much money can a programmer get for a year ?
**

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

** The programmer 50W The knowledge system and growth route of annual salary .
**

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

版权声明
本文为[Mr.Z]所创,转载请带上原文链接,感谢
https://cdmana.com/2020/12/20201224162859567H.html

Scroll to Top