Redis簡介

Redis全稱為Remote Dictionary Server(遠程字典服務) 是一個由Salvatore Sanfilippo開發(fā)的一款開源的糠馆，使用C語言編寫，支持網絡除嘹、基于內存写半，可選持久化的Key-Value數據庫；其支持豐富的數據類型：字符串(String)憾赁、哈希(Map)污朽、 列表(list)、 集合(sets) 和 有序集合(sorted sets)龙考、位圖(bitmaps)、HyperLogLogs等數據結構矾睦。目前開發(fā)主要由Redis Labs公司贊助晦款，最新穩(wěn)定版為6.2.4。

Redis 快到什么程度枚冗？

在探究redis為什么這么快之前缓溅，我們先來分析下影響一個系統快慢的指標有哪些。

• 響應時間：指系統對請求做出響應的時間赁温，用戶對該指標有直觀感受坛怪。

• 吞吐量：指單位時間內處理請求的數量淤齐。

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

吞吐量 = 并發(fā)數量/響應時長

因此響應時長越短袜匿，并發(fā)數越高更啄，吞吐量就越好，應用響應能力就越優(yōu)秀居灯。

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

• 100并發(fā),常用命令每秒執(zhí)行次數
  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的一般讀寫速度可以達到10w+以上噪径，范圍查詢也有1w+ qps的表現贰拿，通過pipeline批量執(zhí)行讀寫更是可以達到50w+以上。

Redis 為什么這么快熄云？

系統實現來看

• key-value（字典）結構 字典結構的時間復雜度為O(1)膨更，類比java中的HashMap。

• 絕大部分請求是純粹的內存操作缴允，速度非臣允兀快。 redis是一個內存數據庫练般，內存讀寫相對于磁盤IO來說要快幾個數量級矗漾，系統運行如果需要等待磁盤I/O的完成，將導致整個系統的性能下降薄料。

• C語言編寫 C語言簡潔高效敞贡，可以直接操作內存，編譯后生成的機器碼基本上和直接寫匯編生成的機器碼是相當的摄职；但語法限制不嚴格誊役，面向過程缺乏封裝，難以掌握谷市，對使用者要求高蛔垢。

IO模型

image.png

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

• 基于非阻塞的IO多路復用機制括蝠。

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

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

  • 避免線程不安全的情況，簡化數據結構和算法的實現（不用考慮并發(fā)）婆跑；

采用的單線程而不是因為單線程性能高而使用單線程此熬，主要是因為單線程實現很簡單，且限制redis性能主要是內存及網絡IO滑进。實際上Redis6.0中的多線程也只是IO多線程犀忱，將主線程的 IO 讀寫任務拆分出來給一組獨立的線程執(zhí)行，使得多個 socket 的讀寫可以并行化扶关，命令執(zhí)行仍是單線程阴汇。

Redis的數據結構是精心設計的

redis主要的基本數據結構有

• string 字符串類型

• list 列表類型

• hash 哈希表類型

• set 無序集合類型

• zset 有序集合類型

Redis的核心對象為redisObject位于server.h源碼中，結構定義如下

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

type類型

encoding 編碼

不同類型編碼與對象的結構關系

image.png

image.png

下面我們sds及l(fā)ist兩種類型為例講解redis的數據結構設計

string

Redis中节槐，字符串是可以修改的搀庶，長度是動態(tài)可變的，在底層它是以字節(jié)數組的形式存在的铜异，被稱為簡單動態(tài)字符串sds(simple dynamic string)哥倔。數據結構定義如下：

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

image-20210618215247254.png

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

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

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

2. 增長時空間預分配,減少內存的頻繁分配，惰性內存空間回收缆镣。

   • C字符串在處理增長或者縮短操作時芽突，程序會對這個C字符串的數組進行一次內存重分配操作。

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

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

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

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

   • 當 SDS 進行字符串擴充時岗喉，首先會檢查當前的字節(jié)數組的長度是否足夠秋度。如果不夠的話，會先進行自動擴容钱床，然后再進行字符串操作荚斯。

4. 二進制安全

   • SDS的API都是二進制安全的。

   • SDS的buf屬性為字節(jié)數組查牌，程序不會對其中的數據做任何的限制事期，數據存進去是什么樣子，讀出來就是什么樣子纸颜，因此可以用來保存的音頻兽泣、圖片、視頻等數據胁孙。

list

版本3.2之前唠倦，當列表對象中元素的長度比較小或者數量比較少的時候，采用ziplist來存儲浊洞，當列表對象中元素的長度比較大或者數量比較多的時候牵敷，則會轉而使用雙向列表linkedlist來存儲。

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

• 雙向鏈表linkedlist節(jié)點帶有prev法希、next指針枷餐、head指針和tail指針，獲取前置節(jié)點苫亦、后置節(jié)點毛肋、表頭節(jié)點和表尾節(jié)點的復雜度都是O(1)，便于在表的兩端進行push和pop操作屋剑，但是它的內存開銷比較大润匙，每個node上除了要保存數據之外，還要額外保存兩個指針唉匾；另外雙向鏈表的各個節(jié)點是單獨的內存塊孕讳，地址不連續(xù)匠楚，容易產生內存碎片。

• ziplist存儲在一段連續(xù)的內存上厂财，由一系列特殊編碼的連續(xù)內存塊組成的順序型數據結構芋簿，查找，添加璃饱、修改与斤、刪除操作時間復雜度為O(n)，且添加荚恶、修改撩穿、刪除時需要頻繁的申請和釋放內存，因此它適合數據比較小的情況谒撼。

ziplist 結構

redis/src目錄下ziplist.c中：

image.png

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

• zltail：32bit無符號整數嗤栓，記錄最后一個entry的偏移量冻河，方便快速定位到最后一個entry；

• zllen：16bit無符號整數茉帅，記錄entry的個數叨叙；

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

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

image.png

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

ziplist entry結構

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é)進行表示肋演，此時抑诸，previous_entry_length的第一個字節(jié)是固定的254（0xFE）（作為這種情況的一個標志）烂琴，后面4個字節(jié)才表示前一個元素的長度。

encoding Redis為了節(jié)約空間哼鬓，對encoding字段進行復雜的設計监右，Redis通過encoding來判斷存儲數據的類型边灭。

• 00xxxxxx 最大長度位 63 的短字符串异希，后面的6個位存儲字符串的位數；

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

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

• 11000000 表示 int16授药；

• 11010000 表示 int32；

• 11100000 表示 int64呜魄；

• 11110000 表示 int24悔叽；

• 11111110 表示 int8；

• 11111111 表示 ziplist 的結束爵嗅，也就是 zlend 的值 0xFF娇澎；

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

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

什么條件下會用ziplist戚啥？

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

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

  
  
  image-20210618214019087.png

image-20210618214349155.png

quickList

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

image.png

其結構源碼位于quicklist.h中

typedef struct quicklistNode {
    struct quicklistNode *prev; /*指向鏈表前一個節(jié)點的指針*/
    struct quicklistNode *next; /*指向鏈表后一個節(jié)點的指針*/
    unsigned char *zl;
    unsigned int sz;             /* ziplist占用byte數*/
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* 數據類型，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é)數組*/
} quicklistLZF;

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

image.png

黃色背景是普通的ziplist節(jié)點炫彩，紫色背景是被壓縮后的ziplist節(jié)點(LZF節(jié)點)，LZF是種無損壓縮算法絮短。 redis為了節(jié)省內存空間江兢，會將quicklist的節(jié)點用LZF壓縮后存儲，不是所有節(jié)點均壓縮丁频，可以通過配置compress的值杉允，compress為0表示所有節(jié)點都不壓縮邑贴，否則就表示從兩端開始有多少個節(jié)點不壓縮，圖中所示叔磷，compress就是1拢驾，表示從兩端開始，第1個節(jié)點不做LZF壓縮改基。compress默認是0(不壓縮)繁疤，具體可根據業(yè)務實際使用場景去配置。

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

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

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

綜上可見redis在數據結構設計上下了很多心思挠羔，幾乎到了變態(tài)的地步井仰，很多結構追求時間與空間的平衡。

總結

redis 能做到如此之快褥赊，除了其內存操作糕档、IO模型、極致的數據結構外拌喉，也包括其精妙的系統設計速那，如簡潔的協議、漸進式rehash尿背、key的惰性過期策略端仰、multi事務操作等等。本文所講為拋磚引玉之作田藐，遠遠不能夠涵蓋redis的極致設計荔烧，redis中有更多精彩的設計值得我們大家去探索去深究。