preface

The list type is used to store multiple ordered strings. In Redis, you can push and pop both ends of a list, get a list of elements in a specified range, get elements with a specified index index, and so on.

As a flexible data structure, lists can act as stacks and queues, and have many application scenarios in practical development.

As shown in the figure, elements A, B, C, D, and E form an ordered list from left to right. Each string in the list is called an element, and a list can store up to 2 ^ 32-1 elements.

  • List insertion and pop-up operations

  • List fetching, intercepting, and deleting operations

Other articles

  • Redis series (1) – Redis introduction and master-slave setup

  • In-depth analysis of Redis series ii – Redis Sentinel mode and high availability cluster

  • In-depth analysis of Redis series (3) – Redis cluster mode construction and detailed explanation of the principle

  • In-depth analysis of Redis series (4) – Redis data structure and global command overview

  • An in-depth analysis of Redis series 5 – Redis data structure strings

  • In-depth analysis of Redis series (6) – Redis data structure hashing

  • An in-depth look at Redis series 7 – Redis data structure list

  • An in-depth analysis of Redis series (eight) – Redis data structure collection

The body of the

1. Related commands

Commands are described in terms of the five types of operations on lists:

1.1. Adding commands

1.1.1. Insert elements from the right

rpush key value [value …]

Insert elements C, b, a from right to left:

127.0.0.1:6379> rpush listkey c b a
(integer) 3
Copy the code

The lrange 0-1 command fetches all the elements of the list from left to right:

127.0.0.1:6379> lrange ListKey 0-1 1)"c"
2) "b"
3) "a"
Copy the code

1.1.2. Insert elements from the left

lpush key value [value …]

It uses the same method as Rpush, except that it is inserted from the left, which I won’t repeat here.

1.1.3. Insert elements before or after an element

linsert key before|after pivot value

The linsert command finds the first element in the list equal to pivot, and inserts a new element value before or after it. For example, the following operation inserts redis before element B in the list:

127.0.0.1:6379> linsert listkey before b redis
(integer4)Copy the code

The result is 4, representing the length of the current list, which becomes:

127.0.0.1:6379> lrange ListKey 0-1 1)"c"
2) "redis"
3) "b"
4) "a"
Copy the code

1.2. Query commands

1.2.1. Get the list of elements in the specified range

lrange key start stop

The lrange operation retrieves all elements in the specified index range of the list.

Index subscripts have two characteristics:

  • One, the index subscripts are 0 to n-1 from left to right, but -1 to -n from right to left.

  • Second, the end option in lrange contains itself, unlike many programming languages that do not include end.

To get the second to fourth elements of the list from left to right, do the following:

127.0.0.1:6379> lrange listkey 1 3
1) "redis"
2) "b"
3) "a"
Copy the code

To get the first to third elements of the list from right to left, do the following:

127.0.0.1:6379> lrange listKey -3 -1)"redis"
2) "b"
3) "a"
Copy the code

1.2.2. Gets the element with the specified index subscript in the list

lindex key index

For example, the last element of the current list is a:

127.0.0.1:6379 > lindex listkey - 1"a"
Copy the code

1.2.3. Get the list length

llen key

For example, the following example currently has a list length of 4:

127.0.0.1:6379 > llen listkey (integer4)Copy the code

1.3. Delete commands

1.3.1. Pop elements from the left side of the list

lpop key

The following operations pop up the leftmost element C in the list, and the list changes to Redis, B, and A.

127.0.0.1:6379 > lpop listkey"c"127.0.0.1:6379> lrange ListKey 0-1 1)"redis"
2) "b"
3) "a"
Copy the code

1.3.2. Pop the element from the right side of the list

rpop key

It is used in the same way as LPOP, except that meta-elements pop up from the right side of the list.

127.0.0.1:6379 > lpop listkey"a"127.0.0.1:6379> lrange ListKey 0-1 1)"c"
2) "redis"
3) "b"
Copy the code

1.3.3. Delete the specified element

lrem key count value

The lREM command will find the element equal to value in the list and delete it. According to the difference of count, it can be divided into three cases:

  • Count > 0: Deletes a maximum of count elements from left to right.

  • Count < 0: Deletes up to the absolute value of count from right to left.

  • Count = 0, delete all.

For example, if five AS are inserted from left to right, the current list becomes “A a A a a a redis b a”. The following operation will remove the four AS from the left side of the list:

127.0.0.1:6379> lrem listkey 4 a
(integer) 4 127.0.0.1:6379> lrange ListKey 0-1 1)"a"
2) "redis"
3) "b"
4) "a"
Copy the code

1.3.4. Trim the list by index range

127.0.0.1:6379> ltrim listKey 1 3 OK 127.0.0.1:6379> lrange ListKey 0-1 1)"redis"
2) "b"
3) "a"
Copy the code

1.4. Modify commands

1.4.1. Modify the element with the specified index subscript

Modify the element with the specified index subscript:

lset key index newValue

The following action sets the third element in the listKey to mysql:

127.0.0.1:6379> lset listKey 2 mysql OK 127.0.0.1:6379> lrange listKey 0-1 1)"redis"
2) "b"
3) "mysql"
Copy the code

1.5. Block operation command

The commands for blocking pop-up operations are as follows:

blpop key [key …] timeout brpop key [key …] timeout

Blpop and BRPOP are blocking versions of LPOP and RPOP. They can be used in the same way except for the different pop-up directions. Therefore, the brpop command is used as an example.

  • key[key…] : Multiple keys in a list.

  • Timeout: indicates the blocking time (unit: second).

For the timeout argument, you want the atmosphere list to be empty or not empty:

  • The list is empty

If timeout = 3, the client will wait 3 seconds to return, and if timeout = 0, the client will block and wait:

127.0.0.1:6379 > brpop list:test 3
(nil)
(3.10s)
127.0.0.1:6379> brpop list:test0... Block...Copy the code

If data element1 is added during this time, the client immediately returns:

127.0.0.1:6379 > brpop list:test 3
1) "list:test"
2) "element1"(2.06 s)Copy the code
  • The list is not empty: the client returns immediately.
127.0.0.1:6379 > brpop list:test0, 1)"list:test"
2) "element1"
Copy the code

There are two things to be aware of when using BRPOP:

  • One, if yesMultiple keys, thenbrpop 会 From left to rightIterate over the key, once there isA key 能 Pop-up element, the clientReturn immediately:
Brpop list:1 list:2 list:3 0.. Blocking..Copy the code

At this point, another client inserts elements to list:2 and list:3 respectively:

client-lpush> lpush list:2 element2
(integer) 1
client-lpush> lpush list:3 element3
(integer1)Copy the code

The client immediately returns element2 in list:2, because list:2 is the first element that can pop up.

127.0.0.1:6379> brpop list:1 list:2 list:3 0 1"list:2"
2) "element2"
Copy the code
  • Second, ifMultiple clients 对 The same keyperformbrpop, thenThe first to perform brpopOf the commandThe clientcanTo obtainTo the pop-up value.

Execute brPOP commands on three clients in sequence:

  • Client 1:
client-1> brpop list:test0... Block...Copy the code
  • Client 2:
client-2> brpop list:test0... Block...Copy the code
  • Client 3:
client-3> brpop list:test0... Block...Copy the code

At this point, another client lpush an element into the list:test list:

client-lpush> lpush list:test element
(integer1)Copy the code

Then client 1 gets the element because client 1 executes the BRPOP command first, while client 2 and client 3 continue to block.

client> brpop list:test0, 1)"list:test"
2) "element"
Copy the code

Now that the basic commands for lists are covered, the following table shows the time complexity of the related commands:

2. Internal coding

There are two internal encodings for list types:

2.1. Ziplist (Compressed List)

When the number of list elements is smaller than the list-max-ziplist-entries configuration (512 by default) and the value of each element is smaller than the list-max-ziplist-value configuration (64 bytes by default), Redis uses Ziplist as an internal implementation of lists to reduce memory usage.

2.2. Linkedlist

Redis uses linkedList as an internal implementation of a list when the list type does not meet Ziplist’s criteria.

2.3. Coding conversion

The following example demonstrates the internal encoding of list types and the corresponding changes.

  • When the elementThe number of less 且 No big elementsWhen,The internal encoding 为 ziplist:
127.0.0.1:6379> rpush listkey e1 e2 e3
(integer) 3
127.0.0.1:6379> object encoding listkey
"ziplist"
Copy the code
  • When the number of elements exceeds512A,The internal encodingintolinkedlist:
127.0.0.1:6379> rpush listKey e4 e5... e512 e513 (integer) 513
127.0.0.1:6379> object encoding listkey
"linkedlist"
Copy the code
  • When some element exceeds64 byte.The internal encodingWill becomelinkedlist:
127.0.0.1:6379 > rpush listkey"one string is bigger than 64 byte..."
(integer) 4
127.0.0.1:6379> object encoding listkey
"linkedlist"
Copy the code

Redis3.2 provides quickList internal encoding, which is simply a Ziplist node linkedList, which combines the advantages of both Ziplist and LinkedList. Provides a better internal coding implementation for list types, and its design principles can be found in another Redis author, Matt Stancliff’s redis-QuickList blog.

3. Application scenarios

3.1. Message queues

Blocking queues are implemented through Redis’s lpush + BRPOP command combination. As shown in the figure:

Producer clients use LRpush to insert elements from the left side of the list, and multiple consumer clients use BRPOP blocking to “grab” elements from the bottom of the list, ensuring load balancing and high availability for consumption.

3.2. List of articles

Each user has his or her own article list, which needs to be displayed in pages. Consider using a list at this point, because lists are not only ordered, but also support fetching elements by index range.

  • Use per articleHash structureStorage, such as per article3A propertytitle,timestamp,content:
hmset acticle:1 title xx timestamp 1476536196 content xxxx hmset acticle:2 title yy timestamp 1476536196 content yyyy . hmset acticle:k title kk timestamp 1476512536 content kkkkCopy the code
  • Present the user with a list of articlesAdd the article.user:{id}:articlesAs a list of user articleskey:
lpush user:1:acticles article:1 article:3 article:5
lpush user:2:acticles article:2 article:4 article:6
...
lpush user:k:acticles article:7 article:8
Copy the code
  • pagingTo obtainList of user articles, for examplePseudo codeGet the userid=1The former10Article:
articles = lrange user:1:articles 0 9
for article in {articles}
    hgetall {article}
Copy the code

There are two problems with saving and retrieving a list of articles using list types:

  • First: If a large number of articles are obtained in each page, multiple HGEtall operations need to be performed. In this case, Pipeline can be used for batch acquisition, or mGET can be used to serialize article data into string type for batch acquisition.

  • Second: The lrange command performs well at both ends of the list when fetching a list of articles in pages, but the performance of fetching elements in the middle range of the list deteriorates if the list is large. Consider a secondary split of the list, or use Redis 3.2’s Internal QuickList encoding, which combines the features of Ziplist and LinkedList to fetch the middle range of the list.

3.3. Other scenarios

In fact, there are many use scenarios for lists, as follows:

Command combination Corresponding data structure
lpush + lpop The Stack (Stack)
lpush + rpop Queue
lpush + ltrim Capped Collection
lpush + brpop Message Queue

summary

This article introduced some basic commands, internal encodings, and application scenarios for lists in Redis. By combining different commands, you can transform lists into different data structures for use.

reference

Redis Development and Operation

Welcome to pay attention to the technical public number: Zero one Technology Stack

This account will continue to share learning materials and articles on back-end technologies, including virtual machine basics, multithreaded programming, high-performance frameworks, asynchronous, caching and messaging middleware, distributed and microservices, architecture learning and progression.