Redis from Getting Started to Giving up series (three) List

This example is based on: 5.0.4 List is a common data structure in Redis, which is implemented as QuickList, which is a Ziplist bidirectional linked List

Redis from start to Give up series (a) String

Redis from Getting Started to Giving up series (2) Hash

First let’s look at how to use the List type in Redis

// Set the list of keys to value
lpush key value [value...]
Copy the code

Code examples:

// The stack is the same as rpush and rpop
> lpush books java python c
(integer) 3
> lpop books
"c"
> lpop books
"python"
> lpop books
"java"
----------------------------------
// return the list element of the range specified by key and the range offset specified by start and stop
// Start and stop are all based on 0
> lrange books 0 2
1) "c"
2) "python"
3) "java"
----------------------------------
// Ltrim can be used as a fixed-length list, fetching the latest 2 items each time
> lpush books java python c c++
(integer) 4
> ltrim books 0 1
OK
> lrange books 0 -1
1) "c++"
2) "c"
----------------------------------
// When there are no pop-ups in the given list, the connection will be blocked by blPOP, brPOP commands until the wait times out or pop-ups are found.
// Set the timeout to 1 second
> BLPOP books 1
1) "books"
2) "c++"
> BLPOP books 1
1) "books"
2) "c"
> BLPOP books 1
(nil)
(1.05s)
----------------------------------
Copy the code

The use of redis list ends here.

The source code parsing

Quicklist is a Ziplist bidirectional linked list. What is the internal structure of quickList?

/* quicklist is a 40 byte struct (on 64-bit systems) describing a quicklist. * 'count' is the number of total entries. *  'len' is the number of quicklist nodes. * 'compress' is: -1 if compression disabled, otherwise it's the number * of quicklistNodes to leave uncompressed at ends of quicklist. * 'fill' is the user-requested  (or default) fill factor. */
typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* total count of all entries in all ziplists */
    unsigned long len;          /* number of quicklistNodes */
    int fill : 16;              /* fill factor for individual nodes */
    unsigned int compress : 16; /* depth of end nodes not to compress; 0=off */
} quicklist;

/* quicklistNode is a 32 byte struct describing a ziplist for a quicklist. * We use bit fields keep the quicklistNode at  32 bytes. * count: 16 bits, max 65536 (max zl bytes is 65k, so max count actually < 32k). * encoding: 2 bits, RAW=1, LZF=2. * container: 2 bits, NONE=1, ZIPLIST=2. * recompress: 1 bit, bool, true if node is temporarry decompressed for usage. * attempted_compress: 1 bit, boolean, used for verifying during testing. * extra: 10 bits, free for future use; pads out the remainder of 32 bits */
typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* was this node previous compressed? * /
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;
/* quicklistLZF is a 4+N byte struct holding 'sz' followed by 'compressed'. * 'sz' is byte length of 'compressed' field.  * 'compressed' is LZF data with total (compressed) length 'sz' *NOTE: uncompressed length is stored in quicklistNode->sz.
 * When quicklistNode->zl is compressed, node->zl points to a quicklistLZF */
typedef struct quicklistLZF {
    unsigned int sz; /* LZF size in bytes*/
    char compressed[];
} quicklistLZF;
Copy the code

From the above we can see that quickList is a bidirectional linked list, so when we use lpush, rPOP, etc operations are O(1).

Ziplist itself is a list that maintains the order of the data (by insertion location), and it’s a compact list. When we want to represent a list with 12 items, we can have multiple options, such as a three-node QuickList, where each ziplist contains four items. Or a two-node Quicklist, each ziplist contains six items so how does Redis choose? We can find the clues in redis.conf

# Lists are also encoded in a special way to save a lot of space.
# The number of entries allowed per internal list node can be specified
# as a fixed maximum size or a maximum number of elements.
# For a fixed maximum size, use -5 through -1, meaning:
# -5: max size: 64 Kb <-- not recommended for normal workloads
# -4: max size: 32 Kb <-- not recommended
# -3: max size: 16 Kb <-- probably not recommended
# -2: max size: 8 Kb <-- good
# -1: max size: 4 Kb <-- good
# Positive numbers mean store up to _exactly_ that number of elements
# per list node.
# The highest performing option is usually -2 (8 Kb size) or -1 (4 Kb size),
# but if your use case is unique, adjust the settings as necessary.
list-max-ziplist-size -2

# Lists may also be compressed.
# Compress depth is the number of quicklist ziplist nodes from *each* side of
# the list to *exclude* from compression. The head and tail of the list
# are always uncompressed for fast push/pop operations. Settings are:
# 0: disable all list compression
# 1: depth 1 means "don't start compressing until after 1 node into the list,
# going from either the head or tail"
# So: [head]->node->node->... ->node->[tail]
# [head], [tail] will always be uncompressed; inner nodes will compress.
# 2: [head]->[next]->node->node->... ->node->[prev]->[tail]
# 2 here means: don't compress head or head->next or tail->prev or tail,
# but compress all nodes between them.
# 3: [head]->[next]->[next]->node->node->... ->node->[prev]->[prev]->[tail]
# etc.
list-compress-depth 0
Copy the code

list-max-ziplist-size
Copy the code

When set to positive means that at most that number of elements can be stored, The authors of Redis recommend setting it to -1 or -2, the size of the ziplist that can store elements on each QuickList node. When the list is long, the data in the middle may be accessed infrequently, in which case the list provides a parameter to compress the data in the middle

list-compress-depth 0
Copy the code

This parameter indicates the number of uncompressed nodes at both ends of the QuickList. The head and tail nodes are always uncompressed for quick access

0: this is a special value, indicating that none is compressed. This is the default value for Redis.
1: indicates that one node at both ends of the QuickList is not compressed, and the middle node is compressed.
2: indicates that two nodes at both ends of the QuickList are not compressed, and the middle node is compressed.
3: indicates that three nodes at both ends of the QuickList are not compressed, and the middle node is compressed.
And so on…

The structure diagram of quickList is as follows:

list-max-ziplist-size 3
list-compress-depth 1
Copy the code

In this example, we can see that one node at each end of the quickList is not compressed, and their data Pointers point to the real Ziplist (zL pointer). The other nodes in the middle are compressed and their data Pointers point to quicklistLZF

Application scenarios

1. Message queue (no ACK mechanism)

// Producers use Lpush to put a message into a list, and consumers can retrieve the message via RPOP and keep the order of the message.
>lpush message "ces"
(integer) 1
>rpop message
"ces"
Copy the code

2. The timeline

// One scenario is when the user sends a tweet, lpush it to the list, and then lrange can retrieve the latest tweet information
> lpush weibo "xiaoxi1"
(integer) 1
> lpush weibo "xiaoxi2"
(integer) 2
> lpush weibo "xiaoxi3"
(integer) 3
> lrange weibo 0 9
1) "xiaoxi3"
2) "xiaoxi2"
3) "xiaoxi1"
Copy the code

Redis from Getting Started to Giving up series (three) List