有序集 · Redis 設計與實現（第一版）

# 有序集 [TOC=2,3] `REDIS_ZSET` （有序集）是 [ZADD](http://redis.readthedocs.org/en/latest/sorted_set/zadd.html#zadd "(in Redis 命令參考 v2.8)") 、 [ZCOUNT](http://redis.readthedocs.org/en/latest/sorted_set/zcount.html#zcount "(in Redis 命令參考 v2.8)") 等命令的操作對象，它使用 `REDIS_ENCODING_ZIPLIST` 和 `REDIS_ENCODING_SKIPLIST` 兩種方式編碼： ![digraph redis_zset { node [shape=plaintext, style = filled]; edge [style = bold]; // type REDIS_ZSET [label="有序集合\nREDIS_ZSET", fillcolor = "#95BBE3"]; // encoding REDIS_ENCODING_ZIPLIST [label="ziplist\nREDIS_ENCODING_ZIPLIST", fillcolor = "#FADCAD"]; REDIS_ENCODING_SKIPLIST [label="跳躍表\nREDIS_ENCODING_SKIPLIST", fillcolor = "#FADCAD"]; // edge REDIS_ZSET -> REDIS_ENCODING_ZIPLIST; REDIS_ZSET -> REDIS_ENCODING_SKIPLIST; // datastruct 1 ziplist [label="ziplist"]; REDIS_ENCODING_ZIPLIST -> ziplist; // datastruct 2 zset [label="redis.h/zset"]; dict [label="dict.h/dict"]; zskiplist [label="redis.h/zskiplist"]; REDIS_ENCODING_SKIPLIST -> zset; zset -> dict; zset -> zskiplist;}](https://box.kancloud.cn/2015-09-13_55f4effcf0888.svg) ### 編碼的選擇在通過 [ZADD](http://redis.readthedocs.org/en/latest/sorted_set/zadd.html#zadd "(in Redis 命令參考 v2.8)") 命令添加第一個元素到空 `key` 時，程序通過檢查輸入的第一個元素來決定該創建什么編碼的有序集。如果第一個元素符合以下條件的話，就創建一個 `REDIS_ENCODING_ZIPLIST` 編碼的有序集： - 服務器屬性 `server.zset_max_ziplist_entries` 的值大于 `0` （默認為 `128` ）。 - 元素的 `member` 長度小于服務器屬性 `server.zset_max_ziplist_value` 的值（默認為 `64` ）。否則，程序就創建一個 `REDIS_ENCODING_SKIPLIST` 編碼的有序集。 ### 編碼的轉換對于一個 `REDIS_ENCODING_ZIPLIST` 編碼的有序集，只要滿足以下任一條件，就將它轉換為 `REDIS_ENCODING_SKIPLIST` 編碼： - `ziplist` 所保存的元素數量超過服務器屬性 `server.zset_max_ziplist_entries` 的值（默認值為 `128` ） - 新添加元素的 `member` 的長度大于服務器屬性 `server.zset_max_ziplist_value` 的值（默認值為 `64` ） ### ZIPLIST 編碼的有序集當使用 `REDIS_ENCODING_ZIPLIST` 編碼時，有序集將元素保存到 `ziplist` 數據結構里面。其中，每個有序集元素以兩個相鄰的 `ziplist` 節點表示，第一個節點保存元素的 `member` 域，第二個元素保存元素的 `score` 域。多個元素之間按 `score` 值從小到大排序，如果兩個元素的 `score` 相同，那么按字典序對 `member` 進行對比，決定那個元素排在前面，那個元素排在后面。 ~~~ |<-- element 1 -->|<-- element 2 -->|<-- ....... -->| +---------+---------+--------+---------+--------+---------+---------+---------+ | ZIPLIST | | | | | | | ZIPLIST | | ENTRY | member1 | score1 | member2 | score2 | ... | ... | ENTRY | | HEAD | | | | | | | END | +---------+---------+--------+---------+--------+---------+---------+---------+ score1 <= score2 <= ... ~~~ 雖然元素是按 `score` 域有序排序的，但對 `ziplist` 的節點指針只能線性地移動，所以在 `REDIS_ENCODING_ZIPLIST` 編碼的有序集中，查找某個給定元素的復雜度為 \(O(N)\) 。每次執行添加/刪除/更新操作都需要執行一次查找元素的操作，因此這些函數的復雜度都不低于 \(O(N)\) ，至于這些操作的實際復雜度，取決于它們底層所執行的 `ziplist` 操作。 ### SKIPLIST 編碼的有序集當使用 `REDIS_ENCODING_SKIPLIST` 編碼時，有序集元素由 `redis.h/zset` 結構來保存： ~~~ /* * 有序集 */ typedef struct zset { // 字典 dict *dict; // 跳躍表 zskiplist *zsl; } zset; ~~~ `zset` 同時使用字典和跳躍表兩個數據結構來保存有序集元素。其中，元素的成員由一個 `redisObject` 結構表示，而元素的 `score` 則是一個 `double` 類型的浮點數，字典和跳躍表兩個結構通過將指針共同指向這兩個值來節約空間（不用每個元素都復制兩份）。下圖展示了一個 `REDIS_ENCODING_SKIPLIST` 編碼的有序集： ![digraph zset { rankdir = LR; node [shape = record, style = filled]; edge [style = bold]; label = "在實際中，字典和跳躍表通過指針來共享元素的 member 和 score\n圖中對每個元素都重復顯示了一遍，只是為了展示的方便"; zset [label = "<head>zset |<dict>dict |<zskiplist> zskiplist"]; // skiplist skiplist [label ="<head>zskipNode |<3> |<2> |<1> |<score>score\n NULL |<robj>robj\n NULL", fillcolor = "#FADCAD"]; six [label = "<head>zskipNode |<3> |<2> |<1> |<score>score\n 6 |<robj>robj\n x", fillcolor = "#FADCAD"]; ten [label = "<head>zskipNode | <1> |<score>score\n 10 |<robj>robj\n y", fillcolor = "#FADCAD"]; fiften [label = "<head>zskipNode |<3> |<2> |<1> |<score>score\n 15 |<robj>robj\n z", fillcolor = "#FADCAD"]; zset:dict -> dict:head; zset:zskiplist -> skiplist:head; skiplist:3 -> six:3; skiplist:2 -> six:2; skiplist:1 -> six:1; six:1 -> ten:1; six:2 -> fiften:2; six:3 -> fiften:3; ten:1 -> fiften:1; // dict dict [label = "<head>dictht | ... |<table> table | ...", fillcolor = "#A8E270"]; bucket [label = "<head>dictEntry**\n(bucket) |<0> 0 |<1> 1 |<2> 2", fillcolor = "#95BBE3"]; entry_x [label = "<head>dictEntry |{<key>key\n x |<value>value\n 6}", fillcolor = "#F2F2F2"]; entry_y [label = "<head>dictEntry |{<key>key\n y |<value>value\n 10}", fillcolor = "#F2F2F2"]; entry_z [label = "<head>dictEntry |{<key>key\n z |<value>value\n 15}", fillcolor = "#F2F2F2"]; dict:table -> bucket:head; bucket:0 -> entry_x:head; bucket:1 -> entry_y:head; bucket:2 -> entry_z:head;}](https://box.kancloud.cn/2015-09-13_55f4effd05d06.svg) 通過使用字典結構，并將 `member` 作為鍵，`score` 作為值，有序集可以在 \(O(1)\) 復雜度內： - 檢查給定 `member` 是否存在于有序集（被很多底層函數使用）； - 取出 `member` 對應的 `score` 值（實現 [ZSCORE](http://redis.readthedocs.org/en/latest/sorted_set/zscore.html#zscore "(in Redis 命令參考 v2.8)") 命令）。另一方面，通過使用跳躍表，可以讓有序集支持以下兩種操作： - 在 \(O(\log N)\) 期望時間、 \(O(N)\) 最壞時間內根據 `score` 對 `member` 進行定位（被很多底層函數使用）； - 范圍性查找和處理操作，這是（高效地）實現 [ZRANGE](http://redis.readthedocs.org/en/latest/sorted_set/zrange.html#zrange "(in Redis 命令參考 v2.8)") 、 [ZRANK](http://redis.readthedocs.org/en/latest/sorted_set/zrank.html#zrank "(in Redis 命令參考 v2.8)") 和 [ZINTERSTORE](http://redis.readthedocs.org/en/latest/sorted_set/zinterstore.html#zinterstore "(in Redis 命令參考 v2.8)") 等命令的關鍵。通過同時使用字典和跳躍表，有序集可以高效地實現按成員查找和按順序查找兩種操作。