Redis壓縮列表研究與優(yōu)化設(shè)計(jì)

張慧寧，李擁軍，王紹東

1.廣東石油化工學(xué)院 實(shí)驗(yàn)教學(xué)部，廣東 茂名 525000

2.華南理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，廣州 510006

3.騰訊科技有限公司 MIG安全云部，廣東 深圳 518000

1 引言

傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù)建立在關(guān)系模型基礎(chǔ)上，借助集合代數(shù)等數(shù)學(xué)概念和方法來(lái)處理數(shù)據(jù)庫(kù)中的數(shù)據(jù)[1-3]。隨著互聯(lián)網(wǎng)業(yè)務(wù)與數(shù)據(jù)量逐漸增大，傳統(tǒng)數(shù)據(jù)庫(kù)存在單機(jī)（單庫(kù)）性能瓶頸且擴(kuò)展困難的先天性缺陷，無(wú)法滿足日益增長(zhǎng)的海量數(shù)據(jù)存儲(chǔ)及其超高并發(fā)數(shù)據(jù)讀寫性能要求，從而衍生出各種不同的NoSQL數(shù)據(jù)庫(kù)產(chǎn)品[4-7]。NoSQL簡(jiǎn)單、易于大規(guī)模分布式擴(kuò)展，并且讀寫性能優(yōu)越，常見(jiàn)的有Redis、MemCached以及MongoDB等，其中Redis不僅讀寫性能高，支持多種數(shù)據(jù)結(jié)構(gòu)，支持?jǐn)?shù)據(jù)持久化，而被廣泛使用[4，8]。

Redis作為一個(gè)開源Key-Value模型分布式內(nèi)存數(shù)據(jù)庫(kù)，可將用戶全部數(shù)據(jù)分布存儲(chǔ)在節(jié)點(diǎn)內(nèi)存空間，極大提升了數(shù)據(jù)讀寫操作效率[7]。其包含列表、字符串、集合、哈希、有序集合5種Redis數(shù)據(jù)結(jié)構(gòu)類型[8-11]。同時(shí)每種數(shù)據(jù)結(jié)構(gòu)類型針對(duì)不同應(yīng)用場(chǎng)景支持不同編碼方式，壓縮列表（ziplist）為其中之一。

由于壓縮列表能節(jié)約內(nèi)存，因此哈希鍵、列表鍵和有序集合鍵初始化的底層實(shí)現(xiàn)皆采用壓縮列表。壓縮列表通過(guò)節(jié)點(diǎn)的previous_entry_length域（見(jiàn)圖1）保存前驅(qū)節(jié)點(diǎn)長(zhǎng)度，便于存儲(chǔ)數(shù)據(jù)時(shí)實(shí)現(xiàn)查找。但此方法連鎖更新時(shí)間復(fù)雜度為O(N2)。具體分析見(jiàn)2.2節(jié)。

本文針對(duì)Redis壓縮列表連鎖更新過(guò)程中時(shí)間復(fù)雜度優(yōu)化問(wèn)題，設(shè)計(jì)了新的內(nèi)存空間級(jí)聯(lián)擴(kuò)展操作方式，以降低連鎖更新時(shí)的時(shí)間復(fù)雜度，同時(shí)優(yōu)化結(jié)構(gòu)體，提升壓縮列表操作性能。

2 Redis壓縮列表研究

2.1 壓縮列表結(jié)構(gòu)

分析發(fā)現(xiàn)，Redis單機(jī)服務(wù)器每秒讀寫操作可達(dá)6萬(wàn)次，在大多數(shù)場(chǎng)景下壓縮列表對(duì)效率的提升起到了重要的作用[12]。壓縮列表（ziplist）是緊湊的數(shù)據(jù)存儲(chǔ)模式，由連續(xù)特殊編碼的內(nèi)存字節(jié)空間組成，包含多個(gè)不同類型節(jié)點(diǎn)（entry）的順序型數(shù)據(jù)結(jié)構(gòu)[13-14]。其功能是將數(shù)據(jù)按照既定的編碼規(guī)則存儲(chǔ)在一塊內(nèi)存區(qū)域中，該內(nèi)存在物理上是連續(xù)的，邏輯上則被按功效區(qū)分為多個(gè)部分，其作用是在一定可控制的時(shí)間復(fù)雜度前提下盡可能地減少不必要的內(nèi)存開銷，從而達(dá)到節(jié)約內(nèi)存能耗的效果[15-17]。Redis壓縮列表數(shù)據(jù)結(jié)構(gòu)模型如圖1所示。

壓縮列表（ziplist）內(nèi)存布局分header、entries、end三個(gè)功能區(qū)，其中 header包含 zlbytes、zltail、zllen 屬性。entries包含zlentry屬性，end包含zlend屬性。

zlbytes記錄整個(gè)ziplist占用的內(nèi)存字節(jié)總數(shù)；zltail記錄ziplist表尾節(jié)點(diǎn)距離起始位置偏移字節(jié)數(shù)大?。醋詈笠粋€(gè)節(jié)點(diǎn)到壓縮列表的起始位置字節(jié)數(shù)量）；zllen記錄ziplist包含的節(jié)點(diǎn)總數(shù)量，但當(dāng)節(jié)點(diǎn)數(shù)超過(guò)65 535時(shí)則需重新遍歷整個(gè)ziplist才能計(jì)算得出節(jié)點(diǎn)數(shù)量。zlentry保存長(zhǎng)度受限的字符數(shù)組或整數(shù)數(shù)組。結(jié)尾符zlend用于標(biāo)記ziplist末端，為特殊值0xFF。

Zlentry將空間劃分previous_entry_length域、encoding域、content域。為閱讀方便，將previous_entry_length域縮寫為prevlen域。

entry的prevlen域用于記錄前驅(qū)節(jié)點(diǎn)所占內(nèi)存空間字節(jié)數(shù)，具有1字節(jié)或5字節(jié)存儲(chǔ)形態(tài)。5字節(jié)存儲(chǔ)實(shí)例如圖1（b）所示，當(dāng)整體編碼值為0xFE000007E1，其中值的最高位字節(jié)以0xFE表示，之后4字節(jié)0x000007E1（十進(jìn)制值2017）是前驅(qū)節(jié)點(diǎn)的實(shí)際長(zhǎng)度。encoding域，用于記錄content存儲(chǔ)內(nèi)容的編碼方式。若encoding域首字節(jié)高兩位為11則content域存儲(chǔ)內(nèi)容為整數(shù)編碼，否則以字節(jié)數(shù)組編碼表示。末端content域用于存儲(chǔ)實(shí)際的數(shù)據(jù)，因此Content域存放的是（十進(jìn)制值2018）當(dāng)前節(jié)點(diǎn)的值。

壓縮列表中每個(gè)entry所包含的所有字節(jié)位相關(guān)的特殊含義都可以通過(guò)解析函數(shù)zipEntry（）使用結(jié)構(gòu)本體zlentry保存，prevrawlensize域記錄prevlen域的大小是1或者5，prevrawlen域記錄前驅(qū)節(jié)點(diǎn)所占內(nèi)存空間字節(jié)數(shù)，lensize域記錄encoding所占內(nèi)存空間字節(jié)數(shù)，len域則記錄content的長(zhǎng)度，hadersize域表示節(jié)點(diǎn)的頭部大小，保存prevlen與encoding的長(zhǎng)度之和，encoding域保存content存儲(chǔ)數(shù)據(jù)的編碼方式，指針p則指向content存儲(chǔ)的數(shù)據(jù)內(nèi)容。

圖1 壓縮列表數(shù)據(jù)結(jié)構(gòu)

綜上所述，Redis壓縮列表適用于小數(shù)據(jù)量的高性能操作，專注運(yùn)算上效率的提升。從壓縮列表的設(shè)計(jì)結(jié)構(gòu)中不難看出其緊湊的存儲(chǔ)方式對(duì)降低內(nèi)存占用有著明顯優(yōu)勢(shì)。

2.2 壓縮列表連鎖更新問(wèn)題分析

2.2.1 產(chǎn)生連鎖更新的原因

壓縮列表以節(jié)點(diǎn)形式存儲(chǔ)，可以有任意多個(gè)節(jié)點(diǎn)。entry的prevlen域占用的內(nèi)存空間大小是根據(jù)前驅(qū)節(jié)點(diǎn)長(zhǎng)度決定為1字節(jié)或者5字節(jié)。若首字節(jié)為特殊字符0xFE，則表示prevlen域占據(jù)5字節(jié)內(nèi)存空間，之后4字節(jié)表示前驅(qū)節(jié)點(diǎn)所占據(jù)的內(nèi)存空間字節(jié)數(shù)，否則只使用首字節(jié)表示前驅(qū)節(jié)點(diǎn)所占內(nèi)存空間大小，即1字節(jié)長(zhǎng)度。因此當(dāng)ziplist刪除一個(gè)entry或者新增一個(gè)entry時(shí)，后繼節(jié)點(diǎn)的prevlen域所占內(nèi)存空間大小可能會(huì)隨之發(fā)生改變[18-19]。這種可靈活擴(kuò)展的特性是直接引發(fā)連鎖更新問(wèn)題的根本原因。

壓縮列表的存儲(chǔ)數(shù)據(jù)形式等同于增加節(jié)點(diǎn)，而增加節(jié)點(diǎn)將出現(xiàn)3種可能：

（1）用于記錄new節(jié)點(diǎn)長(zhǎng)度所需內(nèi)存空間小于等于后繼節(jié)點(diǎn)prevlen域的表示長(zhǎng)度，即兩者相等（同為1字節(jié)或5字節(jié)）。則不需要對(duì)后繼節(jié)點(diǎn)進(jìn)行內(nèi)存空間擴(kuò)展，直接存儲(chǔ)前節(jié)點(diǎn)數(shù)據(jù)即可。

（2）后繼節(jié)點(diǎn)prevlen域長(zhǎng)度為5字節(jié)，能滿足記錄new節(jié)點(diǎn)的最大空間存儲(chǔ)需求，同上，不擴(kuò)展程序直接更新。

（3）new節(jié)點(diǎn)占用的內(nèi)存空間較大，后繼節(jié)點(diǎn)的prevlen域現(xiàn)有空間長(zhǎng)度不足以保存，程序必須對(duì)ziplist進(jìn)行內(nèi)存重新分配，并擴(kuò)展后繼節(jié)點(diǎn)的內(nèi)存空間。此種操作方式可能會(huì)引發(fā)連鎖更新問(wèn)題。

Redis壓縮列表連鎖更新過(guò)程如圖2所示。

2.2.2 連鎖更新產(chǎn)生的前提條件及出現(xiàn)頻率

在實(shí)際應(yīng)用中可能出現(xiàn)一種特殊情況，即ziplist在某一時(shí)刻存在多個(gè)連續(xù)的、長(zhǎng)度介于250字節(jié)到253字節(jié)之間的節(jié)點(diǎn)entry1至entryN，由于這N個(gè)節(jié)點(diǎn)長(zhǎng)度均小于254字節(jié)，那么entry1到entryN的prevlen域長(zhǎng)度均為1字節(jié)，此種情況的構(gòu)成是引發(fā)連鎖更新的前提條件，如圖3（a）所示。

若此時(shí)通過(guò)lpush命令（頭插法）插入一個(gè)長(zhǎng)度大于等于254字節(jié)的新節(jié)點(diǎn)“new”，插入后new節(jié)點(diǎn)將成為entry1的前驅(qū)節(jié)點(diǎn)，而此時(shí)entry1的prevlen域長(zhǎng)度為1字節(jié)，不能保存前驅(qū)節(jié)點(diǎn)new節(jié)點(diǎn)的長(zhǎng)度，需要通過(guò)內(nèi)存重新分配操作將entry1的prevlen域擴(kuò)展為5字節(jié)，實(shí)現(xiàn)entry的prevlen域更新。如圖3（b）所示。

圖2 壓縮列表連鎖更新流程圖

圖3 連鎖更新的產(chǎn)生條件及節(jié)點(diǎn)擴(kuò)展方式

同理，由于entry1之前的長(zhǎng)度介于250～253字節(jié)之間，當(dāng)完成prevlen域擴(kuò)展后entry1占用的內(nèi)存空間會(huì)大于等于254字節(jié)，而此時(shí)entry2的prevlen域長(zhǎng)度為1字節(jié)，因此亦需將entry2的prevlen域大小由1字節(jié)擴(kuò)展為5字節(jié)，隨著這一過(guò)程的不斷進(jìn)行，Redis需要不斷地對(duì)entry3至entryN的prevlen域大小進(jìn)行空間重新分配和內(nèi)存移動(dòng)，直到所有entry都滿足壓縮列表對(duì)每個(gè)節(jié)點(diǎn)的屬性要求，將這種連續(xù)的特殊entry所引發(fā)的連鎖操作稱為連鎖更新。同樣，當(dāng)Redis進(jìn)行壓縮列表刪除操作時(shí)也可能會(huì)引發(fā)連鎖更新。

由以上分析可知，連鎖更新產(chǎn)生頻繁程度取決于實(shí)際應(yīng)用數(shù)據(jù)大小，本文通過(guò)實(shí)驗(yàn)表明，實(shí)際應(yīng)用數(shù)據(jù)大小在250～253字節(jié)所占比例越大，則連鎖更新產(chǎn)生的幾率越大。

2.2.3 原算法時(shí)間復(fù)雜度分析

ziplist原更新算法的時(shí)間復(fù)雜度問(wèn)題要探究到一般情況和最壞情況。

現(xiàn)假設(shè)在列表區(qū)間需要擴(kuò)展更新的連續(xù)節(jié)點(diǎn)數(shù)為m（m=■rN■,0

則一共移動(dòng)

由等差公式得：

在一般情況下，由于插入或刪除而引起的連鎖更新的節(jié)點(diǎn)個(gè)數(shù)m(m?N)甚至不產(chǎn)生連鎖更新(m=0)，此時(shí)r→0，可設(shè)移動(dòng)一個(gè)節(jié)點(diǎn)位置一次的時(shí)間代價(jià)為T(1)，則對(duì)于產(chǎn)生m個(gè)點(diǎn)連鎖更新導(dǎo)致的移動(dòng)節(jié)點(diǎn)的總的時(shí)間代價(jià)為：

即在一般情況下，ziplist使用的時(shí)間復(fù)雜度為O(N)。

在最壞情況下，同樣設(shè)移動(dòng)一個(gè)節(jié)點(diǎn)位置一次的時(shí)間代價(jià)為T(1)，則對(duì)于產(chǎn)生的m個(gè)節(jié)點(diǎn)，r→1，連鎖更新導(dǎo)致的移動(dòng)節(jié)點(diǎn)的總的時(shí)間代價(jià)為：

所以在最壞情況下，ziplist使用的時(shí)間復(fù)雜度為O(N2)。

3 優(yōu)化方案

時(shí)間復(fù)雜度是衡量算法好壞的重要指標(biāo)。算法執(zhí)行時(shí)間是與算法中基本操作的執(zhí)行次數(shù)成正比。由此可知，原更新算法可進(jìn)一步優(yōu)化。優(yōu)化方案可以分別從算法更新流程和列表結(jié)構(gòu)兩個(gè)方面進(jìn)行考慮，后文將從這兩個(gè)方面分別對(duì)算法進(jìn)行優(yōu)化，并對(duì)二者的性能做分析。

3.1 連鎖更新優(yōu)化步驟與算法分析

通過(guò)2.2節(jié)分析可知，產(chǎn)生連鎖更新時(shí)間復(fù)雜度問(wèn)題的主要原因是：內(nèi)存重新分配操作以及內(nèi)存移動(dòng)操作兩個(gè)方面因素造成了不同程度的時(shí)間消耗。為優(yōu)化時(shí)間耗損，針對(duì)原壓縮列表更新過(guò)程不足，提出連鎖更新優(yōu)化算法方案，減少基本操作的執(zhí)行次數(shù)，使時(shí)間復(fù)雜度由O(N2)降為O(N)。

優(yōu)化后流程如圖4所示，有效避免了因擴(kuò)展節(jié)點(diǎn)導(dǎo)致的節(jié)點(diǎn)重復(fù)移動(dòng)。

優(yōu)化后算法步驟為：

（1）輸入更新前的ziplist的首地址 zl，以及原entry(k)節(jié)點(diǎn)的起始地址 p。

（2）從ziplist頭部信息獲取當(dāng)前ziplist所占內(nèi)存空間長(zhǎng)度：

圖4 壓縮列表連鎖更新優(yōu)化流程

（3）計(jì)算需要擴(kuò)充的內(nèi)存空間長(zhǎng)度extra。

（4）計(jì)算出內(nèi)容總共需要擴(kuò)充的空間extra之后，即可對(duì)ziplist進(jìn)行擴(kuò)充，從后往前進(jìn)行節(jié)點(diǎn)移動(dòng)，同時(shí)對(duì)需要更新prevlen字段的節(jié)點(diǎn)進(jìn)行擴(kuò)充更新。

（5）更新完成后返回zl，算法結(jié)束。

其中第（3）步，計(jì)算需要擴(kuò)充的內(nèi)存空間長(zhǎng)度extra的算法步驟為：

步驟1初始化extra=0。

步驟2判斷 p所指是否為ziplist的結(jié)尾，即若p=ZIPLIST_ENTRY_END（zl），則ziplist不需要擴(kuò)充內(nèi)存返回zl，算法結(jié)束；否則，執(zhí)行步驟3。

步驟3獲取 p所指當(dāng)前節(jié)點(diǎn)cur=ZlEntry(p)，ZlEntry(p)函數(shù)參數(shù)為某一節(jié)點(diǎn)首地址，功能是獲取 p所指的節(jié)點(diǎn)。

步驟4計(jì)算當(dāng)前節(jié)點(diǎn)在所占內(nèi)存空間大?。篟awlen=cur.prevlensize+cur.encodingsize+cur.contentsize。

步驟5判斷該節(jié)點(diǎn)是否為尾節(jié)點(diǎn)，即若p[Rawlen]=ZIP_END，則無(wú)后續(xù)節(jié)點(diǎn)需要擴(kuò)充，跳轉(zhuǎn)到步驟4；否則計(jì)算出存儲(chǔ)當(dāng)前節(jié)點(diǎn)長(zhǎng)度所需要的內(nèi)存空間長(zhǎng)度：

步驟6找到下一個(gè)節(jié)點(diǎn)：

步驟7判斷下一個(gè)節(jié)點(diǎn)是否需要更新prevlen字段記錄：

若next.prevlen=Rawlen，則下一個(gè)節(jié)點(diǎn)prevlen字段記錄的前置節(jié)點(diǎn)的長(zhǎng)度和當(dāng)前節(jié)點(diǎn)在內(nèi)存中所占空間長(zhǎng)度相等，則下一個(gè)節(jié)點(diǎn)不再需要更新，跳轉(zhuǎn)到步驟4。

否則，執(zhí)行步驟8。

步驟8判斷下一個(gè)節(jié)點(diǎn)prevlen字段是否需要擴(kuò)充：

若next.prevlensize≥Rawlensize，則表示下一個(gè)節(jié)點(diǎn)prevlen字段足夠記錄前置節(jié)點(diǎn)長(zhǎng)度，則只需要將下一個(gè)節(jié)點(diǎn)prevlen字段記錄的前置節(jié)點(diǎn)的長(zhǎng)度為更改為當(dāng)前節(jié)點(diǎn)的長(zhǎng)度即可。跳轉(zhuǎn)到步驟4。

若next.prevlensize

步驟9移動(dòng)到下一個(gè)節(jié)點(diǎn)，p=p+Rawlen；跳轉(zhuǎn)到步驟3。

優(yōu)化后操作是將長(zhǎng)度為L(zhǎng)的新節(jié)點(diǎn)插入到列表位置k，實(shí)現(xiàn)將數(shù)據(jù)對(duì)某個(gè)節(jié)點(diǎn)的前插操作，具體操作是先檢查插入或刪除的位置k合法性，然后查找表中第k-1個(gè)節(jié)點(diǎn)，統(tǒng)計(jì)后續(xù)節(jié)點(diǎn)所需擴(kuò)展空間大小，將其向后移動(dòng)一次。

優(yōu)化后節(jié)點(diǎn)插入示意圖如圖5所示，其中（b）是（a）移動(dòng)的最終結(jié)果，其中統(tǒng)計(jì)所需節(jié)點(diǎn)擴(kuò)展大小的主要操作為：

假設(shè)新節(jié)點(diǎn)的長(zhǎng)度為L(zhǎng)≥254字節(jié)，原列表有N個(gè)節(jié)點(diǎn)，插入位置為k，則前k-1個(gè)節(jié)點(diǎn)不需要移動(dòng)位置，第k+i個(gè)節(jié)點(diǎn)e(K+i)后移字節(jié)數(shù)為(L+(i+1)×EXPANSION)，其中 i=0,1,…,N-k,EXPANSION為擴(kuò)展字節(jié)數(shù)。

圖5 壓縮列表時(shí)間復(fù)雜度解決方案

假設(shè)new節(jié)點(diǎn)插入的位置共有n個(gè)，節(jié)點(diǎn)插入任意位置的概率相等，則new節(jié)點(diǎn)插入第k位置的概率Pk為設(shè)插入第k位置的總移動(dòng)次數(shù)為Tk。

時(shí)間復(fù)雜度算法推演步驟如下：

當(dāng)k=n時(shí)，移動(dòng)最后一個(gè)節(jié)點(diǎn)1次，Tn=1。

…

當(dāng)k=1時(shí)，全部節(jié)點(diǎn)各移動(dòng)1次，總共移動(dòng)n次，T1=n。

則推算移動(dòng)次數(shù)T的數(shù)學(xué)期望：

即平均移動(dòng)次數(shù)：

故優(yōu)化后的時(shí)間復(fù)雜度為O(N)。

優(yōu)化后Redis壓縮列表進(jìn)行連鎖更新操作時(shí)，對(duì)節(jié)點(diǎn)內(nèi)存空間重新分配及內(nèi)存移動(dòng)操作僅需進(jìn)行一次，而不是N次。即先進(jìn)行順序遍歷統(tǒng)計(jì)完成連鎖更新所需擴(kuò)展的內(nèi)存空間大小，然后進(jìn)行一次內(nèi)存空間重新分配操作，最后依次倒序?qū)ntry(N)～entry(K)進(jìn)行內(nèi)存移動(dòng)操作并對(duì)應(yīng)更新其prevlen域，從而所有節(jié)點(diǎn)僅需移動(dòng)1次。算法在耗時(shí)上優(yōu)于原算法，程序優(yōu)化后，連鎖更新的時(shí)間復(fù)雜度量級(jí)由O(N2)下降為O(N)。

3.2 連鎖更新優(yōu)化算法實(shí)現(xiàn)

從算法描述看出，_ziplistCascadeUpdate函數(shù)用來(lái)處理內(nèi)存空間級(jí)聯(lián)擴(kuò)展操作。當(dāng)一個(gè)新增節(jié)點(diǎn)需要插入列表時(shí)，如果原節(jié)點(diǎn)的prevlen不足以保存新節(jié)點(diǎn)的長(zhǎng)度，那么就需要進(jìn)行擴(kuò)展[19]。特別是這種擴(kuò)展操作又可能導(dǎo)致后繼節(jié)點(diǎn)需要擴(kuò)展[20]。如圖6所示，假設(shè)從e(k+1)到e(k+m)這m個(gè)節(jié)點(diǎn)需要連鎖更新，即均為1字節(jié)長(zhǎng)度。針對(duì)這一函數(shù)_ZiplistCascadeUpdate（）級(jí)聯(lián)更新函數(shù)優(yōu)化后算法實(shí)現(xiàn)的核心步驟為：

（1）初始化ziplst需要擴(kuò)充的內(nèi)存空間

（2）對(duì)i=k+1,k+2,…,k+m

（3）對(duì)i=n,n-1,…,k+m+1

（4）對(duì) i=k+m,k+m-1,…,k+j,…,k+1

（5）若k+m+1!=ZIPLIST_ENTRY_END(zl)

算法結(jié)束。

圖6 包含多節(jié)點(diǎn)的壓縮列表

3.3 連鎖更新算法優(yōu)化前后功能對(duì)比分析

為了直觀分析算法優(yōu)化前后功能差異，下面首先簡(jiǎn)單描述原算法的算法步驟。

優(yōu)化前算法核心步驟描述：

（1）對(duì) i=k+1,k+2,…,k+m

對(duì) j=n,n-1,…,i+1

Entrymove(j,j+EXPANSION);//節(jié)點(diǎn) j往后移動(dòng)EXPANSION個(gè)字節(jié)。

Enlarge(i);//節(jié)點(diǎn)i的起始地址不變，但是prevlen字段也擴(kuò)充了EXPANSION個(gè)字節(jié)。

Relength(i);//更新第i個(gè)節(jié)點(diǎn)的prevlen字段的值為前置節(jié)點(diǎn)更新之后的長(zhǎng)度。

（2）若k+m+1!=ZIPLIST_ENTRY_END(zl)Relength(k+m+1)

算法結(jié)束。

在優(yōu)化前的算法中，對(duì)于k+m+1節(jié)點(diǎn)及之后的節(jié)點(diǎn)，即i=k+m+1,i=k+m+2,…,n,每一個(gè)節(jié)點(diǎn)在內(nèi)存里位移量為：

L0(i)=EXPANSION×m

而對(duì)于i=k+1,k+2,…k+j,…,k+m,每一個(gè)節(jié)點(diǎn)在內(nèi)存里位移量

L0(i)=EXPANSION×(j-1)

而對(duì)于e(k)節(jié)點(diǎn)及之前的節(jié)點(diǎn)都未移動(dòng)，位移量為零。即，i=1,2,…,k,有：

L1(i)=0

在優(yōu)化后的算法中，對(duì)于k+m+1節(jié)點(diǎn)及之后連續(xù)的節(jié)點(diǎn)，即i=k+m+1,i=k+m+2,…,n,每一個(gè)節(jié)點(diǎn)在內(nèi)存里位移量為：

L1(i)=extra

而對(duì)于i=k+1,k+2,…,k+j,…,k+m,每一個(gè)節(jié)點(diǎn)在內(nèi)存里位移量為：

L1(i)=extra-EXPANSION×(m-j+1)

而對(duì)于e(k)節(jié)點(diǎn)及之前的節(jié)點(diǎn)都未移動(dòng)，位移量為零。即，i=1,i=2,…,k,有：

L1(i)=0

將_ZiplistCascadeUpdate（）函數(shù)優(yōu)化前后效果進(jìn)行對(duì)比分析可得：

優(yōu)化后算法中extra=EXPANSION×m。

則對(duì)于ziplist中k+m+1節(jié)點(diǎn)及之后的節(jié)點(diǎn)，有：

對(duì)于ziplist中k+1節(jié)點(diǎn)到k+m節(jié)點(diǎn)，有：

對(duì)于ziplist中k節(jié)點(diǎn)及之前的節(jié)點(diǎn)都有：

通過(guò)對(duì)比發(fā)現(xiàn)，優(yōu)化前后的_ZiplistCascadeUpdate（）函數(shù)使ziplist上每個(gè)節(jié)點(diǎn)在內(nèi)存中最終的相對(duì)位置和狀態(tài)完全一致，所以_ZiplistCascadeUpdate（）函數(shù)優(yōu)化前后功能等效。

3.4 結(jié)構(gòu)優(yōu)化

優(yōu)化結(jié)構(gòu)之后重新編譯redis，在服務(wù)器的實(shí)驗(yàn)環(huán)境下，通過(guò)模擬實(shí)驗(yàn)驗(yàn)證其功能，在后期將對(duì)結(jié)構(gòu)優(yōu)化問(wèn)題進(jìn)行深入討論研究，此處只對(duì)算法做簡(jiǎn)要討論，提供解決思路。

重新設(shè)計(jì)的壓縮列表連鎖更新處理流程，雖能將時(shí)間復(fù)雜度降為O(N)，但仍存在連鎖更新問(wèn)題，其根源在于當(dāng)前節(jié)點(diǎn)的prevlen域長(zhǎng)度會(huì)根據(jù)前驅(qū)節(jié)點(diǎn)的大小進(jìn)行動(dòng)態(tài)調(diào)整。prevlen域用于實(shí)現(xiàn)壓縮列表逆序遍歷，若將其替換為entry_length域放置在節(jié)點(diǎn)末尾來(lái)記錄當(dāng)前節(jié)點(diǎn)長(zhǎng)度，亦可實(shí)現(xiàn)逆序遍歷。entry_length域編碼方式與prevlen域一樣，但需逆向解析，即若當(dāng)前節(jié)點(diǎn)長(zhǎng)度大于等于254，entry_length域占5字節(jié)，末字節(jié)為固定值0xFE，標(biāo)識(shí)前4字節(jié)表示當(dāng)前節(jié)點(diǎn)長(zhǎng)度，此時(shí)可使用屬性zllen結(jié)合entry_length域獲取末尾節(jié)點(diǎn)位置，故可刪除屬性zltail。

優(yōu)化后的壓縮列表如圖7所示。

圖7 優(yōu)化后的壓縮列表結(jié)構(gòu)

圖7 （b）中enconding記錄整數(shù)編碼占用1字節(jié)，content存放整數(shù)內(nèi)容占用5字節(jié)，entry_length域用于存放自身節(jié)點(diǎn)在內(nèi)存空間中的長(zhǎng)度，所示節(jié)點(diǎn)總長(zhǎng)度占用6字節(jié)小于254字節(jié)，則entry_length用1字節(jié)表示即可，記錄為0x6。由圖7（a）、（b）中對(duì)比看出，結(jié)構(gòu)體優(yōu)化從根本上改變了原結(jié)構(gòu)記錄前驅(qū)節(jié)點(diǎn)長(zhǎng)度的特征。

在保證算法正常逆序遍歷，且按上文所示對(duì)節(jié)點(diǎn)進(jìn)行存儲(chǔ)結(jié)構(gòu)調(diào)整，優(yōu)化后的算法功能和原算法功能是等效的。對(duì)算法的功能及性能的驗(yàn)證在實(shí)驗(yàn)過(guò)程中將做詳細(xì)的對(duì)比分析。

結(jié)構(gòu)調(diào)整后優(yōu)化算法逆序遍歷的實(shí)現(xiàn)步驟：

步驟1輸入壓縮列表ziplist，其首地址為zl。

步驟2 解析zl前6個(gè)字節(jié)，獲取zl信息，得到zlbytes、zllen。

步驟3找到尾節(jié)點(diǎn)tail,tail=zl+zlbytes-2，同時(shí)將指針p指向zl尾節(jié)點(diǎn)的最后一個(gè)字節(jié)位置。

步驟4判斷鏈表是否已經(jīng)遍歷完或者鏈表為空，若遍歷完成或者鏈表為空，算法結(jié)束，否則執(zhí)行步驟5。

步驟5解析當(dāng)前節(jié)點(diǎn)的Entry_Length字段，確定指針 p所指節(jié)點(diǎn)的實(shí)際空間長(zhǎng)度len以及用來(lái)表示該長(zhǎng)度的變量lensize的值（1字節(jié)或5字節(jié)）。

步驟6解析節(jié)點(diǎn)的encoding字段：

首先執(zhí)行操作 ptr=p-len+1，此時(shí) ptr指向 p指向的當(dāng)前節(jié)點(diǎn)的encoding字段的首地址。調(diào)用解析出編碼當(dāng)前節(jié)點(diǎn)所需的內(nèi)存空間長(zhǎng)度encodingsize和當(dāng)前節(jié)點(diǎn)真實(shí)內(nèi)容長(zhǎng)度contentlen。

步驟7訪問(wèn)當(dāng)前節(jié)點(diǎn)的實(shí)際數(shù)據(jù)content字段：

以ptr+=encodingsize為起始位置的長(zhǎng)度為contentlen的連續(xù)內(nèi)存空間上存放的便是當(dāng)前節(jié)點(diǎn)的實(shí)際數(shù)據(jù)content。

步驟8指針 p往前移動(dòng)一個(gè)節(jié)點(diǎn)長(zhǎng)度，然后轉(zhuǎn)向步驟4。

4 實(shí)驗(yàn)測(cè)試與結(jié)果分析

為驗(yàn)證新算法性能，抽取可靠數(shù)據(jù)樣本，對(duì)連鎖更新優(yōu)化前后Redis服務(wù)器對(duì)于壓縮列表進(jìn)行插入操作時(shí)的處理速度進(jìn)行統(tǒng)計(jì)與對(duì)比分析[21]。

4.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)所需測(cè)試環(huán)境為服務(wù)器1臺(tái)，配置如下：Intel?Xeon?CPU E5-2620 v2 6核12線程CPU，32 GB內(nèi)存，240 GB硬盤，操作系統(tǒng)采用Ubuntu16.04LTS版本，數(shù)據(jù)庫(kù)為Redis3.0.3版本，腳本環(huán)境為Ptyhon3.4.6。

4.2 實(shí)驗(yàn)步驟

考慮特定情況下執(zhí)行時(shí)間存在一定的隨機(jī)性，為方便實(shí)驗(yàn)結(jié)果對(duì)比，本實(shí)驗(yàn)采用python隨機(jī)生成10組字符串?dāng)?shù)據(jù)樣本，重復(fù)實(shí)驗(yàn)50次，取其結(jié)果的平均值。

實(shí)驗(yàn)采用的步驟為：首先通過(guò)lpush命令插入單個(gè)長(zhǎng)度為250～253字節(jié)長(zhǎng)度的數(shù)據(jù)樣本到Redis數(shù)據(jù)庫(kù)，隨后通過(guò)插入長(zhǎng)度為255字節(jié)的數(shù)據(jù)，來(lái)觸發(fā)連鎖更新機(jī)制，最后統(tǒng)計(jì)優(yōu)化前后兩個(gè)版本的Redis數(shù)據(jù)庫(kù)實(shí)例處理每組數(shù)據(jù)樣本所需的時(shí)間消耗，緩存占用，性能變化等數(shù)據(jù)，用來(lái)做實(shí)驗(yàn)對(duì)比。

實(shí)驗(yàn)過(guò)程中，每插入下一組數(shù)據(jù)樣本前，對(duì)Redis數(shù)據(jù)庫(kù)進(jìn)行清空操作，刪除上一次數(shù)據(jù)樣本的所有數(shù)據(jù)，以確保每組數(shù)據(jù)插入前的初始環(huán)境狀態(tài)完全一致。

壓縮列表連鎖更新測(cè)試方案設(shè)計(jì)如圖8所示。

4.3 實(shí)驗(yàn)結(jié)果分析

4.3.1 連鎖更新時(shí)間消耗對(duì)比

針對(duì)連鎖更新的時(shí)間消耗對(duì)比問(wèn)題，實(shí)驗(yàn)過(guò)程中每次從10 000個(gè)數(shù)據(jù)量開始，每次疊加10 000個(gè)數(shù)據(jù)量，最高為100 000個(gè)數(shù)據(jù)量，重復(fù)50次后，取其平均值進(jìn)行對(duì)比驗(yàn)證。

圖8 壓縮列表連鎖更新測(cè)試方案

相同數(shù)據(jù)量下的連鎖更新優(yōu)化前后的時(shí)間消耗對(duì)比如圖9所示。

圖9 連鎖更新時(shí)間消耗對(duì)比

對(duì)比以上數(shù)據(jù)和曲線圖可以看出，優(yōu)化了壓縮列表連鎖更新問(wèn)題的Redis數(shù)據(jù)庫(kù)實(shí)例在處理相同數(shù)據(jù)量，相同連鎖更新的情況下，時(shí)間消耗更少。

另在實(shí)驗(yàn)過(guò)程中，對(duì)每次Redis數(shù)據(jù)庫(kù)實(shí)例插入數(shù)據(jù)時(shí)所占用內(nèi)存空間進(jìn)行采集，多次重復(fù)實(shí)驗(yàn)后取其平均值，得到表1數(shù)據(jù)。

表1 連鎖更新優(yōu)化前后緩存消耗對(duì)比

對(duì)比優(yōu)化前后的Redis實(shí)例內(nèi)存占用情況，在數(shù)據(jù)量相同的情況下，優(yōu)化后的Redis數(shù)據(jù)庫(kù)實(shí)例，通過(guò)對(duì)相同數(shù)據(jù)量情況下的連鎖更新消耗時(shí)間以及內(nèi)存占用情況的對(duì)比驗(yàn)證，在不影響Redis原有功能的前提下，表明優(yōu)化后的連鎖更新耗時(shí)更少，處理相等數(shù)據(jù)量的緩存消耗穩(wěn)定。

4.3.2 優(yōu)化后Redis服務(wù)器插入性能

為了驗(yàn)證連鎖更新重新設(shè)計(jì)實(shí)現(xiàn)后，Redis服務(wù)器壓縮列表增刪等操作性能是否有所提升或者下降，使用了ziplist自帶的測(cè)試工具對(duì)壓縮列表在列表頭部與列表尾部進(jìn)行push+pop操作，對(duì)比連鎖更新優(yōu)化前后壓縮列表插入、刪除操作的處理速度效率[2]。連鎖更新優(yōu)化前后壓縮列表使用頭插法（HEAD）與尾插法（TAIL）兩種不同操作方式處理相同數(shù)據(jù)量所需時(shí)間分布如圖10所示。

圖10 頭插法與尾插法處理時(shí)間消耗對(duì)比

實(shí)驗(yàn)數(shù)據(jù)對(duì)比分析統(tǒng)計(jì)結(jié)果發(fā)現(xiàn)，連鎖更新優(yōu)化前后壓縮列表進(jìn)行push+pop操作所需的處理時(shí)間效率基本一致，并不影響原有的操作處理效率[22]。但不同的操作頭插法與尾插法的操作效率差別較大，頭插法算法簡(jiǎn)單但在鏈表中節(jié)點(diǎn)的次序和輸入數(shù)據(jù)的順序不一致，若希望兩者次序一致，可采用尾插法。該方法是將新節(jié)點(diǎn)插入到當(dāng)前鏈表的尾部上，為此必須加一個(gè)位指針r，使其始終指向當(dāng)前鏈表的尾部節(jié)點(diǎn)。

同時(shí)，從壓縮列表頭插法（HEAD）與尾插法（TAIL）處理時(shí)間消耗分布圖還可以看出，壓縮列表使用頭插法進(jìn)行數(shù)據(jù)增加、刪除操作所需處理時(shí)間遠(yuǎn)大于使用尾插法進(jìn)行數(shù)據(jù)增加、刪除操作所需處理時(shí)間，這是因?yàn)轭^插法（HEAD）操作比尾插法（TAIL）操作增加了一個(gè)內(nèi)存移動(dòng)過(guò)程，數(shù)據(jù)量越大，所需移動(dòng)內(nèi)存字節(jié)數(shù)越多，因此所需時(shí)間更多。

對(duì)比優(yōu)化前后兩個(gè)Redis服務(wù)器實(shí)例在處理相同連鎖更新情況的數(shù)據(jù)，優(yōu)化前的Redis數(shù)據(jù)庫(kù)實(shí)例隨著數(shù)據(jù)的增加，處理連鎖更新所占用時(shí)間也隨之增加，反之優(yōu)化后的Redis服務(wù)器實(shí)例所花費(fèi)的時(shí)間增長(zhǎng)緩慢，從實(shí)驗(yàn)結(jié)果可以看出，優(yōu)化后的壓縮列表在處理連鎖更新過(guò)程上所消耗的時(shí)間大大減少，從側(cè)面反映出當(dāng)數(shù)據(jù)量越來(lái)越大，優(yōu)化后的處理連鎖更新所用的時(shí)間復(fù)雜度也從O(N2)減少成O(N)，驗(yàn)證了論文中的方案設(shè)計(jì)思路。

4.3.3結(jié)構(gòu)優(yōu)化后連鎖更新時(shí)間消耗對(duì)比

為了驗(yàn)證結(jié)構(gòu)體優(yōu)化后的作用，實(shí)驗(yàn)過(guò)程中分別采用了3個(gè)Redis數(shù)據(jù)庫(kù)實(shí)例進(jìn)行對(duì)比驗(yàn)證，分別為：

實(shí)例1沒(méi)有采用任何優(yōu)化的原始?jí)嚎s列表。

實(shí)例2采用優(yōu)化連鎖更新算法后的壓縮列表。

實(shí)例3采用優(yōu)化結(jié)構(gòu)體的壓縮列表。

對(duì)這3個(gè)Redis實(shí)例進(jìn)行數(shù)據(jù)插入，通過(guò)與4.3.1小節(jié)相同的實(shí)驗(yàn)方式對(duì)結(jié)構(gòu)體優(yōu)化后壓縮列表進(jìn)行的測(cè)試。分別采集不同數(shù)據(jù)量情況下壓縮列表進(jìn)行連鎖更新所消耗的時(shí)間，得到的數(shù)據(jù)如表2所示。

表2 結(jié)構(gòu)體優(yōu)化前后連鎖更新時(shí)間消耗對(duì)比

連鎖更新時(shí)間消耗對(duì)比曲線圖如圖11所示。

圖11 結(jié)構(gòu)體優(yōu)化前后連鎖更新時(shí)間消耗對(duì)比

從上述數(shù)據(jù)可以看出，采用了結(jié)構(gòu)體優(yōu)化壓縮列表的Redis實(shí)例，和采用了連鎖更新算法優(yōu)化壓縮列表的Redis實(shí)例，在處理相同數(shù)據(jù)量的情況下，所消耗的時(shí)間幾乎一致，相比較優(yōu)化的原始?jí)嚎s列表Redis實(shí)例消耗的時(shí)間少，同時(shí)表明，結(jié)構(gòu)體優(yōu)化后的壓縮列表與優(yōu)化了連鎖更新算法的壓縮列表在處理連鎖更新方面時(shí)間復(fù)雜度幾乎一致。

4.3.4 結(jié)構(gòu)體優(yōu)化后性能驗(yàn)證

（1）固定數(shù)據(jù)插入對(duì)比驗(yàn)證

針對(duì)結(jié)構(gòu)體優(yōu)化前后，數(shù)據(jù)插入耗時(shí)的對(duì)比，實(shí)驗(yàn)采用兩個(gè)不同的壓縮列表實(shí)例，一個(gè)優(yōu)化了結(jié)構(gòu)體，另一個(gè)維持原狀態(tài)，通過(guò)對(duì)這兩個(gè)壓縮列表分別插入1萬(wàn)～5萬(wàn)個(gè)節(jié)點(diǎn)數(shù)據(jù)（單節(jié)點(diǎn)長(zhǎng)度固定為250個(gè)字節(jié)），采集每次插入所消耗的時(shí)間，多次重復(fù)后取其平均值，對(duì)比優(yōu)化前后的時(shí)間消耗，得到優(yōu)化前后時(shí)間消耗對(duì)比曲線圖，如圖12所示。

通過(guò)以上數(shù)據(jù)可以表明，在不造成連鎖更新的情況下，結(jié)構(gòu)體優(yōu)化前后，插入數(shù)據(jù)所消耗的時(shí)間幾乎等效，不會(huì)對(duì)壓縮列表的性能造成影響。

圖12 結(jié)構(gòu)體優(yōu)化前后無(wú)連鎖更新時(shí)耗時(shí)對(duì)比

（2）隨機(jī)數(shù)據(jù)插入對(duì)比驗(yàn)證

實(shí)驗(yàn)采用1萬(wàn)～10萬(wàn)個(gè)單個(gè)長(zhǎng)度在1～500字節(jié)的節(jié)點(diǎn)，在結(jié)構(gòu)體優(yōu)化前后的壓縮列表采用隨機(jī)頭插、尾插的方式進(jìn)行插入操作，記錄壓縮列表消耗的時(shí)間，重復(fù)多次實(shí)驗(yàn)后，取其平均值后，得出的數(shù)據(jù)如圖13所示。

圖13 結(jié)構(gòu)體優(yōu)化前后隨機(jī)插入時(shí)間消耗對(duì)比

上述實(shí)驗(yàn)數(shù)據(jù)表明一般情況下，結(jié)構(gòu)體優(yōu)化后對(duì)壓縮列表插入的數(shù)據(jù)量越大時(shí)，優(yōu)化效果越明顯。

通過(guò)多次對(duì)比實(shí)驗(yàn)驗(yàn)證了兩種優(yōu)化方案的性能，實(shí)驗(yàn)測(cè)試效果表明，兩種方案在最壞情況下對(duì)壓縮列表的性能優(yōu)化明顯，通常情況下，插入的數(shù)據(jù)量越大優(yōu)化效果越明顯。

5 總結(jié)

Redis壓縮列表連鎖更新機(jī)制，最壞情況下時(shí)間復(fù)雜度為O(N2)。針對(duì)此情況，提出兩種解決方案，第一種是通過(guò)設(shè)計(jì)新的算法，在原連鎖更新機(jī)制的基礎(chǔ)上，先進(jìn)行順序遍歷統(tǒng)計(jì)完成連鎖更新所需擴(kuò)展的內(nèi)存空間，然后進(jìn)行一次內(nèi)存空間重新分配操作，從而將連鎖更新的時(shí)間復(fù)雜度降為O(N)。第二種給出壓縮列表結(jié)構(gòu)體優(yōu)化方案，在不影響原有功能的基礎(chǔ)上消除了存儲(chǔ)節(jié)點(diǎn)時(shí)由于連鎖更導(dǎo)致的時(shí)間復(fù)雜度偏大問(wèn)題。由實(shí)驗(yàn)結(jié)果分析可知，結(jié)構(gòu)體優(yōu)化后的壓縮列表讀寫操作性能獲得了明顯提升，實(shí)現(xiàn)了性能優(yōu)化。

兩種方案都有效減少了原方案在出現(xiàn)大量連鎖更新時(shí)的時(shí)間消耗，但是所提出的優(yōu)化方案是否適合所有場(chǎng)景，在實(shí)際應(yīng)用場(chǎng)景中是否也有較好的效果，還需要做進(jìn)一步探討。在優(yōu)化連鎖更新算法方面，針對(duì)字符串的長(zhǎng)度有較大限制的場(chǎng)景中，這種優(yōu)化效果尤為明顯，比如在對(duì)字符長(zhǎng)度有要求且用戶量巨大的的微博、Twitter等應(yīng)用，在后續(xù)工作中，會(huì)著重對(duì)各種實(shí)際應(yīng)用場(chǎng)景進(jìn)行測(cè)試，以驗(yàn)證優(yōu)化的連鎖更新算法在實(shí)際應(yīng)用中的效果。在結(jié)構(gòu)優(yōu)化方面，后續(xù)將對(duì)Redis底層知識(shí)進(jìn)行深入研究，將實(shí)驗(yàn)擴(kuò)展到實(shí)際應(yīng)用環(huán)境中，此處只對(duì)算法做簡(jiǎn)要討論，為后期進(jìn)一步優(yōu)化提供解決思路。