Redis壓縮列表原理與應用分析

摘要
Redis是一款著名的key-value內存數據庫軟件，同時也是一款卓越的數據結構服務軟件。它支持字符串、列表、哈希表、集合、有序集合五種數據結構類型，同時每種數據結構類型針對不同的應用場景又支持不同的編碼方式。這篇文章主要介紹壓縮列表編碼，在理解壓縮列表編碼原理的基礎上介紹Redis對壓縮列表的應用，最后再對Redis壓縮列表應用進行分析。

Redis壓縮列表原理與應用

壓縮列表是一種數據結構，這種數據結構的功能是將一系列數據與其編碼信息存儲在一塊連續的內存區域，這塊內存物理上是連續的，邏輯上被分為多個組成部分，其目的是在一定可控的時間復雜讀條件下盡可能的減少不必要的內存開銷，從而達到節省內存的效果，這么介紹有點玄乎，我們先一起看看它的實現原理吧，Redis3.2版本中，作者對壓縮列表的實現在ziplist.h和ziplist.c中。

壓縮列表原理

我認為將數據按照一定規則存儲在內存中可以用“編碼”這個詞描述，因此下面會常用“編碼”這個詞。

總體編碼

上面說到壓縮列表是一塊連續的內存區域，這塊內存區域布編碼示意圖大致如下：

Redis壓縮列表內存編碼示意圖

常態的壓縮列表內存編碼如上圖所示，整個內存塊區域內分為五個部分，下面分別介紹著五個部分：

zlbytes：存儲一個無符號整數，固定四個字節長度，用于存儲壓縮列表所占用的字節，當重新分配內存的時候使用，不需要遍歷整個列表來計算內存大小。

zltail：存儲一個無符號整數，固定四個字節長度，代表指向列表尾部的偏移量，偏移量是指壓縮列表的起始位置到指定列表節點的起始位置的距離。

zllen：壓縮列表包含的節點個數，固定兩個字節長度，源碼中指出當節點個數大于2^16-2個數的時候，該值將無效，此時需要遍歷列表來計算列表節點的個數。

entryX：列表節點區域，長度不定，由列表節點緊挨著組成。

zlend：一字節長度固定值為255，用于表示列表結束。

列表元素編碼

上面介紹了壓縮列表的總體內存布局，對于初entryX區域以外的四個區域的長度都是固定的，下面再看看entryX區域的編碼情況。

每個列表節點由三部分組成：

壓縮列表節點編碼示意圖

每個壓縮列表節點區域頭部包含兩部分，一部分叫做previous length，另一部分叫encoding，最后是主體內容，叫做content，下面分別介紹他們：

previous length

用于存儲上一個節點的長度，因此壓縮列表可以從尾部向頭部遍歷，即當前節點位置減去上一個節點的長度即得到上一個節點的起始位置。previous length的長度可能是1個字節或者是5個字節，如果上一個節點的長度小于254，則該節點只需要一個字節就可以表示前一個節點的長度了，如果前一個節點的長度大于等于254，則previous length的第一個字節為254，后面用四個字節表示當前節點前一個節點的長度。這么做很有效地減少了內存的浪費。

encoding

節點的encoding保存的是節點的content的內容類型以及長度，encoding類型一共有兩種，一種字節數組一種是整數，encoding區域長度為1字節、2字節或者5字節長。Redis作者巧妙的利用了前兩個字節來表示content存儲的內容類型和encoding區域的長度，我們先看看字節數組類型的encoding內容：

content為字節數組的encoding內容

再看看整數編碼類型的encoding內容：

content為整數的encoding內容

content

content區域用于保存節點的內容，節點內容類型和長度由encoding決定，上面可以看出目前content的內容類型有整數類型和字節數組類型，且某些條件下content的長度可能為0。

相信到這里，我們都明白了壓縮列表的原理，壓縮列表并不是對數據利用某種算法進行壓縮，而是將數據按照一定規則編碼在一塊連續的內存區域，目的是節省內存。下面我們看看壓縮列表在Redis中的應用領域。

Redis中壓縮列表的應用
Redis中，不同的數據類型廣泛地應用了壓縮列表編碼，整理如下表：

Redis中數據結構類型與壓縮列表的應用

上表總結了壓縮列表編碼在Redis不同的數據類型中的應用，Redis一共支持五種數據結構類型，其中有三種數據結構在一定條件下會應用壓縮列表，至于什么條件后面會分析，值得一提的是Redis當前支持的GEO（地理位置）對壓縮列表也有應用，具體此處不做討論。

Redis壓縮列表應用分析

上面部分介紹了Redis壓縮列表的原理與應用，下面簡單分析一下，主要從通過試圖回答一些問題來分析：Redis為什么使用壓縮列表？使用壓縮列表的好處是什么？使用壓縮列表的好處還有什么？壓縮列表的應用對與我們使用內存有沒有什么啟發？

Redis對于每種數據結構、無論是列表、哈希表還是有序集合，在決定是否應用壓縮列表作為當前數據結構類型的底層編碼的時候都會依賴一個開關和一個閾值，開關用來決定我們是否要啟用壓縮列表編碼，閾值總的來說通常指當前結構存儲的key數量有沒有達到一個數值（條件），或者是value值長度有沒有達到一定的長度（條件）。任何策略都有其應用場景，不同場景應用不同策略。為什么當前結構存儲的數據條目達到一定數值使用壓縮列表就不好？壓縮列表的新增、刪除的操作平均時間復雜度為O(N)，隨著N的增大，時間必然會增加，他不像哈希表可以以O(1)的時間復雜度找到存取位置，然而在一定N內的時間復雜度我們可以容忍。然而壓縮列表利用巧妙的編碼技術除了存儲內容盡可能的減少不必要的內存開銷，將數據存儲于連續的內存區域，這對于Redis本身來說是有意義的，因為Redis是一款內存數據庫軟件，想辦法盡可能減少內存的開銷是Redis設計者一定要考慮的事情。

另外，經過仔細琢磨，我認為使用壓縮列表的好處除了節約內存之外，還有減少內存碎片的作用，我把這種行為叫做"合并存儲"，也就是將很多小的數據塊存儲在一個比較大的內存區域，試想想，如果我們將要存儲的數據都是很小的條目，我們為每一個數據條目都單獨的申請內存，結果是這些條目將有可能分散在內存的每一個角落，最終導致碎片增加，這是一件令人頭疼的事情。

總結

這篇文章在介紹Redis壓縮列表原理與應用的基礎之上對Redis壓縮列表的應用進行分析，分析部分主要摻雜著個人的理解與認知，如果有不同觀點或者補充觀點，歡迎留言討論。