Rpush adds values to the end of the list

> rpush mylist "a" "b"
(integer2)Copy the code

Use lrange to view inserted values

> lrange mylist 0 2
1) "a"
2) "b"
Copy the code

Linsert can insert values before or after a specified element

> linsert mylist before "m" "l"
-1
> linsert mylist before "d" "e"
5
> lrange mylist 0 -1
1) "e"
2) "d"
3) "c"
4) "a"
5) "b"
Copy the code

If the specified element does not exist, it will not be inserted

Rpop can correspond to the value at the end of the pop-up queue

> lrange mylist 0 -1
1) "e"
2) "d"
3) "c"
4) "a"
5) "b"
6) "a"
7) "b"
8) "c"
> rpop mylist
"c"
Copy the code

The rpush command performs tracing

The entry to rpush is in rpushCommand

Code.SLICE.source("robj *lobj = lookupKeyWrite(c->db,c->argv[1]); \n" +
        "\n" +
        " if (lobj && lobj->type ! = OBJ_LIST) {\n" +
        " addReply(c,shared.wrongtypeerr); \n" +
        " return; \n" +
        "}")
        .interpretation("Find if there was a key with the same name before, if there is, but the key encoding is not OBJ_LIST will return an error.");
Code.SLICE.source("for (j = 2; j < c->argc; j++) ")
        .interpretation("Go through all the values, insert them one by one.");
Code.SLICE.source("if (! lobj) {\n" +
        " lobj = createQuicklistObject(); \n" +
        " quicklistSetOptions(lobj->ptr, server.list_max_ziplist_size,\n" +
        " server.list_compress_depth); \n" +
        " dbAdd(c->db,c->argv[1],lobj); \n" +
        " }\n" +
        " listTypePush(lobj,c->argv[j],where); \n" +
        " pushed++;")
        .interpretation("If the exact same key didn't exist before, create a new one, quickList, save it, insert it.");
Copy the code

Insert, associated with a data structure, is a QuickList, each node of which is a QuickList node

doubly linked list

A regular Redis bidirectional list looks like this

[0] <-> [1] <-> [2] <->... <-> [N]Copy the code
  • The listNode for each node contains three Pointers: prev/ Next /value (the three Pointers are 24 bytes long). – Each data point to a redisObject, which contains 32bit metadata, a reference to an int, and a pointer to the content (16 bytes in total).
  • The value inside the redisObject is SDS, which consists of two int fields and string contents (total 4 bytes +contents).

That is, each node contains at least 40 bytes of metadata content, as well as some other internal allocation for calculation, so if you only insert a string of 10 characters internally, it is obvious that the space of the element data exceeds the content of the storage, which is wasteful

ziplist

Redis uses Ziplist to solve the problem of storing small amounts of data in a conventional bidirectional linked list. Its structure is as follows

[total size][tail offset][cached element count][entry 0]... [entry N][END]Copy the code

An empty Ziplist takes up only 11 bytes

[size=4 bytes][tail offset=4 bytes][count=2 bytes][END=1 byte]
Copy the code

For each entry, its structure is

[length of previous entry][length of this entry][contents]
Copy the code
  1. The length of the previous entry is used to ensure reverse traversal.
  2. Ziplist uses variable length encoding and smaller offsets if small content is stored

But this approach has created problems

  1. Each insertion of an element requires that subsequent elements be moved back, and insertion means that memory needs to be reallocated
  2. When you delete an element, all elements move forward

That means ziplist is best kept small for the most efficient use of space and time

quicklist

The structure of a QuickList looks like this

[ziplist 0] <-> [ziplist 1] <-> ... <-> [ziplist N]
Copy the code

Control the number of Ziplist entries on each node by list-max-ziplist-entries, or create a QuickListNode if the limit is exceeded. advantage

  1. A list of any length is an efficient use of memory
  2. Again, O(1) gets the head and tail
  3. Deleting a list of an area improves efficiency
  4. The original RDB and AOF formats are maintained
  5. If you limit each Ziplist to one entry, it converts to the original Linked List with better memory utilization

This approach also introduces additional operations

  1. To insert elements in the middle of a QuickList, you may need to take apart the original Ziplist and create additional QuickListNodes
  2. To remove elements from quickList, you need to merge multiple Ziplists
  3. All inserts mean that ziplist needs to be reallocated
  4. Insertion in the header requires the original Ziplist entity to be moved back

The structure of QuickList is as follows

Code.SLICE.source("typedef struct quicklist {" +
        " quicklistNode *head; /* header */" +
        " quicklistNode *tail; /* end */" +
        " unsigned long count; /* The number of entries in all ziplists */\n" +
        " unsigned long len; /* Number of quicklistNodes */\n" +
        " int fill : 16; List-max-ziplist-size */\n" +
        " unsigned int compress : 16; /* list_compress_depth */\n" +
        "} quicklist;")
        .interpretation("Head and tail function Pointers are up to 8 bytes long,count and len are up to 8 bytes unsigned long, and the last two fields have a total of 32bits for a total of 40 bytes.")
        .interpretation("List-max-ziplist-size A positive number is used to limit the ziplist size. For example, 5 indicates that each QuickList node ziplist contains a maximum of five items. The maximum value is 1 << 15. +
                "-1 indicates that the ziplist size on each QuickList node cannot exceed 4KB,-2(the default) indicates that the ziplist size cannot exceed 8KB, and so on, up to -5, which cannot exceed 64KB.")
        .interpretation("List_compress_depth 0 = uncompressed,1 = 1 on each end of the QuickList, 2 = 2 on each end of the QuickList, the rest of the quickList, and so on, up to 1 << 16"); / /... Code.SLICE.source("typedef struct quicklistNode {\n" +
        " struct quicklistNode *prev; /* The first node of the current node */" +
        " struct quicklistNode *next; /* Next node of the current node */" +
        " unsigned char *zl; /* Data pointer. If the current node is not compressed, it points to a ziplist, otherwise quicklistLZF*/" +
        " unsigned int sz; /* zl refers to the total size of the ziplist, the calculation is compressed, also refers to the size before compression */\n" +
        " unsigned int count : 16; /* Number of items in ziplist */\n" +
        " unsigned int encoding : 2; /* RAW==1 or LZF==2 */\n" +
        " unsigned int container : 2; /* NONE==1 or ZIPLIST==2 */\n" +
        " unsigned int recompress : 1; /* Check whether the data is compressed before, such as the process of decompressing the data needs to be restored after */\n" +
        " unsigned int attempted_compress : 1; /* node can't compress; too small */\n" +
        " unsigned int extra : 10; /* extension field */\n" +
        "} quicklistNode;")
        .interpretation("From front to back,quickList itself is a bidirectional list.")
        .interpretation(1: structure size prev, next, zl,sz unsigned int,sz unsigned int,sz unsigned int,sz unsigned int);
Copy the code

Quicklistnode itself can be compressed based on how far the node is from head/tail for even greater space savings

conclusion

Each QuickList node stores a configurable amount of Ziplist. If there are multiple QuickList Nodes, the ziplist will be compressed using the LZF algorithm according to the configured compression depth

The appendix

Rpush source tracking quickList and other list implementation comparison and performance test notes Matt.sh Redis internal data structure (5) — QuickList zhang Tieley (4) — Ziplist Zhang Tieley Redis design and implementation RedIS development and operation