雙向鏈表linkedlist

Redis實(shí)現(xiàn)的是標(biāo)準(zhǔn)的雙向鏈表。

鏈表節(jié)點(diǎn)定義：

鏈表定義：

總結(jié)鏈表實(shí)現(xiàn)：

1.每個(gè)節(jié)點(diǎn)有前后節(jié)點(diǎn)指針，且第一個(gè)節(jié)點(diǎn)的指針為NULL,最后一個(gè)節(jié)點(diǎn)的指針為NULL(無(wú)環(huán))。

2.對(duì)雙鏈表進(jìn)行封裝，鏈表第一個(gè)節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)指針，以及鏈表長(zhǎng)度。

優(yōu)點(diǎn)：

在鏈表兩端進(jìn)行push和pop操作都是O(1)。

獲取鏈表的長(zhǎng)度操作O(1)。

多態(tài)，可以存儲(chǔ)c語(yǔ)言支持的任何數(shù)據(jù)類型，通過(guò)void *萬(wàn)能指針。

缺點(diǎn)：

內(nèi)存開(kāi)銷比較大。每個(gè)節(jié)點(diǎn)上除了要保存數(shù)據(jù)之外，還要額外保存兩個(gè)指針

各個(gè)節(jié)點(diǎn)是單獨(dú)的內(nèi)存塊，地址不連續(xù)，節(jié)點(diǎn)多了容易產(chǎn)生內(nèi)存碎片。

壓縮列表轉(zhuǎn)化成雙向鏈表?xiàng)l件

創(chuàng)建新列表時(shí) redis 默認(rèn)使用 redis_encoding_ziplist 編碼， 當(dāng)以下任意一個(gè)條件被滿足時(shí)， 列表會(huì)被轉(zhuǎn)換成 redis_encoding_linkedlist 編碼：

試圖往列表新添加一個(gè)字符串值，且這個(gè)字符串的長(zhǎng)度超過(guò) server.list_max_ziplist_value (默認(rèn)值為 64 )。

ziplist 包含的節(jié)點(diǎn)超過(guò) server.list_max_ziplist_entries (默認(rèn)值為 512 )。

注意：這兩個(gè)條件是可以修改的，在 redis.conf 中

list-max-ziplist-value 64list-max-ziplist-entries 512

ziplist

壓縮列表 ziplist 是為 Redis 節(jié)約內(nèi)存而開(kāi)發(fā)的。

ziplist 是由一系列特殊編碼的內(nèi)存塊構(gòu)成的列表(像內(nèi)存連續(xù)的數(shù)組，但每個(gè)元素長(zhǎng)度不同)， 一個(gè) ziplist 可以包含多個(gè)節(jié)點(diǎn)(entry)。

ziplist 將表中每一項(xiàng)存放在前后連續(xù)的地址空間內(nèi)，每一項(xiàng)因占用的空間不同，而采用變長(zhǎng)編碼。

當(dāng)元素個(gè)數(shù)較少時(shí)，Redis 用 ziplist 來(lái)存儲(chǔ)數(shù)據(jù)，當(dāng)元素個(gè)數(shù)超過(guò)某個(gè)值時(shí)，鏈表鍵中會(huì)把 ziplist 轉(zhuǎn)化為 linkedlist，字典鍵中會(huì)把 ziplist 轉(zhuǎn)化為 hashtable。

由于內(nèi)存是連續(xù)分配的，所以遍歷速度很快。

在3.2之后，ziplist被quicklist替代。但是仍然是zset底層實(shí)現(xiàn)之一。

ziplist內(nèi)存布局

ziplist使用連續(xù)的內(nèi)存塊，每一個(gè)節(jié)點(diǎn)(entry)都是連續(xù)存儲(chǔ)的；ziplist 存儲(chǔ)分布如下：

常態(tài)的壓縮列表內(nèi)存布局如上圖所示，整個(gè)內(nèi)存塊區(qū)域內(nèi)分為五個(gè)部分，下面分別介紹著五個(gè)部分：

zlbytes：存儲(chǔ)一個(gè)無(wú)符號(hào)整數(shù)，固定四個(gè)字節(jié)長(zhǎng)度，用于存儲(chǔ)壓縮列表所占用的字節(jié)，當(dāng)重新分配內(nèi)存的時(shí)候使用，不需要遍歷整個(gè)列表來(lái)計(jì)算內(nèi)存大小。

zltail：存儲(chǔ)一個(gè)無(wú)符號(hào)整數(shù)，固定四個(gè)字節(jié)長(zhǎng)度，代表指向列表尾部的偏移量，偏移量是指壓縮列表的起始位置到指定列表節(jié)點(diǎn)的起始位置的距離。

zllen：壓縮列表包含的節(jié)點(diǎn)個(gè)數(shù)，固定兩個(gè)字節(jié)長(zhǎng)度，源碼中指出當(dāng)節(jié)點(diǎn)個(gè)數(shù)大于2^16-2個(gè)數(shù)的時(shí)候，該值將無(wú)效，此時(shí)需要遍歷列表來(lái)計(jì)算列表節(jié)點(diǎn)的個(gè)數(shù)。

entries：列表節(jié)點(diǎn)區(qū)域，長(zhǎng)度不定，由列表節(jié)點(diǎn)緊挨著組成。每個(gè)節(jié)點(diǎn)可以保存一個(gè)字節(jié)數(shù)組或者是一個(gè)整數(shù)值。

zlend：一字節(jié)長(zhǎng)度固定值為255，用于表示列表結(jié)束。

上面介紹了壓縮列表的總體內(nèi)存布局，對(duì)于初entries區(qū)域以外的四個(gè)區(qū)域的長(zhǎng)度都是固定的，下面再看看此區(qū)域中每個(gè)節(jié)點(diǎn)的布局情況。

每個(gè)列表節(jié)點(diǎn)由三部分組成：

previous length：記錄前一個(gè)節(jié)點(diǎn)所占有的內(nèi)存字節(jié)數(shù)，通過(guò)該值，我們可以從當(dāng)前節(jié)點(diǎn)計(jì)算前一個(gè)節(jié)點(diǎn)的地址，可以用來(lái)實(shí)現(xiàn)從表尾向表頭節(jié)點(diǎn)遍歷；

len/encoding：記錄了當(dāng)前節(jié)點(diǎn)content占有的內(nèi)存字節(jié)數(shù)及其存儲(chǔ)類型，用來(lái)解析content用；

content：保存了當(dāng)前節(jié)點(diǎn)的值。

最關(guān)鍵的是prevrawlen和len/encoding，content只是實(shí)際存儲(chǔ)數(shù)值的比特位。

為了節(jié)省內(nèi)存，根據(jù)上一個(gè)節(jié)點(diǎn)的長(zhǎng)度prevlength 可以將entry節(jié)點(diǎn)分為兩類：

entry的前8位小于254，則這8位就表示上一個(gè)節(jié)點(diǎn)的長(zhǎng)度

entry的前8位等于254，則意味著上一個(gè)節(jié)點(diǎn)的長(zhǎng)度無(wú)法用8位表示，后面32位才是真實(shí)的prevlength。用254 不用255(11111111)作為分界是因?yàn)?55是zlend的值，它用于判斷ziplist是否到達(dá)尾部。

根據(jù)當(dāng)前節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)類型及長(zhǎng)度，可以將ziplist節(jié)點(diǎn)分為9類：

其中整數(shù)節(jié)點(diǎn)分為6類：

整數(shù)節(jié)點(diǎn)的encoding的長(zhǎng)度為8位，其中高2位用來(lái)區(qū)分整數(shù)節(jié)點(diǎn)和字符串節(jié)點(diǎn)(高2位為11時(shí)是整數(shù)節(jié)點(diǎn))，低6位用來(lái)區(qū)分整數(shù)節(jié)點(diǎn)的類型，定義如下:

#define ZIP_INT_16B (0xc0 | 0<<4)//整數(shù)data,占16位(2字節(jié))

#define ZIP_INT_32B (0xc0 | 1<<4)//整數(shù)data,占32位(4字節(jié))

#define ZIP_INT_64B (0xc0 | 2<<4)//整數(shù)data,占64位(8字節(jié))

#define ZIP_INT_24B (0xc0 | 3<<4)//整數(shù)data,占24位(3字節(jié))

#define ZIP_INT_8B 0xfe //整數(shù)data,占8位(1字節(jié))

/*4 bit integer immediate encoding*/

//整數(shù)值1~13的節(jié)點(diǎn)沒(méi)有data，encoding的低四位用來(lái)表示data

#define ZIP_INT_IMM_MASK 0x0f

#define ZIP_INT_IMM_MIN 0xf1 /* 11110001 */

#define ZIP_INT_IMM_MAX 0xfd /* 11111101 */

值得注意的是 最后一種encoding是存儲(chǔ)整數(shù)0~12的節(jié)點(diǎn)的encoding，它沒(méi)有額外的data部分，encoding的高4位表示這個(gè)類型，低4位就是它的data。這種類型的節(jié)點(diǎn)的encoding大小介于ZIP_INT_24B與ZIP_INT_8B之間(1~13)，但是為了表示整數(shù)0，取出低四位xxxx之后會(huì)將其-1作為實(shí)際的data值(0~12)。在函數(shù)zipLoadInteger中，我們可以看到這種類型節(jié)點(diǎn)的取值方法：

當(dāng)data小于63字節(jié)時(shí)(2^6)，節(jié)點(diǎn)存為上圖的第一種類型，高2位為00，低6位表示data的長(zhǎng)度。

當(dāng)data小于16383字節(jié)時(shí)(2^14)，節(jié)點(diǎn)存為上圖的第二種類型，高2位為01，后續(xù)14位表示data的長(zhǎng)度。

當(dāng)data小于4294967296字節(jié)時(shí)(2^32)，節(jié)點(diǎn)存為上圖的第二種類型，高2位為10，下一字節(jié)起連續(xù)32位表示data的長(zhǎng)度。

字符串節(jié)點(diǎn)分為3類：

當(dāng)data小于63字節(jié)時(shí)(2^6)，節(jié)點(diǎn)存為上圖的第一種類型，高2位為00，低6位表示data的長(zhǎng)度。

當(dāng)data小于16383字節(jié)時(shí)(2^14)，節(jié)點(diǎn)存為上圖的第二種類型，高2位為01，后續(xù)14位表示data的長(zhǎng)度。

當(dāng)data小于4294967296字節(jié)時(shí)(2^32)，節(jié)點(diǎn)存為上圖的第二種類型，高2位為10，下一字節(jié)起連續(xù)32位表示data的長(zhǎng)度。

上圖可以看出：不同于整數(shù)節(jié)點(diǎn)encoding永遠(yuǎn)是8位，字符串節(jié)點(diǎn)的encoding可以有8位、16位、40位三種長(zhǎng)度

相同encoding類型的整數(shù)節(jié)點(diǎn) data長(zhǎng)度是固定的，但是相同encoding類型的字符串節(jié)點(diǎn)，data長(zhǎng)度取決于encoding后半部分的值。

#define ZIP_STR_06B (0 << 6)//字符串data,最多有2^6字節(jié)(encoding后半部分的length有6位,length決定data有多少字節(jié))

#define ZIP_STR_14B (1 << 6)//字符串data,最多有2^14字節(jié)

#define ZIP_STR_32B (2 << 6)//字符串data,最多有2^32字節(jié)

如何通過(guò)一個(gè)節(jié)點(diǎn)向前跳轉(zhuǎn)到另一個(gè)節(jié)點(diǎn)？

從尾部向頭部遍歷(利用 ztail 和privious_entry_length)，用指向當(dāng)前節(jié)點(diǎn)的指針 e ， 減去前一個(gè) entry的長(zhǎng)度， 得出的結(jié)果就是指向前一個(gè)節(jié)點(diǎn)的地址 p 。

已知節(jié)點(diǎn)的位置，求data的值

entry布局 可以看出，若要算出data的偏移量，得先計(jì)算出prevlength所占內(nèi)存大小(1字節(jié)和5字節(jié))：

//根據(jù)ptr指向的entry，返回這個(gè)entry的prevlensize

#define ZIP_DECODE_PREVLENSIZE(ptr, prevlensize) do { \

if ((ptr)[0]

(prevlensize)= 1; \

}else{ \

(prevlensize)= 5; \

} \

}while(0);

接著再用ZIP_DECODE_LENGTH(ptr + prevlensize, encoding, lensize, len)算出encoding所占的字節(jié)，返回給lensize；data所占的字節(jié)返回給len

//根據(jù)ptr指向的entry求出該entry的len(encoding里存的 data所占字節(jié))和lensize(encoding所占的字節(jié))

#define ZIP_DECODE_LENGTH(ptr, encoding, lensize, len) do { \ZIP_ENTRY_ENCODING((ptr), (encoding)); \if ((encoding)

(lensize)= 1; \

(len)= (ptr)[0] & 0x3f; \

}else if ((encoding) ==ZIP_STR_14B) { \

(lensize)= 2; \

(len)= (((ptr)[0] & 0x3f) << 8) | (ptr)[1]; \

}else if (encoding ==ZIP_STR_32B) { \

(lensize)= 5; \

(len)= ((ptr)[1] << 24) |\

((ptr)[2] << 16) |\

((ptr)[3] << 8) |\

((ptr)[4]); \

}else{ \

assert(NULL); \

} \

}else{ \

(lensize)= 1; \

(len)=zipIntSize(encoding); \

} \

}while(0);//將ptr的encoding解析成1個(gè)字節(jié)：00000000、01000000、10000000(字符串類型)和11??????(整數(shù)類型)//如果是整數(shù)類型，encoding直接照抄ptr的;如果是字符串類型，encoding被截?cái)喑梢粋€(gè)字節(jié)并清零后6位

#define ZIP_ENTRY_ENCODING(ptr, encoding) do { \(encoding)= (ptr[0]); \if ((encoding) < ZIP_STR_MASK) (encoding) &=ZIP_STR_MASK; \

}while(0)//根據(jù)encoding返回?cái)?shù)據(jù)(整數(shù))所占字節(jié)數(shù)

unsigned int zipIntSize(unsigned charencoding) {switch(encoding) {case ZIP_INT_8B: return 1;case ZIP_INT_16B: return 2;case ZIP_INT_24B: return 3;case ZIP_INT_32B: return 4;case ZIP_INT_64B: return 8;default: return 0; /*4 bit immediate*/}

assert(NULL);return 0;

}

完成以上步驟之后，即可算出data的位置:ptr+prevlensize+lensize，以及data的長(zhǎng)度len

連鎖更新

每個(gè)節(jié)點(diǎn)的previous_entry_length屬性都記錄了前一個(gè)節(jié)點(diǎn)的長(zhǎng)度

如果前一個(gè)節(jié)點(diǎn)的長(zhǎng)度小于254，那么previous_entry_length屬性需要用1字節(jié)長(zhǎng)的空間來(lái)保存這個(gè)長(zhǎng)度值

如果前一個(gè)節(jié)點(diǎn)的長(zhǎng)度大于等于254，那么previous_entry_length屬性需要5字節(jié)長(zhǎng)的空間來(lái)保存這個(gè)長(zhǎng)度值

考慮這樣一種情況：在一個(gè)壓縮列表中，有多個(gè)連續(xù)的、長(zhǎng)度介于250字節(jié)到253字節(jié)之間的節(jié)點(diǎn)e1至eN

|zlbytes|zltail|zllen|e1|e2|e3|...|eN|zlend|

因?yàn)閑1至eN的所有節(jié)點(diǎn)的長(zhǎng)度都小于254字節(jié)，所以記錄這些節(jié)點(diǎn)的長(zhǎng)度只需要1字節(jié)長(zhǎng)的previous_entry_length屬性，換句話說(shuō)，e1至eN的所有節(jié)點(diǎn)的previous_entry_length屬性都是1字節(jié)長(zhǎng)的。

如果我們將一個(gè)長(zhǎng)度大于等于254字節(jié)的新節(jié)點(diǎn)new設(shè)置到壓縮列表的表頭節(jié)點(diǎn)，那么new將成為e1的潛質(zhì)節(jié)點(diǎn)。

此時(shí)e1到eN的每個(gè)節(jié)點(diǎn)的previous_entry_length屬性都要擴(kuò)展為5字節(jié)以符合壓縮列表對(duì)節(jié)點(diǎn)的要求，程序需要不斷的對(duì)壓縮列表進(jìn)行空間重分配操作。

Redis將這種在特殊情況下產(chǎn)生的多次空間擴(kuò)展操作稱之為“連鎖更新”。

除了添加新節(jié)點(diǎn)可能會(huì)引發(fā)連鎖更新之外，刪除節(jié)點(diǎn)也可能會(huì)連鎖更新。

因?yàn)檫B鎖更新在最壞情況下需要對(duì)壓縮列表執(zhí)行N次空間重分配操作，而每次空間重分配的最壞復(fù)雜度為O(N)，所以連鎖更新的最壞復(fù)雜度為O(N2)。

注意的是，盡管連鎖更新的復(fù)雜度較高，但它真正趙成性能問(wèn)題的幾率是很低的：

首先，壓縮列表里要恰好有多個(gè)連續(xù)的、長(zhǎng)度介于250字節(jié)至253字節(jié)之間的節(jié)點(diǎn)，連鎖更新才有可能被引發(fā)，在實(shí)際中，這種情況并不多見(jiàn)；

其次，即使出現(xiàn)連鎖更新，但只要更新的節(jié)點(diǎn)數(shù)量不多，就不會(huì)對(duì)性能造成任何影響：比如說(shuō)，對(duì)三五個(gè)節(jié)點(diǎn)進(jìn)行連鎖更新是絕對(duì)不會(huì)影響性能的；

Redis中壓縮列表的應(yīng)用

Redis中，不同的數(shù)據(jù)類型廣泛地應(yīng)用了壓縮列表編碼，整理如下表：

ziplist總結(jié)

ziplist的主要優(yōu)點(diǎn)是節(jié)省內(nèi)存,且ziplist存儲(chǔ)在一段連續(xù)的內(nèi)存上，所以存儲(chǔ)效率很高。但是，它不利于修改操作，插入和刪除操作需要頻繁的申請(qǐng)和釋放內(nèi)存。

查找操作只能按順序查找(可以是從前往后、也可以從后往前)

一旦數(shù)據(jù)發(fā)生改動(dòng)，就會(huì)引發(fā)內(nèi)存realloc，可能導(dǎo)致內(nèi)存拷貝。當(dāng)ziplist長(zhǎng)度很長(zhǎng)的時(shí)候，一次realloc可能會(huì)導(dǎo)致大批量的數(shù)據(jù)拷貝。

quickList

可以認(rèn)為quickList，是ziplist和linkedlist二者的結(jié)合；quickList將二者的優(yōu)點(diǎn)結(jié)合起來(lái)。

官方給出的定義：

A generic doubly linked quicklist implementation

A doubly linked list of ziplists

quickList是一個(gè)ziplist組成的雙向鏈表。每個(gè)節(jié)點(diǎn)使用ziplist來(lái)保存數(shù)據(jù)。

本質(zhì)上來(lái)說(shuō)，quicklist里面保存著一個(gè)一個(gè)小的ziplist。結(jié)構(gòu)如下：

/*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*/typedefstructquicklistNode {struct quicklistNode *prev; //上一個(gè)node節(jié)點(diǎn)

struct quicklistNode *next; //下一個(gè)node

unsigned char *zl; //保存的數(shù)據(jù) 壓縮前ziplist 壓縮后壓縮的數(shù)據(jù)

unsigned int sz; /*ziplist size in bytes*/unsignedint count : 16; /*count of items in ziplist*/unsignedint encoding : 2; /*RAW==1 or LZF==2*/unsignedint container : 2; /*NONE==1 or ZIPLIST==2*/unsignedint recompress : 1; /*was this node previous compressed?*/unsignedint attempted_compress : 1; /*node can't compress; too small*/unsignedint 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*/typedefstructquicklistLZF {

unsignedint sz; /*LZF size in bytes*/

charcompressed[];

} 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.*/typedefstructquicklist {

quicklistNode*head; //頭結(jié)點(diǎn)

quicklistNode *tail; //尾節(jié)點(diǎn)

unsigned long count; /*total count of all entries in all ziplists*/unsignedint len; /*number of quicklistNodes*/

int fill : 16; /*fill factor for individual nodes*///負(fù)數(shù)代表級(jí)別，正數(shù)代表個(gè)數(shù)

unsigned int compress : 16; /*depth of end nodes not to compress;0=off*///壓縮級(jí)別

} quicklist;

quickList就是一個(gè)標(biāo)準(zhǔn)的雙向鏈表的配置，有head 有tail;

每一個(gè)節(jié)點(diǎn)是一個(gè)quicklistNode，包含prev和next指針。

每一個(gè)quicklistNode 包含 一個(gè)ziplist，*zp 壓縮鏈表里存儲(chǔ)鍵值。

所以quicklist是對(duì)ziplist進(jìn)行一次封裝，使用小塊的ziplist來(lái)既保證了少使用內(nèi)存，也保證了性能。

refer：

《Redis設(shè)計(jì)與實(shí)現(xiàn)》

總結(jié)

以上是生活随笔為你收集整理的redis创建像mysql表结构_Redis数据结构列表实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。