Redis list of five data structures

Article Directory

1. What is a list?

2. List storage structure

1. Before Redis 3.2

2. Versions after Redis 3.2

ziplist

quicklist

Three, basic commands

Four, application scenarios



1. What is a list?

List is a basic data structure of redis. It is implemented internally using a doubly linked list (quicklist), so the time complexity of adding elements to the two ends of the list is O(1), and the closer to the two ends, the faster the speed of obtaining elements.

2. List storage structure

1. Before Redis 3.2

The value object of the list type is implemented internally by a linkedlist or a ziplist.

When the number of elements of the list and the length of a single element are relatively small , Redis will use ziplist to compress the list to reduce memory usage. Otherwise, the linkedlist structure will be adopted.

Both storage methods have advantages and disadvantages:

A doubly linked list performs push and pop operations at both ends of the linked list. The complexity on the insertion node is relatively low, but the memory overhead is relatively large;

Ziplist is stored in a continuous memory, so the storage efficiency is very high, but insertion and deletion require frequent application and release of memory;

2. Versions after Redis 3.2

Using quicklist, quicklist is also a doubly linked list, but each node of the list is a ziplist, which is actually a combination of linkedlist and ziplist. Each node ziplist in quicklist can store multiple data elements. The quicklist saves the head and tail nodes, which can be easily operated on both ends.

ziplist

Let's talk about ziplist first: the compressed list is developed by redis in order to save memory. It is an ordered data structure composed of a series of specially coded continuous memory blocks.

It is used in list/hash/zset.

Let me talk about the structure of ziplist, as shown in the figure.

 *  [0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff] *        |             |          |       |       |     | *     zlbytes        zltail    entries   "2"     "5"   end

The above is the structure of a ziplist, with two entries, "2" and "5".

zlbyte: occupies 4 bytes, indicating the length of the ziplist;

zltail: occupies 4 bytes, indicating the offset of the last entry, that is, the offset to "5", which is 0x0c;

entries: 2 bytes, the number of entries, there are two entries in total;

entry: follow-up analysis;

end: 0xff, end marker bit.

For the structure of ziplist entry, please refer to the note for details:

/* We use this function to receive information about a ziplist entry. * Note that this is not how the data is actually encoded, is just what we * get filled by a function in order to operate more easily. */typedef struct zlentry {  // 压缩列表节点    // prevrawlensize是指prevrawlen的大小,有1字节和5字节两种    unsigned int prevrawlensize; /* Bytes used to encode the previous entry len*/        //  prevrawlen是前一个zlentry节点的长度    unsigned int prevrawlen;     /* Previous entry len. */     // lensize为编码len所需的字节大小    unsigned int lensize;        /* Bytes used to encode this entry type/len.                                    For example strings have a 1, 2 or 5 bytes                                    header. Integers always use a single byte.*/     // len为当前节点长度    unsigned int len;            /* Bytes used to represent the actual entry.                                    For strings this is just the string length                                    while for integers it is 1, 2, 3, 4, 8 or                                    0 (for 4 bit immediate) depending on the                                    number range. */     // 当前节点的header大小    unsigned int headersize;     /* prevrawlensize + lensize. */     // 节点的编码方式    unsigned char encoding;      /* Set to ZIP_STR_* or ZIP_INT_* depending on                                    the entry encoding. However for 4 bits                                    immediate integers this can assume a range                                    of values and must be range-checked. */        // 指向节点的指针    unsigned char *p;            /* Pointer to the very start of the entry, that                                    is, this points to prev-entry-len field. */} zlentry;

Zlentry can be easily understood by three parts: prevlength, encoding, data

  • prevlength: record the length of the previous node, in order to facilitate reverse traversal of the ziplist
  • encoding: The encoding rules of the current node.
  • data: the value of the current node, which can be a number or a string
  • If the first 8 bits of entry are less than 254, these 8 bits represent the length of the previous node
  • If the first 8 bits of the entry are equal to 254, it means that the length of the previous node cannot be represented by 8 bits, and the last 32 bits are the real prevlength. Use 254 instead of 255 (11111111) as the boundary because 255 is the value of zlend, which is used to determine whether the ziplist has reached the end.

quicklist

quicklist.c - A doubly linked list of ziplists //ziplist 的双向链表  /* Minimum ziplist size in bytes for attempting compression. */#define MIN_COMPRESS_BYTES 48  /* Minimum size reduction in bytes to store compressed quicklistNode data. * This also prevents us from storing compression if the compression * resulted in a larger size than the original data. */#define MIN_COMPRESS_IMPROVE 8

As you can see from quicklist.c, the basis for whether the data in the list is compressed:
 * If the length of the element is less than 48, no compression;
 * The difference between the length of the element before and after compression is no more than 8, no compression;

The structure of quicklistNode is explained as follows, you can clearly see that each node is a ziplist:

/* 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 temporary 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;           /* ziplist的地址 */    unsigned int sz;             /* ziplist 大小(字节) */    unsigned int count : 16;     /* 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;

The structure of quicklist is described as follows:

/* 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: 0 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. * 'bookmakrs are an optional feature that is used by realloc this struct, *      so that they don't consume memory when not used. */typedef struct quicklist {    quicklistNode *head;        /* 头结点 */    quicklistNode *tail;        /* 尾结点 */    unsigned long count;        /* 在所有ziplist中entry的个数总和 */    unsigned long len;          /* quicklistNodes的个数 */    int fill : QL_FILL_BITS;    /* ziplist大小限定,由server.list_max_ziplist_size给定 */    unsigned int compress : QL_COMP_BITS; /* 节点压缩深度设置,由server.list-compress-depth给定,0表示关闭压缩 */    unsigned int bookmark_count: QL_BM_BITS;    quicklistBookmark bookmarks[];} quicklist;

Three, basic commands

# 从队列的左侧入队一个或多个元素LPUSH key value [value ...] # 从队列的左侧弹出一个元素LPOP key # 从队列的右侧入队一个或多个元素RPUSH key value [value ...] # 从队列的右侧弹出一个元素RPOP key # 获取list从start到end之间的元素[start, end]LRANGE key start end # 移除从表头到表尾,最先发现的count 个 valueLREM key count value # RPOP 的阻塞版本,当list中没有元素,该命令会阻塞BRPOP key timeout # 裁剪最近5条记录ltrim key 0 4

Four, application scenarios

1. The latest news list and other functions, such as Weibo, Moments, Likes, etc.

2. Message queue (not recommended, data may be lost when redis is closed unexpectedly)

3. Stack, queue, blocking queue