Redis壓縮列表研究與優化設計

張慧寧，李擁軍，王紹東

1.廣東石油化工學院 實驗教學部，廣東 茂名 525000

2.華南理工大學 計算機科學與工程學院，廣州 510006

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

1 引言

傳統關系型數據庫建立在關系模型基礎上，借助集合代數等數學概念和方法來處理數據庫中的數據[1-3]。隨著互聯網業務與數據量逐漸增大，傳統數據庫存在單機（單庫）性能瓶頸且擴展困難的先天性缺陷，無法滿足日益增長的海量數據存儲及其超高并發數據讀寫性能要求，從而衍生出各種不同的NoSQL數據庫產品[4-7]。NoSQL簡單、易于大規模分布式擴展，并且讀寫性能優越，常見的有Redis、MemCached以及MongoDB等，其中Redis不僅讀寫性能高，支持多種數據結構，支持數據持久化，而被廣泛使用[4，8]。

Redis作為一個開源Key-Value模型分布式內存數據庫，可將用戶全部數據分布存儲在節點內存空間，極大提升了數據讀寫操作效率[7]。其包含列表、字符串、集合、哈希、有序集合5種Redis數據結構類型[8-11]。同時每種數據結構類型針對不同應用場景支持不同編碼方式，壓縮列表（ziplist）為其中之一。

由于壓縮列表能節約內存，因此哈希鍵、列表鍵和有序集合鍵初始化的底層實現皆采用壓縮列表。壓縮列表通過節點的previous_entry_length域（見圖1）保存前驅節點長度，便于存儲數據時實現查找。但此方法連鎖更新時間復雜度為O(N2)。具體分析見2.2節。

本文針對Redis壓縮列表連鎖更新過程中時間復雜度優化問題，設計了新的內存空間級聯擴展操作方式，以降低連鎖更新時的時間復雜度，同時優化結構體，提升壓縮列表操作性能。

2 Redis壓縮列表研究

2.1 壓縮列表結構

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

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

zlbytes記錄整個ziplist占用的內存字節總數；zltail記錄ziplist表尾節點距離起始位置偏移字節數大小（即最后一個節點到壓縮列表的起始位置字節數量）；zllen記錄ziplist包含的節點總數量，但當節點數超過65 535時則需重新遍歷整個ziplist才能計算得出節點數量。zlentry保存長度受限的字符數組或整數數組。結尾符zlend用于標記ziplist末端，為特殊值0xFF。

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

entry的prevlen域用于記錄前驅節點所占內存空間字節數，具有1字節或5字節存儲形態。5字節存儲實例如圖1（b）所示，當整體編碼值為0xFE000007E1，其中值的最高位字節以0xFE表示，之后4字節0x000007E1（十進制值2017）是前驅節點的實際長度。encoding域，用于記錄content存儲內容的編碼方式。若encoding域首字節高兩位為11則content域存儲內容為整數編碼，否則以字節數組編碼表示。末端content域用于存儲實際的數據，因此Content域存放的是（十進制值2018）當前節點的值。

壓縮列表中每個entry所包含的所有字節位相關的特殊含義都可以通過解析函數zipEntry（）使用結構本體zlentry保存，prevrawlensize域記錄prevlen域的大小是1或者5，prevrawlen域記錄前驅節點所占內存空間字節數，lensize域記錄encoding所占內存空間字節數，len域則記錄content的長度，hadersize域表示節點的頭部大小，保存prevlen與encoding的長度之和，encoding域保存content存儲數據的編碼方式，指針p則指向content存儲的數據內容。

圖1 壓縮列表數據結構

綜上所述，Redis壓縮列表適用于小數據量的高性能操作，專注運算上效率的提升。從壓縮列表的設計結構中不難看出其緊湊的存儲方式對降低內存占用有著明顯優勢。

2.2 壓縮列表連鎖更新問題分析

2.2.1 產生連鎖更新的原因

壓縮列表以節點形式存儲，可以有任意多個節點。entry的prevlen域占用的內存空間大小是根據前驅節點長度決定為1字節或者5字節。若首字節為特殊字符0xFE，則表示prevlen域占據5字節內存空間，之后4字節表示前驅節點所占據的內存空間字節數，否則只使用首字節表示前驅節點所占內存空間大小，即1字節長度。因此當ziplist刪除一個entry或者新增一個entry時，后繼節點的prevlen域所占內存空間大小可能會隨之發生改變[18-19]。這種可靈活擴展的特性是直接引發連鎖更新問題的根本原因。

壓縮列表的存儲數據形式等同于增加節點，而增加節點將出現3種可能：

（1）用于記錄new節點長度所需內存空間小于等于后繼節點prevlen域的表示長度，即兩者相等（同為1字節或5字節）。則不需要對后繼節點進行內存空間擴展，直接存儲前節點數據即可。

（2）后繼節點prevlen域長度為5字節，能滿足記錄new節點的最大空間存儲需求，同上，不擴展程序直接更新。

（3）new節點占用的內存空間較大，后繼節點的prevlen域現有空間長度不足以保存，程序必須對ziplist進行內存重新分配，并擴展后繼節點的內存空間。此種操作方式可能會引發連鎖更新問題。

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

2.2.2 連鎖更新產生的前提條件及出現頻率

在實際應用中可能出現一種特殊情況，即ziplist在某一時刻存在多個連續的、長度介于250字節到253字節之間的節點entry1至entryN，由于這N個節點長度均小于254字節，那么entry1到entryN的prevlen域長度均為1字節，此種情況的構成是引發連鎖更新的前提條件，如圖3（a）所示。

若此時通過lpush命令（頭插法）插入一個長度大于等于254字節的新節點“new”，插入后new節點將成為entry1的前驅節點，而此時entry1的prevlen域長度為1字節，不能保存前驅節點new節點的長度，需要通過內存重新分配操作將entry1的prevlen域擴展為5字節，實現entry的prevlen域更新。如圖3（b）所示。

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

圖3 連鎖更新的產生條件及節點擴展方式

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

由以上分析可知，連鎖更新產生頻繁程度取決于實際應用數據大小，本文通過實驗表明，實際應用數據大小在250～253字節所占比例越大，則連鎖更新產生的幾率越大。

2.2.3 原算法時間復雜度分析

ziplist原更新算法的時間復雜度問題要探究到一般情況和最壞情況。

現假設在列表區間需要擴展更新的連續節點數為m（m=■rN■,0

則一共移動

由等差公式得：

在一般情況下，由于插入或刪除而引起的連鎖更新的節點個數m(m?N)甚至不產生連鎖更新(m=0)，此時r→0，可設移動一個節點位置一次的時間代價為T(1)，則對于產生m個點連鎖更新導致的移動節點的總的時間代價為：

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

在最壞情況下，同樣設移動一個節點位置一次的時間代價為T(1)，則對于產生的m個節點，r→1，連鎖更新導致的移動節點的總的時間代價為：

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

3 優化方案

時間復雜度是衡量算法好壞的重要指標。算法執行時間是與算法中基本操作的執行次數成正比。由此可知，原更新算法可進一步優化。優化方案可以分別從算法更新流程和列表結構兩個方面進行考慮，后文將從這兩個方面分別對算法進行優化，并對二者的性能做分析。

3.1 連鎖更新優化步驟與算法分析

通過2.2節分析可知，產生連鎖更新時間復雜度問題的主要原因是：內存重新分配操作以及內存移動操作兩個方面因素造成了不同程度的時間消耗。為優化時間耗損，針對原壓縮列表更新過程不足，提出連鎖更新優化算法方案，減少基本操作的執行次數，使時間復雜度由O(N2)降為O(N)。

優化后流程如圖4所示，有效避免了因擴展節點導致的節點重復移動。

優化后算法步驟為：

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

（2）從ziplist頭部信息獲取當前ziplist所占內存空間長度：

圖4 壓縮列表連鎖更新優化流程

（3）計算需要擴充的內存空間長度extra。

（4）計算出內容總共需要擴充的空間extra之后，即可對ziplist進行擴充，從后往前進行節點移動，同時對需要更新prevlen字段的節點進行擴充更新。

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

其中第（3）步，計算需要擴充的內存空間長度extra的算法步驟為：

步驟1初始化extra=0。

步驟2判斷 p所指是否為ziplist的結尾，即若p=ZIPLIST_ENTRY_END（zl），則ziplist不需要擴充內存返回zl，算法結束；否則，執行步驟3。

步驟3獲取 p所指當前節點cur=ZlEntry(p)，ZlEntry(p)函數參數為某一節點首地址，功能是獲取 p所指的節點。

步驟4計算當前節點在所占內存空間大小：Rawlen=cur.prevlensize+cur.encodingsize+cur.contentsize。

步驟5判斷該節點是否為尾節點，即若p[Rawlen]=ZIP_END，則無后續節點需要擴充，跳轉到步驟4；否則計算出存儲當前節點長度所需要的內存空間長度：

步驟6找到下一個節點：

步驟7判斷下一個節點是否需要更新prevlen字段記錄：

若next.prevlen=Rawlen，則下一個節點prevlen字段記錄的前置節點的長度和當前節點在內存中所占空間長度相等，則下一個節點不再需要更新，跳轉到步驟4。

否則，執行步驟8。

步驟8判斷下一個節點prevlen字段是否需要擴充：

若next.prevlensize≥Rawlensize，則表示下一個節點prevlen字段足夠記錄前置節點長度，則只需要將下一個節點prevlen字段記錄的前置節點的長度為更改為當前節點的長度即可。跳轉到步驟4。

若next.prevlensize

步驟9移動到下一個節點，p=p+Rawlen；跳轉到步驟3。

優化后操作是將長度為L的新節點插入到列表位置k，實現將數據對某個節點的前插操作，具體操作是先檢查插入或刪除的位置k合法性，然后查找表中第k-1個節點，統計后續節點所需擴展空間大小，將其向后移動一次。

優化后節點插入示意圖如圖5所示，其中（b）是（a）移動的最終結果，其中統計所需節點擴展大小的主要操作為：

假設新節點的長度為L≥254字節，原列表有N個節點，插入位置為k，則前k-1個節點不需要移動位置，第k+i個節點e(K+i)后移字節數為(L+(i+1)×EXPANSION)，其中 i=0,1,…,N-k,EXPANSION為擴展字節數。

圖5 壓縮列表時間復雜度解決方案

假設new節點插入的位置共有n個，節點插入任意位置的概率相等，則new節點插入第k位置的概率Pk為設插入第k位置的總移動次數為Tk。

時間復雜度算法推演步驟如下：

當k=n時，移動最后一個節點1次，Tn=1。

…

當k=1時，全部節點各移動1次，總共移動n次，T1=n。

則推算移動次數T的數學期望：

即平均移動次數：

故優化后的時間復雜度為O(N)。

優化后Redis壓縮列表進行連鎖更新操作時，對節點內存空間重新分配及內存移動操作僅需進行一次，而不是N次。即先進行順序遍歷統計完成連鎖更新所需擴展的內存空間大小，然后進行一次內存空間重新分配操作，最后依次倒序對entry(N)～entry(K)進行內存移動操作并對應更新其prevlen域，從而所有節點僅需移動1次。算法在耗時上優于原算法，程序優化后，連鎖更新的時間復雜度量級由O(N2)下降為O(N)。

3.2 連鎖更新優化算法實現

從算法描述看出，_ziplistCascadeUpdate函數用來處理內存空間級聯擴展操作。當一個新增節點需要插入列表時，如果原節點的prevlen不足以保存新節點的長度，那么就需要進行擴展[19]。特別是這種擴展操作又可能導致后繼節點需要擴展[20]。如圖6所示，假設從e(k+1)到e(k+m)這m個節點需要連鎖更新，即均為1字節長度。針對這一函數_ZiplistCascadeUpdate（）級聯更新函數優化后算法實現的核心步驟為：

（1）初始化ziplst需要擴充的內存空間

（2）對i=k+1,k+2,…,k+m

（3）對i=n,n-1,…,k+m+1

（4）對 i=k+m,k+m-1,…,k+j,…,k+1

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

算法結束。

圖6 包含多節點的壓縮列表

3.3 連鎖更新算法優化前后功能對比分析

為了直觀分析算法優化前后功能差異，下面首先簡單描述原算法的算法步驟。

優化前算法核心步驟描述：

（1）對 i=k+1,k+2,…,k+m

對 j=n,n-1,…,i+1

Entrymove(j,j+EXPANSION);//節點 j往后移動EXPANSION個字節。

Enlarge(i);//節點i的起始地址不變，但是prevlen字段也擴充了EXPANSION個字節。

Relength(i);//更新第i個節點的prevlen字段的值為前置節點更新之后的長度。

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

算法結束。

在優化前的算法中，對于k+m+1節點及之后的節點，即i=k+m+1,i=k+m+2,…,n,每一個節點在內存里位移量為：

L0(i)=EXPANSION×m

而對于i=k+1,k+2,…k+j,…,k+m,每一個節點在內存里位移量

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

而對于e(k)節點及之前的節點都未移動，位移量為零。即，i=1,2,…,k,有：

L1(i)=0

在優化后的算法中，對于k+m+1節點及之后連續的節點，即i=k+m+1,i=k+m+2,…,n,每一個節點在內存里位移量為：

L1(i)=extra

而對于i=k+1,k+2,…,k+j,…,k+m,每一個節點在內存里位移量為：

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

而對于e(k)節點及之前的節點都未移動，位移量為零。即，i=1,i=2,…,k,有：

L1(i)=0

將_ZiplistCascadeUpdate（）函數優化前后效果進行對比分析可得：

優化后算法中extra=EXPANSION×m。

則對于ziplist中k+m+1節點及之后的節點，有：

對于ziplist中k+1節點到k+m節點，有：

對于ziplist中k節點及之前的節點都有：

通過對比發現，優化前后的_ZiplistCascadeUpdate（）函數使ziplist上每個節點在內存中最終的相對位置和狀態完全一致，所以_ZiplistCascadeUpdate（）函數優化前后功能等效。

3.4 結構優化

優化結構之后重新編譯redis，在服務器的實驗環境下，通過模擬實驗驗證其功能，在后期將對結構優化問題進行深入討論研究，此處只對算法做簡要討論，提供解決思路。

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

優化后的壓縮列表如圖7所示。

圖7 優化后的壓縮列表結構

圖7 （b）中enconding記錄整數編碼占用1字節，content存放整數內容占用5字節，entry_length域用于存放自身節點在內存空間中的長度，所示節點總長度占用6字節小于254字節，則entry_length用1字節表示即可，記錄為0x6。由圖7（a）、（b）中對比看出，結構體優化從根本上改變了原結構記錄前驅節點長度的特征。

在保證算法正常逆序遍歷，且按上文所示對節點進行存儲結構調整，優化后的算法功能和原算法功能是等效的。對算法的功能及性能的驗證在實驗過程中將做詳細的對比分析。

結構調整后優化算法逆序遍歷的實現步驟：

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

步驟2 解析zl前6個字節，獲取zl信息，得到zlbytes、zllen。

步驟3找到尾節點tail,tail=zl+zlbytes-2，同時將指針p指向zl尾節點的最后一個字節位置。

步驟4判斷鏈表是否已經遍歷完或者鏈表為空，若遍歷完成或者鏈表為空，算法結束，否則執行步驟5。

步驟5解析當前節點的Entry_Length字段，確定指針 p所指節點的實際空間長度len以及用來表示該長度的變量lensize的值（1字節或5字節）。

步驟6解析節點的encoding字段：

首先執行操作 ptr=p-len+1，此時 ptr指向 p指向的當前節點的encoding字段的首地址。調用解析出編碼當前節點所需的內存空間長度encodingsize和當前節點真實內容長度contentlen。

步驟7訪問當前節點的實際數據content字段：

以ptr+=encodingsize為起始位置的長度為contentlen的連續內存空間上存放的便是當前節點的實際數據content。

步驟8指針 p往前移動一個節點長度，然后轉向步驟4。

4 實驗測試與結果分析

為驗證新算法性能，抽取可靠數據樣本，對連鎖更新優化前后Redis服務器對于壓縮列表進行插入操作時的處理速度進行統計與對比分析[21]。

4.1 實驗環境

實驗所需測試環境為服務器1臺，配置如下：Intel?Xeon?CPU E5-2620 v2 6核12線程CPU，32 GB內存，240 GB硬盤，操作系統采用Ubuntu16.04LTS版本，數據庫為Redis3.0.3版本，腳本環境為Ptyhon3.4.6。

4.2 實驗步驟

考慮特定情況下執行時間存在一定的隨機性，為方便實驗結果對比，本實驗采用python隨機生成10組字符串數據樣本，重復實驗50次，取其結果的平均值。

實驗采用的步驟為：首先通過lpush命令插入單個長度為250～253字節長度的數據樣本到Redis數據庫，隨后通過插入長度為255字節的數據，來觸發連鎖更新機制，最后統計優化前后兩個版本的Redis數據庫實例處理每組數據樣本所需的時間消耗，緩存占用，性能變化等數據，用來做實驗對比。

實驗過程中，每插入下一組數據樣本前，對Redis數據庫進行清空操作，刪除上一次數據樣本的所有數據，以確保每組數據插入前的初始環境狀態完全一致。

壓縮列表連鎖更新測試方案設計如圖8所示。

4.3 實驗結果分析

4.3.1 連鎖更新時間消耗對比

針對連鎖更新的時間消耗對比問題，實驗過程中每次從10 000個數據量開始，每次疊加10 000個數據量，最高為100 000個數據量，重復50次后，取其平均值進行對比驗證。

圖8 壓縮列表連鎖更新測試方案

相同數據量下的連鎖更新優化前后的時間消耗對比如圖9所示。

圖9 連鎖更新時間消耗對比

對比以上數據和曲線圖可以看出，優化了壓縮列表連鎖更新問題的Redis數據庫實例在處理相同數據量，相同連鎖更新的情況下，時間消耗更少。

另在實驗過程中，對每次Redis數據庫實例插入數據時所占用內存空間進行采集，多次重復實驗后取其平均值，得到表1數據。

表1 連鎖更新優化前后緩存消耗對比

對比優化前后的Redis實例內存占用情況，在數據量相同的情況下，優化后的Redis數據庫實例，通過對相同數據量情況下的連鎖更新消耗時間以及內存占用情況的對比驗證，在不影響Redis原有功能的前提下，表明優化后的連鎖更新耗時更少，處理相等數據量的緩存消耗穩定。

4.3.2 優化后Redis服務器插入性能

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

圖10 頭插法與尾插法處理時間消耗對比

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

同時，從壓縮列表頭插法（HEAD）與尾插法（TAIL）處理時間消耗分布圖還可以看出，壓縮列表使用頭插法進行數據增加、刪除操作所需處理時間遠大于使用尾插法進行數據增加、刪除操作所需處理時間，這是因為頭插法（HEAD）操作比尾插法（TAIL）操作增加了一個內存移動過程，數據量越大，所需移動內存字節數越多，因此所需時間更多。

對比優化前后兩個Redis服務器實例在處理相同連鎖更新情況的數據，優化前的Redis數據庫實例隨著數據的增加，處理連鎖更新所占用時間也隨之增加，反之優化后的Redis服務器實例所花費的時間增長緩慢，從實驗結果可以看出，優化后的壓縮列表在處理連鎖更新過程上所消耗的時間大大減少，從側面反映出當數據量越來越大，優化后的處理連鎖更新所用的時間復雜度也從O(N2)減少成O(N)，驗證了論文中的方案設計思路。

4.3.3結構優化后連鎖更新時間消耗對比

為了驗證結構體優化后的作用，實驗過程中分別采用了3個Redis數據庫實例進行對比驗證，分別為：

實例1沒有采用任何優化的原始壓縮列表。

實例2采用優化連鎖更新算法后的壓縮列表。

實例3采用優化結構體的壓縮列表。

對這3個Redis實例進行數據插入，通過與4.3.1小節相同的實驗方式對結構體優化后壓縮列表進行的測試。分別采集不同數據量情況下壓縮列表進行連鎖更新所消耗的時間，得到的數據如表2所示。

表2 結構體優化前后連鎖更新時間消耗對比

連鎖更新時間消耗對比曲線圖如圖11所示。

圖11 結構體優化前后連鎖更新時間消耗對比

從上述數據可以看出，采用了結構體優化壓縮列表的Redis實例，和采用了連鎖更新算法優化壓縮列表的Redis實例，在處理相同數據量的情況下，所消耗的時間幾乎一致，相比較優化的原始壓縮列表Redis實例消耗的時間少，同時表明，結構體優化后的壓縮列表與優化了連鎖更新算法的壓縮列表在處理連鎖更新方面時間復雜度幾乎一致。

4.3.4 結構體優化后性能驗證

（1）固定數據插入對比驗證

針對結構體優化前后，數據插入耗時的對比，實驗采用兩個不同的壓縮列表實例，一個優化了結構體，另一個維持原狀態，通過對這兩個壓縮列表分別插入1萬～5萬個節點數據（單節點長度固定為250個字節），采集每次插入所消耗的時間，多次重復后取其平均值，對比優化前后的時間消耗，得到優化前后時間消耗對比曲線圖，如圖12所示。

通過以上數據可以表明，在不造成連鎖更新的情況下，結構體優化前后，插入數據所消耗的時間幾乎等效，不會對壓縮列表的性能造成影響。

圖12 結構體優化前后無連鎖更新時耗時對比

（2）隨機數據插入對比驗證

實驗采用1萬～10萬個單個長度在1～500字節的節點，在結構體優化前后的壓縮列表采用隨機頭插、尾插的方式進行插入操作，記錄壓縮列表消耗的時間，重復多次實驗后，取其平均值后，得出的數據如圖13所示。

圖13 結構體優化前后隨機插入時間消耗對比

上述實驗數據表明一般情況下，結構體優化后對壓縮列表插入的數據量越大時，優化效果越明顯。

通過多次對比實驗驗證了兩種優化方案的性能，實驗測試效果表明，兩種方案在最壞情況下對壓縮列表的性能優化明顯，通常情況下，插入的數據量越大優化效果越明顯。

5 總結

Redis壓縮列表連鎖更新機制，最壞情況下時間復雜度為O(N2)。針對此情況，提出兩種解決方案，第一種是通過設計新的算法，在原連鎖更新機制的基礎上，先進行順序遍歷統計完成連鎖更新所需擴展的內存空間，然后進行一次內存空間重新分配操作，從而將連鎖更新的時間復雜度降為O(N)。第二種給出壓縮列表結構體優化方案，在不影響原有功能的基礎上消除了存儲節點時由于連鎖更導致的時間復雜度偏大問題。由實驗結果分析可知，結構體優化后的壓縮列表讀寫操作性能獲得了明顯提升，實現了性能優化。

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