眾所周知，redis是有名的哈希存儲，從而實現(xiàn)從鍵對值的快速訪問。它使用了一個哈希表來保存所有鍵值對。
redis值的基本數(shù)據(jù)類型包含五大類：String、List、Set、Sorted Set、Hash。除String外，其它4種類型因為value值都是一組集合，所以后4中類型也叫做集合類型。它們所對應(yīng)的底層數(shù)據(jù)結(jié)構(gòu)如下:
因為redis有多種數(shù)據(jù)類型，不同的數(shù)據(jù)類型有一些元數(shù)據(jù)需要記錄(如LRU,被引用次數(shù)等），所以redis會用一個redisObject對象來保存這些元數(shù)據(jù)，并用指針指向?qū)嶋H數(shù)據(jù)。redisObject的定義如下：(https://github.com/redis/redis/blob/unstable/src/server.h):
typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
* LFU data (least significant 8 bits frequency
* and most significant 16 bits access time). */
int refcount;
void *ptr;
} robj;
type表示對象的類型，占4個bit。string,list,hash等
encoding:對象的編碼類型，占4個bit。如string類型有int、raw、embstr三種編碼。
refcount:*記錄該對象被引用的次數(shù)，占用4字節(jié)。
ptr:指向具體數(shù)據(jù)的指針，占用8字節(jié)。
所以一個redisObjects的大小為16個字節(jié)。
綜合起來，redis的存儲結(jié)構(gòu)大概如下：
關(guān)于key存儲的是SDS還是redisObject,一定要注意。redis在開始時把key和value都轉(zhuǎn)成了redisObject。但在最后進行db存儲操作的時候，又只取出了redisObject對象中ptr所指向的SDS結(jié)構(gòu)體?？丛创a時看到db中的setKey之后沒細看，糾結(jié)了我好久。
好了，接下來就開始逐一了解一下這五種數(shù)據(jù)類型以及他們的數(shù)據(jù)結(jié)構(gòu)。首先是String。
-----------------------------------------String---------------------------------------
String就是我們經(jīng)常用到的典型的鍵-單值,例如：
127.0.0.1:6379> SET 'name' 'huan'
OK
String類型的數(shù)據(jù)，redis會用簡單動態(tài)字符串(Simple Daynamic String,SDS)結(jié)構(gòu)體來保存數(shù)據(jù)。
buffer： 字節(jié)數(shù)組，保存實際數(shù)據(jù)。為表示數(shù)據(jù)結(jié)束，會在最后加一個'\0'
Len： buffer的已用長度。會使用sdsReqType方法據(jù)長度的大小和系統(tǒng)選擇合適的字節(jié)數(shù)（1/2/4/8）。
Alloc： 實際的分配長度，會取離len最近的2的冪次方。一般會大于len。和len一樣根據(jù)長度的大小選擇合適的字節(jié)數(shù)。
flags： 標記字段，目前只使用了3bits
sdshdr8結(jié)構(gòu)體定義如下:
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[];
};
當(dāng)我們設(shè)置一個簡單的字符串鍵值對(<6bytes)，計算使用內(nèi)存為80bytes.
before_mem = get_memory_info()
r.set("key1","key1")
after_mem = get_memory_info()
print("used:{}".format(after_mem-before_mem))
#輸出
已使用的內(nèi)存為1109120B
已使用的內(nèi)存為1109200B
used:80
但如果key和value都是字符串形式的整型， 則只需要使用64bytes.
before_mem = get_memory_info()
r.set("1001","100202")
after_mem = get_memory_info()
print("used:{}".format(after_mem-before_mem))
#輸出
已使用的內(nèi)存為1109056B
已使用的內(nèi)存為1109120B
used:64
get_memory_info方法：
def get_memory_info()->(float,float):
info_mem = r.info(section='memory')
used_memory = info_mem['used_memory']
print("已使用的內(nèi)存為{}B".format(used_memory))
return used_memory
這是因為String有三種編碼方式int,embstr, raw，所對應(yīng)的底層存儲方式不同。
當(dāng)字符串為長整型時，直接將redisObject的指針ptr直接存儲為整型數(shù)據(jù)。
當(dāng)字符串小于等于44字節(jié)時，redisObject的指針ptr與它所指向的SDS結(jié)構(gòu)連續(xù)存儲。
當(dāng)字符串大于44字節(jié)時，SDS不再和redisObject連續(xù)存儲了，而是單獨地分配空間，通過ptr指針指向。
這樣做的目的是為了更好地利用內(nèi)存，減少內(nèi)存碎片。
-----------------------------------------Hash---------------------------------------
Hash類型包含key、filed、value三部分,如：
127.0.0.1:6379> hset website google google.cn
(integer) 0
127.0.0.1:6379> hget website google
"google.cn"
即一個key下面還有域的概念，一個key將對應(yīng)多組field:value。這樣對于一些具有相同前綴的key我們可以進行切割，把key的相同部分提取出來作為key,不同部分為field,既可以進行一個分類區(qū)分，又可以節(jié)省內(nèi)存空間。
Hash的底層結(jié)構(gòu)使用緊湊列表listpack(改進版的壓縮列表ziplist)和哈希表兩種方式進行存儲。
int hashTypeSet(robj *o, sds field, sds value, int flags) {
if (o->encoding == OBJ_ENCODING_LISTPACK) {
...
} else if (o->encoding == OBJ_ENCODING_HT){
...
}
Hash類型默認使用壓縮列表存儲，但它設(shè)置了用壓縮列表保存數(shù)據(jù)時的兩個閾值，如果超過了這兩個閾值，則使用哈希表保存數(shù)據(jù)。兩個閾值分別是：
hash-max-ziplist-entries:表示用壓縮列表保存時哈希集合中的最大元素個數(shù)
hash-max-ziplist-value:表示用壓縮列表保存時哈希集合中單個元素的最大長度。
我們可以在redis.conf中設(shè)置這兩個值，默認設(shè)置為：
hash-max-ziplist-entries 512
hash-max-ziplist-value 64
我們看一下內(nèi)存存儲情況
before = get_memory_info()
r.hset('website','baidu','baidu.com')
after = get_memory_info()
print(after-before)
before = get_memory_info()
r.hset('website','google','google.cn')
after = get_memory_info()
print(after-before)
#輸出
已使用的內(nèi)存為1090160B
已使用的內(nèi)存為1090288B
128 此時我的redis里面是沒有數(shù)據(jù)的，如果非空，此值為96
已使用的內(nèi)存為1090288B
已使用的內(nèi)存為1090304B
16
如果key不存在，需要分配dictEntry等，實際數(shù)據(jù)所占的內(nèi)存比比較小，而一旦key已存在，所使用的內(nèi)存就小了。那就看看壓縮列表是怎樣存儲以減少內(nèi)存的吧
壓縮列表
因為listpack是ziplist的改進版，我們就先從壓縮列表看起吧。壓縮列表的文檔相對詳細很多。我們可以看下他們兩個的entry的定義，基本一樣的：
/* Each entry in the ziplist is either a string or an integer. */
typedef struct {
/* When string is used, it is provided with the length (slen). */
unsigned char *sval;
unsigned int slen;
/* When integer is used, 'sval' is NULL, and lval holds the value. */
long long lval;
} ziplistEntry;
/* Each entry in the listpack is either a string or an integer. */
typedef struct {
/* When string is used, it is provided with the length (slen). */
unsigned char *sval;
uint32_t slen;
/* When integer is used, 'sval' is NULL, and lval holds the value. */
long long lval;
} listpackEntry;
zlbytes:4字節(jié)，指整個壓縮列表的長度
zltail:4字節(jié)，最后一個entry的偏移量。主要是用于pop的時候可以直接定位而不需要遍歷。（listpack沒有此字段）
zllen:2字節(jié)，entry的個數(shù)。當(dāng)超過2^16-2 個時，設(shè)置為2^16-1，此時需要遍歷才能知道有多少個。
zlend:ziplist的結(jié)束標志。0xFF。ziplist中其它字段都不會存在0xFF。
entry:
entry里面可以存字符串，可以存整型。主要包括以下幾部分:
prev_len:前一個數(shù)據(jù)的長度。當(dāng)長度小于254的時候，只需1個字節(jié)；當(dāng)長度大于等于254的時候，占5個字節(jié)，第一個字節(jié)設(shè)置為FE，后面4個字節(jié)表示長度。
encoding:2個bit。表示數(shù)據(jù)是字符串還是整型等，以及是多少長度的。如：
00|pppppp:表示長度小于或等于63(6bits)的字符串。后面6bits表示字符串長度
len數(shù)據(jù)的長度
結(jié)合源碼中給出的注釋例子：
* The following is a ziplist containing the two elements representing
* the strings "2" and "5". It is composed of 15 bytes, that we visually
* split into sections:
*
* [0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff]
* | | | | | |
* zlbytes zltail entries "2" "5" end
看完上面，為什么說ziplist節(jié)省空間呢？因為ziplist是按順序存儲數(shù)據(jù)的，相當(dāng)于數(shù)組。但是又不同于數(shù)據(jù)，數(shù)據(jù)只需要多大的空間，它存分配多少給存取，因為它有記錄長度的字段。而不像數(shù)組，它每一個數(shù)據(jù)都需要按數(shù)組的最大長度的數(shù)據(jù)分配空間。而它不能存儲過大的數(shù)據(jù)，也是因為它是順序存取，所以讀取的時候是要遍歷的，如果數(shù)據(jù)過多，就會影響其性能。當(dāng)其超過其閾值時，就要轉(zhuǎn)換成其它的數(shù)據(jù)結(jié)構(gòu)存儲了。
-----------------------------------------List---------------------------------------
示例
r.lpush('op','on')
r.lpush('op','off')
r.linsert('op','AFTER','on','color')
r.lrange('op',0,r.llen("op"))
許多地方都說列表的底層存儲結(jié)構(gòu)為壓縮列表或雙向鏈表。實際上，redis后面也做了優(yōu)化，用的是快速列表quicklist。根據(jù)它的描述可得知是一個listpack的鏈表。即綜合了壓縮列表和雙向鏈表。
#define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of listpacks */
整數(shù)數(shù)組的結(jié)構(gòu)定義如下：
typedef struct intset {
uint32_t encoding; #有16B/32B/64B
uint32_t length; #整型數(shù)組中數(shù)據(jù)的個數(shù)
int8_t contents[]; #一個柔性數(shù)組，用于存取具體的集合數(shù)據(jù)
} intset;
-----------------------------------------Set---------------------------------------
示例
SADD bbs "discuz.net"
Set集合的底層存儲結(jié)構(gòu)為整數(shù)數(shù)組和哈希表。在redis的配置中有一個參數(shù)可配置整型數(shù)組中元素的最大個數(shù)，默認為512。最大不能超過1G，即使配置超過1G了，代碼也會進行修正。當(dāng)超過最大個數(shù)時，就轉(zhuǎn)成哈希表存儲。
set-max-intset-entries 512
/* Convert to regular set when the intset contains
* too many entries. */
size_t max_entries = server.set_max_intset_entries;
/* limit to 1G entries due to intset internals. */
if (max_entries >= 1<<30) max_entries = 1<<30;
if (intsetLen(subject->ptr) > max_entries)
setTypeConvert(subject,OBJ_ENCODING_HT);
-----------------------------------------Sorted Set---------------------------------
sorted set 底層使用緊湊列表listpack和跳表skiplist兩種結(jié)構(gòu)保存數(shù)據(jù)。同時為了插入和刪除的時間復(fù)雜度為O(log(n))，它還使用哈希表保存數(shù)據(jù)。
ZSETs are ordered sets using two data structures to hold the same elements in order to get O(log(N)) INSERT and REMOVE operations into a sorted data structure.
The elements are added to a hash table mapping Redis objects to scores. At the same time the elements are added to a skip list mapping scores to Redis objects (so objects are sorted by scores in this "view").
typedef struct zset {
dict *dict;
zskiplist *zsl;
} zset;
它同樣有兩個配置選項控制是使用壓縮列表還是跳表
zset-max-ziplist-entries 128
zset-max-ziplist-value 64
zset-max-ziplist-entries: 壓縮列表中元素的最大個數(shù)
zset-max-ziplist-value：壓縮列表中單個元素的最大長度
