Loading... # Redis列表list底层原理 > 原文地址: https://zhuanlan.zhihu.com/p/102422311 在版本3.2之前，Redis列表list使用两种数据结构作为底层实现: - 压缩列表ziplist - 双向链表linkedlist 因为双向链表占用的内存比压缩列表要多， 所以当创建新的列表键时， 列表会优先考虑使用压缩列表， 并且在有需要的时候， 才从压缩列表实现转换到双向链表实现。 ###压缩列表转化成双向链表条件 创建新列表时 redis 默认使用 redis_encoding_ziplist 编码， 当以下任意一个条件被满足时， 列表会被转换成 redis_encoding_linkedlist 编码： - 试图往列表新添加一个字符串值，且这个字符串的长度超过 server.list_max_ziplist_value （默认值为 64）。 - ziplist 包含的节点超过 server.list_max_ziplist_entries （默认值为 512 ）。 注意：这两个条件是可以修改的，在 redis.conf 中： ``` list-max-ziplist-value 64 list-max-ziplist-entries 512 ``` ## 双向链表linkedlist 当链表entry数据超过512、或单个value 长度超过64，底层就会转化成linkedlist编码；linkedlist是标准的双向链表，Node节点包含prev和next指针，可以进行双向遍历；还保存了 head 和 tail 两个指针，因此，对链表的表头和表尾进行插入的复杂度都为 (1) —— 这是高效实现 LPUSH 、 RPOP、 RPOPLPUSH 等命令的关键。linkedlist比较简单，我们重点来分析ziplist。 ## 压缩列表ziplist 压缩列表 ziplist 是为 Redis 节约内存而开发的。 Redis官方对于ziplist的定义是（出自ziplist.c的文件头部注释）： ``` /* The ziplist is a specially encoded dually linked list that is designed * to be very memory efficient. It stores both strings and integer values, * where integers are encoded as actual integers instead of a series of * characters. It allows push and pop operations on either side of the list * in O(1) time. However, because every operation requires a reallocation of * the memory used by the ziplist, the actual complexity is related to the * amount of memory used by the ziplist. * ``` ziplist 是由一系列特殊编码的内存块构成的列表(像内存连续的数组，但每个元素长度不同)， 一个 ziplist 可以包含多个节点（entry）。ziplist 将表中每一项存放在前后连续的地址空间内，每一项因占用的空间不同，而采用变长编码。 当元素个数较少时，Redis 用 ziplist 来存储数据，当元素个数超过某个值时，链表键中会把 ziplist 转化为 linkedlist，字典键中会把 ziplist 转化为 hashtable。由于内存是连续分配的，所以遍历速度很快。 在3.2之后，ziplist被quicklist替代。但是仍然是zset底层实现之一。 ### ziplist 是一个特殊的双向链表 特殊之处在于：没有维护双向指针:prev next；而是存储上一个 entry的长度和 当前entry的长度，通过长度推算下一个元素在什么地方。 牺牲读取的性能，获得高效的存储空间，因为(简短字符串的情况)存储指针比存储entry长度 更费内存。这是典型的“时间换空间”。 ### ziplist使用局限性 字段、值比较小，才会用ziplist。 ### 压缩列表ziplist存储结构 ziplist使用连续的内存块，每一个节点（entry）都是连续存储的。由于每一项、占用的空间可能都不同，只能在添加entry的时候确定，也就是每个entry占用的实际长度只有在节点添加后才确定，因此**entry采用变长编码。** ### ziplist节点entry结构 ziplist每一个存储节点、都是一个 zlentry，就是上文我们所说的entry； zlentry的源码定义： ``` typedef struct zlentry { // 压缩列表节点 unsigned int prevrawlensize, prevrawlen; // prevrawlen是前一个节点的长度，prevrawlensize是指prevrawlen的大小，有1字节和5字节两种 unsigned int lensize, len; // len为当前节点长度 lensize为编码len所需的字节大小 unsigned int headersize; // 当前节点的header大小 unsigned char encoding; // 节点的编码方式 unsigned char *p; // 指向节点的指针 } zlentry; void zipEntry(unsigned char *p, zlentry *e) { // 根据节点指针返回一个enrty ZIP_DECODE_PREVLEN(p, e->prevrawlensize, e->prevrawlen); // 获取prevlen的值和长度 ZIP_DECODE_LENGTH(p + e->prevrawlensize, e->encoding, e->lensize, e->len); // 获取当前节点的编码方式、长度等 e->headersize = e->prevrawlensize + e->lensize; // 头大小 e->p = p; } ``` 可见，每一个存储节点 zlentry，都包含 - prevrawlen 前一个 entry的长度 - lensize 当前entry的长度 #### 如何通过一个节点向前跳转到另一个节点？ 用指向当前节点的指针 e ， 减去 前一个 entry的长度， 得出的结果就是指向前一个节点的地址 p 。 #### 完整的zlentry由以下3各部分组成： - prevrawlen：记录前一个节点所占有的内存字节数，通过该值，我们可以从当前节点计算前一个节点的地址，可以用来实现表尾向表头节点遍历； - len/encoding：记录了当前节点content占有的内存字节数及其存储类型，用来解析content用； - content：保存了当前节点的值。最关键的是prevrawlen和len/encoding，content只是实际存储数值的比特位。 #### prevrawlen是变长编码，有两种表示方法： - 如果前一节点的长度小于 254 字节，则使用1字节(uint8_t)来存储prevrawlen； - 如果前一节点的长度大于等于 254 字节，那么将第 1 个字节的值设为 254 ，然后用接下来的 4 个字节保存实际长度。 ### ziplist连锁更新问题 因为在ziplist中，每个zlentry都存储着前一个节点所占的字节数，而这个数值又是**变长编码**的。假设存在一个压缩列表，其包含e1、e2、e3、e4…..，e1节点的大小为253字节，那么e2.prevrawlen的大小为1字节，如果此时在e2与e1之间插入了一个新节点e_new，e_new编码后的整体长度（包含e1的长度）为**254字节**，此时e2.prevrawlen就需要扩充为**5字节**；如果e2的整体长度变化又引起了e3.prevrawlen的存储长度变化，那么e3也需要扩…….如此递归直到表尾节点或者某一个节点的prevrawlen本身长度可以容纳前一个节点的变化。**其中每一次扩充都需要进行空间再分配操作**。删除节点亦是如此，只要引起了操作节点之后的节点的prevrawlen的变化，都可能引起连锁更新。 连锁更新在最坏情况下需要进行N次空间再分配，而每次空间再分配的最坏时间复杂度为O(N)，因此连锁更新的总体时间复杂度是O(N^2)。 即使涉及连锁更新的时间复杂度这么高，但它能引起的性能问题的概率是极低的：需要列表中存在大量的节点长度接近254的zlentry。 由于ziplist连锁更新的问题，也使得ziplist的优缺点极其明显；也使得后续Redis采取折中，替换了ziplist。 ziplist的主要优点是节省内存，但它上面的查找操作只能按顺序查找（可以是从前往后、也可以从后往前）。 ziplist将数据按照一定规则编码在一块连续的内存区域，目的是节省内存，这种结构并不擅长做修改操作。一旦数据发生改动，就会引发内存realloc，可能导致内存拷贝。 ## Redis3.2+ list的新实现quickList Redis中的列表list，在版本3.2之前，列表底层的编码是ziplist和linkedlist实现的，但是在版本3.2之后，重新引入 quicklist，列表的底层都由quicklist实现。 在版本3.2之前，当列表对象中元素的长度比较小或者数量比较少的时候，采用ziplist来存储，当列表对象中元素的长度比较大或者数量比较多的时候，则会转而使用双向列表linkedlist来存储。 **这两种存储方式的优缺点** - 双向链表linkedlist便于在表的两端进行push和pop操作，在插入节点上复杂度很低，但是它的内存开销比较大。首先，它在每个节点上除了要保存数据之外，还要额外保存两个指针；其次，双向链表的各个节点是单独的内存块，地址不连续，节点多了容易产生内存碎片。 - ziplist存储在一段连续的内存上，所以存储效率很高。但是，它不利于修改操作，插入和删除操作需要频繁的申请和释放内存。特别是当ziplist长度很长的时候，一次realloc可能会导致大批量的数据拷贝。 ### quickList 可以认为quickList，是ziplist和linkedlist二者的结合；quickList将二者的优点结合起来。 官方给出的定义 ``` A generic doubly linked quicklist implementation A doubly linked list of ziplists ``` quickList是一个ziplist组成的双向链表。每个节点使用ziplist来保存数据。 本质上来说，quicklist里面保存着一个一个小的ziplist。结构如下： ![v2-800dbf77bba29897de1ad769d0149f8f_720w.jpg][1] ``` /* 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: 12 bits, free for future use; pads out the remainder of 32 bits */ typedef struct quicklistNode { struct quicklistNode *prev; //上一个node节点 struct quicklistNode *next; //下一个node unsigned char *zl; //保存的数据 压缩前ziplist 压缩后压缩的数据 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; /* quicklist is a 32 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 int 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; ``` quickList就是一个标准的双向链表的配置，有head 有tail; 每一个节点是一个quicklistNode，包含prev和next指针。 每一个quicklistNode 包含 一个ziplist，*zp 压缩链表里存储键值。 所以quicklist是对ziplist进行一次封装，使用小块的ziplist来既保证了少使用内存，也保证了性能。 ## 列表list其他实现点 Redis列表list底层的编码分析完了，我们再来探讨两个list其他的实现点： ### list是如何实现阻塞队列的？ 阻塞队列，就像ArrayBlockingQueue那样，消费端取数据时，如果列表为空，就阻塞。Redis是如何实现的呢？ `blpop 、 brpop 和 brpoplpush`这个几个阻塞命令的实现原理： 只有当这些命令被用于空列表时， 它们才会阻塞客户端。 阻塞一个客户端需要执行以下步骤： - 将客户端的状态设为“正在阻塞”，并记录阻塞这个客户端的各个键，以及阻塞的最长时限（timeout）等数据。 - 将客户端的信息记录到 server.db[i]->blocking_keys 中（其中 i 为客户端所使用的数据库号码）。 - 继续维持客户端和服务器之间的网络连接，但不再向客户端传送任何信息，造成客户端阻塞。 步骤 2 是将来解除阻塞的关键， server.db[i]->blocking_keys 是一个字典， 字典的键是那些造成客户端阻塞的键， 而字典的值是一个链表， 链表里保存了所有因为这个键而被阻塞的客户端 （被同一个键所阻塞的客户端可能不止一个）： ![v2-55a09b68f9d07f82d490d9afbb9105cb_720w.jpg][2] ### ziplist和linkedlist 编码下的list，列表操作命令底层实现不同 `lpush、rpush、lpop、rpop`等进行列表操作，这些命令在不同编码的列表对象下的实现方法是不同的。 对linkedlist来说，这些命令都是基于prev、next、head、tail指针完成的，双向链表基于指针，实现比较容易。 而ziplist则是 通过当前entry的指针，加减位移的偏移量(前一个entry的长度)，进行跳跃节点。 [1]: https://www.princelei.club/usr/uploads/2020/11/1218543676.jpg [2]: https://www.princelei.club/usr/uploads/2020/11/3224119560.jpg Last modification：November 27th, 2020 at 05:32 pm © 允许规范转载
