Redis源码分析 List实现

在版本3.2之前，Redis中的列表是 ziplist 和 linkedlist 实现的，在3.2之后，由quicklist实现。

双向链表linkedlist在表的两端进行push和pop操作非常方便，但是地址不连续，而且需要保持额外的指针。
ziplist是连续内存，存储效率高。但不利于修改操作，插入和删除需要重新申请和释放内存。

先看quicklist数据结构

/* Node, quicklist, and Iterator are the only data structures used currently. *//* 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: 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;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 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: -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 long 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数据结构说明

fill是ziplist大小

compress是节点压缩深度

quicklistNode 数据结构说明

*zl是数据指针，如果没有被压缩，就指向ziplist，否则指向quicklistLZF

count是ziplist的数据个数

encoding : 2; 编码方式，1：ziplist，2：quicklistLZF

quicklist整体数据结构图

PUSH操作

/*-----------------------------------------------------------------------------* List Commands*----------------------------------------------------------------------------*/void pushGenericCommand(client *c, int where) {int j, pushed = 0;robj *lobj = lookupKeyWrite(c->db,c->argv[1]);if (lobj && lobj->type != OBJ_LIST) {addReply(c,shared.wrongtypeerr);return;}for (j = 2; j < c->argc; j++) {if (!lobj) {lobj = createQuicklistObject();quicklistSetOptions(lobj->ptr, server.list_max_ziplist_size,server.list_compress_depth);dbAdd(c->db,c->argv[1],lobj);}listTypePush(lobj,c->argv[j],where);pushed++;}addReplyLongLong(c, (lobj ? listTypeLength(lobj) : 0));if (pushed) {char *event = (where == LIST_HEAD) ? "lpush" : "rpush";signalModifiedKey(c->db,c->argv[1]);notifyKeyspaceEvent(NOTIFY_LIST,event,c->argv[1],c->db->id);}server.dirty += pushed;
}void lpushCommand(client *c) {pushGenericCommand(c,LIST_HEAD);
}void rpushCommand(client *c) {pushGenericCommand(c,LIST_TAIL);
}

lpush和rpush操作都是调用pushGenericCommand

pushGenericCommand调用listTypePush

/*-----------------------------------------------------------------------------* List API*----------------------------------------------------------------------------*//* The function pushes an element to the specified list object 'subject',* at head or tail position as specified by 'where'.** There is no need for the caller to increment the refcount of 'value' as* the function takes care of it if needed. */
void listTypePush(robj *subject, robj *value, int where) {if (subject->encoding == OBJ_ENCODING_QUICKLIST) {int pos = (where == LIST_HEAD) ? QUICKLIST_HEAD : QUICKLIST_TAIL;value = getDecodedObject(value);size_t len = sdslen(value->ptr);quicklistPush(subject->ptr, value->ptr, len, pos);decrRefCount(value);} else {serverPanic("Unknown list encoding");}
}

quicklistPush和quicklistPop

/* Default pop function** Returns malloc'd value from quicklist */
int quicklistPop(quicklist *quicklist, int where, unsigned char **data,unsigned int *sz, long long *slong) {unsigned char *vstr;unsigned int vlen;long long vlong;if (quicklist->count == 0)return 0;int ret = quicklistPopCustom(quicklist, where, &vstr, &vlen, &vlong,_quicklistSaver);if (data)*data = vstr;if (slong)*slong = vlong;if (sz)*sz = vlen;return ret;
}/* Wrapper to allow argument-based switching between HEAD/TAIL pop */
void quicklistPush(quicklist *quicklist, void *value, const size_t sz,int where) {if (where == QUICKLIST_HEAD) {quicklistPushHead(quicklist, value, sz);} else if (where == QUICKLIST_TAIL) {quicklistPushTail(quicklist, value, sz);}
}

quicklistPushHead和quicklistPushTail

/* Add new entry to head node of quicklist.** Returns 0 if used existing head.* Returns 1 if new head created. */
int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {quicklistNode *orig_head = quicklist->head;if (likely(_quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) {quicklist->head->zl =ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD);quicklistNodeUpdateSz(quicklist->head);} else {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);
}/* Add new entry to tail node of quicklist.** Returns 0 if used existing tail.* Returns 1 if new tail created. */
int quicklistPushTail(quicklist *quicklist, void *value, size_t sz) {quicklistNode *orig_tail = quicklist->tail;if (likely(_quicklistNodeAllowInsert(quicklist->tail, quicklist->fill, sz))) {quicklist->tail->zl =ziplistPush(quicklist->tail->zl, value, sz, ZIPLIST_TAIL);quicklistNodeUpdateSz(quicklist->tail);} else {quicklistNode *node = quicklistCreateNode();node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_TAIL);quicklistNodeUpdateSz(node);_quicklistInsertNodeAfter(quicklist, quicklist->tail, node);}quicklist->count++;quicklist->tail->count++;return (orig_tail != quicklist->tail);
}

最重要就是这一行代码：

ziplistPush

unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where) {unsigned char *p;p = (where == ZIPLIST_HEAD) ? ZIPLIST_ENTRY_HEAD(zl) : ZIPLIST_ENTRY_END(zl);return __ziplistInsert(zl,p,s,slen);
}

__ziplistInsert在 ziplist.c太长了不贴代码了。

关于LZF压缩算法是第三方的，redis直接引用了。

LZF的压缩算法，该算法用于对quicklist的节点进行压缩操作。list的设计目的是能够存放很长的数据列表，当列表很长时，必然会占用很高的内存空间，且list中最容易访问的是两端的数据，中间的数据访问率较低，于是就可以从这个出发点来进一步节省内存用于其他操作。

lzh.h

/** Copyright (c) 2000-2008 Marc Alexander Lehmann <schmorp@schmorp.de>** Redistribution and use in source and binary forms, with or without modifica-* tion, are permitted provided that the following conditions are met:**   1.  Redistributions of source code must retain the above copyright notice,*       this list of conditions and the following disclaimer.**   2.  Redistributions in binary form must reproduce the above copyright*       notice, this list of conditions and the following disclaimer in the*       documentation and/or other materials provided with the distribution.** THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MER-* CHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO* EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPE-* CIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;* OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,* WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTH-* ERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED* OF THE POSSIBILITY OF SUCH DAMAGE.** Alternatively, the contents of this file may be used under the terms of* the GNU General Public License ("GPL") version 2 or any later version,* in which case the provisions of the GPL are applicable instead of* the above. If you wish to allow the use of your version of this file* only under the terms of the GPL and not to allow others to use your* version of this file under the BSD license, indicate your decision* by deleting the provisions above and replace them with the notice* and other provisions required by the GPL. If you do not delete the* provisions above, a recipient may use your version of this file under* either the BSD or the GPL.*/#ifndef LZF_H
#define LZF_H/***********************************************************************
**
**	lzf -- an extremely fast/free compression/decompression-method
**	http://liblzf.plan9.de/
**
**	This algorithm is believed to be patent-free.
**
***********************************************************************/#define LZF_VERSION 0x0105 /* 1.5, API version *//** Compress in_len bytes stored at the memory block starting at* in_data and write the result to out_data, up to a maximum length* of out_len bytes.** If the output buffer is not large enough or any error occurs return 0,* otherwise return the number of bytes used, which might be considerably* more than in_len (but less than 104% of the original size), so it* makes sense to always use out_len == in_len - 1), to ensure _some_* compression, and store the data uncompressed otherwise (with a flag, of* course.** lzf_compress might use different algorithms on different systems and* even different runs, thus might result in different compressed strings* depending on the phase of the moon or similar factors. However, all* these strings are architecture-independent and will result in the* original data when decompressed using lzf_decompress.** The buffers must not be overlapping.** If the option LZF_STATE_ARG is enabled, an extra argument must be* supplied which is not reflected in this header file. Refer to lzfP.h* and lzf_c.c.**/
unsigned int
lzf_compress (const void *const in_data,  unsigned int in_len,void             *out_data, unsigned int out_len);/** Decompress data compressed with some version of the lzf_compress* function and stored at location in_data and length in_len. The result* will be stored at out_data up to a maximum of out_len characters.** If the output buffer is not large enough to hold the decompressed* data, a 0 is returned and errno is set to E2BIG. Otherwise the number* of decompressed bytes (i.e. the original length of the data) is* returned.** If an error in the compressed data is detected, a zero is returned and* errno is set to EINVAL.** This function is very fast, about as fast as a copying loop.*/
unsigned int
lzf_decompress (const void *const in_data,  unsigned int in_len,void             *out_data, unsigned int out_len);#endif

扩展阅读参考：

https://blog.csdn.net/belalds/article/details/91976367

https://blog.csdn.net/harleylau/article/details/80534159