壓縮列表（Ziplist）其應用場景主要包括以下幾個方面：

1. 哈希表（Hash）

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

使用條件

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

2. 列表（List）

當 Redis 列表中的元素數(shù)量較少且每個元素的長度較短時，壓縮列表會被用作列表的底層實現(xiàn)，以節(jié)省內(nèi)存。

使用條件

• 列表的元素數(shù)量較少（默認不超過 512 個，可以通過配置參數(shù) list-max-ziplist-entries 調(diào)整）。
• 每個元素的字符串長度較短（默認不超過 64 字節(jié)，可以通過配置參數(shù) list-max-ziplist-value 調(diào)整）。

3. 有序集合（Sorted Set）

在有序集合中，當成員數(shù)量較少且成員和分數(shù)的長度較短時，壓縮列表會被用作有序集合的底層實現(xiàn)之一，以提高存儲效率。

使用條件

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

優(yōu)點與缺點

優(yōu)點：

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

缺點：

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

示例及實際應用

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

# 創(chuàng)建一個包含用戶屬性的哈希表
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"]

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

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

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

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

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

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

底層實現(xiàn)

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

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

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

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

每個節(jié)點由以下部分組成：

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

3. 編碼方式

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

• 字符串編碼：

  • 長度小于或等于 63 字節(jié)：6 位表示長度
  • 長度小于或等于 16383 字節(jié)：14 位表示長度
  • 長度大于 16383 字節(jié)：32 位表示長度

• 整數(shù)編碼：

  • 1 字節(jié)整數(shù)：表示范圍為 [-128, 127]
  • 3 字節(jié)整數(shù)：表示范圍為 [-2^23, 2^23-1]
  • 5 字節(jié)整數(shù)：表示范圍為 [-2^39, 2^39-1]

4. 操作

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

插入

插入一個新節(jié)點，需要找到插入位置，調(diào)整后續(xù)節(jié)點的 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: 擴展內(nèi)存以容納新節(jié)點
    // step 3: 調(diào)整其他節(jié)點的 previous_entry_length 字段
    // step 4: 將新節(jié)點寫入壓縮列表
}

刪除

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

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

查找

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

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

擴容機制

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

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

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

2. 擴容步驟

步驟1：計算新長度

首先，根據(jù)當前壓縮列表的總長度和新節(jié)點的大小，計算出擴容后所需的總長度。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4. 內(nèi)存收縮

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

收縮示例

假設(shè)刪除操作導致壓縮列表變得非常稀疏，可以通過重新分配較小的內(nèi)存空間來實現(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è)計與實現(xiàn)的詳細內(nèi)容，更多關(guān)于Redis壓縮列表的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論