SDS (Simple Dynamic String)是 Redis 最基礎的數據結構。直譯過來就是”簡單的動態字元串“。Redis 自己實現了一個動態的字元串,而不是直接使用了 C 語言中的字元串。 sds 的數據結構: struct sdshdr { // buf 中已占用空間的長度 int l ... SDS (Simple Dynamic String)是 Redis 最基礎的數據結構。直譯過來就是”簡單的動態字元串“。Redis 自己實現了一個動態的字元串,而不是直接使用了 C 語言中的字元串。 sds 的數據結構: struct sdshdr { // buf 中已占用空間的長度 int len; // buf 中剩餘可用空間的長度 int free; // 數據空間 char buf[]; } 所以一個 SDS 的就如下圖: 所以我們看到,sds 包含3個參數。buf 的長度 len,buf 的剩餘長度,以及buf。 為什麼這麼設計呢? 可以直接獲取字元串長度。 C 語言中,獲取字元串的長度需要用指針遍歷字元串,時間複雜度為 O(n),而 SDS 的長度,直接從len 獲取複雜度為 O(1)。 杜絕緩衝區溢出。 由於C 語言不記錄字元串長度,如果增加一個字元傳的長度,如果沒有註意就可能溢出,覆蓋了緊挨著這個字元的數據。對於SDS 而言增加字元串長度需要驗證 free的長度,如果free 不夠就會擴容整個 buf,防止溢出。 減少修改字元串長度時造成的記憶體再次分配。 redis 作為高性能的記憶體資料庫,需要較高的相應速度。字元串也很大概率的頻繁修改。 SDS 通過未使用空間這個參數,將字元串的長度和底層buf的長度之間的額關係解除了。buf的長度也不是字元串的長度。基於這個分設計 SDS 實現了空間的預分配和惰性釋放。 預分配 如果對 SDS 修改後,如果 len 小於 1MB 那 len = 2 * len + 1byte。 這個 1 是用於保存空位元組。 如果 SDS 修改後 len 大於 1MB 那麼 len = 1MB + len + 1byte。 惰性釋放 如果縮短 SDS 的字元串長度,redis並不是馬上減少 SDS 所占記憶體。只是增加 free 的長度。同時向外提供 API 。真正需要釋放的時候,才去重新縮小 SDS 所占的記憶體 二進位安全。 C 語言中的字元串是以 ”\0“ 作為字元串的結束標記。而 SDS 是使用 len 的長度來標記字元串的結束。所以SDS 可以存儲字元串之外的任意二進位流。因為有可能有的二進位流在流中就包含了”\0“造成字元串提前結束。也就是說 SDS 不依賴 “\0” 作為結束的依據。 相容C語言 SDS 按照慣例使用 ”\0“ 作為結尾的管理。部分普通C 語言的字元串 API 也可以使用。 鏈表 C語言中並沒有鏈表這個數據結構所以 Redis 自己實現了一個。Redis 中的鏈表是: typedef struct listNode { // 前置節點 struct listNode *prev; // 後置節點 struct listNode *next; // 節點的值 void *value;} listNode; 非常典型的雙向鏈表的數據結構。 同時為雙向鏈表提供瞭如下操作的函數: /* * 雙端鏈表迭代器 */typedef struct listIter { // 當前迭代到的節點 listNode *next; // 迭代的方向 int direction;} listIter; /* * 雙端鏈表結構 */typedef struct list { // 表頭節點 listNode *head; // 表尾節點 listNode *tail; // 節點值複製函數 void *(*dup)(void *ptr); // 節點值釋放函數 void (*free)(void *ptr); // 節點值對比函數 int (*match)(void *ptr, void *key); // 鏈表所包含的節點數量 unsigned long len;} list; 鏈表的結構比較簡單,數據結構如下: 總結一下性質: 雙向鏈表,某個節點尋找上一個或者下一個節點時間複雜度 O(1)。 list 記錄了 head 和 tail,尋找 head 和 tail 的時間複雜度為 O(1)。 獲取鏈表的長度 len 時間複雜度 O(1)。 字典 字典數據結構極其類似 java 中的 Hashmap。 Redis的字典由三個基礎的數據結構組成。最底層的單位是哈希表節點。結構如下: typedef struct dictEntry { // 鍵 void *key; // 值 union { void *val; uint64_t u64; int64_t s64; } v; // 指向下個哈希表節點,形成鏈表 struct dictEntry *next; } dictEntry; 實際上哈希表節點就是一個單項列表的節點。保存了一下下一個節點的指針。 key 就是節點的鍵,v是這個節點的值。這個 v 既可以是一個指針,也可以是一個 uint64_t或者 int64_t 整數。*next 指向下一個節點。 通過一個哈希表的數組把各個節點鏈接起來: typedef struct dictht { // 哈希表數組 dictEntry **table; // 哈希表大小 unsigned long size; // 哈希表大小掩碼,用於計算索引值 // 總是等於 size - 1 unsigned long sizemask; // 該哈希表已有節點的數量 unsigned long used; } dictht; dictht 通過圖示我們觀察: 實際上,如果對java 的基本數據結構瞭解的同學就會發現,這個數據結構和 java 中的 HashMap 是很類似的,就是數組加鏈表的結構。 字典的數據結構: typedef struct dict { // 類型特定函數 dictType *type; // 私有數據 void *privdata; // 哈希表 dictht ht[2]; // rehash 索引 // 當 rehash 不在進行時,值為 -1 int rehashidx; /* rehashing not in progress if rehashidx == -1 */ // 目前正在運行的安全迭代器的數量 int iterators; /* number of iterators currently running */ } dict; 其中的dictType 是一組方法,代碼如下: /* * 字典類型特定函數 */ 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; 字典的數據結構如下圖: 這裡我們可以看到一個dict 擁有兩個 dictht。一般來說只使用 ht[0],當擴容的時候發生了rehash的時候,ht[1]才會被使用。 當我們觀察或者研究一個hash結構的時候偶我們首先要考慮的這個 dict 如何插入一個數據? 我們梳理一下插入數據的邏輯。 計算Key 的 hash 值。找到 hash 映射到 table 數組的位置。 如果數據已經有一個 key 存在了。那就意味著發生了 hash 碰撞。新加入的節點,就會作為鏈表的一個節點接到之前節點的 next 指針上。 如果 key 發生了多次碰撞,造成鏈表的長度越來越長。會使得字典的查詢速度下降。為了維持正常的負載。Redis 會對 字典進行 rehash 操作。來增加 table 數組的長度。所以我們要著重瞭解一下 Redis 的 rehash。步驟如下: 根據ht[0] 的數據和操作的類型(擴大或縮小),分配 ht[1] 的大小。 將 ht[0] 的數據 rehash 到 ht[1] 上。 rehash 完成以後,將ht[1] 設置為 ht[0],生成一個新的ht[1]備用。 漸進式的 rehash 。 其實如果字典的 key 數量很大,達到千萬級以上,rehash 就會是一個相對較長的時間。所以為了字典能夠在 rehash 的時候能夠繼續提供服務。Redis 提供了一個漸進式的 rehash 實現,rehash的步驟如下: 分配 ht[1] 的空間,讓字典同時持有 ht[1] 和 ht[0]。 在字典中維護一個 rehashidx,設置為 0 ,表示字典正在 rehash。 在rehash期間,每次對字典的操作除了進行指定的操作以外,都會根據 ht[0] 在 rehashidx 上對應的鍵值對 rehash 到 ht[1]上。 隨著操作進行, ht[0] 的數據就會全部 rehash 到 ht[1] 。設置ht[0] 的 rehashidx 為 -1,漸進的 rehash 結束。 這樣保證數據能夠平滑的進行 rehash。防止 rehash 時間過久阻塞線程。 在進行 rehash 的過程中,如果進行了 delete 和 update 等操作,會在兩個哈希表上進行。如果是 find 的話優先在ht[0] 上進行,如果沒有找到,再去 ht[1] 中查找。如果是 insert 的話那就只會在 ht[1]中插入數據。這樣就會保證了 ht[1] 的數據只增不減,ht[0]的數據只減不增。 dict的數據結構定義 為了實現增量式重哈希(incremental rehashing),dict的數據結構里包含兩個哈希表。在重哈希期間,數據從第一個哈希表向第二個哈希表遷移。 dict的C代碼定義如下(出自Redis源碼dict.h): typedef struct dictEntry { void *key; union { void *val; uint64_t u64; int64_t s64; double d; } v; struct dictEntry *next; } dictEntry; 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; /* This is our hash table structure. Every dictionary has two of this as we * implement incremental rehashing, for the old to the new table. */ typedef struct dictht { dictEntry **table; unsigned long size; unsigned long sizemask; unsigned long used; } dictht; typedef struct dict { dictType *type; void *privdata; dictht ht[2]; long rehashidx; /* rehashing not in progress if rehashidx == -1 */ int iterators; /* number of iterators currently running */ } dict; 為了能更清楚地展示dict的數據結構定義,我們用一張結構圖來表示它。如下。 結合上面的代碼和結構圖,可以很清楚地看出dict的結構。一個dict由如下若幹項組成: 一個指向dictType結構的指針(type)。它通過自定義的方式使得dict的key和value能夠存儲任何類型的數據。 一個私有數據指針(privdata)。由調用者在創建dict的時候傳進來。 兩個哈希表(ht[2])。只有在重哈希的過程中,ht[0]和ht[1]才都有效。而在平常情況下,只有ht[0]有效,ht[1]裡面沒有任何數據。上圖表示的就是重哈希進行到中間某一步時的情況。 當前重哈希索引(rehashidx)。如果rehashidx = -1,表示當前沒有在重哈希過程中;否則,表示當前正在進行重哈希,且它的值記錄了當前重哈希進行到哪一步了。 當前正在進行遍歷的iterator的個數。這不是我們現在討論的重點,暫時忽略。 dictType結構包含若幹函數指針,用於dict的調用者對涉及key和value的各種操作進行自定義。這些操作包含: hashFunction,對key進行哈希值計算的哈希演算法。 keyDup和valDup,分別定義key和value的拷貝函數,用於在需要的時候對key和value進行深拷貝,而不僅僅是傳遞對象指針。 keyCompare,定義兩個key的比較操作,在根據key進行查找時會用到。 keyDestructor和valDestructor,分別定義對key和value的析構函數。 私有數據指針(privdata)就是在dictType的某些操作被調用時會傳回給調用者。 需要詳細察看的是dictht結構。它定義一個哈希表的結構,由如下若幹項組成: 一個dictEntry指針數組(table)。key的哈希值最終映射到這個數組的某個位置上(對應一個bucket)。如果多個key映射到同一個位置,就發生了衝突,那麼就拉出一個dictEntry鏈表。 size:標識dictEntry指針數組的長度。它總是2的指數。 sizemask:用於將哈希值映射到table的位置索引。它的值等於(size-1),比如7, 15, 31, 63,等等,也就是用二進位表示的各個bit全1的數字。每個key先經過hashFunction計算得到一個哈希值,然後計算(哈希值 & sizemask)得到在table上的位置。相當於計算取餘(哈希值 % size)。 used:記錄dict中現有的數據個數。它與size的比值就是裝載因數(load factor)。這個比值越大,哈希值衝突概率越高。 dictEntry結構中包含k, v和指向鏈表下一項的next指針。k是void指針,這意味著它可以指向任何類型。v是個union,當它的值是uint64_t、int64_t或double類型時,就不再需要額外的存儲,這有利於減少記憶體碎片。當然,v也可以是void指針,以便能存儲任何類型的數據。 dict的創建(dictCreate) dict *dictCreate(dictType *type, void *privDataPtr) { dict *d = zmalloc(sizeof(*d)); _dictInit(d,type,privDataPtr); return d; } int _dictInit(dict *d, dictType *type, void *privDataPtr) { _dictReset(&d->ht[0]); _dictReset(&d->ht[1]); d->type = type; d->privdata = privDataPtr; d->rehashidx = -1; d->iterators = 0; return DICT_OK; } static void _dictReset(dictht *ht) { ht->table = NULL; ht->size = 0; ht->sizemask = 0; ht->used = 0; } dictCreate為dict的數據結構分配空間併為各個變數賦初值。其中兩個哈希表ht[0]和ht[1]起始都沒有分配空間,table指針都賦為NULL。這意味著要等第一個數據插入時才會真正分配空間。 dict的查找(dictFind) #define dictIsRehashing(d) ((d)->rehashidx != -1) dictEntry *dictFind(dict *d, const void *key) { dictEntry *he; unsigned int h, idx, table; if (d->ht[0].used + d->ht[1].used == 0) return NULL; /* dict is empty */ if (dictIsRehashing(d)) _dictRehashStep(d); h = dictHashKey(d, key); for (table = 0; table <= 1; table++) { idx = h & d->ht[table].sizemask; he = d->ht[table].table[idx]; while(he) { if (key==he->key || dictCompareKeys(d, key, he->key)) return he; he = he->next; } if (!dictIsRehashing(d)) return NULL; } return NULL; } 上述dictFind的源碼,根據dict當前是否正在重哈希,依次做了這麼幾件事: 如果當前正在進行重哈希,那麼將重哈希過程向前推進一步(即調用_dictRehashStep)。實際上,除了查找,插入和刪除也都會觸發這一動作。這就將重哈希過程分散到各個查找、插入和刪除操作中去了,而不是集中在某一個操作中一次性做完。 計算key的哈希值(調用dictHashKey,裡面的實現會調用前面提到的hashFunction)。 先在第一個哈希表ht[0]上進行查找。在table數組上定位到哈希值對應的位置(如前所述,通過哈希值與sizemask進行按位與),然後在對應的dictEntry鏈表上進行查找。查找的時候需要對key進行比較,這時候調用dictCompareKeys,它裡面的實現會調用到前面提到的keyCompare。如果找到就返回該項。否則,進行下一步。 判斷當前是否在重哈希,如果沒有,那麼在ht[0]上的查找結果就是最終結果(沒找到,返回NULL)。否則,在ht[1]上進行查找(過程與上一步相同)。 下麵我們有必要看一下增量式重哈希的_dictRehashStep的實現。 static void _dictRehashStep(dict *d) { if (d->iterators == 0) dictRehash(d,1); } int dictRehash(dict *d, int n) { int empty_visits = n*10; /* Max number of empty buckets to visit. */ if (!dictIsRehashing(d)) return 0; while(n-- && d->ht[0].used != 0) { dictEntry *de, *nextde; /* Note that rehashidx can't overflow as we are sure there are more * elements because ht[0].used != 0 */ assert(d->ht[0].size > (unsigned long)d->rehashidx); while(d->ht[0].table[d->rehashidx] == NULL) { d->rehashidx++; if (--empty_visits == 0) return 1; } de = d->ht[0].table[d->rehashidx]; /* Move all the keys in this bucket from the old to the new hash HT */ while(de) { unsigned int h; nextde = de->next; /* Get the index in the new hash table */ h = dictHashKey(d, de->key) & d->ht[1].sizemask; de->next = d->ht[1].table[h]; d->ht[1].table[h] = de; d->ht[0].used--; d->ht[1].used++; de = nextde; } d->ht[0].table[d->rehashidx] = NULL; d->rehashidx++; } /* Check if we already rehashed the whole table... */ if (d->ht[0].used == 0) { zfree(d->ht[0].table); d->ht[0] = d->ht[1]; _dictReset(&d->ht[1]); d->rehashidx = -1; return 0; } /* More to rehash... */ return 1; } dictRehash每次將重哈希至少向前推進n步(除非不到n步整個重哈希就結束了),每一步都將ht[0]上某一個bucket(即一個dictEntry鏈表)上的每一個dictEntry移動到ht[1]上,它在ht[1]上的新位置根據ht[1]的sizemask進行重新計算。rehashidx記錄了當前尚未遷移(有待遷移)的ht[0]的bucket位置。 如果dictRehash被調用的時候,rehashidx指向的bucket里一個dictEntry也沒有,那麼它就沒有可遷移的數據。這時它嘗試在ht[0].table數組中不斷向後遍歷,直到找到下一個存有數據的bucket位置。如果一直找不到,則最多走n*10步,本次重哈希暫告結束。 最後,如果ht[0]上的數據都遷移到ht[1]上了(即d->ht[0].used == 0),那麼整個重哈希結束,ht[0]變成ht[1]的內容,而ht[1]重置為空。 根據以上對於重哈希過程的分析,我們容易看出,本文前面的dict結構圖中所展示的正是rehashidx=2時的情況,前面兩個bucket(ht[0].table[0]和ht[0].table[1])都已經遷移到ht[1]上去了。 dict的插入(dictAdd和dictReplace) dictAdd插入新的一對key和value,如果key已經存在,則插入失敗。 dictReplace也是插入一對key和value,不過在key存在的時候,它會更新value。 int dictAdd(dict *d, void *key, void *val) { dictEntry *entry = dictAddRaw(d,key); if (!entry) return DICT_ERR; dictSetVal(d, entry, val); return DICT_OK; } dictEntry *dictAddRaw(dict *d, void *key) { int index; dictEntry *entry; dictht *ht; if (dictIsRehashing(d)) _dictRehashStep(d); /* Get the index of the new element, or -1 if * the element already exists. */ if ((index = _dictKeyIndex(d, key)) == -1) return NULL; /* Allocate the memory and store the new entry. * Insert the element in top, with the assumption that in a database * system it is more likely that recently added entries are accessed * more frequently. */ ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0]; entry = zmalloc(sizeof(*entry)); entry->next = ht->table[index]; ht->table[index] = entry; ht->used++; /* Set the hash entry fields. */ dictSetKey(d, entry, key); return entry; } static int _dictKeyIndex(dict *d, const void *key) { unsigned int h, idx, table; dictEntry *he; /* Expand the hash table if needed */ if (_dictExpandIfNeeded(d) == DICT_ERR) return -1; /* Compute the key hash value */ h = dictHashKey(d, key); for (table = 0; table <= 1; table++) { idx = h & d->ht[table].sizemask; /* Search if this slot does not already contain the given key */ he = d->ht[table].table[idx]; while(he) { if (key==he->key || dictCompareKeys(d, key, he->key)) return -1; he = he->next; } if (!dictIsRehashing(d)) break; } return idx; } 以上是dictAdd的關鍵實現代碼。我們主要需要註意以下幾點: 它也會觸發推進一步重哈希(_dictRehashStep)。 如果正在重哈希中,它會把數據插入到ht[1];否則插入到ht[0]。 在對應的bucket中插入數據的時候,總是插入到dictEntry的頭部。因為新數據接下來被訪問的概率可能比較高,這樣再次查找它時就比較次數較少。 _dictKeyIndex在dict中尋找插入位置。如果不在重哈希過程中,它只查找ht[0];否則查找ht[0]和ht[1]。 _dictKeyIndex可能觸發dict記憶體擴展(_dictExpandIfNeeded,它將哈希表長度擴展為原來兩倍,具體請參考dict.c中源碼)。 dictReplace在dictAdd基礎上實現,如下: int dictReplace(dict *d, void *key, void *val) { dictEntry *entry, auxentry; /* Try to add the element. If the key * does not exists dictAdd will suceed. */ if (dictAdd(d, key, val) == DICT_OK) return 1; /* It already exists, get the entry */ entry = dictFind(d, key); /* Set the new value and free the old one. Note that it is important * to do that in this order, as the value may just be exactly the same * as the previous one. In this context, think to reference counting, * you want to increment (set), and then decrement (free), and not the * reverse. */ auxentry = *entry; dictSetVal(d, entry, val); dictFreeVal(d, &auxentry); return 0; } 在key已經存在的情況下,dictReplace會同時調用dictAdd和dictFind,這其實相當於兩次查找過程。這裡Redis的代碼不夠優化。 dict的刪除(dictDelete) dictDelete的源碼這裡忽略,具體請參考dict.c。需要稍加註意的是: dictDelete也會觸發推進一步重哈希(_dictRehashStep) 如果當前不在重哈希過程中,它只在ht[0]中查找要刪除的key;否則ht[0]和ht[1]它都要查找。 刪除成功後會調用key和value的析構函數(keyDestructor和valDestructor)。 dict的實現相對來說比較簡單,本文就介紹到這。在下一篇中我們將會介紹Redis中動態字元串的實現——sds,敬請期待。 sds的數據結構定義 我們知道,在C語言中,字元串是以’\0’字元結尾(NULL結束符)的字元數組來存儲的,通常表達為字元指針的形式(char *)。它不允許位元組0出現在字元串中間,因此,它不能用來存儲任意的二進位數據。 我們可以在sds.h中找到sds的類型定義: typedef char *sds; 肯定有人感到困惑了,竟然sds就等同於char *?我們前面提到過,sds和傳統的C語言字元串保持類型相容,因此它們的類型定義是一樣的,都是char *。在有些情況下,需要傳入一個C語言字元串的地方,也確實可以傳入一個sds。但是,sds和char *並不等同。sds是Binary Safe的,它可以存儲任意二進位數據,不能像C語言字元串那樣以字元’\0’來標識字元串的結束,因此它必然有個長度欄位。但這個長度欄位在哪裡呢?實際上sds還包含一個header結構: struct __attribute__ ((__packed__)) sdshdr5 { unsigned char flags; /* 3 lsb of type, and 5 msb of string length */ char buf[]; }; struct __attribute__ ((__packed__)) sdshdr8 { uint8_t len; /* used */ uint8_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; }; struct __attribute__ ((__packed__)) sdshdr16 { uint16_t len; /* used */ uint16_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; }; struct __attribute__ ((__packed__)) sdshdr32 { uint32_t len; /* used */ uint32_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; }; struct __attribute__ ((__packed__)) sdshdr64 { uint64_t len; /* used */ uint64_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; }; sds一共有5種類型的header。之所以有5種,是為了能讓不同長度的字元串可以使用不同大小的header。這樣,短字元串就能使用較小的header,從而節省記憶體。 一個sds字元串的完整結構,由在記憶體地址上前後相鄰的兩部分組成: 一個header。通常包含字元串的長度(len)、最大容量(alloc)和flags。sdshdr5有所不同。 一個字元數組。這個字元數組的長度等於最大容量+1。真正有效的字元串數據,其長度通常小於最大容量。在真正的字元串數據之後,是空餘未用的位元組(一般以位元組0填充),允許在不重新分配記憶體的前提下讓字元串數據向後做有限的擴展。在真正的字元串數據之後,還有一個NULL結束符,即ASCII碼為0的’\0’字元。這是為了和傳統C字元串相容。之所以字元數組的長度比最大容量多1個位元組,就是為了在字元串長度達到最大容量時仍然有1個位元組存放NULL結束符。 除了sdshdr5之外,其它4個header的結構都包含3個欄位: len: 表示字元串的真正長度(不包含NULL結束符在內)。 alloc: 表示字元串的最大容量(不包含最後多餘的那個位元組)。 flags: 總是占用一個位元組。其中的最低3個bit用來表示header的類型。header的類型共有5種,在sds.h中有常量定義。 #define SDS_TYPE_5 0 #define SDS_TYPE_8 1 #define SDS_TYPE_16 2 #define SDS_TYPE_32 3 #define SDS_TYPE_64 4 sds的數據結構,我們有必要非常仔細地去解析它。 Redis dict結構舉例 上圖是sds的一個內部結構的例子。圖中展示了兩個sds字元串s1和s2的記憶體結構,一個使用sdshdr8類型的header,另一個使用sdshdr16類型的header。但它們都表達了同樣的一個長度為6的字元串的值:”tielei”。下麵我們結合代碼,來解釋每一部分的組成。 sds的字元指針(s1和s2)就是指向真正的數據(字元數組)開始的位置,而header位於記憶體地址較低的方向。在sds.h中有一些跟解析header有關的巨集定義: #define SDS_TYPE_MASK 7 #define SDS_TYPE_BITS 3 #define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T))); #define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T)))) #define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS) 其中SDS_HDR用來從sds字元串獲得header起始位置的指針,比如SDS_HDR(8, s1)表示s1的header指針,SDS_HDR(16, s2)表示s2的header指針。 當然,使用SDS_HDR之前我們必須先知道到底是哪一種header,這樣我們才知道SDS_HDR第1個參數應該傳什麼。由sds字元指針獲得header類型的方法是,先向低地址方向偏移1個位元組的位置,得到flags欄位。比如,s1[-1]和s2[-1]分別獲得了s1和s2的flags的值。然後取flags的最低3個bit得到header的類型。 由於s1[-1] == 0x01 == SDS_TYPE_8,因此s1的header類型是sdshdr8。 由於s2[-1] == 0x02 == SDS_TYPE_16,因此s2的header類型是sdshdr16。 有了header指針,就能很快定位到它的len和alloc欄位: s1的header中,len的值為0x06,表示字元串數據長度為6;alloc的值為0x80,表示字元數組最大容量為128。 s2的header中,len的值為0x0006,表示字元串數據長度為6;alloc的值為0x03E8,表示字元數組最大容量為1000。(註意:圖中是按小端地址構成) 在各個header的類型定義中,還有幾個需要我們註意的地方: 在各個header的定義中使用了__attribute__ ((packed)),是為了讓編譯器以緊湊模式來分配記憶體。如果沒有這個屬性,編譯器可能會為struct的欄位做優化對齊,在其中填充空位元組。那樣的話,就不能保證header和sds的數據部分緊緊前後相鄰,也不能按照固定向低地址方向偏移1個位元組的方式來獲取flags欄位了。 在各個header的定義中最後有一個char buf[]。我們註意到這是一個沒有指明長度的字元數組,這是C語言中定義字元數組的一種特殊寫法,稱為柔性數組(flexible array member),只能定義在一個結構體的最後一個欄位上。 它在這裡只是起到一個標記的作用,表示在flags欄位後面就是一個字元數組,或者說,它指明瞭緊跟在flags欄位後面的這個字元數組在結構體中的偏移位置。而程式在為header分配的記憶體的時候,它並不占用記憶體空間。 如果計算sizeof(struct sdshdr16)的值,那麼結果是5個位元組,其中沒有buf欄位。 sdshdr5與其它幾個header結構不同,它不包含alloc欄位,而長度使用flags的高5位來存儲。 因此,它不能為字元串分配空餘空間。如果字元串需要動態增長,那麼它就必然要重新分配記憶體才行。所以說,這種類型的sds字元串更適合存儲靜態的短字元串(長度小於32)。 至此,我們非常清楚地看到了:sds字元串的header,其實隱藏在真正的字元串數據的前面(低地址方向)。這樣的一個定義,有如下幾個好處: header和數據相鄰,而不用分成兩塊記憶體空間來單獨分配。這有利於減少記憶體碎片,提高存儲效率(memory efficiency)。 雖然header有多個類型,但sds可以用統一的char *來表達。且它與傳統的C語言字元串保持類型相容。 如果一個sds裡面存儲的是可列印字元串,那麼我們可以直接把它傳給C函數,比如使用strcmp比較字元串大小,或者使用printf進行列印。 弄清了sds的數據結構,它的具體操作函數就比較好理解了。 sds的一些基礎函數 sdslen(const sds s): 獲取sds字元串長度。 sdssetlen(sds s, size_t newlen): 設置sds字元串長度。 sdsinclen(sds s, size_t inc): 增加sds字元串長度。 sdsalloc(const sds s): 獲取sds字元串容量。 sdssetalloc(sds s, size_t newlen): 設置sds字元串容量。 sdsavail(const sds s): 獲取sds字元串空餘空間(即alloc - len)。 sdsHdrSize(char type): 根據header類型得到header大小。 sdsReqType(size_t string_size): 根據字元串數據長度計算所需要的header類型。 這裡我們挑選sdslen和sdsReqType的代碼,察看一下。 static inline size_t sdslen(const sds s) { unsigned char flags = s[-1]; switch(flags&SDS_TYPE_MASK) { case SDS_TYPE_5: return SDS_TYPE_5_LEN(flags); case SDS_TYPE_8: return SDS_HDR(8,s)->len; case SDS_TYPE_16: return SDS_HDR(16,s)->len; case SDS_TYPE_32: return SDS_HDR(32,s)->len; case SDS_TYPE_64: return SDS_HDR(64,s)->len; } return 0; } static inline char sdsReqType(size_t string_size) { if (string_size < 1<<5) return SDS_TYPE_5; if (string_size < 1<<8) return SDS_TYPE_8; if (string_size < 1<<16) return SDS_TYPE_16; if (string_size < 1ll<<32) return SDS_TYPE_32; return SDS_TYPE_64; } 跟前面的分析類似,sdslen先用s[-1]向低地址方向偏移1個位元組,得到flags;然後與SDS_TYPE_MASK進行按位與,得到header類型;然後根據不同的header類型,調用SDS_HDR得到header起始指針,進而獲得len欄位。 通過sdsReqType的代碼,很容易看到: 長度在0和2^5-1之間,選用SDS_TYPE_5類型的header。 長度在25和28-1之間,選用SDS_TYPE_8類型的header。 長度在28和216-1之間,選用SDS_TYPE_16類型的header。 長度在216和232-1之間,選用SDS_TYPE_32類型的header。 長度大於232的,選用SDS_TYPE_64類型的header。能表示的最大長度為264-1。 註:sdsReqType的實現代碼,直到3.2.0,它在長度邊界值上都一直存在問題,直到最近3.2 branch上的commit 6032340才修複。 sds的創建和銷毀 sds sdsnewlen(const void *init, size_t initlen) { void *sh; sds s; char type = sdsReqType(initlen); /* Empty strings are usually created in order to append. Use type 8 * since type 5 is not good at this. */ if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8; int hdrlen = sdsHdrSize(type); unsigned char *fp; /* flags pointer. */ sh = s_malloc(hdrlen+initlen+1); if (!init) memset(sh, 0, hdrlen+initlen+1); if (sh == NULL) return NULL; s = (char*)sh+hdrlen; fp = ((unsigned char*)s)-1; switch(type) { case SDS_TYPE_5: { *fp = type | (initlen << SDS_TYPE_BITS); break; } case SDS_TYPE_8: { SDS_HDR_VAR(8,s); sh->len = initlen; sh->alloc = initlen; *fp = type; break; } case SDS_TYPE_16: { SDS_HDR_VAR(16,s); sh->len = initlen; sh->alloc = initlen; *fp = type; break; } case SDS_TYPE_32: { SDS_HDR_VAR(32,s); sh->len = initlen; sh->alloc = initlen; *fp = type; break; } case SDS_TYPE_64: { SDS_HDR_VAR(64,s); sh->len = initlen; sh->alloc = initlen; *fp = type; break; } } if (initlen && init) memcpy(s, init, initlen); s[initlen] = '\0'; return s; } sds sdsempty(void) { return sdsnewlen("",0); } sds sdsnew(const char *init) { size_t initlen = (init == NULL) ? 0 : strlen(init); return sdsnewlen(init, initlen); } void sdsfree(sds s) { if (s == NULL) return; s_free((char*)s-sdsHdrSize(s[-1])); } sdsnewlen創建一個長度為initlen的sds字元串,並使用init指向的字元數組(任意二進位數據)來初始化數據。如果init為NULL,那麼使用全0來初始化數據。它的實現中,我們需要註意的是: 如果要創建一個長度為0的空字元串,那麼不使用SDS_TYPE_5類型的header,而是轉而使用SDS_TYPE_8類型的header。這是因為創建的空字元串一般接下來的操作很可能是追加數據,但SDS_TYPE_5類型的sds字元串不適合追加數據(會引發記憶體重新分配)。 需要的記憶體空間一次性進行分配,其中包含三部分:header、數據、最後的多餘位元組(hdrlen+initlen+1)。 初始化的sds字元串數據最後會追加一個NULL結束符(s[initlen] = ‘\0’)。 關於sdsfree,需要註意的是:記憶體要整體釋放,所以要先計算出header起始指針,把它傳給s_free函數。這個指針也正是在sdsnewlen中調用s_malloc返回的那個地址。 sds的連接(追加)操作 sds sdscatlen(sds s, const void *t, size_t len) { size_t curlen = sdslen(s); s = sdsMakeRoomFor(s,len); if (s == NULL) return NULL; memcpy(s+curlen, t, len); sdssetlen(s, curlen+len); s[curlen+len] = '\0'; return s; } sds sdscat(sds s, const char *t) { return sdscatlen(s, t, strlen(t)); } sds sdscatsds(sds s, const sds t) { return sdscatlen(s, t, sdslen(t)); } sds sdsMakeRoomFor(sds s, size_t addlen) { void *sh, *newsh; size_t avail = sdsavail(s); size_t len, newlen; char type, oldtype = s[-1] & SDS_TYPE_MASK; int hdrlen; /* Return ASAP if there is enough space left. */ if (avail >= addlen) return s; len = sdslen(s); sh = (char*)s-sdsHdrSize(oldtype); newlen = (len+addlen); if (newlen < SDS_MAX_PREALLOC) newlen *= 2; else newlen += SDS_MAX_PREALLOC; type = sdsReqType(newlen); /* Don't use type 5: the user is appending to the string and type 5 is * not able to remember empty space, so sdsMakeRoomFor() must be called * at every appending operation. */ if (type == SDS_TYPE_5) type = SDS_TYPE_8; hdrlen = sdsHdrSize(type); if (oldtype==type) { newsh = s_realloc(sh, hdrlen+newlen+1); if (newsh == NULL) return NULL; s = (char*)newsh+hdrlen; } else { /* Since the header size changes, need to move the string forward, * and can't use realloc */ newsh = s_malloc(hdrlen+newlen+1); if (newsh == NULL) return NULL; memcpy((char*)newsh+hdrlen, s, len+1); s_free(sh); s = (char*)newsh+hdrlen; s[-1] = type; sdssetlen(s, len); } sdssetalloc(s, newlen); return s; } sdscatlen將t指向的長度為len的任意二進位數據追加到sds字元串s的後面。本文開頭演示的string的append命令,內部就是調用sdscatlen來實現的。 在sdscatlen的實現中,先調用sdsMakeRoomFor來保證字元串s有足夠的空間來追加長度為len的數據。sdsMakeRoomFor可能會分配新的記憶體,也可能不會。 sdsMakeRoomFor是sds實現中很重要的一個函數。關於它的實現代碼,我們需要註意的是: 如果原來字元串中的空餘空間夠用(avail >= addlen),那麼它什麼也不做,直接返回。 如果需要分配空間,它會比實際請求的要多分配一些,以防備接下來繼續追加。它在字元串已經比較長的情況下要至少多分配SDS_MAX_PREALLOC個位元組,這個常量在sds.h中定義為(1024*1024)=1MB。 按分配後的空間大小,可能需要更換header類型(原來header的alloc欄位太短,表達不了增加後的容量)。 如果需要更換header,那麼整個字元串空間(包括header)都需要重新分配(s_malloc),並拷貝原來的數據到新的位置。 如果不需要更換header(原來的header夠用),那麼調用一個比較特殊的s_realloc,試圖在原來的地址上重新分配空間。s_realloc的具體實現得看Redis編譯的時候選用了哪個allocator(在Linux上預設使用jemalloc)。 但不管是哪個realloc的實現,它所表達的含義基本是相同的:它儘量在原來分配好的地址位置重新分配,如果原來的地址位置有足夠的空餘空間完成重新分配,那麼它返回的新地址與傳入的舊地址相同;否則,它分配新的地址塊,併進行數據搬遷。參見http://man.cx/realloc。 從sdscatlen的函數介面,我們可以看到一種使用模式:調用它的時候,傳入一個舊的sds變數,然後它返回一個新的sds變數。由於它的內部實現可能會造成地址變化,因此調用者在調用完之後,原來舊的變數就失效了,而都應該用新返回的變數來替換。不僅僅是sdscatlen函數,sds中的其它函數(比如sdscpy、sdstrim、sdsjoin等),還有Redis中其它一些能自動擴展記憶體的數據結構(如ziplist),也都是同樣的使用模式。 淺談sds與string的關係 現在我們回過頭來看看本文開頭給出的string操作的例子。 append操作使用sds的sdscatlen來實現。前面已經提到。 setbit和getrange都是先根據key取到整個sds字元串,然後再從字元串選取或修改指定的部分。由於sds就是一個字元數組,所以對它的某一部分進行操作似乎都比較簡單。 但是,string除了支持這些操作之外,當它存儲的值是個數字的時候,它還支持incr、decr等操作。那麼,當string存儲數字值的時候,它的內部存儲還是sds嗎? 實際上,不是了。而且,這種情況下,setbit和getrange的實現也會有所不同。這些細節,我們放在下一篇介紹robj的時候再進行系統地討論。 什麼是ziplist Redis官方對於ziplist的定義是(出自ziplist.c的文件頭部註釋): The ziplist is a specially encoded dually linked list that is designed to be very memory efficient. It stores both strings and integer values, where integers are encoded as actual integers instead of a series of characters. It allows push and pop operations on either side of the list in O(1) time. 翻譯一下就是說:ziplist是一個經過特殊編碼的雙向鏈表,它的設計目標就是為了提高存儲效率。ziplist可以用於存儲字元串或整數,其中整數是按真正的二進位表示進行編碼的,而不是編碼成字元串序列。它能以O(1)的時間複雜度在表的兩端提供push和pop操作。 實際上,ziplist充分體現了Redis對於存儲效率的追求。一個普通的雙向鏈表,鏈表中每一項都占用獨立的一塊記憶體,各項之間用地址指針(或引用)連接起來。這種方式會帶來大量的記憶體碎片,而且地址指針也會占用額外的記憶體。而ziplist卻是將表中每一項存放在前後連續的地址空間內,一個ziplist整體占用一大塊記憶體。它是一個表(list),但其實不是一個鏈表(linked list)。 另外,ziplist為了在細節上節省記憶體,對於值的存儲採用了變長的編碼方式,大概意思是說,對於大的整數,就多用一些位元組來存儲,而對於小的整數,就少用一些位元組來存儲。我們接下來很快就會討論到這些實現細節。 ziplist的數據結構定義 ziplist的數據結構組成是本文要討論的重點。實際上,ziplist還是稍微有點複雜的,它複雜的地方就在於它的數據結構定義。一旦理解了數據結構,它的一些操作也就比較容易理解了。 我們接下來先從總體上介紹一下ziplist的數據結構定義,然後舉一個實際的例子,通過例子來解釋ziplist的構成。如果你看懂了這一部分,本文的任務就算完成了一大半了。 從巨集觀上看,ziplist的記憶體結構如下: <zlbytes><zltail><zllen><entry>...<entry><zlend> 各個部分在記憶體上是前後相鄰的,它們分別的含義如下: <zlbytes>: 32bit,表示ziplist占用的位元組總數(也包括<zlbytes>本身占用的4個位元組)。 <zltail>: 32bit,表示ziplist表中最後一項(entry)在ziplist中的偏移位元組數。<zltail>的存在,使得我們可以很方便地找到最後一項(不用遍歷整個ziplist),從而可以在ziplist尾端快速地執行push或pop操作。 <zllen>: 16bit, 表示ziplist中數據項(entry)的個數。zllen欄位因為只有16bit,所以可以表達的最大值為216-1。這裡需要特別註意的是,如果ziplist中數據項個數超過了16bit能表達的最大值,ziplist仍然可以來表示。那怎麼表示呢?這裡做了這樣的規定:如果`<zllen>`小於等於216-2(也就是不等於2^16-1),那麼<zllen>就表示ziplist中數據項的個數;否則,也就是<zllen>等於16bit全為1的情況,那麼<zllen>就不表示數據項個數了,這時候要想知道ziplist中數據項總數,那麼必須對ziplist從頭到尾遍歷各個數據項,才能計數出來。 <entry>: 表示真正存放數據的數據項,長度不定。一個數據項(entry)也有它自己的內部結構,這個稍後再解釋。 <zlend>: ziplist最後1個位元組,是一個結束標記,值固定等於255。 上面的定義中還值得註意的一點是:<zlbytes>, <zltail>, <zllen>既然占據多個位元組,那麼在存儲的時候就有大端(big endian)和小端(little endian)的區別。ziplist採取的是小端模式來存儲,這在下麵我們介紹具體例子的時候還會再詳細解釋。 我們再來看一下每一個數據項<entry>的構成: <prevrawlen><len><data> 我們看到在真正的數據(<data>)前面,還有兩個欄位: <prevrawlen>: 表示前一個數據項占用的總位元組數。這個欄位的用處是為了讓ziplist能夠從後向前遍歷(從後一項的位置,只需向前偏移prevrawlen個位元組,就找到了前一項)。這個欄位採用變長編碼。 <len>: 表示當前數據項的數據長度(即<data>部分的長度)。也採用變長編碼。 那麼<prevrawlen>和<len>是怎麼進行變長編碼的呢?各位讀者打起精神了,我們終於講到了ziplist的定義中最繁瑣的地方了。 先說<prevrawlen>。它有兩種可能,或者是1個位元組,或者是5個位元組: 如果前一個數據項占用位元組數小於254,那麼<prevrawlen>就只用一個位元組來表示,這個位元組的值就是前一個數據項的占用位元組數。 如果前一個數據項占用位元組數大於等於254,那麼<prevrawlen>就用5個位元組來表示,其中第1個位元組的值是254(作為這種情況的一個標記),而後面4個位元組組成一個整型值,來真正存儲前一個數據項的占用位元組數。 有人會問了,為什麼沒有255的情況呢? 這是因為:255已經定義為ziplist結束標記<zlend>的值了。在ziplist的很多操作的實現中,都會根據數據項的第1個位元組是不是255來判斷當前是不是到達ziplist的結尾了,因此一個正常的數據的第1個位元組(也就是<prevrawlen>的第1個位元組)是不能夠取255這個值的,否則就衝突了。 而<len>欄位就更加複雜了,它根據第1個位元組的不同,總共分為9種情況(下麵的表示法是按二進位表示): |00pppppp| - 1 byte。第1個位元組最高兩個bit是00,那麼<len>欄位只有1個位元組,剩餘的6個bit用來表示長度值,最高可以表示63 (2^6-1)。 |01pppppp|qqqqqqqq| - 2 bytes。第1個位元組最高兩個bit是01,那麼<len>欄位占2個位元組,總共有14個bit用來表示長度值,最高可以表示16383 (2^14-1)。 |10__|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| - 5 bytes。第1個位元組最高兩個bit是10,那麼len欄位占5個位元組,總共使用32個bit來表示長度值(6個bit捨棄不用),最高可以表示2^32-1。需要註意的是:在前三種情況下,<data>都是按字元串來存儲的;從下麵第4種情況開始,<data>開始變為按整數來存儲了。 |11000000| - 1 byte。<len>欄位占用1個位元組,值為0xC0,後面的數據<data>存儲為2個位元組的int16_t類型。 |11010000| - 1 byte。<len>欄位占用1個位元組,值為0xD0,後面的數據<data>存儲為4個位元組的int32_t類型。 |11100000| - 1 byte。<len>欄位占用1個位元組,值為0xE0,後面的數據<data>存儲為8個位元組的int64_t類型。 |11110000| - 1 byte。<len>欄位占用1個位元組,值為0xF0,後面的數據<data>存儲為3個位元組長的整數。 |11111110| - 1 byte。<len>欄位占用1個位元組,值為0xFE,後面的數據<data>存儲為1個位元組的整數。 |1111xxxx| - - (xxxx的值在0001和1101之間)。這是一種特殊情況,xxxx從1到13一共13個值,這時就用這13個值來表示真正的數據。註意,這裡是表示真正的數據,而不是數據長度了。也就是說,在這種情況下,後面不再需要一個單獨的<data>欄位來表示真正的數據了,而是<len>和<data>合二為一了。另外,由於xxxx只能取0001和1101這13個值了(其它可能的值和其它情況衝突了,比如0000和1110分別同前面第7種第8種情況衝突,1111跟結束標記衝突),而小數值應該從0開始,因此這13個值分別表示0到12,即xxxx的值減去1才是它所要表示的那個整數數據的值。 好了,ziplist的數據結構定義,我們介紹完了,現在我們看一個具體的例子。 上圖是一份真實的ziplist數據。我們逐項解讀一下: 這個ziplist一共包含33個位元組。位元組編號從byte[0]到byte[32]。圖中每個位元組的值使用16進位表示。 頭4個位元組(0x21000000)是按小端(little endian)模式存儲的<zlbytes>欄位。什麼是小端呢?就是指數據的低位元組保存在記憶體的低地址中(參見維基百科詞條Endianness)。因此,這裡<zlbytes>的值應該解析成0x00000021,用十進位表示正好就是33。 接下來4個位元組(byte[4..7])是<zltail>,用小端存儲模式來解釋,它的值是0x0000001D(值為29),表示最後一個數據項在byte[29]的位置(那個數據項為0x05FE14)。 再接下來2個位元組(byte[8..9]),值為0x0004,表示這個ziplist里一共存有4項數據。 接下來6個位元組(byte[10..15])是第1個數據項。其中,prevrawlen=0,因為它前面沒有數據項;len=4,相當於前面定義的9種情況中的第1種,表示後面4個位元組按字元串存儲數據,數據的值為”name”。 接下來8個位元組(byte[16..23])是第2個數據項,與前面數據項存儲格式類似,存儲1個字元串”tielei”。 接下來5個位元組(byte[24..28])是第3個數據項,與前面數據項存儲格式類似,存儲1個字元串”age”。 接下來3個位元組(byte[29..31])是最後一個數據項,它的格式與前面的數據項存儲格式不太一樣。其中,第1個位元組prevrawlen=5,表示前一個數據項占用5個位元組;第2個位元組=FE,相當於前面定義的9種情況中的第8種,所以後面還有1個位元組用來表示真正的數據,並且以整數表示。它的值是20(0x14)。 最後1個位元組(byte[32])表示<zlend>,是固定的值255(0xFF)。 總結一下,這個ziplist里存了4個數據項,分別為: 字元串: “name” 字元串: “tielei” 字元串: “age” 整數: 20 (好吧,被你發現了~~tielei實際上當然不是20歲,他哪有那麼年輕啊……) 實際上,這個ziplist是通過兩個hset命令創建出來的。這個我們後半部分會再提到。 好了,既然你已經閱讀到這裡了,說明你還是很有耐心的(其實我寫到這裡也已經累得不行了)。可以先把本文收藏,休息一下,回頭再看後半部分。 接下來我要貼一些代碼了。 ziplist的介面 我們先不著急看實現,先來挑幾個ziplist的重要的介面,看看它們長什麼樣子: unsigned char *ziplistNew(void); unsigned char *ziplistMerge(unsigned char **first, unsigned char **second); unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where); unsigned char *ziplistIndex(unsigned char *zl, int index); unsigned char *ziplistNext(unsigned char *zl, unsigned char *p); unsigned char *ziplistPrev(unsigned char *zl, unsigned char *p); unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen); unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p); unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int vlen, unsigned int skip); unsigned int ziplistLen(unsigned char *zl); 我們從這些介面的名字就可以粗略猜出它們的功能,下麵簡單解釋一下: ziplist的數據類型,沒有用自定義的struct之類的來表達,而就是簡單的unsigned char *。這是因為ziplist本質上就是一塊連續記憶體,內部組成結構又是一個高度動態的設計(變長編碼),也沒法用一個固定的數據結構來表達。 ziplistNew: 創建一個空的ziplist(只包含<zlbytes><zltail><zllen><zlend>)。 ziplistMerge: 將兩個ziplist合併成一個新的ziplist。 ziplistPush: 在ziplist的頭部或尾端插入一段數據(產生一個新的數據項)。註意一下這個介面的返回值,是一個新的ziplist。調用方必須用這裡返回的新的ziplist,替換之前傳進來的舊的ziplist變數,而經過這個函數處理之後,原來舊的ziplist變數就失效了。為什麼一個簡單的插入操作會導致產生一個新的ziplist呢?這是因為ziplist是一塊連續空間,對它的追加操作,會引發記憶體的realloc,因此ziplist的記憶體位置可能會發生變化。實際上,我們在之前介紹sds的文章中提到過類似這種介面使用模式(參見sdscatlen函數的說明)。 ziplistIndex: 返回index參數指定的數據項的記憶體位置。index可以是負數,表示從尾端向前進行索引。 ziplistNext和ziplistPrev分別返回一個ziplist中指定數據項p的後一項和前一項。 ziplistInsert: 在ziplist的任意數據項前面插入一個新的數據項。 ziplistDelete: 刪除指定的數據項。 ziplistFind: 查找給定的數據(由vstr和vlen指定)。註意它有一個skip參數,表示查找的時候每次比較之間要跳過幾個數據項。為什麼會有這麼一個參數呢?其實這個參數的主要用途是當用ziplist表示hash結構的時候,是按照一個field,一個value來依次存入ziplist的。也就是說,偶數索引的數據項存field,奇數索引的數據項存value。當按照field的值進行查找的時候,就需要把奇數項跳過去。 ziplistLen: 計算ziplist的長度(即包含數據項的個數)。 ziplist的插入邏輯解析 ziplist的相關介面的具體實現,還是有些複雜的,限於篇幅的原因,我們這裡只結合代碼來講解插入的邏輯。插入是很有代表性的操作,通過這部分來一窺ziplist內部的實現,其它部分的實現我們也就會很容易理解了。 ziplistPush和ziplistInsert都是插入,只是對於插入位置的限定不同。它們在內部實現都依賴一個名為__ziplistInsert的內部函數,其代碼如下(出自ziplist.c): static unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) { size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen; unsigned int prevlensize, prevlen = 0; size_t offset; int nextdiff = 0; unsigned char encoding = 0; long long value = 123456789; /* initialized to avoid warning. Using a value that is easy to see if for some reason we use it uninitialized. */ zlentry tail; /* Find out prevlen for the entry that is inserted. */ if (p[0] != ZIP_END) { ZIP_DECODE_PREVLEN(p, prevlensize, prevlen); } else { unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl); if (ptail[0] != ZIP_END) { prevlen = zipRawEntryLength(ptail); } } /* See if the entry can be encoded */ if (zipTryEncoding(s,slen,&value,&encoding)) { /* 'encoding' is set to the appropriate integer encoding */ reqlen = zipIntSize(encoding); } else { /* 'encoding' is untouched, however zipEncodeLength will use the * string length to figure out how to encode it. */ reqlen = slen; } /* We need space for both the length of the previous entry and * the length of the payload. */ reqlen += zipPrevEncodeLength(NULL,prevlen); reqlen += zipEncodeLength(NULL,encoding,slen); /* When the insert position is not equal to the tail, we need to * make sure that the next entry can hold this entry's length in * its prevlen field. */ nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0; /* Store offset because a realloc may change the address of zl. */ offset = p-zl; zl = ziplistResize(zl,curlen+reqlen+nextdiff); p = zl+offset; /* Apply memory move when necessary and update tail offset. */ if (p[0] != ZIP_END) { /* Subtract one because of the ZIP_END bytes */ memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff); /* Encode this entry's raw length in the next entry. */ zipPrevEncodeLength(p+reqlen,reqlen); /* Update offset for tail */ ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen); /* When the tail contains more than one entry, we need to take * "nextdiff" in account as well. Otherwise, a change in the * size of prevlen doesn't have an effect on the *tail* offset. */ zipEntry(p+reqlen, &tail); if (p[reqlen+tail.headersize+tail.len] != ZIP_END) { ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff); } } else { /* This element will be the new tail. */ ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl); } /* When nextdiff != 0, the raw length of the next entry has changed, so * we need to cascade the update throughout the ziplist */ if (nextdiff != 0) { offset = p-zl; zl = __ziplistCascadeUpdate(zl,p+reqlen); p = zl+offset; } /* Write the entry */ p += zipPrevEncodeLength(p,prevlen); p += zipEncodeLength(p,encoding,slen); if (ZIP_IS_STR(encoding)) { memcpy(p,s,slen); } else { zipSaveInteger(p,value,encoding); } ZIPLIST_INCR_LENGTH(zl,1); return zl; } 我們來簡單解析一下這段代碼: 這個函數是在指定的位置p插入一段新的數據,待插入數據的地址指針是s,長度為slen。插入後形成一個新的數據項,占據原來p的配置,原來位於p位置的數據項以及後面的所有數據項,需要統一向後移動,給新插入的數據項留出空間。參數p指向的是ziplist中某一個數據項的起始位置,或者在向尾端插入的時候,它指向ziplist的結束標記<zlend>。 函數開始先計算出待插入位置前一個數據項的長度prevlen。這個長度要存入新插入的數據項的<prevrawlen>欄位。 然後計算當前數據項占用的總位元組數reqlen,它包含三部分:<prevrawlen>, <len>和真正的數據。其中的數據部分會通過調用zipTryEncoding先來嘗試轉成整數。 由於插入導致的ziplist對於記憶體的新增需求,除了待插入數據項占用的reqlen之外,還要考慮原來p位置的數據項(現在要排在待插入數據項之後)的<prevrawlen>欄位的變化。本來它保存的是前一項的總長度,現在變成了保存當前插入的數據項的總長度。這樣它的<prevrawlen>欄位本身需要的存儲空間也可能發生變化,這個變化可能是變大也可能是變小。這個變化了多少的值nextdiff,是調用zipPrevLenByteDiff計算出來的。如果變大了,nextdiff是正值,否則是負值。 現在很容易算出來插入後新的ziplist需要多少位元組了,然後調用ziplistResize來重新調整大小。ziplistResize的實現里會調用allocator的zrealloc,它有可能會造成數據拷貝。 現在額外的空間有了,接下來就是將原來p位置的數據項以及後面的所有數據都向後挪動,併為它設置新的<prevrawlen>欄位。此外,還可能需要調整ziplist的<zltail>欄位。 最後,組裝新的待插入數據項,放在位置p。 hash與ziplist hash是Redis中可以用來存儲一個對象結構的比較理想的數據類型。一個對象的各個屬性,正好對應一個hash結構的各個field。 我們在網上很容易找到這樣一些技術文章,它們會說存儲一個對象,使用hash比string要節省記憶體。實際上這麼說是有前提的,具體取決於對象怎麼來存儲。如果你把對象的多個屬性存儲到多個key上(各個屬性值存成string),當然占的記憶體要多。但如果你採用一些序列化方法,比如Protocol Buffers,或者Apache Thrift,先把對象序列化為位元組數組,然後再存入到Redis的string中,那麼跟hash相比,哪一種更省記憶體,就不一定了。 當然,hash比序列化後再存入string的方式,在支持的操作命令上,還是有優勢的:它既支持多個field同時存取(hmset/hmget),也支持按照某個特定的field單獨存取(hset/hget)。 實際上,ha