Redis 是速度非常快的非關(guān)系型（NoSQL）內(nèi)存鍵值數(shù)據(jù)庫哈打，可以存儲鍵和五種不同類型的值之間的映射。

Redis的五種基本類型

String

Redis 是用 C 語言開發(fā)完成的，但在 Redis 字符串中赁项，并沒有使用 C 語言中的字符串葛躏，而是用一種稱為 SDS（Simple Dynamic String）的結(jié)構(gòu)體來保存字符串澈段。

struct sdshdr {
    int len;
    int free;
    char buf[];
}

• len：用于記錄 buf 中已使用空間的長度；
• free：buf 中空閑空間的長度舰攒；
• buf[]：存儲實際內(nèi)容败富。

優(yōu)點：

• 常數(shù)時間內(nèi)可以獲得字符串的長度；
• 避免了緩沖區(qū)溢出摩窃；
• 減少字符串修改時帶來的內(nèi)存重新分配的次數(shù)兽叮；
  • 空間預(yù)分配。如果對 SDS 修改后猾愿，len 的長度小于 1M鹦聪，那么程序?qū)⒎峙浜?len 相同長度的未使用空間。
  • 惰性空間釋放蒂秘。當(dāng)對 SDS 進行縮短操作時泽本，程序并不會回收多余的內(nèi)存空間，而是使用 free 字段將這些字節(jié)數(shù)量記錄下來不釋放材彪，后面如果需要 append 操作，則直接使用 free 中未使用的空間琴儿，減少了內(nèi)存的分配段化。
• 二進制安全。字符串結(jié)束不是'\0'造成，而是由SDS中的len來決定显熏。

應(yīng)用場景：緩存、計數(shù)器晒屎、分布式鎖等喘蟆。

List

Redis列表是簡單的字符串列表，按照插入順序排序鼓鲁≡坦欤可以添加一個元素導(dǎo)列表的頭部（左邊）或者尾部（右邊）。

在版本3.2之前骇吭，Redis 列表list使用兩種數(shù)據(jù)結(jié)構(gòu)作為底層實現(xiàn)橙弱。

• 壓縮列表ziplist；
• 雙向鏈表linkedlist燥狰；

因為雙向鏈表占用的內(nèi)存比壓縮列表要多棘脐， 所以當(dāng)創(chuàng)建新的列表鍵時， 列表會優(yōu)先考慮使用壓縮列表龙致， 并且在有需要的時候蛀缝， 才從壓縮列表實現(xiàn)轉(zhuǎn)換到雙向鏈表實現(xiàn)。

壓縮列表轉(zhuǎn)化成雙向鏈表條件：

創(chuàng)建新列表時 redis 默認使用 redis_encoding_ziplist 編碼目代， 當(dāng)以下任意一個條件被滿足時屈梁， 列表會被轉(zhuǎn)換成 redis_encoding_linkedlist 編碼：

• 試圖往列表新添加一個字符串值嗤练，且這個字符串的長度超過 server.list_max_ziplist_value （默認值為 64 ）。
• ziplist 包含的節(jié)點超過 server.list_max_ziplist_entries （默認值為 512 ）俘闯。

注意：這兩個條件是可以修改的潭苞，在 redis.conf 中。

壓縮列表ziplist：

• 一個特殊的雙向鏈表真朗。沒有維護雙向指針:prev next此疹；而是存儲上一個 entry的長度和 當(dāng)前entry的長度，通過長度推算下一個元素在什么地方遮婶。
• 字段蝗碎、值比較小，才會用ziplist旗扑；

ziplist使用一塊連續(xù)的內(nèi)存蹦骑，每一個節(jié)點（entry）都是連續(xù)存儲的，其包含了如下內(nèi)容：

每一個存儲節(jié)點（entry）都是一個zlentry (zip list entry)致燥。ziplist每一個存儲節(jié)點登疗、都是一個 zlentry，就是上文所說的entry嫌蚤；

typedef struct zlentry {    // 壓縮列表節(jié)點
    unsigned int prevrawlensize, prevrawlen;    // prevrawlen是前一個節(jié)點的長度辐益，prevrawlensize是指prevrawlen的大小，有1字節(jié)和5字節(jié)兩種
    unsigned int lensize, len;  // len為當(dāng)前節(jié)點長度 lensize為編碼len所需的字節(jié)大小
    unsigned int headersize;    // 當(dāng)前節(jié)點的header大小
    unsigned char encoding; // 節(jié)點的編碼方式
    unsigned char *p;   // 指向節(jié)點的指針
} zlentry;

void zipEntry(unsigned char *p, zlentry *e) {   // 根據(jù)節(jié)點指針返回一個enrty
    ZIP_DECODE_PREVLEN(p, e->prevrawlensize, e->prevrawlen);    // 獲取prevlen的值和長度
    ZIP_DECODE_LENGTH(p + e->prevrawlensize, e->encoding, e->lensize, e->len);  // 獲取當(dāng)前節(jié)點的編碼方式脱吱、長度等
    e->headersize = e->prevrawlensize + e->lensize; // 頭大小
    e->p = p;
}

ziplist的主要優(yōu)點是節(jié)省內(nèi)存，但它上面的查找操作只能按順序查找（可以是從前往后箱蝠、也可以從后往前）ziplist將數(shù)據(jù)按照一定規(guī)則編碼在一塊連續(xù)的內(nèi)存區(qū)域，目的是節(jié)省內(nèi)存抡锈，這種結(jié)構(gòu)并不擅長做修改操作。一旦數(shù)據(jù)發(fā)生改動床三，就會引發(fā)內(nèi)存realloc，可能導(dǎo)致內(nèi)存拷貝撇簿。

雙向鏈表linkedlist

當(dāng)鏈表entry數(shù)據(jù)超過512差购、或單個value 長度超過64，底層就會轉(zhuǎn)化成linkedlist編碼欲逃；

linkedlist是標(biāo)準(zhǔn)的雙向鏈表，Node節(jié)點包含prev和next指針稳析，可以進行雙向遍歷；還保存了 head 和 tail 兩個指針彰居，因此，對鏈表的表頭和表尾進行插入的復(fù)雜度都為 (1) —— 這是高效實現(xiàn) LPUSH 陈惰、 RPOP、 RPOPLPUSH 等命令的關(guān)鍵抬闯。

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

• 雙向鏈表linkedlist便于在表的兩端進行push和pop操作，在插入節(jié)點上復(fù)雜度很低溶握，但是它的內(nèi)存開銷比較大。首先平委，它在每個節(jié)點上除了要保存數(shù)據(jù)之外夺谁，還要額外保存兩個指針；其次匾鸥，雙向鏈表的各個節(jié)點是單獨的內(nèi)存塊，地址不連續(xù)勿负，節(jié)點多了容易產(chǎn)生內(nèi)存碎片。
• ziplist存儲在一段連續(xù)的內(nèi)存上奴愉，所以存儲效率很高琅摩。但是房资，它不利于修改操作，插入和刪除操作需要頻繁的申請和釋放內(nèi)存檀头。特別是當(dāng)ziplist長度很長的時候轰异，一次realloc可能會導(dǎo)致大批量的數(shù)據(jù)拷貝岖沛。

版本3.2之后，重新引入 quicklist搭独，列表的底層都由quicklist實現(xiàn)婴削。

quickList

可以認為quickList，是ziplist和linkedlist二者的結(jié)合牙肝；quickList將二者的優(yōu)點結(jié)合起來唉俗。quickList是一個ziplist組成的雙向鏈表，每個節(jié)點使用ziplist來保存數(shù)據(jù)惊奇。

typedef struct quicklistNode {
    struct quicklistNode *prev; //上一個node節(jié)點
    struct quicklistNode *next; //下一個node
    unsigned char *zl;            //保存的數(shù)據(jù) 壓縮前ziplist 壓縮后壓縮的數(shù)據(jù)
    unsigned int sz;             /* ziplist size in bytes */
    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; /* was this node previous compressed? */
    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; /* LZF size in bytes*/
    char compressed[];
} quicklistLZF;

typedef struct quicklist {
    quicklistNode *head; //頭結(jié)點
    quicklistNode *tail; //尾節(jié)點
    unsigned long count;        /* total count of all entries in all ziplists */
    unsigned int len;           /* number of quicklistNodes */
    int fill : 16;              /* fill factor for individual nodes *///負數(shù)代表級別互躬，正數(shù)代表個數(shù)
    unsigned int compress : 16; /* depth of end nodes not to compress;0=off *///壓縮級別
} quicklist;

• quickList就是一個標(biāo)準(zhǔn)的雙向鏈表的配置，有head 有tail颂郎；
• 每一個節(jié)點是一個quicklistNode吼渡，包含prev和next指針；
• 每一個quicklistNode 包含 一個ziplist乓序，*zp 壓縮鏈表里存儲鍵值寺酪；

所以quicklist是對ziplist進行一次封裝，使用小塊的ziplist來既保證了少使用內(nèi)存替劈，也保證了性能寄雀。

應(yīng)用場景：鏈表、隊列陨献、微博關(guān)注人時間軸列表等盒犹。

Set

Set 就是一個集合,集合的概念就是一堆不重復(fù)值的組合。利用 Redis 提供的 Set 數(shù)據(jù)結(jié)構(gòu),可以存儲一些集合性的數(shù)據(jù)眨业。

Set的底層存儲結(jié)構(gòu)底層使用了intset和hashtable兩種數(shù)據(jù)結(jié)構(gòu)急膀，intset可以理解為數(shù)組，hashtable就是普通的哈希表（key為set的值龄捡，value為null）卓嫂。使用intset存儲必須滿足下面兩個條件，否則使用hashtable聘殖，條件如下：

• 集合對象保存的所有元素都是整數(shù)值晨雳；
• 集合對象保存的元素數(shù)量不超過512個。

intset數(shù)據(jù)結(jié)構(gòu)

intset內(nèi)部其實是一個數(shù)組（int8_t coentents[]數(shù)組）奸腺，而且存儲數(shù)據(jù)的時候是有序的餐禁，因為在查找數(shù)據(jù)的時候是通過二分查找來實現(xiàn)的。

typedef struct intset {
    // 編碼方式
    uint32_t encoding;
    // 集合包含的元素數(shù)量
    uint32_t length;
    // 保存元素的數(shù)組
    int8_t contents[];
} intset;

應(yīng)用場景：去重突照、贊帮非、踩喜鼓、共同好友等。

Hash

Redis hash 是一個string類型的field和value的映射表庄岖，hash特別適合用于存儲對象。

Redis的哈希對象的底層存儲可以使用ziplist（壓縮列表）和hashtable心剥。當(dāng)hash對象可以同時滿足一下兩個條件時优烧，哈希對象使用ziplist編碼链峭。

• 哈希對象保存的所有鍵值對的鍵和值的字符串長度都小于64字節(jié)；
• 哈希對象保存的鍵值對數(shù)量小于512個熙卡。

Redis的hash架構(gòu)就是標(biāo)準(zhǔn)的hashtab的結(jié)構(gòu)驳癌，通過掛鏈解決沖突問題役听。

應(yīng)用場景：用戶信息、Hash 表等甜滨。

Zset

Redis 有序集合和集合一樣也是string類型元素的集合艳吠，且不允許重復(fù)的成員孽椰。

不同的是每個元素都會關(guān)聯(lián)一個double類型的分數(shù)黍匾。redis正是通過分數(shù)來為集合中的成員進行從小到大的排序呛梆。zset底層的存儲結(jié)構(gòu)包括ziplist或skiplist，在同時滿足以下兩個條件的時候使用ziplist纹腌，其他時候使用skiplist，兩個條件如下：

• 有序集合保存的所有元素的長度小于64字節(jié)莱褒；
• 有序集合保存的元素數(shù)量小于128個涎劈。

當(dāng)skiplist作為zset的底層存儲結(jié)構(gòu)的時候，使用skiplist按序保存元素及分值谅海，使用dict來保存元素和分值的映射關(guān)系扭吁。

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

typedef struct zskiplist {
    //表頭節(jié)點和表尾節(jié)點
   struct zskiplistNode *header, *tail;
    //表中節(jié)點的的數(shù)量
   unsigned long length;
    //表中層數(shù)最大的節(jié)點層數(shù)
   int level;
 } zskiplist;

前進指針：用于從表頭向表尾方向遍歷智末；

后退指針：用于從表尾向表頭方向回退一個節(jié)點徒河，和前進指針不同的是，前進指針可以一次性跳躍多個節(jié)點由蘑，后退指針每次只能后退到上一個節(jié)點尼酿。

跨度：表示當(dāng)前節(jié)點和下一個節(jié)點的距離植影，跨度越大，兩個節(jié)點中間相隔的元素越多鹿响。

應(yīng)用場景：訪問量排行榜惶我、點擊量排行榜等博投。

編碼轉(zhuǎn)化

Redis 使用對象（redisObject）來表示數(shù)據(jù)庫中的鍵值，當(dāng)我們在 Redis 中創(chuàng)建一個鍵值對時听怕，至少創(chuàng)建兩個對象，一個對象是用做鍵值對的鍵對象松忍，另一個是鍵值對的值對象鸣峭。

typedef struct redisObject{
    //類型
   unsigned type:4;
   //編碼
   unsigned encoding:4;
   //指向底層數(shù)據(jù)結(jié)構(gòu)的指針
   void *ptr;
    //...
 }robj;

其中 type 字段記錄了對象的類型酥艳，包含字符串對象充石、列表對象、哈希對象拉岁、集合對象惰爬、有序集合對象。

過期數(shù)據(jù)刪除

三種刪除策略：

• 定時刪除陵叽。在這是鍵的過期時間的同時巩掺，創(chuàng)建一個定時器 Timer页畦，讓定時器在鍵過期時間來臨時立即執(zhí)行對過期鍵的刪除；
• 惰性刪除独令。鍵過期后不管记焊，每次讀取該鍵時栓撞，判斷該鍵是否過期，如果過期刪除該鍵返回空瓢颅；
• 定期刪除弛说。每隔一段時間對數(shù)據(jù)庫中的過期鍵進行一次檢查木人。

總之

Redis性能如此高的原因，有如下幾點：

• 純內(nèi)存操作渔嚷；
• 單線程稠曼；
• 高效的數(shù)據(jù)結(jié)構(gòu)霞幅；
• 合理的數(shù)據(jù)結(jié)構(gòu)編碼。