寫在前面

前方高能！前方高能！前方高能！文章較長，可能需要花費您兩個小時的時間，請做好心理準備，但是一旦你準備看下去，我相信您一定會有收獲，不枉此行，let’s go!!!

一、簡單動態字符串

說明：

Redis沒有直接使用C語言傳統的字符串表示(以空字符結尾的字符數組， 以下簡稱C字符串) ， 而是自己構建了一種名為簡單動態字符串(simple dynamic string， SDS) 的抽象類型， 并將SDS用作Redis的默認字符串表示。

SDS的定義代碼

struct sdshdr {
//記錄buf數組中已使用字節的數量
//等于SDS所保存字符串的長度
int len;
//記錄buf數組中未使用字節的數量
int free;
//字節數組， 用于保存字符串
//最后一個字節則保存了空字符'\0',遵循C字符串以空字符結尾的慣例
//不計算在SDS的len屬性里面
char buf[];

};

SDS圖示說明

C字符串和SDS之間的區別

Redis只會使用C字符串作為字面量， 在大多數情況下， Redis使用SDS(Simple Dynamic String， 簡單動態字符串) 作為字符串表示。

重點總結：

·Redis只會使用C字符串作為字面量， 在大多數情況下， Redis使用SDS(Simple Dynamic String， 簡單動態字符串) 作為字符串表示。

·比起C字符串， SDS具有以下優點：

1) 常數復雜度獲取字符串長度。

2) 杜絕緩沖區溢出。

3) 減少修改字符串長度時所需的內存重分配次數。

4) 二進制安全。

5) 兼容部分C字符串函數。

二、鏈表

說明

因為Redis使用的C語言并沒有內置這種數據結構， 所以Redis構建了自己的鏈表實現。

鏈表結構定義

代碼節點listNode說明：

typedef struct listNode {
//前置節點
struct listNode * prev;
//后置節點
struct listNode * next;
//節點的值
void * value;

}listNode;

節點圖示說明：

鏈表list結構代碼說明：

typedef struct list {
//表頭節點
listNode * head;
//表尾節點
listNode * tail;
//鏈表所包含的節點數量unsigned long len;
//節點值復制函數
void *(*dup)(void *ptr);
//節點值釋放函數
void (*free)(void *ptr);
//節點值對比函數
int (*match)(void *ptr,void *key);

} list;

list圖示說明：

特點：雙端、無環、帶表頭指針和表尾指針、帶鏈表長度計數器、多態

重點總結：

·鏈表被廣泛用于實現Redis的各種功能， 比如列表鍵、 發布與訂閱、 慢查詢、 監視器等。

·每個鏈表節點由一個listNode結構來表示， 每個節點都有一個指向前置節點和后置節點的指針， 所以Redis的鏈表實現是雙端鏈表。

·每個鏈表使用一個list結構來表示， 這個結構帶有表頭節點指針、 表尾節點指針， 以及鏈表長度等信息。

·因為鏈表表頭節點的前置節點和表尾節點的后置節點都指向NULL， 所以Redis的鏈表實現是無環鏈表。

·通過為鏈表設置不同的類型特定函數， Redis的鏈表可以用于保存各種不同類型的值。

三、字典

說明：

字典， 又稱為符號表(sy mbol table) 、 關聯數組(associative array) 或映射(map) ，是一種用于保存鍵值對(key-value pair) 的抽象數據結構。字典經常作為一種數據結構內置在很多高級編程語言里面， 但Redis所使用的C語言并沒有內置這種數據結構， 因此Redis構建了自己的字典實現。

Redis的字典使用哈希表作為底層實現， 一個哈希表里面可以有多個哈希表節點， 而每個哈希表節點就保存了字典中的一個鍵值對。

Redis字典所使用的哈希表由dict.h/dictht結構定義

typedef struct dictht {
//哈希表數組
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小掩碼， 用于計算索引值
//總是等于size-1
unsigned long sizemask;
//該哈希表已有節點的數量
unsigned long used;

} dictht;

hash表的圖示：

table屬性是一個數組， 數組中的每個元素都是一個指向dict.h/dictEntry結構的指針， 每個dictEntry結構保存著一個鍵值對。

hash表節點定義

typedef struct dictEntry {
//鍵
void *key;
//值
union{void *val;
uint64_tu64;
int64_ts64;
} v;
//指向下個哈希表節點， 形成鏈表
struct dictEntry *next;
} dictEntry;

next屬性是指向另一個哈希表節點的指針， 這個指針可以將多個哈希值相同的鍵值對連接在一次， 以此來解決鍵沖突(collision) 的問題。舉個例子， 圖4-2就展示了如何通過next指針， 將兩個索引值相同的鍵k1和k0連接在一起。

字典定義代碼

typedef struct dict {
//類型特定函數dictType *type;
//私有數據
void *privdata;
//哈希表
dictht ht[2];
// rehash索引
//當rehash不在進行時， 值為-1
in trehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;

type屬性和privdata屬性是針對不同類型的鍵值對， 為創建多態字典而設置的：

·type屬性是一個指向dictTy pe結構的指針， 每個dictType結構保存了一簇用于操作特定類型鍵值對的函數， Redis會為用途不同的字典設置不同的類型特定函數。

·而privdata屬性則保存了需要傳給那些類型特定函數的可選參數

.ht屬性是一個包含兩個項的數組， 數組中的每個項都是一個dictht哈希表， 一般情況下，字典只使用ht[0]哈希表， ht[1]哈希表只會在對ht[0]哈希表進行rehash時使用。除了ht[1]之外， 另一個和rehash有關的屬性就是rehashidx， 它記錄了rehash目前的進度， 如果目前沒有在進行rehash， 那么它的值為-1。

typedef struct dictType {
//計算哈希值的函數
unsigned int (*hashFunction)(const void *key);
//復制鍵的函數
void *(*keyDup)(void *privdata, const void *key);
//復制值的函數
void *(*valDup)(void *privdata, const void *obj);
//對比鍵的函數
int (*keyCompare)
(void *privdata, const void *key1, const void *key2);
//銷毀鍵的函數
void (*keyDestructor)(void *privdata, void *key);
//銷毀值的函數
void (*valDestructor)(void *privdata, void *obj);

} dictType;

字典定義圖示：

哈希算法說明

當要將一個新的鍵值對添加到字典里面時， 程序需要先根據鍵值對的鍵計算出哈希值和索引值， 然后再根據索引值， 將包含新鍵值對的哈希表節點放到哈希表數組的指定索引上面。

Redis計算哈希值和索引值的方法如下：

#使 用字典設置的哈希函數， 計算鍵key的哈希值

hash = dict->type->hashFunction(key);

#使用哈希表的sizemask屬性和哈希值， 計算出索引值

#根據情況不同， ht[x]可以是ht[0]或者ht[1]

index = hash & dict->ht[x].sizemask;

hash算法舉例

舉個例子， 對于圖4-4所示的字典來說， 如果我們要將一個鍵值對k0和v0添加到字典里面， 那么程序會先使用語句：

hash = dict->type->hashFunction(k0);

計算鍵k0的哈希值。

假設計算得出的哈希值為8， 那么程序會繼續使用語句：

index = hash&dict->ht[0].sizemask = 8 & 3 = 0;

計算出鍵k0的索引值0， 這表示包含鍵值對k0和v0的節點應該被放置到哈希表數組的索引0位置上， 如圖4-5所示。

當字典被用作數據庫的底層實現， 或者哈希鍵的底層實現時， Redis使用MurmurHash2算法來計算鍵的哈希值。MurmurHash算法最初由Austin Appleby于2008年發明， 這種算法的優點在于， 即使輸入的鍵是有規律的， 算法仍能給出一個很好的隨機分布性， 并且算法的計算速度也非常快。MurmurHash算法目前的最新版本為MurmurHash3， 而Redis使用的是MurmurHash2， 關于MurmurHash算法的更多信息可以參考該算法的主頁：http://code.google.com/p/smhasher/。

解決鍵沖突

當有兩個或以上數量的鍵被分配到了哈希表數組的同一個索引上面時， 我們稱這些鍵發生了沖突(collision) 。Redis的哈希表使用鏈地址法(separate chaining) 來解決鍵沖突， 每個哈希表節點都有一個next指針， 多個哈希表節點可以用next指針構成一個單向鏈表， 被分配到同一個索引上的多個節點可以用這個單向鏈表連接起來， 這就解決了鍵沖突的問題。
舉個例子， 假設程序要將鍵值對k2和v2添加到圖4-6所示的哈希表里面， 并且計算得出k2的索引值為2， 那么鍵k1和k2將產生沖突， 而解決沖突的辦法就是使用next指針將鍵k2和k1所
在的節點連接起來， 如圖4-7所示。
因為dictEntry節點組成的鏈表沒有指向鏈表表尾的指針， 所以為了速度考慮， 程序總是將新節點添加到鏈表的表頭位置(復雜度為O(1) ) ， 排在其他已有節點的前面。

rehash

隨著操作的不斷執行， 哈希表保存的鍵值對會逐漸地增多或者減少， 為了讓哈希表的負載因子(load factor) 維持在一個合理的范圍之內， 當哈希表保存的鍵值對數量太多或者太少時， 程序需要對哈希表的大小進行相應的擴展或者收縮。
擴展和收縮哈希表的工作可以通過執行rehash(重新散列) 操作來完成， Redis對字典的哈希表執行rehash的步驟如下：

1) 為字典的ht[1]哈希表分配空間， 這個哈希表的空間大小取決于要執行的操作， 以及ht[0]當前包含的鍵值對數量(也即是ht[0].used屬性的值) ：

·如果執行的是擴展操作， 那么ht[1]的大小為第一個大于等于ht[0].used*2的2 ⁿ(2的n次方冪) ；

·如果執行的是收縮操作， 那么ht[1]的大小為第一個大于等于ht[0].used的2 ⁿ。

2) 將保存在ht[0]中的所有鍵值對rehash到ht[1]上面：rehash指的是重新計算鍵的哈希值
和索引值， 然后將鍵值對放置到ht[1]哈希表的指定位置上。

3) 當ht[0]包含的所有鍵值對都遷移到了ht[1]之后(ht[0]變為空表) ， 釋放ht[0]， 將ht[1]設置為ht[0]， 并在ht[1]新創建一個空白哈希表， 為下一次rehash做準備。
舉個例子， 假設程序要對圖4-8所示字典的ht[0]進行擴展操作， 那么程序將執行以下步驟：

1) ht[0].used當前的值為4， 4*2=8， 而8(2 ³) 恰好是第一個大于等于4的2的n次方， 所以程序會將ht[1]哈希表的大小設置為8。圖4-9展示了ht[1]在分配空間之后， 字典的樣子。

2) 將ht[0]包含的四個鍵值對都rehash到ht[1]， 如圖4-10所示。

3) 釋放ht[0]， 并將ht[1]設置為ht[0]， 然后為ht[1]分配一個空白哈希表， 如圖4-11所示。
至此， 對哈希表的擴展操作執行完畢， 程序成功將哈希表的大小從原來的4改為了現在的8。

哈希表的擴展與收縮

當以下條件中的任意一個被滿足時， 程序會自動開始對哈希表執行擴展操作：

1) 服務器目前沒有在執行BGSAVE命令或者BGREWRITEAOF命令， 并且哈希表的負載
因子大于等于1。

2) 服務器目前正在執行BGSAVE命令或者BGREWRITEAOF命令， 并且哈希表的負載因子大于等于5。其中哈希表的負載因子可以通過公式：

#負載因子=哈希表已保存節點數量/哈希表大小

load_factor = ht[0].used / ht[0].size計算得出。
例如， 對于一個大小為4， 包含4個鍵值對的哈希表來說， 這個哈希表的負載因子為：load_factor = 4 / 4 = 1

又例如， 對于一個大小為512， 包含256個鍵值對的哈希表來說， 這個哈希表的負載因子為：load_factor = 256 / 512 = 0.5根據BGSAVE命令或BGREWRITEAOF命令是否正在執行， 服務器執行擴展操作所需的負載因子并不相同， 這是因為在執行BGSAVE命令或BGREWRITEAOF命令的過程中， Redis需要創建當前服務器進程的子進程， 而大多數操作系統都采用寫時復制(copy-on-write) 技術來優化子進程的使用效率， 所以在子進程存在期間， 服務器會提高執行擴展操作所需的負載因子， 從而盡可能地避免在子進程存在期間進行哈希表擴展操作， 這可以避免不必要的內存寫入操作， 最大限度地節約內存。另一方面， 當哈希表的負載因子小于0.1時， 程序自動開始對哈希表執行收縮操作。

漸進式rehash

擴展或收縮哈希表需要將ht[0]里面的所有鍵值對rehash到ht[1]里面， 但
是， 這個rehash動作并不是一次性、 集中式地完成的， 而是分多次、 漸進式地完成的。這樣做的原因在于， 如果ht[0]里只保存著四個鍵值對， 那么服務器可以在瞬間就將這些鍵值對全部rehash到ht[1]；但是， 如果哈希表里保存的鍵值對數量不是四個， 而是四百萬、四千萬甚至四億個鍵值對， 那么要一次性將這些鍵值對全部rehash到ht[1]的話， 龐大的計算量可能會導致服務器在一段時間內停止服務。因此， 為了避免rehash對服務器性能造成影響， 服務器不是一次性將ht[0]里面的所有鍵值對全部rehash到ht[1]， 而是分多次、 漸進式地將ht[0]里面的鍵值對慢慢地rehash到ht[1]。
以下是哈希表漸進式rehash的詳細步驟：

1) 為ht[1]分配空間， 讓字典同時持有ht[0]和ht[1]兩個哈希表。

2) 在字典中維持一個索引計數器變量rehashidx， 并將它的值設置為0， 表示rehash工作正式開始。

3) 在rehash進行期間， 每次對字典執行添加、 刪除、 查找或者更新操作時， 程序除了執行指定的操作以外， 還會順帶將ht[0]哈希表在rehashidx索引上的所有鍵值對rehash到ht[1]，當rehash工作完成之后， 程序將rehashidx屬性的值增一。

4) 隨著字典操作的不斷執行， 最終在某個時間點上， ht[0]的所有鍵值對都會被rehash至ht[1]， 這時程序將rehashidx屬性的值設為-1， 表示rehash操作已完成。漸進式rehash的好處在于它采取分而治之的方式， 將rehash鍵值對所需的計算工作均攤到對字典的每個添加、 刪除、 查找和更新操作上， 從而避免了集中式rehash而帶來的龐大計算量。圖4-12至圖4-17展示了一次完整的漸進式rehash過程， 注意觀察在整個rehash過程中， 字典的rehashidx屬性是如何變化的。

漸進式rehash執行期間的哈希表操作因為在進行漸進式rehash的過程中， 字典會同時使用ht[0]和ht[1]兩個哈希表， 所以在漸進式rehash進行期間， 字典的刪除(delete) 、 查找(find) 、 更新(update) 等操作會在兩個哈希表上進行。例如， 要在字典里面查找一個鍵的話， 程序會先在ht[0]里面進行查找， 如果沒找到的話， 就會繼續到ht[1]里面進行查找， 諸如此類。另外， 在漸進式rehash執行期間， 新添加到字典的鍵值對一律會被保存到ht[1]里面， 而ht[0]則不再進行任何添加操作， 這一措施保證了ht[0]包含的鍵值對數量會只減不增， 并隨著rehash操作的執行而最終變成空表。

重點總結

字典被廣泛用于實現Redis的各種功能， 其中包括數據庫和哈希鍵。

·Redis中的字典使用哈希表作為底層實現， 每個字典帶有兩個哈希表， 一個平時使用，另一個僅在進行rehash時使用。

·當字典被用作數據庫的底層實現， 或者哈希鍵的底層實現時， Redis使用MurmurHash2算法來計算鍵的哈希值。·哈希表使用鏈地址法來解決鍵沖突， 被分配到同一個索引上的多個鍵值對會連接成一個單向鏈表。

·在對哈希表進行擴展或者收縮操作時， 程序需要將現有哈希表包含的所有鍵值對rehash到新哈希表里面， 并且這個rehash過程并不是一次性地完成的， 而是漸進式地完成的。

四、跳躍表

說明：

跳躍表(skiplist) 是一種有序數據結構， 它通過在每個節點中維持多個指向其他節點的指針， 從而達到快速訪問節點的目的。跳躍表支持平均O(logN) 、 最壞O(N) 復雜度的節點查找， 還可以通過順序性操作來批量處理節點。在大部分情況下， 跳躍表的效率可以和平衡樹相媲美， 并且因為跳躍表的實現比平衡樹要來得更為簡單， 所以有不少程序都使用跳躍表來代替平衡樹。Redis使用跳躍表作為有序集合鍵的底層實現之一， 如果一個有序集合包含的元素數量比較多， 又或者有序集合中元素的成員(member) 是比較長的字符串時， Redis就會使用跳躍表來作為有序集合鍵的底層實現。

跳躍表的節點

typedef struct zskiplistNode {
//層
struct zskiplistLevel {
//前進指針
struct zskiplistNode *forward;
//跨度
unsigned int span;
} level[];
//后退指針
struct zskiplistNode *backward;
//分值
double score;
//成員對象
robj *obj;
} zskiplistNode;

跳躍表代碼定義

typedef struct zskiplist {
//表頭節點和表尾節點
structz skiplistNode *header, *tail;
//表中節點的數量
unsigned long length;
//表中層數最大的節點的層數
int level;
} zskiplist;

header和tail指針分別指向跳躍表的表頭和表尾節點， 通過這兩個指針， 程序定位表頭節點和表尾節點的復雜度為O(1) 。通過使用length屬性來記錄節點的數量， 程序可以在O(1) 復雜度內返回跳躍表的長度。level屬性則用于在O(1) 復雜度內獲取跳躍表中層高最大的那個節點的層數量， 注意表頭節點的層高并不計算在內。

重點總結

·跳躍表是有序集合的底層實現之一。

·Redis的跳躍表實現由zskiplist和zskiplistNode兩個結構組成， 其中zskiplist用于保存跳躍表信息(比如表頭節點、 表尾節點、 長度) ， 而zskiplistNode則用于表示跳躍表節點。

·每個跳躍表節點的層高都是1至32之間的隨機數。·在同一個跳躍表中， 多個節點可以包含相同的分值， 但每個節點的成員對象必須是唯一的。

·跳躍表中的節點按照分值大小進行排序， 當分值相同時， 節點按照成員對象的大小進行排序。

五、整數集合

說明：

整數集合(intset) 是集合鍵的底層實現之一， 當一個集合只包含整數值元素， 并且這個集合的元素數量不多時(小于512)， Redis就會使用整數集合作為集合鍵的底層實現。

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

} intset;

升級

每當我們要將一個新元素添加到整數集合里面， 并且新元素的類型比整數集合現有所有元素的類型都要長時， 整數集合需要先進行升級(upgrade) ， 然后才能將新元素添加到整數集合里面。
升級整數集合并添加新元素共分為三步進行：

1) 根據新元素的類型， 擴展整數集合底層數組的空間大小， 并為新元素分配空間。

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

3) 將新元素添加到底層數組里面。

升級的好處

整數集合的升級策略有兩個好處， 一個是提升整數集合的靈活性， 另一個是盡可能地節約內存。

重點總結

·整數集合是集合鍵的底層實現之一。·整數集合的底層實現為數組， 這個數組以有序、 無重復的方式保存集合元素， 在有需要時， 程序會根據新添加元素的類型， 改變這個數組的類型。

·升級操作為整數集合帶來了操作上的靈活性， 并且盡可能地節約了內存。

·整數集合只支持升級操作， 不支持降級操作。

六、壓縮列表

說明：

壓縮列表(ziplist) 是列表鍵和哈希鍵的底層實現之一。當一個列表鍵只包含少量列表項， 并且每個列表項要么就是小整數值， 要么就是長度比較短的字符串， 那么Redis就會使用壓縮列表來做列表鍵的底層實現。

壓縮列表構成

壓縮列表是Redis為了節約內存而開發的， 是由一系列特殊編碼的連續內存塊組成的順序型(sequential) 數據結構。一個壓縮列表可以包含任意多個節點(entry) ， 每個節點可以保存一個字節數組或者一個整數值。圖7-1展示了壓縮列表的各個組成部分， 表7-1則記錄了各個組成部分的類型、 長度以及用途。

壓縮列表節點的構成

每個壓縮列表節點可以保存一個字節數組或者一個整數值， 其中， 字節數組可以是以下
三種長度的其中一種：

·長度小于等于63(2 6–1) 字節的字節數組；

·長度小于等于16383(2 14–1) 字節的字節數組；

·長度小于等于4294967295(2 32–1) 字節的字節數組；
而整數值則可以是以下六種長度的其中一種：·4位長， 介于0至12之間的無符號整數；

·1字節長的有符號整數；

·3字節長的有符號整數；

·int16_t類型整數；

·int32_t類型整數；

·int64_t類型整數。
每個壓縮列表節點都由previous_entry_length、 encoding、 content三個部分組成， 如圖7-4所示

previous_entry_length

節點的previous_entry _length屬性以字節為單位， 記錄了壓縮列表中前一個節點的長度。previous_entry_length屬性的長度可以是1字節或者5字節：

·如果前一節點的長度小于254字節， 那么previous_entry_length屬性的長度為1字節：前一節點的長度就保存在這一個字節里面。

·如果前一節點的長度大于等于254字節， 那么previous_entry_length屬性的長度為5字節：其中屬性的第一字節會被設置為0xFE(十進制值254) ， 而之后的四個字節則用于保存前一節點的長度。
圖7-5展示了一個包含一字節長previous_entry_length屬性的壓縮列表節點， 屬性的值為0x05， 表示前一節點的長度為5字節

重點總結

·壓縮列表是一種為節約內存而開發的順序型數據結構。·壓縮列表被用作列表鍵和哈希鍵的底層實現之一。

·壓縮列表可以包含多個節點， 每個節點可以保存一個字節數組或者整數值。

·添加新節點到壓縮列表， 或者從壓縮列表中刪除節點， 可能會引發連鎖更新操作， 但這種操作出現的幾率并不高。

七、對象

說明

Redis用到的所有主要數據結構， 比如簡單動態字符串(SDS) 、 雙端鏈表、 字典、 壓縮列表、 整數集合等等。Redis并沒有直接使用這些數據結構來實現鍵值對數據庫， 而是基于這些數據結構創建了一個對象系統， 這個系統包含字符串對象、 列表對象、 哈希對象、 集合對象和有序集合對象這五種類型的對象， 每種對象都用到了至少一種我們前面所介紹的數據結構。通過這五種不同類型的對象， Redis可以在執行命令之前， 根據對象的類型來判斷一個對象是否可以執行給定的命令。使用對象的另一個好處是， 我們可以針對不同的使用場景， 為對象設置多種不同的數據結構實現， 從而優化對象在不同場景下的使用效率。除此之外， Redis的對象系統還實現了基于引用計數技術的內存回收機制， 當程序不再使用某個對象的時候， 這個對象所占用的內存就會被自動釋放；另外， Redis還通過引用計數技術實現了對象共享機制， 這一機制可以在適當的條件下， 通過讓多個數據庫鍵共享同一個對象來節約內存。最后， Redis的對象帶有訪問時間記錄信息， 該信息可以用于計算數據庫鍵的空轉時長，在服務器啟用了maxmemory功能的情況下， 空轉時長較大的那些鍵可能會優先被服務器刪除

對象代碼定義

typedef struct redisObject {
//類型
unsigned type:4;
//編碼
unsigned encoding:4;
//指向底層實現數據結構的指針
void *ptr;
// ...
} robj;

對象類型

編碼和底層實現

各對象類型編碼轉換條件和時機

字符串對象

int編碼的字符串對象和embstr編碼的字符串對象在條件滿足的情況下， 會被轉換為raw編碼的字符串對象。對于int編碼的字符串對象來說， 如果我們向對象執行了一些命令， 使得這個對象保存的不再是整數值， 而是一個字符串值， 那么字符串對象的編碼將從int變為raw。另外， 因為Redis沒有為embstr編碼的字符串對象編寫任何相應的修改程序(只有int編碼的字符串對象和raw編碼的字符串對象有這些程序) ， 所以embstr編碼的字符串對象實際上是只讀的。當我們對embstr編碼的字符串對象執行任何修改命令時， 程序會先將對象的編碼從embstr轉換成raw， 然后再執行修改命令。因為這個原因， embstr編碼的字符串對象在執行修改命令之后， 總會變成一個raw編碼的字符串對象

列表對象

當列表對象可以同時滿足以下兩個條件時， 列表對象使用ziplist編碼：·列表對象保存的所有字符串元素的長度都小于64字節；·列表對象保存的元素數量小于512個；不能滿足這兩個條件的列表對象需要使用linkedlist編碼。注意

以上兩個條件的上限值是可以修改的， 具體請看配置文件中關于list-max-ziplist-value選項和list-max-ziplist-entries選項的說明。對于使用ziplist編碼的列表對象來說， 當使用ziplist編碼所需的兩個條件的任意一個不能被滿足時， 對象的編碼轉換操作就會被執行， 原本保存在壓縮列表里的所有列表元素都會被轉移并保存到雙端鏈表里面， 對象的編碼也會從ziplist變為linkedlist。

哈希對象

當哈希對象可以同時滿足以下兩個條件時， 哈希對象使用ziplist編碼：·哈希對象保存的所有鍵值對的鍵和值的字符串長度都小于64字節；·哈希對象保存的鍵值對數量小于512個；不能滿足這兩個條件的哈希對象需要使用hashtable編碼。注意這兩個條件的上限值是可以修改的， 具體請看配置文件中關于hash-max-ziplist-value選項和hash-max-ziplist-entries選項的說明。對于使用ziplist編碼的列表對象來說， 當使用ziplist編碼所需的兩個條件的任意一個不能被滿足時， 對象的編碼轉換操作就會被執行， 原本保存在壓縮列表里的所有鍵值對都會被轉移并保存到字典里面， 對象的編碼也會從ziplist變為hashtable。

集合對象

當集合對象可以同時滿足以下兩個條件時， 對象使用intset編碼：·集合對象保存的所有元素都是整數值；·集合對象保存的元素數量不超過512個。不能滿足這兩個條件的集合對象需要使用hashtable編碼。注意第二個條件的上限值是可以修改的， 具體請看配置文件中關于set-max-intset-entries選項的說明。對于使用intset編碼的集合對象來說， 當使用intset編碼所需的兩個條件的任意一個不能被滿足時， 就會執行對象的編碼轉換操作， 原本保存在整數集合中的所有元素都會被轉移并保存到字典里面， 并且對象的編碼也會從intset變為hashtable。

有序集合對象

當有序集合對象可以同時滿足以下兩個條件時， 對象使用ziplist編碼：·有序集合保存的元素數量小于128個；·有序集合保存的所有元素成員的長度都小于64字節；不能滿足以上兩個條件的有序集合對象將使用skiplist編碼。注意以上兩個條件的上限值是可以修改的， 具體請看配置文件中關于zset-max-ziplist-entries選項和zset-max-ziplist-value選項的說明。對于使用ziplist編碼的有序集合對象來說， 當使用ziplist編碼所需的兩個條件中的任意一個不能被滿足時， 就會執行對象的編碼轉換操作， 原本保存在壓縮列表里的所有集合元素都會被轉移并保存到zset結構里面， 對象的編碼也會從ziplist變為skiplist。

內存回收

因為C語言并不具備自動內存回收功能， 所以Redis在自己的對象系統中構建了一個引用計數(reference counting) 技術實現的內存回收機制， 通過這一機制， 程序可以通過跟蹤對象的引用計數信息， 在適當的時候自動釋放對象并進行內存回收。每個對象的引用計數信息由redisObject結構的refcount屬性記錄：

typedef struct redisObject {
// ...
//引用計數
int refcount;
// ...
} robj;

對象的引用計數信息會隨著對象的使用狀態而不斷變化：

·在創建一個新對象時， 引用計數的值會被初始化為1；

·當對象被一個新程序使用時， 它的引用計數值會被增一；

·當對象不再被一個程序使用時， 它的引用計數值會被減一；

·當對象的引用計數值變為0時， 對象所占用的內存會被釋放。
表8-12列出了修改對象引用計數的API， 這些API分別用于增加、 減少、 重置對象的引用計數。

對象共享

目前來說， Redis會在初始化服務器時， 創建一萬個字符串對象， 這些對象包含了從0到9999的所有整數值， 當服務器需要用到值為0到9999的字符串對象時， 服務器就會使用這些共享對象， 而不是新創建對象。另外， 這些共享對象不單單只有字符串鍵可以使用， 那些在數據結構中嵌套了字符串對象的對象(linkedlist編碼的列表對象、 hashtable編碼的哈希對象、hashtable編碼的集合對象，以及zset編碼的有序集合對象) 都可以使用這些共享對象。

對象的空轉時長

除了前面介紹過的ty pe、 encoding、 ptr和refcount四個屬性之外， redisObject結構包含的最后一個屬性為lru屬性， 該屬性記錄了對象最后一次被命令程序訪問的時間：

typedef struct redisObject {
// ...
unsigned lru:22;
// ...
} robj;

OBJECT IDLETIME命令可以打印出給定鍵的空轉時長， 這一空轉時長就是通過將當前時間減去鍵的值對象的lru時間計算得出的OBJECT IDLETIME命令的實現是特殊的， 這個命令在訪問鍵的值對象時， 不會修改值對象的lru屬性。除了可以被OBJECT IDLETIME命令打印出來之外， 鍵的空轉時長還有另外一項作用：如果服務器打開了maxmemory選項， 并且服務器用于回收內存的算法為volatile-lru或者allkeys-lru， 那么當服務器占用的內存數超過了maxmemory選項所設置的上限值時， 空轉時長較高的那部分鍵會優先被服務器釋放， 從而回收內存。配置文件的maxmemory選項和maxmemory-policy選項的說明介紹了關于這方面的更多信息。

重點總結

·Redis數據庫中的每個鍵值對的鍵和值都是一個對象。

·Redis共有字符串、 列表、 哈希、 集合、 有序集合五種類型的對象， 每種類型的對象至少都有兩種或以上的編碼方式， 不同的編碼可以在不同的使用場景上優化對象的使用效率。

·服務器在執行某些命令之前， 會先檢查給定鍵的類型能否執行指定的命令， 而檢查一個鍵的類型就是檢查鍵的值對象的類型。

·Redis的對象系統帶有引用計數實現的內存回收機制， 當一個對象不再被使用時， 該對象所占用的內存就會被自動釋放。

·Redis會共享值為0到9999的字符串對象。·對象會記錄自己的最后一次被訪問的時間， 這個時間可以用于計算對象的空轉時間。

如果您已閱讀到此，感謝您對公眾號里文章的認可，請動動你可愛的小指頭關注此公眾號，每天都有硬核技術文章推送，就算離開也能找到回家的路

總結

以上是生活随笔為你收集整理的c语言数据结构将链串里所有值为x的字符删除_redis数据结构与对象到底长什么样？...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。