在一次使用redis list的時候罐栈，使用object encoding命令查看編碼類型烫沙。時出現(xiàn)了quicklist
192.168.99.100:6379> lpush list a b c d
(integer) 4
192.168.99.100:6379> object encoding list
"quicklist"
192.168.99.100:6379>
而我只記得linkedlist和ziplist搬素。 這次抽了個時間來翻翻源碼绷耍，為了弄清楚:
list對象的
linkedlist編碼祈匙、ziplist編碼忽刽、以及編碼轉(zhuǎn)換機(jī)制是否還存在？
List
# 使用LPUSH命令夺欲，lpushCommand會被調(diào)用
void lpushCommand(redisClient *c) {
pushGenericCommand(c,REDIS_HEAD);
}
void pushGenericCommand(redisClient *c, int where) {
int j, waiting = 0, pushed = 0;
# 如果命令是 LPUSH key value1 value2
# 則這里的argv = ["LPUSH", "key", "value1", "value2"]
robj *lobj = lookupKeyWrite(c->db,c->argv[1]);
# 如果key對應(yīng)的類型不是list會報錯并退出
if (lobj && lobj->type != REDIS_LIST) {
addReply(c,shared.wrongtypeerr);
return;
}
# 每一次循環(huán)就是在處理LPUSH操作的一個值
for (j = 2; j < c->argc; j++) {
# 嘗試將argv[j]轉(zhuǎn)換成合適的編碼：RAW跪帝、EMBSTR、INT
c->argv[j] = tryObjectEncoding(c->argv[j]);
# list的自動創(chuàng)建些阅，創(chuàng)建的list默認(rèn)使用Ziplist編碼
if (!lobj) {
lobj = createZiplistObject();
dbAdd(c->db,c->argv[1],lobj);
}
# Push的操作在listTypePush
listTypePush(lobj,c->argv[j],where);
pushed++;
}
# 命令回復(fù)
addReplyLongLong(c, waiting + (lobj ? listTypeLength(lobj) : 0));
if (pushed) {
char *event = (where == REDIS_HEAD) ? "lpush" : "rpush";
# 發(fā)送信號：key已修改
signalModifiedKey(c->db,c->argv[1]);
# 發(fā)送鍵空間伞剑、鍵時間通知
notifyKeyspaceEvent(REDIS_NOTIFY_LIST,event,c->argv[1],c->db->id);
}
server.dirty += pushed;
}
void listTypePush(robj *subject, robj *value, int where) {
# 判斷value是否滿足編碼轉(zhuǎn)換條件
listTypeTryConversion(subject,value);
# 判斷l(xiāng)ist是否滿足編碼轉(zhuǎn)換條件
# 如果list長度大于等于server.list_max_ziplist_entries
# 那么list會從Ziplist轉(zhuǎn)換成Linkedlist編碼
if (subject->encoding == REDIS_ENCODING_ZIPLIST &&
ziplistLen(subject->ptr) >= server.list_max_ziplist_entries)
listTypeConvert(subject,REDIS_ENCODING_LINKEDLIST);
# 針對不同編碼，調(diào)用不同API來增加list節(jié)點
if (subject->encoding == REDIS_ENCODING_ZIPLIST) {
int pos = (where == REDIS_HEAD) ? ZIPLIST_HEAD : ZIPLIST_TAIL;
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");
}
}
# 如果添加的value是sds(Simple Dynamic String), sds可以是raw或embstr編碼
# 且sds的長度大于server.list_max_ziplist_value
# 那么list會從Ziplist轉(zhuǎn)換成Linkedlist編碼
void listTypeTryConversion(robj *subject, robj *value) {
if (subject->encoding != REDIS_ENCODING_ZIPLIST) return;
if (sdsEncodedObject(value) &&
sdslen(value->ptr) > server.list_max_ziplist_value)
listTypeConvert(subject,REDIS_ENCODING_LINKEDLIST);
}
這是我所熟知的list編碼轉(zhuǎn)換機(jī)制扑眉，而quicklist是redis 3.2新加入的結(jié)構(gòu)纸泄。那我直接去看了redis 4.0的版本赖钞，了解下list編碼轉(zhuǎn)換機(jī)制是否有所改變腰素。
void pushGenericCommand(client *c, int where) {
...
for (j = 2; j < c->argc; j++) {
if (!lobj) {
# list自動創(chuàng)建時，使用的是quicklist
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++;
}
...
}
void listTypePush(robj *subject, robj *value, int where) {
# 添加元素時雪营，如果不是quicklist編碼就會報錯
# 那很大程度上意味著list只有一種編碼了
if (subject->encoding == OBJ_ENCODING_QUICKLIST) {
int pos = (where == LIST_HEAD) ? QUICKLIST_HEAD : QUICKLIST_TAIL;
value = getDecodedObject(value); # 確保value是一個字符串對象弓千，而不是INT
size_t len = sdslen(value->ptr);
# 直接調(diào)用的quicklist API
quicklistPush(subject->ptr, value->ptr, len, pos);
decrRefCount(value); # 引用計數(shù)器
} else {
serverPanic("Unknown list encoding");
}
}
3.2版本的listTypePush會根據(jù)不同的編碼調(diào)用不同數(shù)據(jù)結(jié)構(gòu)的API，而4.0直接調(diào)用了quicklist的API献起，以前的編碼轉(zhuǎn)換的機(jī)制已經(jīng)不存在了洋访。
Quicklist
這次的目的已達(dá)到，但還是來了解下quicklist
quicklist - A doubly linked list of ziplists
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;
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;
typedef struct quicklistEntry {
const quicklist *quicklist;
quicklistNode *node;
unsigned char *zi;
unsigned char *value;
long long longval;
unsigned int sz;
int offset;
} quicklistEntry;
- quicklist 是一個雙向鏈表谴餐，head姻政、tail分別指向頭尾節(jié)點
- quicklistNode 是雙向鏈表的節(jié)點，prev岂嗓、next分別指向前驅(qū)汁展、后繼結(jié)點
- quicklistNode.zl 指向一個ziplist（或者quicklistLZF結(jié)構(gòu)）
- quicklistEntry 包裹著list的每一個值，作為ziplist的一個節(jié)點
可以想象得到厌殉，當(dāng)一個空的quicklist加入一個值value時食绿，會有以下操作（不一定以這個順序）：
- 使用Entry包裹value
- 創(chuàng)建一個ziplist，把Entry加入到ziplist中
- 創(chuàng)建一個Node公罕，Node.zl指向ziplist
- 創(chuàng)建quicklist器紧，將Node加入quicklist中
原來版本的list直接使用的一個ziplist，而現(xiàn)在版本的list可以看成使用多個ziplist楼眷，然后通過雙向鏈表連接起來铲汪。如果知道ziplist的特性熊尉，那這樣的優(yōu)點就很明顯了。
由于ziplist的連鎖更新掌腰。ziplist的插入刪除操作在最壞情況下的復(fù)雜度為O(n^2)帽揪，雖然導(dǎo)致整條ziplist連鎖更新的概率很低。將原來的ziplist劃分成多條ziplist后辅斟，插入刪除一個元素转晰，即使情況再極端也只會引起一段ziplist的連鎖更新。
