Redis 有序集合對(duì)象

有序集合的編碼可以是 ziplist 或者 skiplist 。

ziplist 編碼的有序集合對(duì)象使用壓縮列表作為底層實(shí)現(xiàn)， 每個(gè)集合元素使用兩個(gè)緊挨在一起的壓縮列表節(jié)點(diǎn)來保存， 第一個(gè)節(jié)點(diǎn)保存元素的成員（member）， 而第二個(gè)元素則保存元素的分值（score）。

壓縮列表內(nèi)的集合元素按分值從小到大進(jìn)行排序， 分值較小的元素被放置在靠近表頭的方向， 而分值較大的元素則被放置在靠近表尾的方向。

舉個(gè)例子， 如果我們執(zhí)行以下 ZADD 命令， 那么服務(wù)器將創(chuàng)建一個(gè)有序集合對(duì)象作為 price 鍵的值：

redis> ZADD price 8.5 apple 5.0 banana 6.0 cherry
(integer) 3

如果 price 鍵的值對(duì)象使用的是 ziplist 編碼， 那么這個(gè)值對(duì)象將會(huì)是圖 8-14 所示的樣子， 而對(duì)象所使用的壓縮列表則會(huì)是 8-15 所示的樣子。

skiplist 編碼的有序集合對(duì)象使用 zset 結(jié)構(gòu)作為底層實(shí)現(xiàn)， 一個(gè) zset 結(jié)構(gòu)同時(shí)包含一個(gè)字典和一個(gè)跳躍表：

typedef struct zset {

    zskiplist *zsl;

    dict *dict;

} zset;

zset 結(jié)構(gòu)中的 zsl 跳躍表按分值從小到大保存了所有集合元素， 每個(gè)跳躍表節(jié)點(diǎn)都保存了一個(gè)集合元素： 跳躍表節(jié)點(diǎn)的 object 屬性保存了元素的成員， 而跳躍表節(jié)點(diǎn)的 score 屬性則保存了元素的分值。 通過這個(gè)跳躍表， 程序可以對(duì)有序集合進(jìn)行范圍型操作， 比如 ZRANK 、ZRANGE 等命令就是基于跳躍表 API 來實(shí)現(xiàn)的。

除此之外， zset 結(jié)構(gòu)中的 dict 字典為有序集合創(chuàng)建了一個(gè)從成員到分值的映射， 字典中的每個(gè)鍵值對(duì)都保存了一個(gè)集合元素： 字典的鍵保存了元素的成員， 而字典的值則保存了元素的分值。 通過這個(gè)字典， 程序可以用  復(fù)雜度查找給定成員的分值， ZSCORE 命令就是根據(jù)這一特性實(shí)現(xiàn)的， 而很多其他有序集合命令都在實(shí)現(xiàn)的內(nèi)部用到了這一特性。

有序集合每個(gè)元素的成員都是一個(gè)字符串對(duì)象， 而每個(gè)元素的分值都是一個(gè) double 類型的浮點(diǎn)數(shù)。 值得一提的是， 雖然 zset 結(jié)構(gòu)同時(shí)使用跳躍表和字典來保存有序集合元素， 但這兩種數(shù)據(jù)結(jié)構(gòu)都會(huì)通過指針來共享相同元素的成員和分值， 所以同時(shí)使用跳躍表和字典來保存集合元素不會(huì)產(chǎn)生任何重復(fù)成員或者分值， 也不會(huì)因此而浪費(fèi)額外的內(nèi)存。

為什么有序集合需要同時(shí)使用跳躍表和字典來實(shí)現(xiàn)？

在理論上來說， 有序集合可以單獨(dú)使用字典或者跳躍表的其中一種數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)， 但無論單獨(dú)使用字典還是跳躍表， 在性能上對(duì)比起同時(shí)使用字典和跳躍表都會(huì)有所降低。

舉個(gè)例子， 如果我們只使用字典來實(shí)現(xiàn)有序集合， 那么雖然以  內(nèi)存空間 （因?yàn)橐獎(jiǎng)?chuàng)建一個(gè)數(shù)組來保存排序后的元素）。

另一方面， 如果我們只使用跳躍表來實(shí)現(xiàn)有序集合， 那么跳躍表執(zhí)行范圍型操作的所有優(yōu)點(diǎn)都會(huì)被保留， 但因?yàn)闆]有了字典， 所以根據(jù)成員查找分值這一操作的復(fù)雜度將從  。

因?yàn)橐陨显颍?為了讓有序集合的查找和范圍型操作都盡可能快地執(zhí)行， Redis 選擇了同時(shí)使用字典和跳躍表兩種數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)有序集合。

舉個(gè)例子， 如果前面 price 鍵創(chuàng)建的不是 ziplist 編碼的有序集合對(duì)象， 而是 skiplist 編碼的有序集合對(duì)象， 那么這個(gè)有序集合對(duì)象將會(huì)是圖 8-16 所示的樣子， 而對(duì)象所使用的 zset 結(jié)構(gòu)將會(huì)是圖 8-17 所示的樣子。

注意

為了展示方便， 圖 8-17 在字典和跳躍表中重復(fù)展示了各個(gè)元素的成員和分值， 但在實(shí)際中， 字典和跳躍表會(huì)共享元素的成員和分值， 所以并不會(huì)造成任何數(shù)據(jù)重復(fù)， 也不會(huì)因此而浪費(fèi)任何內(nèi)存。

編碼的轉(zhuǎn)換

當(dāng)有序集合對(duì)象可以同時(shí)滿足以下兩個(gè)條件時(shí)， 對(duì)象使用 ziplist 編碼：

1. 有序集合保存的元素?cái)?shù)量小于 128 個(gè)；
2. 有序集合保存的所有元素成員的長(zhǎng)度都小于 64 字節(jié)；

不能滿足以上兩個(gè)條件的有序集合對(duì)象將使用 skiplist 編碼。

注意

以上兩個(gè)條件的上限值是可以修改的， 具體請(qǐng)看配置文件中關(guān)于 zset-max-ziplist-entries 選項(xiàng)和 zset-max-ziplist-value 選項(xiàng)的說明。

對(duì)于使用 ziplist 編碼的有序集合對(duì)象來說， 當(dāng)使用 ziplist 編碼所需的兩個(gè)條件中的任意一個(gè)不能被滿足時(shí)， 程序就會(huì)執(zhí)行編碼轉(zhuǎn)換操作， 將原本儲(chǔ)存在壓縮列表里面的所有集合元素轉(zhuǎn)移到 zset 結(jié)構(gòu)里面， 并將對(duì)象的編碼從 ziplist 改為 skiplist 。

以下代碼展示了有序集合對(duì)象因?yàn)榘诉^多元素而引發(fā)編碼轉(zhuǎn)換的情況：

# 對(duì)象包含了 128 個(gè)元素
redis> EVAL "for i=1, 128 do redis.call('ZADD', KEYS[1], i, i) end" 1 numbers
(nil)

redis> ZCARD numbers
(integer) 128

redis> OBJECT ENCODING numbers
"ziplist"

# 再添加一個(gè)新元素
redis> ZADD numbers 3.14 pi
(integer) 1

# 對(duì)象包含的元素?cái)?shù)量變?yōu)?129 個(gè)
redis> ZCARD numbers
(integer) 129

# 編碼已改變
redis> OBJECT ENCODING numbers
"skiplist"

以下代碼則展示了有序集合對(duì)象因?yàn)樵氐某蓡T過長(zhǎng)而引發(fā)編碼轉(zhuǎn)換的情況：

# 向有序集合添加一個(gè)成員只有三字節(jié)長(zhǎng)的元素
redis> ZADD blah 1.0 www
(integer) 1

redis> OBJECT ENCODING blah
"ziplist"

# 向有序集合添加一個(gè)成員為 66 字節(jié)長(zhǎng)的元素
redis> ZADD blah 2.0 oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
(integer) 1

# 編碼已改變
redis> OBJECT ENCODING blah
"skiplist"

有序集合命令的實(shí)現(xiàn)

因?yàn)橛行蚣湘I的值為有序集合對(duì)象， 所以用于有序集合鍵的所有命令都是針對(duì)有序集合對(duì)象來構(gòu)建的， 表 8-11 列出了其中一部分有序集合鍵命令， 以及這些命令在不同編碼的有序集合對(duì)象下的實(shí)現(xiàn)方法。

表 8-11 有序集合命令的實(shí)現(xiàn)方法