神级Redis列表实现原理之quicklist结构解析

冷不防 2023-09-30 10:12 16阅读 0赞

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y2B5LiA5oqA5pyv5pap_size_20_color_FFFFFF_t_70_g_se_x_16][]

本文分析：quicklist结构如何解决这个问题并实现Redis的列表类型。

quicklist的设计思想很简单，将一个长ziplist拆分为多个短ziplist，避免插入或删除元素时导致大量的内存拷贝。  
ziplist存储数据的形式更类似于数组，而quicklist是真正意义上的链表结构，它由quicklistNode节点链接而成，在quicklistNode中使用ziplist存储数据。

> 提示：本文以下代码如无特殊说明，均位于quicklist.h/quicklist.c中。  
> 本文以下说的“节点”，如无特殊说明，都指quicklistNode节点，而不是ziplist中的节点。

#### 定义 ####

quicklistNode的定义如下：

typedef struct quicklistNode {
        struct quicklistNode *prev;
        struct quicklistNode *next;
        unsigned char *zl;
        unsigned int sz;             
        unsigned int count : 16;  
        unsigned int encoding : 2; 
        unsigned int container : 2; 
        unsigned int recompress : 1;
        unsigned int attempted_compress : 1;
        unsigned int extra : 10; 
    } quicklistNode;

*  prev、next：指向前驱节点，后驱节点。
 *  zl：ziplist，负责存储数据。
 *  sz：ziplist占用的字节数。
 *  count：ziplist的元素数量。
 *  encoding：2代表节点已压缩，1代表没有压缩。
 *  container：目前固定为2，代表使用ziplist存储数据。
 *  recompress：1代表暂时解压（用于读取数据等），后续需要时再将其压缩。
 *  extra：预留属性，暂未使用。

当链表很长时，中间节点数据访问频率较低。这时Redis会将中间节点数据进行压缩，进一步节省内存空间。Redis采用是无损压缩算法—LZF算法。  
压缩后的节点定义如下：

typedef struct quicklistLZF {
        unsigned int sz;
        char compressed[];
    } quicklistLZF;

*  sz：压缩后的ziplist大小。
 *  compressed：存放压缩后的ziplist字节数组。

quicklist的定义如下：

typedef struct quicklist {
        quicklistNode *head;
        quicklistNode *tail;
        unsigned long count;        
        unsigned long len;          
        int fill : QL_FILL_BITS;              
        unsigned int compress : QL_COMP_BITS;
        unsigned int bookmark_count: QL_BM_BITS;
        quicklistBookmark bookmarks[];
    } quicklist;

*  head、tail：指向头节点、尾节点。
 *  count：所有节点的ziplist的元素数量总和。
 *  len：节点数量。
 *  fill：16bit，用于判断节点ziplist是否已满。
 *  compress：16bit，存放节点压缩配置。

quicklist的结构如图2-5所示。

![48906d77e872c6da6115dce126a6fc51.png][]

图2-5

#### 操作分析 ####

插入元素到quicklist头部：

int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {
        quicklistNode *orig_head = quicklist->head;
        // [1]
        if (likely(
                _quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) {
            // [2]
            quicklist->head->zl =
                ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD);
            // [3]
            quicklistNodeUpdateSz(quicklist->head);
        } else {
            // [4]
            quicklistNode *node = quicklistCreateNode();
            node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);
    
            quicklistNodeUpdateSz(node);
            _quicklistInsertNodeBefore(quicklist, quicklist->head, node);
        }
        quicklist->count++;
        quicklist->head->count++;
        return (orig_head != quicklist->head);
    }

参数说明：

*  value、sz：插入元素的内容与大小。

【1】判断head节点ziplist是否已满，\_quicklistNodeAllowInsert函数中根据quicklist.fill属性判断节点是否已满。  
【2】head节点未满，直接调用ziplistPush函数，插入元素到ziplist中。  
【3】更新quicklistNode.sz属性。  
【4】head节点已满，创建一个新节点，将元素插入新节点的ziplist中，再将该节点头插入quicklist中。

也可以在quicklist的指定位置插入元素：

REDIS_STATIC void _quicklistInsert(quicklist *quicklist, quicklistEntry *entry,
                                       void *value, const size_t sz, int after) {
        int full = 0, at_tail = 0, at_head = 0, full_next = 0, full_prev = 0;
        int fill = quicklist->fill;
        quicklistNode *node = entry->node;
        quicklistNode *new_node = NULL;
        ...
        // [1]
        if (!_quicklistNodeAllowInsert(node, fill, sz)) {
            full = 1;
        }
    
        if (after && (entry->offset == node->count)) {
            at_tail = 1;
            if (!_quicklistNodeAllowInsert(node->next, fill, sz)) {
                full_next = 1;
            }
        }
    
        if (!after && (entry->offset == 0)) {
            at_head = 1;
            if (!_quicklistNodeAllowInsert(node->prev, fill, sz)) {
                full_prev = 1;
            }
        }
        // [2]
        ...
    }

参数说明：

*  entry：quicklistEntry结构，quicklistEntry.node指定元素插入的quicklistNode节点，quicklistEntry.offset指定插入ziplist的索引位置。
 *  after：是否在quicklistEntry.offset之后插入。

【1】根据参数设置以下标志。

*  full：待插入节点ziplist是否已满。
 *  at\_tail：是否ziplist尾插。
 *  at\_head：是否ziplist头插。
 *  full\_next：后驱节点是否已满。
 *  full\_prev：前驱节点是否已满。

> 提示：头插指插入链表头部，尾插指插入链表尾部。

【2】根据上面的标志进行处理，代码较烦琐，这里不再列出。  
这里的执行逻辑如表2-2所示。

<table> 
 <thead> 
  <tr> 
   <th>条件</th> 
   <th>条件说明</th> 
   <th>处理方式</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>!full &amp;&amp; after</td> 
   <td>待插入节点未满，ziplist尾插</td> 
   <td>再次检查ziplist插入位置是否存在后驱元素，如果不存在则调用ziplistPush函数插入元素（更快），否则调用ziplistInsert插入元素</td> 
  </tr> 
  <tr> 
   <td>!full &amp;&amp; !after</td> 
   <td>待插入节点未满，非ziplist尾插</td> 
   <td>调用ziplistInsert函数插入元素</td> 
  </tr> 
  <tr> 
   <td>full &amp;&amp; at_tail &amp;&amp; node -&gt; next &amp;&amp; !full_next &amp;&amp; after</td> 
   <td>待插入节点已满，尾插，后驱节点未满</td> 
   <td>将元素插入后驱节点ziplist中</td> 
  </tr> 
  <tr> 
   <td>full &amp;&amp; at_head &amp;&amp; node -&gt; prev &amp;&amp; !full_prev &amp;&amp; !after</td> 
   <td>待插入节点已满，ziplist头插，前驱节点未满</td> 
   <td>将元素插入前驱节点ziplist中</td> 
  </tr> 
  <tr> 
   <td>full &amp;&amp; ((at_tail &amp;&amp; node -&gt; next &amp;&amp; full_next &amp;&amp; after) ||(at_head &amp;&amp; node-&gt;prev &amp;&amp; full_prev &amp;&amp; !after))</td> 
   <td>满足以下条件：(1)待插入节点已满&nbsp; (2)尾插且后驱节点已满，或者头插且前驱节点已满</td> 
   <td>构建一个新节点，将元素插入新节点，并根据after参数将新节点插入quicklist中</td> 
  </tr> 
  <tr> 
   <td>full</td> 
   <td>待插入节点已满，并且在节点ziplist中间插入</td> 
   <td>将插入节点的数据拆分到两个节点中，再插入拆分后的新节点中</td> 
  </tr> 
 </tbody> 
</table>

我们只看最后一种场景的实现：

// [1]
        quicklistDecompressNodeForUse(node);
        // [2]
        new_node = _quicklistSplitNode(node, entry->offset, after);
        new_node->zl = ziplistPush(new_node->zl, value, sz,
                                    after ? ZIPLIST_HEAD : ZIPLIST_TAIL);
        new_node->count++;
        quicklistNodeUpdateSz(new_node);
        // [3]
        __quicklistInsertNode(quicklist, node, new_node, after);
        // [4]
        _quicklistMergeNodes(quicklist, node);

【1】如果节点已压缩，则解压节点。  
【2】从插入节点中拆分出一个新节点，并将元素插入新节点中。  
【3】将新节点插入quicklist中。  
【4】尝试合并节点。\_quicklistMergeNodes尝试执行以下操作：

*  将node->prev->prev合并到node->prev。
 *  将node->next合并到node->next->next。
 *  将node->prev合并到node。
 *  将node合并到node->next。  
    合并条件：如果合并后节点大小仍满足quicklist.fill参数要求，则合并节点。  
    这个场景处理与B+树的节点分裂合并有点相似。

quicklist常用的函数如表2-3所示。

<table> 
 <thead> 
  <tr> 
   <th>函数</th> 
   <th>作用</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>quicklistCreate、quicklistNew</td> 
   <td>创建一个空的quicklist</td> 
  </tr> 
  <tr> 
   <td>quicklistPushHead，quicklistPushTail</td> 
   <td>在quicklist头部、尾部插入元素</td> 
  </tr> 
  <tr> 
   <td>quicklistIndex</td> 
   <td>查找给定索引的quicklistEntry节点</td> 
  </tr> 
  <tr> 
   <td>quicklistDelEntry</td> 
   <td>删除给定的元素</td> 
  </tr> 
 </tbody> 
</table>

**配置说明**

*  list-max-ziplist-size：配置server.list\_max\_ziplist\_size属性，该值会赋值给quicklist.fill。取正值，表示quicklist节点的ziplist最多可以存放多少个元素。例如，配置为5，表示每个quicklist节点的ziplist最多包含5个元素。取负值，表示quicklist节点的ziplist最多占用字节数。这时，它只能取-1到-5这五个值（默认值为-2），每个值的含义如下：  
    \-5：每个quicklist节点上的ziplist大小不能超过64 KB。  
    \-4：每个quicklist节点上的ziplist大小不能超过32 KB。  
    \-3：每个quicklist节点上的ziplist大小不能超过16 KB。  
    \-2：每个quicklist节点上的ziplist大小不能超过8 KB。  
    \-1：每个quicklist节点上的ziplist大小不能超过4 KB。
 *  list-compress-depth：配置server.list\_compress\_depth属性，该值会赋值给quicklist.compress。  
    0：表示节点都不压缩，Redis的默认配置。  
    1：表示quicklist两端各有1个节点不压缩，中间的节点压缩。  
    2：表示quicklist两端各有2个节点不压缩，中间的节点压缩。  
    3：表示quicklist两端各有3个节点不压缩，中间的节点压缩。  
    以此类推。

#### 编码 ####

ziplist由于结构紧凑，能高效使用内存，所以在Redis中被广泛使用，可用于保存用户列表、散列、有序集合等数据。  
列表类型只有一种编码格式OBJ\_ENCODING\_QUICKLIST，使用quicklist存储数据（redisObject.ptr指向quicklist结构）。列表类型的实现代码在t\_list.c中，读者可以查看源码了解实现更多细节。

**总结**

*  ziplist是一种结构紧凑的数据结构，使用一块完整内存存储链表的所有数据。
 *  ziplist内的元素支持不同的编码格式，以最大限度地节省内存。
 *  quicklist通过切分ziplist来提高插入、删除元素等操作的性能。
 *  链表的编码格式只有OBJ\_ENCODING\_QUICKLIST。
    
    ![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y2B5LiA5oqA5pyv5pap_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y2B5LiA5oqA5pyv5pap_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/b0043a4b3a95448daf9ee56e7647ed98.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Y2B5LiA5oqA5pyv5pap,size_20,color_FFFFFF,t_70,g_se,x_16
[48906d77e872c6da6115dce126a6fc51.png]: https://img-blog.csdnimg.cn/img_convert/48906d77e872c6da6115dce126a6fc51.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y2B5LiA5oqA5pyv5pap_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/3d1ca4dfb6b940458af050098bbeec62.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Y2B5LiA5oqA5pyv5pap,size_20,color_FFFFFF,t_70,g_se,x_16