redis list数据结构
redis list数据结构底层采用压缩列表ziplist或linkedlist两种数据结构进行存储，首先以ziplist进行存储，在不满足ziplist的存储要求后转换为linkedlist列表。
当列表对象同时满足以下两个条件时，列表对象使用ziplist进行存储，否则用linkedlist存储。
- 列表对象保存的所有字符串元素的长度小于64字节
- 列表对象保存的元素数量小于512个。
redis list元素添加过程
list的数据添加根据传入的变量个数一个个顺序添加，整个顺序如下：
- 创建list对象并添加到db的数据结构当中
- 针对每个待插入的元素添加到list当中
void pushGenericCommand(redisClient *c, int where) {
int j, waiting = 0, pushed = 0;
// 取出列表对象
robj *lobj = lookupKeyWrite(c->db,c->argv[1]);
// 如果列表对象不存在，那么可能有客户端在等待这个键的出现
int may_have_waiting_clients = (lobj == NULL);
if (lobj && lobj->type != REDIS_LIST) {
addReply(c,shared.wrongtypeerr);
return;
}
// 将列表状态设置为就绪
if (may_have_waiting_clients) signalListAsReady(c,c->argv[1]);
// 遍历所有输入值，并将它们添加到列表中
for (j = 2; j < c->argc; j++) {
// 编码值
c->argv[j] = tryObjectEncoding(c->argv[j]);
// 如果列表对象不存在，那么创建一个，并关联到数据库
if (!lobj) {
lobj = createZiplistObject();
dbAdd(c->db,c->argv[1],lobj);
}
// 将值推入到列表
listTypePush(lobj,c->argv[j],where);
pushed++;
}
// 返回添加的节点数量
addReplyLongLong(c, waiting + (lobj ? listTypeLength(lobj) : 0));
// 如果至少有一个元素被成功推入，那么执行以下代码
if (pushed) {
char *event = (where == REDIS_HEAD) ? "lpush" : "rpush";
// 发送键修改信号
signalModifiedKey(c->db,c->argv[1]);
// 发送事件通知
notifyKeyspaceEvent(REDIS_NOTIFY_LIST,event,c->argv[1],c->db->id);
}
server.dirty += pushed;
}
list的每个元素的插入过程中，我们会对是否需要进行转码作两个判断：
- 对每个插入元素的长度进行判断是否进行ziplist->linkedlist的转码。
- 对list总长度是否超过ziplist最大长度的判断。
/*
* 将给定元素添加到列表的表头或表尾。
*
* 参数 where 决定了新元素添加的位置：
*
* - REDIS_HEAD 将新元素添加到表头
*
* - REDIS_TAIL 将新元素添加到表尾
*
*
* 调用者无须担心 value 的引用计数，因为这个函数会负责这方面的工作。
*/
void listTypePush(robj *subject, robj *value, int where) {
// 是否需要转换编码？
listTypeTryConversion(subject,value);
// #define REDIS_LIST_MAX_ZIPLIST_ENTRIES 512
if (subject->encoding == REDIS_ENCODING_ZIPLIST &&
ziplistLen(subject->ptr) >= server.list_max_ziplist_entries)
listTypeConvert(subject,REDIS_ENCODING_LINKEDLIST);
// ZIPLIST
if (subject->encoding == REDIS_ENCODING_ZIPLIST) {
int pos = (where == REDIS_HEAD) ? ZIPLIST_HEAD : ZIPLIST_TAIL;
// 取出对象的值，因为 ZIPLIST 只能保存字符串或整数
value = getDecodedObject(value);
subject->ptr = ziplistPush(subject->ptr,value->ptr,sdslen(value->ptr),pos);
decrRefCount(value);
// 双端链表
} else if (subject->encoding == REDIS_ENCODING_LINKEDLIST) {
if (where == REDIS_HEAD) {
listAddNodeHead(subject->ptr,value);
} else {
listAddNodeTail(subject->ptr,value);
}
incrRefCount(value);
// 未知编码
} else {
redisPanic("Unknown list encoding");
}
}
判断ziplist中单个元素的长度是否超过64的长度，如果超过了长度那么就需要转编码格式为linkedlist编码。
/*
* 对输入值 value 进行检查，看是否需要将 subject 从 ziplist 转换为双端链表，
* 以便保存值 value 。
*
* 函数只对 REDIS_ENCODING_RAW 编码的 value 进行检查，
* 因为整数编码的值不可能超长。
*/
void listTypeTryConversion(robj *subject, robj *value) {
// 确保 subject 为 ZIPLIST 编码
if (subject->encoding != REDIS_ENCODING_ZIPLIST) return;
if (sdsEncodedObject(value) &&
// 看字符串是否过长，#define REDIS_LIST_MAX_ZIPLIST_VALUE 64
sdslen(value->ptr) > server.list_max_ziplist_value)
// 将编码转换为双端链表
listTypeConvert(subject,REDIS_ENCODING_LINKEDLIST);
}
redis ziplist数据结构
ziplist又叫压缩列表，整体的数据格式如下，暂时可以临时看一看，后面会针对数据结构专门的文章来解释。
/*
空白 ziplist 示例图
area |<---- ziplist header ---->|<-- end -->|
size 4 bytes 4 bytes 2 bytes 1 byte
+---------+--------+-------+-----------+
component | zlbytes | zltail | zllen | zlend |
| | | | |
value | 1011 | 1010 | 0 | 1111 1111 |
+---------+--------+-------+-----------+
^
|
ZIPLIST_ENTRY_HEAD
&
address ZIPLIST_ENTRY_TAIL
&
ZIPLIST_ENTRY_END
非空 ziplist 示例图
area |<---- ziplist header ---->|<----------- entries ------------->|<-end->|
size 4 bytes 4 bytes 2 bytes ? ? ? ? 1 byte
+---------+--------+-------+--------+--------+--------+--------+-------+
component | zlbytes | zltail | zllen | entry1 | entry2 | ... | entryN | zlend |
+---------+--------+-------+--------+--------+--------+--------+-------+
^ ^ ^
address | | |
ZIPLIST_ENTRY_HEAD | ZIPLIST_ENTRY_END
|
ZIPLIST_ENTRY_TAIL
*/
/*
* 保存 ziplist 节点信息的结构
*/
typedef struct zlentry {
// prevrawlen ：前置节点的长度
// prevrawlensize ：编码 prevrawlen 所需的字节大小
unsigned int prevrawlensize, prevrawlen;
// len ：当前节点值的长度
// lensize ：编码 len 所需的字节大小
unsigned int lensize, len;
// 当前节点 header 的大小
// 等于 prevrawlensize + lensize
unsigned int headersize;
// 当前节点值所使用的编码类型
unsigned char encoding;
// 指向当前节点的指针
unsigned char *p;
}
redis linkedlist数据结构
双向列表的格式是通用的数据结构，不用过多解释大家都能理解了。
/*
* 双端链表节点
*/
typedef struct listNode {
// 前置节点
struct listNode *prev;
// 后置节点
struct listNode *next;
// 节点的值
void *value;
} listNode;
/*
* 双端链表迭代器
*/
typedef struct listIter {
// 当前迭代到的节点
listNode *next;
// 迭代的方向
int direction;
} listIter;
/*
* 双端链表结构
*/
typedef struct list {
// 表头节点
listNode *head;
// 表尾节点
listNode *tail;
// 节点值复制函数
void *(*dup)(void *ptr);
// 节点值释放函数
void (*free)(void *ptr);
// 节点值对比函数
int (*match)(void *ptr, void *key);
// 链表所包含的节点数量
unsigned long len;
} list;
