支持的數(shù)據(jù)結(jié)構(gòu)

String/Hash/Set/Zset/List

RedisObject 核心對象

image.png

image.png

image.png

/*
 * Redis 對象
 */
typedef struct redisObject {

    // 類型
    unsigned type:4;

    // 編碼方式
    unsigned encoding:4;

    // LRU - 24位, 記錄最末一次訪問時間（相對于lru_clock）; 或者 LFU（最少使用的數(shù)據(jù)：8位頻率，16位訪問時間）
    unsigned lru:LRU_BITS; // LRU_BITS: 24

    // 引用計數(shù)
    int refcount;

    // 指向底層數(shù)據(jù)結(jié)構(gòu)實例
    void *ptr;

} robj;

對象共享機制

redis會將常見的值放入一個共享對象中，避免了程序重新分配的麻煩，類似于jvm中的常量池。
預(yù)分配的對象如下：

1. 各種命令的返回值，如成功時返回的OK，錯誤的ERROR，命令入隊事物時返回的QUEUE等。
2. 包括0在內(nèi)，小于REDIS_SHARED_INTEGERS（默認為10000）的所有整數(shù)。
   注意：共享對象只能被字典和雙向鏈表這種帶有指針的數(shù)據(jù)結(jié)構(gòu)引用。

引用計數(shù)和對象的銷毀

redis內(nèi)的refcount，如果為0，則表示可以回收。

1. refcount表示這個對象被引用了多少次
2. 當?shù)谝淮伪粍?chuàng)建時，refcount為1
3. 當對這個對象進行共享時，refcount+1
4. 當使用完對象或引用被消除時，refcount-1
5. 當refcount為0時，這個redisobject和引用的內(nèi)存結(jié)構(gòu)會被消除

SDS字符串

Redis3.2之前

typedef char *sds
struct sdschar {
    // buf[] 中已使用的字節(jié)數(shù)
    int len;
    // buf[] 中未使用的字節(jié)數(shù)
    int free;
    // 字符數(shù)組，用于實際存儲字符串內(nèi)容
    char buf[];
}

image.png

Redis3.2之后

image.png

1. 杜絕緩沖區(qū)溢出
   1. 通過len來獲取字符串的長度，而不是空字符來決定結(jié)尾，在內(nèi)存重分配下，杜絕緩沖區(qū)溢出的情況。
2. 獲取字符串的長度是O(1)復(fù)雜度
   1. 通過len來獲取長度，而C中是通過遍歷得來，是O(n)復(fù)雜度。
3. 減少修改字符串時，帶來的內(nèi)存重分配次數(shù)
   1. 在修改的過程中，通過len和free來確定空間大小長度，在內(nèi)存空間夠用的情況下，可以減少內(nèi)存重分配。
4. 惰性空間釋放
   1. SDS提供了API來進行空間釋放，對于空閑空間，可以在有需要的情況下進行釋放。
5. 二進制安全
   1. C中不能保存空字符，會被認為是字符串的結(jié)尾，這種限制使得C只能保存文本數(shù)據(jù)，而不能保存圖片/音頻/視頻等壓縮的二進制。
   2. 但是Redis中不是通過空字符，而是通過len來判斷字符串長度，所以不存在這個問題。
6. 兼容部分C的函數(shù)
   1. 雖然SDS的API都是二進制安全的，但是依然遵循C中以空字符結(jié)尾的規(guī)定。

image.png

ZipList 壓縮表

整體存儲格式：

image.png

• zlbytes: unint32_t，存儲的是整個ziplist占用的字節(jié)數(shù)
• zltail: unint32_t，指最后一個entry的偏移量，為了快速完成定位，實現(xiàn)pop等操作
• zllen: unint16_t，指整個ziplist內(nèi)entry的數(shù)量，最大值為65535，如果entry的數(shù)量超過了最大值限制，那么該值會固定為65535，獲取全部entry數(shù)量則需要通過遍歷來獲得
• zlend: 1byte，終止字節(jié)，為0xFF，ziplist保證在任何情況下，entry的首字節(jié)都不會為0xFF

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

1. 一般結(jié)構(gòu) <prevlen> <encoding> <entry-data>

   • prevlen: 前一個entry的大小
     1. 當前一個entry的長度小于254時，prevlen為1個字節(jié)。
     2. 當大于254時，為5個字節(jié)，且第一個字節(jié)設(shè)置為254，后4個字節(jié)表示前一個字節(jié)的長度。
   • encoding: 編碼格式
     1. 前2位表示類型，為11時，表示存儲的是int，此時encoding的后幾位存儲的是int的數(shù)據(jù)。
     2. 不為11時，存儲的是string，此時encoding的后幾位表示的是string的字符串長度。
   • entry-data: 用于存儲entry的數(shù)據(jù)

2. 特殊結(jié)構(gòu) <prevlen> <encoding>

   • 當encoding為int時，encoding和entry-data合并，都在encoding中展示，為了節(jié)省空間。

為什么ziplist特別省內(nèi)存

1. 對于數(shù)組，每個元素占用的內(nèi)存是一致的，取決于最大的元素，需要預(yù)留空間。
2. ziplist盡量細化每個元素，通過encoding的格式，按照每個元素實際的大小來存儲。
3. 在遍歷時如何定位元素，為了解決遍歷，增加記錄上個元素的length，所以增加了prevlen。

ziplist的缺點

1. ziplist不預(yù)留內(nèi)存空間，每次操作都會重新申請內(nèi)存空間，每次刪除也會立即縮容。
2. 節(jié)點如果擴容，會導(dǎo)致entry的長度增加，在極端情況下，會導(dǎo)致prevlen的長度從1個字節(jié)變成5個字節(jié)，且導(dǎo)致鏈式反應(yīng)，每個entry都會需要進行prevlen的擴容。

QuickList 快表 （Redis3.2之后）

image.png

1. 基于ziplist和雙向鏈表2種數(shù)據(jù)結(jié)構(gòu)融合而成的數(shù)據(jù)結(jié)構(gòu)
2. 最外層是雙向鏈表，Node節(jié)點相互連接，Node內(nèi)的數(shù)據(jù)指針指向ziplist
3. quicklist內(nèi)單節(jié)點最大存儲為8kb
4. 實現(xiàn)了基于lzf算法的壓縮api，將中間不常用的節(jié)點進行壓縮來節(jié)省內(nèi)存

Dict 字典/哈希表

image.png

1. 當發(fā)生hash沖突是，通過外鏈法解決沖突

2. 內(nèi)部含有2個hash表，默認使用hash[0]，當達到需要擴容的階段時，進行rehash，copy到hash[1]中。

3. rehash是漸進式rehash，每次操作數(shù)據(jù)時，將對應(yīng)數(shù)據(jù)copy到hash[1]中，并清除hash[0]中的數(shù)據(jù)；直到所有數(shù)據(jù)均copy到hash[1]中，若有些數(shù)據(jù)一直未被訪問，則采用定時進行遷移。

4. 觸發(fā)擴容條件：
   哈希表的負載因子計算：負載因子 = 哈希表已保存節(jié)點數(shù)量 / 哈希表大小
   load_factor = ht[0].used / ht[0].size

   1、服務(wù)器目前沒有在執(zhí)行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的負載因子大于等于 1。

   2、服務(wù)器目前正在執(zhí)行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的負載因子大于等于 5。

5. 觸發(fā)縮容條件：
   負載因子小于0.1

IntSet 整數(shù)集

Redis在存儲集合時，如果集合內(nèi)只包含整數(shù)且數(shù)目較少時，會采用IntSet來存儲。

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

• encoding：表示編碼方式，取值有3個：INTSET_ENC_INT16, INTSET_ENC_INT32, INTSET_ENC_INT64
• length: 存儲的整數(shù)的個數(shù)
• contents: 實際指向的存儲數(shù)據(jù)的內(nèi)存區(qū)域，雖然定義為int8_t，但實際以encoding為準

整數(shù)集合的升級

在int16類型的集合內(nèi)插入一個int32的數(shù)據(jù)：

1. 根據(jù)新元素的數(shù)據(jù)類型，對內(nèi)存空間進行擴容，分配為按照int32來分配的內(nèi)存空間
2. 將底層原始數(shù)組的數(shù)據(jù)類型轉(zhuǎn)換為新的長度，并遷移到新分配的內(nèi)存空間中
3. 改變encoding的值，并length+1

當最大元素刪除后，是否需要降級？
不會，為了減少開銷

ZipList 跳表

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

/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

skiplist和平衡樹的對比

1. skiplist更適用于范圍查找，只需要在底層鏈表中進行遍歷查找；而平衡樹需要重新進行中序查找。
2. skiplist和平衡樹的查詢復(fù)雜度都是O(logn），但是實現(xiàn)起來更簡單。
3. 在節(jié)點插入變更時，skiplist更為簡單一些，只需要插入節(jié)點并修改相鄰指針，而平衡樹在節(jié)點更新時會需要更多的操作，阻塞時間也會更長。

Redis的對象和編碼格式的關(guān)系

String支持3種編碼格式 -> RAW / INT / EMBSTR

• RAW

  1. 長度大于44字節(jié)的字符串
  2. 新增時會生成2個對象，redisObject和SDS，指針指向SDS，所以需要2塊內(nèi)存空間。

• INT

  1. 可以保存為long表示的整數(shù)值
  2. 新增時是1塊內(nèi)存空間

• EMBSTR

  1. 長度小于44字節(jié)的字符串
  2. 新增時分配1塊內(nèi)存空間，redisObject和SDS是連續(xù)的。但是當字符串需要修改時，只能銷毀重新分配，所以EMBSTR是只讀的。
  3. 因為在修改時只能銷毀并重新分配，所以修改一定會變更為RAW類型，無論是否到達44字節(jié)。

ps： redis對于浮點數(shù)類型也是作為字符串保存的，在需要的時候再轉(zhuǎn)換為浮點數(shù)類型

List -> quickList

從目前的版本（6.0）來看，List僅支持quickList（之前的版本有l(wèi)inked和ziplist這2種編碼）。

Hash -> ziplist/hashtable(dict)

image.png

當同時滿足以下2個條件時，使用ziplist：

1. 列表保存的元素小于512個（ps：可以通過配置修改）
2. 每個元素長度小于64字節(jié)

Set -> intset/hashtable(dict)

image.png

image.png

當同時滿足以下2個條件時，使用intset

1. 集合中所有元素都是整數(shù)
2. 集合對象中所有元素不超過512個（ps：可以通過配置set-max-intset-entries修改）

zSet -> zipList/dict&skipList

tips：對于skipList的編碼格式，其實是同時采用了dict和skiplist的數(shù)據(jù)結(jié)構(gòu)來存儲
說明：有序集合本身使用dict或skiplist其中一種都可以實現(xiàn)，如果單獨使用dict來實現(xiàn)，那么查找可以達到O(1)的復(fù)雜度，但是每次范圍查詢排序需要進行額外操作；如果單獨使用skiplist，雖然可以使用范圍操作，但是查找復(fù)雜度卻是O(logn)，所以redis采用了2種數(shù)據(jù)結(jié)構(gòu)混合。但雖然同時使用了2種數(shù)據(jù)結(jié)構(gòu)，但數(shù)據(jù)其實只有1份，通過指針指向到對應(yīng)地址。

image.png

當同時滿足以下2個條件，使用ziplist編碼：

1. 保存的元素數(shù)量小于128個（可配置）
2. 保存的元素長度都小于64個（可配置）

參考文章：https://www.pdai.tech/md/db/nosql-redis/db-redis-x-redis-ds.html