摘要：從代碼上看字典也是在哈希表基礎上再抽象了一層而已。在中，哈希表實際上就是數組鏈表的形式來構建的。后，在哈希沖突時是將新的節點添加到鏈表的表尾。在對哈希表進行擴展或者收縮操作時，過程并不是一次性地完成的，而是漸進式地完成的。

只有光頭才能變強

最近在學Redis，我相信只要是接觸過Java開發的都會聽過Redis這么一個技術。面試也是非常高頻的一個知識點，之前一直都是處于了解階段。秋招過后這段時間是沒有什么壓力的，所以打算系統學學Redis，這也算是我從零學習Redis的筆記吧。

本文力求講清每個知識點，希望大家看完能有所收獲。

首先，肯定是去官網看看官方是怎么介紹Redis的啦。https://redis.io/topics/introduction

如果像我一樣，英語可能不太好的，可能看不太懂。沒事，咱們Chrome瀏覽器可以切換成中文的，中文是我們的母語，肯定沒啥壓力了。Eumm...

讀完之后，發現中文也就那樣了。

一大堆沒見過的技術：lua(Lua腳本)、replication(復制)、Redis Sentinel(哨兵)、Redis Cluster(Redis 集群)，當然我們也會有看得懂的技術：transactions(事務)、different levels of on-disk persistence(數據持久化)、LRU eviction(LRU淘汰機制)..

至少官方介紹Redis的第一句應該是可以很容易看懂："Redis is an open source (BSD licensed),in-memory data structure store, used as a database,cache and message broker."

Redis是一個開源的，基于內存的數據結構存儲，可用作于數據庫、緩存、消息中間件。

從官方的解釋上，我們可以知道：Redis是基于內存，支持多種數據結構。

從經驗的角度上，我們可以知道：Redis常用作于緩存。

就我個人認為：學習一種新技術，先把握該技術整體的知識(思想)，再扣細節，這樣學習起來會比較輕松一些。所以我們先以“內存”、“數據結構”、“緩存”來對Redis入門。

從上面可知：Redis是基于內存，常用作于緩存的一種技術，并且Redis存儲的方式是以key-value的形式。

我們可以發現這不就是Java的Map容器所擁有的特性嗎，那為什么還需要Redis呢？

Java實現的Map是本地緩存，如果有多臺實例(機器)的話，每個實例都需要各自保存一份緩存，緩存不具有一致性

Redis實現的是分布式緩存，如果有多臺實例(機器)的話，每個實例都共享一份緩存，緩存具有一致性。

Java實現的Map不是專業做緩存的，JVM內存太大容易掛掉的。一般用做于容器來存儲臨時數據，緩存的數據隨著JVM銷毀而結束。Map所存儲的數據結構，緩存過期機制等等是需要程序員自己手寫的。

Redis是專業做緩存的，可以用幾十個G內存來做緩存。Redis一般用作于緩存，可以將緩存數據保存在硬盤中，Redis重啟了后可以將其恢復。原生提供豐富的數據結構、緩存過期機制等等簡單好用的功能。

參考資料：

為什么要用redis而不用map做緩存?https://segmentfault.com/q/1010000009106416

如果我們的網站出現了性能問題(訪問時間慢)，按經驗來說，一般是由于數據庫撐不住了。因為一般數據庫的讀寫都是要經過磁盤的，而磁盤的速度可以說是相當慢的(相對內存來說)

科普文：讓 CPU 告訴你硬盤和網絡到底有多慢https://zhuanlan.zhihu.com/p/24726196

如果學過Mybaits、Hibernate的同學就可以知道，它們有一級緩存、二級緩存這樣的功能(終究來說還是本地緩存)。目的就是為了：不用每次讀取的時候，都要查一次數據庫。

有了緩存之后，我們的訪問就變成這樣了：

本文不會講述命令的使用方式，具體的如何使用可查詢API。

Redis 命令參考：http://doc.redisfans.com/

try Redis(不用安裝Redis即可體驗Redis命令)：http://try.redis.io/

Redis支持豐富的數據結構，常用的有string、list、hash、set、sortset這幾種。學習這些數據結構是使用Redis的基礎！

"Redis is written in ANSI C"-->Redis由C語言編寫

首先還是得聲明一下，Redis的存儲是以key-value的形式的。Redis中的key一定是字符串，value可以是string、list、hash、set、sortset這幾種常用的。

但要值得注意的是：Redis并沒有直接使用這些數據結構來實現key-value數據庫，而是基于這些數據結構創建了一個對象系統。

簡單來說：Redis使用對象來表示數據庫中的鍵和值。每次我們在Redis數據庫中新創建一個鍵值對時，至少會創建出兩個對象。一個是鍵對象，一個是值對象。

Redis中的每個對象都由一個redisObject結構來表示：

typedef struct redisObject{
    
    // 對象的類型
    unsigned type 4:;

    // 對象的編碼格式
    unsigned encoding:4;

    // 指向底層實現數據結構的指針
    void * ptr;

    //.....


}robj;

簡單來說就是Redis對key-value封裝成對象，key是一個對象，value也是一個對象。每個對象都有type(類型)、encoding(編碼)、ptr(指向底層數據結構的指針)來表示。

下面我就來說一下我們Redis常見的數據類型：string、list、hash、set、sortset。它們的底層數據結構究竟是怎么樣的！

簡單動態字符串(Simple dynamic string,SDS)

Redis中的字符串跟C語言中的字符串，是有點差距的。

Redis使用sdshdr結構來表示一個SDS值：

struct sdshdr{

    // 字節數組，用于保存字符串
    char buf[];

    // 記錄buf數組中已使用的字節數量，也是字符串的長度
    int len;

    // 記錄buf數組未使用的字節數量
    int free;
}

例子：

SDS與C的字符串表示比較

sdshdr數據結構中用len屬性記錄了字符串的長度。那么獲取字符串的長度時，時間復雜度只需要O(1)。

SDS不會發生溢出的問題，如果修改SDS時，空間不足。先會擴展空間，再進行修改！(內部實現了動態擴展機制)。

SDS可以減少內存分配的次數(空間預分配機制)。在擴展空間時，除了分配修改時所必要的空間，還會分配額外的空閑空間(free 屬性)。

SDS是二進制安全的，所有SDS API都會以處理二進制的方式來處理SDS存放在buf數組里的數據。

對于鏈表而言，我們不會陌生的了。在大學期間肯定開過數據結構與算法課程，鏈表肯定是講過的了。在Java中Linkedxxx容器底層數據結構也是鏈表+[xxx]的。我們來看看Redis中的鏈表是怎么實現的：

使用listNode結構來表示每個節點：

typedef strcut listNode{

    //前置節點
    strcut listNode  *pre;

    //后置節點
    strcut listNode  *pre;

    //節點的值
    void  *value;

}listNode

使用listNode是可以組成鏈表了，Redis中使用list結構來持有鏈表：

typedef struct list{

    //表頭結點
    listNode  *head;

    //表尾節點
    listNode  *tail;

    //鏈表長度
    unsigned long len;

    //節點值復制函數
    void *(*dup) (viod *ptr);

    //節點值釋放函數
    void  (*free) (viod *ptr);

    //節點值對比函數
    int (*match) (void *ptr,void *key);

}list

具體的結構如圖：

Redis的鏈表有以下特性：

無環雙向鏈表

獲取表頭指針，表尾指針，鏈表節點長度的時間復雜度均為O(1)

鏈表使用void *指針來保存節點值，可以保存各種不同類型的值

聲明：《Redis設計與實現》里邊有“字典”這么一個概念，我個人認為還是直接叫哈希表比較通俗易懂。從代碼上看：“字典”也是在哈希表基礎上再抽象了一層而已。

在Redis中，key-value的數據結構底層就是哈希表來實現的。對于哈希表來說，我們也并不陌生。在Java中，哈希表實際上就是數組+鏈表的形式來構建的。下面我們來看看Redis的哈希表是怎么構建的吧。

在Redis里邊，哈希表使用dictht結構來定義：

    typedef struct dictht{
        
        //哈希表數組
        dictEntry **table;  
    
        //哈希表大小
        unsigned long size;    
    
        //哈希表大小掩碼，用于計算索引值
        //總是等于size-1
        unsigned long sizemark;     
    
        //哈希表已有節點數量
        unsigned long used;
         
    }dictht

我們下面繼續寫看看哈希表的節點是怎么實現的吧：

    typedef struct dictEntry {
        
        //鍵
        void *key;
    
        //值
        union {
            void *value;
            uint64_tu64;
            int64_ts64;
        }v;    
    
        //指向下個哈希節點，組成鏈表
        struct dictEntry *next;
    
    }dictEntry;

從結構上看，我們可以發現：Redis實現的哈希表和Java中實現的是類似的。只不過Redis多了幾個屬性來記錄常用的值：sizemark(掩碼)、used(已有的節點數量)、size(大小)。

同樣地，Redis為了更好的操作，對哈希表往上再封裝了一層(參考上面的Redis實現鏈表)，使用dict結構來表示：

typedef struct dict {

    //類型特定函數
    dictType *type;

    //私有數據
    void *privdata;
  
    //哈希表
    dictht ht[2];

    //rehash索引
    //當rehash不進行時，值為-1
    int rehashidx;  

}dict;


//-----------------------------------

typedef struct dictType{

    //計算哈希值的函數
    unsigned int (*hashFunction)(const void * key);

    //復制鍵的函數
    void *(*keyDup)(void *private, const void *key);
 
    //復制值得函數
    void *(*valDup)(void *private, const void *obj);  

    //對比鍵的函數
    int (*keyCompare)(void *privdata , const void *key1, const void *key2)

    //銷毀鍵的函數
    void (*keyDestructor)(void *private, void *key);
 
    //銷毀值的函數
    void (*valDestructor)(void *private, void *obj);  

}dictType

所以，最后我們可以發現，Redis所實現的哈希表最后的數據結構是這樣子的：

從代碼實現和示例圖上我們可以發現，Redis中有兩個哈希表：

ht[0]：用于存放真實的key-vlaue數據

ht[1]：用于擴容(rehash)

Redis中哈希算法和哈希沖突跟Java實現的差不多，它倆差異就是：

Redis哈希沖突時：是將新節點添加在鏈表的表頭。

JDK1.8后，Java在哈希沖突時：是將新的節點添加到鏈表的表尾。

下面來具體講講Redis是怎么rehash的，因為我們從上面可以明顯地看到，Redis是專門使用一個哈希表來做rehash的。這跟Java一次性直接rehash是有區別的。

在對哈希表進行擴展或者收縮操作時，reash過程并不是一次性地完成的，而是漸進式地完成的。

Redis在rehash時采取漸進式的原因：數據量如果過大的話，一次性rehash會有龐大的計算量，這很可能導致服務器一段時間內停止服務。

Redis具體是rehash時這么干的：

(1:在字典中維持一個索引計數器變量rehashidx，并將設置為0，表示rehash開始。

(2:在rehash期間每次對字典進行增加、查詢、刪除和更新操作時，除了執行指定命令外；還會將ht[0]中rehashidx索引上的值rehash到ht[1]，操作完成后rehashidx+1。

(3:字典操作不斷執行，最終在某個時間點，所有的鍵值對完成rehash，這時將rehashidx設置為-1，表示rehash完成

(4:在漸進式rehash過程中，字典會同時使用兩個哈希表ht[0]和ht[1]，所有的更新、刪除、查找操作也會在兩個哈希表進行。例如要查找一個鍵的話，服務器會優先查找ht[0]，如果不存在，再查找ht[1]，諸如此類。此外當執行新增操作時，新的鍵值對一律保存到ht[1]，不再對ht[0]進行任何操作，以保證ht[0]的鍵值對數量只減不增，直至變為空表。

跳躍表(shiplist)是實現sortset(有序集合)的底層數據結構之一！

跳躍表可能對于大部分人來說不太常見，之前我在學習的時候發現了一篇不錯的文章講跳躍表的，建議大家先去看完下文再繼續回來閱讀：

漫畫算法：什么是跳躍表？http://blog.jobbole.com/111731/

Redis的跳躍表實現由zskiplist和zskiplistNode兩個結構組成。其中zskiplist保存跳躍表的信息(表頭，表尾節點，長度)，zskiplistNode則表示跳躍表的節點。

按照慣例，我們來看看zskiplistNode跳躍表節點的結構是怎么樣的：

typeof struct zskiplistNode {
        // 后退指針
        struct zskiplistNode *backward;
        // 分值
        double score;
        // 成員對象
        robj *obj;
        // 層
        struct zskiplistLevel {
                // 前進指針
                struct zskiplistNode *forward;
                // 跨度
                unsigned int span;
        } level[];
} zskiplistNode;

zskiplistNode的對象示例圖(帶有不同層高的節點)：

示例圖如下：

zskiplist的結構如下：

typeof struct zskiplist {
        // 表頭節點，表尾節點
        struct skiplistNode *header,*tail;
        // 表中節點數量
        unsigned long length;
        // 表中最大層數
        int level;
} zskiplist;

最后我們整個跳躍表的示例圖如下：

整數集合是set(集合)的底層數據結構之一。當一個set(集合)只包含整數值元素，并且元素的數量不多時，Redis就會采用整數集合(intset)作為set(集合)的底層實現。

整數集合(intset)保證了元素是不會出現重復的，并且是有序的(從小到大排序)，intset的結構是這樣子的：

typeof struct intset {
        // 編碼方式
        unit32_t encoding;
        // 集合包含的元素數量
        unit32_t lenght;
        // 保存元素的數組
        int8_t contents[];
} intset;

intset示例圖：

說明：雖然intset結構將contents屬性聲明為int8_t類型的數組，但實際上contents數組并不保存任何int8_t類型的值，contents數組的真正類型取決于encoding屬性的值：

INTSET_ENC_INT16

INTSET_ENC_INT32

INTSET_ENC_INT64

從編碼格式的名字我們就可以知道，16,32,64編碼對應能存放的數字范圍是不一樣的。16明顯最少，64明顯最大。

如果本來是INTSET_ENC_INT16的編碼，想要存放大于INTSET_ENC_INT16編碼能存放的整數值，此時就得編碼升級(從16升級成32或者64)。步驟如下：

1）根據新元素類型拓展整數集合底層數組的空間并為新元素分配空間。

2）將底層數組現有的所以元素都轉換成與新元素相同的類型，并將類型轉換后的元素放到正確的位上，需要維持底層數組的有序性質不變。

3）將新元素添加到底層數組。

另外一提：只支持升級操作，并不支持降級操作。

壓縮列表(ziplist)是list和hash的底層實現之一。如果list的每個都是小整數值，或者是比較短的字符串，壓縮列表(ziplist)作為list的底層實現。

壓縮列表(ziplist)是Redis為了節約內存而開發的，是由一系列的特殊編碼的連續內存塊組成的順序性數據結構。

壓縮列表結構圖例如下：

下面我們看看節點的結構圖：

壓縮列表從表尾節點倒序遍歷，首先指針通過zltail偏移量指向表尾節點，然后通過指向節點記錄的前一個節點的長度依次向前遍歷訪問整個壓縮列表。

再次看回這張圖，覺不覺得就很好理解了？

在上面的圖我們知道string類型有三種編碼格式：

int：整數值，這個整數值可以使用long類型來表示

如果是浮點數，那就用embstr或者raw編碼。具體用哪個就看這個數的長度了

embstr：字符串值，這個字符串值的長度小于39字節

raw：字符串值，這個字符串值的長度大于39字節

embstr和raw的區別：

raw分配內存和釋放內存的次數是兩次，embstr是一次

embstr編碼的數據保存在一塊連續的內存里面

編碼之間的轉換：

int類型如果存的不再是一個整數值，則會從int轉成raw

embstr是只讀的，在修改的時候回從embstr轉成raw

在上面的圖我們知道list類型有兩種編碼格式：

ziplist：字符串元素的長度都小于64個字節&&總數量少于512個

linkedlist：字符串元素的長度大于64個字節||總數量大于512個

ziplist編碼的列表結構：

    redis > RPUSH numbers 1 "three" 5
    (integer) 3 

linkedlist編碼的列表結構：

編碼之間的轉換：

原本是ziplist編碼的，如果保存的數據長度太大或者元素數量過多，會轉換成linkedlist編碼的。

在上面的圖我們知道hash類型有兩種編碼格式：

ziplist：key和value的字符串長度都小于64字節&&鍵值對總數量小于512

hashtable：key和value的字符串長度大于64字節||鍵值對總數量大于512

ziplist編碼的哈希結構：

hashtable編碼的哈希結構：

編碼之間的轉換：

原本是ziplist編碼的，如果保存的數據長度太大或者元素數量過多，會轉換成hashtable編碼的。

在上面的圖我們知道set類型有兩種編碼格式：

intset：保存的元素全都是整數&&總數量小于512

hashtable：保存的元素不是整數||總數量大于512

intset編碼的集合結構：

hashtable編碼的集合結構：

編碼之間的轉換：

原本是intset編碼的，如果保存的數據不是整數值或者元素數量大于512，會轉換成hashtable編碼的。

在上面的圖我們知道set類型有兩種編碼格式：

ziplist：元素長度小于64&&總數量小于128

skiplist：元素長度大于64||總數量大于128

ziplist編碼的有序集合結構：

skiplist編碼的有序集合結構：

有序集合(sortset)對象同時采用skiplist和哈希表來實現：

skiplist能夠達到插入的時間復雜度為O(logn)，根據成員查分值的時間復雜度為O(1)

編碼之間的轉換：

原本是ziplist編碼的，如果保存的數據長度大于64或者元素數量大于128，會轉換成skiplist編碼的。

(1：服務器在執行某些命令的時候，會先檢查給定的鍵的類型能否執行指定的命令。

比如我們的數據結構是sortset，但你使用了list的命令。這是不對的，服務器會檢查一下我們的數據結構是什么才會進一步執行命令

(2：Redis的對象系統帶有引用計數實現的內存回收機制。

對象不再被使用的時候，對象所占用的內存會釋放掉

(3：Redis會共享值為0到9999的字符串對象

(4：對象會記錄自己的最后一次被訪問時間，這個時間可以用于計算對象的空轉時間。

本文主要講了一下Redis常用的數據結構，以及這些數據結構的底層設計是怎么樣的。整體來說不會太難，因為這些數據結構我們在學習的過程中多多少少都接觸過了，《Redis設計與實現》這本書寫得也足夠通俗易懂。

至于我們在使用的時候挑選哪些數據結構作為存儲，可以簡單看看：

string-->簡單的key-value

list-->有序列表(底層是雙向鏈表)-->可做簡單隊列

set-->無序列表(去重)-->提供一系列的交集、并集、差集的命令

hash-->哈希表-->存儲結構化數據

sortset-->有序集合映射(member-score)-->排行榜

如果大家有更好的理解方式或者文章有錯誤的地方還請大家不吝在評論區留言，大家互相學習交流~~~

參考博客：

Redis簡明教程http://bridgeforyou.cn/2018/05/19/Redis-Tutorial/

五旬大爺教你一窺redis之謎https://zhuanlan.zhihu.com/p/34762100

參考資料：

《Redis設計與實現》

《Redis實戰》

一個堅持原創的Java技術公眾號：Java3y，歡迎大家關注

原創技術文章導航：

文章的目錄導航(腦圖+海量視頻資源)：https://github.com/ZhongFuCheng3y/3y