Redis高可用高性能緩存的應用系列 - 資料類型以及底層結構和原理

概述

介紹redis緩存原理與設計執行流程，單線程的處理方式是高效的原因，以及redis資料類型以及底層結構和原理進行說明，這對我們使用Redis有很大幫助。

底層運作實作模型

用戶端的請求先進行linux運作核心，而redis和核心之間用了epoll非阻塞I/O多路複用的方式來處理,請求是I/O操作會有序的存入在epoll的待處理隊列中，Redis的是記憶體操作，記憶體運作的速度要遠遠高于I/O操作的，Redis是單線程的處理方式是高效的，Redis會順序的一筆一筆的處理在epoll的待處理隊列中的請求。

所謂Redis單線程是用于計算的worker線程，redis還會有其他的線程，比如持久化，異步删除等等。

Redis基本結構

Redis核心結構隻要有redisServer和redisObject組成，在Redis初始化的時候，先初始化RedisServer結構，通過dict映射dictEntry，把具體的類型和值存入redisObject進行統一管理，如果有不了解的地方，可以看redis設計與實作一書。

redisServer

1.下面是redisServer的結構體初始化，在檔案server.h中。

struct redisServer {
    /* General */
    pid_t pid;                  /* Main process pid. */
    pthread_t main_thread_id;         /* Main thread id */
    char *configfile;    /* Absolute config file path, or NULL */
    
    //...
    redisDb *db;
    dict *commands;             /* Command table */
    dict *orig_commands;        /* Command table before command renaming. */
    aeEventLoop *el;
    // ...
}
複制代碼           

redisDb *db ：儲存了資料庫的資訊，初始化預設16個資料庫，通過參數``可以修改， dict是redisDb中最核心的結構體，dict中儲存了所有的鍵值對，稱為鍵空間。

對dict的了解很重要，Redis的對象相當于大的dict結構體對象，所有的類型結構實作的都是以dict做前提的。

typedef struct redisDb {
    dict *dict;                
    dict *expires;              
    dict *blocking_keys;       
    dict *blocking_keys_unblock_on_nokey;  
    dict *ready_keys;           
    dict *watched_keys; 
    // ...
} redisDb;
複制代碼           

下面在看dict結構，它做了2個字典做漸進式Hash，資料組儲存的是具體的dictEntry。

struct dict {
    dictType *type;
    dictEntry **ht_table[2];
    unsigned long ht_used[2];
    long rehashidx; 
    int16_t pauserehash; 
    signed char ht_size_exp[2];
    void *metadata[];           
};

struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;    
    void *metadata[];
};
複制代碼           

dictEntry *next ，當Hash的值一樣時就形成一個連結清單，指向下一個dictEntry，再dictEntry結構體中，key儲存實際的key值，val指向的是redisObject結構。

redisObject

下面詳細介紹一下redisObject類型和結構體中主要的功能：

• type: 對外的資料類型，string、hash、list、set 、zset，通過type指令看到的類型。
• encoding：内部實際儲存的資料類型，具體選擇時通過配置檔案對應參數實作的，例如list 按照存入的值分為ziplist和quicklist。
• lru：管理緩存淘汰機制
• refcount：引用計數，主要用于記憶體回收使用
• ptr：存儲真實資料的實體指針位址

struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; 
    int refcount;
    void *ptr;
};
複制代碼           

Redis資料結構

String

Redis的底層實作沒有實作C語言的字元串，而是自己簡單封裝了一層動态字元串Sds,Sds内部又可以轉為int、embstr、raw。

127.0.0.1:6379> set number 100
OK
127.0.0.1:6379> object encoding number
"int"

127.0.0.1:6379> set name stark張宇
OK
127.0.0.1:6379> object encoding name
"embstr"

127.0.0.1:6379> set logstr “stark張宇關于Redisraw類型編碼的示範，他需要超過44位元組”
OK
127.0.0.1:6379> object encoding logstr
"raw"
複制代碼           

Sds内部的裝換取決于存儲值的位元組大小，值為int的直接存儲成int，小于等于44位元組的存儲成embstr類型，大于44位元組的存儲成raw類型。

embstr與raw存儲上的差別：embstr存儲在一塊連續上的記憶體，讀取一次就可以，raw存儲的是不連續的記憶體，需要讀取2次記憶體。

Redis為什麼這麼設計Sds結構體存儲字元串?

1.效率:變量中經常會用到字元串長度len，如果使用C語言的字元長度時，需要對整個字元串進行周遊，它的時間複雜度O(n),在Sds中的len，時間複雜度O(1),在高并發場景下，頻繁周遊字元串，會造成性能瓶頸。

2.防止資料溢出：C語言的字元串因為沒有 記錄自身長度，另外Sds再儲存二進制是安全的，友善value值修改時修改存儲空間。

3.記憶體空間的預配置設定：當修改字元串記憶體空間時，不僅會修改字元串存儲空間，還會額外預留白間，下次修改的時候就會先檢查未使用的記憶體空間。

4.惰性空間釋放：當當修改字元串記憶體空間變小時，不會立即回收記憶體空間，防止再次修改。

配置設定記憶體空間規則：當值小于1M時，就會配置設定相同的空間，當大于1M時就會配置設定1M的空間。

Hash

Redis的Hash的底層是一個dict，當資料量比較小或者資料值比較小時會采用ziplist,資料大的時候采用hashtable的結構來存儲資料。

127.0.0.1:6379> hgetall user1
1) "name"
2) "stark"
3) "age"
4) "33"
5) "sex"
6) "1"
127.0.0.1:6379> object encoding user1
"ziplist"

127.0.0.1:6379> hset user1 mark "stark張宇關于HashTable類型編碼的示範，值很大他就變成了HashTable"
(integer) 1
127.0.0.1:6379> object encoding user1
"hashtable"
複制代碼           

ziplist

ziplist結構的組成部分詳解：

• zlbytes: 32位無符号整型，表示整個ziplist所占的空間大小，包含了zlbytes所占的4個位元組。這個字段可以在重置整個ziplist大小時不需要周遊整個list來确定大小,空間換時間。
• zltail:32位無符号整型，表示整個list中最後一項所在的偏移量，友善再尾部做pop操作。
• zllen:16位，表示ziplist中所存儲的entry數量。
• entry：不定長，可能有多個。
• zlend:8位，ziplist的末尾表示，其固定值是255。

entry由3部分組成，前一個entry的大小，目前編碼類型和長度，真實的字元串和數字。

ziplist優缺點: 優點：因為是連續記憶體空間，是以使用率高，通路效率高。 缺點：更新效率低，當插入和删除一個元素時，會頻繁的進行記憶體的擴充和縮小，資料的搬移效率低。

list

Redis的list的有序資料結構，底層分為ziplist和quicklist。

ziplist在Hash類型裡已經說了，在這裡不做多餘的叙述了。

quicklist結構的優缺點：

優點：因為是雙向連結清單，更新效率比較高，在插入和删除操作時非常友善，複雜度O(n),前後元素的複雜度是O(1)。 缺點:增加了記憶體的開銷。

Set

Redis裡面的Set是無序的，自動去重的資料類型，它的底層是一個dict，當資料用整型并且資料元素小于配置檔案中set-max-intest-entries,否則用dict。

127.0.0.1:6379> sadd gather 100 200 300
(integer) 3
127.0.0.1:6379> object encoding gather
"intset"
127.0.0.1:6379> sadd gather stark
(integer) 1
127.0.0.1:6379> object encoding gather
"hashtable"
複制代碼           

Zset

Redis的Zset是有序的，自動去重的資料類型，底層是由字典Dict和跳表Skiplist實作的，資料較少時使用Ziplist結構來存儲。

Ziplist可以在配置檔案中通過zset-max-ziplist-entries和zset-max-ziplist-value來配置。

常見問題：Redis的Zset為什麼不使用紅黑樹和二叉樹，而要選擇跳表呢？

1)紅黑樹和二叉樹的範圍查找不是很好，有序集合很大的場景是進行範圍查找的，範圍查找在跳表上是非常友善的，因為它是一個連結清單，紅黑樹和二叉樹的範圍查找相對來說就複雜的多。2)跳表的實作要比紅黑樹簡單很多了。

作者：stark張宇

連結：https://juejin.cn/post/7217360688264200249