Redis(一)-底層數據結構

概述

本節(jié)主要分析Redis key-value及5大基本數據類型背后對應的具體數據結構，只有了解了底層數據結構才能真正做到靈活掌握基本數據類型的使用

1. 全局哈希表

全局哈希表用于存儲所有的鍵值對，結構類似HashMap，由哈希桶數組 + entry鏈表組成


Redis全局哈希表.png

1.1 哈希桶數組

--結構定義
typedef struct dictht {  
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;
  • **table: 哈希表數組，數組的每個項是dictEntry鏈表的頭結點指針
  • **size: 哈希表大小；在redis的實現(xiàn)中，size也是觸發(fā)擴容的閾值
  • **sizemask: 哈希表大小掩碼，用于計算索引值；總是等于size-1
  • **used: 哈希表中保存的節(jié)點的數量

1.2 dictEntry

--結構定義
typedef struct dictEntry {  
    void *key;  
    void *val;  
    struct dictEntry *next;  
} dictEntry;
  • *key: 指向基本對象結構RedisObject(key都是字符串對象)的指針，Redis鍵值對中的每一個鍵值都是用RedisObject保存
  • *val: 指向基本對象結構RedisObject的指針，val可以是String/List/Set/ZSet/Hash
  • *next: 指向鏈表中下一個dictEntry指針

1.3 RedisObject

--結構定義
typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:REDIS_LRU_BITS; 
    int refcount;
    void *ptr;
} robj;
  • type: 類型，即5種基本數據類型String/Set/List/Hash/Sorted Set
  • encoding: 編碼方式，用來表示Redis中實現(xiàn)各個基本類型的底層數據結構，例如SDS、壓縮列表、哈希表、跳表等
  • lru: 記錄了這個對象最后一次被訪問的時間，用于淘汰過期的鍵值對
  • refcount: 記錄了對象的引用計數；
  • *ptr: 指向數據的指針

1.4 哈希沖突的處理

類比HashMap很容易想到全局哈希表這種結構的兩個問題

1.4.1 哈希沖突怎么辦？

通常處理哈希沖突的方法有拉鏈法和鏈表法，通過全局哈希表結構能看出Redis使用鏈表法

1.4.2 數組擴容怎么辦？

哈希表保存的鍵值對逐漸地增多， dictEntry鏈表長度就會越來越長，導致查詢變慢，就需要進行擴容；為了使rehash操作更高效，避免同時復制大量數據，Redis默認使用兩個全局哈希表 + 漸進式rehash進行操作

  • 開始插入數據時，默認使用哈希表1，當需要擴容rehash時才使用哈希表2
  • 給哈希表2分配更大的空間，例如是當前哈希表1大小的兩倍
  • redis每處理一個請求時，從哈希表1中的第一個索引位置開始，順帶著將這個索引位置上的所有dictEntry鏈表拷貝到哈希表2中；等處理下一個請求時，再順帶拷貝哈希表1中的下一個索引位置的dictEntry鏈表
  • 釋放哈希表1的內存空間

2. int/embstr/raw

  1. 當保存64位有符號整數時，String類型會把它保存為一個8字節(jié)的Long類型整數，即int編碼方式；
  2. 當保存的數據中包含字符時，String類型就會用簡單動態(tài)字符串SDS結構體來保存，對應embstr或raw編碼
  3. 當字符串比較短(小于44字節(jié))時，RedisObject中的元數據(type/encoding/lru/refcount)、指針(ptr)和SDS是一塊連續(xù)的內存區(qū)域，這樣就可以避免內存碎片，即embstr編碼
  4. 當字符串比較大(大于44字節(jié))時，SDS的數據量就開始變多了，Redis會給SDS分配獨立的空間，并用指針指向SDS結構，即raw編碼
--SDS結構定義
struct sdshdr {
    int len; 
    int alloc;
    char buf[]; 
};

buf：字節(jié)數組，保存實際數據。為了表示字節(jié)數組的結束，Redis會自動在數組最后加一個“\0”，這就會額外占用1個字節(jié)的開銷
len：占4個字節(jié)，表示buf的已用長度
alloc：也占個4字節(jié)，表示buf的實際分配長度，一般大于len

String編碼 (1).png

3. linkedlist/ziplist/quicklist

Redis3.2之前，列表對象其底層存儲結構可以有兩種，即：linkedlist和ziplist，而在Redis 3.2之后，列表對象底層存儲結構優(yōu)化成為了另一種:quicklist。而quicklist可以認為是linkedlist和ziplist的結合體

3.1 linkedlist

linkedlist是一個雙向列表，每個節(jié)點都會存儲指向上一個節(jié)點和指向下一個節(jié)點的指針。linkedlist因為每個節(jié)點的空間是不連續(xù)的，所以可能會造成過多的空間碎片


redis-linkedlist.png
typedef struct list {
    listNode *head;//頭節(jié)點
    listNode *tail;//尾節(jié)點
    void *(*dup)(void *ptr);//節(jié)點值復制函數
    void (*free)(void *ptr);//節(jié)點值釋放函數
    int (*match)(void *ptr, void *key);//節(jié)點值對比函數
    unsigned long len;//節(jié)點數量
} list;

typedef struct listNode {
    struct listNode *prev;//前一個節(jié)點
    struct listNode *next;//后一個節(jié)點
    void *value;//值(字符串對象)
} listNode;

3.2 ziplist

ziplist是為了節(jié)省內存而開發(fā)的一種壓縮列表數據結構，由一系列連續(xù)內存塊組成的順序型數據結構；ziplist和linkedlist最大的區(qū)別是ziplist不存儲指向上一個節(jié)點和下一個節(jié)點的指針，存儲的是上一個節(jié)點的長度和當前節(jié)點的長度，犧牲了部分讀寫性能來換取更高的內存利用率，是一種時間換空間的思想


redis-ziplist.png
  • zlbytes: 列表長度
  • zltail: 列表尾的偏移量
  • zllen: 列表中的 entry 個數
  • zlend: 列表結束
  • entry prev_len: 表示前一個 entry 的長度，prev_len有兩種取值情況：1字節(jié)或5字節(jié)。取值1字節(jié)時，表示上一個entry的長度小于254字節(jié)。雖然1字節(jié)的值能表示的數值范圍是0到255，但是壓縮列表中zlend的取值默認是255，因此，就默認用255表示整個壓縮列表的結束，其他表示長度的地方就不能再用255這個值了。所以，當上一個entry長度小于254字節(jié)時，prev_len取值為1字節(jié)，否則，就取值為5字節(jié)
  • entry len: 表示自身長度，4 字節(jié)
  • encoding: 表示編碼方式，1 字節(jié)；
  • data: 保存實際數據
--entry使用時需要序列化成zlentry再使用
typedef struct zlentry {
    unsigned int prevrawlensize; /* 內存中編碼后的prevrawlen用了多少字節(jié) */
    unsigned int prevrawlen;     /* 前一個entry占用的長度，主要是為了entry之間跳轉 */
    unsigned int lensize;        /* 內存中編碼后的len用了多少字節(jié) */
    unsigned int len;            /* 當前entry的長度，如果是string則表示string的長度，如果是整數，則len依賴于具體數值大小。*/
    unsigned int headersize;     /* prevrawlensize + lensize. entry的head部分用了多少字節(jié) */
    unsigned char encoding;      /* 當前entry的編碼格式 */
    unsigned char *p;            /* 指向數據域的指針 */
} zlentry;

3.3 quicklist

3.2之后引入的，統(tǒng)一用quicklist來存儲列表對象，可以理解成是一種混合結構,quicklist 是 ziplist 和 linkedlist 的混合體，它將 linkedlist 按段切分，每一段使用 ziplist 來緊湊存儲，多個 ziplist 之間使用雙向指針串接起來。這樣既滿足了快速的插入刪除性能，又不會出現(xiàn)太大的空間冗余


redis-quicklist.png
typedef struct quicklist {
    quicklistNode *head;//列表頭節(jié)點
    quicklistNode *tail;//列表尾節(jié)點
    unsigned long count;//ziplist中一共存儲了多少元素，即:每一個quicklistNode內的count相加
    unsigned long len; //雙向鏈表的長度，即quicklistNode的數量
    int fill : 16;//填充因子
    unsigned int compress : 16;//壓縮深度 0-不壓縮
} quicklist;

typedef struct quicklistNode {
    struct quicklistNode *prev;//前一個節(jié)點
    struct quicklistNode *next;//后一個節(jié)點
    unsigned char *zl;//當前指向的ziplist或者quicklistLZF
    unsigned int sz;//當前ziplist占用字節(jié)
    unsigned int count : 16;//ziplist中存儲的元素個數，16字節(jié)(最大65535個)
    unsigned int encoding : 2; //是否采用了LZF壓縮算法壓縮節(jié)點 1：RAW 2:LZF
    unsigned int container : 2; //存儲結構，NONE=1, ZIPLIST=2
    unsigned int recompress : 1; //當前ziplist是否需要再次壓縮(如果前面被解壓過則為true，表示需要再次被壓縮)
    unsigned int attempted_compress : 1;//測試用 
    unsigned int extra : 10; //后期留用
} quicklistNode;

4. intset

當一個集合只包含整數值元素， 并且這個集合的元素數量不多時， Redis 就會使用整數集合作為集合鍵的底層實現(xiàn)，來節(jié)約內存；但是由于是連續(xù)空間，修改效率不高


redis-intset.png
typedef struct intset {
    uint32_t encoding;   // 編碼方式
    uint32_t length;     // 集合包含的元素數量
    int8_t contents[];   // 保存元素的數組，從小到大排序，無重復
} intset;

encoding記錄了當前集合的編碼方式，主要有三種：

  • INTSET_ENC_INT16: 此時contents[]內的每個元素都是一個int16_t類型的整數值，范圍是：-32768 ~ 32767(-2^15 ~ 2^15-1)
  • INTSET_ENC_INT32: 此時contents[]內的每個元素都是一個int32_t類型的整數值，范圍是：-2147483648 ~ 2147483647(-2^31 ~ 2^31-1)
  • INTSET_ENC_INT64: 此時contents[]內的每個元素都是一個int64_t類型的整數值，范圍是：-9223372036854775808 ~ 9223372036854775807(-2^63 ~ 2^63-1)

5. hashtable

hashtable用來存儲key-value格式數據，數據結構類似java種hashmap和全局哈希表


redis-hashtable.png
/* 字典 */
typedef struct dict {
    dictType *type;      // 類型特定函數
    void *privdata;      // 私有數據
    dictht ht[2];        // 哈希表，注意這里是兩個哈希表
    int rehashidx;       // rehash 索引，當 rehash 不在進行時，值為 -1
    int iterators;       // 目前正在運行的安全迭代器的數量
} dict;

/* 哈希表 */
typedef struct dictht {
    dictEntry **table;      // 哈希表數組，用鏈表方式解決沖突問題
    unsigned long size;     // 哈希表大小
    unsigned long sizemask; // 哈希表大小掩碼，用于計算索引值，總是等于 size - 1
    unsigned long used;     // 該哈希表已有節(jié)點的數量
} dictht;

/* 字典entry */
typedef struct dictEntry {  
    void *key;              //指向基本對象結構RedisObject(key都是字符串對象)的指針
    void *val;              //指向基本對象結構RedisObject的指針，val可以是String/List/Set/ZSet/Hash
    struct dictEntry *next; //指向鏈表中下一個dictEntry指針
} dictEntry;
  • hashtable跟全局哈希表類似，也是采用兩個哈希表dictht + 漸進式rehash的方案

6. skiplist

有序鏈表只能逐一查找元素，導致操作起來非常緩慢，于是就出現(xiàn)了跳表。跳表在鏈表的基礎上，增加了多級索引，通過索引位置的幾個跳轉，實現(xiàn)數據的快速定位。大部分情況下，跳躍表的效率可以等同于平衡樹，但是跳躍表的實現(xiàn)卻遠遠比平衡樹的實現(xiàn)簡單，所以Redis選擇了使用跳躍表來實現(xiàn)有序集合;


redis-skiplist.png
/* 有序集合 */
typedef struct zset {
    dict *dict;       // 字典，鍵為成員，值為分值， 用于支持 O(1) 復雜度的按成員取分值操作
    zskiplist *zsl;   // 跳躍表，按分值排序成員，用于支持平均復雜度為 O(log N) 的按分值定位成員操作， 以及范圍操作
} zset;

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

/*  跳躍表節(jié)點 */
typedef struct zskiplistNode {
    robj *obj;                         // 成員對象
    double score;                      // 分值
    struct zskiplistNode *backward;    // 后退指針
    struct zskiplistLevel {            // 層
        struct zskiplistNode *forward; // 前進指針
        unsigned int span;             // 跨度
    } level[];
} zskiplistNode;
  • level[](層)：level即跳躍表中的層，是一個數組，也就是說一個節(jié)點的元素可以擁有多個層，即多個指向其他節(jié)點的指針，程序可以通過不同層級的指針來選擇最快捷的路徑提升訪問速度。level是在每次創(chuàng)建新節(jié)點的時候根據冪次定律隨機生成的一個介于1~32之間的數字。
  • forward(前進指針): 每個層都會有一個指向鏈表尾部方向元素的指針，遍歷元素的時候需要使用到前進指針。
  • span(跨度): 跨度記錄了兩個節(jié)點之間的距離,需要注意的是，如果指向了NULL的話，則跨度為0
  • backward(后退指針): 和前進指針不一樣的是后退指針只有一個，所以每次只能后退至前一個節(jié)點。
  • ele(元素): 跳躍表中元素是一個sds對象，元素必須唯一不能重復
  • score(分值): 節(jié)點的分值是一個double類型的浮點數，跳躍表中會將節(jié)點按照分值按照從小到大的順序排列，不同節(jié)點的分值可以重復。

小結

本文主要分析了redis底層用到的各種數據結構。redis是用 C 編寫，本文列舉的typedef struct可以類比java中實體對象，理解起來還是比較容易的
---------over---------

?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
【社區(qū)內容提示】社區(qū)部分內容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內容（如有圖片或視頻亦包括在內）由作者上傳并發(fā)布，文章內容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內容

  • 一、redis中數據對象 redis有五大數據類型, 通過統(tǒng)一對象redisObject存儲, redisObje...
    newbtao閱讀 673評論 0贊 0
  • 說明 說到Redis的數據結構，我們大概會很快想到Redis的5種常見數據結構：字符串(String)、列表(Li...
    TurboSnail閱讀 514評論 0贊 0
  • 1.演示數據類型的實現(xiàn) 上篇博客我們在介紹 key 相關命令的時候，介紹了如下命令： ``` OBJECT ENC...
    mkdlp閱讀 436評論 0贊 0
  • redis對象結構 注：本文基于redis3.0 redis是一種鍵值（key-value）數據庫，鍵的數據類型是...
    曉鑫_閱讀 473評論 0贊 0
  • 久違的晴天，家長會。 家長大會開好到教室時，離放學已經沒多少時間了。班主任說已經安排了三個家長分享經驗。 放學鈴聲...
    飄雪兒5閱讀 7,812評論 16贊 22

友情鏈接更多精彩內容