[TOC] ## **什么是壓縮列表** 壓縮列表（ziplist）是**列表鍵**和**哈希鍵**的底層實現之一。當一個列表鍵只包含少量列表項，并且每個列表項要么就是小整數值，要么就是長度比較短的字符串，那么Redis就會使用**壓縮列表來做列表鍵的底層**實現。 示例： ``` redis>?RPUSH?lst?1?3?5?10086?"hello"?"world" (integer)6 redis>?OBJECT?ENCODING?lst "ziplist" ``` 列表鍵里面包含的都是1、3、5、10086這樣的小整數值，以及"hello"、"world"這樣的短字符串 當一個哈希鍵只包含少量鍵值對，比且每個鍵值對的鍵和值要么就是**小整數值**，要么就是**長度比較短的字符串**，那么Redis就會使用壓縮列表來做哈希鍵的底層實現 ``` redis>?HMSET?profile?"name"?"Jack"?"age"?28?"job"?"Programmer" OK redis>?OBJECT?ENCODING?profile "ziplist" ``` **哈希鍵里面包含的所有鍵和值都是小整數值或者短字符串** ` ` ## **壓縮列表的原理** ### **壓縮列表的構成** 壓縮列表是Redis為了節約內存而開發的，是由一系列特殊編碼的連續內存塊組成的順序型（sequential）數據結構。一個壓縮列表可以包含任意多個節點（entry），每個節點可以保存一個字節數組或者一個整數值。 ` ` 記錄了各個組成部分的類型、長度以及用途  ` ` 壓縮列表示例：  * 列表zlbytes屬性的值為0xd2（十進制210），表示壓縮列表的總長為210字節。 * 列表zltail屬性的值為0xb3（十進制179），這表示如果我們有一個指向壓縮列表起始地址的指針p，那么只要用指針p加上偏移量179，就可以計算出表尾節點entry5的地址。 * 列表zllen屬性的值為0x5（十進制5），表示壓縮列表包含五個節點。 ### **壓縮列表節點的構成** 每個**壓縮列表節點**可以保存**一個字節數組**或者**一個整數值** 字節數組可以是以下三種長度的其中一種： * 長度小于等于63（26–1）字節的字節數組； * 長度小于等于16383（214–1）字節的字節數組； * 長度小于等于4294967295（232–1）字節的字節數組； ` ` 整數值則可以是以下六種長度的其中一種： * 4位長，介于0至12之間的無符號整數； * 1字節長的有符號整數； * 3字節長的有符號整數； * int16\_t類型整數； * int32\_t類型整數； * int64\_t類型整數。 ` ` 每個壓縮列表節點都由**previous\_entry\_length、encoding、content**三個部分組成:  ` ` ### **previous\_entry\_length** 節點的previous\_entry\_length屬性以字節為單位，記錄了壓縮列表中前一個節點的長度. ` ` **previous\_entry\_length屬性的長度**可以是**1字節**或者**5字節**： * 如果**前一節點的長度小于254字節**，那么previous\_entry\_length屬性的長度為1字節：前一節點的長度就保存在這一個字節里面。 ` ` 示例：包含一字節長previous\_entry\_length屬性的壓縮列表節點，屬性的值為0x05，表示前一節點的長度為5字節  ` ` * 如果**前一節點的長度大于等于254字節**，那么previous\_entry\_length屬性的長度為5字節：其中屬性的第一字節會被設置為0xFE（十進制值254），而之后的四個字節則用于保存前一節點的長度。 ` ` 示例：包含五字節長previous\_entry\_length屬性的壓縮節點，屬性的值為0xFE00002766，其中值的最高位字節0xFE表示這是一個五字節長的previous\_entry\_length屬性，而之后的四字節0x00002766（十進制值10086）才是前一節點的實際長度。  ` ` **計算前一個指針的起始地址** 節點的previous\_entry\_length屬性記錄了前一個節點的長度，程序可以通過指針運算，根據當前節點的起始地址來計算出前一個節點的起始地址。 ` ` 示例： 如果我們有一個指向當前節點起始地址的指針c，那么我們只要用指針c減去當前節點previous\_entry\_length屬性的值，就可以得出一個指向前一個節點起始地址的指針p：  >**壓縮列表的從表尾向表頭遍歷操作**就是使用這一原理實現的，只要我們擁有了一個指向某個節點起始地址的指針，那么通過這個指針以及這個節點的previous\_entry\_length屬性，程序就可以一直向前一個節點回溯，最終到達壓縮列表的表頭節點。  ` ` ### **encoding** 節點的encoding屬性記錄了節點的content屬性所保存數據的類型以及長度： * 一字節、兩字節或者五字節長，值的最高位為00、01或者10的是字節數組編碼：這種編碼表示節點的content屬性保存著字節數組，數組的長度由編碼除去最高兩位之后的其他位記錄； * 一字節長，值的最高位以11開頭的是整數編碼：這種編碼表示節點的content屬性保存著整數值，整數值的類型和長度由編碼除去最高兩位之后的其他位記錄； ` ` 所有可用的字節數組編碼+所有可用的整數編碼:  >表格中的下劃線“\_”表示留空，而b、x等變量則代表實際的二進制數據，為了方便閱讀，多個字節之間用空格隔開。 ` ` ### **content** 節點的content屬性負責**保存節點的值**，節點值可以是**一個字節數組或者整數**，值的類型和長度由節點的encoding屬性決定。 示例1：  * 編碼的最高兩位00表示節點保存的是一個字節數組； * 編碼的后六位001011記錄了字節數組的長度11； * content屬性保存著節點的值"hello world" ` ` 示例2：  * 編碼11000000表示節點保存的是一個int16\_t類型的整數值； * content屬性保存著節點的值10086。 ` ` ### **連鎖更新** 每個節點的previous\_entry\_length屬性都記錄了前一個節點的長度： * 如果前一節點的長度小于254字節，那么previous\_entry\_length屬性需要用1字節長的空間來保存這個長度值。 * 如果前一節點的長度大于等于254字節，那么previous\_entry\_length屬性需要用5字節長的空間來保存這個長度值。 ` ` #### **插入節點造成的連鎖更新** 考慮這樣一種情況：在一個壓縮列表中，有多個連續的、長度介于250字節到253字節之間的節點e1至eN  因為e1至eN的所有節點的長度都小于254字節，所以記錄這些節點的長度只需要1字節長的previous\_entry\_length屬性，換句話說，**e1至eN的所有節點的previous\_entry\_length屬性都是1字節長**的。 這時，如果我們將一個長度大于等于254字節的新節點new設置為壓縮列表的表頭節點，那么new將成為e1的前置節點:  ` ` * 因為**e1的previous\_entry\_length屬性僅長1字節**，它沒辦法保存新節點new的長度，所以程序將對壓縮列表執行空間重分配操作，并**將e1節點的previous\_entry\_length屬性從原來的1字節長擴展為5字節長**。 * 現在，麻煩的事情來了，**e1原本的長度介于250字節至253字節之間，在為previous\_entry\_length屬性新增四個字節的空間**之后，**e1的長度就變成了介于254字節至257字節之間**，而這種長度**使用1字節長的previous\_entry\_length屬性是沒辦法保存的**。 * 因此，為了讓e2的previous\_entry\_length屬性可以記錄下e1的長度，程序需要再次對壓縮列表**執行空間重分配操作**，并**將e2節點的previous\_entry\_length屬性從原來的1字節長擴展為5字節長**。 * 正如擴展e1引發了對e2的擴展一樣，擴展e2也會引發對e3的擴展，而擴展e3又會引發對e4的擴展……為了讓每個節點的previous\_entry\_length屬性都符合壓縮列表對節點的要求，程序需要不斷地對壓縮列表執行空間重分配操作，直到eN為止。 >Redis將這種在特殊情況下產生的連續多次空間擴展操作稱之為“連鎖更新” 除了添加新節點可能會引發連鎖更新之外，刪除節點也可能會引發連鎖更新。 ` `  ` ` #### **刪除節點造成的連鎖更新** 如果e1至eN都是大小介于250字節至253字節的節點，big節點的長度大于等于254字節（需要5字節的previous\_entry\_length來保存），而small節點的長度小于254字節（只需要1字節的previous\_entry\_length來保存），那么當我們將small節點從壓縮列表中刪除之后，為了讓e1的previous\_entry\_length屬性可以記錄big節點的長度，程序將擴展e1的空間，并由此引發之后的連鎖更新。 ` ` #### **連鎖更新時間復雜度** 因為連鎖更新在最壞情況下需要對壓縮列表執行N次空間重分配操作，而每次空間重分配的最壞**復雜度為O（N）**，所以連鎖更新的**最壞復雜度為O（N2）**。 盡管連鎖更新的復雜度較高，但它真正**造成性能問題的幾率是很低**的： * 壓縮列表里要恰好有多個連續的、長度介于250字節至253字節之間的節點，連鎖更新才有可能被引發，在實際中，這種情況并不多見； * 即使出現連鎖更新，但只要被更新的節點數量不多，就不會對性能造成任何影響：比如說，對三五個節點進行連鎖更新是絕對不會影響性能的； >ziplistPush等命令的**平均復雜度僅為O（N）** ` ` ## **壓縮列表重點** * 壓縮列表是一種為節約內存而開發的順序型數據結構。 * 壓縮列表被用作列表鍵和哈希鍵的底層實現之一。 * 壓縮列表可以包含多個節點，每個節點可以保存一個字節數組或者整數值。 * 添加新節點到壓縮列表，或者從壓縮列表中刪除節點，可能會引發連鎖更新操作，但這種操作出現的幾率并不高。