[TOC] ## 概述 redis有7中基礎類型，字符串string、列表list、哈希表hash、集合set、有序集合zset、stream、GEO。我著重記錄前面五個類型的數據，并給出對應的redis源碼的數據結構。 對應的五個處理文件，斷點調試的文件： t_string.c 、 t_list.c、t_hash.c、 t_set.c、t_zset.c、t_stream ## 字符串string ### 字符串的使用方式 設置鍵值對 ``` set k v get k ``` redis服務接收到設置鍵值對的指令的流程 * 嘗試對值對象進行編碼 * 設置鍵值對，存儲到字典的哈希表的一個節點中 * 通知給redis客戶端 ### 字符串編碼 Redis為了將內存的使用率做到極致，針對字符串對象，提供了三種數據結構 ```cpp #define REDIS_ENCODING_RAW 0 /* Raw representation */ #define REDIS_ENCODING_INT 1 /* Encoded as integer */ #define REDIS_ENCODING_EMBSTR 8 /* Embedded sds string encoding */ ``` 1. `REDIS_ENCODING_INT`類型的數據編碼流程 * 只對長度小于或等于 21 字節，并且可以被解釋為整數的字符串進行編碼, 如果值小于1000，則被存儲到共享對象中，引用計數+1，通過復用來減少內存碎片，以及減少操作耗時的共享對象。 * 如果編碼類型為`REDIS_ENCODING_RAW`, 則銷毀掉原來的內存，把編碼改為`REDIS_ENCODING_INT`，并重新賦值，代碼如下： ```cpp if (len <= 21 && string2l(s,len,&value)) { if (server.maxmemory == 0 && value >= 0 && value < REDIS_SHARED_INTEGERS) { decrRefCount(o); //銷毀原來的內存 incrRefCount(shared.integers[value]);// 引用計數+1 return shared.integers[value]; //使用共享內存 } else { if (o->encoding == REDIS_ENCODING_RAW) sdsfree(o->ptr); //銷毀原來的內存 o->encoding = REDIS_ENCODING_INT;//修改編碼狀態 o->ptr = (void*) value; return o; } } ``` 2.針對`REDIS_ENCODING_RAW`的編碼方式，redis的處理是嘗試從 SDS 中移除所有空余空間 * raw 編碼會調用兩次內存分配函數來分別創建 redisObject 結構和 sdshdr 結構,而 embstr 編碼則通過調用一次內存分配函數來分配一塊連續的空間， 空間中依次包含 redisObject 和 sdshdr 兩個結構 3. 當字符串長度小于`44`，則使用`REDIS_ENCODING_EMBSTR`的編碼方式 ``` #define REDIS_ENCODING_EMBSTR_SIZE_LIMIT 44 ``` *embstr類型是如何存放字符串的【重點】* 我們知道一般cpu從內存中讀取數據會先讀取到 cache line（緩存行）， 一個緩存行基本占64個字節，其中redisObject最少占16個字節（根據屬性的類型計算得出），所以如果要讀取一個 redisObject，會發現只讀取了16個字節，剩下的48個字節的空間相當于浪費，所以為了提高性能（主要減少了內存讀取的次數），所以再RedisObject空間后又開辟48個字節的連續空間，將ptr指向的值存入其中，注意此處存入的是字符串類型，48個字節對應的是sdshdr8存儲結構。而 sdshdr8 在不存入數據的情況下，最少要 4 個字節（其中一個字節是字符串尾部的'\\0'）,那么還剩余 44 個字節，所以如果在 44 個字節以內字符串就可以放在緩存行里面，從而減少了內存I/O次數 *embstr 編碼方式的優點*： * embstr 編碼將創建字符串對象所需的*內存分配次數從 raw 編碼的兩次降低為一次*。 * 釋放 embstr 編碼的字符串對象*只需要調用一次內存釋放函數*，而釋放 raw 編碼的字符串對象需要調用兩次內存釋放函數。 * 因為 embstr 編碼的字符串對象的所有數據都保存在一塊連續的內存里面，所以這種編碼的字符串對象比起 raw ，*編碼的字符串對象能夠更好地利用緩存帶來的優勢*。 ### 字符串在Redis中所使用的內部數據結構 在Redis中使用字典dict來存儲鍵值對。設置key的值 ``` void setKey(redisDb *db, robj *key, robj *val) ``` 添加或覆蓋數據庫中的鍵值對: ``` if (lookupKeyWrite(db,key) == NULL) { dbAdd(db,key,val); //添加 } else { dbOverwrite(db,key,val);//覆蓋 } ``` 可以看到底層鍵值對是存儲在字典里的哈希表里的一個節點中。 ## 列表list Redis列表是簡單的字符串列表，按照插入順序排序。你可以添加一個元素到列表的頭部（左邊）或者尾部（右邊）. 一個列表最多可以包含 2^32- 1 個元素 (4294967295, 每個列表超過40億個元素)。 使用方式： ``` >lpush k v ``` ### 查看列表list的使用流程 * redis服務收到客戶端的`lpush`指令 * 嘗試將字符串編碼，參考上面的字符串編碼 * 是否需要轉換編碼？指的是list的編碼，3.2版本以前編碼格式有兩種`REDIS_ENCODING_ZIPLIST`,`REDIS_ENCODING_LINKEDLIST`，3.2(包括3.2)版本之后升級為雙向鏈表quicklist ## hash列表 redis的哈希對象的底層存儲可以使用ziplist（壓縮列表）和hashtable。當hash對象可以同時滿足下面兩個條件時，哈希對象使用ziplist編碼。 * 哈希對象保存的所有鍵值對的鍵和值的字符串長度都小于64字節 * 哈希對象保存的鍵值對數量小于512個 ziplist的數據結構請看：[ziplist壓縮列表](ziplist.md). 判斷條件的代碼如下： ``` if (sdsEncodedObject(argv[i]) && sdslen(argv[i]->ptr) > server.hash_max_ziplist_value) { hashTypeConvert(o, OBJ_ENCODING_HT); break; } //server.hash_max_ziplist_value = 64 ``` ### hash存儲過程源碼分析 以`hset`命令為例進行分析，整個過程如下： * 首先查看hset中key對應的value是否存在，`hashTypeLookupWriteOrCreate`。 * 判斷`key`和`value`的長度確定是否需要從`zipList`到`hashtable`轉換，`hashTypeTryConversion`。 * 對`key/value`進行`string`層面的編碼，解決內存效率問題。 * `hashTypeSet`,判斷是否使用ziplist或hashtable * 更新`hash`節點中`key/value`問題。 * 其他后續操作的問題 ``` void hashTypeConvertZiplist(robj *o, int enc) { serverAssert(o->encoding == OBJ_ENCODING_ZIPLIST); if (enc == OBJ_ENCODING_ZIPLIST) { /* Nothing to do... */ } else if (enc == OBJ_ENCODING_HT) { hashTypeIterator *hi; dict *dict; int ret; hi = hashTypeInitIterator(o); dict = dictCreate(&hashDictType, NULL); //分配內存 while (hashTypeNext(hi) != C_ERR) { sds key, value; key = hashTypeCurrentObjectNewSds(hi,OBJ_HASH_KEY); //編碼key value = hashTypeCurrentObjectNewSds(hi,OBJ_HASH_VALUE);//編碼value ret = dictAdd(dict, key, value);//把key-value添加到字典里 if (ret != DICT_OK) { serverLogHexDump(LL_WARNING,"ziplist with dup elements dump", o->ptr,ziplistBlobLen(o->ptr)); serverPanic("Ziplist corruption detected"); } } hashTypeReleaseIterator(hi); zfree(o->ptr); //銷毀之前的內存 o->encoding = OBJ_ENCODING_HT; o->ptr = dict; //把新的hashtable賦值給ptr } else { serverPanic("Unknown hash encoding"); } } ``` ## set集合 Redis 的 Set 是 String 類型的無序集合。集合成員是唯一的，這就意味著集合中不能出現重復的數據。 Redis 中集合是通過哈希表實現的，所以添加，刪除，查找的復雜度都是 O(1)。 集合中最大的成員數為 232 - 1 (4294967295, 每個集合可存儲40多億個成員)。 ### set集合的底層數據 **Redis使用Dict和IntSet保存Set數據**。 * 當所有數據都是整數的時候使用`intset` * 否則就使用`dict`。 `intset.h`： ``` //inset 數據結構，在set數據量小且都是整型數據時使用 typedef struct intset { // 編碼范圍，由具體存儲值決定 uint32_t encoding; // 數組長度 uint32_t length; // 具體存儲元素的容器 int8_t contents[]; } intset; ``` ### set集合數據操作流程 以`sadd`操作為例子，分析流程 ``` redis-cli> sadd 11 20 3 ``` 收到客戶端的指令，進入函數 ``` void saddCommand(client *c) ``` 循環添加進入集合 ``` int setTypeAdd(robj *subject, sds value) ``` 判斷是否是整數類型數據, 使用`intset`存儲數據： ``` if (isSdsRepresentableAsLongLong(value,&llval) == C_OK) { ... subject->ptr = intsetAdd(subject->ptr,llval,&success); ... } ``` 如果有不是整數類型的數據，則轉化為`dict`數據類型 ``` setTypeConvert(subject,OBJ_ENCODING_HT); ``` ## zset有序集合 Redis 有序集合和集合一樣也是 string 類型元素的集合,且不允許重復的成員。 不同的是每個元素都會關聯一個 double 類型的分數。redis 正是通過分數來為集合中的成員進行從小到大的排序。 有序集合的成員是唯一的,但分數(score)卻可以重復。 集合是通過哈希表實現的，所以添加，刪除，查找的復雜度都是 O(1)。 集合中最大的成員數為 232 - 1 (4294967295, 每個集合可存儲40多億個成員)。 ### zset的底層數據結構 zset的底層數據使用`ziplist`和`zset` * 有序集合保存的元素數量小于128個 * 有序集合保存的所有元素的長度小于64字節 當滿足上述條件時，使用`ziplist`, 否則就使用`zset`。 server.h ``` typedef struct zskiplistNode { sds ele; double score; struct zskiplistNode *backward; struct zskiplistLevel { struct zskiplistNode *forward; unsigned long span; } level[]; } zskiplistNode; typedef struct zskiplist { struct zskiplistNode *header, *tail; unsigned long length; int level; } zskiplist; typedef struct zset { dict *dict; //方便查詢某一個key zskiplist *zsl; //方面范圍查詢 } zset; ``` ### zset添加數據流程 以`zadd`為例子 ``` redis> zadd t1 2 a 1 c 3 b ``` 收到客戶端數據，進入函數 ``` void zaddGenericCommand(client *c, int flags) ``` 判斷是否有該key ``` zobj = lookupKeyWrite(c->db,key) ``` 檢查是否是`OBJ_ZSET`數據類型： ``` if (checkType(c,zobj,OBJ_ZSET)) goto cleanup; ``` 如果所有元素的長度小于64字節，則使用`ziplist`編碼，否則使用`OBJ_ENCODING_SKIPLIST`. 遍歷元素，添加到集合中 ``` zsetAdd(zobj, score, ele, &retflags, &newscore); ``` 使用ziplist編碼的時候會判斷，"有序集合保存的元素數量小于128個，有序集合保存的所有元素的長度小于64字節", 不滿足上述條件則轉化為`OBJ_ENCODING_SKIPLIST`編碼 ``` if (zzlLength(zobj->ptr) > server.zset_max_ziplist_entries || sdslen(ele) > server.zset_max_ziplist_value) zsetConvert(zobj,OBJ_ENCODING_SKIPLIST); ``` 使用`OBJ_ENCODING_SKIPLIST`編碼,數據結構是`zset`，`zset`包含一個`dict`和一個`zskiplist`,`dict`用來查詢數據到分數(score)的對應關系，而`zskiplist`用來根據分數查詢數據（可能是范圍查找）。 ### **范圍操作命令** `zset`中有很多跟范圍相關的命令，大致可以歸納為以下三種： 1. 獲取或刪除指定排位區間內的元素，如zrange、zrevrange、zremrangebyrank命令。 2. 獲取或刪除指定分值區間內的元素，如zrangebyscore、zrevrangebyscore、zremrangebyscore命令。 3. 獲取或刪除指定字典序區間內的元素，如zrangebylex、zremrangebylex。對于這種情況，需要注意：只有當插入到有序集合（Sorted set）中的所有元素的分值score都相同時，使用zrangebylex或zremrangebylex命令可以認為存儲在有序集合中的元素是按字典序排序（Lexicographical ordering）的，然后返回或刪除元素值在最小值 min 及最大值 max 之間的所有元素。如果有序集合中的元素存在不同的分值，所返回或刪除的元素是不確定的。