亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

Redis中ziplist壓縮列表的實現

 更新時間:2023年06月14日 09:10:13   作者:mooddance  
本文主要介紹了Redis中ziplist壓縮列表的實現,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧

一 前言

List 列表是簡單的字符串列表,按照插入順序排序,可以從頭部或尾部向 List 列表添加元素。最大長度為 2^32 - 1,也即每個列表支持超過 40 億個元素。

Redis 的 List 類型有多種實現方式,由雙向鏈表或壓縮列表(v7.0 由 listpack 替代)實現的。這篇文章就是介紹其中一種實現 ziplist - 壓縮列表。

ziplist 被設計成一種內存緊湊型的數據結構,占用一塊連續(xù)的內存空間,不僅可以利用 CPU 緩存,而且會針對不同長度的數據,進行相應編碼,這種方法可以有效地節(jié)省內存開銷。

二 源碼解讀

一如既往,關于 ziplist 的定義和實現還是放在一對文件中,分別是 ziplist.h 和 ziplist.c。在 ziplist.c 文件的頭部有著這么一段注釋介紹什么是 ziplist。

ziplist 是一個經過特殊編碼的雙向鏈表,旨在提高內存效率。 它存儲字符串和整數值,其中整數被編碼為實際整數而不是一系列字符。 它允許在 O(1) 時間內在列表的任一側進行推送和彈出操作。 但是,由于每個操作都需要重新分配 ziplist 使用的內存,因此實際復雜性與 ziplist 使用的內存量有關。

從這段話得到:對于不同的數據類型有著不同的編碼方式,理解為會對數據進行壓縮,從而達到減少內存使用的目的。但是隨著存儲的 value 數據級增加,使用 ziplist 所付出的代價也隨之增加。

2.1 ziplist 布局

ziplist 是一個特殊雙向鏈表,不像普通的鏈表使用前后指針關聯在一起,它是存儲在連續(xù)內存上的。

/* 創(chuàng)建一個空的 ziplist. */
unsigned char *ziplistNew(void) {
    unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE;
    unsigned char *zl = zmalloc(bytes);
    ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
    ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
    ZIPLIST_LENGTH(zl) = 0;
    zl[bytes-1] = ZIP_END;
    return zl;
}

整體的結構布局如下圖:

  • zlbytes: 32 位無符號整型,記錄 ziplist 整個結構體的占用空間大小。當然了也包括 zlbytes 本身。這個結構有個很大的用處,就是當需要修改 ziplist 時候不需要遍歷即可知道其本身的大小。 這個 SDS 中記錄字符串的長度有相似之處,這些好的設計往往在平時的開發(fā)中可以采納一下。
  • zltail: 32 位無符號整型, 記錄整個 ziplist 中最后一個 entry 的偏移量。所以在尾部進行 POP 操作時候不需要先遍歷一次。
  • zllen: 16 位無符號整型, 記錄 entry 的數量, 所以只能表示 2^16。但是 Redis 作了特殊的處理:當實體數超過 2^16 ,該值被固定為 2^16 - 1。 所以這種時候要知道所有實體的數量就必須要遍歷整個結構了。
  • entry: 真正存數據的結構。
  • zlend: 8 位無符號整型, 固定為 255 (0xFF)。為 ziplist 的結束標識。

2.2 entry 節(jié)點

每個 entry 都包含兩條信息的元數據為前綴:
第一元數據用來存儲前一個 entry 的長度,以便能夠從后向前遍歷列表。
第二元數據是表示 entry 的編碼形式。 用來表示 entry 類型,整數或字符串,在字符串的情況下,它還表示字符串有效的長度。

typedef struct zlentry {
    unsigned int prevrawlensize; /* 用于編碼前一個節(jié)點字節(jié)長度*/
    unsigned int prevrawlen;     
    unsigned int lensize;        /* 用于編碼此節(jié)點類型/長度的字節(jié)。
    								例如,字符串有1、2或5個字節(jié)標題。
    								整數總是使用一個字節(jié)。
    							*/
    unsigned int len;            /* 用于表示節(jié)點實際的字節(jié)。
									對于字符串,這只是字符串長度
									而對于整數,它是1、2、3、4、8或
									0,具體取決于數字范圍。 
								*/
    unsigned int headersize;     /* prevrawlensize + lensize. */
    unsigned char encoding;      /* 設置為ZIP_STR_*或ZIP_INT_*,具體取決于節(jié)點編碼。*/
    unsigned char *p;            /* 第一個節(jié)點的地址指針,prev-entry-len */
} zlentry;

所以一個完整的 ziplist 是這樣存儲的:

2.2.1 prelen

  • 記錄前一個 entry 的長度。若前一個 entry 的長度小于 254 , 則使用 1 個字節(jié)的 8 位無符號整數來表示。
  • 若前一個 entry 長度大于等于 254,則使用 5 個字節(jié)來表示。第 1 個字節(jié)固定為 254 (FE) 作為標識,剩余 4 字節(jié)則用來表示前一個 entry 的實際大小。

1. 前一個 entry 大小不超過 253。

<prevlen from 0 to 253> <encoding> <entry>

2. 前一個 entry 大小超過 253。

0xFE <4 bytes unsigned little endian prevlen> <encoding> <entry>

2.2.2 encoding 編碼

entry 的編碼字段取決于具體值的內容,分為字符串、數字兩種類型單獨處理。

1. 當 entry 是字符串時,有 3 種編碼方式。編碼第 1 個字節(jié)的前 2 位將保存用于存儲字符串長度的編碼類型,后面是字符串的實際長度。

1. 長度小于或等于 63 字節(jié)(6 位)的字符串值。 “pppppp”表示無符號的 6 位數據長度。
|00pppppp| - 1 byte
2. 長度小于或等于 16383 字節(jié)(14 位)的字符串值。14 位的數據采用  big endian 存儲。
big endian 是一種字節(jié)序方式,有Little-Endian、Big-Endian兩種。
|01pppppp|qqqqqqqq| - 2 bytes
3. 長度大于或等于 16384 字節(jié)的字符串值。
采用 big endian 存儲且可表示的字符串長度最大2^32-1,所以第一個字節(jié)沒有用到,所以低6位沒有用,所以都是0。
|10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| - 5 bytes 

2. 當 entry 是整數時,有 6 種編碼方式。前 2 位都固定為 1,接下來的 2 位用于指定將在此標頭后存儲哪種類型的整數。

與 ziplist 標頭一樣,所有整數都以 Little-Endian 序表示,即使此代碼是在 Big-Endian 系統(tǒng)中編譯的。

1. 整數編碼為 int16_t(2 字節(jié))。
|11000000| - 3 bytes
2. 整數編碼為int32_t(4個字節(jié))。
|11010000| - 5 bytes
3. 整數編碼為 int64_t(8 字節(jié))。
|11100000| - 9 bytes
4. 整數編碼為24位帶符號(3個字節(jié))。
|11110000| - 4 bytes
5. 整數編碼為 8 位有符號(1 字節(jié))。
|11111110| - 2 bytes
6. 0到12的無符號整數。編碼后的值實際上是1到13,因為0000和1111不能用,所以要從編碼后的4位值中減去1才能得到正確的值。
|1111xxxx| - (with xxxx between 0001 and 1101) immediate 4 bit integer

3. 結尾編碼標識

1. 表示 ziplist 結尾的標識。
|11111111|

三 連鎖更新

連鎖更新是 ziplist 一個比較大的缺點,這也是在 v7.0 被 listpack 所替代的一個重要原因。

ziplist 在更新或者新增時候,如空間不夠則需要對整個列表進行重新分配。當新插入的元素較大時,可能會導致后續(xù)元素的 prevlen 占用空間都發(fā)生變化,從而引起「連鎖更新」問題,導致每個元素的空間都要重新分配,造成訪問壓縮列表性能的下降。

ziplist 節(jié)點的 prevlen 屬性會根據前一個節(jié)點的長度進行不同的空間大小分配:

  • 如果前一個節(jié)點的長度小于 254 字節(jié),那么 prevlen 屬性需要用 1 字節(jié)的空間來保存這個長度值。
  • 如果前一個節(jié)點的長度大于等于 254 字節(jié),那么 prevlen 屬性需要用 5 字節(jié)的空間來保存這個長度值。

假設有這樣的一個 ziplist,每個節(jié)點都是等于 253 字節(jié)的。新增了一個大于等于 254 字節(jié)的新節(jié)點,由于之前的節(jié)點 prevlen 長度是 1 個字節(jié)。

為了要記錄新增節(jié)點的長度所以需要對節(jié)點 1 進行擴展,由于節(jié)點 1 本身就是 253 字節(jié),再加上擴展為 5 字節(jié)的 pervlen 則長度超過了 254 字節(jié),這時候下一個節(jié)點又要進行擴展了。噩夢就開始了。

四 總結

  • ziplist 為了節(jié)省內存,采用了緊湊的連續(xù)存儲。所以在修改操作下并不能像一般的鏈表那么容易,需要從新分配新的內存,然后復制到新的空間。
  • ziplist 是一個雙向鏈表,可以在時間復雜度為 O(1) 從下頭部、尾部進行 pop 或 push。
  • 新增或更新元素可能會出現連鎖更新現象。
  • 不能保存過多的元素,否則查詢效率就會降低。

其實使用中并沒有直接指定是否使用這種數據結構,但是可以設置何種情況下使用它??梢栽?Redis 的配置文件中進行設置。

支持的數據類型有 List 對象、Hash 對象、Zset 對象,有以下可選設置項:

  • hash-max-ziplist-entries:hash 類型元素數量超過指定數據后時候。使用 hash 存儲, 否則使用壓縮表。
  • hash-max-ziplist-value: hash 類型元素長度超過指定數據后時候。 使用 hash 存儲,否則使用壓縮鏈表。
  • zset-max-ziplist-entries:zset 類型 壓縮列表 ziplist 最大限制元素數。超過指定值將會使用跳表 skiplist + dict 來存儲。
  • zset-max-ziplist-value:set 類型 壓縮列表 ziplist 最大限制大小。超過指定將會使用跳表 skiplist+dict 來存儲。
  • list-max-ziplist-value: list 保存的所有字符串元素的長度都小于64字節(jié)。
  • list-max-ziplist-entries:list 保存的元素數量小于512個。

到此這篇關于Redis中ziplist壓縮列表的實現的文章就介紹到這了,更多相關Redis ziplist壓縮列表內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!

相關文章

  • 基于Redis實現抽獎功能及問題小結

    基于Redis實現抽獎功能及問題小結

    這篇文章主要介紹了基于Redis實現抽獎功能,本文通過實例代碼給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2021-08-08
  • Linux快速部署Redis

    Linux快速部署Redis

    這篇文章介紹了Linux下快速部署Redis的方法,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2022-01-01
  • 詳解Redis 數據類型

    詳解Redis 數據類型

    這篇文章主要介紹了Redis 數據類型的相關資料,文中講解非常細致,代碼幫助大家更好的理解和學習,感興趣的朋友可以了解下
    2020-08-08
  • Redis7.2.x主從復制的實現示例

    Redis7.2.x主從復制的實現示例

    本文主要介紹了Redis7.2.x主從復制的實現示例,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2024-06-06
  • 利用Redis實現訪問次數限流的方法詳解

    利用Redis實現訪問次數限流的方法詳解

    這篇文章主要給大家介紹了關于如何利用Redis實現訪問次數限流的相關資料,文中通過實例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
    2022-02-02
  • Redis分布式限流組件設計與使用實例

    Redis分布式限流組件設計與使用實例

    本文主要講解基于 自定義注解+Aop+反射+Redis+Lua表達式 實現的限流設計方案。實現的限流設計與實際使用。具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2021-08-08
  • Redis刪除某個目錄下的數據的實現

    Redis刪除某個目錄下的數據的實現

    本文介紹了如何在Redis中刪除指定目錄下的數據,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2024-09-09
  • Redis優(yōu)化token校驗主動失效的實現方案

    Redis優(yōu)化token校驗主動失效的實現方案

    在普通的token頒發(fā)和校驗中 當用戶發(fā)現自己賬號和密碼被暴露了時修改了登錄密碼后舊的token仍然可以通過系統(tǒng)校驗直至token到達失效時間,所以系統(tǒng)需要token主動失效的一種能力,所以本文給大家介紹了Redis優(yōu)化token校驗主動失效的實現方案,需要的朋友可以參考下
    2024-03-03
  • redis中如何使用lua腳本讓你的靈活性提高5個逼格詳解

    redis中如何使用lua腳本讓你的靈活性提高5個逼格詳解

    這篇文章主要給大家介紹了關于redis中如何使用lua腳本讓你的靈活性提高5個逼格的相關資料,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2018-10-10
  • Redis中實現查找某個值的范圍

    Redis中實現查找某個值的范圍

    這篇文章主要介紹了Redis中實現查找某個值的范圍,本文的題引來了Redis作者Salvatore Sanfilippo(@antirez)的回答,比較經典,需要的朋友可以參考下
    2015-06-06

最新評論