Redis簡介

Redis全稱為Remote Dictionary Server(遠(yuǎn)程字典服務(wù)) 是一個由Salvatore Sanfilippo開發(fā)的一款開源的，使用C語言編寫，支持網(wǎng)絡(luò)、基于內(nèi)存，可選持久化的Key-Value數(shù)據(jù)庫；其支持豐富的數(shù)據(jù)類型：字符串(String)、哈希(Map)、 列表(list)、 集合(sets) 和 有序集合(sorted sets)、位圖(bitmaps)、HyperLogLogs等數(shù)據(jù)結(jié)構(gòu)。目前開發(fā)主要由Redis Labs公司贊助，最新穩(wěn)定版為6.2.4。

Redis 快到什么程度？

在探究redis為什么這么快之前，我們先來分析下影響一個系統(tǒng)快慢的指標(biāo)有哪些。

• 響應(yīng)時間：指系統(tǒng)對請求做出響應(yīng)的時間，用戶對該指標(biāo)有直觀感受。

• 吞吐量：指單位時間內(nèi)處理請求的數(shù)量。

• 并發(fā)數(shù)：指系統(tǒng)可以同時承載的正常使用系統(tǒng)功能的用戶的數(shù)量。

吞吐量 = 并發(fā)數(shù)量/響應(yīng)時長

因此響應(yīng)時長越短，并發(fā)數(shù)越高，吞吐量就越好，應(yīng)用響應(yīng)能力就越優(yōu)秀。

下面我們可以通過redis提供的基準(zhǔn)測試工具redis-benchmark測試下到底有多快。 硬件環(huán)境：centos7 單核CPU(主頻 2.1GHz) 2G內(nèi)存、 redis版本 3.2.4

• 100并發(fā),常用命令每秒執(zhí)行次數(shù)
  image.png

• 100并發(fā)，使用10 萬隨機 key 連續(xù)GET、 SET 200 萬次
  image.png

• 100并發(fā)，使用10 萬隨機 key ，GET、 SET 200 萬次，16個指令一批次
  image.png

  壓測過程中CPU使用率 16%

  [圖片上傳失敗...(image-f03165-1624415605556)]

  由上測試可以看到redis的一般讀寫速度可以達(dá)到10w+以上，范圍查詢也有1w+ qps的表現(xiàn)，通過pipeline批量執(zhí)行讀寫更是可以達(dá)到50w+以上。

Redis 為什么這么快？

系統(tǒng)實現(xiàn)來看

• key-value（字典）結(jié)構(gòu) 字典結(jié)構(gòu)的時間復(fù)雜度為O(1)，類比java中的HashMap。

• 絕大部分請求是純粹的內(nèi)存操作，速度非?？?。 redis是一個內(nèi)存數(shù)據(jù)庫，內(nèi)存讀寫相對于磁盤IO來說要快幾個數(shù)量級，系統(tǒng)運行如果需要等待磁盤I/O的完成，將導(dǎo)致整個系統(tǒng)的性能下降。

• C語言編寫 C語言簡潔高效，可以直接操作內(nèi)存，編譯后生成的機器碼基本上和直接寫匯編生成的機器碼是相當(dāng)?shù)?；但語法限制不嚴(yán)格，面向過程缺乏封裝，難以掌握，對使用者要求高。

IO模型

image.png

圖中fd就是套接字，當(dāng)select/epoll等系統(tǒng)函數(shù)監(jiān)聽到一旦fd上有請求到達(dá)時，就會出發(fā)相應(yīng)的事件，這些事件會被放進(jìn)一個事件隊列，Redis 以單線程對該事件隊列不斷進(jìn)行處理。 為什么redis采用單線程效率這么高？

• 基于非阻塞的IO多路復(fù)用機制。

• redis的獲取 (socket 讀)、解析、執(zhí)行、內(nèi)容返回 (socket 寫) 采用單線程，有以下好處：

  • 避免了不必要的多進(jìn)程或者多線程的上下文切換和競態(tài)條件消耗的CPU，不用去考慮各種鎖的問題，不存在加鎖、釋放鎖操作，沒有因為可能出現(xiàn)死鎖而導(dǎo)致的性能消耗；

  • 避免線程不安全的情況，簡化數(shù)據(jù)結(jié)構(gòu)和算法的實現(xiàn)（不用考慮并發(fā)）；

采用的單線程而不是因為單線程性能高而使用單線程，主要是因為單線程實現(xiàn)很簡單，且限制redis性能主要是內(nèi)存及網(wǎng)絡(luò)IO。實際上Redis6.0中的多線程也只是IO多線程，將主線程的 IO 讀寫任務(wù)拆分出來給一組獨立的線程執(zhí)行，使得多個 socket 的讀寫可以并行化，命令執(zhí)行仍是單線程。

Redis的數(shù)據(jù)結(jié)構(gòu)是精心設(shè)計的

redis主要的基本數(shù)據(jù)結(jié)構(gòu)有

• string 字符串類型

• list 列表類型

• hash 哈希表類型

• set 無序集合類型

• zset 有序集合類型

Redis的核心對象為redisObject位于server.h源碼中，結(jié)構(gòu)定義如下

typedef struct redisObject { 
 unsigned type:4;// 類型
 unsigned encoding:4;// 編碼  
 unsigned lru:LRU_BITS; //LRU算法,對象最后一次被訪問的時間
int refcount; //引用計數(shù) 
void *ptr;// 底層數(shù)據(jù)結(jié)構(gòu)的指針 
} robj;

type類型

encoding 編碼

不同類型編碼與對象的結(jié)構(gòu)關(guān)系

image.png

image.png

下面我們sds及l(fā)ist兩種類型為例講解redis的數(shù)據(jù)結(jié)構(gòu)設(shè)計

string

Redis中，字符串是可以修改的，長度是動態(tài)可變的，在底層它是以字節(jié)數(shù)組的形式存在的，被稱為簡單動態(tài)字符串sds(simple dynamic string)。數(shù)據(jù)結(jié)構(gòu)定義如下：

struct sdshdr { 
    int len;   // buf 中已占用空間的長度
    int free;  //  buf 中剩余可用空間的長度
    char buf[]; // 內(nèi)容,字節(jié)數(shù)組
};

image-20210618215247254.png

如上圖表示空閑空間長度為0、已經(jīng)使用的空間長度為4的SDS字符串。同時SDS為了能夠使用部分C字符串函數(shù)，遵循了C字符串以空字符（\0）結(jié)尾的慣例，保存空字符的1字節(jié)不計算在SDS len屬性中。

SDS有以下優(yōu)點：

1. 保存了len屬性,獲取字符串長度, 常數(shù)復(fù)雜度O(1) , c語言中獲取字符串長度為O(n)。

2. 增長時空間預(yù)分配,減少內(nèi)存的頻繁分配，惰性內(nèi)存空間回收。

   • C字符串在處理增長或者縮短操作時，程序會對這個C字符串的數(shù)組進(jìn)行一次內(nèi)存重分配操作。

   • 對SDS的空間進(jìn)行擴展的時候，程序不僅會為SDS分配修改所必須的空間，還會為SDS分配額外的未使用的空間,這樣可以減少連續(xù)執(zhí)行字符串增長操作所需的內(nèi)存重分配次數(shù)。

   • 對SDS的字符串進(jìn)行縮短操作的時候，程序不會立刻使用內(nèi)存重分配來回收縮短之后多出來的字節(jié)，使用free屬性將多余字節(jié)調(diào)配記錄下來，通過惰性空間釋放策略，SDS避免了縮短字符串時所需的內(nèi)存重分配次數(shù)也為將來可能存在的增長操作提供了優(yōu)化。

3. 避免緩沖區(qū)溢出

   • C語言字符串不記錄自身長度，容易造成緩沖區(qū)溢出。如當(dāng)對兩個內(nèi)存緊挨著的字符串中的一個執(zhí)行拼接操作（strcat），就會導(dǎo)致concat的內(nèi)容覆蓋了另一個字符的內(nèi)容。

   • 當(dāng) SDS 進(jìn)行字符串?dāng)U充時，首先會檢查當(dāng)前的字節(jié)數(shù)組的長度是否足夠。如果不夠的話，會先進(jìn)行自動擴容，然后再進(jìn)行字符串操作。

4. 二進(jìn)制安全

   • SDS的API都是二進(jìn)制安全的。

   • SDS的buf屬性為字節(jié)數(shù)組，程序不會對其中的數(shù)據(jù)做任何的限制，數(shù)據(jù)存進(jìn)去是什么樣子，讀出來就是什么樣子，因此可以用來保存的音頻、圖片、視頻等數(shù)據(jù)。

list

版本3.2之前，當(dāng)列表對象中元素的長度比較小或者數(shù)量比較少的時候，采用ziplist來存儲，當(dāng)列表對象中元素的長度比較大或者數(shù)量比較多的時候，則會轉(zhuǎn)而使用雙向列表linkedlist來存儲。

這兩種鏈表存儲方式的優(yōu)缺點

• 雙向鏈表linkedlist節(jié)點帶有prev、next指針、head指針和tail指針，獲取前置節(jié)點、后置節(jié)點、表頭節(jié)點和表尾節(jié)點的復(fù)雜度都是O(1)，便于在表的兩端進(jìn)行push和pop操作，但是它的內(nèi)存開銷比較大，每個node上除了要保存數(shù)據(jù)之外，還要額外保存兩個指針；另外雙向鏈表的各個節(jié)點是單獨的內(nèi)存塊，地址不連續(xù)，容易產(chǎn)生內(nèi)存碎片。

• ziplist存儲在一段連續(xù)的內(nèi)存上，由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序型數(shù)據(jù)結(jié)構(gòu)，查找，添加、修改、刪除操作時間復(fù)雜度為O(n)，且添加、修改、刪除時需要頻繁的申請和釋放內(nèi)存，因此它適合數(shù)據(jù)比較小的情況。

ziplist 結(jié)構(gòu)

redis/src目錄下ziplist.c中：

image.png

• zlbytes：32bit無符號整數(shù)，表示ziplist占用的字節(jié)總數(shù)（包括本身占用的4個字節(jié)）；

• zltail：32bit無符號整數(shù)，記錄最后一個entry的偏移量，方便快速定位到最后一個entry；

• zllen：16bit無符號整數(shù)，記錄entry的個數(shù)；

• entry：存儲的若干個元素，可以為字節(jié)數(shù)組或者整數(shù)；

• zlend：ziplist最后一個字節(jié)，是一個結(jié)束的標(biāo)記位，值固定為255。

image.png

如上圖所示，zlbytes的值為0x50（十進(jìn)制80），表示壓縮列表的總長度為80字節(jié)。 zltail的值為0x3c（十進(jìn)制60），entry3元素距離列表起始位置的偏移量為60，起始位置的指針加上60就能算出表尾節(jié)點entry3的地址。 zllen的值為0x3（十進(jìn)制3），表示壓縮列表包含3個節(jié)點。

ziplist entry結(jié)構(gòu)

image.png

ziplist entry由previous_entry_length、encoding、content三部分組成。 previous_entry_length previous_entry_length 是一個變長字段

• 前一個元素的長度小于254字節(jié)時，previous_entry_length用1個字節(jié)表示；

• 前一個元素的長度大于等于254字節(jié)時，previous_entry_length用5個字節(jié)進(jìn)行表示，此時，previous_entry_length的第一個字節(jié)是固定的254（0xFE）（作為這種情況的一個標(biāo)志），后面4個字節(jié)才表示前一個元素的長度。

encoding Redis為了節(jié)約空間，對encoding字段進(jìn)行復(fù)雜的設(shè)計，Redis通過encoding來判斷存儲數(shù)據(jù)的類型。

• 00xxxxxx 最大長度位 63 的短字符串，后面的6個位存儲字符串的位數(shù)；

• 01xxxxxx xxxxxxxx 中等長度的字符串，后面14個位來表示字符串的長度；

• 10000000 pppppppp rrrrrrrr ssssssss tttttttt 特大字符串，需要使用額外 4 個字節(jié)來表示長度。第一個字節(jié)前綴是10，剩余 6 位沒有使用，統(tǒng)一置為零；

• 11000000 表示 int16；

• 11010000 表示 int32；

• 11100000 表示 int64；

• 11110000 表示 int24；

• 11111110 表示 int8；

• 11111111 表示 ziplist 的結(jié)束，也就是 zlend 的值 0xFF；

• 1111xxxx 表示極小整數(shù)，xxxx 的范圍只能是 (0001~1101), 也就是1~13。

content 保存節(jié)點的值，節(jié)點值可以是字節(jié)數(shù)組或者整數(shù)，值的類型和長度由encoding決定。

什么條件下會用ziplist？

• 列表對象保存的所有字符串元素的長度都小于等于64字節(jié)

• 列表對象保存的元素數(shù)量小于等于512個

  
  
  image-20210618214019087.png

image-20210618214349155.png

quickList

3.2版本后列表為將ziplist和雙向列表linkedlist的各自優(yōu)點結(jié)合后的quickList

image.png

其結(jié)構(gòu)源碼位于quicklist.h中

typedef struct quicklistNode {
    struct quicklistNode *prev; /*指向鏈表前一個節(jié)點的指針*/
    struct quicklistNode *next; /*指向鏈表后一個節(jié)點的指針*/
    unsigned char *zl;
    unsigned int sz;             /* ziplist占用byte數(shù)*/
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* 數(shù)據(jù)類型，RAW==1 or LZF==2  */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* 這個節(jié)點以前是否被壓縮過 */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

typedef struct quicklistLZF {
    unsigned int sz; /* 表示壓縮后的ziplist大小*/
    char compressed[]; /*存放壓縮后的ziplist字節(jié)數(shù)組*/
} quicklistLZF;

typedef struct quicklist {
    quicklistNode *head;        /*指向頭節(jié)點的指針*/
    quicklistNode *tail;        /*指向尾節(jié)點的指針*/
    unsigned long count;        /* 所有ziplist中entry的數(shù)量 */
    unsigned long len;          /* quicklistNode的數(shù)量 */
    int fill : 16;              /* 16bit，ziplist大小設(shè)置，存放list-max-ziplist-size參數(shù)的值 */
    unsigned int compress : 16; /* 16bit，節(jié)點壓縮深度設(shè)置，存放list-compress-depth參數(shù)的值 */
} quicklist;

image.png

黃色背景是普通的ziplist節(jié)點，紫色背景是被壓縮后的ziplist節(jié)點(LZF節(jié)點)，LZF是種無損壓縮算法。 redis為了節(jié)省內(nèi)存空間，會將quicklist的節(jié)點用LZF壓縮后存儲，不是所有節(jié)點均壓縮，可以通過配置compress的值，compress為0表示所有節(jié)點都不壓縮，否則就表示從兩端開始有多少個節(jié)點不壓縮，圖中所示，compress就是1，表示從兩端開始，第1個節(jié)點不做LZF壓縮。compress默認(rèn)是0(不壓縮)，具體可根據(jù)業(yè)務(wù)實際使用場景去配置。

問題：為什么quicklist 的全部ziplist節(jié)點不都壓縮？

list兩端的數(shù)據(jù)變更最為頻繁，像lpush,rpush,lpop,rpop等命令都是在兩端操作，如果頻繁壓縮或解壓縮會代碼不必要的性能損耗。

由結(jié)構(gòu)可見quicklist是一個雙向鏈表的結(jié)構(gòu)，內(nèi)部節(jié)點quicklistnode均保存一個ziplist，每個ziplist中保存一批列表的數(shù)據(jù)(ziplist大小可通過redis.conf中l(wèi)ist-max-ziplist-size配置)，這樣既可以避免大量鏈表指針帶來的內(nèi)存消耗，也可以避免ziplist更新導(dǎo)致的性能損耗。

綜上可見redis在數(shù)據(jù)結(jié)構(gòu)設(shè)計上下了很多心思，幾乎到了變態(tài)的地步，很多結(jié)構(gòu)追求時間與空間的平衡。

總結(jié)

redis 能做到如此之快，除了其內(nèi)存操作、IO模型、極致的數(shù)據(jù)結(jié)構(gòu)外，也包括其精妙的系統(tǒng)設(shè)計，如簡潔的協(xié)議、漸進(jìn)式rehash、key的惰性過期策略、multi事務(wù)操作等等。本文所講為拋磚引玉之作，遠(yuǎn)遠(yuǎn)不能夠涵蓋redis的極致設(shè)計，redis中有更多精彩的設(shè)計值得我們大家去探索去深究。