1. 首頁 > 生活百科 > >

二 京東云開發者| Redis數據結構-List、Hash、Set及Sorted Set的結構實現

生活百科

1 引言之前介紹了Redis的數據存儲及String類型的實現，接下來再來看下List、Hash、Set及Sorted Set的數據結構的實現 。
2 ListList類型通常被用作異步消息隊列、文章列表查詢等；存儲有序可重復數據或做為簡單的消息推送機制時，可以使用Redis的List類型 。對于這些數據的存儲通常會使用鏈表或者數組作為存儲結構 。

  • 使用數組存儲，隨機訪問節點通過索引定位時間復雜度為O(1) 。但在初始化時需要分配連續的內存空間；在增加數據時 ， 如果超過當前分配空間，需要將數據整體搬遷移到新數組中 。
  • 使用鏈表存儲 ， 在進行前序遍歷或后續遍歷，當前節點中要存儲前指針和后指針，這兩個指針在分別需要8byte共16byte空間存儲，存在大量節點會因指針占用過多空間 。鏈表雖然不需要連續空間存儲可以提高內存利用率，但頻繁的增加和刪除操作會使內存碎片化，影響數據讀寫速率 。
如果我們能夠將鏈表和數組的特點結合起來就能夠很好處理List類型的數據存儲 。
2.1 ZipList3.2之前Redis使用的是ZipList，具體結構如下：
二 京東云開發者| Redis數據結構-List、Hash、Set及Sorted Set的結構實現

文章插圖
  • zlbytes: 4byte 記錄整個壓縮列表占用的內存字節數：在對壓縮列表進行內存重分配，或者計算 zlend 的位置時使用 。
  • zltail：4byte 記錄壓縮列表表尾節點距離壓縮列表的起始地址有多少字節： 通過這個偏移量，程序無須遍歷整個壓縮列表就可以確定表尾節點的地址 。
  • zllen：2byte 記錄了壓縮列表包含的節點數量： 當這個屬性的值小于 UINT16_MAX（65535）時，這個屬性的值就是壓縮列表包含節點的數量； 當這個值等于UINT16_MAX 時 ， 節點的真實數量需要遍歷整個壓縮列表才能計算得出 。
  • entry X：壓縮列表包含的各個節點，節點的長度由節點保存的內容決定 。包含屬性如下：
  • prerawlen：記錄前一個節點所占內存的字節數，方便查找上一個元素地址
  • len：data根據len的首個byte選用不同的數據類型來存儲data
  • data：本元素的信息
  • zlend: 尾節點 恒等于255
ziplist是一個連續的內存塊，由表頭、若干個entry節點和壓縮列表尾部標識符zlend組成 ， 通過一系列編碼規則，提高內存的利用率，使用于存儲整數和短字符串 。每次增加和刪除數據時，所有數據都在同一個ziplist中都會進行搬移操作 。如果將一個組數據按閾值進行拆分出多個數據，就能保證每次只操作某一個ziplist 。3.2之后使用的quicklist與ziplist 。
2.2 QuickListquicklist就是維護了一種宏觀上的雙端鏈表(類似于B樹) ， 鏈表的節點為對ziplist包裝的quicklistNode，每個quciklistNode都會通過前后指針相互指向 ， quicklist包含頭、尾quicklistNode的指針 。
typedef struct quicklist {quicklistNode *head;quicklistNode *tail;unsigned long count;/* total count of all entries in all ziplists */unsigned long len;/* number of quicklistNodes */int fill : QL_FILL_BITS;/* fill factor for individual nodes */unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */...} quicklist;
  • *head：表頭節點
  • *tail：表尾節點
  • count：節點包含entries數量
  • len：quicklistNode節點計數器
  • fill：保存ziplist的大?。?配置文件設定
  • compress：保存壓縮程度值，配置文件設定
quicklistNode：
typedef struct quicklistNode {struct quicklistNode *prev;struct quicklistNode *next;unsigned char *zl;unsigned int sz;/* ziplist size in bytes */unsigned int count : 16;/* count of items in ziplist */。。。} quicklistNode;
  • *prev：前置節點
  • *next：后置節點
  • *zl：不進行壓縮時指向一個ziplist結構 ， 壓縮時指向quicklistLZF結構(具體內容請參考下方鏈接)
  • sz：ziplist個數
  • count：ziplist中包含的節點數
在redis.conf通過設置每個ziplist的最大容量，quicklist的數據壓縮范圍,提升數據存取效率,單個ziplist節點最大能存儲量 ， 超過則進行分裂 ， 將數據存儲在新的ziplist節點中
-5: max size: 64 Kb <— not recommended for normal workloads
-4: max size: 32 Kb <— not recommended
-3: max size: 16 Kb <— probably not recommended
-2: max size: 8 Kb <— good
-1: max size: 4 Kb <— good
List-max-ziplist-size -20代表所有節點，都不進行壓縮，1.代表從頭節點往后一個，尾結點往前一個不用壓縮 ， 其它值以此類推List-compress-depth 1
Redis 的鏈表實現的特性可以總結如下：

推薦閱讀