Redis底層探秘（四）：整數集合及壓縮清單

At the Bercy Arena in Paris, a "ballet" in the air is being staged. No, it's not a circus show, it's the men's parallel bars final at Paris 2024. China's Zou Jingyuan and Zhang Boheng are like two nimble monkeys, somersaulting and jumping on the parallel bars, leaving the audience stunned.

Paris 2024 Gymnastics: Zou Jingyuan played perfectly to successfully defend the men's parallel bars title

The reign of the "King of the Parallel Bars".

Zou Jingyuan, known as the "King of Parallel Bars", once again proved that his title is not for nothing. He behaved like a tango on parallel bars, with grace and strength, making one wonder if he had hidden springs on the parallel bars.

Zhang Boheng's wonderful performance

Although Zhang Boheng failed to make it to the podium, his performance was also wonderful. His movements on the parallel bars are as smooth as a swimming fish, but unfortunately the difficulty score is slightly lower, otherwise he may be able to give Zou Jingyuan a "brother competition".

Thrilling finals

In the finals, players from all over the world sang and I appeared, which was as exciting as a Hollywood blockbuster. Ukraine's Kovton set a high tone for the match as soon as he came up, as if to say: "Come on, see who can surpass me!" "

Although Shinnosuke Oka of Japan has won two gold medals at this Olympics, he does not seem to have played the strength of the "all-around champion" in parallel bars. It seems that even if it is "all-powerful", there are times when it is not so "capable"!

Zou Jingyuan's perfect performance

When Zou Jingyuan appeared on the stage, the entire gymnasium seemed to be quiet. His movements were perfect, and he landed almost motionless, as if he had been nailed to the ground. Although the difficulty score is not the highest, the completion score is as high as 9.3 points, which is like dancing a perfect ballet on the parallel bars.

In the end, Zou Jingyuan successfully defended his title with a high score of 16.2 points, becoming the first Chinese player to defend the Olympic title of men's parallel bars. It seems that the title of "King of Parallel Bars" will continue to be worn for a few more years!

Overall, the competition not only showcased the extraordinary skills of the gymnasts, but also taught us a vivid life lesson. Just like Zou Jingyuan's performance on the parallel bars, life also requires us to maintain a balance between difficulties and challenges, and to show grace and strength. And, just as gymnastics requires a balance of difficulty and completion, our lives also need to focus on the solid completion of each step while pursuing lofty goals.

It seems that if we want to achieve good results on the "parallel bars" of life, we still have a lot to learn and work!

Redis底層探秘（四）：整數集合及壓縮清單

整數集合

整數集合（intset）是集合鍵的底層實作之一，當一個集合隻包含整數值元素，并且這個集合的元素數量不多時，Redis就會使用鄭書記和作為集合鍵的底層實作。

整數集合的實作

整數集合是redis用于儲存整數值的集合抽象資料結構，它可以可以儲存類型位int16_t、int32_t、int64_t的整數值，并且保證集合中不會出現重複元素。

intset.h/intset結構表示一個整數集合

typedef struct intset {
    uint32_t encoding;//編碼方式
    uint32_t length;//集合包含的元素數量
    int8_t contents[];//儲存元素的數組
} intset;

contents數組是整數集合的底層實作：整數集合的每個元素都是contents數組的一個數組項，各個項在數組中按值的大小從小到大有序地排列，并且數組中不包含任何重複項。

length屬性記錄了整數集合包含的元素數量，也即是contents數組的長度。

雖然intset結構将contents屬性聲明為int8 t類型的數組，但實際上contents數組真正類型取決于encoding屬性的值：

上圖中，contents數組儲存的四個整數值中，隻有-2675256175807981027是真正需要用int64_t類型來儲存的，而其他的1、3、5三個值都可以用int16_t類型來儲存，不過根據整數集合的更新規則，當想一個底層為int16_t數組的整數集合添加一個int64_t類型的整數值時，整數集合已有的所有元素都會被轉換成int64_t類型。

更新

每當我們要講一個新元素添加到整數集合裡面，并且新元素的類型比整數集合現有元素類型長時，整數集合都需要先進行更新（upgrade），然後才能将新元素添加到整數集合裡面。

更新整數集合并添加新元素共分為三步進行：

1 根據新元素的類型，擴張整數集合底層數組的空間大小，并為新元素配置設定空間。

2 将底層數組現有的所有元素都轉換成與新元素相同的類型，并将類型轉換後的元素繼續放置到正确的位上，而且在放置元素的過程中，需要繼續維持底層數組的有序性質不變。

3 将新元素添加到底層數組裡面

因為每次想整數集合添加新元素都可能引起更新，而每次更新都需要對底層數組中已有的所有元素進行類型轉換，是以想整數集合添加新元素的時間複雜度為O(N)。

因為引發更新的新元素的長度總是比整數集合現有的所有元素長度都大，是以這個新元素的值要麼大于所有現有元素，要麼小于所有現有元素。

更新的好處

整數集合的更新政策有兩個好處，一個是提升整數集合的靈活性，另一個是盡可能地節約記憶體。

提升靈活性

因為C語言是靜态類型語言，為了避免類型錯誤，我們通常不會講兩種不同類型的值放在同一個資料結構裡面。

但是，因為整數集合可以通過自動更新底層數組來适應新元素，是以我們可以随意地将int16_t、int32_t、int64_t類型的整數添加到集合中，而不必擔心出現類型錯誤。

降級

整數集合不支援降級操作，一旦對數組進行了更新，編碼就會一直保持更新後的狀态。

整數集合API

壓縮清單

壓縮清單（ziplist）是清單鍵和哈希鍵的底層實作之一。當一個清單鍵隻包含少量清單項，并且每個清單項要麼是小整數值，要麼是長度比較短的字元串，那麼redis就會使用壓縮清單來作為清單鍵的底層實作。

另外，當一個哈希鍵隻包含少量鍵值對，并且每個鍵值對的鍵和值要麼是小整數值，要麼是長度比較短的字元串，那麼redis就會使用壓縮清單來做哈希鍵的底層實作。

舉個栗子，執行以下指令

127.0.0.1:6379> hmset profile “name” “jack“ “age” 28 
ok
127.0.0.1:6379> object encoding profile
"ziplist"

壓縮清單的構成

壓縮清單是redis為了節約記憶體而開發的，是由一系列特殊編碼的連續記憶體塊組成的順序型資料結構。一個壓縮表可以包含任意多個節點（entry），每個節點可以儲存一個位元組數組或者一個整數值。

下圖展示了壓縮清單的各個組成部分：

以下為各個組成部分的作用

下圖展示了一個壓縮清單示例：

1 清單zlbytes屬性值為0x50（十進制80），表示壓縮清單總長80位元組。

2 libzltail屬性的值為0x3c（十進制60），這表示如果我們有一個指向壓縮清單起始位址的指針p，那麼隻要用指針p加上偏移量60，就可以計算出表尾節點entry3的位址。

3 清單zllen屬性的值為0x3（十進制3），表示壓縮清單包含三個節點。

壓縮清單節點的構成

每個壓縮清單節點可以儲存一個位元組數組或者一個整數值，其中，位元組數組可以是一下三種長度的其中一種：

1 長度小于等于63（2^6-1）位元組的位元組數組

2 長度小于等于16383（2^14-1）位元組的位元組數組

3 長度小于等于4294967295（2^32-1）位元組的位元組數組

而整數值則可以是以下六種長度的其中一種

1 4位長，介于0至12之間的無符号整數

2 1季節長的有符号整數

3 3位元組長的有符号整數

4 int16_t類型整數

5 int32_t類型整數

6 int64_t類型整數

每個壓縮清單節點都由previous_entry_length、encoding、content三個部分組成，如下圖

我們分别介紹這三部分

previous_entry_length

節點的previous_entry_length屬性以位元組為機關，記錄了壓縮清單中前一個節點的長度。previous_entry_length屬性的長度可以使1位元組或者5位元組：

1 如果前一節點的長度小于254位元組，那麼previous_entry_length屬性的長度為1位元組：前一節點的長度就儲存在這一位元組裡面。

2 如果前一節點的長度大于等于254位元組，那麼previous_entry_length屬性的長度為5位元組：其中屬性的第一個位元組會被設定為0xFE（十進制值254），而之後的四個字接則用于儲存前一節點的長度。

這兩種情況如下圖

因為節點的previous_entry_length屬性記錄了前一個節點的長度，是以程式可以通過指針運算，根據目前節點的起始位址來計算出前一個節點的起始位址。

壓縮清單的從表尾向表頭周遊操作就是使用這一原理實作的，隻要我們擁有了一個指向某個節點起始位址的指針，程式就可以一直向前一個節點回溯，最終到達壓縮清單的表頭節點。

encoding

節點的encoding屬性記錄了節點的content屬性所儲存資料類型以及長度：

1 一位元組、兩位元組或者五位元組長，值的最高位為00、01或者10的是位元組數組編碼：這種編碼表示節點的content屬性儲存着位元組數組，數組的長度由編碼除去最高兩位之後的其他位記錄。

2 一位元組長，值的最高位以11開頭的是整數編碼：這種編碼表示節點的content屬性儲存着整數值，整數值的類型和長度由編碼出去最高兩位之後的其他位記錄。

下表中的下劃線“_”表示留白，而b、x等變量則代表實際的二進制資料，多個位元組之間用空格隔開。

content

節點的content屬性負責儲存節點的值，節點值可以是一個位元組數組或者整數，值的類型和長度由節點的encoding屬性決定。

圖7-9展示了一個儲存位元組數組的節點示例：

1 編碼的最高兩位00表示節點儲存的是一個位元組數組

2 編碼的後兩位001011記錄了位元組數組的長度11

3 content屬性儲存着節點的值“hello world”

圖7-10展示了一個儲存整數值的節點示例：

1 編碼11000000表示節點儲存的是一個int16_t類型的整數值

2 content屬性儲存着節點的值10086

連鎖更新

前面說過，每個節點的previous_entry_length屬性都記錄了前一個節點的長度：如果前一節點的長度小于254位元組，那麼previous_entry_length屬性的長度為1位元組，前一節點的長度就儲存在這一位元組裡面。

現在，考慮這樣一種情況：在一個壓縮清單中，有多個連續的，長度介于250位元組到253位元組之間的節點e1至eN。

以為e1至eN的所有節點的長度都小于254位元組，是以記錄這些節點的長度隻需要1位元組長的previous_entry_length屬性。

這時，如果我們将一個長度大于等于254位元組的新節點new 設定為壓縮清單的表頭節點，如下圖

因為e1的previous_entry_length屬性僅長1位元組，它沒辦法儲存新節點new的長度，是以程式将對壓縮清單執行空間重配置設定操作，并将e1節點的previous_entry_length屬性從原來的1位元組長擴充為5位元組長。

現在，麻煩的事情來了，e1原本的長度介于250位元組至253位元組之間，在為previous_entry_length屬性新增4個位元組的空間之後，e1的長度就變成了介于254位元組至257位元組之間，而這種長度使用1位元組長的previous_entry_length屬性是沒辦法儲存的。

因為，為了讓e2的previous_entry_length屬性可以記錄下e1的長度，程式需要再次對壓縮清單執行空間重配置設定操作，并将e2節點的previous_entry_length屬性從原來的1位元組長擴充為5位元組長。

如此循環，程式需要不斷地對壓縮清單執行空間重配置設定操作，直到eN為止。

redis将這種特殊情況下産生的連續多次空間擴充操作稱之為“連鎖更新”（cascade update）。除了添加新節點可能會引發連鎖更新外，删除節點也可能會引發連鎖更新。

因為連鎖更新在最壞情況下需要對壓縮清單執行n次空間重配置設定操作，而每次空間重配置設定的最壞複雜度為O(N),是以連鎖更新的最壞複雜度為O(N^2)。

要注意的是，盡管連鎖更新的複雜度較高，但它真正造成性能問題的幾率是很低的

1 壓縮清單要恰好有多個連續的、長度介于250-253位元組之間的節點，連鎖更新才有可能被引發。

2 即使出現連鎖更新，隻要被更新的節點數量不多，就不會對性能造成影響。

是以，ziplistpush等指令的平均複雜度僅為O（n），實際使用中，我們可以放心地使用這些函數，而不必擔心連鎖更新會影響壓縮清單性能。

壓縮清單API

因為ziplistpush、ziplistinsert、ziplistdelete和ziplistdeleterange四個函數都可能引發連鎖更新，是以他們最壞複雜度都是O(N^2)

Paris 2024 Gymnastics: Zou Jingyuan played perfectly to successfully defend the men's parallel bars title

Redis底層探秘（四）：整數集合及壓縮清單

整數集合

整數集合的實作

更新

降級

整數集合API

壓縮清單

壓縮清單的構成

壓縮清單節點的構成

previous_entry_length

encoding

content

連鎖更新

壓縮清單API