• preface
  • define
  • conclusion
  • Refer to the article
  • To contact me

preface

Redis is already familiar to everyone. It is also used in daily work and frequently involved in interviews. So how deep do we know about it?

I read several books related to Redis and tried to understand its concrete implementation, and recorded some underlying data structures and implementation principles.

This article introduces the implementation of the low-level Listpack (compact list) in Redis. It is one of the data structures used by Redis’s Stream.

define

Redis design listpack is to replace Ziplist, in the Redis series (3) of the underlying data structure of the compression list we mentioned that Ziplist in a very small probability is possible to cascade updates, when the continuous scale of the larger cascade updates occur, The performance of Redis is greatly affected.

While we all know that this is a very small probability, this design flaw was not accepted by the Redis authors, so a new data structure was introduced in version 5.0 called ListPack, which everyone translates as a compact list.

Its definition is very similar to Ziplist, but with some new design, to solve the ziplist pain point problem. Therefore, this article is based on what you already know about Ziplist.

Ziplist is defined as follows: Note: This is the definition of ziplist

struct ziplist<T>{
    // The number of bytes for the entire compressed list
    int32 zlbytes;
    // The offset from the last node to the start of the compressed list can be used to quickly locate the last element in the compressed list
    int32 zltail_offset;
    // Compress the number of elements in the list
    int16 zllength;
    // List of element contents, stored in arrays, next to each other in memory
    T[] entries;
    // The end flag bit of the compressed list, always 0xFF.
    int8 zlend;
}
Copy the code

The listpack definition is basically the same as above, except that the ZLtail_offset attribute is removed.

Let’s recall, what does Ziplist do with this property? It is used to conveniently find the last node, and then facilitate reverse traversal. The new ListPack of course solves this problem and can be relieved to remove this attribute.

The listPack node is defined as follows:

int<var> encoding;
optional byte[] content;
int<var> length;
Copy the code

There are two changes to ziplist’s definition:

  1. The length of the record is no longer the length of the previous node, but its own length.
  2. Put the length of the record itself at the end of the node.

The benefits of this are:

  1. The zltail_offset attribute is not required to quickly locate the last node. withTotal length of listPAC - the length of the last node.
  2. Each node records its own length. When the value of this node changes, you only need to change its own length. There is no need to change the properties of other nodes, which completely solves the cascading update problem.

conclusion

Listpack is a data structure designed by Redis to replace Ziplist. It completely solves ziplist’s cascading update problem by recording the length of each node and placing it at the end of the node.

Listpack was introduced in version 5.0, but due to the widespread use of Ziplist within Reids, there are some compatibility issues and we can expect this to be a gradual replacement process.

Also in the Stream data structure introduced in version 5.0, listPack is used instead of Ziplist.

Refer to the article

Design and Implementation of Redis (2nd Edition)

Redis Deep Adventures: Core Principles and Practical Applications

To the end.

To contact me

Finally, welcome to follow my personal public account [Huyanshi], I will update many backend engineers’ study notes from time to time. Also welcome direct public number private letter or mailbox to contact me, must know all without reserve, endless.


All the above are personal thoughts, if there is any mistake welcome to comment.

Welcome to reprint, please sign and keep the original link.

Contact email: [email protected]

For more study notes, see personal blog or follow wechat official account < huyan10 >——>HuYan ten