從零單排學Redis【青銅】

• 2019 年 10 月 5 日
• 筆記

只有光頭才能變強

redis

最近在學Redis，我相信只要是接觸過Java開發的都會聽過Redis這麼一個技術。面試也是非常高頻的一個知識點，之前一直都是處於了解階段。秋招過後這段時間是沒有什麼壓力的，所以打算系統學學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入門。

1.1為什麼要用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

1.2為什麼要用快取？

如果我們的網站出現了性能問題(訪問時間慢)，按經驗來說，一般是由於資料庫撐不住了。因為一般資料庫的讀寫都是要經過磁碟的，而磁碟的速度可以說是相當慢的(相對記憶體來說)

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

資料庫撐不住了

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

有了快取之後，我們的訪問就變成這樣了：

有了快取提高了並發和性能

二、Redis的數據結構

本文不會講述命令的使用方式，具體的如何使用可查詢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數據結構

但要值得注意的是：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(指向底層數據結構的指針)來表示。

以值為1006的字元串對象為例

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

2.1SDS簡單動態字元串

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

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

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

struct sdshdr{        // 位元組數組，用於保存字元串      char buf[];        // 記錄buf數組中已使用的位元組數量，也是字元串的長度      int len;        // 記錄buf數組未使用的位元組數量      int free;  }  

例子：

SDS例子

2.1.1使用SDS的好處

SDS與C的字元串表示比較

1. sdshdr數據結構中用len屬性記錄了字元串的長度。那麼獲取字元串的長度時，時間複雜度只需要O(1)。
2. SDS不會發生溢出的問題，如果修改SDS時，空間不足。先會擴展空間，再進行修改！(內部實現了動態擴展機制)。
3. SDS可以減少記憶體分配的次數(空間預分配機制)。在擴展空間時，除了分配修改時所必要的空間，還會分配額外的空閑空間(free 屬性)。
4. SDS是二進位安全的，所有SDS API都會以處理二進位的方式來處理SDS存放在buf數組裡的數據。

2.2鏈表

對於鏈表而言，我們不會陌生的了。在大學期間肯定開過數據結構與演算法課程，鏈表肯定是講過的了。在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  

具體的結構如圖：

2.2.1Redis鏈表的特性

Redis的鏈表有以下特性：

• 無環雙向鏈表
• 獲取表頭指針，表尾指針，鏈表節點長度的時間複雜度均為O(1)
• 鏈表使用void *指針來保存節點值，可以保存各種不同類型的值

2.3哈希表

聲明：《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在哈希衝突時：是將新的節點添加到鏈表的表尾。

2.3.1rehash的過程

下面來具體講講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]的鍵值對數量只減不增，直至變為空表。

2.4跳躍表(shiplist)

跳躍表(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;  

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

跳躍表示例圖

2.5整數集合(intset)

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

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

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

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）將新元素添加到底層數組。

另外一提：只支援升級操作，並不支援降級操作。

2.6壓縮列表(ziplist)

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

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

壓縮列表結構圖例如下：

壓縮列表的組成部分

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

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

三、Redis中數據結構的對象

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

數據結構對應的類型與編碼

3.1字元串(stirng)對象

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

• int：整數值，這個整數值可以使用long類型來表示
  • 如果是浮點數，那就用embstr或者raw編碼。具體用哪個就看這個數的長度了
• embstr：字元串值，這個字元串值的長度小於39位元組
• raw：字元串值，這個字元串值的長度大於39位元組

embstr和raw的區別：

• raw分配記憶體和釋放記憶體的次數是兩次，embstr是一次
• embstr編碼的數據保存在一塊連續的記憶體裡面

編碼之間的轉換：

• int類型如果存的不再是一個整數值，則會從int轉成raw
• embstr是只讀的，在修改的時候回從embstr轉成raw

3.2列表(list)對象

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

• ziplist：字元串元素的長度都小於64個位元組&&總數量少於512個
• linkedlist：字元串元素的長度大於64個位元組||總數量大於512個

ziplist編碼的列表結構：

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

ziplist的列表結構

linkedlist編碼的列表結構：

linkedlist編碼的列表結構

編碼之間的轉換：

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

3.3哈希(hash)對象

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

• ziplist：key和value的字元串長度都小於64位元組&&鍵值對總數量小於512
• hashtable：key和value的字元串長度大於64位元組||鍵值對總數量大於512

ziplist編碼的哈希結構：

ziplist編碼的哈希結構1

ziplist編碼的哈希結構2

hashtable編碼的哈希結構：

hashtable編碼的哈希結構

編碼之間的轉換：

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

3.4集合(set)對象

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

• intset：保存的元素全都是整數&&總數量小於512
• hashtable：保存的元素不是整數||總數量大於512

intset編碼的集合結構：

intset編碼的集合結構

hashtable編碼的集合結構：

hashtable編碼的集合結構

編碼之間的轉換：

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

3.5有序集合(sortset)對象

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

• ziplist：元素長度小於64&&總數量小於128
• skiplist：元素長度大於64||總數量大於128

ziplist編碼的有序集合結構：

ziplist編碼的有序集合結構1

ziplist編碼的有序集合結構2

skiplist編碼的有序集合結構：

skiplist編碼的有序集合結構

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

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

編碼之間的轉換：

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

3.6Redis對象一些細節

• (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，歡迎大家關注

3y所有的原創技術文章導航：

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