快捷導(dǎo)航

Redis壓縮列表的設(shè)計(jì)與實(shí)現(xiàn)

更新時(shí)間：2024年08月25日 08:41:45 作者：逸風(fēng)尊者

壓縮列表（Ziplist）是 Redis 為了節(jié)省內(nèi)存而設(shè)計(jì)的一種緊湊型數(shù)據(jù)結(jié)構(gòu),主要用于存儲(chǔ)長(zhǎng)度較短且數(shù)量較少的元素集合,本文給大家介紹了Redis壓縮列表的設(shè)計(jì)與實(shí)現(xiàn),文中通過(guò)代碼示例講解的非常詳細(xì),需要的朋友可以參考下

壓縮列表（Ziplist）其應(yīng)用場(chǎng)景主要包括以下幾個(gè)方面：

1. 哈希表（Hash）

在 Redis 中，當(dāng)哈希表（Hash）的鍵值對(duì)數(shù)量較少且每個(gè)鍵和值的長(zhǎng)度較短時(shí)，Redis 會(huì)使用壓縮列表作為哈希表的底層實(shí)現(xiàn)。這種方式可以大幅度減少內(nèi)存開銷，提高存儲(chǔ)效率。

使用條件

鍵值對(duì)數(shù)量較少（默認(rèn)不超過(guò) 512 個(gè)，可以通過(guò)配置參數(shù) hash-max-ziplist-entries 調(diào)整）。
每個(gè)鍵和值的字符串長(zhǎng)度較短（默認(rèn)不超過(guò) 64 字節(jié)，可以通過(guò)配置參數(shù) hash-max-ziplist-value 調(diào)整）。

2. 列表（List）

當(dāng) Redis 列表中的元素?cái)?shù)量較少且每個(gè)元素的長(zhǎng)度較短時(shí)，壓縮列表會(huì)被用作列表的底層實(shí)現(xiàn)，以節(jié)省內(nèi)存。

使用條件

列表的元素?cái)?shù)量較少（默認(rèn)不超過(guò) 512 個(gè)，可以通過(guò)配置參數(shù) list-max-ziplist-entries 調(diào)整）。
每個(gè)元素的字符串長(zhǎng)度較短（默認(rèn)不超過(guò) 64 字節(jié)，可以通過(guò)配置參數(shù) list-max-ziplist-value 調(diào)整）。

3. 有序集合（Sorted Set）

在有序集合中，當(dāng)成員數(shù)量較少且成員和分?jǐn)?shù)的長(zhǎng)度較短時(shí)，壓縮列表會(huì)被用作有序集合的底層實(shí)現(xiàn)之一，以提高存儲(chǔ)效率。

使用條件

成員數(shù)量較少（默認(rèn)不超過(guò) 128 個(gè)，可以通過(guò)配置參數(shù) zset-max-ziplist-entries 調(diào)整）。
每個(gè)成員和分?jǐn)?shù)的字符串長(zhǎng)度較短（默認(rèn)不超過(guò) 64 字節(jié)，可以通過(guò)配置參數(shù) zset-max-ziplist-value 調(diào)整）。

優(yōu)點(diǎn)與缺點(diǎn)

優(yōu)點(diǎn)：

高效內(nèi)存利用：通過(guò)緊湊的存儲(chǔ)結(jié)構(gòu)，大幅減少內(nèi)存占用。
適合小數(shù)據(jù)量：在存儲(chǔ)小規(guī)模數(shù)據(jù)時(shí)，能夠提供良好的性能和內(nèi)存效率。

缺點(diǎn)：

操作代價(jià)較高：由于壓縮列表是連續(xù)存儲(chǔ)結(jié)構(gòu)，插入和刪除操作可能需要移動(dòng)大量數(shù)據(jù)，性能相對(duì)較低。
不適合大數(shù)據(jù)量：壓縮列表更適合小規(guī)模的數(shù)據(jù)存儲(chǔ)，當(dāng)數(shù)據(jù)量變大時(shí)，操作效率會(huì)顯著下降。

示例及實(shí)際應(yīng)用

假設(shè)我們有一個(gè)包含用戶屬性的哈希表結(jié)構(gòu)，并且用戶屬性數(shù)量較少，屬性值也較短，這樣的哈希表會(huì)被存儲(chǔ)為壓縮列表：

# 創(chuàng)建一個(gè)包含用戶屬性的哈希表
HSET user:1000 name "Alice"
HSET user:1000 age "30"
HSET user:1000 city "New York"

# 獲取用戶屬性
HGETALL user:1000
# 返回 ["name", "Alice", "age", "30", "city", "New York"]

當(dāng)滿足壓縮列表的使用條件時(shí)，上述哈希表將以壓縮列表的形式存儲(chǔ)，從而節(jié)省內(nèi)存開銷。

同樣地，對(duì)于一個(gè)短列表和一個(gè)小規(guī)模有序集合，它們也可以被存儲(chǔ)為壓縮列表：

# 創(chuàng)建一個(gè)短列表
LPUSH mylist "element1"
LPUSH mylist "element2"
LPUSH mylist "element3"

# 獲取列表所有元素
LRANGE mylist 0 -1
# 返回 ["element3", "element2", "element1"]

# 創(chuàng)建一個(gè)小規(guī)模有序集合
ZADD myzset 1 "member1"
ZADD myzset 2 "member2"
ZADD myzset 3 "member3"

# 獲取有序集合所有成員
ZRANGE myzset 0 -1 WITHSCORES
# 返回 ["member1", "1", "member2", "2", "member3", "3"]

底層實(shí)現(xiàn)

1. 整體結(jié)構(gòu)

壓縮列表由一系列按順序排列的節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)可以存儲(chǔ)一個(gè)整數(shù)或一個(gè)字節(jié)數(shù)組。所有數(shù)據(jù)都存儲(chǔ)在連續(xù)的內(nèi)存塊中。整體結(jié)構(gòu)如下：

zlbytes：4 字節(jié)，記錄整個(gè)壓縮列表占用的內(nèi)存字節(jié)數(shù)。
zltail：4 字節(jié)，指向壓縮列表尾部節(jié)點(diǎn)的偏移量，便于快速定位最后一個(gè)節(jié)點(diǎn)。
zllen：2 字節(jié)，記錄壓縮列表中的節(jié)點(diǎn)數(shù)量。如果超過(guò) 65535，則需要遍歷整個(gè)列表來(lái)計(jì)算節(jié)點(diǎn)數(shù)量。
entryX：一個(gè)或多個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)存儲(chǔ)一個(gè)實(shí)際數(shù)據(jù)。
zlend：1 字節(jié)，特殊標(biāo)志符，值固定為 0xFF，標(biāo)記壓縮列表的結(jié)束。

2. 節(jié)點(diǎn)結(jié)構(gòu)

每個(gè)節(jié)點(diǎn)由以下部分組成：

previous_entry_length：存儲(chǔ)前一個(gè)節(jié)點(diǎn)的長(zhǎng)度，以便支持反向遍歷。當(dāng)前一個(gè)節(jié)點(diǎn)長(zhǎng)度小于 254 字節(jié)時(shí)，該字段占 1 字節(jié)；否則，該字段占 5 字節(jié)。
encoding：編碼類型和長(zhǎng)度信息，用于標(biāo)識(shí)當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)類型及其長(zhǎng)度。該字段的長(zhǎng)度取決于實(shí)際編碼方式。
content：實(shí)際存儲(chǔ)的數(shù)據(jù)，可以是整數(shù)或字節(jié)數(shù)組。

3. 編碼方式

壓縮列表支持多種編碼方式，根據(jù)數(shù)據(jù)類型和長(zhǎng)度選擇最合適的編碼方式。常見(jiàn)的編碼方式包括：

字符串編碼：
- 長(zhǎng)度小于或等于 63 字節(jié)：6 位表示長(zhǎng)度
- 長(zhǎng)度小于或等于 16383 字節(jié)：14 位表示長(zhǎng)度
- 長(zhǎng)度大于 16383 字節(jié)：32 位表示長(zhǎng)度
整數(shù)編碼：
- 1 字節(jié)整數(shù)：表示范圍為 [-128, 127]
- 3 字節(jié)整數(shù)：表示范圍為 [-2^23, 2^23-1]
- 5 字節(jié)整數(shù)：表示范圍為 [-2^39, 2^39-1]

4. 操作

壓縮列表支持多種操作，包括插入、刪除、查找等。這些操作通過(guò)調(diào)整節(jié)點(diǎn)結(jié)構(gòu)和更新相關(guān)元數(shù)據(jù)來(lái)實(shí)現(xiàn)。

插入

插入一個(gè)新節(jié)點(diǎn)，需要找到插入位置，調(diào)整后續(xù)節(jié)點(diǎn)的 previous_entry_length 字段，并可能觸發(fā)內(nèi)存重分配。例如：

unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
    // step 1: 找到插入位置
    // step 2: 擴(kuò)展內(nèi)存以容納新節(jié)點(diǎn)
    // step 3: 調(diào)整其他節(jié)點(diǎn)的 previous_entry_length 字段
    // step 4: 將新節(jié)點(diǎn)寫入壓縮列表
}

刪除

刪除一個(gè)節(jié)點(diǎn)，需要調(diào)整前后節(jié)點(diǎn)的連接關(guān)系，并可能觸發(fā)內(nèi)存收縮。例如：

unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p) {
    // step 1: 找到要?jiǎng)h除的節(jié)點(diǎn)
    // step 2: 釋放節(jié)點(diǎn)占用的空間
    // step 3: 調(diào)整其他節(jié)點(diǎn)的 previous_entry_length 字段
    // step 4: 縮減內(nèi)存
}

查找

遍歷壓縮列表，查找滿足條件的節(jié)點(diǎn)。例如：

unsigned char *ziplistFind(unsigned char *zl, unsigned char *s, unsigned int slen, unsigned int skip) {
    // step 1: 遍歷壓縮列表
    // step 2: 比較節(jié)點(diǎn)內(nèi)容
    // step 3: 返回匹配的節(jié)點(diǎn)
}

擴(kuò)容機(jī)制

壓縮列表（Ziplist）的主要設(shè)計(jì)目標(biāo)之一是節(jié)省內(nèi)存。為了保持?jǐn)?shù)據(jù)緊湊存儲(chǔ)，壓縮列表使用連續(xù)的內(nèi)存塊。因此，當(dāng)需要插入新的數(shù)據(jù)時(shí)，如果現(xiàn)有內(nèi)存塊空間不足，就需要進(jìn)行擴(kuò)容操作。

1. 擴(kuò)容觸發(fā)條件

當(dāng)需要在壓縮列表中插入新節(jié)點(diǎn)，但當(dāng)前內(nèi)存空間不足以容納該新節(jié)點(diǎn)時(shí)，會(huì)觸發(fā)擴(kuò)容操作。這是為了確保壓縮列表能夠繼續(xù)正常存儲(chǔ)新增的數(shù)據(jù)。

2. 擴(kuò)容步驟

步驟1：計(jì)算新長(zhǎng)度

首先，根據(jù)當(dāng)前壓縮列表的總長(zhǎng)度和新節(jié)點(diǎn)的大小，計(jì)算出擴(kuò)容后所需的總長(zhǎng)度。

size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)); // 當(dāng)前壓縮列表的總長(zhǎng)度
size_t reqlen = zipRawEntryLength(p); // 新節(jié)點(diǎn)所需的長(zhǎng)度
size_t newlen = curlen + reqlen; // 新的總長(zhǎng)度

步驟2：分配新內(nèi)存

根據(jù)計(jì)算出的新長(zhǎng)度，為壓縮列表分配一個(gè)更大的內(nèi)存塊。這個(gè)過(guò)程通常使用 zrealloc 函數(shù)，該函數(shù)不僅會(huì)增加所需的最小容量，還會(huì)多分配一些額外的空間，以減少頻繁的內(nèi)存重分配操作，從而提高性能。

if (newlen > curlen) {
    zl = zrealloc(zl, newlen); // 分配新的內(nèi)存塊
    ZIPLIST_BYTES(zl) = intrev32ifbe(newlen); // 更新 zlbytes 字段
}

步驟3：復(fù)制舊數(shù)據(jù)

在分配了新的內(nèi)存塊之后，將舊的壓縮列表數(shù)據(jù)復(fù)制到新的內(nèi)存塊中。這是由 zrealloc 自動(dòng)處理的，程序員無(wú)需手動(dòng)干預(yù)。

步驟4：更新元數(shù)據(jù)

擴(kuò)容后，需要更新壓縮列表的元數(shù)據(jù)字段，包括 zlbytes、zltail 等，以反映新的內(nèi)存布局。

ZIPLIST_BYTES(zl) = intrev32ifbe(newlen); // 更新 zlbytes
// 如果插入點(diǎn)在尾部，需要更新 zltail
if (tail_pos == curlen) {
    ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(new_tail_offset);
}

步驟5：插入新節(jié)點(diǎn)

在更新完元數(shù)據(jù)之后，在適當(dāng)?shù)奈恢貌迦胄鹿?jié)點(diǎn)，并調(diào)整相關(guān)的 previous_entry_length 和其他必要的字段。

unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
    // ... 前面部分略 ...

    // 插入新節(jié)點(diǎn)
    memmove(p + reqlen, p, curlen - (p - zl));
    zipSetEntry(zl, p, s, slen);
    
    // 更新 zlend 標(biāo)志
    ZIPLIST_END(zl) = 0xFF;
    
    return zl;
}

3. 內(nèi)存分配策略

Redis 使用 Jemalloc 或者系統(tǒng)默認(rèn)的內(nèi)存分配器來(lái)進(jìn)行內(nèi)存管理。內(nèi)存擴(kuò)展時(shí)，通常會(huì)分配比實(shí)際需求更多的內(nèi)存，以減少未來(lái)再次擴(kuò)容的次數(shù)。這種策略稱為“緩沖區(qū)增長(zhǎng)”，可以顯著提升性能，避免頻繁的內(nèi)存分配和數(shù)據(jù)拷貝。

4. 內(nèi)存收縮

除了擴(kuò)容，壓縮列表還可能進(jìn)行收縮操作。當(dāng)刪除大量節(jié)點(diǎn)或者節(jié)點(diǎn)內(nèi)容縮小時(shí)，壓縮列表可能會(huì)釋放不再需要的內(nèi)存空間。這通常發(fā)生在內(nèi)存非常緊張或者節(jié)點(diǎn)刪除操作非常頻繁的情況下。

收縮示例

假設(shè)刪除操作導(dǎo)致壓縮列表變得非常稀疏，可以通過(guò)重新分配較小的內(nèi)存空間來(lái)實(shí)現(xiàn)收縮：

unsigned char *ziplistShrink(unsigned char *zl) {
    size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl));
    size_t newlen = calculateNewLengthAfterDeletion(zl);

    if (newlen < curlen) {
        zl = zrealloc(zl, newlen);
        ZIPLIST_BYTES(zl) = intrev32ifbe(newlen);
    }

    return zl;
}

以上就是Redis壓縮列表的設(shè)計(jì)與實(shí)現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于Redis壓縮列表的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: