本文轉(zhuǎn)自互聯(lián)網(wǎng)

創(chuàng)新互聯(lián)是一家專(zhuān)業(yè)提供夏河企業(yè)網(wǎng)站建設(shè),專(zhuān)注與網(wǎng)站設(shè)計(jì)、成都網(wǎng)站制作、成都h5網(wǎng)站建設(shè)、小程序制作等業(yè)務(wù)。10年已為夏河眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專(zhuān)業(yè)網(wǎng)站設(shè)計(jì)公司優(yōu)惠進(jìn)行中。

本系列文章將整理到我在GitHub上的《Java面試指南》倉(cāng)庫(kù)，更多精彩內(nèi)容請(qǐng)到我的倉(cāng)庫(kù)里查看

https://github.com/h3pl/Java-Tutorial

喜歡的話(huà)麻煩點(diǎn)下Star哈

文章首發(fā)于我的個(gè)人博客：

www.how2playlife.com

本文是微信公眾號(hào)【Java技術(shù)江湖】的《探索redis設(shè)計(jì)與實(shí)現(xiàn)》其中一篇，本文部分內(nèi)容來(lái)源于網(wǎng)絡(luò)，為了把本文主題講得清晰透徹，也整合了很多我認(rèn)為不錯(cuò)的技術(shù)博客內(nèi)容，引用其中了一些比較好的博客文章，如有侵權(quán)，請(qǐng)聯(lián)系作者。

該系列博文會(huì)告訴你如何從入門(mén)到進(jìn)階，Redis基本的使用方法，Redis的基本數(shù)據(jù)結(jié)構(gòu)，以及一些進(jìn)階的使用方法，同時(shí)也需要進(jìn)一步了解Redis的底層數(shù)據(jù)結(jié)構(gòu)，再接著，還會(huì)帶來(lái)Redis主從復(fù)制、集群、分布式鎖等方面的相關(guān)內(nèi)容，以及作為緩存的一些使用方法和注意事項(xiàng)，以便讓你更完整地了解整個(gè)Redis相關(guān)的技術(shù)體系，形成自己的知識(shí)框架。

如果對(duì)本系列文章有什么建議，或者是有什么疑問(wèn)的話(huà)，也可以關(guān)注公眾號(hào)【Java技術(shù)江湖】聯(lián)系作者，歡迎你參與本系列博文的創(chuàng)作和修訂。

這周開(kāi)始學(xué)習(xí) Redis，看看Redis是怎么實(shí)現(xiàn)的。所以會(huì)寫(xiě)一系列關(guān)于 Redis的文章。這篇文章關(guān)于 Redis 的基礎(chǔ)數(shù)據(jù)。閱讀這篇文章你可以了解：

• 動(dòng)態(tài)字符串（SDS）
• 鏈表
• 字典

三個(gè)數(shù)據(jù)結(jié)構(gòu) Redis 是怎么實(shí)現(xiàn)的。

SDS

SDS （Simple Dynamic String）是 Redis 最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)。直譯過(guò)來(lái)就是”簡(jiǎn)單的動(dòng)態(tài)字符串“。Redis 自己實(shí)現(xiàn)了一個(gè)動(dòng)態(tài)的字符串，而不是直接使用了 C 語(yǔ)言中的字符串。

sds 的數(shù)據(jù)結(jié)構(gòu)：

struct sdshdr {   
// buf 中已占用空間的長(zhǎng)度 int len; 
// buf 中剩余可用空間的長(zhǎng)度 int free; 
// 數(shù)據(jù)空間 
char buf[];
}

所以一個(gè) SDS 的就如下圖：

所以我們看到，sds 包含3個(gè)參數(shù)。buf 的長(zhǎng)度 len，buf 的剩余長(zhǎng)度，以及buf。

為什么這么設(shè)計(jì)呢？

• 可以直接獲取字符串長(zhǎng)度。
  C 語(yǔ)言中，獲取字符串的長(zhǎng)度需要用指針遍歷字符串，時(shí)間復(fù)雜度為 O(n)，而 SDS 的長(zhǎng)度，直接從len 獲取復(fù)雜度為 O(1)。

• 杜絕緩沖區(qū)溢出。
  由于C 語(yǔ)言不記錄字符串長(zhǎng)度，如果增加一個(gè)字符傳的長(zhǎng)度，如果沒(méi)有注意就可能溢出，覆蓋了緊挨著這個(gè)字符的數(shù)據(jù)。對(duì)于SDS 而言增加字符串長(zhǎng)度需要驗(yàn)證 free的長(zhǎng)度，如果free 不夠就會(huì)擴(kuò)容整個(gè) buf，防止溢出。

• 減少修改字符串長(zhǎng)度時(shí)造成的內(nèi)存再次分配。
  redis 作為高性能的內(nèi)存數(shù)據(jù)庫(kù)，需要較高的相應(yīng)速度。字符串也很大概率的頻繁修改。 SDS 通過(guò)未使用空間這個(gè)參數(shù)，將字符串的長(zhǎng)度和底層buf的長(zhǎng)度之間的額關(guān)系解除了。buf的長(zhǎng)度也不是字符串的長(zhǎng)度?；谶@個(gè)分設(shè)計(jì) SDS 實(shí)現(xiàn)了空間的預(yù)分配和惰性釋放。

  1. 預(yù)分配
     如果對(duì) SDS 修改后，如果 len 小于 1MB 那 len = 2 * len + 1byte。 這個(gè) 1 是用于保存空字節(jié)。
     如果 SDS 修改后 len 大于 1MB 那么 len = 1MB + len + 1byte。
  2. 惰性釋放
     如果縮短 SDS 的字符串長(zhǎng)度，redis并不是馬上減少 SDS 所占內(nèi)存。只是增加 free 的長(zhǎng)度。同時(shí)向外提供 API 。真正需要釋放的時(shí)候，才去重新縮小 SDS 所占的內(nèi)存

• 二進(jìn)制安全。
  C 語(yǔ)言中的字符串是以 ”\0“ 作為字符串的結(jié)束標(biāo)記。而 SDS 是使用 len 的長(zhǎng)度來(lái)標(biāo)記字符串的結(jié)束。所以SDS 可以存儲(chǔ)字符串之外的任意二進(jìn)制流。因?yàn)橛锌赡苡械亩M(jìn)制流在流中就包含了”\0“造成字符串提前結(jié)束。也就是說(shuō) SDS 不依賴(lài) “\0” 作為結(jié)束的依據(jù)。

• 兼容C語(yǔ)言
  SDS 按照慣例使用 ”\0“ 作為結(jié)尾的管理。部分普通C 語(yǔ)言的字符串 API 也可以使用。

鏈表

C語(yǔ)言中并沒(méi)有鏈表這個(gè)數(shù)據(jù)結(jié)構(gòu)所以 Redis 自己實(shí)現(xiàn)了一個(gè)。Redis 中的鏈表是：

typedef struct listNode { 
// 前置節(jié)點(diǎn) struct listNode *prev; 
// 后置節(jié)點(diǎn) struct listNode *next; 
// 節(jié)點(diǎn)的值 void *value;} listNode;

非常典型的雙向鏈表的數(shù)據(jù)結(jié)構(gòu)。

同時(shí)為雙向鏈表提供了如下操作的函數(shù)：

/* * 雙端鏈表迭代器 */typedef struct listIter { 
// 當(dāng)前迭代到的節(jié)點(diǎn) listNode *next; 
// 迭代的方向 int direction;} listIter;
/* * 雙端鏈表結(jié)構(gòu) 
*/typedef struct list { 
// 表頭節(jié)點(diǎn) listNode *head; 
// 表尾節(jié)點(diǎn) listNode *tail; 
// 節(jié)點(diǎn)值復(fù)制函數(shù) void *(*dup)(void *ptr); 
// 節(jié)點(diǎn)值釋放函數(shù) void (*free)(void *ptr); 
// 節(jié)點(diǎn)值對(duì)比函數(shù) int (*match)(void *ptr, void *key); 
// 鏈表所包含的節(jié)點(diǎn)數(shù)量 unsigned long len;} list;

鏈表的結(jié)構(gòu)比較簡(jiǎn)單，數(shù)據(jù)結(jié)構(gòu)如下：

總結(jié)一下性質(zhì)：

• 雙向鏈表，某個(gè)節(jié)點(diǎn)尋找上一個(gè)或者下一個(gè)節(jié)點(diǎn)時(shí)間復(fù)雜度 O(1)。
• list 記錄了 head 和 tail，尋找 head 和 tail 的時(shí)間復(fù)雜度為 O(1)。
• 獲取鏈表的長(zhǎng)度 len 時(shí)間復(fù)雜度 O(1)。

字典

字典數(shù)據(jù)結(jié)構(gòu)極其類(lèi)似 java 中的 Hashmap。

Redis的字典由三個(gè)基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)組成。最底層的單位是哈希表節(jié)點(diǎn)。結(jié)構(gòu)如下：

typedef struct dictEntry {
    // 鍵
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下個(gè)哈希表節(jié)點(diǎn)，形成鏈表
    struct dictEntry *next;
} dictEntry;

實(shí)際上哈希表節(jié)點(diǎn)就是一個(gè)單項(xiàng)列表的節(jié)點(diǎn)。保存了一下下一個(gè)節(jié)點(diǎn)的指針。 key 就是節(jié)點(diǎn)的鍵，v是這個(gè)節(jié)點(diǎn)的值。這個(gè) v 既可以是一個(gè)指針，也可以是一個(gè) uint64_t或者 int64_t 整數(shù)。*next 指向下一個(gè)節(jié)點(diǎn)。

通過(guò)一個(gè)哈希表的數(shù)組把各個(gè)節(jié)點(diǎn)鏈接起來(lái)：
typedef struct dictht {

    // 哈希表數(shù)組
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩碼，用于計(jì)算索引值
    // 總是等于 size - 1
    unsigned long sizemask;
    // 該哈希表已有節(jié)點(diǎn)的數(shù)量
    unsigned long used;
} dictht;

dictht

通過(guò)圖示我們觀察：

實(shí)際上，如果對(duì)java 的基本數(shù)據(jù)結(jié)構(gòu)了解的同學(xué)就會(huì)發(fā)現(xiàn)，這個(gè)數(shù)據(jù)結(jié)構(gòu)和 java 中的 HashMap 是很類(lèi)似的，就是數(shù)組加鏈表的結(jié)構(gòu)。

字典的數(shù)據(jù)結(jié)構(gòu)：

typedef struct dict {
    // 類(lèi)型特定函數(shù)
    dictType *type;
    // 私有數(shù)據(jù)
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash 索引
    // 當(dāng) rehash 不在進(jìn)行時(shí)，值為 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
    // 目前正在運(yùn)行的安全迭代器的數(shù)量
    int iterators; /* number of iterators currently running */
} dict;

其中的dictType 是一組方法，代碼如下：

/*
 * 字典類(lèi)型特定函數(shù)
 */
typedef struct dictType {
    // 計(jì)算哈希值的函數(shù)
    unsigned int (*hashFunction)(const void *key);
    // 復(fù)制鍵的函數(shù)
    void *(*keyDup)(void *privdata, const void *key);
    // 復(fù)制值的函數(shù)
    void *(*valDup)(void *privdata, const void *obj);
    // 對(duì)比鍵的函數(shù)
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    // 銷(xiāo)毀鍵的函數(shù)
    void (*keyDestructor)(void *privdata, void *key);
    // 銷(xiāo)毀值的函數(shù)
    void (*valDestructor)(void *privdata, void *obj);
} dictType;